계산기 사용가능 여부 불가능
자료구조론 2 2
제 3 문. 다음 그래프를 보고 질문에 답하시오. (총 25점)
0 3 4
2 1 5
1) 이 그래프를 인접행렬(adjacency matrix) 표현법으로 표현하시오. (5점)
2) 정점(vertex) 0에서 출발하는 깊이우선탐색(depth first search)을 수행할 때, 정점들의 방문 순서를 쓰시오. (5점)
(단, 인접한 정점을 방문할 때 항상 번호가 작은 정점부터 방문한다고 가정한다) 3) 그래프가 인접행렬로 표현되어 있을 때, 깊이우선탐색을 수행하는 순환 함수
(recursive function)를 C언어로 작성하시오. (10점)
(단, 정점의 개수는 n, 인접행렬은 이차원배열 A, 배열 visited[]는 전역변수로 선언되고 적당한 값으로 초기화되었다고 가정한다)
4) 간선(edge)이 교차하지 않고 평면에 그릴 수 있는 그래프를 평면그래프 (planar graph)라고 한다. 위의 그래프는 평면그래프인가 아닌가? 평면그래프 라면 위의 그래프와 동등하며 간선이 교차하지 않는 평면그래프를 그리시오.
평면그래프가 아니라면 평면그래프가 될 수 없는 이유를 설명하시오. (5점)
제 4 문. 차수가 m인 B－트리는 m－원 탐색트리로 다음의 성질을 만족한다.
∘단말노드를 제외한 모든 노드는 최대 m개, 최소 ⌈m/2⌉개의 자식을 갖는다. 단, 루트노드는 단말노드가 아닐 경우 자식노드의 최소 개수는 2개이다.
⌈⌉는 올림(ceil)연산을 나타낸다.
∘모든 단말노드는 같은 레벨에 존재한다.
∘단말노드가 아닌 노드는 k개의 자식노드를 가질 경우 k － 1개의 키 값을 저장한다.
B－트리에 관한 다음 질문에 답하시오. (총 20점)
1) 루트노드의 레벨을 1로 할 경우, 높이가 h인 B－트리가 가질 수 있는 노드 개수의 최소값을 구하려 한다. 노드가 가질 수 있는 자식노드의 최소 개수를 t ＝⌈m/2⌉로 나타낸다. t를 이용하여 노드 개수의 최소값을 나타내는 식을 풀이과정과 함께 쓰시오. (10점)
2) 루트노드의 레벨을 1로 할 경우, 높이가 h인 B－트리가 저장할 수 있는 키 값의 개수의 최소값을 구하시오. 1)번 문제의 t를 이용하여 식을 표현하시오.
(5점)
3) 키 값이 n개인 경우 트리 높이의 최대값 h를 구하시오. n과 1)번 문제의 t를 이용하여 식을 표현하시오. (5점)
행정안전부 시험출제과장
계산기 사용가능 여부 불가능
자료구조론 1 2
자료구조론
2010년 시행 행정고등고시(기술직) 제2차시험
응시번호 : 성명 :
제 1 문. 다음과 같이 동작하는 n비트 이진 계수기(binary counter)가 있다고 하자.
이 계수기에 동작 신호가 들어오면 값이 1만큼 증가한다. 예를 들어 n ＝8일 때, 이진 계수기가 어떤 단계 t에서의 상태가 S(t) ＝ 00010011이라고 가정하면 동작 신호가 들어오고 난 뒤의 상태는 S(t ＋ 1) ＝ 00010100이 된다. 모든 비트가 1인 경우에 동작 신호가 들어오면 다음 상태의 모든 비트는 0이 된다.
이 경우 S(t)에서 S(t ＋ 1)로 바뀔 때 달라지는 비트의 수를 연산 비용이라고 하자. 즉 0에서 1로 또는 1에서 0으로 바뀌는 비트의 수를 계산한다.
하나의 동작신호에 따라 계수기의 상태를 변경하는 작업의 복잡도 (complexity)는 연산 비용이 가장 많이 필요한 경우(worst case)와 가장 적게 필요한 경우(best case), 그리고 평균적인 경우(average case)로 나누어 분석할 수 있다. 각 경우의 복잡도를 점근 표기법(asymptotic notation) 가운데 하나인
표기법을 사용하여 n에 대해 나타내시오. 이 때 그 계산과정을 반드시 나타
내야 한다. (총 25점)
1) 가장 많이 필요한 경우(worst case) (5점) 2) 가장 적게 필요한 경우(best case) (5점) 3) 평균적인 경우(average case) (15점)
제 2 문. 다음은 퀵 정렬(quick sort)에서 사용하는 partition 함수를 사용하여 전역변수 a로 주어진 정수 배열에서 중앙값을 구하여 출력하는 C프로그램이다. partition 함수의 매개변수 p와 q는 배열 a에서 탐색 범위를 나타내는 배열 인덱스들이다.
(총 30점) (단, 입력의 크기, 즉, 배열 a의 크기를 n이라고 가정한다. n이 짝수일 경우
n/2 번째로 작은 원소가 중앙값이며, n이 홀수일 경우 (n ＋ 1)/2 번째로 작은 원소가 중앙값이다)
1) (가) 부분에 들어갈 루프(loop) 형태의 코드를 쓰시오. (15점)
2) 이 알고리즘의 시간복잡도를 최선의 경우, 최악의 경우, 평균적인 경우로 나누어 표기법을 이용하여 표현하고 그 근거를 간략히 설명하시오. (15점)
#include <stdio.h>
int a[] = { ... }; // 크기 n인 정수 배열 void main() {
int p = 0, q = sizeof(a)/sizeof(int) - 1, mid = (p + q)/2;
int x = 0;
(가)
printf("%d", a[x]);
}
int partition(int p, int q) {
int pivot = a[p], x, y = p, tmp;
for (x = p + 1; x <= q; x++) if (a[x] < pivot) {
y++;
tmp = a[x]; a[x] = a[y]; a[y] = tmp;
}
tmp = a[p]; a[p] = a[y]; a[y] = tmp;
return y;
}
