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

세 정점 무방향 완전 그래프의 신장 트리는 3가지이다.
신장 트리는 정점 3개를 간선 2개로 잇으므로, 간선 3개 중 하나를 빼는 경우의 수만큼 생긴다. 케일리 공식으로도 $n^{n-2}=3^{1}=3$ 이다.
1가지: 어느 간선을 빼도 서로 다른 트리가 되므로 하나뿐일 수 없다.
2가지: 뺄 수 있는 간선 후보가 3개이므로 부족하다.
4가지: 간선 3개 중 2개를 고르는 경우는 $\binom{3}{2}=3$ 을 넘을 수 없다.

중위 순회 결과는 4, 2, 5, 1, 6, 3, 7이다.
중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순으로 방문한다. 루트 1의 왼쪽 서브트리(2를 루트로 4, 5가 자식)는 4, 2, 5, 오른쪽 서브트리(3을 루트로 6, 7이 자식)는 6, 3, 7 순이 되어 둘 사이에 루트 1이 들어간다.
2, 4, 5, 1, 3, 6, 7은 각 서브트리에서 루트를 먼저 방문하고 전체 루트를 가운데 둔 순서로, 중위 순회가 아니다.
2, 4, 5, 3, 6, 7, 1은 루트를 맨 마지막에 방문한 형태로 중위 순회 규칙과 맞지 않는다.
4, 5, 2, 1, 6, 7, 3은 각 서브트리를 후위 순회한 순서로, 서브트리 루트를 자식 사이가 아닌 뒤에 방문했다.

수행시간 효율이 좋은 순서는 A, C, B, D이다.
증가 속도는 $n\log n \lt n^2 \lt 2^n \lt n!$ 이다. 다항식은 지수보다 느리게, 지수는 팩토리얼보다 느리게 증가한다.
A, C, D, B: $n!$ 이 $2^n$ 보다 빠르게 커지므로 D가 B보다 뒤에 와야 한다.
C, A, B, D: $n^2$ 이 $n\log n$ 보다 크므로 C가 A보다 앞설 수 없다.
C, A, D, B: C·A 순서와 B·D 순서가 모두 뒤바뀌었다.

옳은 것은 ㄴ, ㄹ이다.
ㄴ: 트리는 노드가 n개이면 간선이 n−1개이므로 9개 노드는 간선 8개다.
ㄹ: 7개 노드의 최대 높이는 한 줄로 늘어선 경우 7, 최소 높이는 완전 이진 트리인 경우 3이므로 차는 4이다.
ㄱ: 높이 5인 이진 트리의 최대 노드 수는 $2^5-1=31$ 이므로 15가 아니다.
ㄷ: 인덱스 i의 부모는 $\lfloor i/2 \rfloor$ 이므로 13의 부모는 6이다.

최종 스택은 아래부터 3, 5, 8이 쌓인 상태이다.
push(3)·push(7) 후 pop()으로 7이 빠져 [3], push(5)·push(8)로 [3, 5, 8]이 된다. peek()은 top을 읽기만 하고 제거하지 않으며, push(10) 후 pop()으로 10이 빠져 [3, 5, 8]이 남는다.
3, 5만 남은 상태: peek()을 삭제 연산으로 오해한 결과다.
5, 8, 10이 남은 상태: 바닥의 3은 꺼낸 적이 없고 10은 마지막 pop()으로 제거된다.
10, 8, 5, 3이 가득 찬 상태: 마지막 pop()을 반영하지 않았다.

