D2: 4, 2, 6, 8, 5, 3, 7 → 이진 탐색 트리 T2
D3: 4, 6, 3, 8, 2, 5, 7 → 이진 탐색 트리 T3
D4: 4, 6, 8, 5, 7, 2, 3 → 이진 탐색 트리 T4
모양이 다른 트리는 T3이다.
이진 탐색 트리의 모양은 각 키가 들어갈 때 이미 있는 조상 노드와의 대소 관계로 정해진다. 루트 4의 왼쪽 부분에서 T1·T2·T4는 2가 먼저 들어가 2의 오른쪽 자식이 3이 되지만, T3는 3이 먼저 들어가 3의 왼쪽 자식이 2가 된다.
- T1(D1): 루트 4, 왼쪽 2(오른쪽 자식 3), 오른쪽 6(왼쪽 5, 오른쪽 8), 8의 왼쪽 자식 7인 구조이다.
- T2(D2): 삽입 순서만 다를 뿐 모든 키의 부모가 T1과 같아 같은 모양이다.
- T4(D4): 오른쪽 키(6, 8, 5, 7)를 먼저 넣고 2, 3을 나중에 넣어도 부모 관계가 T1과 같아 같은 모양이다.

옳지 않은 것은 노드 C가 노드 D보다 작아야 한다는 설명이다.
최소 힙은 부모 키 ≤ 자식 키라는 조건만 만족하면 되므로, C와 D처럼 서로 다른 서브트리에 있는 노드 사이에는 크기 관계가 정해지지 않는다.
- 완전 이진 트리 — 힙은 완전 이진 트리 형태로 유지되므로 옳다.
- 루트 A의 최솟값 — 모든 노드의 조상인 루트가 가장 작은 키를 가지므로 옳다.
- B와 C의 동일 키 — 형제 노드끼리는 제약이 없어 같은 키를 가질 수 있으므로 옳다.
| [0] | [1] | [2] | [3] | [4] | |
|---|---|---|---|---|---|
| [0] | 0 | 1 | 0 | 0 | 0 |
| [1] | 0 | 0 | 1 | 1 | 0 |
| [2] | 0 | 0 | 0 | 0 | 1 |
| [3] | 0 | 0 | 0 | 0 | 1 |
| [4] | 0 | 1 | 0 | 0 | 0 |
주어진 그래프는 사이클이 존재하는 방향 그래프이다.
행렬이 대칭이 아니므로 방향 그래프이고, 간선은 0→1, 1→2, 1→3, 2→4, 3→4, 4→1의 6개이다. 이 중 1→2→4→1(또는 1→3→4→1)이 사이클을 이룬다.
- 간선 5개인 무방향 그래프: 행렬이 비대칭인 방향 그래프이고 간선도 6개이다.
- 정점 0에서 정점 4까지 단순 경로 길이 2: 0→1→2→4 또는 0→1→3→4로 길이가 3이다.
- 정점 3에 도달할 경로가 없는 정점: 0→1→3, 2→4→1→3, 4→1→3처럼 모든 정점이 정점 1을 거쳐 정점 3에 도달한다.

