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

1. (15점) 다음 각각에 대해 간략히 설명하시오.

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

(b) Union-Find 구조에서 경로 압축(path compression)

(c) 해쉬 함수(hash function)

2. (20점) 그래프의 분지수(degree)는 정점들의 분지수의 최대값을 말한다. 그래프 [eqn: G]의 정점의 개수를 [eqn: n], 에지의 개수를 [eqn: m]이라고 하자. 그래프 [eqn: G]의 분지수(degree)를 구하는 효율적인 알고리즘을 기술하시오. 그리고 [eqn: G]가 각각 인접 리스트(adjacency list)와 인접 행렬(adjacency matrix)로 표현되어 있을 때 제시한 알고리즘의 시간복잡도를 분석하시오.

3. (20점) 최대 힙(max heap)은 삽입(Insert)와 최대값 삭제(DeleteMax) 연산을 제공하는 자료 구조이다. 다음 물음에 답하시오.

(a) 최대 힙의 DeleteMax 연산 알고리즘을 기술하시오.

(b) 위 (a)에 기술된 DeleteMax 알고리즘이 옳게 동작함을 보이고, 시간복잡도를 분석하시오. 최대 힙에는 [eqn: n]개의 원소가 있다고 가정한다.

4. (20점) AVL 트리에서 노드 하나를 삽입하였더니 삽입된 노드가 에 포함되게 되어 노드 C의 균형 인자(balance factor)가 +2가 되었다. 오른쪽 그림은 C를 루트로 하는 부그래프를 보여주고 있고, 노드 C를 제외한 다른 노드의 균형 인자는 모두 -1, 0, 혹은 1이다.

(a) AVL 트리 삽입 알고리즘을 따르면 어떤 회전(rotation)이 일어나게 되는데, 그 회전이 일어나고 난 후의 AVL 트리를 해당 부분만 그려 보이시오.

(b) 이 때 노드 A, B, C의 균형 인자는 모두 -1, 0, 혹은 1이 되며, 또한 해당 부분의 부트리 높이는 회전이 일어나기 전과 비교할 때 정확히 하나 줄어든다는 사실을 증명하시오.

5. (25점) 그래프 [eqn: G(V,E)]에 서로 다른 두 정점 [eqn: s]와 [eqn: t]가 주어져 있고, [eqn: s]와 [eqn: t]를 포함하지 않는 정점 부분집합 [eqn: F```( SUBSET V)]가 주어져 있다.

(a) [eqn: F]에 속한 정점을 중간 정점으로 지나지 않으면서 [eqn: s]와 [eqn: t]를 잇는 경로가 존재하는지를 판별하고, 존재하는 경우 그 중 하나를 찾아주는 효율적인 알고리즘을 기술하시오.

(b) 위 (a)에서 제시한 알고리즘이 옳게 동작함을 보이고 시간복잡도를 분석하시오.

(c) 만약 위 (a)에서 [eqn: F]에 속한 정점을 지나지 않는 경로가 여럿 있을 때, 그 중 가장 짧은 즉 지나는 에지의 수가 최소인 경로를 찾고자 한다. 이 문제에 대한 아이디어를 간략히 기술하시오.

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