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

17년 1회차

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

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

17년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 C 언어 함수를 사용하여 function(9)를 수행했을 때, 반환되는 값은?
int function(int n)
{
if (n <= 1) return 1;
if (n % 2 == 0)
return n * function(n-1);
else
return n * function(n-3);
}
160
284
3540
4672
정답 및 해설

function(9)의 반환값은 540이다.

9는 홀수이므로 9×function(6), 6은 짝수이므로 6×function(5), 5는 홀수이므로 5×function(2), 2는 짝수이므로 2×function(1)로 이어지고, n ≤ 1이면 1을 반환하며 재귀가 끝난다.

되돌아오며 곱하면 function(2)=2, function(5)=5×2=10, function(6)=6×10=60, function(9)=9×60=540이다.

문제 2
다음 이진 트리(binary tree)의 순회 방법으로 옳지 않은 것은?
1전위(preorder) 순회 : A B G H D C E F I
2중위(inorder) 순회 : G B H D A C F E I
3후위(postorder) 순회 : G D H B F E I C A
4레벨 순서(level order) 순회 : A B C G H E D F I
정답 및 해설

후위 순회 결과를 G D H B F E I C A 로 적은 것이 옳지 않다. 실제 후위 순회는 G D H B F I E C A이다.

트리는 A의 왼쪽에 B(왼쪽 G, 오른쪽 H), H의 오른쪽에 D가 있고, A의 오른쪽에 C, C의 오른쪽에 E(왼쪽 F, 오른쪽 I)가 있다. 후위 순회는 왼쪽→오른쪽→루트 순이므로 E 서브트리는 F, I, E 순서로 방문해야 하는데, 해당 보기는 E를 I보다 먼저 적었다.

  • 전위 순회(루트→왼쪽→오른쪽): A B G H D C E F I 로 옳다.
  • 중위 순회(왼쪽→루트→오른쪽): G B H D A C F E I 로 옳다.
  • 레벨 순서 순회(깊이별 왼쪽부터): A / B C / G H E / D F I 이므로 A B C G H E D F I 로 옳다.
문제 3
다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph)에 대하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성했을 때, 최소 비용은?
[0][1][2][3]
[0]0512
[1]50∞4
[2]1∞03
[3]2430
16
27
38
49
정답 및 해설

최소 비용 신장 트리의 비용은 7이다.

간선을 가중치 순으로 나열하면 (0,2)=1, (0,3)=2, (2,3)=3, (1,3)=4, (0,1)=5이고, 정점 1과 2 사이는 ∞이므로 간선이 없다. 크루스칼 알고리즘으로 사이클이 생기지 않는 간선만 고른다.

  • (0,2)=1과 (0,3)=2를 차례로 선택한다.
  • (2,3)=3은 정점 0을 거쳐 이미 연결되어 사이클이 생기므로 제외한다.
  • (1,3)=4를 선택하면 정점 4개를 간선 3개로 모두 잇게 되어 완성된다.

합계는 1+2+4=7이다.

문제 4
78개의 간선(edge)으로 이루어진 이진 트리(binary tree)가 가질 수 있는 최대 높이와 최소 높이의 차이는? (단, 루트 노드만 존재하는 이진 트리의 높이는 1이다)
171
272
373
474
정답 및 해설

최대 높이와 최소 높이의 차이는 72이다.

간선이 78개이면 노드 수는 간선 수+1인 79개이다. 최대 높이는 노드가 한 줄로 이어진 편향 트리일 때로 79이다.

최소 높이는 완전 이진 트리 형태일 때로, 높이 h의 최대 노드 수 2h−12^h-1이 79 이상이 되는 최소 h를 찾는다.
26−1=63<79≤27−1=1272^6-1=63 \lt 79 \le 2^7-1=127이므로 최소 높이는 7이다.

따라서 차이는 79-7=72이다.

문제 5
1과 1000 사이의 정수로 구성된 이진 탐색 트리(binary search tree)에서 숫자 629를 탐색한다고 할 때, 옳지 않은 비교 순서는?
119, 929, 172, 891, 224, 735, 405, 674, 537, 629
2876, 807, 24, 186, 314, 717, 690, 428, 512, 629
329, 829, 815, 137, 369, 504, 805, 589, 692, 629
4926, 87, 813, 318, 572, 826, 635, 598, 580, 629
정답 및 해설

옳지 않은 비교 순서는 926, 87, 813, 318, 572, 826, …으로 이어지는 순서이다.

이진 탐색 트리에서는 비교할 때마다 탐색 범위가 좁아지므로, 이후 비교되는 값은 항상 지금까지의 하한과 상한 사이에 있어야 한다.

  • 926, 87, 813, … 순서: 629가 813보다 작아 왼쪽으로 내려갔으므로 이후 값은 813보다 작아야 하는데 826이 나와 모순이다.
  • 19, 929, 172, … 순서: 범위가 (19, 929) → (172, 929) → (172, 891) → … → (537, 674)로 일관되게 좁아져 가능하다.
  • 876, 807, 24, … 순서: 범위가 (24, 807) → … → (512, 690)으로 좁아지며 모든 값이 범위 안에 있어 가능하다.
  • 29, 829, 815, … 순서: 범위가 (29, 815) → … → (589, 692)로 좁아지며 모순이 없어 가능하다.
문제 6
단순 연결 리스트(singly linked list)의 노드를 나타내는 구조체 node에 다음 노드를 가리키는 포인터 link가 있다고 하자. 2개의 노드로 구성된 단순 연결 리스트에서 첫 번째 노드와 두 번째 노드의 사이에 새로운 노드를 삽입하면서 리스트의 순서를 역순으로 변환하고자 한다. p에는 리스트의 시작 주소가 저장되어 있으며, new에는 새로운 노드의 주소가 저장되어 있다고 가정할 때, 명령문의 실행 순서로 옳은 것은? (단, 역순 변환 후 p에는 리스트의 새로운 시작 주소가 저장되어 있어야 한다)
1p→link = new; p = p→link; new→link = p; new→link→link = NULL;
2p = p→link; p→link = new; new→link = p; new→link→link = NULL;
3new→link = p; p→link = new; p = p→link; new→link→link = NULL;
4new→link = p; p = p→link; p→link = new; new→link→link = NULL;
정답 및 해설

옳은 실행 순서는 new→link = p; p = p→link; p→link = new; new→link→link = NULL;이다.

처음 리스트를 A→B라 하면 목표는 B→new→A이고 p는 B를 가리켜야 한다. 이 순서는 new가 A를 가리키게 한 뒤 p를 B로 옮기고, B가 new를 가리키게 한 다음 A의 link를 NULL로 만들어 완성한다.

  • p→link = new 로 시작하는 순서: A의 link를 먼저 덮어써 B의 주소를 잃는다.
  • p = p→link; p→link = new; new→link = p 순서: new가 A가 아닌 B를 가리키게 되어 A가 리스트에서 빠진다.
  • new→link = p; p→link = new 로 시작하는 순서: A의 link를 new로 바꿔 B의 주소를 잃는다.
문제 7
다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 마지막 행은 정렬이 완료된 후의 결과이다. 중간의 행들은 합병정렬(merge sort), 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘을 통하여 얻을 수 있는 중간 과정을 보여준다. 각 행에 사용된 정렬 알고리즘을 바르게 나열한 것은? (단, 퀵정렬에서 피봇은 가장 오른쪽에 있는 원소를 사용한다)
입력214115252137459231836411
㉠915212125374145231836411
㉡491115183745412321362125
㉢152121253741459182341136
㉣491125213745412318362115
결과491115182121232536374145
㉠ ㉡ ㉢ ㉣
1삽입정렬 선택정렬 합병정렬 퀵정렬
2삽입정렬 퀵정렬 합병정렬 선택정렬
3합병정렬 선택정렬 삽입정렬 퀵정렬
4합병정렬 퀵정렬 선택정렬 삽입정렬
정답 및 해설

