[7급 국가직 자료구조론] 12년 1회차
7급 국가직 자료구조론 기출문제

12년 1회차

총 20문항 · 객관식 · A4 약 1장

1 / 1
A4정답 포함
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

12년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 함수를 이용하여 recursive(4)를 수행한 결과 값은?
int recursive( int n ) {
if(n<1) return 2;
else return( 22 * recursive(n-1) + 1);
}
1149
2265
3373
4597
정답 및 해설

재귀식을 바닥부터 차례로 풀면 recursive(4)의 값은 597이다.

n이 1보다 작으면 2를 반환하고, 그 외에는 22×r(n−1)+1=4r(n−1)+12^{2} \times r(n-1) + 1 = 4r(n-1) + 1을 반환하는 재귀 호출 구조이다.

r(0) = 2
r(1) = 4×2+1 = 9
r(2) = 4×9+1 = 37
r(3) = 4×37+1 = 149
r(4) = 4×149+1 = 597

  • 149는 r(3)에서 멈춘 값으로, 한 단계를 덜 계산한 것이다.
  • 265는 점화식 어느 단계에서도 나오지 않는 값이다.
  • 373도 점화식 어느 단계에서도 나오지 않는 값이다.
문제 2
if 문장에서 포인터 변수 pt1과 pt2에 대한 설명으로 옳지 않은 것은?
1if (&pt1==&pt2)의 경우에 서로 다른 포인터 변수가 동일한 주소에 있을 수 있다.
2if (pt1==pt2)는 같은 대상을 가리키는지를 검증한다.
3if (*pt1==*pt2)의 경우에 가리키는 대상이 다를지라도 변수 값은 같을 수 있다.
4if (pt1==pt2)는 가리키는 대상의 주소가 동일한 것인지를 검증한다.
정답 및 해설

서로 다른 변수는 동일한 주소를 가질 수 없으므로, &pt1==&pt2 에서 서로 다른 포인터 변수가 같은 주소에 있을 수 있다는 설명이 옳지 않다.

&pt1은 포인터 변수 자신의 주소, pt1은 그 변수에 저장된 값(가리키는 대상의 주소), *pt1은 가리키는 대상의 값이다.

  • pt1==pt2는 두 포인터가 같은 대상을 가리키는지 검증한다 — 옳다.
  • *pt1==*pt2는 값 비교이므로 대상이 달라도 값이 같으면 참이 될 수 있다 — 옳다.
  • pt1==pt2는 곧 가리키는 대상의 주소가 동일한지를 비교하는 것이다 — 옳다.
문제 3
스택 수(stack number)란 다음 장치의 왼쪽 큐 LQ에 들어 갈 수 있는 숫자열을 말한다. 오른쪽 큐 RQ로부터 데이터가 하나씩 중간에 있는 스택 MS를 거치거나 바로 LQ로 입력될 수 있다. 즉, 데이터가 LQ에 입력될 때 RQ에서 직접 입력되거나 MS에서 한 데이터를 삭제해서 LQ에 추가할 수 있다. 다음 장치에서 생성할 수 있는 스택 수는?
11 8 5 6 7 4 9 3 10 2
23 4 6 7 8 5 9 2 1 10
33 4 8 5 6 7 2 9 1 10
49 4 7 5 6 3 8 1 2 10
정답 및 해설

이 장치는 1부터 10까지 순서대로 들어오는 입력을 스택 하나로 재배열하는 것이므로, 출력열이 유효한 스택 순열이어야 하며 3 4 6 7 8 5 9 2 1 10만 가능하다.

판정 요령은 어떤 수가 나올 때 그보다 작은데 아직 안 나온 수는 스택에 쌓여 있으므로, 이후에는 큰 수부터 역순으로만 나올 수 있다는 것이다. 정답열은 1·2를 쌓고 3·4를 바로 보내고, 5를 쌓은 뒤 6·7·8을 보내고 5를 꺼내며, 9를 보낸 뒤 2·1을 꺼내고 10을 보내면 만들어진다.

  • 1 8 5 6 7 4 9 3 10 2: 8이 나올 때 스택 top은 7인데 다음에 5가 나와야 하므로 불가능하다.
  • 3 4 8 5 6 7 2 9 1 10: 8이 나올 때 스택에 5·6·7이 쌓여 top이 7인데 5가 먼저 나오므로 불가능하다.
  • 9 4 7 5 6 3 8 1 2 10: 9가 나올 때 1~8이 모두 스택에 있어 top이 8인데 4가 나오므로 불가능하다.
문제 4
합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은?
1점근분석(asymptotic analysis)할 때, 퀵정렬(quick sort)의 최악수행시간 보다 빠르다.
2추가적인 메모리 사용없이 간단히 구현할 수 있다.
3크기 n인 입력에 대한 최악수행시간을 T(n)이라 할 때, T(n)=2×T(n/2)+cnT(n) = 2 \times T(n/2) + cn으로 나타낼 수 있다. (단, c≥1c \ge 1 상수)
4분할정복(divide and conquer) 기법을 사용한다.
정답 및 해설

합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.

정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 O(n)O(n)이다.

  • 합병정렬의 최악 시간은 O(nlog⁡n)O(n \log n)으로, 퀵정렬의 최악 O(n2)O(n^{2})보다 빠르다 — 옳다.
  • 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 T(n)=2T(n/2)+cnT(n) = 2T(n/2) + cn이 성립한다 — 옳다.
  • 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.
문제 5
방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑하여 다음과 같이 인접행렬로 표현될 때, 위상 정렬(topological sort)이 가능한 것은?
1
abcdef
a11
b11
c11
d11
e11
f
2
abcdef
a11
b11
c11
d1
e111
f
3
abcdef
a11
b11
c11
d1
e11
f
4
abcdef
a11
b11
c11
d1
e11
f1
정답 및 해설

위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.

d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.

  • d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
  • e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
  • f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.
