자료구조 중간고사

□98. 4. 21

담당교수: 박 정흠

1. (20) 리스트 자료구조는 배열을 이용하여 표현할 수도 있고, 연결 리스트를 이용하여 표현할 수도 있다. 위의 각 표현에 대하여 다음과 같은 연산을 어떻게 구현할 수 있는지를 우리말로 설명하고 시간 복잡도가 얼마가 되는지 설명하시오.

(a) k번째 원소를 새로운 원소로 교체하시오.

(b) k번째 위치에 새로운 원소를 삽입하라.

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

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

(b) 큐가 full인 경우 head와 tail의 관계식은 무엇입니까? 그리고 empty인 경우를 어떻게 알 수 있습니까?

(c) 큐에 새로운 원소를 삽입하는 함수 enqueue()와 삭제하는 함수 dequeue()를 작성하시오. 알고리즘은 C 언어를 사용하여 작성하시고, 그렇지 않을 때는 어떤 언어를 사용하는지를 밝히시오.

3. (20) 길이가 각각 n, m인 두 리스트 A, B가 다음과 같이 주어져 있고, 이들은 해드 노드가 있는 이중 연결 리스트(doubly linked list)로 구현되어 있다고 하자.

[eqn: A = (a_1 , a_2 , a_3 , ... , a_n )],  [eqn: B = (b_1 , b_2 , b_3 , ... , b_m )]

이 두 리스트를 합병하여 하나의 이중 연결 리스트를 만드는 알고리즘 merge(A,B)를 구현하시오. 이 때 merge(A,B)를 수행하고 나면 두 리스트는 아래와 같이 나타나게 된다.

[eqn: A = (a_1 , a_2 , a_3 , ... , a_n , b_1 , b_2 , b_3 , ... , b_m )],  [eqn: B = ()]

이 때 가급적이면 효율적인 방식으로 알고리즘을 작성하시오. 그리고 시간 복잡도를 분석하시오. 알고리즘은 C 언어를 사용하여 작성하시고, 그렇지 않을 때는 어떤 언어를 사용하는지를 밝히시오.

4. (20) 길이가 n인 수열이 주어져 있을 때, 최대 부분 수열의 합을 구하는 알고리즘을 우리말로 제시하시오. 이 때 알고리즘은 반드시 순환(recursion)을 이용하여 작성하시오. 그리고 제시한 알고리즘의 시간 복잡도를 분석하시오.

5. (20) 다음과 같은 기하 물체(geometric object)를 위한 자료주조를 제안하시오. 그리고 두 기하 물체가 교차하는지 아닌지를 (예를 들면, 아래 문제 (a)인 경우 두 직사각형의 교집합이 공집합인지 아닌지) 판별하는 알고리즘을 제시하고 시간 복잡도를 분석하시오.

(a) 선분이 모두 X-축이나 Y-축에 평행한 직사각형

(b) 원판(디스크)