[7급 국가직 자료구조론] 24년 1회차 기출문제 정답·해설 페이지

값 7은 색인 6에 저장된다.
최대 힙은 새 키를 마지막 위치에 넣고 부모보다 크면 위로 교환한다. 15, 10, 12, 8, 9, 7은 교환 없이 색인 1~6에 차례로 들어가므로 7은 색인 6에 놓인다.
마지막 20은 색인 7에 들어간 뒤 부모 12(색인 3), 다시 루트 15(색인 1)와 교환되어 배열은 20, 10, 15, 8, 9, 7, 12가 된다. 이 과정에서 색인 6의 7은 움직이지 않는다.
색인 4에는 8이 그대로 남는다.
색인 5에는 9가 그대로 남는다.
색인 7에는 20과 자리를 바꾼 12가 내려온다.

이진 탐색 트리를 중위 순회하면 키가 오름차순으로 나오므로 결과는 0 1 2 3 4 5 6 7 8 9이다.
BST는 모든 노드에서 왼쪽 서브트리 < 루트 < 오른쪽 서브트리가 성립하고, 중위 순회는 왼쪽 → 루트 → 오른쪽 순으로 방문하므로 삽입 순서와 관계없이 정렬된 순서가 된다.
0 2 4 3 1 6 5 9 8 7은 같은 트리를 후위 순회한 결과이다.
7 5 1 0 3 2 4 6 8 9는 같은 트리를 전위 순회한 결과이다.
9 8 6 4 2 3 0 1 5 7은 오른쪽 서브트리를 먼저 방문하는 후위 순회(오른쪽 → 왼쪽 → 루트) 결과로, 중위 순회와 무관하다.

A에서 G까지의 최단 경로는 A → D → F → H → G(거리 5)이다.
다익스트라를 진행하면 먼저 거리 2인 D가 확정되고, D를 거쳐 F가 2+1=3, G가 2+5=7로 갱신된다. 이어 B(3), F(3)가 확정되며 F를 거쳐 C와 H가 각각 4, G는 3+5=8(갱신 없음)이 된다.
H(4)가 확정되면 H를 거친 G까지의 거리가 4+1=5로 갱신되어 최종 최단 거리가 된다.
B와 F를 거쳐 G로 가는 경로: 3+2+5=10으로 더 길다.
C와 F를 거쳐 G로 가는 경로: 6+1+5=12로 더 길다.
D와 F에서 곧바로 G로 가는 경로: 2+1+5=8로, H를 경유하는 5보다 길다.

밑줄 친 문장의 수행 빈도수는 $\dfrac{(n+1)(n+2)}{2}$이다.
바깥 반복은 i = 0, 1, …, n의 n+1회이고, 안쪽 반복은 j = i부터 n까지이므로 i마다 $n-i+1$회 수행된다.
$\sum_{i=0}^{n}(n-i+1) = (n+1)+n+\cdots+1 = \dfrac{(n+1)(n+2)}{2}$
$\dfrac{n(n+1)}{2}$는 1부터 n까지의 합으로, i = 0일 때의 n+1회를 빠뜨린 값이다.
$\dfrac{n(n-1)}{2}$는 n = 1일 때 0이지만, 실제로는 i = 0에서 2회, i = 1에서 1회로 3회 수행된다.
$\dfrac{(n-1)(n+1)}{2}$는 n = 0일 때 음수가 되어 수행 횟수가 될 수 없다(실제는 1회).

주어진 코드는 삽입 정렬이며 시간 복잡도는 $O(n^2)$이다.
바깥 반복은 n-1회이고, 안쪽 반복은 MaxData보다 큰 원소를 한 칸씩 뒤로 미는 동안 최대 i회 수행된다. 역순 입력(최악)에서는 $1+2+\cdots+(n-1) = \dfrac{n(n-1)}{2}$회 비교·이동한다.
$O(\log n)$은 탐색 범위를 절반씩 줄이는 이진 탐색 수준으로, 모든 원소를 다뤄야 하는 정렬에는 불가능하다.
$O(n\log n)$은 병합·힙 정렬 같은 분할 기반 정렬의 복잡도로, 원소를 한 칸씩 옮기는 이 코드의 최악보다 작다.
$O(n^3)$은 3중 반복에 해당하며, 이 코드는 2중 반복이다.