문제 6
다음 데이터를 이용하여 AVL 트리를 생성할 때, 이에 대한 설명으로 옳지 않은 것은?
12, 11, 10, 5, 3, 7, 6, 1, 13, 2, 4
1AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다.
2AVL트리의 루트 값은 5이다.
34가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다.
46은 리프노드이다.
정답 및 해설

완성된 AVL 트리에서 7은 5 → 10 → 7 순으로 세 번 비교로 찾으므로, 네 번의 비교가 필요하다는 설명이 옳지 않다.

삽입 중 회전: 10 삽입 시 LL(루트 11) → 3 삽입 시 LL(노드 10 기준) → 7 삽입 시 LR(루트 10) → 13 삽입 시 RR(노드 11 기준) → 2 삽입 시 LR(노드 3 기준) → 4 삽입 시 루트 10에서 LL 회전이 일어나 루트가 5가 된다.

최종 트리: 5의 왼쪽 2(자식 1, 3), 3의 오른쪽 4 / 5의 오른쪽 10(자식 7, 12), 7의 왼쪽 6, 12의 자식 11, 13.

  • 최종 루트 값은 5이다 — 옳다.
  • 4를 넣으면 루트 10의 균형인수가 2가 되어 재구성이 발생한다 — 옳다.
  • 6은 7의 왼쪽 자식이며 자식이 없는 리프노드이다 — 옳다.
문제 7
다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산(A, B)에 대해 ‘최적으로 구현’한다고 할 때, 연산 A, B 각각에 대한 최악의 시간복잡도는? (단, 그래프의 노드의 개수를 n이라고 하고, 각 노드 쌍 사이에는 최대 1개의 간선(edge)이 존재할 수 있다)
연산 (A) : 노드 i에서 노드 j로의 간선을 삽입한다. (단, 삽입 연산은 항상 간선이 존재하지 않는 노드 쌍에 대해서 수행된다)
연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.
연산 (A) 연산 (B)
1O(1)O(1) O(n)O(n)
2O(log⁡n)O(\log n) O(1)O(1)
3O(1)O(1) O(log⁡n)O(\log n)
4O(n)O(n) O(n)O(n)
정답 및 해설

인접 리스트에서 간선 삽입은 O(1)O(1), 간선 제거는 O(n)O(n)이다.

삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.

  • 삽입 O(log⁡n)O(\log n)·제거 O(1)O(1): 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
  • 삽입 O(1)O(1)·제거 O(log⁡n)O(\log n): 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
  • 삽입 O(n)O(n)·제거 O(n)O(n): 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.
문제 8
다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단, ∞는 두 정점 간에 해당 간선이 없다)
ABCDEFG
A049∞∞∞∞
B40410∞∞∞
C940∞8∞1
D∞10∞025∞
E∞∞820∞6
F∞∞∞5∞03
G∞∞1∞630
1A→B→C→G→D→E→F
2A→B→C→G→E→D→F
3A→B→C→G→E→F→D
4A→B→C→G→F→D→E
정답 및 해설

Dijkstra 알고리즘으로 확정되는 정점 순서는 A→B→C→G→F→D→E이다.

매 단계 미확정 정점 중 최소 거리 정점을 확정하고 인접 거리를 갱신한다.
A 확정: B=4, C=9
B(4) 확정: C=min(9, 8)=8, D=14
C(8) 확정: E=16, G=9
G(9) 확정: E=min(16, 15)=15, F=12
F(12) 확정: D=min(14, 17)=14
D(14) 확정: E=min(15, 16)=15
E(15) 확정

  • G 다음에 D를 고르는 순서는 F(12)가 D(14)보다 가깝다는 점을 놓친 것이다.
  • G 다음 E, D, F 순서는 E(15)보다 F(12)·D(14)가 먼저 확정되어야 하므로 틀리다.
  • G 다음 E, F, D 순서도 E(15)를 가장 가까운 F(12)보다 먼저 확정해 틀리다.
문제 9
이진탐색트리의 노드 삽입에 대한 다음 C 프로그램의 ㉠ ~ ㉡에 들어갈 내용은? (단, T는 이진탐색트리, X는 이진탐색트리에 삽입할 값이다)
struct TreeNode {
int Element;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;

SearchTree Insert( int X, SearchTree T )
{
if ( T == NULL ) {
T = (SearchTree)malloc(sizeof(struct TreeNode));
T->Element = X;
T->Left = T->Right = NULL;
} else if ( X < T->Element )
㉠
else if ( X > T->Element )
㉡
return T;
}
㉠ ㉡
1T->Left = Insert( X, T ); T->Right = Insert( X, T );
2T->Left = Insert( X, T->Left ); T->Right = Insert( X, T->Right );
3T->Left = Insert( X, T->Element ); T->Right = Insert( X, T->Element );
4T->Left = Insert( X, T->Right ); T->Right = Insert( X, T->Left );
정답 및 해설

㉠에는 T->Left = Insert( X, T->Left );, ㉡에는 T->Right = Insert( X, T->Right );가 들어간다.

X가 현재 노드 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에 재귀적으로 삽입하고, 반환된 서브트리 루트를 해당 자식 포인터에 다시 연결한다.

  • Insert( X, T )로 자기 자신을 다시 넘기면 T가 NULL이 되지 않아 무한 재귀에 빠진다.
  • T->Element는 정수 값이므로 트리 포인터 인자로 넘길 수 없다.
  • 왼쪽 자식 자리에 오른쪽 서브트리 삽입 결과를 연결하는 식으로 좌우를 뒤바꾸면 기존 서브트리가 엇갈려 이진탐색트리의 대소 규칙이 깨진다.
문제 10
다음 데이터들을 공백힙(empty heap)에 차례대로 삽입하여 최대힙(max heap)을 생성하였다. 생성된 최대힙에 삭제 연산을 두 번 수행한 후의 결과는?
2, 13, 55, 8, 35, 47, 23, 19
1
2
3
4
정답 및 해설

두 번 삭제한 뒤의 최대힙은 레벨 순서로 35, 19, 23, 2, 8, 13이다(루트 35, 왼쪽 자식 19의 자식 2·8, 오른쪽 자식 23의 자식 13).

차례로 삽입하며 상향 조정하면 힙 배열은 55, 35, 47, 19, 8, 13, 23, 2가 된다.
첫 삭제: 55를 빼고 마지막 원소 2를 루트로 올려 하향 조정 → 47, 35, 23, 19, 8, 13, 2.
둘째 삭제: 47을 빼고 2를 루트로 올려 더 큰 자식과 교환 → 35, 19, 23, 2, 8, 13.

