자료구조 중간고사

2001. 4. 26 (목)

담당교수: 박 정흠

1. (20점) 길이 [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]에 보관되어 있다고 할 때, 원소 [eqn: a_m]을 포함하는 부분 수열 중에 크기가 최대인 부분 수열을 구하는 [eqn: O(n)] 시간 알고리즘을 제시하시오. 부분 수열 [eqn: [i,j]]가 [eqn: a_m]을 포함한다는 것은 [eqn: i le m le j]임을 의미한다.

2. (20점) 주이진 [eqn: n]개의 정수로 이루어진 리스트 [eqn: L]에서 최대값과 최소값을 찾기 위해서는 이 리스트를 크기의 차가 1 이하가 되도록 두 리스트 [eqn: L_1], [eqn: L_2]로 나눈 다음, 각 리스트에서 최대와 최소를 찾아서 두 최대 중에 더 큰 것을 [eqn: L]의 최대값으로, 두 최소 중에서 더 작은 것을 [eqn: L]의 최소값으로 출력하면 된다. 이 알고리즘의 시간복잡도를 분석하시오. [eqn: n = 2^k]이라고 가정하여도 좋다.

3. (30점) 아래 그림 (a)와 같은 희소 행렬을 그림 (b)와 같이 0이 아닌 원소만을 노드로 표현하는 linked representation이 있다. 행렬의 각 행과 열은 헤드 노드가 있는 환형 연결 리스트이고, 행을 나타내는 연결 리스트의 헤드 노드나 열을 나타내는 연결 리스트의 헤드 노드를 다시 환형 연결 리스트로 표현하고 있다. 행렬 전체에 대한 헤드 노드 주소를 포인터 변수 a가 가지고 있을 때, 이 행렬을 (a)와 같은 모양으로 출력하는 프로그램을 작성하시오. 즉, 행렬의 한 행을 한 줄에, 0인 원소를 포함하여 출력하며 큰 괄호는 무시한다.

그림 (a)	그림 (b)

4. (30점) 중위 표기 연산식(infix expression)을 후위 표기 연산식(postfix expression)으로 변환하는 알고리즘을 우리말로 엄밀하게 기술하고, 제시된 알고리즘의 시간잡도를 분석하시오. 단 연산식에는 괄호가 없으며, operand는 모두 정수이고, 연산자는 사칙연산자 +, -, *, / 와 지수연산자 ^만 있다고 가정한다. 예를 들면 2 + 3 * 4 ^ 5 - 6 / 3과 같다.