자료구조 중간고사
2006. 4. 25 (화)	담당교수: 박 정흠	소속:	성명:

1. (15점) 해드 노드가 있는 단순 연결 리스트(singly linked lists)를 이용하여 스택(stack)을 표현하고자 한다. 연결 리스트의 양끝 중 어느 쪽을 top으로 정하는 것이 좋을지를 말하고, 주장을 정당화하시오.

2. (15점) 선형 리스트(linear lists)를 배열(arrays)을 이용하여 표현할 수도 있고 연결 리스트(linked lists)를 이용할 수도 있다. 각 표현 방법의 장단점을 비교 설명하시오.

3. (20점) 아래 각각이 옳음을 정의에 따라 엄밀하게 보이시오.

(a)

(b)

4. (20점) 아래 그림과 같이 희소 행렬을 0이 아닌 원소들에 대해서 그 원소의 행 번호, 열 번호, 원소값을 가지는 배열로 표현할 수 있다. 배열의 첫줄에는 표현하고자 하는 행렬의 행의 수, 열의 수, 그리고 0이 아닌 원소의 수를 보관한다. 0이 아닌 원소들은 행 번호가 작은 것이, 행 번호가 같을 때에는 열 번호가 작은 것이 먼저 나타난다고 가정한다. 이와 같은 형식으로 표현된 두  행렬 A, B가 있을 때, 두 행렬의 합 C를 구하는 알고리즘을 설계하시오. C도 A, B와 같은 형식으로 표현하기로 하고, 각 행렬을 나타내는 배열 이름을 각각 A, B, C라고 한다.

(a) 설계한 알고리즘을 우리말로 설명한 다음 C/C++ 언어로 기술하시오.

row	col	value
4	5	6
0	0	3
0	3	2
2	2	1
2	3	1
2	4	5
3	1	2

(b) 제시한 알고리즘의 시간복잡도를 분석하시오. A와 B에서 0이 아닌 원소들의 수를 각각 a, b라고 한다.

5. (30점) 후위 표기법(postfix notation)으로 표현된 수식이 있다. 수식은 문자 하나로 나타낸 변수와 이진 연산자 +, -, *, /로 구성되어 있다고 가정한다. 수식을 오른쪽 그림과 같이 수식 트리(expression tree)라고 부르는 이진 트리로 나타낼 수 있는데, 수식 트리에서 변수들은 리프를 이루고, 연산자들은 분지수가 2인 노드를 이룬다.

(a) 후위 표기 수식이 입력될 때, 그에 해당하는 수식 트리를 생성하여 루트의 주소를 반환하는 함수 exp_tree()를 먼저 우리말로 설명한 다음 C/C++ 언어를 사용하여 작성하시오. 이 때 트리의 각 노드는 각각 연산자나 피연사자를 보관하기 위한 Data 필드, 그리고 왼쪽 자식과 오른쪽 자식의 주소를 보관하기 위한 Lchild, Rchild 필드를 가지고 있다.

(b) 위에서 작성한 함수가 항상 옳게 동작함을 보이고, 시간 복잡도를 분석하시오.