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

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

(a) 최대 힙(max heap)

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

2. (20점) 개의 정점을 가진 (무향) 그래프가 인접 리스트(adjacency list)로 표현되어 있다. 그리고 특정한 정점 가 주어져 있다.

(a) 와 인접한 노드의 수, 즉 의 분지수를 구하는 알고리즘을 기술하시오.

(b) 를 지나는 사이클, 즉 를 포함하는 사이클을 하나 찾아 출력하는 알고리즘을 기술하시오. 그런 사이클이 존재하지 않으면 ‘-1’을 출력한다. 사이클은 정점의 열로 나타낸다.

3. (20점) 이진 트리의 중순위 운행열(inorder sequence)과 후순위 운행열(postorder sequence)은 이진 트리를 유일하게 결정한다고 알려져 있다. 그러면 이진 트리의 중순위 운행열과 레벨순위 운행열(level-order sequence)이 주어지더라고 이진 트리를 유일하게 결정하는가? 혹은 그렇지 않은가? 당신의 주장을 정당화하시오.

4. (25점) T를 이진 검색 트리(binary search tree)라고 하자. T는 링크를 이용하여 표현되어 있고 각 노드는 left_child, data, right_child의 세 필드를 갖고 있다.

(a) T에서 data값이 K인 노드를 찾아 그 주소를 반환하는 효율적인 알고리즘을 기술하시오. data값이 K인 노드가 존재하지 않으면 null을 반환하도록 한다.

(b) T에서 data값이 K보다 작은 것 중 최대인 노드를 찾아 그 주소를 반환하는 효율적인 알고리즘을 기술하시오. 이때 모든 노드가 K와 같거나 크면 null 값을 반환하도록 한다.

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

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

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

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