각 행은 차례로 삽입정렬, 선택정렬, 합병정렬, 퀵정렬의 중간 과정이다.

㉠은 앞의 8개만 정렬되어 있고 나머지는 입력 순서 그대로여서 정렬 구간을 하나씩 넓혀 가는 삽입정렬이다. ㉢은 정렬된 구간 3개(15~45의 7개, 9·18·23, 4·11·36)로 나뉘어 있어 부분 리스트를 정렬한 뒤 합치는 합병정렬이다.

㉡과 ㉣은 모두 최솟값을 앞으로 교환하는 선택정렬로 만들 수 있지만, ㉣은 맨 오른쪽 11을 피봇으로 분할한 결과(11 왼쪽에 4·9, 오른쪽에 더 큰 값)와도 같다. ㉡은 퀵정렬로 만들 수 없으므로 ㉡이 선택정렬, ㉣이 퀵정렬이다.

  • ㉡을 퀵정렬로 보는 나열: 18이 제자리에 오려면 그보다 먼저 남은 구간의 피봇 25가 제자리로 옮겨져야 하는데 ㉡에서는 25가 맨 끝에 남아 있다.
  • ㉠을 합병정렬로 보는 나열: 앞 8개만 정렬되고 나머지가 입력 그대로인 형태는 합병정렬의 분할·병합으로 나오지 않는다.
  • ㉢을 삽입정렬로 보는 나열: 뒤쪽 원소 9·18·23과 4·11·36이 입력과 다른 순서로 각각 정렬되어 있어 삽입정렬의 중간 결과가 아니다.
문제 8
다음은 차수가 3인 B+ 트리(tree)의 초기 상태이다. 이 트리에 색인키 'F', 'I', 'J'를 순서대로 삽입한 후의 모습은? (단, 단말 노드는 최대 2개의 원소를 포함할 수 있으며, 단말 노드의 분할 시 중간 위치의 값은 오른쪽 노드에 포함되도록 한다)
1
2
3
4
정답 및 해설

삽입 후 트리는 루트 G, 그 아래 D·I, 다시 그 아래 C·E·H·K, 단말 노드 [A B][C][D][E F][G][H][I J][K L]인 높이가 한 단계 늘어난 구조가 된다.

F는 단말 [D E]에 들어가 [D E F]로 넘치므로 [D][E F]로 분할되고 E가 부모 [C D]로 올라간다. 부모 [C D E]도 넘쳐 D가 루트로 올라가 루트는 [D G]가 된다. I는 단말 [H]에 들어가 [H I]가 된다.

J는 [H I]에 들어가 [H I J]가 되어 [H][I J]로 분할되고 I가 부모 [H K]로 올라간다. [H I K]는 [H][K]로 나뉘며 I가 루트로 올라가고, 루트 [D G I]도 넘쳐 G를 새 루트로 하여 [D][I]로 분할된다.

  • 루트가 G 하나이고 내부 노드가 [C E], [I K]로 남은 그림은 내부 노드 분할을 반영하지 않아 차수 3(키 최대 2개) 조건과 맞지 않는다.
  • 단말에 [H I][J]가 생긴 그림은 중간값을 왼쪽 노드에 둔 것으로, 중간값을 오른쪽 노드에 포함한다는 조건에 어긋난다.
  • 단말은 [I J][K L]인데 그 위 내부 노드를 J로 둔 그림은, 오른쪽 단말의 첫 키 K가 구분 키가 되어야 하므로 틀렸다.
문제 9
그림과 같은 최대 힙(max heap)을 구성하기 위한 삽입 순서로 옳은 것은?
150, 30, 40, 70, 60, 10, 20
210, 60, 50, 70, 20, 30, 40
310, 20, 40, 30, 60, 50, 70
450, 60, 30, 10, 20, 70, 40
정답 및 해설

그림의 최대 힙(배열 70, 50, 60, 10, 20, 30, 40)을 만드는 삽입 순서는 50, 60, 30, 10, 20, 70, 40이다.

50 다음 60이 들어오면 위로 교환되어 [60, 50]이 되고, 30·10·20은 부모보다 작아 그대로 붙어 [60, 50, 30, 10, 20]이 된다. 70은 30의 자식 자리에 들어가 30, 60과 차례로 교환되어 루트가 되고, 마지막 40은 부모 60보다 작아 그대로 남아 그림과 같아진다.

  • 50, 30, 40, 70, 60, 10, 20 순서는 70, 60이 왼쪽으로 올라가 [70, 60, 40, 30, 50, 10, 20]이 되어 다르다.
  • 10, 60, 50, 70, 20, 30, 40 순서는 [70, 60, 50, 10, 20, 30, 40]이 되어 루트의 왼쪽 자식이 60이므로 다르다.
  • 10, 20, 40, 30, 60, 50, 70 순서는 [70, 40, 60, 10, 30, 20, 50]이 되어 다르다.
문제 10
다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬 D-1, D0, D1, D2를 차례대로 구한다고 했을 때, D1의 계산 결과는?
1
[0][1][2]
[0]03∞
[1]602
[2]140
2
[0][1][2]
[0]035
[1]602
[2]140
3
[0][1][2]
[0]035
[1]302
[2]140
4
[0][1][2]
[0]03∞
[1]602
[2]150
정답 및 해설

플로이드 알고리즘으로 정점 V(0), V(1)까지 경유를 허용한 D^1은 0행이 0, 3, 5 / 1행이 6, 0, 2 / 2행이 1, 4, 0인 행렬이다.

그래프의 간선은 V(0)→V(1) 3, V(1)→V(0) 6, V(1)→V(2) 2, V(2)→V(0) 1, V(2)→V(1) 5이며, 이것이 초기 행렬 D^-1이다.

D^0(V(0) 경유): D[2][1]=min⁡(5, 1+3)=4D[2][1]=\min(5,\ 1+3)=4
D^1(V(1) 경유): D[0][2]=min⁡(∞, 3+2)=5D[0][2]=\min(\infty,\ 3+2)=5, D[2][0]=min⁡(1, 4+6)=1D[2][0]=\min(1,\ 4+6)=1

  • [0][2]가 ∞이고 [2][1]이 4인 행렬은 V(0)만 경유한 D^0이다.
  • [0][2]가 ∞이고 [2][1]이 5인 행렬은 경유 없는 초기 행렬 D^-1이다.
  • [1][0]이 3인 행렬은 V(2)까지 경유(6 대신 2+1)한 D^2로, D^1 단계에서는 아직 반영되지 않는다.
문제 11
다음은 연결 스택(linked stack)에서 새로운 노드를 삽입하는 C 언어 프로그램이다. ㉠, ㉡에 들어갈 내용으로 옳게 짝지은 것은? (단, top은 스택의 첫 번째 노드를 가리키는 포인터이며, top이 NULL이면 공백 스택이다)
typedef struct node {
int key;
struct node *link;
} StackNode;

StackNode *top = NULL;

void push(int data) {
StackNode *tmp = (struct node*)malloc(sizeof(StackNode));
if (tmp == NULL) {
printf("Memory allocation is failed.\n");
exit(1);
}
tmp→key = data;
if (top == NULL) {
tmp→link = NULL;
top = tmp;
}
else {
( ㉠ );
( ㉡ );
}
}
㉠ ㉡
1tmp→link = top top = tmp
2top→link = tmp tmp = top→link
3top→link = tmp tmp = top
4tmp→link = top top = tmp→link
정답 및 해설

㉠은 tmp→link = top, ㉡은 top = tmp이다.

연결 스택의 삽입은 새 노드를 맨 앞에 붙이는 것이므로, 먼저 새 노드가 기존 첫 노드를 가리키게 한 뒤 top을 새 노드로 옮긴다.

  • top→link = tmp, tmp = top→link 짝: 새 노드를 기존 top 뒤에 붙여 top이 바뀌지 않고, 기존 두 번째 노드 이후가 끊긴다.
  • top→link = tmp, tmp = top 짝: 역시 기존 top 뒤에 새 노드를 붙여 나머지 노드가 끊기고, tmp만 바뀔 뿐 top은 그대로이다.
  • tmp→link = top, top = tmp→link 짝: tmp→link가 기존 top이므로 top이 그대로 남아 새 노드가 스택에 들어가지 않는다.