  • 루트 35의 왼쪽이 23, 오른쪽이 19인 트리: 첫 삭제 뒤 23은 47의 오른쪽 서브트리에 있었으므로 오른쪽 자식 자리에 남아야 한다.
  • 19의 자식이 2·13이고 23의 자식이 8인 트리: 8과 13의 위치가 서로 바뀌어 하향 조정 경로와 맞지 않는다.
  • 왼쪽 23(자식 2·13)·오른쪽 19(자식 8)인 트리: 좌우 서브트리와 리프 배치가 모두 실제 결과와 다르다.
문제 11
다음 연산식을 후위(postfix) 연산식으로 변환했을 때, 4번째 연산자는?
1 + (2 - 3 * 4 / (5 + 6)) - 7
1+
2-
3*
4/
정답 및 해설

후위 연산식은 1 2 3 4 * 5 6 + / - + 7 - 이며, 네 번째 연산자는 -이다.

괄호 안은 3*4를 (5+6)으로 나눈 뒤 2에서 빼므로 2 3 4 * 5 6 + / - 가 된다.
여기에 1을 더하고 7을 빼면 전체 식이 완성된다.

연산자 등장 순서: * → + → / → - → + → -

  • +는 두 번째(5+6)와 다섯 번째(1과의 덧셈)에 나온다.
  • *는 첫 번째 연산자이다.
  • /는 세 번째 연산자이다.
문제 12
다음 선형연결리스트(linear linked list)에서 LEE를 찾기 위한 비교 횟수는? (단, HEADER는 3 이다)
IndexNamePointer
1KIM6
2PARK1
3CHOI4
4BAEK2
5LEE7
6MIN5
7ANN8
8JUNG-
14
25
36
47
정답 및 해설

HEADER 3에서 출발해 포인터를 따라가면 LEE는 여섯 번째 노드에서 찾으므로 비교 횟수는 6회이다.

탐색 경로: CHOI(3) → BAEK(4) → PARK(2) → KIM(1) → MIN(6) → LEE(5)

선형연결리스트는 순차 탐색만 가능하므로 인덱스 순서가 아니라 포인터 순서대로 비교한다.

  • 비교 4회는 KIM까지만 비교한 경우이다.
  • 비교 5회는 MIN까지만 비교한 경우이다.
  • 비교 7회는 LEE를 지나 ANN까지 비교한 경우이다.
문제 13
정렬(sort)에 대한 설명으로 옳지 않은 것은?
1퀵정렬(quick sort)은 스택을 이용하여 수행한다.
2쉘정렬(shell sort)은 최적의 경우에 선택정렬(selection sort) 보다 빠르다.
3힙정렬(heap sort)은 배열을 이용한 포화 이진트리(full binary tree)를 사용한다.
410개 데이터의 버블정렬(bubble sort)은 최대 45번의 비교 연산을 수행한다.
정답 및 해설

힙정렬은 배열로 표현한 완전 이진트리(complete binary tree)를 사용하므로, 포화 이진트리를 사용한다는 설명이 옳지 않다.

포화 이진트리는 모든 레벨이 꽉 찬 트리라 노드 수가 2k−12^{k}-1일 때만 성립하지만, 힙은 마지막 레벨이 왼쪽부터 채워진 완전 이진트리면 된다.

  • 퀵정렬은 분할된 구간을 재귀 호출(스택)로 처리한다 — 옳다.
  • 쉘정렬은 이미 정렬된 최선의 경우 O(nlog⁡n)O(n \log n) 수준으로, 입력과 무관하게 항상 O(n2)O(n^{2})인 선택정렬보다 빠르다 — 옳다.
  • 10개 데이터의 버블정렬 최대 비교 횟수는 9+8+…+1 = 45이다 — 옳다.
문제 14
해시함수(hash function)로 h(k)=k mod 7을 사용하고, 선형탐색(linear probing) 기법을 이용하여 충돌을 해결하고자 한다. 키가 3, 10, 5, 9, 12 순서대로 입력되었을 때, 생성된 해시테이블은?
1
[0][1][2][3][4][5][6]
1293105
2
[0][1][2][3][4][5][6]
1231059
3
[0][1][2][3][4][5][6]
9103125
4
[0][1][2][3][4][5][6]
9310512
정답 및 해설

선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.

3 → 3 mod 7 = 3, [3]에 저장
10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
5 → 5 mod 7 = 5, [5]에 저장
9 → 9 mod 7 = 2, [2]에 저장
12 → 12 mod 7 = 5, 충돌 → [6]에 저장

  • 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
  • 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
  • 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.
문제 15
비어있는 이진 탐색 트리(binary search tree)에 다음 키 값들을 차례로 삽입하여 동적으로 이진 탐색 트리를 구성하였을 때, 5를 탐색하는데 필요한 비교 횟수는?
23, 18, 2, 16, 4, 10, 5, 39, 26, 15
13
25
37
49
정답 및 해설

5를 찾으려면 23 → 18 → 2 → 16 → 4 → 10 → 5 순으로 7회 비교가 필요하다.

삽입 결과 23의 왼쪽 18, 18의 왼쪽 2, 2의 오른쪽 16, 16의 왼쪽 4, 4의 오른쪽 10, 10의 왼쪽 5가 연결되어 한쪽으로 길게 늘어진 편향된 경로가 생긴다.

