1 / 1
A4정답 포함← → 키 · 드래그로 넘김
7급 서울시 자료구조론 기출문제모두CBT · moducbt.com
20년 1회차
문제 1
<보기>의 C언어 함수(func)에서 func(4)+func(9)를 수행한 결과 값은?
<보기>
int func(int n) {
int res = 0;
if(n <= 1) res = n;
else {
int fn, fnm2 = 0, fnm1 = 1;
for(int i = 2; i <= n; i++) {
fn = fnm1 + fnm2;
fnm2 = fnm1;
fnm1 = fn;
}
res = fn;
}
return res;
}123
237
358
494
문제 2
<보기>는 알고리즘의 시간 복잡도(time complexity)를 표시하는 방법 중 하나인 빅오(big-oh) 표기법에 대한 정의이다. 빈칸 (가)와 (나)에 각각 들어갈 수식은?
(가) / (나)
<보기>
두 개의 함수 과 에 대해서 은 다음과 같이 정의한다.
= {: 모든 [ (가) ]에 대해서 [ (나) ]인 양의 상수 와 가 존재한다.}
두 개의 함수 과 에 대해서 은 다음과 같이 정의한다.
= {: 모든 [ (가) ]에 대해서 [ (나) ]인 양의 상수 와 가 존재한다.}
(가) / (나)
1 /
2 /
3 /
4 /
문제 3
1부터 50까지의 정수가 저장된 이진 탐색 트리(binary search tree)에서 루트노드부터 29가 저장된 노드를 탐색하려고 한다. 탐색하는 과정 중에 방문한 노드들의 순서로 옳지 않은 것은?
140 → 5 → 39 → 25 → 29
225 → 30 → 26 → 27 → 29
310 → 30 → 15 → 17 → 29
420 → 35 → 17 → 33 → 29
문제 4
큐(queue)를 적용할 수 있는 상황이 아닌 것은?
1도착한 순서대로 프린트 처리
2비동기적 데이터 전송(파일 입·출력, 파이프, 소켓)
3프로세스 스케줄링
4텍스트 에디터에서의 작업 취소(undo) 과정
문제 5
<보기>는 가중치가 부여된 무방향 그래프(weighted undirected graph)를 인접 행렬(adjacency matrix)로 표현한 것이다. 이 그래프에 대한 최소 비용 신장 트리(minimum spanning tree)에서 간선(edge)의 가중치를 모두 더한 값은?
<보기>
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 8 | 3 | ∞ | ∞ |
| B | 8 | 0 | 5 | 4 | ∞ |
| C | 3 | 5 | 0 | 2 | 6 |
| D | ∞ | 4 | 2 | 0 | 7 |
| E | ∞ | ∞ | 6 | 7 | 0 |
114
215
316
417
문제 6
C언어로 작성된 <보기>의 함수는 입력된 문자열을 검사하여 0 또는 1을 반환한다. 이 함수의 인자로 넣었을 때 1을 반환하는 문자열은? (단, push()는 문자 하나를 스택에 삽입하는 함수이고, pop()은 문자 하나를 스택에서 추출하는 함수이다.)
<보기>
int isTrue(char str[])
{
int length = strlen(str);
for (int i = 0; i < length; i++)
push(str[i]);
for (int i = 0; i < length; i++)
if (pop() != str[i])
return 0;
return 1;
}1AAAAAAaaaaaa
2aaaAAAaaaAAA
3AAAaaaaaaAAA
4AaAaAaAaAaAa
문제 7
<보기>는 단순 연결 리스트(singly linked list)에서 원소들의 순서를 역순으로 변환하는 C언어 프로그램이다. (가), (나), (다)에 들어갈 내용을 옳게 짝지은 것은?
(가) / (나) / (다)
<보기>
typedef struct node {
int key;
struct node *link;
} ListNode;
ListNode *reverse(ListNode *L)
{
ListNode *p, *q, *r;
p = L;
q = NULL;
r = NULL;
while (p != NULL) {
[ (가) ];
[ (나) ];
p = p→link;
[ (다) ];
}
return q;
}(가) / (나) / (다)
1q = p / r = q / q→link = r
2r = q / q = p / q→link = r
3r = q / q = p / r = q→link
4q = p / r = q / r = q→link
문제 8
시작점이 1일 때, <보기>의 그래프에 대한 너비 우선 탐색(breadth first search)의 방문 순서를 바르게 나열한 것은? (단, 같은 우선순위의 정점들은 숫자가 작은 정점을 먼저 방문한다.)