두 번째 분할 후 결과는 4 5 11 20 15 27 59 61 48 37이다.
첫 분할(피벗 27)은 왼쪽에서 27보다 큰 값, 오른쪽에서 27보다 작은 값을 찾아 교환한다. 37과 20, 61과 15를 교환한 뒤 두 포인터가 엇갈리면 피벗을 11과 교환해 11 5 20 4 15 | 27 | 59 61 48 37이 된다.
두 번째 분할은 왼쪽 부분 11 5 20 4 15(피벗 11)에서 20과 4를 교환하고, 엇갈린 위치의 4와 피벗을 교환해 4 5 11 20 15가 된다. 오른쪽 부분은 아직 분할 전이므로 59 61 48 37 그대로이다.
4 5 11 15 20 27 59 61 48 37은 20과 15의 순서까지 정리된 상태로, 이후 분할이 더 진행되어야 나온다.
4 5 11 15 20 27 59 37 48 61은 오른쪽 부분이 분할 전인데도 순서가 바뀌어 있다.
4 5 11 20 15 27 59 37 48 61도 왼쪽은 맞지만 분할 전인 오른쪽 부분의 61과 37이 자리를 바꾸어 있다.

출력은 R-3 R-2 R-0 R-2 R-3이다.
RecursiveFunc(3)은 R-3을 출력하고 3이 홀수이므로 RecursiveFunc(2)를 호출한다. 2는 R-2를 출력하고 짝수이므로 RecursiveFunc(0)을 호출하며, 0은 기저 조건(n <= 0)에 걸려 R-0만 출력하고 반환한다.
복귀하면서 재귀 호출 뒤의 printf가 실행되어 RecursiveFunc(2)가 R-2, RecursiveFunc(3)이 R-3을 차례로 출력한다.
R-3 R-2 R-0은 재귀 호출 뒤에 있는 복귀 시 출력문을 빠뜨린 것이다.
R-3 R-1 R-0 R-2 R-3은 홀수 3에서 n-1인 2가 아니라 1로 넘어간 것으로 추적한 결과다.
R-3 R-2 R-1 R-2 R-3은 짝수 2에서 n-2인 0이 아니라 1로 넘어간 것으로 추적한 결과다.

(가)는 left, (나)는 j<=right이다.
병합 결과를 쓰는 위치 k는 마지막에 sorted[left:right+1]을 arr로 복사하므로 구간 시작인 left에서 출발해야 한다. 병합 반복은 왼쪽 구간(i<=middle)과 오른쪽 구간(j<=right)에 모두 원소가 남아 있는 동안만 비교한다.
left / k<=right 조합은 오른쪽 구간이 먼저 소진돼도 k<=right가 참이어서 비교가 계속되고 arr[j]가 구간 밖을 읽는다.
middle / j<=right 조합은 병합 결과가 구간 중간부터 기록되어 복사 범위 sorted[left:right+1]과 어긋난다.
middle / k<=right 조합은 시작 위치와 반복 조건이 모두 틀렸다.

(가)는 212바이트, (나)는 44바이트이다.
배열 큐는 선언 시 QType 크기가 고정되므로 연산과 관계없이 int 3개와 int 배열 50칸으로 $4 \times 53 = 212$바이트이다.
연결 리스트 큐는 QType(포인터 2개 + int 1개) $8 \times 2 + 4 = 20$바이트에, 노드(int + 포인터) $4 + 8 = 12$바이트가 남은 노드 수만큼 더해진다. 세 번 삽입·한 번 삭제 후 노드는 2개이므로 $20 + 12 \times 2 = 44$바이트이다.
24바이트는 배열 큐의 크기가 될 수 없다. 배열 큐는 삽입 횟수와 관계없이 50칸 배열을 처음부터 포함한다.
56바이트는 삭제된 노드의 메모리 회수를 반영하지 않고 노드 3개분을 더한 값이다.

출력값은 10이다.
test[i][3-j]=i*4+j는 각 행을 거꾸로 채우므로 배열은 행 0: 3 2 1 0, 행 1: 7 6 5 4, 행 2: 11 10 9 8이 된다.
*(test+1)은 행 1의 시작 주소이고 여기에 5를 더하면, 행 우선 저장에서 선형 위치 1×4+5 = 9인 test[2][1]을 가리킨다. 그 값은 10이다.
9는 값이 아니라 선형 위치를 그대로 답한 것이다.
6은 행 1 안의 test[1][1] 값으로, 오프셋 5가 다음 행으로 넘어간다는 점을 놓친 것이다.
5도 행 1 안의 test[1][2] 값으로 같은 착오다.