  • 비교 3회는 2까지만 내려간 경우이다.
  • 비교 5회는 4까지만 내려간 경우이다.
  • 비교 9회는 루트에서 5까지의 경로 길이보다 많아 성립하지 않는다.
문제 16
다음 그래프를 이용하여 Kruskal 알고리즘을 적용하였을 때, 생성된 최소 비용 신장 트리의 비용은?
111
212
313
414
정답 및 해설

Kruskal 알고리즘으로 만든 최소 비용 신장 트리의 비용은 13이다.

정점 6개이므로 간선 5개가 필요하다. 가중치가 작은 간선부터 사이클이 생기지 않는 것만 고르면 1 → 2 → 2를 채택하고, 가중치 3인 간선은 이미 연결된 두 정점을 잇는 사이클이 되어 버린다. 이어서 가중치 4인 간선 두 개를 채택하면 모든 정점이 연결된다.

1+2+2+4+4=131 + 2 + 2 + 4 + 4 = 13

  • 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
  • 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
  • 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.
문제 17
다음과 같은 4개의 노드를 가진 2-3 트리에 키 값 6을 추가하였을 때, 트리의 전체 노드의 수는?
14개
25개
36개
47개
정답 및 해설

키 6을 넣으면 분할이 루트까지 전파되어 높이가 늘고, 전체 노드는 7개가 된다.

6은 오른쪽 리프 [7, 9]에 들어가 [6, 7, 9]로 넘치므로 분할되고 가운데 키 7이 부모로 올라간다. 루트가 [2, 4, 7]로 다시 넘쳐 분할되며 4가 새 루트가 된다.

결과: 루트 [4] / 내부 노드 [2], [7] / 리프 [1], [3], [6], [9] → 1 + 2 + 4 = 7개.

  • 4개: 삽입 전 노드 수 그대로이며, 리프가 넘쳐 분할되는 것을 반영하지 않았다.
  • 5개: 리프 분할만 반영하고 루트 분할을 빠뜨린 경우다.
  • 6개: 루트 분할은 반영했으나 새 루트 노드 생성을 세지 않은 경우다.
문제 18
다항식(polynomial) 표현을 위해 구조체 poly를 정의하였다. 이 구조체를 이용하여 A(x)=−3x999−2x888+1A(x) = -3x^{999} -2x^{888} + 1과 B(x)=x10+x9+x5B(x) = x^{10} + x^{9} + x^{5}을 저장하기 위한 최소 메모리 용량[byte]은? (단, 정수(int)를 표현하는 데 2 byte를 사용하고, 실수(float)를 표현하는 데 4 byte를 사용한다)
typedef struct {
int exp;
float coef;
} poly;
122
224
336
438
정답 및 해설

0이 아닌 항만 (exp, coef) 쌍으로 저장하는 희소 다항식 표현을 쓰면 최소 메모리는 36 byte이다.

poly 하나의 크기: int 2 byte + float 4 byte = 6 byte
A(x)의 항 3개 + B(x)의 항 3개 = 6개
6 × 6 = 36 byte

  • 22 byte는 poly 6개(36 byte)를 담기에 부족하다.
  • 24 byte는 poly 4개 분량에 불과하다.
  • 38 byte는 36 byte에 int 하나(2 byte)를 더 쓴 값으로 최소가 아니다.
문제 19
다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도가 가장 큰 것은?
1임의의 정수 100,000개를 선택정렬(selection sort)로 정렬하는 문제
2정렬된 100,000개의 정수에서 임의의 정수를 이진탐색하는 문제
3반복 호출로 피보나치수열 F0F_{0}, F1F_{1}, F2F_{2}, … 에서 F100000F_{100000} 값을 구하는 문제
4재귀호출로 하노이 탑(tower of Hanoi)의 100,000개 원판 이동 문제
정답 및 해설

하노이 탑의 원판 이동 횟수는 2n−12^{n}-1로 지수 시간이므로 시간복잡도가 가장 크다.

원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1, 즉 O(2n)O(2^{n})이다.

  • 선택정렬은 O(n2)O(n^{2})로 다항 시간이다.
  • 정렬된 배열의 이진탐색은 O(log⁡n)O(\log n)이다.
  • 반복문으로 피보나치 수를 구하면 O(n)O(n)이다.
문제 20
구조체 list를 이용한 두 개의 단순연결리스트 x, y의 후위노드(음영부분)들을 서로 스왑(swap)하기 위한 코드는? (단, 후위노드들의 next는 NULL이 아니다)
struct list { int data; struct list *next; } *x, *y, *tmp;

1tmp = x->next;
x->next->next = y->next->next;
y->next->next = tmp;
tmp = y->next;
x->next = y->next;
y->next = tmp;
2tmp = x->next->next;
x->next->next = y->next->next;
y->next->next = tmp;
tmp = x->next;
x->next = y->next;
y->next = tmp;
3tmp = x->next;
x->next = y->next;
y->next = tmp;
tmp = x->next;
x->next->next = y->next->next;
y->next->next = tmp;
4tmp = x->next->next;
y->next->next = tmp;
x->next->next = y->next->next;
tmp = x->next;
y->next = tmp;
x->next = y->next;
정답 및 해설

음영 노드를 바꾸려면 음영 노드의 next(뒤 연결)를 먼저 교환하고, 그다음 x->next와 y->next를 교환해야 한다. 즉 tmp = x->next->next로 시작해 뒤 연결을 맞바꾼 뒤 tmp = x->next로 앞 연결을 맞바꾸는 코드가 옳다.

뒤 연결을 먼저 바꾸면 각 음영 노드가 상대 리스트의 세 번째 노드를 가리키게 되고, 이후 앞 연결을 바꾸면 x와 y 리스트에 상대 음영 노드가 끼워져 교환이 완성된다.

