수식의 계산 결과는 9이다.
후위 표기식은 스택으로 계산한다. 피연산자는 push 하고, 연산자를 만나면 두 값을 pop 해(먼저 꺼낸 값이 오른쪽 피연산자) 계산한 뒤 다시 push 한다.
2 3 + → 5
5 2 * → 10
2 1 + → 3
3 3 / → 1
10 1 - → 9
- 7은 나눗셈 3 / 를 빠뜨리고 10에서 3을 뺀 값이다.
- 8은 스택 계산의 어느 단계에서도 나오지 않는 값이다.
- 10은 마지막 뺄셈을 하기 전 스택 아래에 남아 있던 중간값이다.
마지막 레벨에는 50개의 노드가 있다.
완전 이진 트리는 마지막 레벨 직전까지 꽉 차 있다. 레벨 k까지의 노드 수는 이고 이므로, 레벨 1~7이 포화 상태이고 레벨 8이 마지막 레벨이다.
- 49는 로, 레벨 7까지의 노드 수를 128로 잘못 센 값이다.
- 78은 레벨 8의 최대 노드 수 128에서 50을 뺀 값, 즉 마지막 레벨의 빈 자리 수이다.
- 127은 레벨 7까지 포화된 노드 수로, 마지막 레벨 위쪽 전체의 노드 수이다.
#include <stdio.h>
void asterisk(int i)
{
if(i > 1){
asterisk(i/3);
asterisk(i/3);
}
printf("*");
}
asterisk(9)는 '*'를 7개 출력한다.
i > 1이면 asterisk(i/3)을 두 번 재귀 호출한 뒤 자신도 '*'를 1개 출력하고, i ≤ 1이면 '*'만 1개 출력한다. 출력 개수를 T(i)라 하면 T(i) = 2T(i/3) + 1이다.
T(1) = 1
T(3) = 2T(1) + 1 = 3
T(9) = 2T(3) + 1 = 7
- 6은 재귀 호출 수만 세고 최초 호출 asterisk(9) 자신의 출력을 빠뜨린 값이다.
- 8은 호출마다 '*'를 정확히 1개씩 출력하는데 전체 호출이 7회뿐이라는 점과 맞지 않는다.
- 9는 인자 값을 그대로 개수로 본 것으로, 출력 개수는 인자가 아니라 호출 횟수와 같다.
| 위치 | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] |
|---|---|---|---|---|---|---|---|---|
| 데이터 | 307 | 424 | 132 | 216 | 241 | 835 | 546 | 630 |
두 번째 자릿수 정렬 후 위치 [3]에는 630이 온다.
LSD 기수 정렬은 일의 자리부터 자릿수별로 안정 정렬을 반복하므로, 같은 자릿값끼리는 이전 단계의 순서를 유지한다.
일의 자리 정렬: 630, 241, 132, 424, 835, 216, 546, 307
십의 자리 정렬: 307, 216, 424, 630, 132, 835, 241, 546
십의 자리가 3인 630, 132, 835 중 앞 단계에서 먼저 있던 630이 위치 [3]에 놓인다.
- 546은 십의 자리 정렬 후 맨 마지막 위치 [7]에 있다.
- 132는 십의 자리가 630과 같지만 일의 자리 단계에서 630 뒤에 있었으므로 위치 [4]에 놓인다.
- 216은 십의 자리가 1이라 위치 [1]에 놓인다.
마지막 키 33은 HT[9]에 저장된다.
이차 조사법은 충돌 시 순서로 빈 자리를 찾는다.
51→7, 27→5, 70→4, 55→0, 13→2
2→2 충돌 → 3
37→4 충돌 → 5 충돌 → 8
23→1
33→0 충돌 → 1 충돌 → 4 충돌 → 9
- HT[1]은 33의 첫 조사 위치(0 + 1)로, 이미 23이 차지하고 있다.
- HT[4]는 그다음 조사 위치(0 + 4)로, 70이 차지하고 있다.
- HT[6]은 비어 있지만 33의 조사 순서(0, 1, 4, 9)에 들어가지 않는다.