(가)는 &a[index], (나)는 result->value이다.
max 함수의 반환형이 DataType *이므로 최댓값 원소의 주소를 반환해야 하고, 그 주소를 받은 result도 포인터이므로 멤버는 화살표 연산자로 접근한다.
&a[index] / result.value 조합은 포인터인 result에 점(.) 연산자를 써서 컴파일 오류가 난다.
a[index] / result->value 조합은 a[index]가 구조체 값 자체여서 포인터 반환형과 맞지 않는다.
a[index] / (*result).value 조합은 (나)가 result->value와 같아 옳지만, 반환값 a[index]가 포인터가 아니다.

후위 표기식은 a b + c d - /이다.
전위식 / + a b - c d는 연산자 /의 두 피연산자가 (+ a b)와 (- c d)이므로 중위식 (a+b) / (c-d)를 나타낸다. 각 부분을 후위로 바꾸면 a b +와 c d -이고, 마지막에 /를 붙인다.
a b c d + - /는 a / (b - (c+d))를 나타내는 다른 식이다.
a b / c d + -는 (a/b) - (c+d)를 나타낸다.
a b c d / + -는 a - (b + c/d)를 나타낸다.

(가)는 n=Node(data, self.top), (나)는 self.top=self.top.next이다.
push는 새 노드의 next가 기존 top을 가리키게 만든 뒤 top을 새 노드로 바꿔야 연결이 유지된다. pop은 꺼낼 노드를 n에 보관하고 top을 바로 아래 노드로 옮긴다.
Node(data, None) / self.top=n.next.next 조합은 새 노드가 기존 스택과 끊기고, pop에서 노드 하나를 건너뛴다.
Node(data, None) / self.top=self.top.next 조합은 pop은 맞지만 push할 때마다 기존 스택이 연결에서 사라진다.
Node(data, self.top) / self.top=n.next.next 조합은 push는 맞지만 n이 top이므로 두 칸 아래로 이동해 원소 하나가 사라진다.

올바른 순서는 b → d → a → c이다.
X의 기존 왼쪽 노드 정보(X -> Llink)는 Y를 연결하는 데 계속 필요하므로, X -> Llink를 Y로 바꾸는 연산은 맨 마지막에 해야 한다.
먼저 Y의 두 링크를 채우고(Y의 왼쪽 = X의 기존 왼쪽 노드, Y의 오른쪽 = X), 기존 왼쪽 노드의 Rlink를 Y로 바꾼 뒤, 마지막으로 X의 Llink를 Y로 바꾼다.
a → c → b → d: c 직후 X -> Llink가 이미 Y이므로 b에서 Y의 왼쪽 링크가 자기 자신을 가리키게 된다.
a → c → d → b: 같은 이유로 b가 Y -> Llink = Y가 되어 기존 왼쪽 노드와의 연결이 끊긴다.
b → c → a → d: c 후에 a를 하면 X -> Llink가 Y이므로 Y -> Rlink만 Y로 바뀌고, 기존 왼쪽 노드의 Rlink는 여전히 X를 가리킨다.

첫 노드부터 검사한 뒤 p가 다시 L로 돌아오면 멈추는 do-while(p!=L) 형태가 옳다.
원형 연결 리스트는 마지막 노드의 link가 첫 노드 L을 가리키므로 p가 L로 돌아오면 한 바퀴를 다 돈 것이다. 시작점 p가 이미 L이므로 조건 검사를 본문 실행 뒤에 해야 모든 노드를 검사할 수 있다.
while(p!=L) 형태는 p=L에서 시작하므로 반복문이 한 번도 실행되지 않아 항상 NULL을 반환한다.
while(p->link!=L) 형태는 마지막 노드에 도달하면 검사 전에 반복이 끝나 마지막 노드를 놓친다.
do-while(p->link!=L) 형태도 p가 마지막 노드로 이동하는 순간 조건이 거짓이 되어 마지막 노드를 검사하지 못한다.

<행 번호, 열 번호, 값> 쌍 표현에 14개가 필요하다는 설명이 옳지 않다.
이 표현은 0이 아닌 원소 하나당 행 번호·열 번호·값 3개를 저장하므로 $7 \times 3 = 21$개가 필요하고, 행렬 크기·원소 수를 담는 머리 행까지 두면 24개가 된다. 14개는 원소당 2개만 센 값이다.
행렬을 그대로 2차원 배열로 두면 $9 \times 12 = 108$개 공간이 필요하다.
108개 중 7개만 0이 아니므로 대부분의 공간이 낭비되어 기억 공간 활용도가 떨어진다.
단순 전치 알고리즘은 열마다 모든 항을 훑어 열의 수 × 항의 수에 비례하고, 최악에는 항의 수가 행의 수 × 열의 수가 되므로 열의 수의 제곱 × 행의 수가 된다.