  • tmp = x->next로 시작하는 코드: y->next->next에 x의 음영 노드 자체를 넣어 x의 세 번째 노드 연결을 잃는다.
  • 앞 연결(x->next, y->next)을 먼저 교환하는 코드: 이후 x->next가 이미 y의 음영 노드를 가리키므로 뒤 연결 교환이 어긋나, y 리스트가 x의 음영 노드·y의 음영 노드·x의 세 번째 노드 순으로 이어지고 y의 세 번째 이후 노드를 잃는다.
  • y->next->next = tmp를 먼저 대입하는 코드: y의 세 번째 노드 주소를 저장 없이 덮어써 y 쪽 뒤 리스트를 잃는다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
12년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 함수를 이용하여 recursive(4)를 수행한 결과 값은?
int recursive( int n ) {
if(n<1) return 2;
else return( 22 * recursive(n-1) + 1);
}
1149
2265
3373
4597
정답 및 해설

재귀식을 바닥부터 차례로 풀면 recursive(4)의 값은 597이다.

n이 1보다 작으면 2를 반환하고, 그 외에는 22×r(n−1)+1=4r(n−1)+12^{2} \times r(n-1) + 1 = 4r(n-1) + 1을 반환하는 재귀 호출 구조이다.

r(0) = 2
r(1) = 4×2+1 = 9
r(2) = 4×9+1 = 37
r(3) = 4×37+1 = 149
r(4) = 4×149+1 = 597

  • 149는 r(3)에서 멈춘 값으로, 한 단계를 덜 계산한 것이다.
  • 265는 점화식 어느 단계에서도 나오지 않는 값이다.
  • 373도 점화식 어느 단계에서도 나오지 않는 값이다.
문제 2
if 문장에서 포인터 변수 pt1과 pt2에 대한 설명으로 옳지 않은 것은?
1if (&pt1==&pt2)의 경우에 서로 다른 포인터 변수가 동일한 주소에 있을 수 있다.
2if (pt1==pt2)는 같은 대상을 가리키는지를 검증한다.
3if (*pt1==*pt2)의 경우에 가리키는 대상이 다를지라도 변수 값은 같을 수 있다.
4if (pt1==pt2)는 가리키는 대상의 주소가 동일한 것인지를 검증한다.
정답 및 해설

서로 다른 변수는 동일한 주소를 가질 수 없으므로, &pt1==&pt2 에서 서로 다른 포인터 변수가 같은 주소에 있을 수 있다는 설명이 옳지 않다.

&pt1은 포인터 변수 자신의 주소, pt1은 그 변수에 저장된 값(가리키는 대상의 주소), *pt1은 가리키는 대상의 값이다.

  • pt1==pt2는 두 포인터가 같은 대상을 가리키는지 검증한다 — 옳다.
  • *pt1==*pt2는 값 비교이므로 대상이 달라도 값이 같으면 참이 될 수 있다 — 옳다.
  • pt1==pt2는 곧 가리키는 대상의 주소가 동일한지를 비교하는 것이다 — 옳다.
문제 3
스택 수(stack number)란 다음 장치의 왼쪽 큐 LQ에 들어 갈 수 있는 숫자열을 말한다. 오른쪽 큐 RQ로부터 데이터가 하나씩 중간에 있는 스택 MS를 거치거나 바로 LQ로 입력될 수 있다. 즉, 데이터가 LQ에 입력될 때 RQ에서 직접 입력되거나 MS에서 한 데이터를 삭제해서 LQ에 추가할 수 있다. 다음 장치에서 생성할 수 있는 스택 수는?
11 8 5 6 7 4 9 3 10 2
23 4 6 7 8 5 9 2 1 10
33 4 8 5 6 7 2 9 1 10
49 4 7 5 6 3 8 1 2 10
정답 및 해설

이 장치는 1부터 10까지 순서대로 들어오는 입력을 스택 하나로 재배열하는 것이므로, 출력열이 유효한 스택 순열이어야 하며 3 4 6 7 8 5 9 2 1 10만 가능하다.

판정 요령은 어떤 수가 나올 때 그보다 작은데 아직 안 나온 수는 스택에 쌓여 있으므로, 이후에는 큰 수부터 역순으로만 나올 수 있다는 것이다. 정답열은 1·2를 쌓고 3·4를 바로 보내고, 5를 쌓은 뒤 6·7·8을 보내고 5를 꺼내며, 9를 보낸 뒤 2·1을 꺼내고 10을 보내면 만들어진다.

  • 1 8 5 6 7 4 9 3 10 2: 8이 나올 때 스택 top은 7인데 다음에 5가 나와야 하므로 불가능하다.
  • 3 4 8 5 6 7 2 9 1 10: 8이 나올 때 스택에 5·6·7이 쌓여 top이 7인데 5가 먼저 나오므로 불가능하다.
  • 9 4 7 5 6 3 8 1 2 10: 9가 나올 때 1~8이 모두 스택에 있어 top이 8인데 4가 나오므로 불가능하다.
문제 4
합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은?
1점근분석(asymptotic analysis)할 때, 퀵정렬(quick sort)의 최악수행시간 보다 빠르다.
2추가적인 메모리 사용없이 간단히 구현할 수 있다.
3크기 n인 입력에 대한 최악수행시간을 T(n)이라 할 때, T(n)=2×T(n/2)+cnT(n) = 2 \times T(n/2) + cn으로 나타낼 수 있다. (단, c≥1c \ge 1 상수)
4분할정복(divide and conquer) 기법을 사용한다.
정답 및 해설

합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.

정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 O(n)O(n)이다.

  • 합병정렬의 최악 시간은 O(nlog⁡n)O(n \log n)으로, 퀵정렬의 최악 O(n2)O(n^{2})보다 빠르다 — 옳다.
  • 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 T(n)=2T(n/2)+cnT(n) = 2T(n/2) + cn이 성립한다 — 옳다.
  • 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.
문제 5
방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑하여 다음과 같이 인접행렬로 표현될 때, 위상 정렬(topological sort)이 가능한 것은?
1
abcdef
a11
b11
c11
d11
e11
f
2
abcdef
a11
b11
c11
d1
e111
f
3
abcdef
a11
b11
c11
d1
e11
f
4
abcdef
a11
b11
c11
d1
e11
f1
정답 및 해설

위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.

d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.

