자료구조 기말고사

2002. 6. 18 (화)

담당교수: 박 정흠

1. (20점) 다음을 간략히 설명하시오.

(a) UNION-FIND 구조의 가중치 법칙(weighting rule)과 경로 압축(path compression)

(b) 해슁(hashing)의 충돌(collision)과 오버플로우(overflow)

2. (15점) 다음 질문에 답하시오.

(a) 최대 힙(max heap)의 정의를 말하시오.

(b) 최대 힙에서 최대값은 루트에 보관되어 있다. 최대값을 삭제하는 알고리즘을 기술하고,시간복잡도를 분석하시오. 최대 힙의 노드 수를 이라고 한다.

3. (15점) 다음 질문에 답하시오.

(a) AVL 트리의 정의를 말하시오.

(b) AVL 트리에서 한 원소를 삽입하는 알고리즘을 우리말로 명확히 말하고, 시간복잡도를 분석하시오. AVL 트리의 노드 수를 이라고 한다.

4. (20점) 어떤 그래프 가 주어져 있을 때, 가 트리(tree)인지 아닌지를 판별하는 효율적인 알고리즘을 설계하고 분석하시오. 트리는 연결되어 있고(connected) 사이클이 없는(acyclic) 그래프라고 정의된다. 단, 그래프는 인접 리스트(adjacency list)로 표현되어 있다고 가정한다.

5. (30점) 이진 트리 에서 두 노드 사이의 거리는 두 노드를 잇는 경로(path)의 길이, 즉 경로에 포함된 에지(edge)의 수라고 정의한다. 트리에서 두 노드를 잇는 경로는 유일함에 유의한다. 이진 트리의 지름(diameter)은 거리가 최대가 되는 두 노드간의 거리를 말한다. 트리 의 지름을 구하는  시간 알고리즘을 설계하고 분석하시오. 거리가 최대인 두 노드를 잇는 경로가 반드시 루트 노드를 지나지 않을 수 있음에 유의한다.