void whatsort(int a[ ], int size)
{
int i, j, temp;
for (i = (size-1); i > 0; i--) {
for (j = 1; j <= i; j++) {
if (a[j-1] > a[j]) {
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
이 함수는 버블 정렬을 구현한 것이다.
안쪽 반복에서 인접한 두 원소 a[j-1]과 a[j]를 비교해 앞쪽이 크면 교환하므로, 한 바퀴가 끝날 때마다 가장 큰 값이 구간 맨 뒤(i 위치)로 밀려난다. 바깥 반복은 이 구간을 한 칸씩 줄여 간다.
- 삽입 정렬: 새 원소를 이미 정렬된 앞부분의 알맞은 위치에 끼워 넣는 방식으로, 구간 끝까지 인접 교환을 되풀이하는 이 구조와 다르다.
- 선택 정렬: 한 바퀴에서 최솟값(또는 최댓값)의 위치를 찾은 뒤 한 번만 교환하므로, 비교할 때마다 교환하는 이 코드와 다르다.
- 힙 정렬: 배열을 힙으로 구성한 뒤 루트를 꺼내며 부모·자식 인덱스 관계로 재조정하는 방식이다.
후위 표현식 계산 중 여덟 번째로 push 되는 값은 3이다.
중위식을 변환하면 4 2 + 3 / 6 2 / 1 - +가 된다. 피연산자는 그대로 push 하고, 연산자를 만나면 두 값을 pop 해 계산한 결과를 다시 push 한다.
push 순서: 4 → 2 → 6(4+2) → 3 → 2(6/3) → 6 → 2 → 3(6/2) → 1 → 2(3-1) → 4(2+2)
- 1: 아홉 번째로 push 되는 피연산자이다.
- 2: 두 번째·다섯 번째·일곱 번째 등에 push 되는 값이다.
- 4: 첫 번째로 push 되는 피연산자이자 마지막 계산 결과이다.

A에서 Prim 알고리즘을 적용하면 최소 비용은 42이고, 마지막으로 선택되는 간선은 (A, G)이다.
Prim 알고리즘은 이미 선택된 정점 집합과 나머지 정점을 잇는 간선 중 가중치가 가장 작은 간선을 하나씩 추가한다. 선택 순서는 (A, B) 10 → (B, C) 5 → (C, E) 3 → (E, F) 7 → (F, D) 6 → (A, G) 11 이다.
합계는 이다. G는 (A, G) 11과 (F, G) 13으로만 연결되므로 마지막에 더 가벼운 (A, G)가 선택된다.
- 43, (A, G): 마지막 간선은 맞지만 최소 비용은 42이다.
- 44, (F, G): (F, G)는 가중치 13으로 (A, G)의 11보다 커서 신장 트리에 포함되지 않고, 비용도 42가 아니다.
- 45, (F, G): 마지막 간선과 비용이 모두 계산 결과와 다르다.

정점 6에서 인접 정점을 오름차순으로 방문하는 DFS의 방문 순서는 6, 5, 3, 1, 0, 2, 4, 7, 8, 9이다.
6의 인접 정점(5, 7) 중 작은 5로 가고, 5에서 3, 3에서 1, 1에서 0으로 내려간다. 0은 더 갈 곳이 없어 되돌아가(backtracking) 1의 다음 인접 정점 2, 이어서 4를 방문한다.
4의 인접 정점은 모두 방문했으므로 5까지 되돌아가 7을 방문하고, 7에서 8, 9 순으로 방문하면 탐색이 끝난다.
- 6, 5, 7, 3, 8, 9, 1, 4, 0, 2: 시작 정점에서 가까운 정점부터 차례로 방문한 너비 우선 탐색(BFS)의 순서이다.
- 6, 5, 3, 4, 2, 1, 0, 7, 8, 9: 3의 인접 정점 중 1이 4보다 작으므로 1을 먼저 방문해야 한다.
- 6, 5, 7, 3, 1, 4, 0, 2, 8, 9: 5에서 3이 7보다 작은데 7을 먼저 방문해 오름차순 조건에 어긋난다.
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[ ], int n)
{
int i, j, least, temp;
for (i = 0; i < n - 1; i++) {
least = i;
for (j = i + 1; j < n; j++)
if (list[j] < list[least]) least = j;
SWAP(list[i], list[least], temp);
}
}
ㄱ. sort(list, 5)의 수행이 완료될 때까지 SWAP은 4회 수행된다.
ㄴ. SWAP이 두 번째 수행된 후 배열 list에는 3, 4, 8, 6, 9가 순서대로 저장되어 있다.
ㄷ. 정렬 알고리즘의 시간 복잡도를 빅세타(Θ) 표기법으로 표현한 것은 Θ(nlogn)이다.
옳은 것은 ㄱ, ㄴ이다. 이 코드는 매 단계 최솟값을 골라 앞자리와 교환하는 선택 정렬이다.
4, 9, 8, 6, 3 → (i=0, 최솟값 3) 3, 9, 8, 6, 4 → (i=1, 최솟값 4) 3, 4, 8, 6, 9 → (i=2, 최솟값 6) 3, 4, 6, 8, 9 → (i=3, 최솟값 8, 자기 자신과 교환) 3, 4, 6, 8, 9
- ㄱ(옳음): SWAP은 바깥 반복마다 조건 없이 한 번씩 수행되므로 회이다.
- ㄴ(옳음): 두 번째 SWAP 직후 배열은 3, 4, 8, 6, 9이다.
- ㄷ(틀림): 입력 상태와 관계없이 비교가 회 일어나므로 시간 복잡도는 이다.
나머지와 다른 AVL 트리가 만들어지는 순서는 3, 4, 6, 5, 7, 8이다.
3, 4, 6 삽입 시 RR 회전으로 4가 루트가 되고, 5와 7을 넣은 뒤 8을 넣으면 루트 4에서 다시 불균형이 생겨 RR 회전이 일어난다. 결과는 루트 6, 왼쪽 4(자식 3, 5), 오른쪽 7(오른쪽 자식 8)이다.
나머지 세 순서는 모두 루트 5, 왼쪽 4(왼쪽 자식 3), 오른쪽 7(자식 6, 8)인 같은 트리가 된다.
- 5, 4, 7, 3, 6, 8: 회전 없이 바로 위 모양이 된다.
- 7, 5, 8, 6, 4, 3: 7(5(4, 6), 8)에서 3을 넣으면 루트 7에서 LL 불균형이 생기고, 오른쪽 회전으로 5가 루트가 된다.
- 8, 7, 5, 4, 6, 3: 8, 7, 5에서 LL 회전으로 7(5, 8)이 되고, 4, 6, 3을 넣은 뒤 다시 LL 회전으로 5가 루트가 된다.
옳지 않은 설명은 단말 노드 키 값의 합이 21이라는 것으로, 실제 합은 20이다.
원래 트리는 루트 5, 왼쪽 2(자식 1, 4), 4의 왼쪽 자식 3, 오른쪽 6, 6의 오른쪽 자식 8(자식 7, 9)이다. 루트를 삭제하면 왼쪽 서브트리 최댓값 4 또는 오른쪽 서브트리 최솟값 6이 루트 자리로 올라온다.
어느 쪽으로 대체해도 단말 노드는 1, 3, 7, 9로 같아 합은 20이다.
- 루트 키가 4와 6 중 하나: 삭제 노드를 중위 선행자나 중위 후속자로 대체하므로 옳다.
- 중위 순회 순서 1, 2, 3, 4, 6, 7, 8, 9: 이진 탐색 트리의 중위 순회는 남은 키의 오름차순이므로 옳다.
- 차수의 합 7: 노드가 8개이면 간선은 7개이고, 각 간선이 부모의 차수를 1씩 늘리므로 옳다.
| 대전 | 광주 | 서울 | 인천 | 대구 | |
|---|---|---|---|---|---|
| 대전 | 0 | 10 | 15 | 25 | 9 |
| 광주 | 10 | 0 | 18 | 20 | ∞ |
| 서울 | 15 | 18 | 0 | 3 | 17 |
| 인천 | 25 | 20 | 3 | 0 | ∞ |
| 대구 | 9 | ∞ | 17 | ∞ | 0 |
두 최단 경로 거리의 차이는 1이다.
인천-대구는 직접 연결이 없으므로 경유 경로를 비교한다.
- 인천→서울→대구: 3 + 17 = 20 (최단)
- 인천→서울→대전→대구: 3 + 15 + 9 = 27
- 인천→대전→대구: 25 + 9 = 34
광주-대구도 직접 연결이 없으며, 광주→대전→대구 = 10 + 9 = 19가 광주→서울→대구(35) 등보다 짧다.
따라서 차이는 20 − 19 = 1이다.
최적 이진 탐색 트리의 평균 비교 횟수는 1.5이다.
평균 비교 횟수는 각 키의 (깊이 × 탐색 확률)의 합이다. 확률이 큰 키를 루트 가까이 두어야 하므로 1을 루트로, 2를 그 오른쪽 자식, 3을 2의 오른쪽 자식으로 둔다.
- 루트 2(자식 1, 3):
- 루트 1, 오른쪽 자식 3, 3의 왼쪽 자식 2:
- 루트 3인 트리: 확률이 가장 큰 키 1이 깊이 2 이상에 놓여 평균이 2를 넘는다.
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|
| 13 | 16 | 9 | 10 | 11 | 2 | 3 |
| 16 | 13 | 9 | 10 | 11 | 2 | 3 |
| 3 | 13 | 9 | 10 | 11 | 2 | 16 |
| 13 | 11 | 9 | 10 | 2 | 3 | 16 |
삽입 후 해시 테이블은 [0]부터 3, 13, 9, 10, 11, 2, 16이다.
충돌이 없으면 위치에 넣고, 충돌하면 간격으로 다음 위치를 조사한다.
9: h=2 → [2]
10: h=3 → [3]
2: h=2 충돌, f=3 → (2+3) mod 7 = 5 → [5]
3: h=3 충돌, f=2 → [5] 충돌 → (3+4) mod 7 = 0 → [0]
16: h=2 충돌, f=4 → (2+4) mod 7 = 6 → [6]
13: h=6 충돌, f=2 → (6+2) mod 7 = 1 → [1]
11: h=4 → [4]
- [0]에 13, [6]에 3을 둔 배치: 13은 [1], 3은 [0]에 들어가므로 틀리다.
- [0]에 16, [1]에 13을 둔 배치: 16은 첫 충돌 후 [6]에 들어가므로 틀리다.
- [1]에 11, [4]에 2, [5]에 3을 둔 배치: 11은 충돌 없이 [4], 2는 [5]에 들어가므로 틀리다.
삭제되는 자료의 순서는 9, 2, 9, 4, 7, 3, 2, 6이다.
스택은 후입선출(LIFO)이므로 pop()은 항상 가장 최근에 push 된 값을 꺼낸다.
push(9)·pop() → 9
push(5, 7, 2)·pop() → 2 (남은 스택 5, 7)
push(9)·pop() → 9
push(4)·pop() → 4
pop() → 7 (남은 스택 5)
push(6, 3)·pop() → 3
push(2)·pop() → 2
pop() → 6 (남은 스택 5)
- 9, 5, 7, 2, 9, 4, 6, 3: 먼저 넣은 값부터 꺼내는 큐(FIFO) 방식으로 처리한 순서이다.
- 2, 3, 6, 4, 9, 2, 7, 5: 첫 pop()의 결과가 9이어야 하므로 시작부터 맞지 않는다.
- 9, 5, 9, 4, 7, 6, 2, 2: 두 번째 pop()에서 맨 위의 2가 아닌 바닥 쪽 5를 꺼낸 것으로 틀리다.
○ 루트 노드는 배열의 인덱스가 1인 위치에 저장된다.
○ 배열 인덱스가 인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 인 위치에 있으며 오른쪽 자식 노드는 인덱스가 인 위치에 있다.

가장 큰 인덱스가 34이고 인덱스가 0부터 시작하므로 필요한 배열의 최소 크기는 35이다.
루트 A가 1이면 B는 2, C는 3, D는 , E는 C의 왼쪽 자식이므로 이다.
F는 D의 왼쪽 자식으로 8, G는 F의 오른쪽 자식으로 , H는 G의 왼쪽 자식으로 가 된다. 사용하지 않는 인덱스 0 자리를 포함해 0~34까지 칸이 있어야 한다.
- 17: G의 인덱스 값일 뿐이며 H의 위치 34를 담지 못한다.
- 18: G(인덱스 17)까지만 담는 크기로 H의 위치 34를 담지 못한다.
- 34: 최대 인덱스 34를 담으려면 인덱스 0을 포함해 원소가 35개 필요하므로 하나 부족하다.
a[2][15][2]의 메모리 주소는 5056이다.
행 우선 순서에서 a[i][j][k]까지 앞선 원소 수는 이다.
- 2800: 원소 수 752에 원소 크기 4를 곱하지 않고 그대로 더한 값이다.
- 2804: 원소 크기 4를 곱하면 오프셋이 3008바이트이므로 3000 미만의 주소는 나올 수 없다.
- 5052: 앞선 원소 수를 751로 잘못 세어 원소 하나만큼 앞선 주소이다.
struct Dnode {
int key;
struct Dnode *prev;
struct Dnode *next;
};
current->next->prev = current;
current->next = current->next->next;
current->prev->next = current;
current->prev = current->prev->prev;
current의 왼쪽 노드를 삭제하려면 먼저 current->prev = current->prev->prev;로 current가 두 칸 왼쪽 노드를 가리키게 하고, 이어서 current->prev->next = current;로 그 노드가 current를 가리키게 한다.
첫 문장 뒤 current->prev는 삭제할 노드의 왼쪽 노드이므로, 두 번째 문장은 그 노드의 next를 current로 바꿔 삭제할 노드를 양방향 모두에서 건너뛰게 한다.
- current->next = current->next->next; 를 먼저 수행하는 순서: current의 오른쪽 노드를 삭제하는 연산이라 문제의 대상과 다르다.
- current->next->prev = current; 를 먼저 수행하는 순서: 역시 current의 오른쪽 노드를 다루며, 순서도 뒤바뀌어 오른쪽 노드 삭제로도 성립하지 않는다.
- current->prev->next = current; 를 먼저 수행하는 순서: 이때 current->prev는 아직 삭제할 노드이므로 삭제할 노드의 next만 바뀌고, 두 칸 왼쪽 노드의 next는 계속 삭제할 노드를 가리킨다.
#include <stdio.h>
int i;
int RecFunc(int n)
{
i++;
if (n <= 1)
return 1;
else
return RecFunc(n-1) + RecFunc(n-2);
}
int main()
{
int result;
i = 0;
result = RecFunc(5);
printf("%d, %d\n", i, result);
}
출력 결과는 15, 8이다.
RecFunc의 반환값은 , 이다. 따라서 R(2)=2, R(3)=3, R(4)=5, R(5)=8이다.
i는 호출될 때마다 1 증가하므로 호출 횟수는 , 이다. C(2)=3, C(3)=5, C(4)=9, C(5)=15이다.
- 13, 5: 호출 횟수와 반환값을 모두 작게 센 값이다.
- 13, 8: 반환값은 맞지만 호출 횟수를 15보다 적게 셌다.
- 15, 5: 호출 횟수는 맞지만 5는 R(4)의 값이고 R(5)는 8이다.
| 위치 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 키 | 3 | 10 | 15 | 19 | 24 | 30 | 40 | 65 | 70 | 74 | 80 | 82 | 87 | 93 |
보간 탐색의 첫 번째 탐색 위치는 3이다.
보간 탐색은 키 값의 비율로 위치를 추정한다.
소수점 이하를 반올림하면 3이다.
- 2: 계산값 3.03을 반올림한 결과보다 작다.
- 4: 키 24가 실제로 저장된 위치일 뿐, 첫 탐색 위치는 비례 계산으로 정해진다.
- 5: 계산값 3.03을 반올림한 결과보다 크다.
struct Cnode {
int key;
struct Cnode *link;
};
last = new_node;
last->link = new_node;
last->link = new_node;
last = new_node;
new_node->link = last->link;
last = new_node;
last->link = new_node;
new_node->link = last->link;
원형 연결 리스트의 끝에 삽입하려면 new_node->link = last->link; → last->link = new_node; → last = new_node; 순서로 수행한다.
last->link는 처음 노드를 가리키므로, 이 값을 먼저 new_node->link에 보관해야 처음 노드를 잃지 않는다. 그다음 기존 마지막 노드를 new_node에 연결하고, 마지막으로 last를 new_node로 옮긴다.
- last = new_node; 를 둘째로 수행하는 순서: 기존 마지막 노드가 new_node와 연결되지 않고, new_node가 자기 자신을 가리키게 된다.
- last->link = new_node; 를 먼저 수행하는 순서: 처음 노드의 주소를 잃어 new_node->link가 자기 자신을 가리키게 된다.
- last = new_node; 를 먼저 수행하는 순서: 기존 마지막 노드를 가리킬 방법이 없어져 리스트에 연결할 수 없다.
typedef struct {
int row;
int col;
int val;
} term;
term A[ ] = ㉠ ;○ 첫 번째 구조체인 A[0]의 row, col, val에는 희소 행렬의 행 개수, 열 개수, 값이 0이 아닌 원소 개수를 순서대로 저장한다.
○ 두 번째부터의 나머지 구조체는 값이 0이 아닌 희소 행렬 원소를 표현하기 위해 사용되며, 각 구조체의 row, col, val에 해당 원소의 행 번호, 열 번호, 값을 순서대로 저장한다.
○ 값이 0이 아닌 희소 행렬 원소 정보는 행 번호의 오름차순으로 구조체 배열 A에 저장되며, 행 번호가 같은 경우에는 열 번호의 오름차순으로 저장된다.
㉠에 들어갈 내용은 {{5, 5, 4}, {0, 1, 5}, {0, 2, 2}, {1, 3, 1}, {3, 0, 3}}이다.
A[0]에는 행 수 5, 열 수 5, 0이 아닌 원소 수 4를 저장한다. 나머지는 행 번호 오름차순(같으면 열 번호 오름차순)으로 (0, 1, 5), (0, 2, 2), (1, 3, 1), (3, 0, 3)을 저장한다.
- {4, 4, 4}로 시작하고 행 순서로 나열한 것: 행·열 개수 자리에 최대 인덱스 4를 잘못 적었다.
- {4, 4, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 행·열 개수도 틀리고, 열 번호 기준으로 정렬해 규칙에도 어긋난다.
- {5, 5, 4}로 시작하고 (3, 0, 3)을 앞에 둔 것: 첫 구조체는 맞지만 열 번호 기준으로 정렬해 행 번호 오름차순 규칙에 어긋난다.
만들 수 있는 신장 트리의 총 개수는 16이다.
케일리 공식에 따르면 정점이 n개인 완전 그래프의 서로 다른 신장 트리 수는 이다.
검산: 간선 6개 중 3개를 고르는 20가지에서 사이클(삼각형)이 되는 4가지를 빼면 16이다.
- 12: 일렬 경로 모양(12개)만 세고 한 정점에 나머지 셋이 붙는 별 모양(4개)을 빠뜨린 값이다.
- 14: 사이클이 되는 조합은 삼각형 4가지뿐이므로 20에서 6을 뺀 이 값은 맞지 않는다.
- 18: 사이클 조합을 2가지만 제외한 셈이 되어 맞지 않는다.
후위 순회 결과는 1, 3, 7, 6, 9, 8, 2이다.
2(흑, 루트)에 1, 8을 적색으로 삽입한다. 9 삽입 시 부모 8과 삼촌 1이 모두 적색이라 색 변경(1, 8 흑)하고, 7은 8의 왼쪽 적색 자식이 된다.
3 삽입 시 부모 7과 삼촌 9가 적색이라 색 변경(7, 9 흑, 8 적)한다. 6 삽입 시 부모 3은 적색, 삼촌(7의 오른쪽)은 흑색이고 꺾인 모양이므로 이중 회전을 하여 6(흑)이 3, 7(적)을 자식으로 갖는다.
최종 트리: 2(1, 8(6(3, 7), 9))
- 1, 3, 6, 2, 9, 8, 7: 루트를 7로 본 순서로, 루트 2는 회전 없이 그대로 유지된다.
- 1, 6, 3, 2, 9, 8, 7: 루트를 7로 잘못 잡았고 6과 3의 부모·자식 관계도 뒤바뀌었다.
- 1, 6, 3, 7, 9, 8, 2: 회전 없이 6을 3의 오른쪽 자식으로 둔 것으로, 이중 회전 후에는 6이 3과 7의 부모가 된다.