자료구조 기말고사

담당교수: 박 정흠

1. (15점) 다음의 정의를 간략히 말하시오.

(a) AVL 트리

(b) 힙(heap)

(c) 후위 표기법(postfix notation)

2. (15점) 희소 행렬(sparse matrix)을 row, col, value의 세 필드를 가진 레코드의 배열로 표현하고자 한다. 아래 그림 (a)와 같은 [eqn: 4 times 4] 행렬이 주어지면, 그림 (b)와 같이 값이 0이 아닌 원소들만 그것의 행 인덱스, 열 인덱스, 그리고 값으로 나타낸다. A[0].row는 행렬의 행의 수, A[0].col은 열의 수, 그리고 A[0].value에는 0이 아닌 원소의 수가 저장되어 있다.  희소 행렬 A, B가 이와 같은 표현으로 주어질 때, 두 행렬의 합을 구하는 알고리즘을 제안하시오. 알고리즘의 기본적인 아이디어를 먼저 간략히 설명하고, C언어로 구현된 프로그램의 부분을 보이시오.

3. (20점) 아래 그림 (c)에 있는 이진 트리에 대하여 질문에 답하시오.

(a) 중순위 운행(inorder traversal)에서 방문되는 노드의 순서를 보이시오.

(b) 후순위 운행(postorder traversal)에 대해서 위 (a)의 질문에 답하시오.

(c) 일반적으로 이진 트리의 중순의 운행 순서와 후순위 운행 순서가 주어져 있을 때 원래의 이진트리를 복구할 수 있는지를 말하고, 주장을 정당화 하시오.

4. (20점) 아래 그림 (d)에 있는 그래프에서 Prim의 알고리즘이 최소 스패닝 트리를 구하는 과정을 보이시오. 이 때 정점 3을 선택하여 알고리즘이 시작된다고 가정한다. 그리고 Prim의 알고리즘의 시간 복잡도가 [eqn: O(n^2 )]이 됨을 보이시오.

5. (15점) 깊이 우선 검색(DFS) 알고리즘을 제시하시오. 그리고 그림 (d)에 있는 그래프에 대해서 정점 0에서 시작하여 DFS 알고리즘이 실행되는 과정을 보이시오.

6.[eqn: PMATRIX { { 0}& {0 }& {11 }& {0}# { 12}& { 0}& {0 }& {0 }# {0 }& {-4 }& {0 }& {0 }# { 0}& {0 }& {0 }&{0 } }] (15점) m-차 검색 트리(m-way search tree)란 무엇인지 정의를 말하시오. 그리고 검색(search) 알고리즘을 제안하고 시간복잡도를 분석하시오.

	row	col	value
A[0]	4	4	3
A[1]	1	3	11
A[2]	2	1	12
A[3]	3	2	-4

(a)	(b)

.

(c)	(d)