heapify(a, 7) 수행 후 배열은 -1, 2, 4, 3, 6, 5, 7, 0이다.
이 함수는 최소 힙의 루트 삭제이다. 루트 1을 item에 보관하고 마지막 원소 5를 temp로 꺼낸 뒤 a[7]=0, n=6으로 만들고, 루트 자리에서 더 작은 자식과 temp를 비교하며 내려간다.
i=1: 자식 a[2]=2, a[3]=3 중 작은 2가 temp 5보다 작으므로 a[1]=2, i=2
i=2: 자식 a[4]=6, a[5]=4 중 작은 4가 5보다 작으므로 a[2]=4, i=5
j=10 > n이므로 종료하고 a[5]=5를 저장한다.
-1, 2, 3, 4, 6, 5, 7, 0은 a[2] 자리에 3이 올라가 있어, i=2에서 자식 6, 4 중 작은 4를 끌어올리는 과정과 맞지 않는다.
-1, 2, 3, 4, 5, 6, 7, 0은 완전히 정렬된 상태로, 한 경로만 따라 내려가는 삭제 연산의 결과가 아니다.
-1, 2, 4, 3, 5, 6, 7, 0은 temp 5가 a[4]에 들어간 형태로, 더 작은 자식 a[5]=4 쪽으로 내려가야 한다는 점과 맞지 않는다.

임계 경로의 길이는 12이며, 경로는 0 → 3 → 6 → 8(a2, a7, a10)이다.
각 정점의 가장 이른 발생 시각은 들어오는 간선 중 최댓값으로 구한다.
1: 5, 2: 3, 3: 4, 4: 3+1=4
5: max(5+2, 4+3)=7, 6: max(4+3, 4+5)=9, 7: 4+2=6
8: max(7+4, 9+3, 6+5)=max(11, 12, 11)=12
10: 0 → 2 → 4 → 6 → 8(3+1+3+3)의 길이로, 가장 긴 경로가 아니다.
11: 0 → 1 → 5 → 8이나 0 → 3 → 7 → 8의 길이로, 가장 긴 경로가 아니다.
13: 13이 되는 경로는 존재하지 않는다.

단일 회전은 1회, 이중 회전은 2회 발생한다.
빨강으로 삽입한 노드의 부모가 빨강일 때, 삼촌이 빨강이면 색 변경만 하고 삼촌이 검정(NIL 포함)이면 회전한다. 삽입 노드·부모·조부모가 일직선이면 단일 회전, 꺾여 있으면 이중 회전이다.
3 삽입: 2 → 6(오른쪽) → 3(왼쪽)으로 꺾이고 삼촌이 없어 이중 회전, 3이 루트가 된다.
4 삽입: 부모 6과 삼촌 2가 모두 빨강이라 색 변경만 한다.
5 삽입: 6 → 4(왼쪽) → 5(오른쪽)로 꺾이고 삼촌이 없어 이중 회전, 5가 4와 6의 부모가 된다.
1·7 삽입: 1은 부모가 검정이라 그대로, 7은 삼촌 4가 빨강이라 색 변경만 한다.
8 삽입: 6 → 7 → 8이 오른쪽 일직선이고 삼촌이 없어 단일 회전한다.
단일 1회·이중 1회로 보면 5 삽입 때의 꺾인 배치에서 일어나는 이중 회전을 빠뜨린 것이다.
단일 2회·이중 1회로 보면 색 변경만으로 해결되는 삽입을 회전으로 센 것이고, 이중 회전도 하나 빠졌다.
단일 2회·이중 2회로 보면 4나 7 삽입처럼 삼촌이 빨강인 경우를 회전으로 센 것이다.

(가)에는 1+count_node(n->left)가 들어간다.
전체 노드 수 = 현재 노드 1개 + 왼쪽 서브트리 노드 수 + 오른쪽 서브트리 노드 수라는 재귀 정의를 그대로 옮긴 것이다. 빈 트리(NULL)는 0을 반환해 재귀가 끝난다.
1만 두면 왼쪽 서브트리를 세지 않아 루트에서 오른쪽으로 이어진 노드만 센다.
n->data는 노드에 저장된 문자의 코드값을 더하므로 개수가 아니다.
count_node(n->left)만 두면 자기 자신을 세지 않아 모든 호출이 결국 0을 반환한다.