Kruskal 알고리즘으로 구한 최소 비용 신장 트리의 비용은 39이다.
가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 버린다. A-B(2), A-C(3), C-D(4), D-G(4)를 고른 뒤 B-D(5)는 A-B-D-C 사이클을 만들어 제외한다.
이어서 G-I(5), D-H(6), B-E(7), H-F(8)를 고르면 정점 9개에 간선 8개가 되어 완성된다.
- 36 — 최소 합 39보다 작아, 사이클 없이 9개 정점을 모두 잇는 방법으로는 얻을 수 없다.
- 44 — D-G(4) 대신 E-G(9)로 G를 연결한 신장 트리의 비용으로, 최소가 아니다.
- 46 — 최소 비용보다 큰 값으로, 더 무거운 간선을 포함한 신장 트리의 비용이다.
후위 순회 결과는 1, 3, 5, 4, 2, 7, 8, 6이다.
전위 순회의 첫 키 6이 루트이고, 이진 탐색 트리이므로 6보다 작은 2, 1, 4, 3, 5는 왼쪽, 8, 7은 오른쪽 서브트리이다. 같은 방식으로 왼쪽은 2(왼쪽 1, 오른쪽 4(왼쪽 3, 오른쪽 5)), 오른쪽은 8(왼쪽 7)로 복원된다.
후위 순회는 왼쪽 → 오른쪽 → 루트 순이므로 1, 3, 5, 4, 2를 방문한 뒤 7, 8, 마지막에 루트 6을 방문한다.
- 1부터 8까지 오름차순: 이진 탐색 트리의 중위 순회 결과이다.
- 1, 3, 2, 6, 5, 8, 7, 4: 루트 6이 마지막에 오지 않아 후위 순회가 될 수 없다.
- 8부터 1까지 내림차순: 오른쪽 → 루트 → 왼쪽으로 도는 역방향 중위 순회 결과이다.
6이 저장된 노드와 18이 저장된 노드는 형제 관계이다.
차수 3인 B-트리는 노드당 키가 최대 2개이므로 키가 3개가 되면 가운데 키를 부모로 올려 분할한다. 2 삽입 때 18이, 6 삽입 때 6이 올라가 루트가 [6, 18]이 되고, 7 삽입 때 [7, 13, 15]에서 13이 올라가 루트 [6, 13, 18]이 다시 분할되면서 13이 새 루트가 된다.
최종 트리는 루트 13 아래 6과 18이 있고, 6의 자식은 2와 7, 18의 자식은 15와 19이다.
- 트리의 높이가 1: 루트 아래로 두 단계가 더 있는 3레벨 트리이므로 높이가 1이 아니다.
- 15가 루트에 저장: 루트에는 13만 있고 15는 리프에 있다.
- 자식 3개인 노드가 존재: 모든 내부 노드가 키 1개와 자식 2개만 가진다.
최종 결과 값은 0이고, 스택 내 피연산자의 최대 개수는 4이다.
9 1 − 로 8, 이어서 2 / 로 4가 되어 스택에는 4만 남는다. 다음에 1, 2, 1을 차례로 넣으면 스택이 [4, 1, 2, 1]로 피연산자 4개가 쌓여 최대가 된다.
이후 2 1 + 로 3, 1 3 * 로 3, 4 3 − 로 1, 마지막 1 1 − 로 0이 된다.
- 0 / 3: 결과 값은 맞지만 덧셈 직전에 피연산자 4개가 쌓인다.
- 1 / 3: 마지막 뺄셈 전의 중간 값이고 최대 개수도 4이다.
- 1 / 4: 최대 개수는 맞지만 마지막 뺄셈까지 수행하면 결과는 0이다.
| 주소 | 데이터 | 다음 노드 주소 |
|---|---|---|
| 100 | LEE | NULL |
| 101 | PARK | 104 |
| 102 | KIM | 101 |
| 103 | JUNG | 102 |
| 104 | SEO | 100 |
○ 주소가 100인 노드의 다음 노드 주소는 ( ㉠ )이다.
○ 주소가 101인 노드의 다음 노드 주소는 ( ㉡ )이다.
○ 주소가 103인 노드의 다음 노드 주소는 ( ㉢ )이다.
○ 주소가 104인 노드의 다음 노드 주소는 ( ㉣ )이다.
주소 102인 노드를 삭제하면 주소 103 노드의 다음 주소만 101로 바뀌므로 NULL / 104 / 101 / 100이 된다.
링크를 따라가면 리스트는 103(JUNG) → 102(KIM) → 101(PARK) → 104(SEO) → 100(LEE) → NULL 순서이다. 단순 연결 리스트의 삭제는 선행 노드의 링크를 삭제 노드의 다음 노드로 바꾸는 것이므로 나머지 링크는 그대로 유지된다.
- NULL / 103 / 101 / 104: 주소 101, 104 노드의 링크는 삭제와 무관해 바뀌지 않는다.
- 101 / 103 / 102 / 104: 마지막 노드(주소 100)는 NULL을 유지해야 하고, 주소 103 노드가 삭제된 노드를 계속 가리키게 된다.
- 101 / 104 / 102 / 100: 마지막 노드의 NULL을 바꾸었고, 주소 103 노드가 삭제된 노드를 계속 가리키게 된다.
#include <stdio.h>
int main()
{
struct human {
char sextype;
union t {
char children[3];
char beard[3];
} u;
int age;
struct date {
int month;
int day;
int year;
} dob;
int personalID;
float salary;
} h[10];
printf("%d, %d, %d", sizeof(struct human),
&h[3].u.children[0] - &h[0].sextype,
&h[5].u.beard[1] - &h[0].sextype);
}
출력 결과는 28, 85, 142이다.
int는 4의 배수 오프셋에 정렬되므로 sextype(1바이트)이 오프셋 0, 공용체 u(가장 큰 멤버 기준 3바이트)가 오프셋 1~3, age가 4, dob(12바이트)가 8~19, personalID가 20, salary가 24에 놓여 구조체 크기는 28바이트이다.
char 주소의 차는 바이트 거리이고, 공용체의 children과 beard는 같은 시작 주소를 공유한다.
- 28, 86, 143: 구조체 크기는 맞지만 u는 오프셋 1에서 시작하므로 차이는 85, 142이다.
- 31, 94, 157: 공용체를 두 멤버 크기의 합인 6바이트로 보고 정렬 패딩 없이 더한 크기(31바이트)로 계산한 값이다.
- 31, 95, 158: 구조체 크기를 잘못 본 데다 오프셋도 한 바이트씩 어긋난 값이다.
#include <stdio.h>
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void recursive(char *list, int i, int n) {
int j, temp;
if (i == n) {
for (j = 0 ; j <= n ; j++)
printf("%c", list[j]);
printf(" ");
}
else {
for (j = i ; j <= n ; j++) {
SWAP(list[i], list[j], temp);
recursive(list, i + 1, n);
SWAP(list[i], list[j], temp);
}
}
}
int main()
{
char list[3] = {'a', 'b', 'c'};
recursive(list, 0, 2);
}
출력 결과는 abc acb bac bca cba cab이다.
함수는 위치 i의 문자를 i부터 n까지의 문자와 차례로 교환하고 나머지 자리를 재귀로 처리한 뒤 다시 교환해 원상 복구하는 순열 생성 알고리즘이므로 3글자 순열 6개가 모두 출력된다.
첫 자리는 a(교환 없음) → b(0·1 교환, bac) → c(0·2 교환, cba) 순이고, 각 경우 둘째 자리 교환으로 abc·acb, bac·bca, cba·cab가 차례로 나온다.
- ab ac bc: i == n일 때 인덱스 0부터 n까지 세 글자를 출력하므로 두 글자 조합이 나올 수 없다.
- ab bc ca: 마찬가지로 두 글자 출력은 불가능하며 출력 개수도 6개이다.
- abc acb bca bac cab cba: b가 맨 앞으로 오면 bac가 먼저, c가 맨 앞으로 오면 abc에서 0·2를 교환한 cba가 먼저 출력된다.
다른 값을 갖는 것은 **((A + 3) + 1)로, A[4][0]의 값인 4가 된다.
A + 3은 3행을 가리키는 행 포인터이고 *(A + 3)은 A[3], *(A + 3) + 1은 A[3][1]의 주소이다. 반면 (A + 3) + 1은 행 단위로 한 번 더 이동한 A + 4이므로 두 번 역참조하면 A[4][0]이 된다.
- A[3][1]: 이다.
- *(*(A + 3) + 1): A[3][1]의 포인터 표기로 2이다.
- *(A[3] + 1): A[3] 행의 둘째 원소인 A[3][1]로 2이다.

