int function(int n)
{
if (n <= 1) return 1;
if (n % 2 == 0)
return n * function(n-1);
else
return n * function(n-3);
}
function(9)의 반환값은 540이다.
9는 홀수이므로 9×function(6), 6은 짝수이므로 6×function(5), 5는 홀수이므로 5×function(2), 2는 짝수이므로 2×function(1)로 이어지고, n ≤ 1이면 1을 반환하며 재귀가 끝난다.
되돌아오며 곱하면 function(2)=2, function(5)=5×2=10, function(6)=6×10=60, function(9)=9×60=540이다.

후위 순회 결과를 G D H B F E I C A 로 적은 것이 옳지 않다. 실제 후위 순회는 G D H B F I E C A이다.
트리는 A의 왼쪽에 B(왼쪽 G, 오른쪽 H), H의 오른쪽에 D가 있고, A의 오른쪽에 C, C의 오른쪽에 E(왼쪽 F, 오른쪽 I)가 있다. 후위 순회는 왼쪽→오른쪽→루트 순이므로 E 서브트리는 F, I, E 순서로 방문해야 하는데, 해당 보기는 E를 I보다 먼저 적었다.
- 전위 순회(루트→왼쪽→오른쪽): A B G H D C E F I 로 옳다.
- 중위 순회(왼쪽→루트→오른쪽): G B H D A C F E I 로 옳다.
- 레벨 순서 순회(깊이별 왼쪽부터): A / B C / G H E / D F I 이므로 A B C G H E D F I 로 옳다.
| [0] | [1] | [2] | [3] | |
|---|---|---|---|---|
| [0] | 0 | 5 | 1 | 2 |
| [1] | 5 | 0 | ∞ | 4 |
| [2] | 1 | ∞ | 0 | 3 |
| [3] | 2 | 4 | 3 | 0 |
최소 비용 신장 트리의 비용은 7이다.
간선을 가중치 순으로 나열하면 (0,2)=1, (0,3)=2, (2,3)=3, (1,3)=4, (0,1)=5이고, 정점 1과 2 사이는 ∞이므로 간선이 없다. 크루스칼 알고리즘으로 사이클이 생기지 않는 간선만 고른다.
- (0,2)=1과 (0,3)=2를 차례로 선택한다.
- (2,3)=3은 정점 0을 거쳐 이미 연결되어 사이클이 생기므로 제외한다.
- (1,3)=4를 선택하면 정점 4개를 간선 3개로 모두 잇게 되어 완성된다.
합계는 1+2+4=7이다.
최대 높이와 최소 높이의 차이는 72이다.
간선이 78개이면 노드 수는 간선 수+1인 79개이다. 최대 높이는 노드가 한 줄로 이어진 편향 트리일 때로 79이다.
최소 높이는 완전 이진 트리 형태일 때로, 높이 h의 최대 노드 수 이 79 이상이 되는 최소 h를 찾는다.
이므로 최소 높이는 7이다.
따라서 차이는 79-7=72이다.
옳지 않은 비교 순서는 926, 87, 813, 318, 572, 826, …으로 이어지는 순서이다.
이진 탐색 트리에서는 비교할 때마다 탐색 범위가 좁아지므로, 이후 비교되는 값은 항상 지금까지의 하한과 상한 사이에 있어야 한다.
- 926, 87, 813, … 순서: 629가 813보다 작아 왼쪽으로 내려갔으므로 이후 값은 813보다 작아야 하는데 826이 나와 모순이다.
- 19, 929, 172, … 순서: 범위가 (19, 929) → (172, 929) → (172, 891) → … → (537, 674)로 일관되게 좁아져 가능하다.
- 876, 807, 24, … 순서: 범위가 (24, 807) → … → (512, 690)으로 좁아지며 모든 값이 범위 안에 있어 가능하다.
- 29, 829, 815, … 순서: 범위가 (29, 815) → … → (589, 692)로 좁아지며 모순이 없어 가능하다.
옳은 실행 순서는 new→link = p; p = p→link; p→link = new; new→link→link = NULL;이다.
처음 리스트를 A→B라 하면 목표는 B→new→A이고 p는 B를 가리켜야 한다. 이 순서는 new가 A를 가리키게 한 뒤 p를 B로 옮기고, B가 new를 가리키게 한 다음 A의 link를 NULL로 만들어 완성한다.
- p→link = new 로 시작하는 순서: A의 link를 먼저 덮어써 B의 주소를 잃는다.
- p = p→link; p→link = new; new→link = p 순서: new가 A가 아닌 B를 가리키게 되어 A가 리스트에서 빠진다.
- new→link = p; p→link = new 로 시작하는 순서: A의 link를 new로 바꿔 B의 주소를 잃는다.
| 입력 | 21 | 41 | 15 | 25 | 21 | 37 | 45 | 9 | 23 | 18 | 36 | 4 | 11 |
| ㉠ | 9 | 15 | 21 | 21 | 25 | 37 | 41 | 45 | 23 | 18 | 36 | 4 | 11 |
| ㉡ | 4 | 9 | 11 | 15 | 18 | 37 | 45 | 41 | 23 | 21 | 36 | 21 | 25 |
| ㉢ | 15 | 21 | 21 | 25 | 37 | 41 | 45 | 9 | 18 | 23 | 4 | 11 | 36 |
| ㉣ | 4 | 9 | 11 | 25 | 21 | 37 | 45 | 41 | 23 | 18 | 36 | 21 | 15 |
| 결과 | 4 | 9 | 11 | 15 | 18 | 21 | 21 | 23 | 25 | 36 | 37 | 41 | 45 |
각 행은 차례로 삽입정렬, 선택정렬, 합병정렬, 퀵정렬의 중간 과정이다.
㉠은 앞의 8개만 정렬되어 있고 나머지는 입력 순서 그대로여서 정렬 구간을 하나씩 넓혀 가는 삽입정렬이다. ㉢은 정렬된 구간 3개(15~45의 7개, 9·18·23, 4·11·36)로 나뉘어 있어 부분 리스트를 정렬한 뒤 합치는 합병정렬이다.
㉡과 ㉣은 모두 최솟값을 앞으로 교환하는 선택정렬로 만들 수 있지만, ㉣은 맨 오른쪽 11을 피봇으로 분할한 결과(11 왼쪽에 4·9, 오른쪽에 더 큰 값)와도 같다. ㉡은 퀵정렬로 만들 수 없으므로 ㉡이 선택정렬, ㉣이 퀵정렬이다.
- ㉡을 퀵정렬로 보는 나열: 18이 제자리에 오려면 그보다 먼저 남은 구간의 피봇 25가 제자리로 옮겨져야 하는데 ㉡에서는 25가 맨 끝에 남아 있다.
- ㉠을 합병정렬로 보는 나열: 앞 8개만 정렬되고 나머지가 입력 그대로인 형태는 합병정렬의 분할·병합으로 나오지 않는다.
- ㉢을 삽입정렬로 보는 나열: 뒤쪽 원소 9·18·23과 4·11·36이 입력과 다른 순서로 각각 정렬되어 있어 삽입정렬의 중간 결과가 아니다.





