높이 h인 m원 탐색 트리의 최대 노드 수는 이므로, 최대 노드 수를 로 본 설명이 옳지 않다.
각 노드는 최대 m개의 자식을 가지므로 레벨별 최대 노드 수는 이고, 이 등비급수의 합이 이다. 은 노드 수가 아니라 노드당 개씩 저장되는 최대 키 수에 해당한다.
- 루트 노드가 최대 m개의 서브트리를 가질 수 있다는 설명은 m원 탐색 트리의 정의 그대로이다.
- 노드에 저장된 키들이 정렬되어 있어야 한다는 설명은 탐색 트리의 조건으로 옳다.
- 각 서브트리 역시 m원 탐색 트리라는 설명은 재귀적 정의로 옳다.
#define MAX_QUEUE_SIZE 10
int queue[MAX_QUEUE_SIZE];
int front = rear = -1;
void addq(int front, int *rear, int item) {
㉠
if ( ㉡ ) {
printf(“Queue is full!!\n”);
return -1;
}
queue[*rear] = item;
}
㉠에는 *rear = (*rear+1) % MAX_QUEUE_SIZE;, ㉡에는 front == *rear가 들어간다.
원형 큐 삽입은 rear를 먼저 한 칸 원형으로 전진시킨 뒤, 전진한 rear가 front와 겹치면 포화로 판단한다. 이 구현은 front 자리를 비워 두어 공백(front == rear)과 포화를 구분한다.
- *rear = (front+1) % MAX_QUEUE_SIZE; 와 front == *rear + 1 조합은 삽입 위치를 front 기준으로 잡아 rear가 차례로 전진하지 않고, 포화 비교에도 나머지 연산이 빠져 있다.
- front = (front+1) % MAX_QUEUE_SIZE; 와 front == *rear 조합은 삽입에서 삭제 쪽 포인터를 옮기는 것이며, front는 값으로 전달되어 바뀌지도 않는다.
- front = (*rear+1) % MAX_QUEUE_SIZE; 와 front == *rear + 1 조합은 rear를 전진시키지 않아 같은 자리에 덮어쓰게 된다.

Kruskal 알고리즘에서 선택되지 않는 간선은 (C, D)이다.
가중치가 작은 간선부터 사이클이 생기지 않으면 채택한다. (A, D)=1, (A, C)=2를 고른 뒤 (C, D)=3은 A–C–D 사이클을 만들므로 버린다.
이어서 (D, E)=4를 채택하고 (C, E)=5는 사이클이라 버리며, (B, C)=6, (B, F)=7을 채택하면 정점 6개에 간선 5개로 신장 트리가 완성된다.
- (A, C)는 가중치 2로 두 번째에 채택된다.
- (B, C)는 가중치 6으로 B를 트리에 연결하며 채택된다.
- (B, F)는 가중치 7로 마지막에 F를 연결하며 채택된다.
struct node {
int data;
struct node *left;
struct node *right;
};
int func(struct node *ptr) {
if (ptr == NULL)
return 0;
else if (ptr->left == NULL
&& ptr->right == NULL)
return 1;
else
return (ptr->data + func(ptr->left)
+ func(ptr->right));
}
함수 func의 결과 값은 20이다.
func는 리프 노드면 1을 반환하고, 그 외 노드는 자기 data에 왼쪽·오른쪽 서브트리 결과를 더한다(NULL은 0).
노드 2는 2+1(리프 1)+0(NULL)=3, 노드 10은 10+1(리프 7)+1(리프 12)=12이다.
루트 5는 5+3+12=20이 된다.
- 17은 내부 노드 data(5, 2, 10)만 더하고 리프가 반환하는 1을 빠뜨린 값이다.
- 37은 리프의 data까지 모든 노드 값을 더한 값으로, 리프는 data가 아니라 1을 반환하므로 틀리다.
행우선으로 저장할 때 원소 의 색인은 이다.
하삼각 행렬의 r행에는 0이 아닌 원소가 r개 있으므로, i행 앞의 행들에 저장된 원소 수는 이다.
i행 안에서 앞에는 개의 원소가 있고 색인이 0부터 시작하므로 두 값을 더한 것이 k가 된다.
예를 들어 는 로, 다음 위치에 저장된다.
- 은 0까지 모두 저장하는 일반 정방 행렬의 행우선 색인이다.
- 은 일반 정방 행렬의 열우선 색인이다.
- 은 상삼각 행렬을 열우선으로 저장할 때의 식으로, 하삼각 행렬의 행우선 저장에는 맞지 않는다.

