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

1. (15점) UNION-FIND 자료구조에서 union 연산과 find 연산이 어떻게 구현될 수 있는 지를 우리말로 간략히 설명하시오. 설명에는 가중치 법칙(weighting rule), 경로 압축(path compression)을 반드시 포함시키시오.

2. (15점) 해쉬 함수(hash function)가 갖추어야할 요건에는 어떤 것이 있는지 말하고, 본인의 주장을 정당화하시오.

3. (20점) n개의 정점을 가진 그래프가 인접 리스트(adjacency list)로 표현되어 있다. 이 그래프에서 정점의 수가 최대인 최대 연결된 요소(maximum connected component)를 찾아서 그 요소에 포함되는 정점을 모두 출력하는 효율적인 프로그램을 작성하고, 시간복잡도를 분석하시오. 각 노드에 해당하는 리스트의 헤드 노드는 배열 graph[]에 있다고 가정한다.

4. (25점) 주어진 이진 트리가 AVL 트리인지 아닌지를 판별하는 효율적인 프로그램을 제시하고, 시간복잡도를 분석하시오. 이진 트리가 AVL 트리가 되기 위해서는 우선 이진 검색 트리가 되어야 하고, 각 노드의 대해서 균형 인자(balance factor)가 -1, 0, 1 중 하나의 값을 가져야 한다. 이진 트리는 링크를 이용하여 표현되어 있고, 각 노드는 left, data, right 세 필드를 가지며, 루트 노드의 주소는 포인터 변수 bt가 보관하고 있다고 가정한다.

5. (25점) n개의 노드를 가진 최대 힙(max heap)에서 임의의 한 노드의 priority를 바꾸는 효율적인 프로그램을 제시하고 시간복잡도를 분석하시오. 힙은 배열 A[]를 이용하여 표현되어 있다고 가정한다. priority를 바꾸어야할 노드의 인덱스는 k로 이미 알고 있다고 가정하고, 노드의 값을 new로 바꾸기로 한다.