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

정점이 n개인 무방향 완전 그래프의 간선 수는 $\dfrac{n(n-1)}{2}$이므로 간선이 55개이면 정점은 11개이다.
공식: $\dfrac{n(n-1)}{2} = 55$
대입: $n(n-1) = 110 = 11 \times 10$
결과: $n = 11$
정점 8개: 간선은 $\dfrac{8 \times 7}{2} = 28$개이다.
정점 9개: 간선은 $\dfrac{9 \times 8}{2} = 36$개이다.
정점 10개: 간선은 $\dfrac{10 \times 9}{2} = 45$개이다.

두 차례 수행 뒤 앞쪽 3개(3, 18, 21)만 정렬되고 뒤쪽(33, 9, 15)은 그대로이므로 삽입 정렬이다.
삽입 정렬은 매 단계 다음 원소를 앞쪽 정렬 구간의 제자리에 끼워 넣는다.
1회: 3을 21 앞에 삽입 → 3, 21, 18, 33, 9, 15
2회: 18을 3과 21 사이에 삽입 → 3, 18, 21, 33, 9, 15
선택 정렬: 최솟값을 차례로 앞에 두므로 2회 후 3, 9, 18, 33, 21, 15가 된다.
버블 정렬: 큰 값이 뒤로 밀려나므로 2회 후 3, 18, 9, 15, 21, 33이 된다.
기수 정렬: 일의 자리 분배 후 21, 3, 33, 15, 18, 9가 되고, 십의 자리까지 2회 수행하면 전체가 정렬된다.

바깥 루프는 1000회, 가장 안쪽 루프는 200회로 고정되고 n에 비례하는 것은 가운데 루프뿐이므로 $O(n)$이다.
반복 횟수: i 루프 1000회 × j 루프 $n-502$회(j = 1 ~ n-502) × k 루프 200회
총 연산: $1000 \times 200 \times (n-502)$
상수 계수를 버리면 선형 시간이다.
$O(1)$: j 루프 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
$O(n^2)$: k 루프는 $n-100$부터 $n+100$ 직전까지로 폭이 200으로 고정되어 n에 비례하지 않는다.
$O(n^3)$: i 루프도 1000회 고정이라 n에 의존하는 루프는 하나뿐이다.

전위 순회와 중위 순회 결과가 같은 것은 모든 노드가 오른쪽 자식만 갖는 오른쪽 사향 트리(1 → 2 → 3 → 4 → 5)이다.
전위는 루트 → 왼쪽 → 오른쪽, 중위는 왼쪽 → 루트 → 오른쪽 순서이므로, 왼쪽 서브트리가 하나도 없으면 두 순회 모두 루트 → 오른쪽 순서가 되어 결과가 같다. 이 트리는 두 순회 모두 1, 2, 3, 4, 5이다.
5를 루트로 왼쪽 자식만 이어진 왼쪽 사향 트리: 전위는 5, 4, 3, 2, 1, 중위는 1, 2, 3, 4, 5로 정반대이다.
2를 루트로 왼쪽에 1, 오른쪽에 3 → 4 → 5가 이어진 트리: 전위는 2, 1, 3, 4, 5, 중위는 1, 2, 3, 4, 5로 앞부분이 다르다.
3을 루트로 왼쪽에 2 → 1, 오른쪽에 4 → 5가 있는 트리: 전위는 3, 2, 1, 4, 5, 중위는 1, 2, 3, 4, 5로 다르다.

(가)~(사)의 합은 6이다.
그래프의 간선은 a-b, a-c, a-d, b-e, c-d, c-e, d-e의 7개이며, 무방향 그래프의 인접 행렬은 대칭이고 자기 자신으로의 간선이 없으면 대각 원소가 0이다.
(가)·(나): a와 b가 연결되어 있으므로 둘 다 1이다.
(다)·(마): b와 e가 연결되어 있으므로 둘 다 1이다.
(라)·(바): c-d, d-e 간선이 있으므로 둘 다 1이다.
(사): e 자신으로의 간선이 없으므로 대각 원소는 0이다.
따라서 1이 6개, 0이 1개로 합은 6이다.