Dijkstra 알고리즘이 최단 거리를 확정하는 노드 순서는 a-b-c-d-e-f이다.
매 단계 거리가 가장 작은 미확정 노드를 확정한다. a(0) 다음 b(2)를 확정하면 c가 2+1=3으로 갱신되어 c(3)가 확정된다.
c에서 d가 3+2=5로 갱신되어 d(5), d에서 e가 5+1=6으로 갱신되어 e(6), 마지막으로 e에서 f가 6+1=7로 f(7)가 확정된다.
- a-b-d-f는 비용 2+4+3=9인 경로로, 최단 경로도 확정 순서도 아니다.
- a-c-d-f는 a에서 c로 직접(4) 가는 경로로, c는 b를 거친 3이 더 짧으며 확정 순서와도 다르다.
- a-c-d-e-f는 a→f 최단 경로(a-b-c-d-e-f, 비용 7)와도 다르고, b의 확정을 빠뜨린 순서이다.
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|
| 21 | 37 | 22 | 17 | 11 | 30 | 5 | 10 | 9 |
첫 데이터를 출력하고 재구성한 히프에서 여섯 번째 위치의 값은 9이다.
내림차순으로 출력하므로 최대 히프를 만든다. 마지막 비단말 노드부터 아래로 조정하면 22와 30, 21과 37이 교환되어 히프는 37, 21, 30, 17, 11, 22, 5, 10, 9가 된다.
루트 37을 출력하고 마지막 원소 9를 루트로 올린 뒤 아래로 재조정하면 9가 30과, 다시 22와 교환되어 30, 21, 22, 17, 11, 9, 5, 10이 된다. 따라서 여섯 번째 칸에는 9가 놓인다.
- 5는 일곱 번째 칸에 그대로 남는다.
- 10은 여덟 번째 칸에 그대로 남는다.
- 11은 다섯 번째 칸에 그대로 남는다.
이 허프만 트리의 가중 외부 경로 길이 합은 112이다.
가장 작은 두 가중치를 반복해서 합치면 3+4=7, 6+7=13, 8+10=18, 13+15=28, 18+28=46 순으로 트리가 만들어진다.
가중 경로 길이 합 = 내부 노드 값의 합 = 7+13+18+28+46 = 112
거리로 확인하면 가 4, 이 3, 가 2이므로 이다.
- 루트까지 가장 긴 거리는 4이며 5가 아니다.
- 가장 긴 거리를 갖는 외부 노드는 뿐이고, 은 거리 3이다.
- 는 모두 거리 2로 같으므로 만 가장 짧다고 할 수 없다.
| 15 | 3 | 1 | 35 | 20 | 4 | 18 | 26 |
마지막 레코드를 피봇으로 분할해 가면 15, 3, 1, 4, 20, 18, 26, 35는 어느 단계에서도 나타나지 않는다.
1단계(피봇 26): 왼쪽에서 26 이상인 35, 오른쪽에서 26 미만인 18을 찾아 교환한 뒤, 엇갈린 위치에 피봇을 놓으면 15, 3, 1, 18, 20, 4, 26, 35가 된다.
2단계(왼쪽 구간, 피봇 4): 15와 1을 교환하고 피봇을 놓아 1, 3, 4, 18, 20, 15, 26, 35가 된다.
3단계(18, 20, 15 구간, 피봇 15): 1, 3, 4, 15, 20, 18, 26, 35가 된다.
1단계 직후 피봇 왼쪽 구간의 다음 피봇은 4이므로, 15, 3, 1이 앞에 그대로 남은 채 4와 18의 자리만 바뀐 배열은 분할 과정에서 만들어지지 않는다.
- 15, 3, 1, 18, 20, 4, 26, 35는 1단계 결과이다.
- 1, 3, 4, 18, 20, 15, 26, 35는 2단계 결과이다.
- 1, 3, 4, 15, 20, 18, 26, 35는 3단계 결과이다.
스택에 가장 많이 쌓일 때 토큰 수는 4개이다.
a 출력 → * 삽입 → ( 삽입 → b 출력 → - 삽입 → c 출력 순으로 진행된다.
이어 *는 스택 top의 -보다 우선순위가 높아 그대로 쌓이므로 스택은 *, (, -, *로 최대가 되며, 여는 괄호도 스택 토큰으로 센다.
이후 ) 에서 *와 -가 꺼내지고 ( 가 제거되며, / 는 같은 우선순위의 *를 꺼낸 뒤 들어가므로 다시 4개에 이르지 않는다. 변환 결과는 a b c d * - * e / 이다.
- 3개는 여는 괄호를 빼고 연산자만 센 값이다.
- 5개는 피연산자가 스택을 거치지 않고 바로 출력된다는 점을 놓친 값이다.
- 6개도 같은 이유로 스택에 실제로 쌓이는 토큰 수를 넘는다.
ㄴ. 사이클이 없고 n - 1개의 간선(edge)을 갖는 연결 그래프(connected graph)를 트리(tree)라고 한다.
ㄷ. n개의 정점(vertex)을 가진 방향 그래프의 최대 간선 수는 개이다.
ㄹ. 경로를 구성하는 간선의 수를 길이라고 할 때, 방향 그래프에서 사이클(cycle)의 길이는 항상 3 이상이다.
옳은 것은 ㄱ, ㄴ이다.
무방향 그래프는 간선 (u, v)와 (v, u)가 같으므로 인접행렬이 주대각선 기준으로 대칭이다. 사이클 없이 연결되고 간선이 n-1개인 그래프는 트리의 정의와 같다.
- ㄷ: n개 정점의 방향 그래프 최대 간선 수는 이며, 가 아니다.
- ㄹ: 방향 그래프에서는 와 만으로 길이 2인 사이클이 생기므로 항상 3 이상인 것은 아니다.
문자 c를 반환하는 것은 head(tail(A))이다.
A = ((a, b), c, d)에서 tail(A) = (c, d)이고, 여기에 첫 원소를 꺼내는 head를 적용하면 c가 된다.
- head(head(A))는 head(A) = (a, b)의 첫 원소인 a를 반환한다.
- head(tail(head(A)))는 (a, b)의 tail인 (b)의 첫 원소 b를 반환한다.
- head(tail(tail(A)))는 tail(tail(A)) = (d)의 첫 원소 d를 반환한다.
struct node {
int data;
struct node *link;
};
int countNode(struct node *ptr, int value)
{
int count = 0;
while ( ㉠ ) {
if ( ptr->data == value ) count++;
㉡
}
return count;
}㉠은 ptr != NULL, ㉡은 ptr = ptr->link;이다.
리스트 끝(NULL)에 도달할 때까지 반복하면서 매번 포인터를 다음 노드로 옮겨야 모든 노드의 data를 검사할 수 있다.
- ptr == NULL 과 ptr->link = ptr; 조합은 비어 있지 않은 리스트에서 반복문이 한 번도 실행되지 않고, 링크도 자기 자신을 가리키게 망가뜨린다.
- ptr == NULL 과 ptr = ptr->link; 조합은 이동은 맞지만 조건이 반대라 비어 있지 않은 리스트에서 반복문이 실행되지 않는다.
- ptr != NULL 과 ptr->link = ptr; 조합은 포인터를 옮기지 않고 노드가 자기 자신을 가리키게 해 무한 반복을 일으킨다.
int fibonacci( int n )
{
printf(“%d\n”, n);
if ( n == 0 )
return 0;
else if ( n == 1 )
return 1;
else
return ( fibonacci( n - 1 )
+ fibonacci( n - 2 ) );
}
출력 순서는 4, 3, 2, 1, 0, 1, 2, 1, 0이다.
함수는 진입하자마자 n을 출력하고 fibonacci(n-1)을 먼저 끝까지 호출한 뒤 fibonacci(n-2)를 호출하는 전위 순회 순서로 출력된다.
f(4) → f(3) → f(2) → f(1), f(0) 출력 후 f(3)의 두 번째 호출 f(1)이 1을 출력하고, 마지막으로 f(4)의 두 번째 호출 f(2) → f(1), f(0)이 2, 1, 0을 출력한다.
- 4, 3, 2, 2, 1, 1, 0, 1, 0은 같은 깊이를 먼저 출력하는 너비 우선 순서처럼 나열한 것이다.
- 4, 3, 2, 1, 0, 2, 1, 1, 0은 f(3)의 두 번째 호출 f(1)보다 f(4)의 f(2)를 먼저 출력해 호출 순서가 어긋난다.
- 4, 3, 2, 1, 0, 2, 1, 0, 1은 f(4)의 f(2)를 먼저 출력한 데다 f(3)의 f(1)을 맨 끝에 두어 호출 순서가 어긋난다.
int binarySearch(int *a, int key, int low,
int high)
{
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (key == a[middle])
return middle;
else if (key > a[middle])
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
비교 횟수가 다른 것은 key가 7인 호출로, 3회 만에 찾는다. 나머지는 모두 5회이다.
low = 1, high = 20에서 시작하고 b[i] = i이므로 middle 값이 곧 비교 대상 값이다. key 7은 middle이 10, 5, 7로 바뀌며 세 번째 비교에서 찾는다. 반복마다 수행하는 비교를 모두 세어도 이 호출만 짧다.
- key 4는 middle이 10, 5, 2, 3, 4로 바뀌어 5회 비교한다.
- key 9는 middle이 10, 5, 7, 8, 9로 바뀌어 5회 비교한다.
- key 14는 middle이 10, 15, 12, 13, 14로 바뀌어 5회 비교한다.
ㄴ.
ㄷ.
ㄹ.
옳은 것은 ㄱ, ㄹ이다.
빅오는 함수가 상한 함수의 상수배 이하로 자라면 성립하고, 세타는 위아래 모두 같은 차수로 묶여야 성립한다.
- ㄱ: 이 보다 훨씬 빠르게 증가하므로 전체가 이다.
- ㄹ: 최고차 항이 이므로 이다.
- ㄴ: 은 보다 로그 배만큼 작아 하한을 만족하지 못하므로 가 아니다.
- ㄷ: 은 보다 배로 커지고 첫 항 도 이미 상한을 넘으므로 이 아니다.

노드 A에서 F까지의 최소 비용은 3이다.
F로 들어오는 간선은 E→F(−7)뿐이고, E는 G→E(4), G는 D→G(2) 또는 F→G로만 도달한다. 따라서 A에서 D까지의 최단 거리가 핵심이다.
음의 간선을 이용한 A→C→B→D가 9−15+10=4로 가장 짧다.
이어서 G=4+2=6, E=6+4=10, F=10−7=3이다. 순환 F→G→E→F의 합은 5+4−7=+2로 양수라 더 줄어들지 않는다.
- 9는 A→C→D(9+1=10)를 거친 값으로, 음의 간선 C→B(−15)를 활용한 더 짧은 경로를 놓친 결과이다(Dijkstra처럼 B를 먼저 확정해 버리면 이 값이 나온다).
typedef struct node{
struct node *link;
char data;
} listNode;
typedef struct{
listNode *head;
} linkedList;
void reverse(linkedList *L)
{
listNode *p, *q, *r;
p = L->head;
q = r = NULL;
while ( p != NULL) {
r = q;
q = p;
p = p->link;
㉠
}
L->head = q;
}㉠에는 q->link = r;가 들어간다.
반복마다 r은 이전 노드, q는 현재 노드, p는 다음 노드를 가리키도록 한 칸씩 이동한다. p를 미리 다음 노드로 옮겨 두었으므로 현재 노드 q의 링크를 이전 노드 r로 뒤집어도 나머지 리스트를 잃지 않는다.
반복이 끝나면 q가 원래의 마지막 노드이므로 L->head = q로 역순 리스트가 완성된다.
- q = q->link;는 링크를 바꾸지 않고 포인터만 옮기므로 역순이 되지 않는다.
- p->link = q;는 다음 노드의 링크를 바꿔 이후 노드를 잃게 되고, 마지막 반복에서 p가 NULL이면 오류가 난다.
- r->link = q;는 이전 노드가 현재 노드를 가리키는 원래 방향 그대로이며, 첫 반복에서 r이 NULL이라 오류가 난다.
#include <stdio.h>
#define MAX 10
void merge( int list[], int temp[], int left,
int middle, int right)
{
int i=left, j=middle+1, k=left, t;
for( ; i <= middle && j <= right ; ) {
if( list[i] <= list[j] )
temp[k] = list[i++];
else
temp[k] = list[j++];
k += 1;
}
if( i > middle ) {
for( t = j ; t <= right ;)
temp[k++] = list[t++];
} else {
for( t = i ; t <= middle ;)
temp[k++] = list[t++];
}
for( t = left ; t <= right ; t++ )
list[t] = temp[t];
}
void mergeSort( int list[], int temp[], int left,
int right)
{
int middle = 0;
if( left < right ) {
middle = (left+right)/2;
mergeSort(list, temp, left, middle);
mergeSort(list, temp, middle+1, right);
merge(list, temp, left, middle, right);
}
}
int main(){
int source[10]={26, 13, 77, 61, 35, 11, 8,
48, 15, 19};
int temp[10] = {0x0,};
mergeSort(source, temp, 0, 9);
}
수행 중 나타나지 않는 배열은 13, 26, 35, 61, 77, 8, 11, 15, 48, 19이다.
mergeSort(0, 9)는 왼쪽 구간 [0..4]를 먼저 끝까지 정렬한 뒤 오른쪽 구간 [5..9]를 처리한다.
[0..2] 병합 후: 13, 26, 77, 61, 35, 11, 8, 48, 15, 19
[0..4] 병합 후: 13, 26, 35, 61, 77, 11, 8, 48, 15, 19
[5..7] 병합 후: 13, 26, 35, 61, 77, 8, 11, 48, 15, 19
[5..9] 병합 후: 13, 26, 35, 61, 77, 8, 11, 15, 19, 48
[8..9]의 15, 19는 병합해도 순서가 그대로이고, 마지막 병합에서 8, 11, 48과 15, 19가 한 번에 합쳐지므로 48이 19 앞에 남은 상태는 생기지 않는다.
- 13, 26, 77, 61, 35, 11, 8, 48, 15, 19는 [0..2] 병합 직후 상태이다.
- 13, 26, 35, 61, 77, 11, 8, 48, 15, 19는 [0..4] 병합 직후 상태이다.
- 13, 26, 35, 61, 77, 8, 11, 15, 19, 48은 [5..9] 병합 직후 상태이다.
2-노드 3-노드 4-노드 5-노드

값 9를 삭제한 결과 트리는 2-노드 0개, 3-노드 3개, 4-노드 1개, 5-노드 2개이다.
차수 5인 B-트리에서 루트 외 노드는 키를 최소 2개 가져야 한다. [9, 10]에서 9를 지우면 [10]만 남아 언더플로가 생기고, 왼쪽 형제 [5, 6]도 최소 개수라 빌려올 수 없으므로 부모 키 8을 내려 [5, 6, 8, 10]으로 합병한다.
그러면 부모 [3, 8]이 [3]으로 언더플로가 되고, 형제 [19, 22]도 최소라 루트 키 15를 내려 [3, 15, 19, 22]로 합병하며 이것이 새 루트가 된다.
결과: 루트 [3, 15, 19, 22] 아래 [1, 2], [5, 6, 8, 10], [16, 18], [20, 21], [24, 25, 26]이다.
- 2-노드 2개·3-노드 6개·4-노드 1개 구성은 합병 없이 9만 지운 상태처럼 노드 수를 센 것으로, 합병 후 전체 노드는 6개뿐이다.
- 2-노드 2개·3-노드 4개·4-노드 1개·5-노드 1개 구성은 키 1개짜리 노드가 남는다고 본 것으로, 합병 후에는 키 1개 노드가 없다.
- 3-노드 2개·4-노드 3개 구성은 키 2개 노드([1, 2], [16, 18], [20, 21])가 3개, 키 3개 노드는 [24, 25, 26] 하나라는 점과 맞지 않는다.