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

C 언어를 사용하여 100행 50열로 이루어진 행렬을 2차원 배열 A[100][50]에 저장하려고 한다. 10행 5열에 정수 값 15를 저장하는 방법으로 옳지 않은 것은?

다음과 같은 7개의 십진수를 입력받아 3단계(three passes)의 기수 정렬(Radix Sort)을 수행하여 오름차순으로 정렬하려고 한다.

379 － 508 － 706 － 193 － 984 － 155 － 133

두 번째 단계를 수행한 후 부분 정렬되어진 결과는?

다음과 같은 단순 연결 리스트(singly linked list)에 대해, 아래와 같은 C 언어로 작성된 프로그램을 수행한 후 포인터 tmp가 가리키는 노드는?

for (tmp ＝ L; tmp → link !＝ p; tmp ＝ tmp → link);
tmp → link ＝ p → link;

다음과 같은 9개의 데이터를 순서대로 입력하여 생성한 이진 탐색 트리(binary search tree)의 높이는?

(단, 루트(root)의 레벨은 1이다)

17, 10, 22, 15, 13, 24, 20, 11, 14

이중 연결 리스트(doubly linked list)에서 포인터 p가 가리키는 노드의 왼쪽으로 포인터 newNode가 가리키는 노드를 삽입한다고 할 때, 연산의 순서가 바르게 나열된 것은?

(단, llink는 왼쪽 노드를 가리키는 포인터이고, rlink는 오른쪽 노드를 가리키는 포인터이다)

(가) p → llink ＝ newNode;

(나) p → llink → rlink ＝ newNode;

(다) newNode → rlink ＝ p;

(라) newNode → llink ＝ p → llink;

다음은 C 언어로 작성된 프로그램의 일부이다. 이 프로그램의 시간 복잡도는?

for (i ＝ 1; i < n; i++) {
	m ＝ 1;
	while (m < i) m ＝ m * 2;
}

다음과 같은 원형 큐(circular queue)에 대해 ‘가’에서 ‘바’까지의 연산들을 차례대로 수행했을 때, 수행이 완료된 후 큐의 상태는?

(단, 현재 상태에서 front ＝ 0, rear ＝ 2이며, front에서는 삭제, rear에서는 삽입이 일어난다)

가. 원소 C 삽입 다. 두 개의 원소 삭제 마. 하나의 원소 삭제

나. 원소 D 삽입 라. 원소 E 삽입 바. 원소 F 삽입

다음 중 중위(infix) 표기식과 그에 대응하는 후위(postfix) 표기식이 일치하지 않는 것은?

중위표기식 후위표기식

다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 차례대로 삽입하여 최대 힙(max heap)을 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?

4, 16, 57, 9, 32, 45, 20, 19

N 개의 원소를 가지는 배열을 합병 정렬(Merge Sort) 알고리즘으로 정렬하고자 한다. 이 알고리즘에서 값을 비교하는 횟수를 $C(N)$이라고 할 때, 순환식(recurrence equation)으로 표현된 $C(N)$과 시간복잡도는?

(단, $N=2^k$이고, $C(1)=0$이라고 가정한다)

$C(N)$ 시간복잡도

일반 리스트 L ＝ (e₁, e₂, …, e_n)에서 head(L)은 첫 번째 원소인 e₁이고, tail(L)은 첫 번째 원소를 제외한 나머지 리스트 (e₂, …, e_n)으로 정의된다고 할 때, 일반 리스트 L ＝ ((a, (b, c)), (d, e), ((f, g), h))에서 head(tail(head(L)))의 값은?

어떤 이진 트리(binary tree)를 전위 순회(preorder traversal)한 결과는 1, 2, 3, 4, 5, 6, 7, 8, 9이고, 중위 순회(inorder traversal)한 결과는 2, 3, 1, 5, 4, 7, 8, 6, 9라고 할 때, 이 이진 트리는?

다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive transitive closure) 행렬 D^*를 인접 행렬로 바르게 표현한 것은?

다음 중 AVL 트리가 아닌 것은?

각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 대해 ‘갑’과 ‘을’의 두 가지 정렬 기법으로 정렬을 수행했을 때 다음과 같은 시간이 소요되었다.

정렬 기법 데이터 세트	갑	을
A	0.21초	0.40초
B	6.71초	0.39초

‘갑’과 ‘을’이 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 힙 정렬(Heap Sort) 중의 하나라면, 바르게 나열된 것은?

갑 을

다음과 같은 그래프에서 Sollin 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구하려고 한다. Sollin 알고리즘의 시작 단계에서는 하나의 정점으로 이루어진 트리들로 구성된 포리스트(forest)에서 각 트리의 최소 비용 간선(edge)을 선택하게 된다. 하나의 정점으로 이루어진 트리에 대한 최소 비용 간선을 선택할 때, 선택되는 간선이 아닌 것은?

다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색(Depth First Search)을 수행할 경우 나타날 수 없는 순서는?

크기가 7(M ＝ 7)인 해시 테이블(hash table)에 이중 해싱(double hashing) 기법을 사용하여 데이터를 삽입한다고 하자. 첫 번째 해시 함수(hash function)는 h₁(k) ＝ k mod M이고, 충돌이 발생할 경우 사용하는 두 번째 해시 함수는 h₂(k) ＝ 5 － (k mod 5)이다. 이러한 해시 함수를 사용하여 다음과 같은 탐색 키들을 차례대로 삽입한다고 할 때, 삽입이 완료된 후 해시 테이블의 상태는?

1, 15, 3, 6, 10

다음은 이진 탐색 트리(binary search tree)에서 최소 키 값을 가지는 노드에 대한 포인터를 반환하는 함수를 C 언어로 구현한 프로그램의 일부이다. ( 가 )와 ( 나 )부분에 해당되는 문장이 바르게 나열된 것은?

struct TreeNode  {
	int data;
	struct TreeNode *Left;
	struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;
SearchTree FindMin(SearchTree T)
{
	if (T == NULL) return NULL;
	else if (T → Left == NULL)    ( 가 )   
	else    ( 나 )   
}

( 가 ) ( 나 )

AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 이른 시간(earliest time)과 가장 늦은 시간(latest time)을 각각 나타내는 early(i)와 late(i)를 구하고자 한다. 가장 이른 사건 발생 시간(earliest event occurrence time)을 earliest라고 하고, 가장 늦은 사건 발생 시간(latest event occurrence time)을 latest라고 할 때, 작업 a_i가 간선 <k, l>로 표현된다면, 다음 식으로부터 early(i)와 late(i)를 구할 수 있다.

early(i) ＝ earliest[k]

late(i) ＝ latest[l] － 작업 a_i의 작업 시간(duration)

다음과 같은 AOE 네트워크에서 early(i)와 late(i)를 구한 결과 중 옳지 않은 것은?