A로부터의 최단 거리를 오름차순으로 나열하면 3, 11, 13, 15, 16, 20, 21이다.
다익스트라 알고리즘으로 확정 순서를 따라가면 B(3), E(11), C(13)가 먼저 확정된다. 이어 F는 C를 거쳐 13+2=15, H는 E를 거쳐 11+5=16으로 확정된다.
D는 C를 거치면 22이지만 H를 거치면 16+4=20으로 더 짧고, G는 D를 거쳐 20+1=21로 확정된다.
3, 11, 13, 15, 16, 21, 22는 마지막 두 거리가 실제 최단 거리인 D의 20(H 경유), G의 21(D 경유)보다 커서 최단 경로 갱신을 놓친 나열이다.
3, 11, 13, 16, 18, 20, 21은 F를 B 경유 거리(18)로 잡아 C를 거치는 15를 반영하지 못했다.
3, 11, 13, 16, 18, 21, 22는 F와 D·G 모두에서 최단 경로 갱신을 놓친 결과다.

회전은 RR회전, LL회전, LR회전 순서로 일어난다.
6, 7, 8 삽입 시 6에서 오른쪽-오른쪽으로 치우쳐 RR회전 → 루트 7, 자식 6·8.
2, 1 삽입 시 6에서 왼쪽-왼쪽으로 치우쳐 LL회전 → 7의 왼쪽이 2(자식 1·6).
5는 6의 왼쪽에 붙어 루트 7의 왼쪽 높이 3, 오른쪽 높이 1이 되고 경로가 왼쪽-오른쪽이므로 LR회전 → 루트 6, 왼쪽 2(자식 1·5), 오른쪽 7(오른쪽 자식 8). 마지막 4는 5의 왼쪽에 붙지만 모든 노드의 균형 인수가 ±1 이내라 회전이 없다.
LL회전, LR회전, LR회전: 처음 6, 7, 8은 오른쪽으로 치우치므로 첫 회전은 RR이다.
LL회전, LR회전, RL회전: 첫 회전이 RR이어야 하고 4 삽입 때는 회전이 없다.
RR회전, LL회전, RL회전: 5의 삽입 경로는 왼쪽 후 오른쪽이므로 RL이 아니라 LR이다.

(가) p->b, (나) p->a, (다) p != s이며, 이를 (*p).b, (*p).a 로 표기한 조합이 맞다.
b는 값, a는 다음 노드 포인터이고 포인터의 멤버 접근 p->b는 (*p).b와 같다. 원형 리스트는 끝이 NULL이 아니라 처음 노드로 돌아오므로, 출발 노드 s로 되돌아올 때 멈춰야 한다.
p.b, p.a, p != NULL: p는 포인터라 점 연산자로 멤버에 접근할 수 없고, NULL을 만나지 않아 끝나지 않는다.
p->a, p->b, p != s: 값 멤버와 링크 멤버가 뒤바뀌었다.
p->b, p->a, p != NULL: 원형 리스트에는 NULL이 없어 무한 반복한다.

나머지와 다른 값을 출력하는 것은 *(p--)를 출력하는 줄이다.
p는 array+2로 값 2를 가리킨다. *(p-1)은 array[1]인 1, *p-1은 2−1인 1이다. *(p--)는 후위 감소라 현재 위치의 2를 출력한 뒤 p가 array+1로 옮겨지고, 이어지는 *p는 1이다.
*(p-1): 한 칸 앞 원소의 값 1을 출력한다.
*p-1: 역참조가 먼저라 2에서 1을 뺀 1을 출력한다.
마지막 *p: 앞 줄의 감소가 반영되어 1을 출력한다.

(가) left_h > right_h, (나) left_h + 1, (다) right_h + 1이다.
트리 높이는 두 서브트리 높이 중 큰 값에 현재 노드 1을 더한 것이다. 왼쪽이 더 크면 left_h + 1, 아니면 right_h + 1을 반환한다.
left_h > right_h, left_h, right_h: 현재 노드를 더하지 않아 어떤 트리든 높이가 0이 된다.
left_h < right_h, left_h, right_h: 작은 쪽을 고르고 1도 더하지 않는다.
left_h < right_h, left_h + 1, right_h + 1: 조건이 뒤집혀 더 낮은 서브트리 기준으로 높이를 반환한다.