  • d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
  • e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
  • f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.
문제 6
다음 데이터를 이용하여 AVL 트리를 생성할 때, 이에 대한 설명으로 옳지 않은 것은?
12, 11, 10, 5, 3, 7, 6, 1, 13, 2, 4
1AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다.
2AVL트리의 루트 값은 5이다.
34가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다.
46은 리프노드이다.
정답 및 해설

완성된 AVL 트리에서 7은 5 → 10 → 7 순으로 세 번 비교로 찾으므로, 네 번의 비교가 필요하다는 설명이 옳지 않다.

삽입 중 회전: 10 삽입 시 LL(루트 11) → 3 삽입 시 LL(노드 10 기준) → 7 삽입 시 LR(루트 10) → 13 삽입 시 RR(노드 11 기준) → 2 삽입 시 LR(노드 3 기준) → 4 삽입 시 루트 10에서 LL 회전이 일어나 루트가 5가 된다.

최종 트리: 5의 왼쪽 2(자식 1, 3), 3의 오른쪽 4 / 5의 오른쪽 10(자식 7, 12), 7의 왼쪽 6, 12의 자식 11, 13.

  • 최종 루트 값은 5이다 — 옳다.
  • 4를 넣으면 루트 10의 균형인수가 2가 되어 재구성이 발생한다 — 옳다.
  • 6은 7의 왼쪽 자식이며 자식이 없는 리프노드이다 — 옳다.
문제 7
다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산(A, B)에 대해 ‘최적으로 구현’한다고 할 때, 연산 A, B 각각에 대한 최악의 시간복잡도는? (단, 그래프의 노드의 개수를 n이라고 하고, 각 노드 쌍 사이에는 최대 1개의 간선(edge)이 존재할 수 있다)
연산 (A) : 노드 i에서 노드 j로의 간선을 삽입한다. (단, 삽입 연산은 항상 간선이 존재하지 않는 노드 쌍에 대해서 수행된다)
연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.
연산 (A) 연산 (B)
1O(1)O(1) O(n)O(n)
2O(log⁡n)O(\log n) O(1)O(1)
3O(1)O(1) O(log⁡n)O(\log n)
4O(n)O(n) O(n)O(n)
정답 및 해설

인접 리스트에서 간선 삽입은 O(1)O(1), 간선 제거는 O(n)O(n)이다.

삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.

  • 삽입 O(log⁡n)O(\log n)·제거 O(1)O(1): 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
  • 삽입 O(1)O(1)·제거 O(log⁡n)O(\log n): 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
  • 삽입 O(n)O(n)·제거 O(n)O(n): 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.
문제 8
다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단, ∞는 두 정점 간에 해당 간선이 없다)
ABCDEFG
A049∞∞∞∞
B40410∞∞∞
C940∞8∞1
D∞10∞025∞
E∞∞820∞6
F∞∞∞5∞03
G∞∞1∞630
1A→B→C→G→D→E→F
2A→B→C→G→E→D→F
3A→B→C→G→E→F→D
4A→B→C→G→F→D→E
정답 및 해설

Dijkstra 알고리즘으로 확정되는 정점 순서는 A→B→C→G→F→D→E이다.

매 단계 미확정 정점 중 최소 거리 정점을 확정하고 인접 거리를 갱신한다.
A 확정: B=4, C=9
B(4) 확정: C=min(9, 8)=8, D=14
C(8) 확정: E=16, G=9
G(9) 확정: E=min(16, 15)=15, F=12
F(12) 확정: D=min(14, 17)=14
D(14) 확정: E=min(15, 16)=15
E(15) 확정

  • G 다음에 D를 고르는 순서는 F(12)가 D(14)보다 가깝다는 점을 놓친 것이다.
  • G 다음 E, D, F 순서는 E(15)보다 F(12)·D(14)가 먼저 확정되어야 하므로 틀리다.
  • G 다음 E, F, D 순서도 E(15)를 가장 가까운 F(12)보다 먼저 확정해 틀리다.
문제 9
이진탐색트리의 노드 삽입에 대한 다음 C 프로그램의 ㉠ ~ ㉡에 들어갈 내용은? (단, T는 이진탐색트리, X는 이진탐색트리에 삽입할 값이다)
struct TreeNode {
int Element;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;

SearchTree Insert( int X, SearchTree T )
{
if ( T == NULL ) {
T = (SearchTree)malloc(sizeof(struct TreeNode));
T->Element = X;
T->Left = T->Right = NULL;
} else if ( X < T->Element )
㉠
else if ( X > T->Element )
㉡
return T;
}
㉠ ㉡
1T->Left = Insert( X, T ); T->Right = Insert( X, T );
2T->Left = Insert( X, T->Left ); T->Right = Insert( X, T->Right );
3T->Left = Insert( X, T->Element ); T->Right = Insert( X, T->Element );
4T->Left = Insert( X, T->Right ); T->Right = Insert( X, T->Left );
정답 및 해설

㉠에는 T->Left = Insert( X, T->Left );, ㉡에는 T->Right = Insert( X, T->Right );가 들어간다.

X가 현재 노드 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에 재귀적으로 삽입하고, 반환된 서브트리 루트를 해당 자식 포인터에 다시 연결한다.

  • Insert( X, T )로 자기 자신을 다시 넘기면 T가 NULL이 되지 않아 무한 재귀에 빠진다.
  • T->Element는 정수 값이므로 트리 포인터 인자로 넘길 수 없다.
  • 왼쪽 자식 자리에 오른쪽 서브트리 삽입 결과를 연결하는 식으로 좌우를 뒤바꾸면 기존 서브트리가 엇갈려 이진탐색트리의 대소 규칙이 깨진다.
문제 10
다음 데이터들을 공백힙(empty heap)에 차례대로 삽입하여 최대힙(max heap)을 생성하였다. 생성된 최대힙에 삭제 연산을 두 번 수행한 후의 결과는?
2, 13, 55, 8, 35, 47, 23, 19
1
2
3
4
정답 및 해설

두 번 삭제한 뒤의 최대힙은 레벨 순서로 35, 19, 23, 2, 8, 13이다(루트 35, 왼쪽 자식 19의 자식 2·8, 오른쪽 자식 23의 자식 13).

차례로 삽입하며 상향 조정하면 힙 배열은 55, 35, 47, 19, 8, 13, 23, 2가 된다.
첫 삭제: 55를 빼고 마지막 원소 2를 루트로 올려 하향 조정 → 47, 35, 23, 19, 8, 13, 2.
둘째 삭제: 47을 빼고 2를 루트로 올려 더 큰 자식과 교환 → 35, 19, 23, 2, 8, 13.

