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

1. (20점) 다음 질문에 답하시오.

(a) 이라는 것의 정의를 엄밀히 말하시오.

(b) 위의 정의에 따라 임을 보이시오.

2. (20점) 배열을 이용하여 환형 큐를 구현하고자 한다. head는 큐에서 삭제가 일어나는 끝을 나타내고 tail은 삽입이 일어나는 끝을 나타내기로 한다. 적절한 구현 방식을 구상한 다음 아래 물음에 답하라.

(a) 큐에 3개의 원소 A, B, C가 있는 경우를 그림으로 나타내시오. 이 때 반드시 head와 tail이 그림에 나타나야 한다.

(b) 큐가 꽉찬(full) 경우 head와 tail의 관계식은 무엇인가? 그리고 비어있는(empty) 경우를 어떻게 알 수 있는가?

(c) 큐에 새로운 원소를 삽입하는 함수 enqueue()와 삭제하는 함수 dequeue()를 C 언어를 사용하여 작성하시오.

3. (20점) 헤드 노드(head node)가 있는 단순 연결 리스트(singly linked list)를 이용하여 다항식을 다음과 같이 표현하였다. 노드 하나는 한 개의 항을 표현하는데, 이를 위해서 각 노드는 coef, exp, 그리고 link 필드를 가지는 레코드이고, coef 필드는 항의 계수를 exp 필드는 지수를 보관한다. 계수가 0인 항은 표시하지 않고, 지수가 높은 항부터 낮은 항의 순서로 보관하고 있다. 예를 들어 다항식 [eqn: p(x) = 3 x^8 - 2x^3 + 7]을 표현하면 다음과 같고 헤드 노드의 주소는 변수 p가 가지고 있다. 지수가 인 항의 계수를 넘겨주는 함수 poly()를 C 언어로 작성하시오.

4. (20점) 다음 질문에 답하시오.

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

(b) 이진 트리에서 분지수(degree)가 2인 노드의 수를 , 분지수가 0인 리프(leaf) 노드의 수를 라고 할때, 임을 증명하시오.

(c) 노드의 개수가 인 이진 트리의 높이(height)의 하한값은 무엇인가? 근거를 밝히시오.

5. (20점) 변수와 이진 연산자 +, -, *, /로 이루어진 수식(expression)이 있다. 이 수식은 오른쪽 그림과 같이 수식 트리(expression tree)를 이용하여 나타낼 수 있다. 이 때 변수들은 수식 트리의 리프를 이루고, 연산자들은 분지수가 2인 노드를 이룬다. 수식 트리를 중순위 운행(inorder traversal)하여 노드를 방문하는 순서대로 노드에 보관되어 있는 변수와 연산자를 출력하면 어떤 경우는 옳은 infix expression을 얻을 수 있지만, 그렇지 않을 수도 있다. 그렇지만 연산자 하나당 한쌍의 괄호 ‘(’, ‘)’를 추가하면 완전히 괄호로 묶은 수식(fully parenthesized expression)을 얻을 수 있다. 수식 트리가 주어져 있을 때, 이것으로부터 완전히 괄호로 묶은 수식을 출력하는 함수 fpe()를 C 언어로 작성하시오. 수식 트리는 링크를 이용하여 표현되어 있고 각 노드는 left_child, data, right_child의 세 필드를 갖고 있다고 가정하고, 루트 노드의 주소는 ptr이 가지고 있다고 하자. 위의 예에 대한 출력은 이거나 혹은 이다.