키 34는 반복 4회 만에 찾는다.
코드는 정렬된 리스트에 대한 이진 탐색이며, 반복마다 middle 값과 비교해 범위를 절반으로 줄인다.
1회: low=0, high=15 → middle=7, list[7]=27 < 34이므로 low=8
2회: low=8, high=15 → middle=11, list[11]=38 > 34이므로 high=10
3회: low=8, high=10 → middle=9, list[9]=30 < 34이므로 low=10
4회: low=10, high=10 → middle=10, list[10]=34로 탐색 성공
3회째 비교 대상은 30이어서 아직 키를 찾지 못한 상태다.
5회는 4회째에 return으로 반복이 끝나므로 나올 수 없다.
6회는 원소 16개에 대한 이진 탐색의 최대 반복 수인 5회보다도 많다.

키 45는 버킷 8에 저장된다.
앞의 키들을 먼저 배치한다.
7: h=7 → 버킷 7
20: h=7 충돌, f=9 → (7+9) mod 13 = 3
3: h=3 충돌, f=3 → (3+3) mod 13 = 6
19: h=6 충돌, f=8 → (6+8) mod 13 = 1
45: h=45 mod 13 = 6에서 충돌하고 f=45 mod 11 = 1이다. $h_1 = (6+1) \bmod 13 = 7$도 차 있으므로 $h_2 = (6+2 \times 1) \bmod 13 = 8$에 저장된다.
버킷 7은 첫 재조사 위치지만 이미 키 7이 있다.
버킷 5는 조사 순서 6 → 7 → 8에 나타나지 않는다.
버킷 11도 조사 순서에 나타나지 않는다.

옳은 것은 ㄱ, ㄹ이다.
그래프의 간선은 A→B, A→C, A→E, B→D, D→A, D→E, D→F, C→F, E→F의 9개이다.
ㄱ(옳음): B→D→A→E→F처럼 길이 4인 단순 경로가 있다. C와 E는 모두 F로만 나가므로 두 정점을 한 경로에 함께 담을 수 없어 길이 5(정점 6개)는 불가능하다.
ㄴ(틀림): 진입차수가 진출차수보다 큰 정점은 E(진입 2, 진출 1)와 F(진입 3, 진출 0)의 2개이다.
ㄷ(틀림): 정점 6개의 완전 방향 그래프는 간선 30개로 21개를 더해야 하고, 무방향으로 보아도 15개 중 9쌍이 이미 연결되어 있어 6개가 필요하다. 어느 쪽도 10개가 아니다.
ㄹ(옳음): A→B를 지우면 진입차수 0인 B부터 B, D, A 순으로 나오고, 그다음 C와 E가 동시에 진입차수 0이 되어 어느 쪽을 먼저 놓아도 되며 마지막이 F이다.

올바른 그림은 간선 0-1, 0-2, 1-2, 1-3, 2-3, 2-5, 3-5, 4-5, 5-6의 9개로 이루어진 그래프이다.
무방향 그래프의 인접 행렬은 대칭이므로 상삼각 부분의 1만 읽으면 간선 목록이 된다. 특히 정점 4는 5와만, 정점 6도 5와만 연결되며 0과 3은 연결되지 않는다.
0과 3이 연결되고 2-4, 3-6 간선이 있는 그림: 행렬의 0행 3열과 2행 4열이 0이므로 틀리다.
2와 4가 연결되고 2-5 간선이 없는 그림: 2행 5열이 1, 2행 4열이 0이므로 틀리다.
0-3, 3-4 간선이 있고 1-2, 2-5 간선이 없는 그림: 행렬과 여러 칸이 어긋난다.

여섯 번째 방문 노드는 깊이 우선 탐색이 I, 너비 우선 탐색이 H이다.
그래프의 간선은 A→B, A→D, B→G, C→A, C→H, D→I, E→C, E→F, F→B, G→H, I→H이며, A에서 도달 가능한 노드는 A, B, D, G, H, I뿐이다.
깊이 우선 탐색: A → B → G → H까지 내려간 뒤 되돌아와 D → I 순이므로 A, B, G, H, D, I.
너비 우선 탐색: A의 인접 B, D, 다음 단계로 B의 G와 D의 I, 마지막으로 H이므로 A, B, D, G, I, H.
C를 여섯 번째로 보는 경우: C로 들어오는 간선은 E→C뿐이라 A에서 C에 도달할 수 없다.
깊이 우선에서 D를 여섯 번째로 보는 경우: D는 다섯 번째로 방문된다.
깊이 우선에서 H를 여섯 번째로 보는 경우: H는 G 다음 네 번째로 방문된다.