  • 루트 35의 왼쪽이 23, 오른쪽이 19인 트리: 첫 삭제 뒤 23은 47의 오른쪽 서브트리에 있었으므로 오른쪽 자식 자리에 남아야 한다.
  • 19의 자식이 2·13이고 23의 자식이 8인 트리: 8과 13의 위치가 서로 바뀌어 하향 조정 경로와 맞지 않는다.
  • 왼쪽 23(자식 2·13)·오른쪽 19(자식 8)인 트리: 좌우 서브트리와 리프 배치가 모두 실제 결과와 다르다.
문제 11
다음 연산식을 후위(postfix) 연산식으로 변환했을 때, 4번째 연산자는?
1 + (2 - 3 * 4 / (5 + 6)) - 7
1+
2-
3*
4/
정답 및 해설

후위 연산식은 1 2 3 4 * 5 6 + / - + 7 - 이며, 네 번째 연산자는 -이다.

괄호 안은 3*4를 (5+6)으로 나눈 뒤 2에서 빼므로 2 3 4 * 5 6 + / - 가 된다.
여기에 1을 더하고 7을 빼면 전체 식이 완성된다.

연산자 등장 순서: * → + → / → - → + → -

  • +는 두 번째(5+6)와 다섯 번째(1과의 덧셈)에 나온다.
  • *는 첫 번째 연산자이다.
  • /는 세 번째 연산자이다.
문제 12
다음 선형연결리스트(linear linked list)에서 LEE를 찾기 위한 비교 횟수는? (단, HEADER는 3 이다)
IndexNamePointer
1KIM6
2PARK1
3CHOI4
4BAEK2
5LEE7
6MIN5
7ANN8
8JUNG-
14
25
36
47
정답 및 해설

HEADER 3에서 출발해 포인터를 따라가면 LEE는 여섯 번째 노드에서 찾으므로 비교 횟수는 6회이다.

탐색 경로: CHOI(3) → BAEK(4) → PARK(2) → KIM(1) → MIN(6) → LEE(5)

선형연결리스트는 순차 탐색만 가능하므로 인덱스 순서가 아니라 포인터 순서대로 비교한다.

  • 비교 4회는 KIM까지만 비교한 경우이다.
  • 비교 5회는 MIN까지만 비교한 경우이다.
  • 비교 7회는 LEE를 지나 ANN까지 비교한 경우이다.
문제 13
정렬(sort)에 대한 설명으로 옳지 않은 것은?
1퀵정렬(quick sort)은 스택을 이용하여 수행한다.
2쉘정렬(shell sort)은 최적의 경우에 선택정렬(selection sort) 보다 빠르다.
3힙정렬(heap sort)은 배열을 이용한 포화 이진트리(full binary tree)를 사용한다.
410개 데이터의 버블정렬(bubble sort)은 최대 45번의 비교 연산을 수행한다.
정답 및 해설

힙정렬은 배열로 표현한 완전 이진트리(complete binary tree)를 사용하므로, 포화 이진트리를 사용한다는 설명이 옳지 않다.

포화 이진트리는 모든 레벨이 꽉 찬 트리라 노드 수가 2k−12^{k}-1일 때만 성립하지만, 힙은 마지막 레벨이 왼쪽부터 채워진 완전 이진트리면 된다.

  • 퀵정렬은 분할된 구간을 재귀 호출(스택)로 처리한다 — 옳다.
  • 쉘정렬은 이미 정렬된 최선의 경우 O(nlog⁡n)O(n \log n) 수준으로, 입력과 무관하게 항상 O(n2)O(n^{2})인 선택정렬보다 빠르다 — 옳다.
  • 10개 데이터의 버블정렬 최대 비교 횟수는 9+8+…+1 = 45이다 — 옳다.
문제 14
해시함수(hash function)로 h(k)=k mod 7을 사용하고, 선형탐색(linear probing) 기법을 이용하여 충돌을 해결하고자 한다. 키가 3, 10, 5, 9, 12 순서대로 입력되었을 때, 생성된 해시테이블은?
1
[0][1][2][3][4][5][6]
1293105
2
[0][1][2][3][4][5][6]
1231059
3
[0][1][2][3][4][5][6]
9103125
4
[0][1][2][3][4][5][6]
9310512
정답 및 해설

선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.

3 → 3 mod 7 = 3, [3]에 저장
10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
5 → 5 mod 7 = 5, [5]에 저장
9 → 9 mod 7 = 2, [2]에 저장
12 → 12 mod 7 = 5, 충돌 → [6]에 저장

  • 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
  • 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
  • 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.
문제 15
비어있는 이진 탐색 트리(binary search tree)에 다음 키 값들을 차례로 삽입하여 동적으로 이진 탐색 트리를 구성하였을 때, 5를 탐색하는데 필요한 비교 횟수는?
23, 18, 2, 16, 4, 10, 5, 39, 26, 15
13
25
37
49
정답 및 해설

5를 찾으려면 23 → 18 → 2 → 16 → 4 → 10 → 5 순으로 7회 비교가 필요하다.

삽입 결과 23의 왼쪽 18, 18의 왼쪽 2, 2의 오른쪽 16, 16의 왼쪽 4, 4의 오른쪽 10, 10의 왼쪽 5가 연결되어 한쪽으로 길게 늘어진 편향된 경로가 생긴다.