문제 12
다음 키(key)를 갖는 데이터들을 공백 AVL 트리에 차례대로 저장하였다. 생성된 AVL 트리를 T라고 할 때, 다음 설명 중에서 옳은 것은?
12, 14, 9, 16, 19, 11
1T에 키가 25인 노드를 삽입하면 루트 노드가 바뀌게 된다.
2T에서 키가 9인 노드를 삭제하면 T의 높이가 1 감소한다.
3T에 키가 7인 노드를 삽입하면 T의 높이가 1 증가한다.
4키가 9인 노드와 키가 16인 노드는 형제 노드이다.
정답 및 해설

옳은 설명은 키가 9인 노드와 16인 노드가 형제라는 것이다.

12, 14, 9, 16을 넣은 뒤 19를 삽입하면 14에서 RR 불균형이 생겨 회전하고, 이어 11을 넣으면 T는 루트 12, 왼쪽 자식 9(오른쪽 자식 11), 오른쪽 자식 16(자식 14, 19)인 높이 3의 트리가 된다. 9와 16은 모두 루트 12의 자식이다.

  • 25를 삽입하는 경우: 19의 오른쪽에 붙어 루트의 균형 인수가 -1이 될 뿐 회전이 없으므로 루트는 12 그대로이다.
  • 9를 삭제하는 경우: 자식 11이 그 자리를 대신하고 12-16-14 경로가 남으므로 높이는 3 그대로이다.
  • 7을 삽입하는 경우: 9의 왼쪽에 붙어 왼쪽 서브트리 높이가 2로 유지되므로 T의 높이는 늘지 않는다.
문제 13
다음 C 언어 함수의 시간 복잡도를 빅오(O) 표기법으로 표현한 것은? (단, n>1n > 1)
void testing(int n)
{
int i, j, sum = 0;
for (i = 0; i < n; i++)
for (j = n; j > 1; j /= 2)
sum += 1;
}
1O(n)
2O(n2)
3O(nlogn)
4O(logn)
정답 및 해설

시간 복잡도는 O(n log n)이다.

바깥 반복문은 i가 0부터 n-1까지 n회 돈다. 안쪽 반복문은 j를 n에서 시작해 1보다 클 동안 절반씩 줄이므로 약 log n회 돈다. 전체 실행 횟수는 두 횟수의 곱인 약 n·log n이다.

  • O(n): 안쪽 반복의 log n배를 빠뜨린 결과이다.
  • O(n2)O(n^2): 안쪽 반복이 n회일 때의 결과인데, j는 1씩이 아니라 절반씩 줄어든다.
  • O(log n): 바깥 반복의 n회를 빠뜨린 결과이다.
문제 14
다음은 원형 연결 리스트(circular linked list)의 길이를 구하는 C 언어 프로그램이다. ㉠ ~ ㉢에 들어갈 내용으로 옳게 짝지은 것은?
typedef struct node {
int key;
struct node *link;
} list_node;
int length(list_node *ptr) {
list_node *temp;
int count = 0;
if ( ㉠ ) {
temp = ptr;
do {
count++;
( ㉡ );
} while ( ㉢ );
}
return count;
}
㉠ ㉡ ㉢
1ptr != NULL temp = temp→link temp != ptr
2ptr == NULL temp = temp→link temp == ptr
3ptr != NULL ptr = temp→link temp != ptr
4ptr == NULL ptr = temp→link temp == ptr
정답 및 해설

㉠은 ptr != NULL, ㉡은 temp = temp→link, ㉢은 temp != ptr이다.

리스트가 비어 있지 않을 때만 세기 시작하고, temp를 한 칸씩 옮기며 개수를 센 뒤 temp가 다시 시작 노드 ptr로 돌아오면 한 바퀴를 돈 것이므로 멈춘다.

  • ptr == NULL, temp = temp→link, temp == ptr 짝: 빈 리스트일 때만 반복에 들어가 NULL을 역참조하고, 비어 있지 않으면 0을 반환한다.
  • ptr != NULL, ptr = temp→link, temp != ptr 짝: temp는 움직이지 않고 ptr만 다음 노드로 바뀌어 노드가 2개 이상이면 무한 반복한다.
  • ptr == NULL, ptr = temp→link, temp == ptr 짝: 빈 리스트일 때만 진입해 NULL 역참조가 일어난다.
문제 15
이중 연결 리스트(doubly linked list)의 노드를 나타내는 구조체 node에 이전 노드를 가리키는 포인터 llink와 다음 노드를 가리키는 포인터 rlink가 있다고 하자. 포인터 new_node가 가리키는 노드를 포인터 p가 가리키는 노드의 왼쪽에 삽입할 때, 문장의 수행 순서를 바르게 나열한 것은?
ㄱ. p→llink→rlink = p→rlink;
ㄴ. p→rlink→llink = p→llink;
ㄷ. p→llink→rlink = new_node;
ㄹ. new_node→rlink = p;
ㅁ. p = new_node;
ㅂ. new_node→llink = p→llink;
ㅅ. p→llink = new_node;
1ㄱ → ㄴ
2ㅂ → ㅅ → ㄷ → ㄹ
3ㄷ → ㅂ → ㄹ → ㅁ
4ㄷ → ㄹ → ㅂ → ㅅ
정답 및 해설

올바른 순서는 ㄷ → ㄹ → ㅂ → ㅅ이다.

p의 왼쪽 노드를 L이라 하면 ㄷ으로 L의 오른쪽 링크를 new_node로, ㄹ로 new_node의 오른쪽 링크를 p로, ㅂ으로 new_node의 왼쪽 링크를 L로 잇고, 마지막에 ㅅ으로 p의 왼쪽 링크를 new_node로 바꾼다. p→llink를 바꾸는 ㅅ이 맨 뒤에 와야 앞 단계들이 p→llink로 L에 접근할 수 있다.

  • ㄱ → ㄴ: p가 가리키는 노드를 리스트에서 떼어 내는 삭제 연산이다.
  • ㅂ → ㅅ → ㄷ → ㄹ: ㅅ 이후 p→llink가 이미 new_node이므로 ㄷ이 new_node 자신의 오른쪽 링크를 바꾸게 되어 L의 링크가 갱신되지 않는다.
  • ㄷ → ㅂ → ㄹ → ㅁ: p의 왼쪽 링크를 new_node로 바꾸는 단계가 없고, 포인터 p만 new_node로 옮길 뿐이다.
문제 16
다음은 C 언어를 사용하여 원형 큐(circular queue)의 삽입(enqueue)과 삭제(dequeue) 연산을 구현한 것이다.
int Q[8] = {0};
int front = 0;
int rear = 0;

void enqueue(int item)
{
rear = (rear + 1) % 8;
if (front == rear) {
printf("Queue is full.\n");
return;
}
Q[rear] = item;
}

int dequeue()
{
int item;
if (front == rear) {
printf("Queue is empty.\n");
exit(1);
}
else {
front = (front + 1) % 8;
item = Q[front];
Q[front] = 0;
return item;
}
}
front와 rear의 값이 0인 공백 큐에 6개의 값 1, 3, 2, 4, 8, 6을 차례대로 삽입하고, 여기에서 2개의 값을 삭제한 다음, 다시 3개의 값 5, 7, 9를 차례대로 삽입할 때, 배열 Q의 최종 모습은?
Q[0]Q[1]Q[2]Q[3]Q[4]Q[5]Q[6]Q[7]
1
07924865
2
24865790
3
79024865
4
90248657
정답 및 해설

배열 Q의 최종 모습은 7, 9, 0, 2, 4, 8, 6, 5이다.