최소 비용 12와 세 번째 간선 가중치 3을 더한 15가 답이다.
Prim 알고리즘은 현재 트리에 인접한 간선 중 최소 가중치를 하나씩 추가한다. A에서 A-B(2), 이어서 B-F(1), 그다음 후보 중 최소인 B-E(3)가 세 번째로 선택된다.
이후 E-D(2), 마지막으로 C를 잇는 B-C(4)를 고른다.
- 13 — 세 번째 간선을 1로 잘못 잡은 경우의 값이다.
- 14 — 세 번째 간선을 2로 잘못 잡은 경우의 값이다.
- 16 — 세 번째 간선을 4로 보거나 C를 C-F(5)로 연결한 경우의 값이다.

BFS 방문 순서는 A, C, D, E, G, I, B, H, F이다.
BFS는 큐를 사용해 가까운 정점부터 방문한다. A의 인접 정점 C, D, E를 알파벳 순으로 넣고, C에서 G, D에서 I, E에서 B와 H를 차례로 추가한다.
마지막으로 B에서 아직 방문하지 않은 F가 추가되어 탐색이 끝난다.
- A, C, D, E, I, G, … — C가 D보다 먼저 꺼내지므로 C의 이웃 G가 D의 이웃 I보다 앞서야 한다.
- A, C, D, G, B, … — E는 A와 직접 연결된 1단계 정점이므로 G보다 먼저 방문해야 한다.
- A, C, D, G, I, B, E, … — 역시 1단계 정점 E가 2단계 정점들보다 뒤에 놓여 BFS 순서가 아니다.