BFS : A, B, C, D, E, G, F, H, I
BFS : A, B, D, E, C, G, F, H, I
BFS : A, B, D, E, C, G, F, H, I
BFS : A, B, C, D, E, G, F, H, I
DFS 방문 순서는 A, B, C, F, H, G, D, E, I, BFS 방문 순서는 A, B, D, E, C, G, F, H, I이다.
DFS는 알파벳 순으로 가장 앞선 미방문 인접 정점으로 계속 내려가므로 A→B→C→F→H→G→D→E로 진행하고, E에서 더 갈 곳이 없어 H까지 되돌아간 뒤 I를 방문한다.
BFS는 A의 인접 정점 B, D, E를 먼저 방문하고, 이어서 C(B에서), G(D에서), F(C에서), H(G에서), I(F에서) 순으로 방문한다.
- DFS가 G 다음에 E, D 순으로 방문한다는 순서: G의 미방문 인접 정점 중 알파벳 순으로 D가 E보다 앞서므로 D를 먼저 방문해야 한다.
- BFS가 A, B, C, D, E 순으로 진행한다는 순서: C는 A와 인접하지 않고 B를 거쳐 발견되므로, A와 직접 인접한 D, E보다 먼저 방문될 수 없다.
#include <stdio.h>
void main()
{
struct node {
int id;
char name[8];
int score;
} A[10];
printf("%d\n", &A[0]);
printf("%d\n", &A[4]);
}
두 출력 값의 차이는 64이다.
구조체 node 하나의 크기는 int 4 + char[8] 8 + int 4 = 16바이트이고, 모든 멤버가 4바이트 경계에 맞아 패딩이 생기지 않는다.
&A[4] − &A[0] = 4 × 16 = 64
- 56은 구조체 크기를 14바이트로 잘못 본 값이다.
- 72는 구조체 크기를 18바이트로 잘못 본 값이다.
- 80은 A[0]부터 A[4]까지 원소 5개 분량(5 × 16)으로 센 값으로, 주소 차이는 원소 4개 분량이다.

23을 삽입한 뒤 LR 회전으로 균형을 맞추면 전위 순회 결과는 27, 19, 7, 23, 30, 41이다.
23은 30의 왼쪽, 19의 오른쪽, 27의 왼쪽 자식으로 삽입된다. 이때 30의 균형 인수가 +2(왼쪽 높이 3, 오른쪽 높이 1)이고 그 왼쪽 자식 19의 균형 인수가 -1이므로 LR 불균형이다.
회전 결과 27이 루트가 되고, 왼쪽에 19(자식 7, 23), 오른쪽에 30(오른쪽 자식 41)이 놓인다. 이를 루트→왼쪽→오른쪽 순으로 방문한다.
- 30, 19, 7, 23, 41, 27: 루트가 30으로 그대로 남아 있어 회전으로 균형을 복구한 트리의 순회가 아니다.
- 30, 7, 19, 23, 27, 41: 역시 루트가 30으로 남아 있고, 전위 순회라면 7보다 부모인 19가 먼저 나와야 한다.
- 27, 19, 7, 30, 23, 41: 23은 27보다 작아 27의 왼쪽 서브트리(19의 오른쪽 자식)에 있으므로 30보다 먼저 방문되어야 한다.