enqueue는 rear를 먼저 1 증가시킨 뒤 저장하므로 1, 3, 2, 4, 8, 6은 Q[1]~Q[6]에 들어가고 rear=6이 된다. dequeue 2회로 front가 2가 되며 Q[1], Q[2]는 0으로 지워진다.

이어서 5는 Q[7], 7은 (7+1)%8=0이므로 Q[0], 9는 Q[1]에 저장된다. 이때 rear=1, front=2로 가득 찬 상태가 아니다.

  • 0, 7, 9, 2, …, 5 배치: 7과 9를 지워진 칸 Q[1], Q[2]에 넣은 것으로, rear는 7 다음 0으로 이어진다.
  • 2, 4, 8, 6, 5, 7, 9, 0 배치: 원소를 앞으로 당겨 저장한 것으로, 원형 큐는 원소를 이동시키지 않는다.
  • 9, 0, 2, …, 7 배치: Q[0]부터 저장을 시작했다고 본 것으로, 이 구현은 rear를 먼저 증가시켜 Q[1]부터 저장한다.
문제 17
다음 C 프로그램의 출력 값으로 옳은 것은? (단, int 데이터 타입은 4 바이트로 표현되며, 배열 a의 시작 주소는 2293520이다)
int main()
{
int a[3][4] = {{10, 15, 20, 25}, {30, 35, 40, 45},
{50, 55, 60, 65}};
printf("a+1 = %d, ", a+1);
printf("*(*a+2) = %d, ", *(*a+2));
printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
return 0;
}
1a+1 = 2293521, *(*a+2) = 50, *(*(a+1)+2) = 55
2a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40
3a+1 = 2293521, *(*a+2) = 20, *(*(a+1)+2) = 40
4a+1 = 2293536, *(*a+2) = 50, *(*(a+1)+2) = 55
정답 및 해설

출력은 a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40이다.

a는 원소가 int[4]인 2차원 배열이므로 a+1은 행 하나(4×4=16바이트)만큼 증가해 2293520+16=2293536이다. *a는 a[0]의 시작 주소이므로 *(*a+2)는 a[0][2]=20이고, *(a+1)은 a[1]의 시작이므로 *(*(a+1)+2)는 a[1][2]=40이다.

  • 2293521, 50, 55 출력: 주소를 1바이트 단위로 증가시키고 원소도 다른 행에서 읽은 값이다.
  • 2293521, 20, 40 출력: 원소 값은 맞지만 포인터 연산은 가리키는 대상(행) 크기 단위로 증가하므로 1만 늘지 않는다.
  • 2293536, 50, 55 출력: 주소는 맞지만 *a+2는 a[0] 행 안에서 int 2개만큼 이동한 a[0][2]를 가리키므로 50이 될 수 없다.
문제 18
다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이 최소한 1개 이상인 연결 그래프의 개수는?
[0][1][2][3]
[0]0111
[1]1010
[2]1100
[3]1000
112
213
314
415
정답 및 해설

간선이 1개 이상인 연결 부분 그래프는 14개이다.

인접행렬에서 간선은 (0,1), (0,2), (0,3), (1,2)의 4개이다. 부분 그래프가 연결이려면 고른 간선들이 하나로 이어져 있어야 하므로 간선 수별로 센다.

  • 간선 1개: 4가지 모두 연결이다.
  • 간선 2개: 6가지 중 공통 정점이 없는 (0,3)과 (1,2) 조합만 끊어져 5가지이다.
  • 간선 3개: 4가지 모두 연결이다.
  • 간선 4개: 1가지이다.

합계는 4+5+4+1=14이다.

문제 19
기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 정렬하고자 한다. 각 단계별 정렬 순서로 나타날 수 없는 것은? (단, 정수 KK는 0≤K≤9990 \le K \le 999 범위에 있고 각 자리수를 나타내는 3개의 서브키(K1K^1, K2K^2, K3K^3)로 구성되어 있다고 생각한다. 여기서 K1K^1는 일의 자리 수, K2K^2는 십의 자리 수, K3K^3는 백의 자리 수를 의미하고, 0≤Ki≤90 \le K^i \le 9이다)
129, 308, 506, 92, 3, 841, 33
13, 506, 308, 129, 33, 841, 92
292, 3, 33, 129, 308, 506, 841
3841, 92, 3, 33, 506, 308, 129
43, 33, 92, 129, 308, 506, 841
정답 및 해설

나타날 수 없는 순서는 92, 3, 33, 129, 308, 506, 841이다.

기수 정렬은 일의 자리부터 안정적으로 분배·수집하므로 각 단계의 결과는 다음과 같다.

  • 일의 자리 기준: 841, 92, 3, 33, 506, 308, 129로 나타날 수 있다.
  • 십의 자리 기준: 3, 506, 308, 129, 33, 841, 92로 나타날 수 있다.
  • 백의 자리 기준: 3, 33, 92, 129, 308, 506, 841로 최종 결과이다.

92, 3, 33, … 순서는 처음 입력을 백의 자리만으로 분배한 결과로, 일의 자리부터 처리하는 기수 정렬의 어느 단계에서도 나오지 않는다.

문제 20
행렬 M=(aij)M=(a_{ij})가 ∣i−j∣>1|i-j| > 1 이면 0 값을 가질 때, 이러한 행렬을 삼중대각행렬(tridiagonal matrix)이라고 하며, 다음은 6×66 \times 6 삼중대각행렬의 예를 보여준다. (단, 1≤i≤m1 \le i \le m, 1≤j≤n1 \le j \le n)
[a11a120000a21a22a230000a32a33a340000a43a44a450000a54a55a560000a65a66]\begin{bmatrix} a_{11} & a_{12} & 0 & 0 & 0 & 0 \\ a_{21} & a_{22} & a_{23} & 0 & 0 & 0 \\ 0 & a_{32} & a_{33} & a_{34} & 0 & 0 \\ 0 & 0 & a_{43} & a_{44} & a_{45} & 0 \\ 0 & 0 & 0 & a_{54} & a_{55} & a_{56} \\ 0 & 0 & 0 & 0 & a_{65} & a_{66} \end{bmatrix}
행렬 M(m×n)M(m \times n)의 0이 아닌 원소 aija_{ij}를 열 우선(column major) 순서로 배열 A에 저장한다고 할 때, 0이 아닌 원소 aija_{ij}가 배열 A에 저장되는 위치를 계산하는 수식으로 옳은 것은? (단, 배열 A의 시작주소는 α\alpha이고, 행렬 MM의 0인 원소는 배열에 저장하지 않는다)
1α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)
2α+3⋅(j−1)+(j−i)\alpha+3 \cdot (j-1)+(j-i)
3α+3⋅(i−1)+(i−j)\alpha+3 \cdot (i-1)+(i-j)
4α+3⋅(i−1)+(j−i)\alpha+3 \cdot (i-1)+(j-i)
정답 및 해설

저장 위치 식은 α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)이며, 열 우선 순서에서 각 열의 0이 아닌 원소 개수로 구한다.

첫 열에는 원소가 2개, 나머지 열에는 3개씩 있으므로 j열 앞에 저장된 원소 수는 2+3(j−2)=3(j−1)−12+3(j-2)=3(j-1)-1이다. j열 안에서는 행 j-1, j, j+1 순으로 저장되어 열 안 오프셋이 i−j+1i-j+1이므로 위치는 α+3(j−1)−1+(i−j+1)=α+3(j−1)+(i−j)\alpha+3(j-1)-1+(i-j+1)=\alpha+3(j-1)+(i-j)이다.

검산: a11,a21,a12a_{11}, a_{21}, a_{12}의 위치가 각각 α,α+1,α+2\alpha, \alpha+1, \alpha+2로 맞는다.

  • 3⋅(j−1)+(j−i)3 \cdot (j-1)+(j-i)를 더하는 식: a21a_{21}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(i−j)3 \cdot (i-1)+(i-j)를 더하는 식: a12a_{12}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(j−i)3 \cdot (i-1)+(j-i)를 더하는 식: 행 우선 순서로 저장할 때의 위치 식이다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