구성된 최대 힙의 리프 키 합은 108이다.
초기 힙 72, 35, 42에 각 키를 맨 끝에 넣고 부모보다 크면 교환하는 상향 조정을 반복한다. 49는 42와, 30은 2와, 41은 30·35와, 27은 14와 교환된다.
최종 배열은 72, 41, 49, 35, 27, 42, 3, 2, 30, 14, 17이고, 노드가 11개이므로 여섯째 위치부터 끝까지가 리프이다.
- 63 — 최종 리프 여섯 개의 합보다 작아, 리프 일부가 빠진 값이다.
- 73 — 상향 조정 결과와 다른 리프 구성에서 나오는 값이다.
- 113 — 최종 리프 합보다 커서, 리프가 아닌 노드의 키가 섞인 값이다.
○ 원형 큐는 원소 개수가 6개인 1차원 배열로 구현되었다.
○ front와 rear의 값이 같을 때 원형 큐는 공백 상태이다.
○ front와 ((rear + 1) mod 6)의 값이 같을 때 원형 큐는 포화 상태이다.
○ enqueue(x)에 의해 rear의 값을 ((rear + 1) mod 6)로 변경한 후 rear가 가리키는 위치에 데이터 x를 삽입한다. 단, 포화 상태일 때에는 데이터 삽입이 이루어지지 않아 원형 큐의 상태가 변하지 않는다.
○ dequeue()에 의해 front의 값을 ((front + 1) mod 6)로 변경한 후 front가 가리키는 위치에서 데이터를 빼내어 삭제한다. 단, 공백 상태일 때에는 데이터 삭제가 이루어지지 않아 원형 큐의 상태가 변하지 않는다.
enqueue(2) → enqueue(5) → enqueue(7) → enqueue(10) → dequeue() → enqueue(11) → enqueue(15) → enqueue(17) → dequeue() → dequeue() → enqueue(20)
연산 후 유효 데이터는 10, 11, 15, 20이고 front는 3, rear는 1이다.
enqueue(2), (5), (7), (10)으로 rear가 4, dequeue()로 front가 1이 된다. enqueue(11)로 rear가 5, enqueue(15)로 rear가 0으로 돌아온다.
이때 front와 (0 + 1) mod 6이 모두 1로 같아 포화 상태이므로 enqueue(17)은 무시된다. 이후 dequeue() 두 번으로 5와 7이 삭제되어 front가 3, enqueue(20)으로 rear가 1이 되어 위치 4, 5, 0, 1에 10, 11, 15, 20이 남는다.
- 10, 11, 15, 17, 20 / 3 / 1: 포화 상태에서 17은 삽입되지 않는다.
- 10, 11, 15, 17, 20 / 4 / 2: 17은 삽입되지 않으며 front는 3, rear는 1이다.
- 10, 11, 15, 20 / 4 / 2: 데이터는 맞지만 dequeue()가 세 번 수행되어 front는 3이고, 17이 무시되므로 rear는 1이다.
총 비교 횟수가 가장 많은 리스트는 이미 정렬된 1, 2, 3, 4, 5이다.
첫 레코드를 피봇으로 쓰면 정렬된 입력에서는 피봇이 항상 최솟값이 되어 한쪽이 비고 다른 쪽이 하나만 줄어드는 최악의 분할이 반복된다. 분할 한 번에 피봇을 나머지 원소와 비교한다고 보면 다음과 같다(구현에 따라 세부 횟수는 달라도 대소 순서는 같다).
- 2, 3, 1, 4, 5: 피봇 2로 [1]과 [3, 4, 5]로 나뉘어 회이다.
- 3, 1, 2, 4, 5: 피봇 3이 가운데 값이라 두 원소씩 균형 있게 나뉘어 회이다.
- 3, 1, 2, 5, 4: 마찬가지로 피봇 3으로 균형 분할되어 6회이다.
후위 순회 결과는 3, 4, 10, 15, 13, 12, 7이다.
10, 4, 7 삽입 시 LR 불균형이 생겨 7이 루트(왼쪽 4, 오른쪽 10)가 된다. 12, 3을 넣은 뒤 13을 넣으면 10에서 RR 불균형이 생겨 회전 후 12(왼쪽 10, 오른쪽 13)가 7의 오른쪽 자식이 된다.
마지막 15는 13의 오른쪽에 붙고 모든 노드의 균형 인수가 −1~1 범위라 회전이 없다. 이 트리를 왼쪽 → 오른쪽 → 루트 순으로 방문한다.
- 3, 7, 4, 12, 15, 13, 10: 회전 후 루트는 7이므로 마지막 방문 노드가 10일 수 없다.
- 3, 7, 4, 15, 13, 12, 10: 회전 없이 일반 이진 탐색 트리로 삽입했을 때의 결과이다.
- 3, 10, 13, 15, 4, 12, 7: 리프 3 다음에는 그 부모 4를 방문해야 하는데 10이 먼저 온다.
#include <stdio.h>
void func(char s[], int size) {
if (size <= 0) return;
s[size-1] = s[size-1] + 1;
func(s,size-2);
}
int main()
{
char str[] = "window";
func(str, 6);
printf("%c", str[3]);
}
출력 결과는 e이다.
func는 s[size-1]을 1 증가시킨 뒤 size를 2씩 줄여 재귀 호출하므로 size가 6, 4, 2일 때 인덱스 5, 3, 1의 문자가 바뀐다.
문자열 window에서 str[3]은 'd'이고, size가 4인 호출에서 1 증가해 'e'가 된다(str[5]는 'x', str[1]은 'j'로 함께 바뀐다).
- d: str[3]의 원래 문자로, 재귀 과정에서 1 증가하므로 그대로 남지 않는다.
- n: str[2]의 원래 문자이며 출력 대상이 아니다.
- o: str[4]의 원래 문자이며 출력 대상이 아니다.
void Largest2nd(int *arr, int n){
int i, max1 = 0, max2 = 0;
for (i = 0; i < n; i++){
if (___㉠___){
max2 = max1;
max1 = arr[i];
}
else if (_____㉡_____)
max2 = arr[i];
}
printf("Second Largest Number = %d\n", max2);
}㉠ / ㉡㉠은 arr[i] > max1, ㉡은 arr[i] > max2 && arr[i] < max1이다.
현재 값이 최댓값보다 크면 기존 최댓값을 max2로 내리고 max1을 갱신하므로 ㉠은 max1보다 큰 경우이다. 그렇지 않으면서 max2보다 크고 max1보다 작은 값일 때만 max2를 갱신해야 한다.
- arr[i] > max1 / arr[i] < max2 && arr[i] > max1: ㉠이 거짓이면 arr[i]가 max1 이하이므로 ㉡을 만족하는 값이 없어 max2가 갱신되지 않는다.
- arr[i] < max1 / arr[i] > max2 && arr[i] < max1: max1이 0에서 시작하고 원소가 모두 양수라 ㉠과 ㉡이 모두 거짓이 되어 0이 출력된다.
- arr[i] < max1 / arr[i] < max2 && arr[i] > max1: 두 조건 모두 성립하지 않아 max1, max2가 0에 머문다.
struct node {
int data;
struct node *link;
};
typedef struct node *node_ptr;
void InsertFront(node_ptr *last_ptr,
node_ptr insert_node){
if (*last_ptr == NULL) {
*last_ptr = insert_node;
_______㉠_______
}
else {
insert_node->link = (*last_ptr)->link;
_______㉡_______
}
}㉠ / ㉡㉠은 insert_node->link = insert_node;, ㉡은 (*last_ptr)->link = insert_node;이다.
빈 리스트에 노드 하나를 넣으면 그 노드가 처음이자 마지막이므로 자기 자신을 가리켜 원형을 이뤄야 한다. 원형 연결 리스트의 맨 앞 노드는 마지막 노드의 link가 가리키는 노드이므로, 새 노드가 기존 첫 노드를 가리키게 한 뒤 마지막 노드의 link를 새 노드로 바꾸면 맨 앞 삽입이 된다.
- insert_node = insert_node->link; / (*last_ptr) = insert_node;: ㉠은 포인터 변수만 바꿀 뿐 자기 순환을 만들지 못하고, ㉡은 마지막 노드의 link를 갱신하지 않아 새 노드가 순환에 들어가지 않는다.
- insert_node = insert_node->link; / (*last_ptr)->link = insert_node;: ㉡은 맞지만 ㉠이 노드의 link를 설정하지 않아 단일 노드 원형이 만들어지지 않는다.
- insert_node->link = insert_node; / (*last_ptr) = insert_node;: ㉠은 맞지만 ㉡이 last 포인터만 새 노드로 옮겨, 기존 마지막 노드가 여전히 옛 첫 노드를 가리키므로 원형이 깨진다.