int recursive( int n ) {
if(n<1) return 2;
else return( 22 * recursive(n-1) + 1);
}재귀식을 바닥부터 차례로 풀면 recursive(4)의 값은 597이다.
n이 1보다 작으면 2를 반환하고, 그 외에는 을 반환하는 재귀 호출 구조이다.
r(0) = 2
r(1) = 4×2+1 = 9
r(2) = 4×9+1 = 37
r(3) = 4×37+1 = 149
r(4) = 4×149+1 = 597
- 149는 r(3)에서 멈춘 값으로, 한 단계를 덜 계산한 것이다.
- 265는 점화식 어느 단계에서도 나오지 않는 값이다.
- 373도 점화식 어느 단계에서도 나오지 않는 값이다.
서로 다른 변수는 동일한 주소를 가질 수 없으므로, &pt1==&pt2 에서 서로 다른 포인터 변수가 같은 주소에 있을 수 있다는 설명이 옳지 않다.
&pt1은 포인터 변수 자신의 주소, pt1은 그 변수에 저장된 값(가리키는 대상의 주소), *pt1은 가리키는 대상의 값이다.
- pt1==pt2는 두 포인터가 같은 대상을 가리키는지 검증한다 — 옳다.
- *pt1==*pt2는 값 비교이므로 대상이 달라도 값이 같으면 참이 될 수 있다 — 옳다.
- pt1==pt2는 곧 가리키는 대상의 주소가 동일한지를 비교하는 것이다 — 옳다.

이 장치는 1부터 10까지 순서대로 들어오는 입력을 스택 하나로 재배열하는 것이므로, 출력열이 유효한 스택 순열이어야 하며 3 4 6 7 8 5 9 2 1 10만 가능하다.
판정 요령은 어떤 수가 나올 때 그보다 작은데 아직 안 나온 수는 스택에 쌓여 있으므로, 이후에는 큰 수부터 역순으로만 나올 수 있다는 것이다. 정답열은 1·2를 쌓고 3·4를 바로 보내고, 5를 쌓은 뒤 6·7·8을 보내고 5를 꺼내며, 9를 보낸 뒤 2·1을 꺼내고 10을 보내면 만들어진다.
- 1 8 5 6 7 4 9 3 10 2: 8이 나올 때 스택 top은 7인데 다음에 5가 나와야 하므로 불가능하다.
- 3 4 8 5 6 7 2 9 1 10: 8이 나올 때 스택에 5·6·7이 쌓여 top이 7인데 5가 먼저 나오므로 불가능하다.
- 9 4 7 5 6 3 8 1 2 10: 9가 나올 때 1~8이 모두 스택에 있어 top이 8인데 4가 나오므로 불가능하다.
합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.
정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 이다.
- 합병정렬의 최악 시간은 으로, 퀵정렬의 최악 보다 빠르다 — 옳다.
- 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 이 성립한다 — 옳다.
- 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | 1 | ||||
| e | 1 | 1 | ||||
| f |
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | 1 | |||
| f |
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f |
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f | 1 |
위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.
d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.
- d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
- e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
- f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.
완성된 AVL 트리에서 7은 5 → 10 → 7 순으로 세 번 비교로 찾으므로, 네 번의 비교가 필요하다는 설명이 옳지 않다.
삽입 중 회전: 10 삽입 시 LL(루트 11) → 3 삽입 시 LL(노드 10 기준) → 7 삽입 시 LR(루트 10) → 13 삽입 시 RR(노드 11 기준) → 2 삽입 시 LR(노드 3 기준) → 4 삽입 시 루트 10에서 LL 회전이 일어나 루트가 5가 된다.
최종 트리: 5의 왼쪽 2(자식 1, 3), 3의 오른쪽 4 / 5의 오른쪽 10(자식 7, 12), 7의 왼쪽 6, 12의 자식 11, 13.
- 최종 루트 값은 5이다 — 옳다.
- 4를 넣으면 루트 10의 균형인수가 2가 되어 재구성이 발생한다 — 옳다.
- 6은 7의 왼쪽 자식이며 자식이 없는 리프노드이다 — 옳다.
연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.