17년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음 C 언어 함수를 사용하여 function(9)를 수행했을 때, 반환되는 값은?
int function(int n)
{
if (n <= 1) return 1;
if (n % 2 == 0)
return n * function(n-1);
else
return n * function(n-3);
}
160
284
3540
4672
정답 및 해설

function(9)의 반환값은 540이다.

9는 홀수이므로 9×function(6), 6은 짝수이므로 6×function(5), 5는 홀수이므로 5×function(2), 2는 짝수이므로 2×function(1)로 이어지고, n ≤ 1이면 1을 반환하며 재귀가 끝난다.

되돌아오며 곱하면 function(2)=2, function(5)=5×2=10, function(6)=6×10=60, function(9)=9×60=540이다.

문제 2
다음 이진 트리(binary tree)의 순회 방법으로 옳지 않은 것은?
1전위(preorder) 순회 : A B G H D C E F I
2중위(inorder) 순회 : G B H D A C F E I
3후위(postorder) 순회 : G D H B F E I C A
4레벨 순서(level order) 순회 : A B C G H E D F I
정답 및 해설

후위 순회 결과를 G D H B F E I C A 로 적은 것이 옳지 않다. 실제 후위 순회는 G D H B F I E C A이다.

트리는 A의 왼쪽에 B(왼쪽 G, 오른쪽 H), H의 오른쪽에 D가 있고, A의 오른쪽에 C, C의 오른쪽에 E(왼쪽 F, 오른쪽 I)가 있다. 후위 순회는 왼쪽→오른쪽→루트 순이므로 E 서브트리는 F, I, E 순서로 방문해야 하는데, 해당 보기는 E를 I보다 먼저 적었다.

  • 전위 순회(루트→왼쪽→오른쪽): A B G H D C E F I 로 옳다.
  • 중위 순회(왼쪽→루트→오른쪽): G B H D A C F E I 로 옳다.
  • 레벨 순서 순회(깊이별 왼쪽부터): A / B C / G H E / D F I 이므로 A B C G H E D F I 로 옳다.
문제 3
다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph)에 대하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성했을 때, 최소 비용은?
[0][1][2][3]
[0]0512
[1]50∞4
[2]1∞03
[3]2430
16
27
38
49
정답 및 해설

최소 비용 신장 트리의 비용은 7이다.

간선을 가중치 순으로 나열하면 (0,2)=1, (0,3)=2, (2,3)=3, (1,3)=4, (0,1)=5이고, 정점 1과 2 사이는 ∞이므로 간선이 없다. 크루스칼 알고리즘으로 사이클이 생기지 않는 간선만 고른다.

  • (0,2)=1과 (0,3)=2를 차례로 선택한다.
  • (2,3)=3은 정점 0을 거쳐 이미 연결되어 사이클이 생기므로 제외한다.
  • (1,3)=4를 선택하면 정점 4개를 간선 3개로 모두 잇게 되어 완성된다.

합계는 1+2+4=7이다.

문제 4
78개의 간선(edge)으로 이루어진 이진 트리(binary tree)가 가질 수 있는 최대 높이와 최소 높이의 차이는? (단, 루트 노드만 존재하는 이진 트리의 높이는 1이다)
171
272
373
474
정답 및 해설

최대 높이와 최소 높이의 차이는 72이다.

간선이 78개이면 노드 수는 간선 수+1인 79개이다. 최대 높이는 노드가 한 줄로 이어진 편향 트리일 때로 79이다.

최소 높이는 완전 이진 트리 형태일 때로, 높이 h의 최대 노드 수 2h−12^h-1이 79 이상이 되는 최소 h를 찾는다.
26−1=63<79≤27−1=1272^6-1=63 \lt 79 \le 2^7-1=127이므로 최소 높이는 7이다.

따라서 차이는 79-7=72이다.

문제 5
1과 1000 사이의 정수로 구성된 이진 탐색 트리(binary search tree)에서 숫자 629를 탐색한다고 할 때, 옳지 않은 비교 순서는?
119, 929, 172, 891, 224, 735, 405, 674, 537, 629
2876, 807, 24, 186, 314, 717, 690, 428, 512, 629
329, 829, 815, 137, 369, 504, 805, 589, 692, 629
4926, 87, 813, 318, 572, 826, 635, 598, 580, 629
정답 및 해설

옳지 않은 비교 순서는 926, 87, 813, 318, 572, 826, …으로 이어지는 순서이다.

이진 탐색 트리에서는 비교할 때마다 탐색 범위가 좁아지므로, 이후 비교되는 값은 항상 지금까지의 하한과 상한 사이에 있어야 한다.

  • 926, 87, 813, … 순서: 629가 813보다 작아 왼쪽으로 내려갔으므로 이후 값은 813보다 작아야 하는데 826이 나와 모순이다.
  • 19, 929, 172, … 순서: 범위가 (19, 929) → (172, 929) → (172, 891) → … → (537, 674)로 일관되게 좁아져 가능하다.
  • 876, 807, 24, … 순서: 범위가 (24, 807) → … → (512, 690)으로 좁아지며 모든 값이 범위 안에 있어 가능하다.
  • 29, 829, 815, … 순서: 범위가 (29, 815) → … → (589, 692)로 좁아지며 모순이 없어 가능하다.
문제 6
단순 연결 리스트(singly linked list)의 노드를 나타내는 구조체 node에 다음 노드를 가리키는 포인터 link가 있다고 하자. 2개의 노드로 구성된 단순 연결 리스트에서 첫 번째 노드와 두 번째 노드의 사이에 새로운 노드를 삽입하면서 리스트의 순서를 역순으로 변환하고자 한다. p에는 리스트의 시작 주소가 저장되어 있으며, new에는 새로운 노드의 주소가 저장되어 있다고 가정할 때, 명령문의 실행 순서로 옳은 것은? (단, 역순 변환 후 p에는 리스트의 새로운 시작 주소가 저장되어 있어야 한다)
1p→link = new; p = p→link; new→link = p; new→link→link = NULL;
2p = p→link; p→link = new; new→link = p; new→link→link = NULL;
3new→link = p; p→link = new; p = p→link; new→link→link = NULL;
4new→link = p; p = p→link; p→link = new; new→link→link = NULL;
정답 및 해설

옳은 실행 순서는 new→link = p; p = p→link; p→link = new; new→link→link = NULL;이다.

처음 리스트를 A→B라 하면 목표는 B→new→A이고 p는 B를 가리켜야 한다. 이 순서는 new가 A를 가리키게 한 뒤 p를 B로 옮기고, B가 new를 가리키게 한 다음 A의 link를 NULL로 만들어 완성한다.

  • p→link = new 로 시작하는 순서: A의 link를 먼저 덮어써 B의 주소를 잃는다.
  • p = p→link; p→link = new; new→link = p 순서: new가 A가 아닌 B를 가리키게 되어 A가 리스트에서 빠진다.
  • new→link = p; p→link = new 로 시작하는 순서: A의 link를 new로 바꿔 B의 주소를 잃는다.
문제 7
다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 마지막 행은 정렬이 완료된 후의 결과이다. 중간의 행들은 합병정렬(merge sort), 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘을 통하여 얻을 수 있는 중간 과정을 보여준다. 각 행에 사용된 정렬 알고리즘을 바르게 나열한 것은? (단, 퀵정렬에서 피봇은 가장 오른쪽에 있는 원소를 사용한다)
입력214115252137459231836411
㉠915212125374145231836411
㉡491115183745412321362125
㉢152121253741459182341136
㉣491125213745412318362115
결과491115182121232536374145
㉠ ㉡ ㉢ ㉣
1삽입정렬 선택정렬 합병정렬 퀵정렬
2삽입정렬 퀵정렬 합병정렬 선택정렬
3합병정렬 선택정렬 삽입정렬 퀵정렬
4합병정렬 퀵정렬 선택정렬 삽입정렬
정답 및 해설