호출될 때마다 c를 먼저 출력하고 n이 0이 될 때까지 c를 1씩 늘려 재귀하므로 마지막 출력값은 5이다.
추적 (n, 출력되는 c): (20, 0) → (10, 1) → (5, 2) → (2, 3) → (1, 4) → (0, 5)
n이 0인 호출은 c를 출력한 뒤 c를 늘리지 않고 1을 반환하며 끝난다.
n은 짝수면 절반, 홀수면 $(n-1)/2$로 줄어들어 재귀 단계 수는 n의 이진수 자릿수(20 = 10100, 다섯 자리)와 같다.

부호 비트 1, 지수 131, 가수 01001이므로 값은 -20.5이다.
부호 비트: 1 → 음수
지수 8비트: 10000011 = 131 → 바이어스 127을 빼면 $131 - 127 = 4$
가수 23비트: 0100100…0 → $1.01001_{(2)}$
값: $-1.01001_{(2)} \times 2^{4} = -10100.1_{(2)}$
결과: $-(16 + 4 + 0.5) = -20.5$
10.5: 부호 비트가 1이므로 양수가 될 수 없다.
-10.75: $1010.11_{(2)}$이 되어야 하므로 지수가 3이어야 하는데 실제 지수는 4이다.
-20.75: $10100.11_{(2)}$이 되어야 하므로 가수가 010011로 끝나야 하는데 실제 가수는 01001 뒤가 모두 0이다.

삽입에서 6회, 삭제에서 4회 원소가 이동하므로 결과는 A, H, B, D, E, F, G이고 총이동 10회이다.
연산 1: 인덱스 1에 H를 넣으려면 B~G 6개를 한 칸씩 뒤로 옮긴다 → A, H, B, C, D, E, F, G (6회)
연산 2: 이제 인덱스 3의 원소는 C이므로 C를 지우고 D~G 4개를 한 칸씩 앞으로 당긴다 → A, H, B, D, E, F, G (4회)
A, H, C, 빈칸, E, F, G (3회): H가 B를 덮어써 B가 사라지고, 삭제 후 빈칸도 메우지 않은 상태다.
A, H, C, E, F, G (3회): 삽입 때 B를 뒤로 밀지 않고 덮어써 B가 사라진 상태다.
A, H, B, 빈칸, D, E, F, G (10회): 삭제 후 뒤 원소를 앞으로 당기지 않아 선형 리스트의 연속성이 깨진 상태다.

ㄱ은 틀리고 ㄴ과 ㄷ이 옳으므로 옳은 것은 ㄴ, ㄷ이다.
(가) 힙 구성: i=3에서 59와 자식 19 비교 → 그대로. i=2에서 11이 큰 자식 48(L[5])과 자리를 바꾼다. i=1에서 61이 두 자식보다 커서 그대로.
결과: (61, 48, 59, 15, 11, 19)
(나) 첫 회(i=5): L[1]과 L[6] 교환 → (19, 48, 59, 15, 11, 61)
adjust(L, 1, 5): 19가 큰 자식 59와 자리를 바꿈 → (59, 48, 19, 15, 11, 61)
ㄱ(틀림): 11은 큰 자식 48과 바뀌어 L[5]에 들어가므로 끝의 두 값은 11, 19 순서다.
ㄴ(옳음): 위 추적 결과와 같다.
ㄷ(옳음): (나) for 문은 약 n회 반복하고 매번 adjust가 힙 높이 $O(\log n)$만큼 내려가므로 $O(n\log n)$이다.