Kruskal 알고리즘의 최소 비용은 44이고, 마지막으로 선택되는 간선은 (B, F)이다.
가중치가 작은 간선부터 사이클이 생기지 않으면 채택한다. 1(H, C), 2(I, G), 3(G, H)를 채택하고 4(I, H)는 사이클이 생겨 버린다. 이어서 5(H, E), 6(A, C), 7(A, B), 8(B, D)를 채택한다.
9(E, C), 10(D, A), 11(G, E)는 모두 사이클을 만들어 버리고, 12(F, B)를 채택하면 정점 9개에 간선 8개가 되어 종료한다.
- 최소 비용 43: 채택된 8개 간선 가중치의 합은 44이다.
- 마지막 간선 (G, E): G와 E는 이미 H를 통해 연결되어 있어 가중치 11인 이 간선은 사이클을 만들므로 채택되지 않는다.
| a | b | a | b | a | d | c | d | a | b | a | c | d | a | b | c | d | d | e |
압축된 문자열은 42비트를 사용한다.
문자별 빈도는 a 6, d 5, b 4, c 3, e 1이다. 허프만 트리는 빈도가 가장 작은 두 노드를 반복해 합친다.
e(1) + c(3) → 4
4 + b(4) → 8
d(5) + a(6) → 11
8 + 11 → 19
코드 길이는 a·b·d 2비트, c·e 3비트이므로 6×2 + 5×2 + 4×2 + 3×3 + 1×3 = 42
- 39는 42보다 짧은데, 허프만 코드는 접두어 코드 중 총 비트 수가 최소이므로 이보다 짧은 접두어 코드는 만들 수 없다.
- 44는 42보다 길어 최적 코드인 허프만 코드의 결과가 될 수 없다.
- 46도 42보다 길어 허프만 코드의 결과가 될 수 없다.
**((a+1)+2)만 a[3][0]을 가리키고, 나머지는 모두 a[1][2]를 나타낸다.
a+1은 1행을 가리키고 *(a+1)은 a[1](1행 첫 원소의 주소)이 되며, 여기에 +2를 하면 a[1][2]의 주소가 된다.
반면 (a+1)+2는 행 단위로 2를 더해 a+3, 즉 3행이 되고, 두 번 역참조하면 a[3][0]이 된다.
- *(*(a+1)+2)는 *(a[1]+2)와 같아 a[1][2]이다.
- *(a[1]+2)는 포인터 산술 정의상 a[1][2]이다.
- a[1][2]는 1행 2열 원소 그 자체이다.
int iterate(int n)
{
int i, count = 0;
for (i = 1; i < n; i *= 2)
count++;
return count;
}
시간 복잡도는 이다.
i는 1, 2, 4, 8, …처럼 매 반복 2배로 커지고 i < n 동안만 반복하므로, 반복 횟수는 이 되는 최소 k, 즉 이다.
- 은 i가 1씩 증가할 때의 반복 횟수이다.
- 은 로그 반복 루프를 바깥 루프가 n번 감쌀 때의 복잡도이며, 이 함수에는 바깥 루프가 없다.
- 은 선형 루프 두 개가 중첩될 때의 복잡도이다.
#include <stdio.h>
#include <stdlib.h>
struct student{
char name[20];
int id;
};
struct student *alloc()
{
struct student *p;
p = ㉠ ;
if(p==NULL){
printf("Memory allocation error.");
return p;
}
printf("Student name?\n");
gets(p->name);
printf("Student id?\n");
scanf("%d", ㉡ );
return p;
}
㉠에는 (struct student *)malloc(sizeof(struct student)), ㉡에는 &(p->id)가 들어간다.
malloc은 void * 를 반환하므로 p의 자료형인 구조체 포인터로 형변환해야 하고, 구조체 값 자료형 (struct student)로는 포인터를 변환할 수 없다. scanf의 %d는 정수를 저장할 주소를 받아야 하므로 id 멤버의 주소를 넘긴다.
- (struct student) 형변환과 &((*p).id) 조합은 ㉡은 맞지만, ㉠에서 포인터를 구조체 값 자료형으로 변환할 수 없다.
- (struct student *) 형변환과 p->id 조합은 ㉠은 맞지만, scanf에 주소가 아닌 정수 값을 넘긴다.
- (struct student) 형변환과 (*p).id 조합은 ㉠, ㉡ 모두 틀렸다.

위상 순서로 옳지 않은 것은 C, A, D, B, E, F이다.
그래프의 간선은 A→B, B→D, B→E, B→F, C→D, C→E, E→F이다. 위상 순서는 모든 간선 u→v에 대해 u가 v보다 앞서야 하는데, 이 순서는 B→D 간선이 있음에도 D가 B보다 먼저 나온다.
- A, B, C, D, E, F: 모든 간선의 선후 관계를 만족한다.
- C, A, B, E, D, F: 진입 차수가 0인 C, A가 먼저 오고 B 다음에 E, D, 마지막에 F가 와 모든 조건을 만족한다.
- A, C, B, E, D, F: A→B, C→D, C→E, B→D, B→E, E→F 조건을 모두 만족한다.
3, 1, 2, 4, 5 순서로 삽입할 때 트리 높이가 가장 낮다(3레벨).
이진 탐색 트리의 높이는 삽입 순서에 따라 달라지며, 루트가 중앙값에 가까울수록 좌우가 고르게 나뉜다. 3을 루트로 하면 왼쪽에 1-2, 오른쪽에 4-5가 각각 두 레벨로 달려 전체 3레벨이 된다.
- 1, 2, 3, 4, 5는 계속 오른쪽 자식으로만 이어져 5레벨의 편향 트리가 된다.
- 1, 3, 2, 4, 5는 1 → 3 → 4 → 5 경로가 생겨 4레벨이 된다.
- 4, 3, 5, 2, 1은 4 → 3 → 2 → 1 경로가 왼쪽으로 이어져 4레벨이 된다.

