10행 5열은 0부터 세는 C 배열에서 A[9][4]이므로 *(&A[0][0] + 904) = 15가 옳지 않다.
행 우선 저장이므로 시작 주소로부터의 오프셋은 행 첨자 × 열 개수 + 열 첨자이다.
오프셋 904는 에 해당해 19행 5열 위치를 가리킨다.
- A[9][4] = 15: 10행 5열을 첨자로 직접 지정한 올바른 방법이다.
- *(A[0] + 454) = 15: A[0]은 첫 행 시작 주소(int 포인터)이므로 454칸 뒤가 10행 5열이다.
- *(&A[9][0] + 4) = 15: 10행 첫 원소 주소에서 4칸 뒤이므로 10행 5열이다.
일의 자리부터 정렬하는 기수 정렬에서 두 번째 단계 후 결과는 706 - 508 - 133 - 155 - 379 - 984 - 193이다.
1단계(일의 자리)는 자리값이 같으면 입력 순서를 유지해 193 - 133 - 984 - 155 - 706 - 508 - 379가 된다.
2단계(십의 자리)는 이 순서에서 십의 자리 0(706, 508), 3(133), 5(155), 7(379), 8(984), 9(193) 순으로 모으며, 같은 버킷 안에서는 안정성에 따라 앞 단계 순서가 유지된다.
- 508 - 706 - 155 - 133 - 379 - 984 - 193: 앞 단계 순서상 706이 508보다 앞서야 하고, 십의 자리 3인 133이 5인 155보다 앞서야 한다.
- 706 - 508 - 155 - 133 - 379 - 193 - 984: 133과 155의 순서가 뒤바뀌었고, 십의 자리 8인 984가 9인 193보다 뒤에 있다.
- 508 - 706 - 133 - 155 - 379 - 193 - 984: 십의 자리가 같은 706과 508의 앞 단계 순서가 깨졌고, 984와 193의 순서도 틀렸다.
tmp→link = p→link;

반복문이 끝났을 때 tmp는 p가 가리키는 노드의 바로 앞 노드인 나를 가리킨다.
for 문은 tmp를 L에서 출발시켜 tmp→link가 p와 같아지는 순간 멈추므로, tmp는 p 직전 노드에 머문다. 이어지는 tmp→link = p→link는 p가 가리키는 노드 다를 리스트에서 떼어 내는 삭제 연산이다.
- 노드 가: L이 가리키는 첫 노드일 뿐, 그 link가 p가 아니므로 반복이 계속된다.
- 노드 다: p 자신이며 tmp→link가 p가 되는 조건을 만족하지 않는다.
- 노드 라: p 뒤의 노드로, tmp는 p를 지나쳐 이동하지 않는다.
(단, 루트(root)의 레벨은 1이다)
생성된 이진 탐색 트리의 높이는 5이다.
17이 루트, 10은 왼쪽, 22는 오른쪽 자식이 된다. 15는 10의 오른쪽, 13은 15의 왼쪽, 11과 14는 각각 13의 왼쪽·오른쪽 자식이 된다. 24와 20은 22의 자식으로 레벨 3이다.
가장 긴 경로는 17 → 10 → 15 → 13 → 11(또는 14)로 레벨 5까지 내려간다.
- 3: 22 쪽 서브트리만 본 값으로, 10 쪽 서브트리가 더 깊다.
- 4: 13까지만 센 값으로, 그 아래 11과 14가 한 레벨 더 있다.
- 6: 레벨 6에 해당하는 노드는 없다.
(단, llink는 왼쪽 노드를 가리키는 포인터이고, rlink는 오른쪽 노드를 가리키는 포인터이다)
(나) p→llink→rlink = newNode;
(다) newNode→rlink = p;
(라) newNode→llink = p→llink;
올바른 순서는 (라) - (다) - (나) - (가)이다.
p→llink를 바꾸기 전에 기존 왼쪽 노드 주소가 필요하므로, 먼저 newNode의 두 링크를 채우고(라, 다) 기존 왼쪽 노드의 rlink를 newNode로 바꾼 뒤(나) 마지막에 p→llink를 갱신한다(가).
- (가) - (나) - (다) - (라): p→llink가 먼저 newNode로 바뀌어 기존 왼쪽 노드 주소를 잃는다.
- (나) - (가) - (라) - (다): (라) 시점에 p→llink가 이미 newNode라서 newNode→llink가 자기 자신을 가리킨다.
- (다) - (라) - (가) - (나): (나) 시점의 p→llink가 newNode라서 기존 왼쪽 노드의 rlink는 갱신되지 않고 newNode→rlink가 자기 자신이 된다.
for (i = 1; i < n; i++) {
m = 1;
while (m < i) m = m * 2;
}이 프로그램의 시간 복잡도는 이다.
안쪽 while은 m을 2배씩 키우므로 i마다 약 회 반복하고, 바깥 for는 n-1회 돈다.
- : 안쪽 반복 횟수가 i에 비례해 늘어날 때의 값이다.
- : 바깥 반복 n회를 빠뜨린 값이다.
- : 안쪽 반복이 상수 횟수일 때의 값이다.
(단, 현재 상태에서 front = 0, rear = 2이며, front에서는 삭제, rear에서는 삽입이 일어난다)
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| A | B |
다. 두 개의 원소 삭제 라. 원소 E 삽입
마. 하나의 원소 삭제 바. 원소 F 삽입
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | D | E |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | C | D | E |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| A | B | F |
| [0] | [1] | [2] | [3] | [4] | [5] |
|---|---|---|---|---|---|
| F | D | E |
수행 후 큐는 [0]에 F, [4]에 D, [5]에 E가 들어 있는 상태이다.
front는 첫 원소 바로 앞 칸을 가리키며, 삽입은 rear를, 삭제는 front를 으로 한 칸씩 옮긴다.
C, D 삽입 → rear = 4
두 개 삭제(A, B) → front = 2
E 삽입 → rear = 5
하나 삭제(C) → front = 3
F 삽입 → rear = 0
- [0] F, [3] C, [4] D, [5] E인 상태: 하나의 원소 삭제로 C가 빠져야 하는데 남아 있다.
- [1] A, [2] B, [3] F인 상태: A와 B가 삭제되지 않았고 C, D, E도 없다.
- [3] F, [4] D, [5] E인 상태: rear가 원형으로 돌아가므로 F는 [0]에 들어가야 하며, C 삭제 후 [3]은 비어 있다.
중위표기식 후위표기식
일치하지 않는 것은 A * B / (C - D) + E와 그 후위식이다.
* 와 / 는 같은 우선순위로 왼쪽부터 결합하므로 ((A*B)/(C-D))+E이고, 후위식은 A B * C D - / E +가 되어야 한다. 제시된 A B * C D - E / + 는 (A*B)+((C-D)/E)를 뜻한다.
- A * B + C / D: (A*B)+(C/D)이므로 A B * C D / + 로 맞다.
- A + (B + C) / D - E: (A+((B+C)/D))-E이므로 A B C + D / + E - 로 맞다.
- A / B - C + D * E: ((A/B)-C)+(D*E)이므로 A B / C - D E * + 로 맞다.