완성된 AVL 트리를 중위 순회하면 네 번째로 방문하는 노드는 15이다.
10 삽입: 19-7-10의 LR 불균형 → 10을 루트로 회전 (왼쪽 7, 오른쪽 19)
32 삽입: 루트 10의 오른쪽이 2 더 높은 RR 불균형 → 10 기준 좌회전으로 19가 루트가 된다.
17, 5 삽입 후에는 균형이 유지된다.
최종 트리: 루트 19, 왼쪽 10(자식 7, 15), 오른쪽 25(오른쪽 자식 32), 7의 왼쪽 5, 15의 오른쪽 17
중위: 5, 7, 10, 15, 17, 19, 25, 32
루트 노드는 17이 아니라 19이다.
전위 순회(19, 10, 7, 5, 15, 17, 25, 32)의 세 번째 노드는 7이다.
후위 순회(5, 7, 17, 15, 10, 32, 25, 19)의 다섯 번째 노드는 10이다.

연산을 모두 마치면 큐에는 D, E, F가 인덱스 0, 1, 2에 남는다 (front = 5, rear = 2).
front는 첫 원소의 한 칸 앞, rear는 마지막 원소 위치이며 인덱스는 $(i+1) \bmod 6$으로 순환한다.
B 삽입: rear 4 → 삭제: front 3 (A 제거) → C 삽입: rear 5 → D 삽입: rear 0
두 개 삭제: front 4 (B 제거), front 5 (C 제거) → E 삽입: rear 1 → F 삽입: rear 2
A, E, F가 남은 상태: A, B, C는 이미 삭제되었으므로 A가 남을 수 없다.
D, F, E가 [0], [4], [5]에 있는 상태: rear는 0 다음 1, 2로 진행하므로 E, F는 [1], [2]에 들어간다.
F, E, A가 남은 상태: 인덱스가 거꾸로 진행된 것이며 삭제된 A도 남아 있다.

레드-블랙 트리는 회전과 재색칠 후에도 이진 탐색 트리 성질을 유지하므로 중위 순회 결과는 항상 오름차순인 1, 2, 3, 4, 5이다.
1(루트, 흑) → 2(적) → 3 삽입 시 적색 연속으로 좌회전해 2가 루트 → 4 삽입 시 삼촌 1이 적색이라 재색칠 → 5 삽입 시 3 기준 좌회전으로 4가 3과 5의 부모가 된다.
최종 형태: 루트 2, 왼쪽 1, 오른쪽 4(자식 3, 5)
1, 3, 5, 4, 2: 최종 트리의 후위 순회 결과다.
2, 1, 3, 5, 4: 오름차순이 아니므로 이진 탐색 트리의 중위 순회가 될 수 없다.
2, 1, 4, 3, 5: 최종 트리의 전위 순회 결과다.

다섯째 노드는 전위 H, 중위 E, 후위 E이다.
트리는 A의 왼쪽 자식 B, 오른쪽 자식 C이고, B 아래 D(자식 G, H)와 E(오른쪽 자식 I), C의 오른쪽 자식 F(자식 J, K)로 이루어진다.
전위: A, B, D, G, H, E, I, C, F, J, K
중위: G, D, H, B, E, I, A, C, J, F, K
후위: G, H, D, I, E, B, J, K, F, C, A
E, H, E 조합: 전위의 다섯째는 E가 아니라 H이고, 중위의 다섯째도 H가 아니라 E이다.
G, E, H 조합: G는 전위 넷째, H는 후위 둘째이다.
H, B, I 조합: B는 중위 넷째, I는 후위 넷째이다.

행 우선 순서에서 arr[3][4][2]는 시작 주소로부터 78바이트 떨어져 있으므로 주소는 α + 78이다.
공식: 오프셋 = $(i \times 5 \times 4 + j \times 4 + k) \times 1$ (char는 1바이트)
대입: $3 \times 20 + 4 \times 4 + 2$
결과: $60 + 16 + 2 = 78$
α + 34: arr[1][3][2]의 위치이다.
α + 96: arr[4][4][0]의 위치이다.
α + 112: arr[5][3][0]의 위치이다.

