7급 국가직 자료구조론 2010년 기출문제

다음 AOE(activity on edge) 네트워크로 표현된 작업들은 병렬로 수행된다. 이 그래프에서 나타나는 임계 경로(critical path)는?

아래 코드는 가용공간 리스트로부터 노드를 할당 받아 이중연결리스트에 새로운 값 x를 삽입하기 위한 함수의 일부이다. 할당 받은 노드에 대한 포인터는 new이고, 이중연결리스트에서의 삽입 위치는 pre가 가리키는 노드 뒤라고 하자. 밑줄 친 ㉠, ㉡에 알맞은 문장은?

new ← getNode();

new.data ← x;

㉠

㉡

pre.rlink ← new;

new.llink ← pre;

㉠ ㉡

다음과 같은 키 값을 갖는 데이터들을 순서대로 삽입하여 AVL 트리를 구성했을 때, 이 트리에서 각 키를 탐색하기 위한 평균 비교횟수는?

8, 12, 23, 9, 7, 6

아래의 알고리즘은 주어진 단순연결리스트를 역순으로 변환하는 알고리즘이다. 알고리즘의 ㉠에 들어갈 내용으로 옳은 것은?

(단, 리스트의 시작 주소를 나타내는 포인터는 start이며 노드의 연결포인터 필드는 link이다)

p = start;
q = NULL;
while (p != NULL) { 
          ㉠      
    p = p->link; 
    q->link = r; 
}
start = q;

크기가 11인 해시 테이블이 있고, 해시함수로 h(k) ＝ k mod 11을 사용한다. 여기서 mod는 모듈로(modulo) 함수를 의미한다. 하나의 해시 값에 대해 두 개씩의 슬롯이 할당되어 있고, 오버플로가 발생하면 다음의 빈 슬롯에 저장하는 선형 조사법(linear probe)을 사용한다고 하자. 데이터가 다음과 같은 순서로 입력된다고 할 때, 원래 계산된 슬롯에 저장되지 않는 데이터의 개수는?

54, 27, 70, 55, 13, 2, 37, 23, 33, 44, 45, 77, 56, 6, 9

C 언어를 사용하여 연결리스트를 구현할 때, 관련이 없는 것은?

다음은 빈 상태의 힙(heap) 배열에 1 ～ 8까지의 키 순서로 삽입이 이루어질 때, 힙이 형성되는 과정을 순서대로 나타낸 그림이다. 빈 칸들에 알맞은 것은?

1

2 1

3 1 2

4 3 2 1

5 4 2 1 3

( )

7 4 6 1 3 2 5

( )

다음 중 트리에 대한 설명으로 옳은 것은?

n개의 식별자 (a₁, a₂, …, a_n)로 구성된 이진탐색트리에 n ＋ 1개의 외부 노드를 추가하여 확장 이진트리를 만들 수 있다. 각 a_i의 탐색 확률이 p_i이고, 각 외부 노드에 속하는 식별자, 즉 내부 노드에 있지 않은 식별자의 탐색 확률이 q_i일 때 주어진 이진탐색트리 T의 전체비용은 다음 식과 같다.

$\begin{array}{rl}\mathrm{cost}(T)=& \sum _{1\le i\le n}{p}_i\mathrm{level}(a_i)\\ & +\sum _{0\le i\le n}{q}_i(\mathrm{level}(\text{external node }i)-1)\end{array}$

전체 비용이 최소인 이진탐색트리를 최적 이진탐색트리라 한다. 3개의 식별자가 (a₁, a₂, a₃) ＝ (do, if, while)이고, (p₁, p₂, p₃) ＝ (0.1, 0.2, 0.5), (q₀, q₁, q₂, q₃) ＝ (0.05, 0.05, 0.05, 0.05)일 때, 최적 이진탐색트리는?

어떤 산술식을 표현한 이진트리에서 전위 순회를 한 결과가 －*AB/*CDE 이었다. 이 이진트리에서 후위 순회한 결과는?

다음 코드의 시간 복잡도를 바르게 나타낸 것은?

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j = j + i)
        for (k = 1; k <= n; k++)
            x = x + k + 1;

다음은 알고리즘의 복잡도 X를 위한 정의다. 어떤 복잡도에 대한 정의인가?

정의 : f(n)=X(g(n))

모든 n (n≥n₀)에 대해 f(n)≤cg(n)을 만족하는 두 양의 상수 c와 n₀가 존재하면 f(n)=X(g(n))이다.

m ＊ n 크기의 정수 값 희소행렬을 정수형 배열에 저장하고자 한다. 가장 효과적인 저장방법을 사용할 때, 필요한 배열의 크기는?

(단, t는 0이 아닌 희소행렬 원소의 개수이며, 배열의 크기는 배열 원소의 수를 의미한다)

정렬에 대한 설명으로 옳지 않은 것은?

행우선(Row major)으로 배열의 값을 저장하는 C 언어에서 3차원 배열 A[4][2][3]을 선언하였다. A[0][0][0]부터 A[3][1][2]에 정수 값 1 ～ 24를 행우선 순서에 따라 차례대로 저장할 때, A[2][1][2]에 저장되는 값은?

2 원 합병정렬에서 런(run)의 크기가 다를 경우, 런의 병합 순서에 따라 실행 속도의 차이가 발생한다. 초기 런의 수가 5개이며 각 런의 크기가 아래와 같을 때, 5개의 런을 하나로 병합하는 최소 시간은?

(단, 크기가 a, b인 두 개의 런을 병합하는 시간은 a ＋ b라고 가정한다)

런 이름	r1	r2	r3	r4	r5
크기	2	4	5	7	8

메소드 호출 xxx(5)에서 반환되는 결과는?

public static int xxx(int n) {
    if (n == 0)
        return 4;
    return 1 + xxx(n - 1);
}

그래프의 깊이우선탐색에 대한 설명으로 옳지 않은 것은?

다음 중 큐(queue)에 대한 설명으로 옳은 것은?

그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드－워샬 알고리즘은 아래의 식으로 표현된다.

$A^k[i][j]=\min \left\{A^{k-1}[i][j],A^{k-1}[i][k]+A^{k-1}[k][j]\right\}$, $k>0$

$A^0[i][j]=\cos t[i][j]$

위의 식에서 $\cos t[i][j]$는 정점 $i$에서 정점 $j$로 가는 간선의 가중치를 나타내며, $A^k[i][j]$는 $k$보다 더 큰 인덱스를 갖는 정점을 통과하지 않으면서 $i$에서 $j$까지 갈 수 있는 최단 경로 비용을 나타낸다. 아래 그래프에 대해 행렬 $A^2$의 값으로 알맞은 것은?