삽입 후 트리는 루트 G, 그 아래 D·I, 다시 그 아래 C·E·H·K, 단말 노드 [A B][C][D][E F][G][H][I J][K L]인 높이가 한 단계 늘어난 구조가 된다.
F는 단말 [D E]에 들어가 [D E F]로 넘치므로 [D][E F]로 분할되고 E가 부모 [C D]로 올라간다. 부모 [C D E]도 넘쳐 D가 루트로 올라가 루트는 [D G]가 된다. I는 단말 [H]에 들어가 [H I]가 된다.
J는 [H I]에 들어가 [H I J]가 되어 [H][I J]로 분할되고 I가 부모 [H K]로 올라간다. [H I K]는 [H][K]로 나뉘며 I가 루트로 올라가고, 루트 [D G I]도 넘쳐 G를 새 루트로 하여 [D][I]로 분할된다.
- 루트가 G 하나이고 내부 노드가 [C E], [I K]로 남은 그림은 내부 노드 분할을 반영하지 않아 차수 3(키 최대 2개) 조건과 맞지 않는다.
- 단말에 [H I][J]가 생긴 그림은 중간값을 왼쪽 노드에 둔 것으로, 중간값을 오른쪽 노드에 포함한다는 조건에 어긋난다.
- 단말은 [I J][K L]인데 그 위 내부 노드를 J로 둔 그림은, 오른쪽 단말의 첫 키 K가 구분 키가 되어야 하므로 틀렸다.