간선의 최대 개수는 45개이다.
자기 간선과 중복 간선이 없으면 서로 다른 두 정점 쌍마다 간선이 최대 하나다. 완전 그래프의 간선 수는 $\dfrac{n(n-1)}{2}=\dfrac{10\times 9}{2}=45$ 이다.
42: 정점 쌍 수보다 3개 적어 최대가 아니다.
43: 정점 쌍 수보다 2개 적어 최대가 아니다.
44: 연결되지 않은 정점 쌍이 하나 남아 최대가 아니다.

(가) push(str[i]), (나) str[i] != pop()이다.
첫 반복에서 문자를 모두 스택에 넣으면 pop() 순서는 문자열의 역순이 된다. 두 번째 반복은 앞에서부터 읽은 문자와 역순 문자를 비교해, 하나라도 다르면 0을, 끝까지 같으면 1을 반환한다.
push(str[i]), str[i] == pop(): 같은 문자일 때 0을 반환해 회문을 거짓으로 판정한다.
push(str[top-i]), str[i] == pop(): top이 -1부터 시작해 엉뚱한 위치를 넣고, 비교 조건도 반대다.
push(str[top-i]), str[i] != pop(): 문자를 차례대로 넣지 못해 역순 비교가 성립하지 않는다.

(가) left <= right, (나) key < a[mid]이다.
원소 하나만 남은 left == right 구간도 검사해야 하므로 등호가 필요하다. key가 a[mid]보다 작으면 왼쪽 절반에 있으므로 right = mid - 1로 구간을 줄인다.
left < right, key < a[mid]: 원소 하나가 남은 구간을 검사하지 않아 찾지 못하는 경우가 생긴다.
left < right, key > a[mid]: 등호 누락에 더해 구간을 반대 방향으로 줄인다.
left <= right, key > a[mid]: key가 클 때 오른쪽 끝을 줄여 탐색 방향이 뒤집힌다.

(가) n-- > 1, (나) z = x + y이다.
피보나치 수는 앞 두 수의 합이므로 z = x + y 후 x, y를 한 칸씩 민다. n이 2 이상이면 반복은 n−1회 돌아야 하며, n-- > 1은 n=2에서 한 번 돌아 1을, n=3에서 두 번 돌아 2를 반환한다.
n-- > 1, z = x - y: 두 수의 차는 피보나치 수가 아니다.
n-- >= 1, z = x + y: n=2에서 두 번 돌아 2를 반환하므로 한 항 더 진행된다.
n-- <= 1, z = x - y: n이 2 이상이면 조건이 처음부터 거짓이라 반복하지 않는다.

A, B, C의 합은 206이다.
A: 높이 5인 완전 이진 트리의 최소는 4레벨까지 포화되고 5레벨에 노드 하나인 경우로 $2^4=16$
B: 높이 6인 포화 이진 트리는 $2^6-1=63$
C: 높이 7인 완전 이진 트리의 최대는 포화 상태로 $2^7-1=127$
합계는 $16+63+127=206$ 이다.
142: C를 높이 6 기준인 63으로 잡은 값과 같아 맞지 않는다.
209: B, C가 정해져 있으므로 A가 19여야 하지만 최소 노드 수는 16이다.
222: A를 $2^5=32$ 로 잡은 값으로, 높이 5의 최소 노드 수가 아니다.

한 단계 처리 후 두 트리의 가중치 합은 9와 16이므로 큰 값은 16이다.
Sollin 알고리즘은 각 트리(초기에는 각 노드)가 자신에 연결된 최소 가중치 간선을 하나씩 동시에 선택한다. A는 A-B(6), B와 E는 B-E(3), C와 D는 C-D(4), F는 F-C(5), G는 G-F(7)를 고른다.
그 결과 A-B-E 트리(6+3=9)와 C-D-F-G 트리(4+5+7=16)의 두 트리로 된 포리스트가 만들어진다.
9는 두 트리 중 작은 쪽인 A-B-E 트리의 가중치 합이다.
12는 D-F 간선의 가중치로, 각 노드의 최소 간선이 아니어서 이 단계에서 선택되지 않는다.
13은 어느 트리의 합과도 맞지 않는 값이다.

