알고리즘의 조건에 대한 설명으로 옳은 것만을 모두 고르면?

1. 1

   ㄱ

2. 2

   ㄱ, ㄴ

3. 3

   ㄴ, ㄷ

4. 4

   ㄱ, ㄴ, ㄷ

해설

알고리즘의 수행 시간 분석에 대한 설명으로 옳지 않은 것은?

1. 1

   알고리즘의 수행 시간은 컴퓨터 성능에 관계없이 명확하게 정의되어야 한다.

2. 2

   알고리즘의 시간복잡도는 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.

3. 3

   최선의 경우의 알고리즘 수행 시간은 모든 입력의 수행 시간에 대한 상한이 된다.

4. 4

   알고리즘의 수행 시간 분석에는 최악의 경우, 평균의 경우, 최선의 경우가 있다.

해설

다음은 그래프에서 너비 우선 탐색(breadth first search) 알고리즘이 동작하는 과정이다. (가)~(다)에 들어갈 내용을 바르게 연결한 것은?

1. 1

   

2. 2

   

3. 3

   

4. 4

   

해설

입력 크기 n에 대한 수행 횟수를 빅오(big-oh) 표기법으로 표현했을 때 옳지 않은 것은?

1. 1

   

2. 2

   

3. 3

   

4. 4

   

해설

다음 의사코드(pseudo code)가 설명하는 정렬 알고리즘은?

1. 1

   버블 정렬(bubble sort)

2. 2

   삽입 정렬(insertion sort)

3. 3

   선택 정렬(selection sort)

4. 4

   퀵 정렬(quick sort)

해설

다음 fib() 함수는 피보나치 수열을 계산한다. fib(6)을 실행할 때, fib() 함수의 호출 횟수는? (단, fib(6)의 호출은 제외한다)

1. 1

   21번

2. 2

   22번

3. 3

   23번

4. 4

   24번

해설

(가)~(다)에 들어갈 점근 표기법은?

1. 1

   

2. 2

   

3. 3

   

4. 4

   

해설

1. 1

   power(x, n);

2. 2

   power(x, n-1);

3. 3

   power(x-1, n);

4. 4

   power(x-1, n-1);

해설

힙 정렬(heap sort)을 수행하기 위해 다음 데이터를 왼쪽부터 차례대로 하나씩 삽입하여 최소힙(min heap)을 구성하였다. 이후 루트를 한 번 삭제하고 최소힙 특성을 유지하기 위해 재조정한 후, 루트의 왼쪽 자식 노드의 값은?

1. 1

   3

2. 2

   4

3. 3

   5

4. 4

   6

해설

다음 조건으로 퀵 정렬(quick sort)을 수행할 때, 처음 데이터 교환이 발생하는 배열의 인덱스 쌍은?

1. 1

   1, 8

2. 2

   2, 6

3. 3

   2, 7

4. 4

   3, 8

해설