[7급 서울시 자료구조론] 26년 1회차
7급 서울시 자료구조론 기출문제

26년 1회차

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

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

26년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
<보기> 수식을 전위 표기법(prefix notation)으로 변환한 후, 스택을 이용하여 계산하려고 한다. 계산 과정에서 스택에 다섯 번째로 삽입(push)하는 값은? (단, 전위표기법을 스택으로 계산할 때, 오른쪽에서 왼쪽으로 읽으며 진행한다.)
(A-B)*C+D/E
1A
2B
3D
4E
정답 및 해설

스택에 다섯 번째로 push되는 값은 B이다.

수식을 전위 표기로 바꾸면 + * - A B C / D E이다. 오른쪽부터 읽으며 피연산자는 push하고, 연산자를 만나면 두 값을 pop해 계산한 결과를 다시 push한다.

push 순서: E → D → (D/E) → C → B → A …

  • A: B 다음, 여섯 번째로 push된다.
  • D: 두 번째로 push된다.
  • E: 가장 먼저(첫 번째로) push된다.
문제 2
이중 연결 리스트(doubly linked list)의 특징에 대한 설명으로 가장 옳은 것은?
1각 노드가 이전 노드와 다음 노드의 정보를 가진다.
2노드들이 메모리의 연속된 공간에 저장된다.
3모든 노드는 하나의 링크만 가진다.
4인덱스를 이용하여 원하는 노드에 직접 접근할 수 있다.
정답 및 해설

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 링크를 가진다.

그래서 양방향 순회가 가능하지만, 노드는 메모리에 흩어져 있고 특정 노드에 가려면 링크를 따라가야 한다.

  • 연속된 메모리 공간에 저장되는 것은 배열(순차 리스트)의 특징이다.
  • 링크가 하나뿐인 것은 단순(단일) 연결 리스트이다.
  • 인덱스로 직접 접근하는 임의 접근은 배열의 특징이며, 연결 리스트는 순차적으로 따라가야 한다.
문제 3
<보기>는 피보나치 수열을 계산하는 C 프로그램이다. fib(5)을 호출했을 때, 함수 fib( )가 호출되는 총 횟수는? (단, 첫 호출도 1회로 계산한다.)
int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return (fib(n-1) + fib(n-2));
}
17
212
315
417
정답 및 해설

fib(5)를 호출하면 함수는 총 15회 호출된다.

호출 횟수를 T(n)T(n)이라 하면 T(n)=1+T(n−1)+T(n−2)T(n)=1+T(n-1)+T(n-2), T(0)=T(1)=1T(0)=T(1)=1이다.

T(2)=1+1+1=3T(2)=1+1+1=3
T(3)=1+3+1=5T(3)=1+3+1=5
T(4)=1+5+3=9T(4)=1+5+3=9
T(5)=1+9+5=15T(5)=1+9+5=15

  • 7회: 중복 호출을 대부분 빠뜨린 값이다.
  • 12회: 재귀 트리의 일부 호출을 누락한 값이다.
  • 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.
문제 4
탐색 알고리즘의 설명으로 가장 옳지 않은 것은?
1순차 탐색의 시간 복잡도는 O(n)O(n)이다.
2색인 순차 탐색에서 인덱스 테이블의 크기가 줄어들면, 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 탐색해야 하는 범위도 커진다.
3색인 순차 탐색의 시간 복잡도는 O(m+m/n)O(m+m/n)이다. (단, nn: 배열의 크기, mm: 인덱스 테이블의 크기)
41, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21과 같이 정렬되었을 때 이진 탐색으로 찾고자 하는 수가 17일 경우, 비교 횟수는 2번이다.
정답 및 해설

색인 순차 탐색의 시간 복잡도는 O(m+n/m)O(m+n/m)이므로, O(m+m/n)O(m+m/n)이라는 설명이 옳지 않다.

크기 mm인 인덱스 테이블을 먼저 탐색한 뒤, 찾은 구간(크기 약 n/mn/m)을 배열에서 순차 탐색하기 때문이다.

  • 순차 탐색은 원소를 처음부터 하나씩 비교하므로 O(n)O(n)이다.
  • 인덱스 테이블이 작아지면 인덱스 간격이 커져 배열에서 탐색할 구간이 넓어진다.
  • 11개 원소의 이진 탐색은 중간값 11과 비교한 뒤 오른쪽 구간의 중간값 17과 비교하므로 비교는 2회이다.
