자료구조 중간고사

2000. 4. 20 (목)

담당교수: 박 정흠

1. (20점) 아래 물음에 답하시오.

(a) [eqn: T(n) = O(n^2 )]이라는 것의 정의를 말하시오.

(b) [eqn: T(n) = n^2 +10n -5]라고 할 때, [eqn: T(n) = O(n^2 )]임을 위의 정의를 이용하여 보이시오.

2. (25점) A, B를 [eqn: n times n] 행렬이라고 하자.

(a) A, B를 곱하여 행렬 C를 구하는 알고리즘을 작성하시오. 알고리즘은 C 언어를 사용하여 작성하고, 그렇지 않을 때는 어떤 언어를 사용하는지를 밝히시오.

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

3. (30점) 다항식을 헤드 노드가 없는 환형 연결 리스트(circular linked list)를 이용하여 표현하기로 한다. 예를 들면 다항식 [eqn: p(x) = 3 x^14 + 2x^8 + 1]은 아래 그림과 같이 표현되어 있다. 각 노드는 coef, exp, link 필드로 구성되어 있다고 하자. ptr은 차수가 가장 높은 항을 가리키고 있고, 항은 차수에 대해서 내림차순으로 정렬되어 있다고 가정한다.

(a) 두 다항식 [eqn: f(x)], [eqn: g(x)]가 있을 때, 두 다항식의 합 [eqn: h(x) = f(x) + g(x)]를 구하는 알고리즘을 C 언어를 사용하여 작성하시오. 만약 [eqn: f(x) = 0]이라면 coef, link 필드가 모두 0인 노드 하나를 가지고 있어서 항상 ptr은 NULL이 아니라고 가정한다. 그리고 [eqn: f(x)], [eqn: g(x)]를 나타내는 리스트는 파괴하지 않는다고 가정한다.

(b) 만약 다항식을 환형 연결리스트를 사용하지 않고, 마지막 노드의 link 필드가 NULL 값을 가지고 있는 연결 리스트를 사용하여 표현했다면, (a)에서 제안한 알고리즘의 어떤 부분을 어떻게 수정하면 되는지 우리말로 자세히 설명하시오.

4. (25점)[eqn: n]개의 부울 변수 [eqn: x_1], [eqn: x_2], [eqn: cdots], [eqn: x_n]이 있다. 이 변수들이 가질 수 있는 모든 가능한 조합을 출력하는 문제를 고려하고 있다. 진리값 true는 1로, false는 0으로 표현하기로 한다. 예를 들어 [eqn: n=2]이면 다음과 같은 조합이 있다: 00, 01, 10, 11. 문제에서 이들 조합의 순서는 고려하지 않는다.

(a) 이 문제에 대한  순환(recursive) 알고리즘을 작성하시오.

(b) 위에서 작성한 알고리즘의 개요를 우리말로 설명하시오.

(c) [eqn: n=3]일 때 위에서 작성한 알고리즘의 출력을 보이시오.