삭제 후의 최대 힙은 레벨 순서로 45 / 32, 20 / 19, 9, 16, 4이다.
차례로 삽입하며 부모와 교환(up-heap)하면 힙 배열은 57, 32, 45, 19, 9, 16, 20, 4가 된다. 삭제는 루트 57을 꺼내고 마지막 원소 4를 루트로 올린 뒤, 더 큰 자식과 교환하며 내려간다(4↔45, 4↔20).
그 결과 배열은 45, 32, 20, 19, 9, 16, 4가 된다.
- 루트가 57이고 오른쪽 자식이 45인 트리: 마지막 원소 4만 빠진 형태로, 루트(최댓값)를 꺼내는 힙 삭제가 반영되지 않았다.
- 루트가 57이고 오른쪽 자식이 20인 트리: 최댓값 57이 아니라 45가 삭제된 형태이다.
- 20의 자식이 4, 16 순서인 트리: 4는 마지막 위치에서 내려온 원소이므로 20의 오른쪽 자식이어야 하고, 왼쪽 자식은 16이다.
(단, 이고, 이라고 가정한다)
시간복잡도
합병 정렬의 비교 횟수는 , 시간복잡도는 이다.
크기 N/2인 두 부분을 각각 정렬하고(), 정렬된 두 리스트를 합병할 때 최악 번 비교한다.
이를 풀면 이다.
- : 한쪽 절반만 재귀하는 식으로 합병 정렬과 다르며, 풀면 이다.
- : 이진 탐색의 비교 횟수 식이다.
- : 합병 비용을 상수로 본 식이며, 풀면 이 되어 짝지은 복잡도와도 맞지 않는다.
head(tail(head(L)))의 값은 (b, c)이다.
head(L)은 첫 원소 (a, (b, c))이고, 그 tail은 a를 뺀 리스트 ((b, c))이다. 이 리스트의 head는 유일한 원소인 (b, c)이다.
tail의 결과는 항상 리스트이므로 괄호 한 겹이 더 씌워진다는 점에 주의한다.
- b: (b, c)에 head를 한 번 더 적용해야 나오는 값이다.
- c: (b, c)의 마지막 원소로, 주어진 연산 결과가 아니다.
- (d, e): L의 두 번째 원소로 head(tail(L))의 값이다.




