자료구조 중간고사

2003. 4. 23 (수)

1. (20점) 길이 인 리스트 와 길이 인 리스트 가 있다. 이 리스트 원소들은 이미 오름차순으로 정렬되어 있고 각각 배열 A[n], B[m]에 보관되어 있다. 아래에 두 리스트를 묶어서 하나의 정렬된 리스트를 생성하는 알고리즘이 있다. 이 알고리즘의 시간복잡도를 분석하시오. 분석 과정을 엄밀히 그리고 충분히 자세하게 기술하시오.

i=0; j=0; k=0;

while ((i < n) && (j < m)) {

if (A[i] <= B[j]) {C[k] = A[i]; i++; k++;};

else {C[k] = B[j]; j++; k++;}

}

while (i < n) {

C[k] = A[i]; i++; k++;

}

while (j < m) {

C[k] = B[j]; j++; k++;

}

2. (25점) 길이 [eqn: n]인 정수의 수열 [eqn: a_0 , \ a_1 , \ a_2 , \ cdots , \ a_n-1]이 있다. 부분 수열 [eqn: [i,j]]라는 것은 [eqn: a_i , \ a_{i+1} , \ cdots , \ a_j]를 말하고, 이 부분 수열의 크기는 [eqn: sum_{i leq k leq j} a_k]이다. 이 수열이 배열 A[n]에 보관되어 있다고 할 때, 음수를 포함하지 않거나 혹은 하나만 포함하는 부분 수열 중에 크기가 최대인 부분 수열을 구하고자 한다.

(a) 효율적인 알고리즘을 설계하여 우리말로 엄밀하게, 혹은 C/C++ 언어로 기술하시오.

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

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

(a) 다항식 p에 한 개의 항 [eqn: a x^b]을 가진 다항식을 곱하여 얻은 다항식을 이와 같은 형식으로 표현하고 그 헤드 노드의 주소를 되돌려 주는 함수를 C/C++ 언어로 작성하시오. 이 때 함수명은 pmul_one(p,a,b)라고 하고, 다항식 p는 변경하지 않고 그대로 유지한다.

(b) 위와 같은 형식으로 표현된 두 다항식을 더하여 헤드 노드의 주소를 반환하는 함수 padd(f,g)를 작성하시오. 이때 다항식 f, g는 더 이상 유지하지 않고 삭제한다. 이 경우 계수가 0인 항이 발생할 수 있음에 유의한다.

(c) 위에서 작성한 두 함수를 이용하여 두 다항식 p, q를 곱하여 헤드 노드의 주소를 반환하는 함수 pmul(p,q)을 작성하시오. 단 다항식 p, q는 변경하지 않고 그대로 유지한다.

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

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

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

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