각 행은 차례로 삽입정렬, 선택정렬, 합병정렬, 퀵정렬의 중간 과정이다.

㉠은 앞의 8개만 정렬되어 있고 나머지는 입력 순서 그대로여서 정렬 구간을 하나씩 넓혀 가는 삽입정렬이다. ㉢은 정렬된 구간 3개(15~45의 7개, 9·18·23, 4·11·36)로 나뉘어 있어 부분 리스트를 정렬한 뒤 합치는 합병정렬이다.

㉡과 ㉣은 모두 최솟값을 앞으로 교환하는 선택정렬로 만들 수 있지만, ㉣은 맨 오른쪽 11을 피봇으로 분할한 결과(11 왼쪽에 4·9, 오른쪽에 더 큰 값)와도 같다. ㉡은 퀵정렬로 만들 수 없으므로 ㉡이 선택정렬, ㉣이 퀵정렬이다.

  • ㉡을 퀵정렬로 보는 나열: 18이 제자리에 오려면 그보다 먼저 남은 구간의 피봇 25가 제자리로 옮겨져야 하는데 ㉡에서는 25가 맨 끝에 남아 있다.
  • ㉠을 합병정렬로 보는 나열: 앞 8개만 정렬되고 나머지가 입력 그대로인 형태는 합병정렬의 분할·병합으로 나오지 않는다.
  • ㉢을 삽입정렬로 보는 나열: 뒤쪽 원소 9·18·23과 4·11·36이 입력과 다른 순서로 각각 정렬되어 있어 삽입정렬의 중간 결과가 아니다.
문제 8
다음은 차수가 3인 B+ 트리(tree)의 초기 상태이다. 이 트리에 색인키 'F', 'I', 'J'를 순서대로 삽입한 후의 모습은? (단, 단말 노드는 최대 2개의 원소를 포함할 수 있으며, 단말 노드의 분할 시 중간 위치의 값은 오른쪽 노드에 포함되도록 한다)
1
2
3
4
정답 및 해설

삽입 후 트리는 루트 G, 그 아래 D·I, 다시 그 아래 C·E·H·K, 단말 노드 [A B][C][D][E F][G][H][I J][K L]인 높이가 한 단계 늘어난 구조가 된다.

F는 단말 [D E]에 들어가 [D E F]로 넘치므로 [D][E F]로 분할되고 E가 부모 [C D]로 올라간다. 부모 [C D E]도 넘쳐 D가 루트로 올라가 루트는 [D G]가 된다. I는 단말 [H]에 들어가 [H I]가 된다.

J는 [H I]에 들어가 [H I J]가 되어 [H][I J]로 분할되고 I가 부모 [H K]로 올라간다. [H I K]는 [H][K]로 나뉘며 I가 루트로 올라가고, 루트 [D G I]도 넘쳐 G를 새 루트로 하여 [D][I]로 분할된다.

  • 루트가 G 하나이고 내부 노드가 [C E], [I K]로 남은 그림은 내부 노드 분할을 반영하지 않아 차수 3(키 최대 2개) 조건과 맞지 않는다.
  • 단말에 [H I][J]가 생긴 그림은 중간값을 왼쪽 노드에 둔 것으로, 중간값을 오른쪽 노드에 포함한다는 조건에 어긋난다.
  • 단말은 [I J][K L]인데 그 위 내부 노드를 J로 둔 그림은, 오른쪽 단말의 첫 키 K가 구분 키가 되어야 하므로 틀렸다.
문제 9
그림과 같은 최대 힙(max heap)을 구성하기 위한 삽입 순서로 옳은 것은?
150, 30, 40, 70, 60, 10, 20
210, 60, 50, 70, 20, 30, 40
310, 20, 40, 30, 60, 50, 70
450, 60, 30, 10, 20, 70, 40
정답 및 해설

그림의 최대 힙(배열 70, 50, 60, 10, 20, 30, 40)을 만드는 삽입 순서는 50, 60, 30, 10, 20, 70, 40이다.

50 다음 60이 들어오면 위로 교환되어 [60, 50]이 되고, 30·10·20은 부모보다 작아 그대로 붙어 [60, 50, 30, 10, 20]이 된다. 70은 30의 자식 자리에 들어가 30, 60과 차례로 교환되어 루트가 되고, 마지막 40은 부모 60보다 작아 그대로 남아 그림과 같아진다.

  • 50, 30, 40, 70, 60, 10, 20 순서는 70, 60이 왼쪽으로 올라가 [70, 60, 40, 30, 50, 10, 20]이 되어 다르다.
  • 10, 60, 50, 70, 20, 30, 40 순서는 [70, 60, 50, 10, 20, 30, 40]이 되어 루트의 왼쪽 자식이 60이므로 다르다.
  • 10, 20, 40, 30, 60, 50, 70 순서는 [70, 40, 60, 10, 30, 20, 50]이 되어 다르다.
문제 10
다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬 D-1, D0, D1, D2를 차례대로 구한다고 했을 때, D1의 계산 결과는?
1
[0][1][2]
[0]03∞
[1]602
[2]140
2
[0][1][2]
[0]035
[1]602
[2]140
3
[0][1][2]
[0]035
[1]302
[2]140
4
[0][1][2]
[0]03∞
[1]602
[2]150
정답 및 해설

플로이드 알고리즘으로 정점 V(0), V(1)까지 경유를 허용한 D^1은 0행이 0, 3, 5 / 1행이 6, 0, 2 / 2행이 1, 4, 0인 행렬이다.

그래프의 간선은 V(0)→V(1) 3, V(1)→V(0) 6, V(1)→V(2) 2, V(2)→V(0) 1, V(2)→V(1) 5이며, 이것이 초기 행렬 D^-1이다.

D^0(V(0) 경유): D[2][1]=min⁡(5, 1+3)=4D[2][1]=\min(5,\ 1+3)=4
D^1(V(1) 경유): D[0][2]=min⁡(∞, 3+2)=5D[0][2]=\min(\infty,\ 3+2)=5, D[2][0]=min⁡(1, 4+6)=1D[2][0]=\min(1,\ 4+6)=1

  • [0][2]가 ∞이고 [2][1]이 4인 행렬은 V(0)만 경유한 D^0이다.
  • [0][2]가 ∞이고 [2][1]이 5인 행렬은 경유 없는 초기 행렬 D^-1이다.
  • [1][0]이 3인 행렬은 V(2)까지 경유(6 대신 2+1)한 D^2로, D^1 단계에서는 아직 반영되지 않는다.
문제 11
다음은 연결 스택(linked stack)에서 새로운 노드를 삽입하는 C 언어 프로그램이다. ㉠, ㉡에 들어갈 내용으로 옳게 짝지은 것은? (단, top은 스택의 첫 번째 노드를 가리키는 포인터이며, top이 NULL이면 공백 스택이다)
typedef struct node {
int key;
struct node *link;
} StackNode;

StackNode *top = NULL;

void push(int data) {
StackNode *tmp = (struct node*)malloc(sizeof(StackNode));
if (tmp == NULL) {
printf("Memory allocation is failed.\n");
exit(1);
}
tmp→key = data;
if (top == NULL) {
tmp→link = NULL;
top = tmp;
}
else {
( ㉠ );
( ㉡ );
}
}
㉠ ㉡
1tmp→link = top top = tmp
2top→link = tmp tmp = top→link
3top→link = tmp tmp = top
4tmp→link = top top = tmp→link
정답 및 해설

㉠은 tmp→link = top, ㉡은 top = tmp이다.

연결 스택의 삽입은 새 노드를 맨 앞에 붙이는 것이므로, 먼저 새 노드가 기존 첫 노드를 가리키게 한 뒤 top을 새 노드로 옮긴다.

  • top→link = tmp, tmp = top→link 짝: 새 노드를 기존 top 뒤에 붙여 top이 바뀌지 않고, 기존 두 번째 노드 이후가 끊긴다.
  • top→link = tmp, tmp = top 짝: 역시 기존 top 뒤에 새 노드를 붙여 나머지 노드가 끊기고, tmp만 바뀔 뿐 top은 그대로이다.
  • tmp→link = top, top = tmp→link 짝: tmp→link가 기존 top이므로 top이 그대로 남아 새 노드가 스택에 들어가지 않는다.