복원한 트리는 루트 1의 왼쪽에 2와 그 오른쪽 자식 3, 오른쪽에 4(왼쪽 5, 오른쪽 6)가 있고, 6의 왼쪽 자식 7의 오른쪽 자식이 8, 6의 오른쪽 자식이 9인 형태이다.
전위 순회의 첫 원소가 루트이고, 중위 순회에서 루트의 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리이다. 1을 기준으로 {2, 3}과 {5, 4, 7, 8, 6, 9}로 나누고, 같은 방식으로 4와 6을 서브트리의 루트로 재귀 분할한다.
- 3이 2의 왼쪽 자식이고 8 아래에 9가 달린 트리: 중위 순회가 3, 2로 시작해 주어진 2, 3과 어긋난다.
- 3이 2의 오른쪽 자식이고 9가 7의 자식, 8이 6의 오른쪽 자식인 트리: 전위 순회가 6, 7, 9, 8 순이 되어 주어진 6, 7, 8, 9와 다르다.
- 3이 2의 왼쪽 자식이고 9가 7의 자식인 트리: 중위 순회가 3, 2로 시작하고 9, 8의 위치도 주어진 순서와 맞지 않는다.

| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 |
반사 이행적 폐쇄는 자기 자신을 포함해 경로로 도달 가능한 모든 정점을 1로 표시한 행렬이다.
그래프는 0→1→2→3 경로와 3→1 역방향 간선, 3→4 간선으로 이루어져 있어 1, 2, 3은 서로 순환하며 4로도 갈 수 있다. 따라서 0행은 모두 1, 1~3행은 0열만 0, 4행은 대각 원소만 1이다.
- 대각 원소 (0, 0)과 (4, 4)가 0인 행렬: 길이 0 경로를 포함하지 않은 이행적 폐쇄이다.
- 대각 원소가 0이고 직접 간선 일부만 1인 행렬: 반사성도 없고 경로를 통한 도달도 반영되지 않았다.
- 대각 원소는 1이지만 직접 간선 일부만 1인 행렬: 반사성은 있으나 경로를 통한 도달(이행성)이 반영되지 않았다.




루트가 20이고 왼쪽 서브트리가 10-15-14로 깊어진 트리는 AVL 트리가 아니다.
AVL 트리는 모든 노드에서 왼쪽·오른쪽 서브트리 높이 차(균형 인수)가 1 이하여야 한다. 이 트리는 루트의 왼쪽 높이가 3, 오른쪽(25) 높이가 1이라 균형 인수가 2이다.
- 루트 15, 왼쪽 10(2, 14), 오른쪽 25(20)인 트리: 모든 노드의 높이 차가 1 이하이다.
- 루트 15에서 10의 오른쪽 자식 12 아래에 14가 붙은 트리: 10에서 높이 차 1, 루트에서 높이 차 1로 균형을 만족한다.
- 루트 14, 왼쪽 4(2, 10(8, 12)), 오른쪽 20(15, 25)인 트리: 4에서 높이 차 1, 루트에서 높이 차 1이다.
| 정렬 기법 데이터 세트 | 갑 | 을 |
|---|---|---|
| A | 0.21초 | 0.40초 |
| B | 6.71초 | 0.39초 |
갑 을
갑은 퀵 정렬, 을은 합병 정렬이다.
갑은 데이터 세트 B에서 시간이 30배 이상 늘었다. 데이터 분포(이미 정렬된 경우 등)에 따라 최악 로 떨어지는 기법은 퀵 정렬뿐이다.
을은 두 세트에서 시간이 거의 같으므로 분포와 무관하게 인 기법이며, 갑이 퀵 정렬인 조합은 을이 합병 정렬인 경우뿐이다.
- 힙 정렬과 퀵 정렬: 힙 정렬은 입력 분포와 무관하게 이라 갑처럼 급격히 느려지지 않는다.
- 합병 정렬과 퀵 정렬: 합병 정렬도 최악이 이라 갑의 큰 편차를 설명하지 못한다.
- 합병 정렬과 힙 정렬: 둘 다 분포에 둔감해 갑의 큰 편차가 나올 수 없다.

