계산기 사용가능 여부 불가능
자료구조론 1 2
자료구조론
2011년도 5급(기술) 공무원 공채 제2차시험
응시번호 : 성명 :
제 1 문. n개의 원소를 갖는 배열 A에 대하여 처음에 Find(A, 0, n-1)로 호출되었을 때
다음 물음에 답하시오. (총 30점)
boolean Find (dtype A[], int s, int t) {
if (s == t) return true;
if (A[s] ≠ A[t]) return false;
int m = (s + t) / 2 ;
if ( Find(A, s, m) and Find(A, m + 1, t) ) return true;
else
return false;
}
1) 함수 Find가 수행하는 기능을 순환함수를 고려하여 자세히 설명하시오. (10점) 2) 함수 Find가 최악의 경우(worst case)에 수행하는 비교 횟수를 f(n)이라고
할 때, f(n)을 순환식으로 표현하시오. (10점)
3) n이 2k(k는 양의 정수)의 값을 가질 때, 2)번에서 구한 f(n)에 대한 Big-Oh(O)를 구하는 계산과정을 보이시오. (10점)
제 2 문. 3개의 알고리즘 module_A, module_B, module_C는 동일한 기능을 수행하도록 C 언어와 유사한 언어로 표현한 함수이다. 알고리즘 module_B는 나머지 연산자(%)를 이용하고, 알고리즘 module_C는 순환함수 기법을 이용한다.
밑줄 친 ㉠에서 ㉤까지의 코드를 각각 작성하시오. (20점)
int module_A(int i, int j) { /* i와 j는 양의 정수 */
int k;
for ( ; j ≠ 0; ) { if ( i > j ) {
k = i; i = j; j = k;
}
j = j - i;
}
return i;
}
int module_B(int i, int j) { /* i와 j는 양의 정수 */
int k;
for ( ; j ≠ 0; ) {
㉠ ;
㉡ ;
㉢ ;
}
return i;
}
int module_C(int i, int j) { /* i와 j는 양의 정수 */
if ( j == 0 )
㉣ ;
else
㉤ ;
}
계산기 사용가능 여부 불가능
자료구조론 2 2
제 3 문. 다음 그래프에 대하여 아래의 물음에 답하시오. (총 30점)
B E
D C
A
4 1
3
1 2 2
1
1) 위 그래프에 대한 인접 리스트를 표현하시오. (단, 노드의 연결 순서는 알파벳 순이며 노드의 표현방식은 알파벳, 가중치와 링크(link)로 구성된다) (5점) 2) 다익스트라 알고리즘(Dijkstra's Algorithm)을 이용하여 A를 시작점으로 D까지의
최단경로를 구하고자 한다. 이 과정에서 최단 경로의 다음(next) 정점을 찾을 때 아래와 같은 모양의 힙(heap)을 이용한다. 최단 경로를 찾는 과정에서 사용되는 힙을 모두 표현하시오. (15점)
A,0
C,∞
B,∞
E,∞
D,∞
3) 가중그래프 G ＝ (V, E)에서, 각 간선(edge)의 가중치에 똑같은 양의 정수 d를 더해서 새로운 가중그래프 G' ＝ (V, E')를 만들 때, G에서 임의의 노드 u로 부터 v로 가는 최단 경로는 G'에서도 최단 경로인가? 맞으면 이를 증명하고, 틀리면 반례를 보이시오. (10점)
제 4 문. 다음 해시 테이블 구조와 주어진 조건을 이용하여, 해시 테이블을 나타내는 배열 table과 키값 key를 매개변수로 받아 삽입할 위치의 인덱스를 반환하는 함수 int insert(struct entry table[], char *key)를 C 언어와 유사한 언어로
작성하시오. (20점)
<해시 테이블 구조>
struct entry { char *key;
char *value;
} table[N];
<조 건>
○ 주어진 키값 key에 대해 0에서 N-1 사이의 해시값을 계산해주는 함수 int hash(char *key)가 주어진다고 가정한다.
○ 충돌은 선형 조사(linear probing) 방식을 사용하여 해결한다.
○ 두 개의 스트링을 비교하여 같을 경우 1을 반환하는 함수 int equal (char *s, char *t)이 주어져 있는 것으로 가정한다.
○ 해시 테이블에 삽입을 위한 여유 공간이 없거나 동일한 키를 갖는 항목이 이미 테이블에 존재할 경우 -1을 반환한다.
○ 해시 테이블은 비어있는 항(element)의 경우 key의 값이 NULL로 설정되어 있는 것으로 가정한다.
