자료구조 중간고사

2002. 4. 23 (화)

담당교수: 박 정흠

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

(a) [eqn: f(n) = O(g(n))]이라는 것의 정의를 엄밀히 말하시오.

(b) 위의 정의에 따라 [eqn: 3 n^3 + 2n^2 + 10 = O(n^3 )]임을 보이시오.

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]이고 길이는 부분 수열에 속한 원소의 수 [eqn: j-i+1]이다. 이 수열이 배열 A[n]에 보관되어 있고 [eqn: k (1 le k le n)]가 주어져 있다고 할 때, 길이가 [eqn: k]인 부분 수열 중에 크기가 최대인 부분 수열을 구하는 효율적인 알고리즘을 설계하시오.

(a) 설계한 알고리즘을 우리말로 간략히 설명한 다음 기술하시오.

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

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

다항식 poly에 한 개의 항 [eqn: a x^b]을 가진 다항식을 더하는 함수를 C 언어로 작성하시오. 이 때 함수명은 padd(poly, a, b)라고 한다. 이 연산이 일어나고 난 뒤에 노드의 수가 줄어들거나 늘어날 수 있음에 유의한다.

4. (30점) 후위 표기 연산식(postfix expression)이 주어져 있을 때, 이 연산식을 계산하는 알고리즘 설계하시오. 단 연산식에 나타나는 operand는 모두 정수이고, 연산자는 사칙연산자 +, -, *, / 와 지수연산자 ^만 있다고 가정한다.

(a) 설계한 알고리즘을 우리말로 엄밀하게 기술하시오.

(b) 위 알고리즘의 시간잡도를 분석하시오.

(c) 만약 전위 표기 연산식(prefix expression)이 주어져 있다면, 어떻게 계산할 수 있을까? 당신의 아이디어를 간략히 설명하시오.