완성된 레드 블랙 트리의 전위 순회는 2B, 1B, 4R, 3B, 5B, 6R이다.
1(B), 3(R) 삽입 후 2를 넣으면 부모 3이 레드이고 삼촌이 없어 회전(오른쪽 후 왼쪽)하여 2B(1R, 3R)가 된다.
4 삽입 시 부모 3과 삼촌 1이 모두 레드라 색 변경: 1B, 3B, 루트 2는 블랙 유지.
5 삽입 시 부모 4는 레드, 삼촌이 없어 3에서 왼쪽 회전 → 4B(3R, 5R).
6 삽입 시 부모 5와 삼촌 3이 레드라 색 변경 → 3B, 5B, 4R.
최종 트리는 루트 2B, 왼쪽 1B, 오른쪽 4R(자식 3B·5B), 5B의 오른쪽 6R이다.
2B, 1R, 4R, 3B, 5B, 6R: 4 삽입 때 색 변경으로 1은 블랙이 된다.
4B, 2R, 1B, 3B, 5B, 6R: 루트가 바뀌는 회전은 2 삽입 때뿐이라 루트는 2로 유지된다.
4B, 2R, 1B, 3R, 5B, 6R: 루트가 2이고, 3은 마지막 색 변경에서 블랙이 된다.

(가)는 n.next = self.last.next, (나)는 self.last.next = n, (다)는 self.last = n 이 들어가 B, D, C 순이다.
self.last 가 마지막 노드를 가리키므로 self.last.next 는 첫 노드다. 새 노드를 끝에 붙이려면 먼저 새 노드가 첫 노드를 가리키게 하고, 기존 마지막 노드가 새 노드를 가리키게 한 뒤, 마지막으로 last 를 새 노드로 옮긴다.
예를 들어 insert(3) 시 3→1 연결, 2→3 연결, last=3 이 되어 그림처럼 1→2→3→1 원형이 되고 last 는 3을 가리킨다.
(가)에 n.next = self.last 를 두면 새 노드가 첫 노드가 아닌 기존 마지막 노드를 가리켜 원형 순서가 깨진다.
(나)에 self.last = n 을 먼저 실행하면 기존 마지막 노드를 잃어, 이어지는 self.last.next = n 이 새 노드 자신을 가리키게 만든다.

(가) top = temp->link, (나) return item이다.
pop은 top을 다음 노드로 옮긴 뒤 원래 top 노드(temp)를 해제하고, 미리 저장해 둔 item을 반환해야 한다.
temp = temp->link, return item: temp가 다음 노드로 바뀌어 엉뚱한 노드를 해제하고 top도 갱신되지 않는다.
temp = temp->link, return top->data: top이 갱신되지 않고 엉뚱한 노드를 해제한다.
top = temp->link, return top->data: 꺼낸 값이 아니라 새 top의 값을 반환하며, 스택이 비면 NULL을 참조한다.

충돌 횟수가 가장 많은 키는 21이다.
h(x) = x mod 13과 선형 조사로 넣으면 12→12, 15→2, 25→12 충돌 후 0, 34→8, 37→11, 75→10, 62→10부터 4회 충돌 후 1, 33→7, 47→8에서 1회 충돌 후 9, 55→3이다.
21은 8부터 9, 10, 11, 12, 0, 1, 2, 3이 모두 차 있어 9회 충돌 후 4에 들어간다. 이어 42는 3·4에서 2회 충돌 후 5, 53은 1부터 5까지 5회 충돌 후 6에 들어간다.
42: 2회 충돌에 그친다.
53: 5회 충돌이다.
62: 4회 충돌이다.