<보기>

11-2-3-4-5-6-7
21-3-4-5-2-7-6
31-3-4-5-6-2-7
41-3-4-6-5-2-7
문제 9
이진 트리(binary tree)를 배열로 저장할 때 <보기 1>과 같은 특성을 갖는다고 가정하자. 이진 트리를 <보기 2>와 같은 형태의 배열로 저장했을 때, 이 트리에 대한 설명으로 가장 옳은 것은?
<보기 1>
• 배열 인덱스 에 저장된 노드의 부모노드 인덱스는
• 배열 인덱스 에 저장된 노드의 왼쪽 자식노드 인덱스는
• 배열 인덱스 에 저장된 노드의 오른쪽 자식노드 인덱스는
• 배열 인덱스 에 저장된 노드의 부모노드 인덱스는
• 배열 인덱스 에 저장된 노드의 왼쪽 자식노드 인덱스는
• 배열 인덱스 에 저장된 노드의 오른쪽 자식노드 인덱스는
<보기 2>
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13] | [14] | [15] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 7 | 28 | 1 | 15 | 30 | 11 | 17 | 36 |
1이 트리는 포화 이진 트리(full binary tree)이다.
2이 트리는 완전 이진 트리(complete binary tree)이다.
3단말 노드(leaf node) 개수는 3개이다.
4이 트리는 이진 탐색 트리(binary search tree)이다.
문제 10
공백 AVL 트리에 키(key)를 차례대로 저장하여 AVL 트리를 구축한다고 할 때, 생성되는 AVL 트리의 모양이 다른 것은?
12, 3, 5, 6, 7, 9
23, 5, 6, 2, 7, 9
35, 2, 3, 7, 6, 9
46, 7, 9, 2, 3, 5
문제 11
<보기>의 중위 표기식(infix expression)을 전위 표기식(prefix expression)으로 변환한 것으로 옳은 것은?
<보기>
((x/y)−z) + (u*v*w) − ((x*z)/u)
((x/y)−z) + (u*v*w) − ((x*z)/u)
1−+−/xyz**uvw/*xzu
2−+−/xyz**uvw*/xzu
3−/xyz+**uvw/*−xzu
4−/xyz+**uvw−/*xzu
문제 12
<보기>의 최대 히프(max heap)에 8을 삽입한 후, 최댓값을 삭제하는 연산을 수행하였다. 이때, 루트노드의 좌·우 자식노드의 값은?
좌 / 우

<보기>
좌 / 우

17 / 5
27 / 6
37 / 8
48 / 7
문제 13
m차 트리(m-ary tree)는 각 노드(node)의 자식노드가 최대 m개인 트리를 의미한다. <보기>의 그림과 같은 연결 리스트(linked list)로 구현된 m차 트리의 노드의 수가 n개일 때, 이 트리의 널 포인터(null pointer)의 총 개수는?

<보기>

1n(m+1)+1
2n(m+1)−1
3n(m−1)+1
4n(m−1)−1
문제 14
최악의 경우 시간 복잡도가 O(log)인 정렬 알고리즘은?
1삽입 정렬(insertion sort)
2퀵 정렬(quick sort)
3합병 정렬(merge sort)
4버블 정렬(bubble sort)
문제 15
데크(deque: double ended queue)에 대해 <보기>와 같이 4가지 연산을 사용할 수 있다고 하자. 데크의 연산을 사용하여 스택과 큐를 구현한다고 할 때, 필요한 데크의 연산을 옳게 짝지은 것은? (여기서 데크를 가리키는 포인터를 d, 스택을 가리키는 포인터를 s, 큐를 가리키는 포인터를 q라고 한다.)
스택의 연산: push(s, item) / pop(s), 큐의 연산: enqueue(q, item) / dequeue(q)
<보기>
• insert_front(d, item): 데크의 첫 번째 원소로 item 삽입
• insert_rear(d, item): 데크의 마지막 원소로 item 삽입
• delete_front(d): 데크의 첫 번째 원소 삭제
• delete_rear(d): 데크의 마지막 원소 삭제
• insert_front(d, item): 데크의 첫 번째 원소로 item 삽입
• insert_rear(d, item): 데크의 마지막 원소로 item 삽입
• delete_front(d): 데크의 첫 번째 원소 삭제
• delete_rear(d): 데크의 마지막 원소 삭제
스택의 연산: push(s, item) / pop(s), 큐의 연산: enqueue(q, item) / dequeue(q)
1insert_rear(d, item) / delete_rear(d) / insert_rear(d, item) / delete_front(d)
2insert_rear(d, item) / delete_front(d) / insert_rear(d, item) / delete_rear(d)
3insert_front(d, item) / delete_front(d) / insert_front(d, item) / delete_front(d)
4insert_front(d, item) / delete_rear(d) / insert_front(d, item) / delete_rear(d)
문제 16
다익스트라(Dijkstra)의 최단 경로 알고리즘을 이용하여 <보기>의 그래프의 정점 E에서 각 정점으로의 최단 경로를 구할 때, 정점 E를 선택한 이후 세 번째로 선택되는 정점은? (단, 각 간선 위의 숫자는 양 정점들 사이의 거리를 의미한다.)

<보기>

1A
2C
3D
4G
문제 17
<보기>는 5개의 노드로 구성된 이진 트리를 전위, 중위, 후위 순회한 결과이다. 이 결과로 알 수 있는 이진 트리의 구성은?

<보기>
• 전위 순회: A − B − D − C − E
• 중위 순회: B − D − A − E − C
• 후위 순회: D − B − E − C − A
• 전위 순회: A − B − D − C − E
• 중위 순회: B − D − A − E − C
• 후위 순회: D − B − E − C − A

1[그림]
2[그림]
3[그림]
4[그림]
문제 18
<보기>의 가중그래프(weighted graph)에 대해, Prim의 알고리즘을 적용해서 최소 비용 신장 트리(minimum spanning tree)를 구성하고자 한다. 정점 D에서 시작할 경우, 정점 D를 선택한 이후 네 번째로 선택되는 정점은?

<보기>

1E
2F
3G
4H
문제 19
<보기>의 해시 함수 와 를 사용하여 이중 해싱법(double hashing)으로 키(key) 값 8, 9, 2, 1, 5, 6을 가지는 레코드들을 크기 7의 공백 해시 테이블에 차례대로 삽입했을 경우 생성되는 배열의 모습으로 가장 옳은 것은? (단, 는 첫 번째 조사 위치를 결정하는 해시 함수이고, 는 충돌 발생 시 조사 간격을 결정하기 위한 해시 함수이다.)
<보기>
•
•
•
•
1
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 8 | 9 | 2 | 1 | 5 | 6 |
2
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 2 | 8 | 9 | 5 | 6 |
3
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 2 | 8 | 9 | 6 | 5 | 1 |
4
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 2 | 8 | 9 | 1 | 5 | 6 |
문제 20
<보기 1>은 list라는 배열에 저장된 n개의 원소를 오름차순으로 정렬하는 알고리즘을 C언어로 표현한 함수이다. 배열 list1과 list2에 저장된 값들이 <보기 2>와 같다고 할 때, 이 배열들을 <보기 1>의 함수를 이용하여 정렬한다면, ㉠ 연산이 실행되는 각각의 횟수는?
list1 / list2
<보기 1>
void sort(int list[], int n)
{
int i, j, key;
for(i = 1; i < n; i++) {
key = list[i];
for(j = i-1; j >= 0 && list[j] > key; j--)
㉠ list[j+1] = list[j];
list[j+1] = key;
}
}<보기 2>
list1
list2
list1
| [0] | [1] | [2] | [3] | [4] |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
| [0] | [1] | [2] | [3] | [4] |
|---|---|---|---|---|
| 5 | 4 | 3 | 2 | 1 |
list1 / list2
10회 / 10회
20회 / 15회
34회 / 10회
44회 / 15회