자료구조 기말고사
2005. 6. 15 (수)	담당교수: 박 정흠	소속:	성명:

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

(a) 최소 스패닝 트리(minimum spanning tree)

(b) 이진 검색 트리(binary search tree)

2. (10점) Union-Find 자료 구조에서 가중 법칙(weighting rule)과 경로 압축(path compression)에 대하여 간략히 설명하시오.

3. (20점) 개의 키가 배열 A[1..n]에 보관되어 있다고 하자.

(a) 배열 A에 보관된 개의 키로 최대 힙(max heap)을 구성하는 알고리즘을 설계하시오. 이때 가능한 효율적이고 메모리를 적게 사용하도록 설계하시오.

(b) 위에서 설계한 알고리즘은 항상 옳은 결과를 출력함을 보이고, 시간복잡도와 공간 복잡도를 분석하시오. 공간 복잡도를 분석할 때 배열 A의 공간은 무시하고 추가로 필요한 공간을 대상으로 하시오.

4. (20점) 에지 가중치가 모두 양수인 유향 그래프에서 최단 경로를 찾는 Dijkstra의 알고리즘이 알려져 있다. Dijkstra의 알고리즘이 항상 최단 경로를 찾을 수 있음을 증명하시오.

5. (20점) 를 임의의 무향 그래프(undirected graph)라고 하자. 의 에지들 중에서 그것을 에서 제거하였을 때 의 연결된 요소(connected component)의 수가 늘어나면 그 에지를 절단 에지(bridge)라고 부른다. 는 인접 리스트로 표현되어 있다고 하고, 의 정점의 수와 에지의 수를 각각 , 이라고 할 때 다음 물음에 답하시오.

(a) 그래프 의 한 에지 가 주어져 있을 때, 그것이 절단 에지인지 아닌지를 판별하는 효율적인 알고리즘을 설계하시오.

(b) 위에서 설계한 알고리즘이 항상 옳은 결과를 출력함을 보이고, 시간복잡도를 분석하시오.

6. (20점) AVL 트리 T의 각 노드는 Lsize 필드를 가지고 있으며 이 필드에는 그 노드의 왼쪽 부트리에 속한 노드의 수 + 1의 값을 가지고 있다고 가정하자. T의 각 노드는 Lsize 필드 이외에 각각 키, 왼쪽 부트리와 오른쪽 부트리의 주소를 보관하기 위한 Data, Lchild, Rchild 필드를 가지고 있다.

(a) T에서 번째로 작은 키를 반환하는 효율적인 알고리즘 avl_find(T,k)를 설계하시오. 인 경우 가장 작은 키를 찾는다.

(b) 위에서 설계한 알고리즘이 항상 옳은 결과를 얻을 수 있음을 보이고, 시간복잡도를 분석하시오.

※ 위 모든 문제에서 알고리즘은 우리말로 엄밀하게 혹은 C/C++ 언어로 기술하시오.