중간 인덱스는 (left+right) / 2이고, 찾는 값이 크면 left = mid+1, 작으면 right = mid-1로 범위를 줄인다.
C에서 정수끼리의 /는 몫만 남기는 정수 나눗셈이다. 이미 비교한 mid는 다음 범위에서 제외해야 범위가 매번 줄어 반복이 끝난다.
(left+right) // 2, mid-1, mid+1: C에서 //는 주석 기호이고, 찾는 값이 클 때 left를 mid-1로 두면 탐색 방향이 반대가 된다.
right-(left-right) // 2, mid, left: 중간값 식이 틀렸고, left = mid로 두면 범위가 줄지 않아 무한 반복될 수 있다.
left+(right-left) / 2, right, mid: 중간값 식은 맞지만 left = right, right = mid로는 범위를 올바르게 좁히지 못한다.

최종 리스트를 출력하면 3 1 2 4 3이다.
func1은 맨 앞 삽입, func2는 맨 뒤 삽입, func3(pos)은 head에서 pos칸 이동한 노드를 반환한다.
func1(1) → 1
func2(2) → 1 2
func1(3) → 3 1 2
func2(4) → 3 1 2 4
func3(0)은 head 노드(데이터 3)이므로 func2(3) → 3 1 2 4 3
1 2 3 4: 원소가 4개뿐이어서 마지막 func2 호출로 추가된 노드가 빠졌다.
2 3 4 1: 원소가 4개뿐이고 삽입 순서와도 맞지 않는다.
3 3 1 2 4: 마지막 3을 맨 앞에 붙인 결과지만 func2는 맨 뒤에 붙인다.

원형 연결 리스트에서 값 4인 노드부터 7개 노드의 값을 더하면 14이다.
p[i]의 value는 i이고 p[4]의 next가 p[0]이라 원형으로 이어진다.
방문 값: 4, 0, 1, 2, 3, 4, 0
합: $4+0+1+2+3+4+0 = 14$

3행 1열이 1인 행렬은 1→2→3→1의 사이클을 포함하므로 위상 정렬이 불가능하다.
위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 행 i, 열 j의 1을 간선 i→j로 읽을 때 대각선 아래가 모두 0인 상삼각 행렬은 번호가 큰 정점에서 작은 정점으로 가는 간선이 없어 사이클이 생기지 않는다.
1→2→3→4의 한 줄 경로 행렬: 상삼각이므로 1, 2, 3, 4 순으로 정렬된다.
1과 2가 각각 3, 4로, 3이 4로 가는 행렬: 상삼각이므로 위상 정렬이 가능하다.
번호가 작은 정점에서 큰 정점으로 모든 간선이 있는 행렬: 상삼각이므로 위상 정렬이 가능하다.

찾는 키 3이 탐색 범위(인덱스 4~6)에 없으므로 보초 위치에서 멈추고 -1을 반환한다.
list[high+1] = list[7]에 key 3을 보초(sentinel)로 넣는다.
i=4부터: list[4]=5, list[5]=6, list[6]=7, list[7]=3 → i=7에서 멈춤
i == high+1이므로 -1 반환
0: 탐색은 인덱스 4부터 시작하므로 0이 반환될 수 없다.
3: 함수는 키 값이 아니라 찾은 인덱스를 반환한다.
4: 시작 인덱스 low이며 list[4]는 5라 키와 다르다.

후위식은 A B - C * D E + F / - 이고, 계산 중 일곱 번째로 push되는 값은 E이다.
피연산자는 push하고, 연산자는 두 값을 pop해 계산한 결과를 다시 push한다.
push 순서: A → B → A-B → C → (A-B)*C → D → E → D+E → F → (D+E)/F → 최종값
C: 네 번째로 push된다.
D: 여섯 번째로 push된다.
(D + E): 여덟 번째로 push된다.