문제 12
다음 키(key)를 갖는 데이터들을 공백 AVL 트리에 차례대로 저장하였다. 생성된 AVL 트리를 T라고 할 때, 다음 설명 중에서 옳은 것은?
12, 14, 9, 16, 19, 11
1T에 키가 25인 노드를 삽입하면 루트 노드가 바뀌게 된다.
2T에서 키가 9인 노드를 삭제하면 T의 높이가 1 감소한다.
3T에 키가 7인 노드를 삽입하면 T의 높이가 1 증가한다.
4키가 9인 노드와 키가 16인 노드는 형제 노드이다.
정답 및 해설

옳은 설명은 키가 9인 노드와 16인 노드가 형제라는 것이다.

12, 14, 9, 16을 넣은 뒤 19를 삽입하면 14에서 RR 불균형이 생겨 회전하고, 이어 11을 넣으면 T는 루트 12, 왼쪽 자식 9(오른쪽 자식 11), 오른쪽 자식 16(자식 14, 19)인 높이 3의 트리가 된다. 9와 16은 모두 루트 12의 자식이다.

  • 25를 삽입하는 경우: 19의 오른쪽에 붙어 루트의 균형 인수가 -1이 될 뿐 회전이 없으므로 루트는 12 그대로이다.
  • 9를 삭제하는 경우: 자식 11이 그 자리를 대신하고 12-16-14 경로가 남으므로 높이는 3 그대로이다.
  • 7을 삽입하는 경우: 9의 왼쪽에 붙어 왼쪽 서브트리 높이가 2로 유지되므로 T의 높이는 늘지 않는다.
문제 13
다음 C 언어 함수의 시간 복잡도를 빅오(O) 표기법으로 표현한 것은? (단, n>1n > 1)
void testing(int n)
{
int i, j, sum = 0;
for (i = 0; i < n; i++)
for (j = n; j > 1; j /= 2)
sum += 1;
}
1O(n)
2O(n2)
3O(nlogn)
4O(logn)
정답 및 해설

시간 복잡도는 O(n log n)이다.

바깥 반복문은 i가 0부터 n-1까지 n회 돈다. 안쪽 반복문은 j를 n에서 시작해 1보다 클 동안 절반씩 줄이므로 약 log n회 돈다. 전체 실행 횟수는 두 횟수의 곱인 약 n·log n이다.

  • O(n): 안쪽 반복의 log n배를 빠뜨린 결과이다.
  • O(n2)O(n^2): 안쪽 반복이 n회일 때의 결과인데, j는 1씩이 아니라 절반씩 줄어든다.
  • O(log n): 바깥 반복의 n회를 빠뜨린 결과이다.
문제 14
다음은 원형 연결 리스트(circular linked list)의 길이를 구하는 C 언어 프로그램이다. ㉠ ~ ㉢에 들어갈 내용으로 옳게 짝지은 것은?
typedef struct node {
int key;
struct node *link;
} list_node;
int length(list_node *ptr) {
list_node *temp;
int count = 0;
if ( ㉠ ) {
temp = ptr;
do {
count++;
( ㉡ );
} while ( ㉢ );
}
return count;
}
㉠ ㉡ ㉢
1ptr != NULL temp = temp→link temp != ptr
2ptr == NULL temp = temp→link temp == ptr
3ptr != NULL ptr = temp→link temp != ptr
4ptr == NULL ptr = temp→link temp == ptr
정답 및 해설

㉠은 ptr != NULL, ㉡은 temp = temp→link, ㉢은 temp != ptr이다.

리스트가 비어 있지 않을 때만 세기 시작하고, temp를 한 칸씩 옮기며 개수를 센 뒤 temp가 다시 시작 노드 ptr로 돌아오면 한 바퀴를 돈 것이므로 멈춘다.

  • ptr == NULL, temp = temp→link, temp == ptr 짝: 빈 리스트일 때만 반복에 들어가 NULL을 역참조하고, 비어 있지 않으면 0을 반환한다.
  • ptr != NULL, ptr = temp→link, temp != ptr 짝: temp는 움직이지 않고 ptr만 다음 노드로 바뀌어 노드가 2개 이상이면 무한 반복한다.
  • ptr == NULL, ptr = temp→link, temp == ptr 짝: 빈 리스트일 때만 진입해 NULL 역참조가 일어난다.
문제 15
이중 연결 리스트(doubly linked list)의 노드를 나타내는 구조체 node에 이전 노드를 가리키는 포인터 llink와 다음 노드를 가리키는 포인터 rlink가 있다고 하자. 포인터 new_node가 가리키는 노드를 포인터 p가 가리키는 노드의 왼쪽에 삽입할 때, 문장의 수행 순서를 바르게 나열한 것은?
ㄱ. p→llink→rlink = p→rlink;
ㄴ. p→rlink→llink = p→llink;
ㄷ. p→llink→rlink = new_node;
ㄹ. new_node→rlink = p;
ㅁ. p = new_node;
ㅂ. new_node→llink = p→llink;
ㅅ. p→llink = new_node;
1ㄱ → ㄴ
2ㅂ → ㅅ → ㄷ → ㄹ
3ㄷ → ㅂ → ㄹ → ㅁ
4ㄷ → ㄹ → ㅂ → ㅅ
정답 및 해설

올바른 순서는 ㄷ → ㄹ → ㅂ → ㅅ이다.

p의 왼쪽 노드를 L이라 하면 ㄷ으로 L의 오른쪽 링크를 new_node로, ㄹ로 new_node의 오른쪽 링크를 p로, ㅂ으로 new_node의 왼쪽 링크를 L로 잇고, 마지막에 ㅅ으로 p의 왼쪽 링크를 new_node로 바꾼다. p→llink를 바꾸는 ㅅ이 맨 뒤에 와야 앞 단계들이 p→llink로 L에 접근할 수 있다.

  • ㄱ → ㄴ: p가 가리키는 노드를 리스트에서 떼어 내는 삭제 연산이다.
  • ㅂ → ㅅ → ㄷ → ㄹ: ㅅ 이후 p→llink가 이미 new_node이므로 ㄷ이 new_node 자신의 오른쪽 링크를 바꾸게 되어 L의 링크가 갱신되지 않는다.
  • ㄷ → ㅂ → ㄹ → ㅁ: p의 왼쪽 링크를 new_node로 바꾸는 단계가 없고, 포인터 p만 new_node로 옮길 뿐이다.
문제 16
다음은 C 언어를 사용하여 원형 큐(circular queue)의 삽입(enqueue)과 삭제(dequeue) 연산을 구현한 것이다.
int Q[8] = {0};
int front = 0;
int rear = 0;

void enqueue(int item)
{
rear = (rear + 1) % 8;
if (front == rear) {
printf("Queue is full.\n");
return;
}
Q[rear] = item;
}

int dequeue()
{
int item;
if (front == rear) {
printf("Queue is empty.\n");
exit(1);
}
else {
front = (front + 1) % 8;
item = Q[front];
Q[front] = 0;
return item;
}
}
front와 rear의 값이 0인 공백 큐에 6개의 값 1, 3, 2, 4, 8, 6을 차례대로 삽입하고, 여기에서 2개의 값을 삭제한 다음, 다시 3개의 값 5, 7, 9를 차례대로 삽입할 때, 배열 Q의 최종 모습은?
Q[0]Q[1]Q[2]Q[3]Q[4]Q[5]Q[6]Q[7]
1
07924865
2
24865790
3
79024865
4
90248657
정답 및 해설

배열 Q의 최종 모습은 7, 9, 0, 2, 4, 8, 6, 5이다.