그림의 최대 힙(배열 70, 50, 60, 10, 20, 30, 40)을 만드는 삽입 순서는 50, 60, 30, 10, 20, 70, 40이다.
50 다음 60이 들어오면 위로 교환되어 [60, 50]이 되고, 30·10·20은 부모보다 작아 그대로 붙어 [60, 50, 30, 10, 20]이 된다. 70은 30의 자식 자리에 들어가 30, 60과 차례로 교환되어 루트가 되고, 마지막 40은 부모 60보다 작아 그대로 남아 그림과 같아진다.
- 50, 30, 40, 70, 60, 10, 20 순서는 70, 60이 왼쪽으로 올라가 [70, 60, 40, 30, 50, 10, 20]이 되어 다르다.
- 10, 60, 50, 70, 20, 30, 40 순서는 [70, 60, 50, 10, 20, 30, 40]이 되어 루트의 왼쪽 자식이 60이므로 다르다.
- 10, 20, 40, 30, 60, 50, 70 순서는 [70, 40, 60, 10, 30, 20, 50]이 되어 다르다.

| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | ∞ |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 4 | 0 |
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | 5 |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 4 | 0 |
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | 5 |
| [1] | 3 | 0 | 2 |
| [2] | 1 | 4 | 0 |
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | ∞ |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 5 | 0 |
플로이드 알고리즘으로 정점 V(0), V(1)까지 경유를 허용한 D^1은 0행이 0, 3, 5 / 1행이 6, 0, 2 / 2행이 1, 4, 0인 행렬이다.
그래프의 간선은 V(0)→V(1) 3, V(1)→V(0) 6, V(1)→V(2) 2, V(2)→V(0) 1, V(2)→V(1) 5이며, 이것이 초기 행렬 D^-1이다.
D^0(V(0) 경유):
D^1(V(1) 경유): ,
- [0][2]가 ∞이고 [2][1]이 4인 행렬은 V(0)만 경유한 D^0이다.
- [0][2]가 ∞이고 [2][1]이 5인 행렬은 경유 없는 초기 행렬 D^-1이다.
- [1][0]이 3인 행렬은 V(2)까지 경유(6 대신 2+1)한 D^2로, D^1 단계에서는 아직 반영되지 않는다.
typedef struct node {
int key;
struct node *link;
} StackNode;
StackNode *top = NULL;
void push(int data) {
StackNode *tmp = (struct node*)malloc(sizeof(StackNode));
if (tmp == NULL) {
printf("Memory allocation is failed.\n");
exit(1);
}
tmp→key = data;
if (top == NULL) {
tmp→link = NULL;
top = tmp;
}
else {
( ㉠ );
( ㉡ );
}
}㉠ ㉡㉠은 tmp→link = top, ㉡은 top = tmp이다.
연결 스택의 삽입은 새 노드를 맨 앞에 붙이는 것이므로, 먼저 새 노드가 기존 첫 노드를 가리키게 한 뒤 top을 새 노드로 옮긴다.
- top→link = tmp, tmp = top→link 짝: 새 노드를 기존 top 뒤에 붙여 top이 바뀌지 않고, 기존 두 번째 노드 이후가 끊긴다.
- top→link = tmp, tmp = top 짝: 역시 기존 top 뒤에 새 노드를 붙여 나머지 노드가 끊기고, tmp만 바뀔 뿐 top은 그대로이다.
- tmp→link = top, top = tmp→link 짝: tmp→link가 기존 top이므로 top이 그대로 남아 새 노드가 스택에 들어가지 않는다.
옳은 설명은 키가 9인 노드와 16인 노드가 형제라는 것이다.
12, 14, 9, 16을 넣은 뒤 19를 삽입하면 14에서 RR 불균형이 생겨 회전하고, 이어 11을 넣으면 T는 루트 12, 왼쪽 자식 9(오른쪽 자식 11), 오른쪽 자식 16(자식 14, 19)인 높이 3의 트리가 된다. 9와 16은 모두 루트 12의 자식이다.
- 25를 삽입하는 경우: 19의 오른쪽에 붙어 루트의 균형 인수가 -1이 될 뿐 회전이 없으므로 루트는 12 그대로이다.
- 9를 삭제하는 경우: 자식 11이 그 자리를 대신하고 12-16-14 경로가 남으므로 높이는 3 그대로이다.
- 7을 삽입하는 경우: 9의 왼쪽에 붙어 왼쪽 서브트리 높이가 2로 유지되므로 T의 높이는 늘지 않는다.
void testing(int n)
{
int i, j, sum = 0;
for (i = 0; i < n; i++)
for (j = n; j > 1; j /= 2)
sum += 1;
}
시간 복잡도는 O(n log n)이다.
바깥 반복문은 i가 0부터 n-1까지 n회 돈다. 안쪽 반복문은 j를 n에서 시작해 1보다 클 동안 절반씩 줄이므로 약 log n회 돈다. 전체 실행 횟수는 두 횟수의 곱인 약 n·log n이다.
- O(n): 안쪽 반복의 log n배를 빠뜨린 결과이다.
- : 안쪽 반복이 n회일 때의 결과인데, j는 1씩이 아니라 절반씩 줄어든다.
- O(log n): 바깥 반복의 n회를 빠뜨린 결과이다.
typedef struct node {
int key;
struct node *link;
} list_node;
int length(list_node *ptr) {
list_node *temp;
int count = 0;
if ( ㉠ ) {
temp = ptr;
do {
count++;
( ㉡ );
} while ( ㉢ );
}
return count;
}㉠ ㉡ ㉢㉠은 ptr != NULL, ㉡은 temp = temp→link, ㉢은 temp != ptr이다.
리스트가 비어 있지 않을 때만 세기 시작하고, temp를 한 칸씩 옮기며 개수를 센 뒤 temp가 다시 시작 노드 ptr로 돌아오면 한 바퀴를 돈 것이므로 멈춘다.
- ptr == NULL, temp = temp→link, temp == ptr 짝: 빈 리스트일 때만 반복에 들어가 NULL을 역참조하고, 비어 있지 않으면 0을 반환한다.
- ptr != NULL, ptr = temp→link, temp != ptr 짝: temp는 움직이지 않고 ptr만 다음 노드로 바뀌어 노드가 2개 이상이면 무한 반복한다.
- ptr == NULL, ptr = temp→link, temp == ptr 짝: 빈 리스트일 때만 진입해 NULL 역참조가 일어난다.
ㄴ. p→rlink→llink = p→llink;
ㄷ. p→llink→rlink = new_node;
ㄹ. new_node→rlink = p;
ㅁ. p = new_node;
ㅂ. new_node→llink = p→llink;
ㅅ. p→llink = new_node;
올바른 순서는 ㄷ → ㄹ → ㅂ → ㅅ이다.
p의 왼쪽 노드를 L이라 하면 ㄷ으로 L의 오른쪽 링크를 new_node로, ㄹ로 new_node의 오른쪽 링크를 p로, ㅂ으로 new_node의 왼쪽 링크를 L로 잇고, 마지막에 ㅅ으로 p의 왼쪽 링크를 new_node로 바꾼다. p→llink를 바꾸는 ㅅ이 맨 뒤에 와야 앞 단계들이 p→llink로 L에 접근할 수 있다.
- ㄱ → ㄴ: p가 가리키는 노드를 리스트에서 떼어 내는 삭제 연산이다.
- ㅂ → ㅅ → ㄷ → ㄹ: ㅅ 이후 p→llink가 이미 new_node이므로 ㄷ이 new_node 자신의 오른쪽 링크를 바꾸게 되어 L의 링크가 갱신되지 않는다.
- ㄷ → ㅂ → ㄹ → ㅁ: p의 왼쪽 링크를 new_node로 바꾸는 단계가 없고, 포인터 p만 new_node로 옮길 뿐이다.
int Q[8] = {0};
int front = 0;
int rear = 0;
void enqueue(int item)
{
rear = (rear + 1) % 8;
if (front == rear) {
printf("Queue is full.\n");
return;
}
Q[rear] = item;
}
int dequeue()
{
int item;
if (front == rear) {
printf("Queue is empty.\n");
exit(1);
}
else {
front = (front + 1) % 8;
item = Q[front];
Q[front] = 0;
return item;
}
}front와 rear의 값이 0인 공백 큐에 6개의 값 1, 3, 2, 4, 8, 6을 차례대로 삽입하고, 여기에서 2개의 값을 삭제한 다음, 다시 3개의 값 5, 7, 9를 차례대로 삽입할 때, 배열 Q의 최종 모습은?| Q[0] | Q[1] | Q[2] | Q[3] | Q[4] | Q[5] | Q[6] | Q[7] |
|---|
| 0 | 7 | 9 | 2 | 4 | 8 | 6 | 5 |
| 2 | 4 | 8 | 6 | 5 | 7 | 9 | 0 |
| 7 | 9 | 0 | 2 | 4 | 8 | 6 | 5 |
| 9 | 0 | 2 | 4 | 8 | 6 | 5 | 7 |
배열 Q의 최종 모습은 7, 9, 0, 2, 4, 8, 6, 5이다.
enqueue는 rear를 먼저 1 증가시킨 뒤 저장하므로 1, 3, 2, 4, 8, 6은 Q[1]~Q[6]에 들어가고 rear=6이 된다. dequeue 2회로 front가 2가 되며 Q[1], Q[2]는 0으로 지워진다.
이어서 5는 Q[7], 7은 (7+1)%8=0이므로 Q[0], 9는 Q[1]에 저장된다. 이때 rear=1, front=2로 가득 찬 상태가 아니다.
- 0, 7, 9, 2, …, 5 배치: 7과 9를 지워진 칸 Q[1], Q[2]에 넣은 것으로, rear는 7 다음 0으로 이어진다.
- 2, 4, 8, 6, 5, 7, 9, 0 배치: 원소를 앞으로 당겨 저장한 것으로, 원형 큐는 원소를 이동시키지 않는다.
- 9, 0, 2, …, 7 배치: Q[0]부터 저장을 시작했다고 본 것으로, 이 구현은 rear를 먼저 증가시켜 Q[1]부터 저장한다.
int main()
{
int a[3][4] = {{10, 15, 20, 25}, {30, 35, 40, 45},
{50, 55, 60, 65}};
printf("a+1 = %d, ", a+1);
printf("*(*a+2) = %d, ", *(*a+2));
printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
return 0;
}
출력은 a+1 = 2293536, *(*a+2) = 20, *(*(a+1)+2) = 40이다.
a는 원소가 int[4]인 2차원 배열이므로 a+1은 행 하나(4×4=16바이트)만큼 증가해 2293520+16=2293536이다. *a는 a[0]의 시작 주소이므로 *(*a+2)는 a[0][2]=20이고, *(a+1)은 a[1]의 시작이므로 *(*(a+1)+2)는 a[1][2]=40이다.
- 2293521, 50, 55 출력: 주소를 1바이트 단위로 증가시키고 원소도 다른 행에서 읽은 값이다.
- 2293521, 20, 40 출력: 원소 값은 맞지만 포인터 연산은 가리키는 대상(행) 크기 단위로 증가하므로 1만 늘지 않는다.
- 2293536, 50, 55 출력: 주소는 맞지만 *a+2는 a[0] 행 안에서 int 2개만큼 이동한 a[0][2]를 가리키므로 50이 될 수 없다.
| [0] | [1] | [2] | [3] | |
|---|---|---|---|---|
| [0] | 0 | 1 | 1 | 1 |
| [1] | 1 | 0 | 1 | 0 |
| [2] | 1 | 1 | 0 | 0 |
| [3] | 1 | 0 | 0 | 0 |
간선이 1개 이상인 연결 부분 그래프는 14개이다.
인접행렬에서 간선은 (0,1), (0,2), (0,3), (1,2)의 4개이다. 부분 그래프가 연결이려면 고른 간선들이 하나로 이어져 있어야 하므로 간선 수별로 센다.
- 간선 1개: 4가지 모두 연결이다.
- 간선 2개: 6가지 중 공통 정점이 없는 (0,3)과 (1,2) 조합만 끊어져 5가지이다.
- 간선 3개: 4가지 모두 연결이다.
- 간선 4개: 1가지이다.
합계는 4+5+4+1=14이다.
나타날 수 없는 순서는 92, 3, 33, 129, 308, 506, 841이다.
기수 정렬은 일의 자리부터 안정적으로 분배·수집하므로 각 단계의 결과는 다음과 같다.
- 일의 자리 기준: 841, 92, 3, 33, 506, 308, 129로 나타날 수 있다.
- 십의 자리 기준: 3, 506, 308, 129, 33, 841, 92로 나타날 수 있다.
- 백의 자리 기준: 3, 33, 92, 129, 308, 506, 841로 최종 결과이다.
92, 3, 33, … 순서는 처음 입력을 백의 자리만으로 분배한 결과로, 일의 자리부터 처리하는 기수 정렬의 어느 단계에서도 나오지 않는다.
행렬 의 0이 아닌 원소 를 열 우선(column major) 순서로 배열 A에 저장한다고 할 때, 0이 아닌 원소 가 배열 A에 저장되는 위치를 계산하는 수식으로 옳은 것은? (단, 배열 A의 시작주소는 이고, 행렬 의 0인 원소는 배열에 저장하지 않는다)
저장 위치 식은 이며, 열 우선 순서에서 각 열의 0이 아닌 원소 개수로 구한다.
첫 열에는 원소가 2개, 나머지 열에는 3개씩 있으므로 j열 앞에 저장된 원소 수는 이다. j열 안에서는 행 j-1, j, j+1 순으로 저장되어 열 안 오프셋이 이므로 위치는 이다.
검산: 의 위치가 각각 로 맞는다.
- 를 더하는 식: 의 위치가 이 되어 성립하지 않는다.
- 를 더하는 식: 의 위치가 이 되어 성립하지 않는다.
- 를 더하는 식: 행 우선 순서로 저장할 때의 위치 식이다.