배열은 최종적으로 0, 10, 6, 20, 12가 되어 합은 48이다.
초기화: 0, 1, 2, 3, 4
processArray (각 원소에 2i를 더함): 0, 3, 6, 9, 12
modifyArray (포인터 연산으로 array[1]=10, array[3]=20): 0, 10, 6, 20, 12
합: $0+10+6+20+12 = 48$
modifyArray가 processArray 뒤에 호출되므로 array[1]과 array[3]은 덮어쓴 값 10, 20이 최종값이다.

도달 가능한 모든 정점 쌍의 최단 경로 합은 57이다.
간선은 A→B 3, A→C 6, A→F 5, B→D 4, C→D 1, C→F 3, D→F 1, E→A 7, E→C 1이다. 출발 정점별로 최단 거리를 구해 더한다.
A에서: B 3, C 6, D 7(A→B→D 또는 A→C→D), F 5로 합 21이다.
B에서: D 4, F 5(B→D→F)로 합 9이다.
C에서: D 1, F 2(C→D→F가 직행 3보다 짧음)로 합 3이다.
D에서: F 1이고, F에서는 나가는 간선이 없어 0이다.
E에서: A 7, C 1, D 2(E→C→D), F 3(E→C→D→F), B 10(E→A→B)으로 합 23이다.
전체 합은 21+9+3+1+23=57이다.

리스트 순서는 C → A → D → B이므로 A를 지우면 C의 right_link는 1030, D의 left_link는 1020으로 바뀐다.
C(1020)의 left_link가 NULL이라 C가 첫 노드이고, 링크를 따라가면 C(1020) ↔ A(1000) ↔ D(1030) ↔ B(1010)이다.
A 삭제: A의 앞 노드 C가 A의 다음 노드 D(1030)를, D가 A의 앞 노드 C(1020)를 가리키게 한다.
B의 right_link를 1030, C의 left_link를 1020으로 바꾸는 것: B는 A와 이웃하지 않으며 C가 자기 자신을 가리키게 된다.
B의 right_link를 1030, D의 left_link를 1020으로 바꾸는 것: D 쪽은 맞지만 B는 마지막 노드라 right_link가 NULL로 유지된다.
C의 right_link를 1020, D의 left_link를 1030으로 바꾸는 것: 두 노드가 각각 자기 자신을 가리키게 된다.

차수 3인 B-트리(노드당 키 최대 2개)에 차례로 넣으면 7, 13, 17 삽입 때 분할이 일어나고 17에서는 루트까지 연쇄 분할되어 총 4회이다.
7 삽입: [1, 5, 7] 오버플로 → 5를 올려 분할 (1회)
13 삽입: [7, 11, 13] 오버플로 → 11을 올려 루트 [5, 11] (2회)
17 삽입: [13, 15, 17] 오버플로 → 15를 올려 루트 [5, 11, 15]가 다시 오버플로 (3회) → 11을 올려 새 루트 생성 (4회)
19 삽입: [17, 19]로 들어가 분할 없음
1회: 7 삽입 때의 첫 분할만 센 값이다.
2회: 13 삽입까지의 분할만 센 값이다.
3회: 17 삽입 때 루트로 번지는 연쇄 분할을 빠뜨린 값이다.

버킷 7과 8이 가득 찬 뒤 들어온 73과 85만 다른 버킷으로 밀려나므로 2개이다.
해시값(k mod 13): 21→8, 33→7, 8→8, 19→6, 76→11, 58→6, 27→1, 83→5, 30→4, 44→5, 7→7, 73→8, 2→2, 66→1, 85→7
슬롯이 2개이므로 한 버킷에 2개까지 저장된다.
73: 버킷 8(21, 8)이 가득 차 선형 조사로 버킷 9에 저장
85: 버킷 7(33, 7)과 버킷 8이 가득 차 버킷 9에 저장
나머지는 같은 해시값이 2개 이하라 원래 버킷에 저장된다.