문제 5
<보기>의 C 프로그램 함수 func에 대해서 배열 arr[] = {1, 2, 3, 4, 5, 6}일 때, func(arr, 6, 2)를 실행한 후 배열 arr[]의 상태는?
void func(int arr[], int n, int k) {
int temp[100];
for (int i = 0; i < n; i++)
temp[i] = arr[(i + k) % n];
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
1[1, 2, 3, 4, 5, 6]
2[2, 3, 4, 5, 6, 1]
3[3, 4, 5, 6, 1, 2]
4[5, 6, 1, 2, 3, 4]
정답 및 해설

실행 후 배열은 [3, 4, 5, 6, 1, 2]가 된다.

temp[i]에 arr[(i+2)%6]을 담으므로 배열이 왼쪽으로 2칸 회전한다. temp[0]=arr[2]=3, temp[1]=arr[3]=4, …, temp[4]=arr[0]=1, temp[5]=arr[1]=2이다.

  • [1, 2, 3, 4, 5, 6]은 회전하지 않은 원래 상태이다.
  • [2, 3, 4, 5, 6, 1]은 왼쪽으로 1칸 회전한 결과이다.
  • [5, 6, 1, 2, 3, 4]는 오른쪽으로 2칸 회전한 결과이다.
문제 6
그래프에 대한 설명으로 가장 옳지 않은 것은?
1완전 그래프에서 정점이 nn개인 방향 그래프의 최대 간선 수는 n(n−1)n(n-1)개이다.
2방향 그래프의 인접 행렬에서 행 ii의 합은 정점 ii의 진출 차수이다.
3방향 그래프의 인접 리스트에서 각 정점의 헤드에 연결된 노드의 수는 정점의 진출 차수이다.
4ee개의 간선을 가진 무방향 그래프의 인접 리스트에 저장되는 연결 노드의 총 수는 ee개이다.
정답 및 해설

무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 2e2e개이다. 따라서 ee개라는 설명이 옳지 않다.

방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 ee개가 된다.

  • 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 n(n−1)n(n-1)개이다.
  • 인접 행렬의 행 ii는 정점 ii에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
  • 인접 리스트에서 헤드 ii에 연결된 노드는 ii에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.
문제 7
<보기>에서 이진 트리(binary tree)의 성질에 대한 설명으로 옳은 것을 모두 고른 것은? (단, 트리의 높이는 루트 노드의 레벨을 1로 하여 계산한다.)
ㄱ. 총 nn개의 노드를 가진 이진 트리의 높이(hh)는 적어도 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil 이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. nn개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 Θ(n)\Theta(n)이다.
1ㄱ
2ㄱ, ㄷ
3ㄴ, ㄹ
4ㄱ, ㄷ, ㄹ
정답 및 해설

옳은 것은 ㄱ, ㄷ이다.

높이 hh인 이진 트리의 최대 노드 수는 2h−12^h-1이므로 n≤2h−1n \le 2^h-1, 즉 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.

  • ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
  • ㄹ: 이진 탐색 트리의 평균 검색 시간은 Θ(log⁡n)\Theta(\log n)이며, Θ(n)\Theta(n)은 한쪽으로 치우친 최악의 경우이다.
문제 8
<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?
Algorithm(int n) {
int i, j, k, l;
int sum = 0;
for (i = 0; i < 500; i++)
for (j = 0; j < 100; j++)
for (k = 1; k < n; k = k * 2)
for (l = 0; l < 10; l++)
sum = sum + i + j + k + l;
}
1O(1)O(1)
2O(n)O(n)
3O(n2)O(n^2)
4O(log⁡n)O(\log n)
정답 및 해설

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

i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 log⁡2n\log_2 n회 반복한다.

총 실행 횟수는 500×100×10×log⁡2n500 \times 100 \times 10 \times \log_2 n이고, 상수를 제거하면 O(log⁡n)O(\log n)이다.

  • O(1)O(1): k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • O(n)O(n): k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
  • O(n2)O(n^2): n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.
문제 9
크기가 6인 원형 큐(circular queue)가 있다. <보기 1>의 설명을 참고하여 <보기 2>의 연산을 모두 수행한 후, rear가 가리키는 배열의 인덱스는?
• 배열의 인덱스는 0부터 5까지 사용한다.
• 초기 상태에서 front와 rear은 모두 0을 가리키며, 큐는 공백 상태이다.
• 공백 상태와 포화 상태를 구분하기 위해 항상 한 칸을 비워 두는 방식으로 구현한다.
• enqueue는 데이터를 삽입하는 연산이며, rear을 먼저 한 칸 이동시킨 후 해당 위치에 저장한다.
• dequeue는 데이터를 삭제하는 연산이며, front를 먼저 한 칸 이동시킨 후 해당 데이터를 삭제한다.
enqueue(A) ⇒ enqueue(B) ⇒ enqueue(C) ⇒
dequeue() ⇒ enqueue(D) ⇒ enqueue(E) ⇒ enqueue(F)
10
23
34
45
정답 및 해설

모든 연산을 마친 뒤 rear는 인덱스 0을 가리킨다.

enqueue는 rear=(rear+1) mod 6rear=(rear+1) \bmod 6, dequeue는 front=(front+1) mod 6front=(front+1) \bmod 6로 이동한다.

A는 1, B는 2, C는 3에 저장되고 dequeue로 front가 1이 된다. D는 4, E는 5, F는 (5+1) mod 6=0(5+1) \bmod 6=0에 저장되며, 이때 다음 칸이 front가 되어 포화 상태가 된다.

  • 3: C까지 삽입한 시점의 rear이다.
  • 4: D까지 삽입한 시점의 rear이다.
  • 5: E까지 삽입한 시점의 rear로, F 삽입 시 원형으로 되돌아가는 것을 반영하지 않은 값이다.
문제 10
[91, 42, 17, 12, 80, 95, 3, 27] 배열을 셸(shell) 정렬로 오름차순 정렬할 때, 간격을 hh에 저장하는데, h=2h=2인 단계가 완료된 직후의 배열 상태는? (단, 최초 간격 hh는 배열 원소 개수 nn에 대하여 h=n2h=\frac{n}{2}이고 이후 각 단계에서 절반으로 감소한다.)
1[3, 12, 17, 27, 80, 42, 91, 95]
2[3, 12, 27, 17, 80, 42, 91, 95]
3[80, 42, 3, 12, 91, 95, 17, 27]
4[80, 42, 3, 12, 95, 91, 17, 27]
정답 및 해설

h=2h=2 단계 직후 배열은 [3, 12, 17, 27, 80, 42, 91, 95]이다.

h=4h=4 단계: (91, 80), (42, 95), (17, 3), (12, 27) 부분 리스트를 각각 정렬하면 [80, 42, 3, 12, 91, 95, 17, 27]이다.

h=2h=2 단계: 짝수 위치 (80, 3, 91, 17)은 (3, 17, 80, 91)로, 홀수 위치 (42, 12, 95, 27)은 (12, 27, 42, 95)로 정렬해 합친다.

  • [3, 12, 27, 17, 80, 42, 91, 95]: 17과 27의 자리가 바뀌어 부분 리스트가 정렬되지 않았다.
  • [80, 42, 3, 12, 91, 95, 17, 27]: h=4h=4 단계까지만 수행한 상태이다.
  • [80, 42, 3, 12, 95, 91, 17, 27]: h=4h=4 단계 결과와도 91, 95의 순서가 다르다.
문제 11
힙(heap)에 대한 설명으로 가장 옳지 않은 것은?
1최대 힙은 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같고, 최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작다.
2삽입 연산 시 노드가 nn개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1n+1번의 노드이며 그 자리에 삽입할 원소를 임시 저장한다.
3일반적인 힙의 삭제 연산 시 루트 노드에 있는 원소를 삭제한다.
4힙을 구현할 때 1차원 배열의 순차 자료구조를 이용하면 인덱스 관계를 이용하여 부모 노드를 찾기가 쉽다.
정답 및 해설

최소 힙은 부모 키값이 자식 키값보다 작거나 같으면 되므로, "항상 작다"고 한 설명이 옳지 않다.

힙은 같은 키값을 허용하므로 최대 힙(부모 ≥ 자식)과 마찬가지로 최소 힙도 등호를 포함한 부모 ≤ 자식 관계를 만족한다.

  • 삽입 시 완전 이진 트리를 유지하려면 마지막 노드 다음 자리(n+1n+1 위치)에 원소를 임시로 두고 부모와 비교하며 올라간다.
  • 힙의 삭제는 루트 원소를 꺼낸 뒤 마지막 노드를 루트로 옮겨 재정렬한다.
  • 배열로 구현하면 노드 ii의 부모는 ⌊i/2⌋\lfloor i/2 \rfloor처럼 인덱스 계산으로 바로 찾는다.
문제 12
가중치 무방향 그래프에서 크루스칼(Kruskal) 알고리즘을 이용해 최소 비용 신장 트리를 구성하려고 한다. 간선의 가중치는 <보기>와 같다. 크루스칼 알고리즘으로 간선을 선택하는 과정에서, 세 번째로 신장 트리에 포함되는 간선은?
(A, B): 2, (A, C): 3, (B, C): 1, (B, D): 5, (C, D): 4
1(A, B)
2(A, C)
3(B, D)
4(C, D)
정답 및 해설

세 번째로 신장 트리에 포함되는 간선은 (C, D)이다.

크루스칼 알고리즘은 가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 제외한다.

(B, C) 1 선택 → (A, B) 2 선택 → (A, C) 3은 A-B-C 사이클을 만들어 제외 → (C, D) 4 선택.

  • (A, B): 두 번째로 포함되는 간선이다.
  • (A, C): 사이클을 만들어 제외된다.
  • (B, D): 정점 4개의 신장 트리는 간선 3개로 이미 완성되어 선택되지 않는다.
문제 13
<보기>와 같은 순회 결과들을 모두 만족하는 7개의 노드로 이루어진 이진 트리의 구조로 옳은 것은?
전위 순회: A − B − D − E − F − C − G
중위 순회: D − B − F − E − A − C − G
후위 순회: D − F − E − B − G − C − A
1
2
3
4
정답 및 해설

세 순회를 모두 만족하는 트리는 E의 왼쪽 자식이 F, C의 오른쪽 자식이 G인 구조이다.

전위 순회의 첫 노드 A가 루트이고, 중위 순회에서 A의 왼쪽(D B F E)이 왼쪽 서브트리, 오른쪽(C G)이 오른쪽 서브트리가 된다. 왼쪽 서브트리는 전위상 B가 루트로 D가 왼쪽, F·E가 오른쪽에 오며, 전위 E−F·중위 F−E이므로 F는 E의 왼쪽 자식이다.

오른쪽 서브트리는 전위 C−G, 중위 C−G이므로 G는 C의 오른쪽 자식이고, 후위 순회 D−F−E−B−G−C−A로도 확인된다.

  • G가 C의 왼쪽 자식인 구조는 중위 순회가 G−C 순서가 되어 맞지 않는다.
  • F가 E의 오른쪽 자식인 구조는 중위 순회가 E−F 순서가 되어 맞지 않는다.
  • E가 B의 왼쪽, D가 B의 오른쪽에 있는 구조는 전위 순회가 A−B−E−F−D… 가 되어 맞지 않는다.
문제 14
<보기>의 코드는 원형 연결 리스트(circular linked list)에서 특정 노드 old를 삭제하는 C언어 함수이다. 빈칸 (가), (나)에 들어갈 내용으로 가장 옳은 것은? (단, head는 첫 번째 노드를 가리키며, 삭제 후에도 기존 노드들의 순서는 유지된다.)
void deleteNode(linkedList_h* CL, listNode* old) {
listNode* pre;
if (CL->head == NULL) return;
if (CL->head->link == CL->head) {
free(CL->head);
CL->head = NULL;
return;
}
else if (old == NULL) return;
else {
pre = CL->head;
while (pre->link != old) {
pre = pre->link;
}
( (가) )
if (old == CL->head) {
( (나) )
}
free(old);
}
}
1(가) old->link = pre->link; (나) CL->head = old->link;
2(가) pre->link = old->link; (나) CL->head = old->link;
3(가) pre->link = old->link; (나) CL->head = pre;
4(가) pre = old->link; (나) CL->head = old->link;
정답 및 해설

(가)는 pre->link = old->link;, (나)는 CL->head = old->link;이다.

pre는 old의 바로 앞 노드이므로 pre의 링크를 old의 다음 노드로 바꿔 old를 리스트에서 떼어낸다. old가 head였다면 순서를 유지하도록 old의 다음 노드를 새 head로 지정한다.

  • old->link = pre->link: 삭제할 노드의 링크만 바뀌고 pre는 여전히 old를 가리켜 연결이 끊기지 않는다.
  • (나)에서 head를 pre로 바꾸는 경우: 마지막 노드가 첫 노드가 되어 기존 순서가 바뀐다.
  • pre = old->link: 지역 변수만 바뀔 뿐 리스트의 링크는 그대로이다.
문제 15
<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. 이때 실제 자식 노드를 가리키는 링크 수를 aa, 중위 선행자 또는 중위 후속자를 가리키는 스레드 수를 bb, 스레드 구성 후에도 NULL로 남는 포인터 수를 cc라고 할 때, aa, bb, cc의 값으로 가장 옳은 것은? (단, 중위 선행자나 중위 후속자가 없는 경우 해당 스레드 포인터에는 NULL을 저장한다.)
1a=7b=6c=1a=7 \quad b=6 \quad c=1
2a=7b=7c=2a=7 \quad b=7 \quad c=2
3a=7b=8c=1a=7 \quad b=8 \quad c=1
4a=9b=7c=2a=9 \quad b=7 \quad c=2
정답 및 해설

중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.

그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 n−1=7n-1=7개이고, 전체 포인터 2n=162n=16개 중 빈 포인터는 16−7=916-7=9개이다.

중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 9−2=79-2=7개이다.

  • 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
  • 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
  • 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.
문제 16
<보기>의 AVL 트리에 5를 삽입한 후, AVL 트리의 균형을 유지하기 위해 수행해야 하는 회전으로 가장 옳은 것은?
1LL 회전
2RR 회전
3LR 회전
4RL 회전
정답 및 해설

5를 삽입하면 루트 30에서 왼쪽-왼쪽 방향으로 불균형이 생기므로 LL 회전을 수행한다.

그림의 트리는 루트 30의 왼쪽에 20(자식 10, 25), 오른쪽에 40이 있다. 5는 30→20→10을 거쳐 10의 왼쪽 자식으로 삽입된다.

삽입 후 30의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 균형 인수가 +2이고, 불균형 노드 30에서 삽입 위치까지 왼쪽→왼쪽으로 내려가므로 20을 축으로 오른쪽 회전하는 LL 유형이다. 회전 후 20이 루트가 되고 왼쪽에 10(자식 5), 오른쪽에 30(자식 25, 40)이 온다.

  • RR 회전은 불균형 노드의 오른쪽-오른쪽에 삽입된 경우에 쓴다.
  • LR 회전은 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우에 쓴다.
  • RL 회전은 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우에 쓴다.
문제 17
<보기>의 방향 그래프에 대해 위상 정렬(topological sort)을 수행할 때, 가능한 서로 다른 위상 순서의 총 개수는?
13
24
35
46
정답 및 해설

가능한 위상 순서는 모두 5가지이다.

그래프의 간선은 A→B, A→C, B→D, C→D, C→E, D→F, E→F이다. 진입 차수가 0인 정점은 A뿐이므로 A가 맨 앞, 모든 경로가 끝나는 F가 맨 뒤에 고정된다.

가운데 B, C, D, E는 D가 B·C 뒤에, E가 C 뒤에 와야 한다. B로 시작하면 B−C−D−E, B−C−E−D의 2가지, C로 시작하면 C−B−D−E, C−B−E−D, C−E−B−D의 3가지가 있어 합은 5가지이다.

  • 3가지는 C로 시작하는 경우만 센 값이다.
  • 4가지는 C−E−B−D처럼 E가 B보다 먼저 오는 순서를 빠뜨린 값이다.
  • 6가지는 가능한 5가지보다 많아, 간선 제약을 어기는 순서를 포함해야만 나오는 값이다.
문제 18
[691, 423, 17, 124, 80, 95, 3, 227] 배열을 LSD(least significant digit) 기수 정렬로 오름차순 정렬할 때, 2단계가 완료된 직후 배열 상태로 가장 옳은 것은?
1[3, 17, 124, 227, 423, 80, 691, 95]
2[3, 17, 423, 124, 227, 80, 691, 95]
3[17, 3, 227, 423, 124, 80, 95, 691]
4[17, 3, 423, 227, 124, 80, 95, 691]
정답 및 해설

2단계 직후 배열은 [3, 17, 423, 124, 227, 80, 691, 95]이다.

1단계(일의 자리): 0→80, 1→691, 3→423·3, 4→124, 5→95, 7→17·227 순으로 모아 [80, 691, 423, 3, 124, 95, 17, 227]이 된다.

2단계(십의 자리, 같은 자릿값은 앞 단계 순서 유지): 0→3, 1→17, 2→423·124·227, 8→80, 9→691·95 순으로 모은다.

  • [3, 17, 124, 227, 423, 80, 691, 95]: 십의 자리가 2인 원소를 백의 자리 기준으로 미리 정렬해 앞 단계 순서를 지키지 않았다.
  • [17, 3, 227, 423, 124, 80, 95, 691]: 십의 자리가 0인 3보다 1인 17을 앞에 두어 십의 자리 기준 정렬이 아니다.
  • [17, 3, 423, 227, 124, 80, 95, 691]: 역시 17이 3보다 앞서 있어 2단계 결과가 될 수 없다.
문제 19
<보기>는 무방향 그래프에서 깊이 우선 탐색(DFS, depth first search)을 수행하는 C 프로그램이다. dfs(0)을 호출했을 때, order[2]와 order[3]의 값으로 가장 옳은 것은?
int adj[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
int visited[5] = { 0, };
int order[5];
int cnt = 0;

void dfs(int v) {
visited[v] = 1;
order[v] = ++cnt;
for (int i = 0; i < 5; i++) {
if (adj[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
1order[2]: 2, order[3]: 4
2order[2]: 3, order[3]: 4
3order[2]: 5, order[3]: 3
4order[2]: 5, order[3]: 4
정답 및 해설

order[2]는 5, order[3]은 3이다.

인접 행렬을 인덱스 순서로 검사하며 방문하지 않은 정점이 있으면 즉시 재귀한다.

dfs(0): order[0]=1 → dfs(1): order[1]=2 → dfs(3): order[3]=3, 더 갈 곳이 없어 복귀 → dfs(4): order[4]=4 → dfs(2): order[2]=5.

  • order[2]: 2, order[3]: 4 — 정점 2는 1→4를 거친 뒤 마지막에 방문되므로 두 번째가 될 수 없다.
  • order[2]: 3, order[3]: 4 — 0과 가까운 정점부터 차례로 방문하는 너비 우선 탐색의 순서이다.
  • order[2]: 5, order[3]: 4 — 정점 1에서 인덱스가 작은 3을 4보다 먼저 방문하므로 order[3]은 3이다.
문제 20
크기가 8인 해시 테이블에서 해시 함수 h(k)=k mod 8h(k)=k \bmod 8을 사용하고, 충돌은 체이닝(chaining)으로 처리한다. <보기>의 키를 순서대로 삽입할 때, 가장 긴 체인이 형성된 버킷의 인덱스와 해당 체인의 길이를 옳게 짝지은 것은? (단, 버킷의 인덱스는 0부터 시작한다.)
13, 25, 6, 21, 14, 29, 8
1인덱스 0, 길이 2
2인덱스 5, 길이 3
3인덱스 5, 길이 4
4인덱스 6, 길이 2
정답 및 해설

가장 긴 체인은 인덱스 5, 길이 3이다.

13→5, 25→1, 6→6, 21→5, 14→6, 29→5, 8→0이므로 버킷 5에 13·21·29의 3개가 연결된다.

  • 인덱스 0, 길이 2: 버킷 0에는 8 하나만 저장된다.
  • 인덱스 5, 길이 4: 버킷 5의 키는 3개뿐이다.
  • 인덱스 6, 길이 2: 6·14의 2개로 가장 긴 체인이 아니다.
7급 서울시 자료구조론 기출문제모두CBT · moducbt.com
26년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
<보기> 수식을 전위 표기법(prefix notation)으로 변환한 후, 스택을 이용하여 계산하려고 한다. 계산 과정에서 스택에 다섯 번째로 삽입(push)하는 값은? (단, 전위표기법을 스택으로 계산할 때, 오른쪽에서 왼쪽으로 읽으며 진행한다.)
(A-B)*C+D/E
1A
2B
3D
4E
정답 및 해설

스택에 다섯 번째로 push되는 값은 B이다.

수식을 전위 표기로 바꾸면 + * - A B C / D E이다. 오른쪽부터 읽으며 피연산자는 push하고, 연산자를 만나면 두 값을 pop해 계산한 결과를 다시 push한다.

push 순서: E → D → (D/E) → C → B → A …

  • A: B 다음, 여섯 번째로 push된다.
  • D: 두 번째로 push된다.
  • E: 가장 먼저(첫 번째로) push된다.
문제 2
이중 연결 리스트(doubly linked list)의 특징에 대한 설명으로 가장 옳은 것은?
1각 노드가 이전 노드와 다음 노드의 정보를 가진다.
2노드들이 메모리의 연속된 공간에 저장된다.
3모든 노드는 하나의 링크만 가진다.
4인덱스를 이용하여 원하는 노드에 직접 접근할 수 있다.
정답 및 해설

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 링크를 가진다.

그래서 양방향 순회가 가능하지만, 노드는 메모리에 흩어져 있고 특정 노드에 가려면 링크를 따라가야 한다.

  • 연속된 메모리 공간에 저장되는 것은 배열(순차 리스트)의 특징이다.
  • 링크가 하나뿐인 것은 단순(단일) 연결 리스트이다.
  • 인덱스로 직접 접근하는 임의 접근은 배열의 특징이며, 연결 리스트는 순차적으로 따라가야 한다.
문제 3
<보기>는 피보나치 수열을 계산하는 C 프로그램이다. fib(5)을 호출했을 때, 함수 fib( )가 호출되는 총 횟수는? (단, 첫 호출도 1회로 계산한다.)
int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return (fib(n-1) + fib(n-2));
}
17
212
315
417
정답 및 해설

fib(5)를 호출하면 함수는 총 15회 호출된다.

호출 횟수를 T(n)T(n)이라 하면 T(n)=1+T(n−1)+T(n−2)T(n)=1+T(n-1)+T(n-2), T(0)=T(1)=1T(0)=T(1)=1이다.

T(2)=1+1+1=3T(2)=1+1+1=3
T(3)=1+3+1=5T(3)=1+3+1=5
T(4)=1+5+3=9T(4)=1+5+3=9
T(5)=1+9+5=15T(5)=1+9+5=15

  • 7회: 중복 호출을 대부분 빠뜨린 값이다.
  • 12회: 재귀 트리의 일부 호출을 누락한 값이다.
  • 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.
문제 4
탐색 알고리즘의 설명으로 가장 옳지 않은 것은?
1순차 탐색의 시간 복잡도는 O(n)O(n)이다.
2색인 순차 탐색에서 인덱스 테이블의 크기가 줄어들면, 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 탐색해야 하는 범위도 커진다.
3색인 순차 탐색의 시간 복잡도는 O(m+m/n)O(m+m/n)이다. (단, nn: 배열의 크기, mm: 인덱스 테이블의 크기)
41, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21과 같이 정렬되었을 때 이진 탐색으로 찾고자 하는 수가 17일 경우, 비교 횟수는 2번이다.
정답 및 해설

색인 순차 탐색의 시간 복잡도는 O(m+n/m)O(m+n/m)이므로, O(m+m/n)O(m+m/n)이라는 설명이 옳지 않다.

크기 mm인 인덱스 테이블을 먼저 탐색한 뒤, 찾은 구간(크기 약 n/mn/m)을 배열에서 순차 탐색하기 때문이다.

  • 순차 탐색은 원소를 처음부터 하나씩 비교하므로 O(n)O(n)이다.
  • 인덱스 테이블이 작아지면 인덱스 간격이 커져 배열에서 탐색할 구간이 넓어진다.
  • 11개 원소의 이진 탐색은 중간값 11과 비교한 뒤 오른쪽 구간의 중간값 17과 비교하므로 비교는 2회이다.
문제 5
<보기>의 C 프로그램 함수 func에 대해서 배열 arr[] = {1, 2, 3, 4, 5, 6}일 때, func(arr, 6, 2)를 실행한 후 배열 arr[]의 상태는?
void func(int arr[], int n, int k) {
int temp[100];
for (int i = 0; i < n; i++)
temp[i] = arr[(i + k) % n];
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
1[1, 2, 3, 4, 5, 6]
2[2, 3, 4, 5, 6, 1]
3[3, 4, 5, 6, 1, 2]
4[5, 6, 1, 2, 3, 4]
정답 및 해설

실행 후 배열은 [3, 4, 5, 6, 1, 2]가 된다.

temp[i]에 arr[(i+2)%6]을 담으므로 배열이 왼쪽으로 2칸 회전한다. temp[0]=arr[2]=3, temp[1]=arr[3]=4, …, temp[4]=arr[0]=1, temp[5]=arr[1]=2이다.

  • [1, 2, 3, 4, 5, 6]은 회전하지 않은 원래 상태이다.
  • [2, 3, 4, 5, 6, 1]은 왼쪽으로 1칸 회전한 결과이다.
  • [5, 6, 1, 2, 3, 4]는 오른쪽으로 2칸 회전한 결과이다.
문제 6
그래프에 대한 설명으로 가장 옳지 않은 것은?
1완전 그래프에서 정점이 nn개인 방향 그래프의 최대 간선 수는 n(n−1)n(n-1)개이다.
2방향 그래프의 인접 행렬에서 행 ii의 합은 정점 ii의 진출 차수이다.
3방향 그래프의 인접 리스트에서 각 정점의 헤드에 연결된 노드의 수는 정점의 진출 차수이다.
4ee개의 간선을 가진 무방향 그래프의 인접 리스트에 저장되는 연결 노드의 총 수는 ee개이다.
정답 및 해설

무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 2e2e개이다. 따라서 ee개라는 설명이 옳지 않다.

방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 ee개가 된다.

  • 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 n(n−1)n(n-1)개이다.
  • 인접 행렬의 행 ii는 정점 ii에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
  • 인접 리스트에서 헤드 ii에 연결된 노드는 ii에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.
문제 7
<보기>에서 이진 트리(binary tree)의 성질에 대한 설명으로 옳은 것을 모두 고른 것은? (단, 트리의 높이는 루트 노드의 레벨을 1로 하여 계산한다.)
ㄱ. 총 nn개의 노드를 가진 이진 트리의 높이(hh)는 적어도 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil 이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. nn개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 Θ(n)\Theta(n)이다.
1ㄱ
2ㄱ, ㄷ
3ㄴ, ㄹ
4ㄱ, ㄷ, ㄹ
정답 및 해설

옳은 것은 ㄱ, ㄷ이다.

높이 hh인 이진 트리의 최대 노드 수는 2h−12^h-1이므로 n≤2h−1n \le 2^h-1, 즉 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.

  • ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
  • ㄹ: 이진 탐색 트리의 평균 검색 시간은 Θ(log⁡n)\Theta(\log n)이며, Θ(n)\Theta(n)은 한쪽으로 치우친 최악의 경우이다.
문제 8
<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?
Algorithm(int n) {
int i, j, k, l;
int sum = 0;
for (i = 0; i < 500; i++)
for (j = 0; j < 100; j++)
for (k = 1; k < n; k = k * 2)
for (l = 0; l < 10; l++)
sum = sum + i + j + k + l;
}
1O(1)O(1)
2O(n)O(n)
3O(n2)O(n^2)
4O(log⁡n)O(\log n)
정답 및 해설

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

i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 log⁡2n\log_2 n회 반복한다.

총 실행 횟수는 500×100×10×log⁡2n500 \times 100 \times 10 \times \log_2 n이고, 상수를 제거하면 O(log⁡n)O(\log n)이다.

  • O(1)O(1): k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • O(n)O(n): k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
  • O(n2)O(n^2): n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.
문제 9
크기가 6인 원형 큐(circular queue)가 있다. <보기 1>의 설명을 참고하여 <보기 2>의 연산을 모두 수행한 후, rear가 가리키는 배열의 인덱스는?
• 배열의 인덱스는 0부터 5까지 사용한다.
• 초기 상태에서 front와 rear은 모두 0을 가리키며, 큐는 공백 상태이다.
• 공백 상태와 포화 상태를 구분하기 위해 항상 한 칸을 비워 두는 방식으로 구현한다.
• enqueue는 데이터를 삽입하는 연산이며, rear을 먼저 한 칸 이동시킨 후 해당 위치에 저장한다.
• dequeue는 데이터를 삭제하는 연산이며, front를 먼저 한 칸 이동시킨 후 해당 데이터를 삭제한다.
enqueue(A) ⇒ enqueue(B) ⇒ enqueue(C) ⇒
dequeue() ⇒ enqueue(D) ⇒ enqueue(E) ⇒ enqueue(F)
10
23
34
45
정답 및 해설

모든 연산을 마친 뒤 rear는 인덱스 0을 가리킨다.

enqueue는 rear=(rear+1) mod 6rear=(rear+1) \bmod 6, dequeue는 front=(front+1) mod 6front=(front+1) \bmod 6로 이동한다.

A는 1, B는 2, C는 3에 저장되고 dequeue로 front가 1이 된다. D는 4, E는 5, F는 (5+1) mod 6=0(5+1) \bmod 6=0에 저장되며, 이때 다음 칸이 front가 되어 포화 상태가 된다.

  • 3: C까지 삽입한 시점의 rear이다.
  • 4: D까지 삽입한 시점의 rear이다.
  • 5: E까지 삽입한 시점의 rear로, F 삽입 시 원형으로 되돌아가는 것을 반영하지 않은 값이다.
문제 10
[91, 42, 17, 12, 80, 95, 3, 27] 배열을 셸(shell) 정렬로 오름차순 정렬할 때, 간격을 hh에 저장하는데, h=2h=2인 단계가 완료된 직후의 배열 상태는? (단, 최초 간격 hh는 배열 원소 개수 nn에 대하여 h=n2h=\frac{n}{2}이고 이후 각 단계에서 절반으로 감소한다.)
1[3, 12, 17, 27, 80, 42, 91, 95]
2[3, 12, 27, 17, 80, 42, 91, 95]
3[80, 42, 3, 12, 91, 95, 17, 27]
4[80, 42, 3, 12, 95, 91, 17, 27]
정답 및 해설

h=2h=2 단계 직후 배열은 [3, 12, 17, 27, 80, 42, 91, 95]이다.

h=4h=4 단계: (91, 80), (42, 95), (17, 3), (12, 27) 부분 리스트를 각각 정렬하면 [80, 42, 3, 12, 91, 95, 17, 27]이다.

h=2h=2 단계: 짝수 위치 (80, 3, 91, 17)은 (3, 17, 80, 91)로, 홀수 위치 (42, 12, 95, 27)은 (12, 27, 42, 95)로 정렬해 합친다.

  • [3, 12, 27, 17, 80, 42, 91, 95]: 17과 27의 자리가 바뀌어 부분 리스트가 정렬되지 않았다.
  • [80, 42, 3, 12, 91, 95, 17, 27]: h=4h=4 단계까지만 수행한 상태이다.
  • [80, 42, 3, 12, 95, 91, 17, 27]: h=4h=4 단계 결과와도 91, 95의 순서가 다르다.
문제 11
힙(heap)에 대한 설명으로 가장 옳지 않은 것은?
1최대 힙은 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같고, 최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작다.
2삽입 연산 시 노드가 nn개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1n+1번의 노드이며 그 자리에 삽입할 원소를 임시 저장한다.
3일반적인 힙의 삭제 연산 시 루트 노드에 있는 원소를 삭제한다.
4힙을 구현할 때 1차원 배열의 순차 자료구조를 이용하면 인덱스 관계를 이용하여 부모 노드를 찾기가 쉽다.
정답 및 해설

최소 힙은 부모 키값이 자식 키값보다 작거나 같으면 되므로, "항상 작다"고 한 설명이 옳지 않다.

힙은 같은 키값을 허용하므로 최대 힙(부모 ≥ 자식)과 마찬가지로 최소 힙도 등호를 포함한 부모 ≤ 자식 관계를 만족한다.

  • 삽입 시 완전 이진 트리를 유지하려면 마지막 노드 다음 자리(n+1n+1 위치)에 원소를 임시로 두고 부모와 비교하며 올라간다.
  • 힙의 삭제는 루트 원소를 꺼낸 뒤 마지막 노드를 루트로 옮겨 재정렬한다.
  • 배열로 구현하면 노드 ii의 부모는 ⌊i/2⌋\lfloor i/2 \rfloor처럼 인덱스 계산으로 바로 찾는다.
문제 12
가중치 무방향 그래프에서 크루스칼(Kruskal) 알고리즘을 이용해 최소 비용 신장 트리를 구성하려고 한다. 간선의 가중치는 <보기>와 같다. 크루스칼 알고리즘으로 간선을 선택하는 과정에서, 세 번째로 신장 트리에 포함되는 간선은?
(A, B): 2, (A, C): 3, (B, C): 1, (B, D): 5, (C, D): 4
1(A, B)
2(A, C)
3(B, D)
4(C, D)
정답 및 해설

세 번째로 신장 트리에 포함되는 간선은 (C, D)이다.

크루스칼 알고리즘은 가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 제외한다.

(B, C) 1 선택 → (A, B) 2 선택 → (A, C) 3은 A-B-C 사이클을 만들어 제외 → (C, D) 4 선택.

  • (A, B): 두 번째로 포함되는 간선이다.
  • (A, C): 사이클을 만들어 제외된다.
  • (B, D): 정점 4개의 신장 트리는 간선 3개로 이미 완성되어 선택되지 않는다.
문제 13
<보기>와 같은 순회 결과들을 모두 만족하는 7개의 노드로 이루어진 이진 트리의 구조로 옳은 것은?
전위 순회: A − B − D − E − F − C − G
중위 순회: D − B − F − E − A − C − G
후위 순회: D − F − E − B − G − C − A
1
2
3
4
정답 및 해설

세 순회를 모두 만족하는 트리는 E의 왼쪽 자식이 F, C의 오른쪽 자식이 G인 구조이다.

전위 순회의 첫 노드 A가 루트이고, 중위 순회에서 A의 왼쪽(D B F E)이 왼쪽 서브트리, 오른쪽(C G)이 오른쪽 서브트리가 된다. 왼쪽 서브트리는 전위상 B가 루트로 D가 왼쪽, F·E가 오른쪽에 오며, 전위 E−F·중위 F−E이므로 F는 E의 왼쪽 자식이다.

오른쪽 서브트리는 전위 C−G, 중위 C−G이므로 G는 C의 오른쪽 자식이고, 후위 순회 D−F−E−B−G−C−A로도 확인된다.

  • G가 C의 왼쪽 자식인 구조는 중위 순회가 G−C 순서가 되어 맞지 않는다.
  • F가 E의 오른쪽 자식인 구조는 중위 순회가 E−F 순서가 되어 맞지 않는다.
  • E가 B의 왼쪽, D가 B의 오른쪽에 있는 구조는 전위 순회가 A−B−E−F−D… 가 되어 맞지 않는다.
문제 14
<보기>의 코드는 원형 연결 리스트(circular linked list)에서 특정 노드 old를 삭제하는 C언어 함수이다. 빈칸 (가), (나)에 들어갈 내용으로 가장 옳은 것은? (단, head는 첫 번째 노드를 가리키며, 삭제 후에도 기존 노드들의 순서는 유지된다.)
void deleteNode(linkedList_h* CL, listNode* old) {
listNode* pre;
if (CL->head == NULL) return;
if (CL->head->link == CL->head) {
free(CL->head);
CL->head = NULL;
return;
}
else if (old == NULL) return;
else {
pre = CL->head;
while (pre->link != old) {
pre = pre->link;
}
( (가) )
if (old == CL->head) {
( (나) )
}
free(old);
}
}
1(가) old->link = pre->link; (나) CL->head = old->link;
2(가) pre->link = old->link; (나) CL->head = old->link;
3(가) pre->link = old->link; (나) CL->head = pre;
4(가) pre = old->link; (나) CL->head = old->link;
정답 및 해설

(가)는 pre->link = old->link;, (나)는 CL->head = old->link;이다.

pre는 old의 바로 앞 노드이므로 pre의 링크를 old의 다음 노드로 바꿔 old를 리스트에서 떼어낸다. old가 head였다면 순서를 유지하도록 old의 다음 노드를 새 head로 지정한다.

  • old->link = pre->link: 삭제할 노드의 링크만 바뀌고 pre는 여전히 old를 가리켜 연결이 끊기지 않는다.
  • (나)에서 head를 pre로 바꾸는 경우: 마지막 노드가 첫 노드가 되어 기존 순서가 바뀐다.
  • pre = old->link: 지역 변수만 바뀔 뿐 리스트의 링크는 그대로이다.
문제 15
<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. 이때 실제 자식 노드를 가리키는 링크 수를 aa, 중위 선행자 또는 중위 후속자를 가리키는 스레드 수를 bb, 스레드 구성 후에도 NULL로 남는 포인터 수를 cc라고 할 때, aa, bb, cc의 값으로 가장 옳은 것은? (단, 중위 선행자나 중위 후속자가 없는 경우 해당 스레드 포인터에는 NULL을 저장한다.)
1a=7b=6c=1a=7 \quad b=6 \quad c=1
2a=7b=7c=2a=7 \quad b=7 \quad c=2
3a=7b=8c=1a=7 \quad b=8 \quad c=1
4a=9b=7c=2a=9 \quad b=7 \quad c=2
정답 및 해설

중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.

그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 n−1=7n-1=7개이고, 전체 포인터 2n=162n=16개 중 빈 포인터는 16−7=916-7=9개이다.

중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 9−2=79-2=7개이다.

  • 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
  • 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
  • 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.
문제 16
<보기>의 AVL 트리에 5를 삽입한 후, AVL 트리의 균형을 유지하기 위해 수행해야 하는 회전으로 가장 옳은 것은?
1LL 회전
2RR 회전
3LR 회전
4RL 회전
정답 및 해설

5를 삽입하면 루트 30에서 왼쪽-왼쪽 방향으로 불균형이 생기므로 LL 회전을 수행한다.

그림의 트리는 루트 30의 왼쪽에 20(자식 10, 25), 오른쪽에 40이 있다. 5는 30→20→10을 거쳐 10의 왼쪽 자식으로 삽입된다.

삽입 후 30의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 균형 인수가 +2이고, 불균형 노드 30에서 삽입 위치까지 왼쪽→왼쪽으로 내려가므로 20을 축으로 오른쪽 회전하는 LL 유형이다. 회전 후 20이 루트가 되고 왼쪽에 10(자식 5), 오른쪽에 30(자식 25, 40)이 온다.

  • RR 회전은 불균형 노드의 오른쪽-오른쪽에 삽입된 경우에 쓴다.
  • LR 회전은 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우에 쓴다.
  • RL 회전은 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우에 쓴다.
문제 17
<보기>의 방향 그래프에 대해 위상 정렬(topological sort)을 수행할 때, 가능한 서로 다른 위상 순서의 총 개수는?
13
24
35
46
정답 및 해설

가능한 위상 순서는 모두 5가지이다.

그래프의 간선은 A→B, A→C, B→D, C→D, C→E, D→F, E→F이다. 진입 차수가 0인 정점은 A뿐이므로 A가 맨 앞, 모든 경로가 끝나는 F가 맨 뒤에 고정된다.

가운데 B, C, D, E는 D가 B·C 뒤에, E가 C 뒤에 와야 한다. B로 시작하면 B−C−D−E, B−C−E−D의 2가지, C로 시작하면 C−B−D−E, C−B−E−D, C−E−B−D의 3가지가 있어 합은 5가지이다.

  • 3가지는 C로 시작하는 경우만 센 값이다.
  • 4가지는 C−E−B−D처럼 E가 B보다 먼저 오는 순서를 빠뜨린 값이다.
  • 6가지는 가능한 5가지보다 많아, 간선 제약을 어기는 순서를 포함해야만 나오는 값이다.
문제 18
[691, 423, 17, 124, 80, 95, 3, 227] 배열을 LSD(least significant digit) 기수 정렬로 오름차순 정렬할 때, 2단계가 완료된 직후 배열 상태로 가장 옳은 것은?
1[3, 17, 124, 227, 423, 80, 691, 95]
2[3, 17, 423, 124, 227, 80, 691, 95]
3[17, 3, 227, 423, 124, 80, 95, 691]
4[17, 3, 423, 227, 124, 80, 95, 691]
정답 및 해설

2단계 직후 배열은 [3, 17, 423, 124, 227, 80, 691, 95]이다.

1단계(일의 자리): 0→80, 1→691, 3→423·3, 4→124, 5→95, 7→17·227 순으로 모아 [80, 691, 423, 3, 124, 95, 17, 227]이 된다.

2단계(십의 자리, 같은 자릿값은 앞 단계 순서 유지): 0→3, 1→17, 2→423·124·227, 8→80, 9→691·95 순으로 모은다.

  • [3, 17, 124, 227, 423, 80, 691, 95]: 십의 자리가 2인 원소를 백의 자리 기준으로 미리 정렬해 앞 단계 순서를 지키지 않았다.
  • [17, 3, 227, 423, 124, 80, 95, 691]: 십의 자리가 0인 3보다 1인 17을 앞에 두어 십의 자리 기준 정렬이 아니다.
  • [17, 3, 423, 227, 124, 80, 95, 691]: 역시 17이 3보다 앞서 있어 2단계 결과가 될 수 없다.
문제 19
<보기>는 무방향 그래프에서 깊이 우선 탐색(DFS, depth first search)을 수행하는 C 프로그램이다. dfs(0)을 호출했을 때, order[2]와 order[3]의 값으로 가장 옳은 것은?
int adj[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
int visited[5] = { 0, };
int order[5];
int cnt = 0;

void dfs(int v) {
visited[v] = 1;
order[v] = ++cnt;
for (int i = 0; i < 5; i++) {
if (adj[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
1order[2]: 2, order[3]: 4
2order[2]: 3, order[3]: 4
3order[2]: 5, order[3]: 3
4order[2]: 5, order[3]: 4
정답 및 해설

order[2]는 5, order[3]은 3이다.

인접 행렬을 인덱스 순서로 검사하며 방문하지 않은 정점이 있으면 즉시 재귀한다.

dfs(0): order[0]=1 → dfs(1): order[1]=2 → dfs(3): order[3]=3, 더 갈 곳이 없어 복귀 → dfs(4): order[4]=4 → dfs(2): order[2]=5.

  • order[2]: 2, order[3]: 4 — 정점 2는 1→4를 거친 뒤 마지막에 방문되므로 두 번째가 될 수 없다.
  • order[2]: 3, order[3]: 4 — 0과 가까운 정점부터 차례로 방문하는 너비 우선 탐색의 순서이다.
  • order[2]: 5, order[3]: 4 — 정점 1에서 인덱스가 작은 3을 4보다 먼저 방문하므로 order[3]은 3이다.
문제 20
크기가 8인 해시 테이블에서 해시 함수 h(k)=k mod 8h(k)=k \bmod 8을 사용하고, 충돌은 체이닝(chaining)으로 처리한다. <보기>의 키를 순서대로 삽입할 때, 가장 긴 체인이 형성된 버킷의 인덱스와 해당 체인의 길이를 옳게 짝지은 것은? (단, 버킷의 인덱스는 0부터 시작한다.)
13, 25, 6, 21, 14, 29, 8
1인덱스 0, 길이 2
2인덱스 5, 길이 3
3인덱스 5, 길이 4
4인덱스 6, 길이 2
정답 및 해설

가장 긴 체인은 인덱스 5, 길이 3이다.

13→5, 25→1, 6→6, 21→5, 14→6, 29→5, 8→0이므로 버킷 5에 13·21·29의 3개가 연결된다.

  • 인덱스 0, 길이 2: 버킷 0에는 8 하나만 저장된다.
  • 인덱스 5, 길이 4: 버킷 5의 키는 3개뿐이다.
  • 인덱스 6, 길이 2: 6·14의 2개로 가장 긴 체인이 아니다.