단일 정점 트리들이 고르는 최소 간선은 (A, B), (C, F), (D, E)뿐이므로 (B, E)는 선택되지 않는다.
Sollin 알고리즘 첫 단계에서는 각 정점마다 연결된 간선 중 가중치가 가장 작은 것을 고른다. A와 B는 가중치 5인 (A, B), C와 F는 15인 (C, F), D와 E는 10인 (D, E)를 고른다.
(B, E)의 가중치 20은 B 입장에서는 (A, B)보다, E 입장에서는 (D, E)보다 크므로 어느 쪽에서도 최소가 아니다.
- (A, B): A와 B 모두의 최소 비용 간선(5)이다.
- (C, F): C와 F 모두의 최소 비용 간선(15)이다.
- (D, E): D와 E 모두의 최소 비용 간선(10)이다.

1-2-3-4-5-6-7-8은 깊이 우선 탐색으로 나올 수 없다.
깊이 우선 탐색은 현재 정점에 방문하지 않은 인접 정점이 남아 있으면 반드시 그쪽으로 내려가고, 없을 때만 되돌아간다. 정점 5는 7, 8과 인접하고 6과는 연결되지 않으므로, 5 다음에는 7이나 8이 와야 한다.
- 1-2-3-4-6-7-5-8: 6에서 막혀 4로 돌아가 7을 방문하고, 7에서 5, 5에서 8로 가는 정상 순서이다.
- 1-2-3-4-6-5-7-8: 6에서 4로 되돌아가 5, 5에서 7, 다시 5로 돌아가 8을 방문한다.
- 1-2-3-4-5-7-8-6: 5에서 7, 막혀 5로 돌아가 8, 다시 4로 돌아가 6을 방문한다.
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 1 | 15 | 3 | 10 | 6 |
| [0] | [1] | [2] | [3] | [4] | [5] | [6] |
|---|---|---|---|---|---|---|
| 6 | 1 | 3 | 10 | 15 |
삽입 완료 후 테이블은 [0]=6, [1]=1, [3]=3, [4]=10, [6]=15이다.
이중 해싱은 충돌 시 위치를 차례로 탐사한다.
1 → [1], 3 → [3]은 충돌 없이 들어간다.
15: 충돌, →
6: 충돌, → 충돌 →
10: 충돌, → [1], [6] 충돌 →
- [2]에 15, [4]에 10, [6]에 6인 상태: 충돌 시 한 칸씩 옮기는 선형 탐사의 결과다.
- [0]에 6, [5]에 10, [6]에 15인 상태: 10은 [1], [6]을 거쳐 [4]에 들어가야 한다.
- [2]에 15, [5]에 10, [6]에 6인 상태: 15부터 두 번째 해시 함수를 올바로 적용하지 않은 결과다.
struct TreeNode {
int data;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;
SearchTree FindMin(SearchTree T)
{
if (T == NULL) return NULL;
else if (T→Left == NULL) ( 가 )
else ( 나 )
}( 가 ) ( 나 )(가)는 return T;, (나)는 return FindMin(T→Left);이다.
이진 탐색 트리의 최솟값은 왼쪽 자식을 끝까지 따라간 노드에 있다. 왼쪽 자식이 없으면 현재 노드가 최소이므로 T를 반환하고, 있으면 왼쪽 서브트리에서 재귀적으로 찾는다.
- return T; 와 return T→Left; 조합: 왼쪽으로 한 단계만 내려가 더 깊은 곳의 최솟값을 놓친다.
- return T→Right; 와 return T→Left; 조합: 왼쪽 자식이 없을 때 최소는 현재 노드인데 더 큰 값인 오른쪽 자식을 반환한다.
- return FindMin(T→Right); 와 return FindMin(T→Left); 조합: 오른쪽 서브트리에는 현재 노드보다 큰 값만 있어 최솟값이 될 수 없다.
late(i) = latest[l] - 작업 ai의 작업 시간(duration)

작업 a3은 early(3) = 6이지만 late(3) = 11이므로, late(3)을 10으로 제시한 결과가 옳지 않다.
전진 계산으로 earliest를 구하면 V1 = 6, V3 = 10, V4 = 7, V6 = 14, V7 = 11, V8 = 19이다. 후진 계산으로 latest를 구하면 V6 = 14, V7 = 16, V4 = min(14 − 2, 16 − 4) = 12이다.
a3은 간선 <1, 4>, 작업 시간 1이므로 late(3) = latest[4] − 1 = 11이다.
- early(5) = 10, late(5) = 10: a5는 <3, 6>, 시간 4로 earliest[3] = 10, latest[6] − 4 = 10이다.
- early(7) = 7, late(7) = 12: a7은 <4, 7>, 시간 4로 earliest[4] = 7, latest[7] − 4 = 12이다.
- early(9) = 14, late(9) = 14: a9는 <6, 8>, 시간 5로 earliest[6] = 14, latest[8] − 5 = 14이다.