  • 비교 3회는 2까지만 내려간 경우이다.
  • 비교 5회는 4까지만 내려간 경우이다.
  • 비교 9회는 루트에서 5까지의 경로 길이보다 많아 성립하지 않는다.
문제 16
다음 그래프를 이용하여 Kruskal 알고리즘을 적용하였을 때, 생성된 최소 비용 신장 트리의 비용은?
111
212
313
414
정답 및 해설

Kruskal 알고리즘으로 만든 최소 비용 신장 트리의 비용은 13이다.

정점 6개이므로 간선 5개가 필요하다. 가중치가 작은 간선부터 사이클이 생기지 않는 것만 고르면 1 → 2 → 2를 채택하고, 가중치 3인 간선은 이미 연결된 두 정점을 잇는 사이클이 되어 버린다. 이어서 가중치 4인 간선 두 개를 채택하면 모든 정점이 연결된다.

1+2+2+4+4=131 + 2 + 2 + 4 + 4 = 13

  • 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
  • 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
  • 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.
문제 17
다음과 같은 4개의 노드를 가진 2-3 트리에 키 값 6을 추가하였을 때, 트리의 전체 노드의 수는?
14개
25개
36개
47개
정답 및 해설

키 6을 넣으면 분할이 루트까지 전파되어 높이가 늘고, 전체 노드는 7개가 된다.

6은 오른쪽 리프 [7, 9]에 들어가 [6, 7, 9]로 넘치므로 분할되고 가운데 키 7이 부모로 올라간다. 루트가 [2, 4, 7]로 다시 넘쳐 분할되며 4가 새 루트가 된다.

결과: 루트 [4] / 내부 노드 [2], [7] / 리프 [1], [3], [6], [9] → 1 + 2 + 4 = 7개.

  • 4개: 삽입 전 노드 수 그대로이며, 리프가 넘쳐 분할되는 것을 반영하지 않았다.
  • 5개: 리프 분할만 반영하고 루트 분할을 빠뜨린 경우다.
  • 6개: 루트 분할은 반영했으나 새 루트 노드 생성을 세지 않은 경우다.
문제 18
다항식(polynomial) 표현을 위해 구조체 poly를 정의하였다. 이 구조체를 이용하여 A(x)=−3x999−2x888+1A(x) = -3x^{999} -2x^{888} + 1과 B(x)=x10+x9+x5B(x) = x^{10} + x^{9} + x^{5}을 저장하기 위한 최소 메모리 용량[byte]은? (단, 정수(int)를 표현하는 데 2 byte를 사용하고, 실수(float)를 표현하는 데 4 byte를 사용한다)
typedef struct {
int exp;
float coef;
} poly;
122
224
336
438
정답 및 해설

0이 아닌 항만 (exp, coef) 쌍으로 저장하는 희소 다항식 표현을 쓰면 최소 메모리는 36 byte이다.

poly 하나의 크기: int 2 byte + float 4 byte = 6 byte
A(x)의 항 3개 + B(x)의 항 3개 = 6개
6 × 6 = 36 byte

  • 22 byte는 poly 6개(36 byte)를 담기에 부족하다.
  • 24 byte는 poly 4개 분량에 불과하다.
  • 38 byte는 36 byte에 int 하나(2 byte)를 더 쓴 값으로 최소가 아니다.
문제 19
다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도가 가장 큰 것은?
1임의의 정수 100,000개를 선택정렬(selection sort)로 정렬하는 문제
2정렬된 100,000개의 정수에서 임의의 정수를 이진탐색하는 문제
3반복 호출로 피보나치수열 F0F_{0}, F1F_{1}, F2F_{2}, … 에서 F100000F_{100000} 값을 구하는 문제
4재귀호출로 하노이 탑(tower of Hanoi)의 100,000개 원판 이동 문제
정답 및 해설

하노이 탑의 원판 이동 횟수는 2n−12^{n}-1로 지수 시간이므로 시간복잡도가 가장 크다.

원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1, 즉 O(2n)O(2^{n})이다.

  • 선택정렬은 O(n2)O(n^{2})로 다항 시간이다.
  • 정렬된 배열의 이진탐색은 O(log⁡n)O(\log n)이다.
  • 반복문으로 피보나치 수를 구하면 O(n)O(n)이다.
문제 20
구조체 list를 이용한 두 개의 단순연결리스트 x, y의 후위노드(음영부분)들을 서로 스왑(swap)하기 위한 코드는? (단, 후위노드들의 next는 NULL이 아니다)
struct list { int data; struct list *next; } *x, *y, *tmp;

1tmp = x->next;
x->next->next = y->next->next;
y->next->next = tmp;
tmp = y->next;
x->next = y->next;
y->next = tmp;
2tmp = x->next->next;
x->next->next = y->next->next;
y->next->next = tmp;
tmp = x->next;
x->next = y->next;
y->next = tmp;
3tmp = x->next;
x->next = y->next;
y->next = tmp;
tmp = x->next;
x->next->next = y->next->next;
y->next->next = tmp;
4tmp = x->next->next;
y->next->next = tmp;
x->next->next = y->next->next;
tmp = x->next;
y->next = tmp;
x->next = y->next;
정답 및 해설

음영 노드를 바꾸려면 음영 노드의 next(뒤 연결)를 먼저 교환하고, 그다음 x->next와 y->next를 교환해야 한다. 즉 tmp = x->next->next로 시작해 뒤 연결을 맞바꾼 뒤 tmp = x->next로 앞 연결을 맞바꾸는 코드가 옳다.

뒤 연결을 먼저 바꾸면 각 음영 노드가 상대 리스트의 세 번째 노드를 가리키게 되고, 이후 앞 연결을 바꾸면 x와 y 리스트에 상대 음영 노드가 끼워져 교환이 완성된다.

  • tmp = x->next로 시작하는 코드: y->next->next에 x의 음영 노드 자체를 넣어 x의 세 번째 노드 연결을 잃는다.
  • 앞 연결(x->next, y->next)을 먼저 교환하는 코드: 이후 x->next가 이미 y의 음영 노드를 가리키므로 뒤 연결 교환이 어긋나, y 리스트가 x의 음영 노드·y의 음영 노드·x의 세 번째 노드 순으로 이어지고 y의 세 번째 이후 노드를 잃는다.
  • y->next->next = tmp를 먼저 대입하는 코드: y의 세 번째 노드 주소를 저장 없이 덮어써 y 쪽 뒤 리스트를 잃는다.