자료구조 기말고사

□98. 6. 16

담당교수: 박 정흠

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

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

(b) 해쉬 함수(hash function)

(c) 힙(heap)

(d) 깊이 우선 검색(depth first search)

2(15). 오른쪽에 있는 이진 트리(binary tree)를 보고 물음에 답하시오.

(a) 중순위 운행(inorder traversal)의 결과를 보이시오. 각 노드를 방문할 때 그 노드 값을 출력한다고 가정한다.

(b) 중순위 운행 알고리즘을 기술하시오. 이 때 가급적 효율적인 알고리즘을 작성하시오.

(c) 위에서 작성한 알고리즘의 시간 복잡도를 분석하시오.

3(15). 그래프 표현의 대표적인 경우로 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)가 있다.

(a) 오른쪽에 있는 그래프를 위의 두 방식으로 표현하여 보시오.

(b) 위 각각 표현 방식에서 분지수(degree)가 최대인 정점(vertex)을 찾는 연산을 우리말로 기술하고 시간 복잡도를 말하시오.

4(20). 오른쪽에 있는 그래프에서 최소 스패닝 트리(minimum spanning tree)를 구하고자 한다.

(a) Krusakal의 알고리즘이 진행하는 과정을 각 단계별로 표시하시오.

(b) Kruskal의 알고리즘에서 어떤 자료 구조를 사용하면 효율적으로 구현할 수 있을까? 이 때 시간 복잡도는 얼마인가?

5(15). Dijkstra의 최단 경로 알고리즘은 에지에 주어진 가중치가 음수가 아닌 경우에 정상적으로 작동한다. Dijkstra의 알고리즘이 잘못된 결과를 출력하는 그래프를 제시하고, 그 그래프에서 Dijkstra 알고리즘의 수행 과정을 보이시오.

6(15). 높이가 [eqn: h]인 AVL 트리는 최소한 [eqn: F_h+3 - 1]개의 노드를 가짐을 증명하시오. 여기서 [eqn: F_n]은 피보나치 수로 다음과 같이 정의된다.

[eqn: F_0 = 0]; [eqn: F_1 = 1]; [eqn: F_n = F_n-1 + F_n-2, n ge 2]