enqueue는 rear를 먼저 1 증가시킨 뒤 저장하므로 1, 3, 2, 4, 8, 6은 Q[1]~Q[6]에 들어가고 rear=6이 된다. dequeue 2회로 front가 2가 되며 Q[1], Q[2]는 0으로 지워진다.

이어서 5는 Q[7], 7은 (7+1)%8=0이므로 Q[0], 9는 Q[1]에 저장된다. 이때 rear=1, front=2로 가득 찬 상태가 아니다.

  • 0, 7, 9, 2, …, 5 배치: 7과 9를 지워진 칸 Q[1], Q[2]에 넣은 것으로, rear는 7 다음 0으로 이어진다.
  • 2, 4, 8, 6, 5, 7, 9, 0 배치: 원소를 앞으로 당겨 저장한 것으로, 원형 큐는 원소를 이동시키지 않는다.
  • 9, 0, 2, …, 7 배치: Q[0]부터 저장을 시작했다고 본 것으로, 이 구현은 rear를 먼저 증가시켜 Q[1]부터 저장한다.
문제 17
다음 C 프로그램의 출력 값으로 옳은 것은? (단, int 데이터 타입은 4 바이트로 표현되며, 배열 a의 시작 주소는 2293520이다)
int main()
{
int a[3][4] = {{10, 15, 20, 25}, {30, 35, 40, 45},
{50, 55, 60, 65}};
printf("a+1 = %d, ", a+1);
printf("*(*a+2) = %d, ", *(*a+2));
printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
return 0;
}
1a+1 = 2293521, *(*a+2) = 50, *(*(a+1)+2) = 55
2a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40
3a+1 = 2293521, *(*a+2) = 20, *(*(a+1)+2) = 40
4a+1 = 2293536, *(*a+2) = 50, *(*(a+1)+2) = 55
정답 및 해설

출력은 a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40이다.

a는 원소가 int[4]인 2차원 배열이므로 a+1은 행 하나(4×4=16바이트)만큼 증가해 2293520+16=2293536이다. *a는 a[0]의 시작 주소이므로 *(*a+2)는 a[0][2]=20이고, *(a+1)은 a[1]의 시작이므로 *(*(a+1)+2)는 a[1][2]=40이다.

  • 2293521, 50, 55 출력: 주소를 1바이트 단위로 증가시키고 원소도 다른 행에서 읽은 값이다.
  • 2293521, 20, 40 출력: 원소 값은 맞지만 포인터 연산은 가리키는 대상(행) 크기 단위로 증가하므로 1만 늘지 않는다.
  • 2293536, 50, 55 출력: 주소는 맞지만 *a+2는 a[0] 행 안에서 int 2개만큼 이동한 a[0][2]를 가리키므로 50이 될 수 없다.
문제 18
다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이 최소한 1개 이상인 연결 그래프의 개수는?
[0][1][2][3]
[0]0111
[1]1010
[2]1100
[3]1000
112
213
314
415
정답 및 해설

간선이 1개 이상인 연결 부분 그래프는 14개이다.

인접행렬에서 간선은 (0,1), (0,2), (0,3), (1,2)의 4개이다. 부분 그래프가 연결이려면 고른 간선들이 하나로 이어져 있어야 하므로 간선 수별로 센다.

  • 간선 1개: 4가지 모두 연결이다.
  • 간선 2개: 6가지 중 공통 정점이 없는 (0,3)과 (1,2) 조합만 끊어져 5가지이다.
  • 간선 3개: 4가지 모두 연결이다.
  • 간선 4개: 1가지이다.

합계는 4+5+4+1=14이다.

문제 19
기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 정렬하고자 한다. 각 단계별 정렬 순서로 나타날 수 없는 것은? (단, 정수 KK는 0≤K≤9990 \le K \le 999 범위에 있고 각 자리수를 나타내는 3개의 서브키(K1K^1, K2K^2, K3K^3)로 구성되어 있다고 생각한다. 여기서 K1K^1는 일의 자리 수, K2K^2는 십의 자리 수, K3K^3는 백의 자리 수를 의미하고, 0≤Ki≤90 \le K^i \le 9이다)
129, 308, 506, 92, 3, 841, 33
13, 506, 308, 129, 33, 841, 92
292, 3, 33, 129, 308, 506, 841
3841, 92, 3, 33, 506, 308, 129
43, 33, 92, 129, 308, 506, 841
정답 및 해설

나타날 수 없는 순서는 92, 3, 33, 129, 308, 506, 841이다.

기수 정렬은 일의 자리부터 안정적으로 분배·수집하므로 각 단계의 결과는 다음과 같다.

  • 일의 자리 기준: 841, 92, 3, 33, 506, 308, 129로 나타날 수 있다.
  • 십의 자리 기준: 3, 506, 308, 129, 33, 841, 92로 나타날 수 있다.
  • 백의 자리 기준: 3, 33, 92, 129, 308, 506, 841로 최종 결과이다.

92, 3, 33, … 순서는 처음 입력을 백의 자리만으로 분배한 결과로, 일의 자리부터 처리하는 기수 정렬의 어느 단계에서도 나오지 않는다.

문제 20
행렬 M=(aij)M=(a_{ij})가 ∣i−j∣>1|i-j| > 1 이면 0 값을 가질 때, 이러한 행렬을 삼중대각행렬(tridiagonal matrix)이라고 하며, 다음은 6×66 \times 6 삼중대각행렬의 예를 보여준다. (단, 1≤i≤m1 \le i \le m, 1≤j≤n1 \le j \le n)
[a11a120000a21a22a230000a32a33a340000a43a44a450000a54a55a560000a65a66]\begin{bmatrix} a_{11} & a_{12} & 0 & 0 & 0 & 0 \\ a_{21} & a_{22} & a_{23} & 0 & 0 & 0 \\ 0 & a_{32} & a_{33} & a_{34} & 0 & 0 \\ 0 & 0 & a_{43} & a_{44} & a_{45} & 0 \\ 0 & 0 & 0 & a_{54} & a_{55} & a_{56} \\ 0 & 0 & 0 & 0 & a_{65} & a_{66} \end{bmatrix}
행렬 M(m×n)M(m \times n)의 0이 아닌 원소 aija_{ij}를 열 우선(column major) 순서로 배열 A에 저장한다고 할 때, 0이 아닌 원소 aija_{ij}가 배열 A에 저장되는 위치를 계산하는 수식으로 옳은 것은? (단, 배열 A의 시작주소는 α\alpha이고, 행렬 MM의 0인 원소는 배열에 저장하지 않는다)
1α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)
2α+3⋅(j−1)+(j−i)\alpha+3 \cdot (j-1)+(j-i)
3α+3⋅(i−1)+(i−j)\alpha+3 \cdot (i-1)+(i-j)
4α+3⋅(i−1)+(j−i)\alpha+3 \cdot (i-1)+(j-i)
정답 및 해설

저장 위치 식은 α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)이며, 열 우선 순서에서 각 열의 0이 아닌 원소 개수로 구한다.

첫 열에는 원소가 2개, 나머지 열에는 3개씩 있으므로 j열 앞에 저장된 원소 수는 2+3(j−2)=3(j−1)−12+3(j-2)=3(j-1)-1이다. j열 안에서는 행 j-1, j, j+1 순으로 저장되어 열 안 오프셋이 i−j+1i-j+1이므로 위치는 α+3(j−1)−1+(i−j+1)=α+3(j−1)+(i−j)\alpha+3(j-1)-1+(i-j+1)=\alpha+3(j-1)+(i-j)이다.

검산: a11,a21,a12a_{11}, a_{21}, a_{12}의 위치가 각각 α,α+1,α+2\alpha, \alpha+1, \alpha+2로 맞는다.

  • 3⋅(j−1)+(j−i)3 \cdot (j-1)+(j-i)를 더하는 식: a21a_{21}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(i−j)3 \cdot (i-1)+(i-j)를 더하는 식: a12a_{12}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(j−i)3 \cdot (i-1)+(j-i)를 더하는 식: 행 우선 순서로 저장할 때의 위치 식이다.