(가) curNode != NULL, (나) head = prevNode, (다) prevNode = curNode이다.
prevNode는 이번에 뒤집을 노드, curNode는 다음 노드를 미리 잡아 두는 포인터, head는 이미 뒤집힌 부분의 첫 노드이다. 반복마다 prevNode의 링크를 head로 돌리고, head를 prevNode로, prevNode를 curNode로 한 칸씩 전진시킨다.
a→b→c를 추적하면 head가 a, b, c로 바뀌며 c→b→a가 되고, curNode가 NULL이 된 반복에서 마지막 노드까지 처리된 뒤 종료한다.
curNode != NULL, head = curNode, curNode = prevNode: head가 아직 뒤집지 않은 노드를 가리키고 포인터가 앞으로 나아가지 않는다.
head != NULL, head = curNode, curNode = prevNode: 시작 시 head가 NULL이라 반복이 실행되지 않는다.
head != NULL, head = prevNode, prevNode = curNode: 갱신 순서는 맞지만 시작 시 head가 NULL이라 반복에 들어가지 못한다.

키 45를 찾을 때까지 탐색 위치는 3회 계산된다.
보간 탐색의 위치 공식은 $low+\dfrac{(key-a[low])(high-low)}{a[high]-a[low]}$ 이다.
첫 계산: $0+\dfrac{43\times 12}{70}\approx 7.37$ → 위치 7, 키 27이 작으므로 low = 8
두 번째: $8+\dfrac{13\times 4}{40}=9.3$ → 위치 9, 키 42가 작으므로 low = 10
세 번째: $10+\dfrac{0\times 2}{27}=10$ → 위치 10에서 45를 찾는다.
2회: 두 번째로 계산한 위치의 키는 42로 아직 찾지 못했다.
4회: 세 번째 계산에서 이미 45를 찾는다.
5회: 세 번째 계산에서 탐색이 끝나므로 더 늘어날 수 없다.

count가 5일 때 출력되는 배열은 2 3 6 5 9 7이다.
간격 h=3: 5·3 정렬로 3 9 2 5 6 7(count 1), 9·6 정렬로 3 6 2 5 9 7(count 2), 2·7은 그대로(count 3).
간격 h=1: 6 삽입은 이동 없음(count 4), 2 삽입은 맨 앞까지 이동해 2 3 6 5 9 7(count 5)이 되어 이때 출력한다.
2 3 5 6 9 7: 5까지 삽입한 count 6 이후의 상태다.
3 6 2 5 9 7: 간격 3 단계가 끝난 count 3·4 시점의 상태다.
3 9 2 5 6 7: count 1 직후의 상태다.

삭제 후 인덱스 6에 저장된 데이터는 10이다.
삽입 과정에서 18은 8·15와, 22는 15·18과, 13은 10과, 26은 13·22와 교환되며 올라가 힙은 [26, 18, 22, 8, 15, 10, 13, 7]이 된다.
삭제 시 루트 26을 빼고 마지막 7을 루트로 옮긴 뒤 더 큰 자식과 교환한다: 7↔22, 이어 7↔13. 결과는 [22, 18, 13, 8, 15, 10, 7]이고 인덱스 6은 10 그대로이다.
8: 인덱스 4에 있다.
13: 재배치로 인덱스 3으로 올라간다.
15: 인덱스 5에 있다.

a[2][3]과 값이 다른 것은 *(a+5*2+3)이다.
a는 문자 5개짜리 행을 가리키는 포인터라 a+1은 한 행씩 이동한다. 따라서 a+13은 배열 범위 밖의 13행 뒤를 가리키고, 역참조 결과도 문자 값이 아니라 행 배열(주소)이다.
*(&a[0][0]+5*2+3): 문자 포인터에서 13칸 이동하므로 행 우선 저장에서 a[2][3]이다.
(a[0]+5*2)[3]: a[0]은 문자 포인터이므로 13칸 뒤 원소, 곧 a[2][3]이다.
(*(a+2))[3]: *(a+2)는 a[2]이므로 a[2][3]과 같다.