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

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

(a) AVL 트리(AVL tree)

(b) 힙(heap)

(c) -차 검색 트리(-way search tree)

(d) 연결 요소(connected component)

2. (20점) 이진 검색 트리에서 노드 하나를 삭제(Delete)하는 알고리즘을 기술하고 시간복잡도를 분석하시오. 단, 이진 검색 트리의 높이(height)를 라고 할 때 시간복잡도는 를 넘을 수 없다.

3. (20점) 를 평면 그래프(planar graph)라고 하자. 평면 그래프란 그래프의 에지들을 그 양끝 정점을 제외하고 서로 교차하지 않게 그릴 수 있는 그래프를 말한다. 정점의 수가 인 평면 그래프의 에지수는 개 이하라고 알려져 있다. 평면 그래프가 인접 리스트로 표현되어 있는 때 주어진 두 정점 사이의 거리를 구하는 효율적인 알고리즘을 제시하고 시간복잡도를 분석하시오. 두 정점을 잇는 경로의 길이는 그 경로가 지나는 에지의 개수라고 정의하며, 두 정점간의 거리는 최단 경로의 길이이다.

4. (20점) 최소 스패닝 트리를 찾는 알고리즘으로 Kruskal의 알고리즘이 널리 알려져 있다.

(a) Kruskal의 알고리즘의 개요를 우리말로 기술하시오.

(b) 위에서 기술한 알고리즘의 각 단계를 어떻게 구현하는 것이 좋을지 제안하시오. 그리고 제안된 방식을 모두 이용하였을 때 최종적인 알고리즘의 시간복잡도를 분석하시오.

5. (20점) 를 개의 정점 [eqn: v_0 , v_1 , v_2 , cdots , v_n-1]을 가진 (에지에 방향이 있는) 유향 그래프라고 하고, 의 비용 행렬을 cost라고 하자.

(a) [eqn: A^k [i][j]]를 중간에 인덱스가 [eqn: k] 이하인 정점 [eqn: \{ v_0 , v_1 , v_2 , cdots , v_k \}]만을 지날 수 있도록 허용될 때 정점 [eqn: v_i]에서 [eqn: v_j]까지 최단 경로의 길이라고 하자. 다음이 성립함을 보이시오:

[eqn: A^k [i][j] = min \{ A^k-1 [i][j], A^k-1 [i][k] + A^k-1 [k][j] \}]. 단, [eqn: A^-1 [i][j] = {\cost}[i][j]].

(b) 위 (a)의 관찰을 이용하여 모든 정점쌍에 대한 최단 경로를 구하는 알고리즘을 완성하고 시간복잡도와 공간복잡도를 분석하시오.

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