13 삽입 후 루트를 삭제하면 루트의 오른쪽 자식은 9가 된다.
삽입: 13은 마지막 위치인 9의 오른쪽 자식으로 들어간 뒤 부모와 비교해 올라간다. 13은 9, 10보다 크므로 두 번 교환되어 21의 왼쪽 자식이 된다(배열 21, 13, 18, 10, 5, 7, 3, 4, 9).
삭제: 루트 21을 제거하고 마지막 노드 9를 루트로 옮긴 뒤, 두 자식 13, 18 중 큰 18과 교환한다. 9는 새 자리의 자식 7, 3보다 크므로 멈춘다(배열 18, 13, 9, 10, 5, 7, 3, 4).
- 10: 삽입 과정에서 13에 밀려 왼쪽 서브트리 아래로 내려가며, 루트의 오른쪽 자식과는 무관하다.
- 13: 삭제 후 루트의 왼쪽 자식이다.
- 18: 삭제 후 새 루트가 된다.
○ 크기가 6이고 인덱스가 0부터 5까지인 배열로 구현된다.
○ 공백 상태에서만 front와 rear의 값이 서로 같으며, 그 외에는 값이 서로 다르다.
○ (front + 1) mod 6은 다음에 삭제할 원소 위치를 가리킨다.
○ (rear + 1) mod 6은 다음에 삽입할 원소 위치를 가리킨다.
○ 최대 ( ㉠ )개의 원소를 저장할 수 있다.
○ front = 5이고 rear = 3인 경우 저장된 원소 수는 ( ㉡ )개이다.
○ front = ( ㉢ )이고 rear = 2인 경우는 포화 상태를 의미한다.
괄호에는 ㉠ 5, ㉡ 4, ㉢ 3이 들어간다.
front = rear를 공백 상태 전용으로 쓰므로, 포화와 구분하려면 배열 한 칸을 비워 둔다. 따라서 크기 6 배열에 최대 5개만 저장한다.
원소 수 = (rear − front + 6) mod 6 = (3 − 5 + 6) mod 6 = 4
포화 조건은 (rear + 1) mod 6 = front이므로 rear = 2이면 front = 3이다.
- ㉠ 6, ㉡ 5, ㉢ 1 조합은 최대 원소 수와 원소 수가 모두 틀렸고, front = 1, rear = 2는 원소가 1개인 상태다.
- ㉠ 6, ㉡ 4, ㉢ 1 조합은 원소 수만 맞고, 6개를 모두 채우면 front = rear가 되어 공백과 구분되지 않는다.
- ㉠ 5, ㉡ 5, ㉢ 3 조합은 front = 5, rear = 3일 때 원소가 위치 0, 1, 2, 3의 4개뿐이라는 점과 맞지 않는다.
unsigned int do_something(unsigned int x, unsigned int y)
{
while (y!=0) {
int temp;
temp = x % y;
x = y;
y = temp;
}
return x;
}
do_something(660, 735)의 결과는 15이다.
이 함수는 나머지 연산을 반복하는 유클리드 호제법으로 두 수의 최대공약수를 구한다.
(660, 735) → (735, 660) → (660, 75) → (75, 60) → (60, 15) → (15, 0)
y가 0이 되는 순간의 x인 15를 반환한다.
- 5는 660과 735의 공약수이지만 최대공약수는 아니다.
- 9는 735의 약수가 아니므로 공약수가 될 수 없다.
- 25는 660의 약수가 아니므로 공약수가 될 수 없다.

2가지 이상의 순회에서 방문 순서가 같은 노드는 B, D, E, G, I의 5개이다.
세 순회 결과는 전위 A, B, D, E, H, C, F, G, I / 중위 D, B, H, E, A, F, C, G, I / 후위 D, H, E, B, F, I, G, C, A이다. 각 노드의 방문 위치를 비교하면 다음과 같다.
| 노드 | 전위 | 중위 | 후위 |
|---|---|---|---|
| A | 1 | 5 | 9 |
| B | 2 | 2 | 4 |
| C | 6 | 7 | 8 |
| D | 3 | 1 | 1 |
| E | 4 | 4 | 3 |
| F | 7 | 6 | 5 |
| G | 8 | 8 | 7 |
| H | 5 | 3 | 2 |
| I | 9 | 9 | 6 |
B·E·G·I는 전위와 중위에서, D는 중위와 후위에서 위치가 같다. A, C, F, H는 세 순회의 위치가 모두 다르다.
- 2개: 일치하는 노드 5개 중 일부만 센 값이다.
- 3개: 전위·중위가 같은 노드만 일부 세고 D를 빠뜨린 값이다.
- 4개: 전위·중위가 같은 B, E, G, I만 세고 중위·후위가 같은 D를 빠뜨린 값이다.

정점 G 바로 다음으로 최단경로가 확정되는 정점은 C이다.
A에서 시작해 거리가 최소인 정점을 차례로 확정하면 B(4) → F(5, A–B–F) → G(9, F 경유) → C(10, B 경유) → E(11, G 경유) → D(12, C 경유) 순이다.
- 정점 D: B 경유 13이었다가 C 확정 후 12로 갱신되며, 가장 마지막에 확정된다.
- 정점 E: G 확정 후 거리가 11로 갱신되지만 C의 10보다 커서 C 다음에 확정된다.
- 정점 F: A–B–F 경로 5로 G보다 먼저 확정된다.