인접 리스트에서 간선 삽입은 , 간선 제거는 이다.
삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.
- 삽입 ·제거 : 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
- 삽입 ·제거 : 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
- 삽입 ·제거 : 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 0 | 4 | 9 | ∞ | ∞ | ∞ | ∞ |
| B | 4 | 0 | 4 | 10 | ∞ | ∞ | ∞ |
| C | 9 | 4 | 0 | ∞ | 8 | ∞ | 1 |
| D | ∞ | 10 | ∞ | 0 | 2 | 5 | ∞ |
| E | ∞ | ∞ | 8 | 2 | 0 | ∞ | 6 |
| F | ∞ | ∞ | ∞ | 5 | ∞ | 0 | 3 |
| G | ∞ | ∞ | 1 | ∞ | 6 | 3 | 0 |
Dijkstra 알고리즘으로 확정되는 정점 순서는 A→B→C→G→F→D→E이다.
매 단계 미확정 정점 중 최소 거리 정점을 확정하고 인접 거리를 갱신한다.
A 확정: B=4, C=9
B(4) 확정: C=min(9, 8)=8, D=14
C(8) 확정: E=16, G=9
G(9) 확정: E=min(16, 15)=15, F=12
F(12) 확정: D=min(14, 17)=14
D(14) 확정: E=min(15, 16)=15
E(15) 확정
- G 다음에 D를 고르는 순서는 F(12)가 D(14)보다 가깝다는 점을 놓친 것이다.
- G 다음 E, D, F 순서는 E(15)보다 F(12)·D(14)가 먼저 확정되어야 하므로 틀리다.
- G 다음 E, F, D 순서도 E(15)를 가장 가까운 F(12)보다 먼저 확정해 틀리다.
struct TreeNode {
int Element;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;
SearchTree Insert( int X, SearchTree T )
{
if ( T == NULL ) {
T = (SearchTree)malloc(sizeof(struct TreeNode));
T->Element = X;
T->Left = T->Right = NULL;
} else if ( X < T->Element )
㉠
else if ( X > T->Element )
㉡
return T;
}㉠ ㉡㉠에는 T->Left = Insert( X, T->Left );, ㉡에는 T->Right = Insert( X, T->Right );가 들어간다.
X가 현재 노드 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에 재귀적으로 삽입하고, 반환된 서브트리 루트를 해당 자식 포인터에 다시 연결한다.
- Insert( X, T )로 자기 자신을 다시 넘기면 T가 NULL이 되지 않아 무한 재귀에 빠진다.
- T->Element는 정수 값이므로 트리 포인터 인자로 넘길 수 없다.
- 왼쪽 자식 자리에 오른쪽 서브트리 삽입 결과를 연결하는 식으로 좌우를 뒤바꾸면 기존 서브트리가 엇갈려 이진탐색트리의 대소 규칙이 깨진다.




두 번 삭제한 뒤의 최대힙은 레벨 순서로 35, 19, 23, 2, 8, 13이다(루트 35, 왼쪽 자식 19의 자식 2·8, 오른쪽 자식 23의 자식 13).
차례로 삽입하며 상향 조정하면 힙 배열은 55, 35, 47, 19, 8, 13, 23, 2가 된다.
첫 삭제: 55를 빼고 마지막 원소 2를 루트로 올려 하향 조정 → 47, 35, 23, 19, 8, 13, 2.
둘째 삭제: 47을 빼고 2를 루트로 올려 더 큰 자식과 교환 → 35, 19, 23, 2, 8, 13.
- 루트 35의 왼쪽이 23, 오른쪽이 19인 트리: 첫 삭제 뒤 23은 47의 오른쪽 서브트리에 있었으므로 오른쪽 자식 자리에 남아야 한다.
- 19의 자식이 2·13이고 23의 자식이 8인 트리: 8과 13의 위치가 서로 바뀌어 하향 조정 경로와 맞지 않는다.
- 왼쪽 23(자식 2·13)·오른쪽 19(자식 8)인 트리: 좌우 서브트리와 리프 배치가 모두 실제 결과와 다르다.
후위 연산식은 1 2 3 4 * 5 6 + / - + 7 - 이며, 네 번째 연산자는 -이다.
괄호 안은 3*4를 (5+6)으로 나눈 뒤 2에서 빼므로 2 3 4 * 5 6 + / - 가 된다.
여기에 1을 더하고 7을 빼면 전체 식이 완성된다.
연산자 등장 순서: * → + → / → - → + → -
- +는 두 번째(5+6)와 다섯 번째(1과의 덧셈)에 나온다.
- *는 첫 번째 연산자이다.
- /는 세 번째 연산자이다.
| Index | Name | Pointer |
|---|---|---|
| 1 | KIM | 6 |
| 2 | PARK | 1 |
| 3 | CHOI | 4 |
| 4 | BAEK | 2 |
| 5 | LEE | 7 |
| 6 | MIN | 5 |
| 7 | ANN | 8 |
| 8 | JUNG | - |
HEADER 3에서 출발해 포인터를 따라가면 LEE는 여섯 번째 노드에서 찾으므로 비교 횟수는 6회이다.
탐색 경로: CHOI(3) → BAEK(4) → PARK(2) → KIM(1) → MIN(6) → LEE(5)
선형연결리스트는 순차 탐색만 가능하므로 인덱스 순서가 아니라 포인터 순서대로 비교한다.
- 비교 4회는 KIM까지만 비교한 경우이다.
- 비교 5회는 MIN까지만 비교한 경우이다.
- 비교 7회는 LEE를 지나 ANN까지 비교한 경우이다.
힙정렬은 배열로 표현한 완전 이진트리(complete binary tree)를 사용하므로, 포화 이진트리를 사용한다는 설명이 옳지 않다.
포화 이진트리는 모든 레벨이 꽉 찬 트리라 노드 수가 일 때만 성립하지만, 힙은 마지막 레벨이 왼쪽부터 채워진 완전 이진트리면 된다.
- 퀵정렬은 분할된 구간을 재귀 호출(스택)로 처리한다 — 옳다.
- 쉘정렬은 이미 정렬된 최선의 경우 수준으로, 입력과 무관하게 항상 인 선택정렬보다 빠르다 — 옳다.
- 10개 데이터의 버블정렬 최대 비교 횟수는 9+8+…+1 = 45이다 — 옳다.
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 12 | 9 | 3 | 10 | 5 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 12 | 3 | 10 | 5 | 9 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 9 | 10 | 3 | 12 | 5 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 9 | 3 | 10 | 5 | 12 |
선형탐색으로 충돌을 해결하면 해시테이블은 [2]=9, [3]=3, [4]=10, [5]=5, [6]=12가 된다.
3 → 3 mod 7 = 3, [3]에 저장
10 → 10 mod 7 = 3, 충돌 → 다음 빈 칸 [4]에 저장
5 → 5 mod 7 = 5, [5]에 저장
9 → 9 mod 7 = 2, [2]에 저장
12 → 12 mod 7 = 5, 충돌 → [6]에 저장
- 12를 [0], 9를 [1]에 둔 테이블은 9의 해시값 2와 12의 다음 빈 칸 [6]을 무시했다.
- 12를 [0], 9를 [6]에 둔 테이블은 9가 비어 있는 [2]에 바로 들어가야 함을 무시했다.
- 10을 [2], 12를 [4]에 둔 테이블은 충돌 시 다음 칸으로 이동하는 선형탐색 규칙에 어긋난다.
5를 찾으려면 23 → 18 → 2 → 16 → 4 → 10 → 5 순으로 7회 비교가 필요하다.
삽입 결과 23의 왼쪽 18, 18의 왼쪽 2, 2의 오른쪽 16, 16의 왼쪽 4, 4의 오른쪽 10, 10의 왼쪽 5가 연결되어 한쪽으로 길게 늘어진 편향된 경로가 생긴다.
- 비교 3회는 2까지만 내려간 경우이다.
- 비교 5회는 4까지만 내려간 경우이다.
- 비교 9회는 루트에서 5까지의 경로 길이보다 많아 성립하지 않는다.

Kruskal 알고리즘으로 만든 최소 비용 신장 트리의 비용은 13이다.
정점 6개이므로 간선 5개가 필요하다. 가중치가 작은 간선부터 사이클이 생기지 않는 것만 고르면 1 → 2 → 2를 채택하고, 가중치 3인 간선은 이미 연결된 두 정점을 잇는 사이클이 되어 버린다. 이어서 가중치 4인 간선 두 개를 채택하면 모든 정점이 연결된다.
- 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
- 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
- 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.

키 6을 넣으면 분할이 루트까지 전파되어 높이가 늘고, 전체 노드는 7개가 된다.
6은 오른쪽 리프 [7, 9]에 들어가 [6, 7, 9]로 넘치므로 분할되고 가운데 키 7이 부모로 올라간다. 루트가 [2, 4, 7]로 다시 넘쳐 분할되며 4가 새 루트가 된다.
결과: 루트 [4] / 내부 노드 [2], [7] / 리프 [1], [3], [6], [9] → 1 + 2 + 4 = 7개.
- 4개: 삽입 전 노드 수 그대로이며, 리프가 넘쳐 분할되는 것을 반영하지 않았다.
- 5개: 리프 분할만 반영하고 루트 분할을 빠뜨린 경우다.
- 6개: 루트 분할은 반영했으나 새 루트 노드 생성을 세지 않은 경우다.
typedef struct {
int exp;
float coef;
} poly;0이 아닌 항만 (exp, coef) 쌍으로 저장하는 희소 다항식 표현을 쓰면 최소 메모리는 36 byte이다.
poly 하나의 크기: int 2 byte + float 4 byte = 6 byte
A(x)의 항 3개 + B(x)의 항 3개 = 6개
6 × 6 = 36 byte
- 22 byte는 poly 6개(36 byte)를 담기에 부족하다.
- 24 byte는 poly 4개 분량에 불과하다.
- 38 byte는 36 byte에 int 하나(2 byte)를 더 쓴 값으로 최소가 아니다.
하노이 탑의 원판 이동 횟수는 로 지수 시간이므로 시간복잡도가 가장 크다.
원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 , 즉 이다.
- 선택정렬은 로 다항 시간이다.
- 정렬된 배열의 이진탐색은 이다.
- 반복문으로 피보나치 수를 구하면 이다.

x->next->next = y->next->next;
y->next->next = tmp;
tmp = y->next;
x->next = y->next;
y->next = tmp;
x->next->next = y->next->next;
y->next->next = tmp;
tmp = x->next;
x->next = y->next;
y->next = tmp;
x->next = y->next;
y->next = tmp;
tmp = x->next;
x->next->next = y->next->next;
y->next->next = tmp;
y->next->next = tmp;
x->next->next = y->next->next;
tmp = x->next;
y->next = tmp;
x->next = y->next;
음영 노드를 바꾸려면 음영 노드의 next(뒤 연결)를 먼저 교환하고, 그다음 x->next와 y->next를 교환해야 한다. 즉 tmp = x->next->next로 시작해 뒤 연결을 맞바꾼 뒤 tmp = x->next로 앞 연결을 맞바꾸는 코드가 옳다.
뒤 연결을 먼저 바꾸면 각 음영 노드가 상대 리스트의 세 번째 노드를 가리키게 되고, 이후 앞 연결을 바꾸면 x와 y 리스트에 상대 음영 노드가 끼워져 교환이 완성된다.
- tmp = x->next로 시작하는 코드: y->next->next에 x의 음영 노드 자체를 넣어 x의 세 번째 노드 연결을 잃는다.
- 앞 연결(x->next, y->next)을 먼저 교환하는 코드: 이후 x->next가 이미 y의 음영 노드를 가리키므로 뒤 연결 교환이 어긋나, y 리스트가 x의 음영 노드·y의 음영 노드·x의 세 번째 노드 순으로 이어지고 y의 세 번째 이후 노드를 잃는다.
- y->next->next = tmp를 먼저 대입하는 코드: y의 세 번째 노드 주소를 저장 없이 덮어써 y 쪽 뒤 리스트를 잃는다.