
단순 연결 리스트로 구현한 데크에서 O(1)에 할 수 없는 연산은 마지막 원소 삭제(deleteLast)이다.
마지막 노드를 지우면 last 를 그 직전 노드로 옮기고 링크를 NULL 로 바꿔야 하는데, 단방향 링크로는 직전 노드를 알 수 없어 first 부터 끝까지 따라가야 하므로 O(n)이 걸린다.
- 첫 번째 원소로 삽입: 새 노드가 기존 first 를 가리키게 하고 first 만 갱신하면 되므로 O(1)이다.
- 마지막 원소로 삽입: last 노드의 링크를 새 노드로 연결하고 last 를 갱신하면 되므로 O(1)이다.
- 첫 번째 원소 삭제: first 를 다음 노드로 옮기기만 하면 되므로 O(1)이다.
(ㄱ) push 연산 수행 전 스택
(ㄴ) push 연산 수행 후 스택

(ㄴ)에서 자료 c를 꺼내려면 pop 이 3회 필요하므로 2회라는 설명이 옳지 않다.
(ㄴ)은 top→a→b→c→d 순서로 연결되어 있고, 스택은 top 쪽부터 꺼내므로 a, b를 먼저 꺼낸 뒤 세 번째 pop 에서 c가 나온다.
- top 이 가리키는 노드가 가장 최근에 push 된 자료라는 설명은 옳다.
- d는 리스트 맨 끝(바닥)에 있으므로 가장 오래된 자료라는 설명은 옳다.
- (ㄱ)은 top→b→c→d 이므로 입력 순서가 d, c, b라는 설명은 옳다.
int PowersRec(int x, int n)
{
int Pow;
if (n == 1)
Pow = x;
else {
if (even(n))
Pow = PowersRec(x*x, n/2);
else
Pow = x * PowersRec(x*x, (n-1)/2);
}
return (Pow);
}
이 알고리즘의 시간 복잡도는 이다.
재귀 호출마다 지수 n이 n/2 또는 (n-1)/2로 절반씩 줄고, 각 호출은 비교·곱셈 같은 상수 시간 작업만 한다.
- : 호출 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
- : x를 n번 곱하는 단순 반복 방식의 복잡도이다.
- : 호출당 작업이 상수이고 호출 횟수가 로그 수준이므로 해당하지 않는다.
void sort(int A[ ], int n)
{
int i, j, key;
for (i = 1; i < n; i++) {
key = A[i];
for (j = i - 1; ㉠ ; j--)
㉡
A[j+1] = key;
}
}
㉠ ㉡
㉠에는 j >= 0 && key < A[j], ㉡에는 A[j+1] = A[j];가 들어간다.
오름차순 삽입 정렬은 key보다 큰 원소를 한 칸씩 오른쪽으로 밀고, 멈춘 위치의 다음 칸 A[j+1]에 key를 넣는다. 맨 앞 A[0]까지 비교해야 하므로 j >= 0 조건이 필요하다.
- key > A[j] 조건으로 미는 조합: key보다 작은 원소를 밀게 되어 내림차순이 된다.
- j > 0 과 A[j-1] = A[j] 조합: A[0]과 비교하지 못하고, 원소를 왼쪽으로 옮겨 값을 덮어쓴다.
- j > 0 과 A[j] = A[j+1] 조합: A[0]과 비교하지 못하고, 이동 방향이 반대라 큰 원소가 오른쪽으로 밀리지 않는다.
int f(int n)
{
if (n == 0 || n == 1)
return n;
return f(n-1) + f(n-2);
}
f(7)을 포함한 총 호출 횟수는 41회이다.
호출 횟수를 C(n)이라 하면 n이 0·1이면 자기 자신 1회이고, 그 외에는 자신 1회에 두 하위 호출의 횟수가 더해진다:
- 25회: f(6)을 처음 호출했을 때의 총 호출 횟수이다.
- 35회: f(6)과 f(5) 호출분(25+15)만 더해도 40회이므로 너무 작다.
- 51회: 40회에 f(7) 자신 1회를 더한 값보다 크므로 성립하지 않는다.
일곱 번째로 push되는 값은 E이다.
후위표기식은 A B - C * D E + F / -이며, 피연산자는 읽을 때 push하고 연산자는 두 값을 pop해 계산한 결과를 push한다.
push 순서: A → B → A-B → C → (A-B)*C → D → E → D+E → F → (D+E)/F → 최종 결과
- D: 여섯 번째로 push된다.
- D+E: 여덟 번째로 push된다.
- (A-B)*C: 다섯 번째로 push된다.
A[4][5][10] 앞에는 원소가 47개 있으므로 이 원소는 48번째이다.
각 차원 크기는 6-3+1=4, 7-2+1=6, 12-8+1=5이고, 행 우선이므로 앞 첨자일수록 큰 묶음 단위로 건너뛴다.
- 47: 0부터 센 오프셋을 그대로 순서로 착각한 값이다.
- 45: 마지막 첨자의 거리 10-8=2를 빠뜨린 값이다.
| (가) | ○ 행 우선 배열이며, 크기는 이다. ○ 첫 번째 행의 3개 열에는 희소행렬에 대한 행의 크기(), 열의 크기(), 0이 아닌 원소의 수()를 순서대로 저장한다. ○ 나머지 개의 각 행에는 0이 아닌 개의 원소들에 대한 정보가 저장되며, 해당 행의 각 열에는 원소들의 행 번호, 열 번호, 저장된 값이 각각 저장된다. ○ 원소들에 대한 정보를 저장할 때는 원소들의 행 번호와 열 번호가 차례대로 오름차순이 되도록 저장한다. | ||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| (나) | :
|
는 2가 아니라 3이므로 이 설명이 옳지 않다.
X에서 행렬 P의 0이 아닌 원소는 이고, Y에서 행렬 Q는 이다.
R의 1행은 Q의 1행이 모두 0이라 0이다.
따라서 Z는 첫 행 (3, 2, 4) 뒤에 (0, 0, 12), (0, 1, 8), (2, 0, 3), (2, 1, 2) 순으로 저장된다.
- : R의 열 크기가 2이므로 옳다.
- : 0이 아닌 원소가 4개이므로 옳다.
- : 첫 원소 R[0][0]의 행 번호가 0이므로 옳다.
구성할 수 있는 서로 다른 최소 힙은 8개이다.
힙은 완전 이진 트리이므로 노드 5개의 모양은 하나로 고정되고, 루트는 최솟값 1이다. 루트의 왼쪽 서브트리는 노드 3개, 오른쪽 서브트리는 노드 1개이다.
남은 2~5 중 왼쪽에 들어갈 3개 선택:
3노드 서브트리는 루트가 최솟값으로 고정되고 두 자식 배치가 2가지
- 1개: 루트만 고정될 뿐 나머지 원소의 배치는 여러 가지이다.
- 6개: 왼쪽 원소 조합 4가지마다 두 배치가 모두 힙 조건을 만족하므로 8보다 적지 않다.
- 10개: 3노드 서브트리 내부 배치는 2가지뿐이므로 8을 넘을 수 없다.

정점 0에서 시작한 깊이 우선 탐색의 순회 순서는 0, 1, 3, 2, 5, 6, 4이다.
DFS는 현재 정점의 인접 리스트를 앞에서부터 보며 아직 방문하지 않은 정점으로 곧바로 내려간다.
0의 리스트에서 1 → 1의 리스트에서 3(0은 방문함) → 3의 리스트에서 2 → 2의 리스트에서 5 → 5의 리스트에서 6 → 6의 리스트에서 4 순으로 방문한다.
- 0, 1, 2, 3, 4, 5, 6은 가까운 정점부터 넓게 방문하는 너비 우선 탐색의 순서이다.
- 2 다음에 4를 방문하는 순서는 2의 인접 리스트에 4가 없으므로 성립하지 않는다.
- 5 다음에 4를 방문하는 순서는 5의 인접 리스트(2, 6)에 4가 없으므로 성립하지 않는다.
최악 시간 복잡도가 인 것은 합병 정렬과 힙 정렬이다.
합병 정렬은 입력과 무관하게 항상 반씩 나누어 합치고, 힙 정렬은 힙 구성 후 n번의 삭제가 각각 이어서 최악에도 이다.
- 삽입·버블 정렬 조합: 역순 입력 같은 최악의 경우 둘 다 이다.
- 선택·퀵 정렬 조합: 선택 정렬은 항상 이고, 퀵 정렬도 피벗이 한쪽으로 치우치면 이다.
- 퀵·힙 정렬 조합: 힙 정렬은 맞지만 퀵 정렬의 최악은 이다.
옳은 표현은 V ={ a, b, c, d, e, f }, E ={ (a, b), (b, c), (c, a) }이다.
간선의 양 끝 정점은 모두 V에 속해야 하며, V와 E는 집합이므로 같은 원소를 중복해 쓰지 않는다. 간선이 없는 고립 정점 d, e, f가 있어도 그래프로 성립한다.
- V ={ a, a, c }인 표현: 정점 a가 중복되고, 간선 (b, b)의 정점 b가 V에 없으며 자기 자신으로 가는 간선도 포함한다.
- V ={ a, c }인 표현: 간선 (a, b), (b, c)의 정점 b가 V에 없다.
- V ={ a, b, c, d }인 표현: 간선 (e, a)의 정점 e가 V에 없다.

최소 비용은 12이고 세 번째로 선택되는 간선은 (b, e)이다.
Prim 알고리즘은 이미 트리에 포함된 정점에서 나가는 간선 중 가장 가벼운 것을 하나씩 추가한다.
a에서 (a, b) 2 → (b, f) 1 → (b, e) 3 → (e, d) 2 → (b, c) 4 순으로 선택되며, 합은 이다.
- 비용을 13으로 본 조합은 최소 비용 계산이 틀렸다.
- (d, e)는 세 번째 단계에서 d, e 모두 아직 트리에 없어 선택될 수 없고, e가 들어온 뒤 네 번째로 선택된다.

강력 연결 요소는 {a, c, d, e, f}와 {b} 두 개이므로 정점 수는 5, 1이다.
a→d→c→f→a 와 a→d→e→f→a 의 두 순환이 정점 a, c, d, e, f를 서로 오갈 수 있게 묶는다. 반면 b는 들어오는 간선만 있고 나가는 간선이 없어 홀로 하나의 요소가 된다.
- 4, 1, 1이나 4, 2로 나누는 것은 c 또는 e가 순환에 포함된다는 점을 놓친 것이다.
- 6개 전체가 하나라고 보는 것은 b에서 다른 정점으로 갈 수 없다는 점에 어긋난다.
p = start;
q = NULL;
while (p != NULL)
{
㉠
p = p->link;
q->link = r;
}
start = q;
㉠에 들어갈 내용은 r = q; q = p;이다.
q는 이미 뒤집힌 부분의 첫 노드, p는 아직 처리하지 않은 노드를 가리킨다. 매 반복에서 r에 이전 q를 보관하고 q를 현재 노드 p로 옮긴 뒤, p를 다음 노드로 전진시키고 q->link = r로 링크 방향을 뒤집는다.
- q = q->link; r = q; : 첫 반복에서 q가 NULL이므로 NULL 포인터를 역참조한다.
- r = q; q = p->link; : q가 현재 노드가 아닌 다음 노드를 가리켜, 진행 중인 노드의 링크를 덮어써 순회가 깨진다.
- q = q->link; : 첫 반복에서 NULL을 역참조하고, r도 갱신되지 않는다.
구성이 불가능한 것은 높이 5, 노드 10개, 단말 노드 6개인 이진 트리이다.
이진 트리에서는 단말 노드 수가 차수 2인 노드 수보다 항상 1 많다().
차수 1인 노드 수가 음수가 되어 성립하지 않는다.
- 노드 23개·높이 5: 높이 5의 노드 수는 5개부터 개까지 가능하다.
- 노드 20개·간선 19개: 모든 트리는 간선 수가 노드 수보다 1 적으므로 가능하다.
- 높이 6·노드 32개인 완전 이진 트리: 5단계까지 31개를 채우고 6단계 맨 왼쪽에 1개를 두면 된다.

원래 일반 트리의 단말 노드는 I, E, F, J, K, L, M의 7개이다.
왼쪽 링크는 첫 자식, 오른쪽 링크는 다음 형제이므로 복원하면 A의 자식은 B, C이고, B의 자식은 D, E, F, D의 자식은 I이다. C의 자식은 G, H, G의 자식은 J, K, L, H의 자식은 M이다.
- B의 자식은 D, E, F로 3개이므로 2개라는 설명은 틀렸다.
- C는 B의 오른쪽(형제) 링크에 있으므로 부모는 B가 아니라 A이다.
- D에서 J까지의 경로는 D-B-A-C-G-J로 길이가 5이므로 4라는 설명은 틀렸다.
(가)
| 1 | 2 | 3 | 4 | 5 | |
| 0.2 | 0.45 | 0.05 | 0.1 | 0.2 |

이진 탐색 트리 (나)의 총비용은 1.75이다.
(나)에서 루트는 (단계 1), 그 자식은 (단계 2), 의 왼쪽 자식 는 단계 3, 의 왼쪽 자식 은 단계 4이다.
- 1.65는 각 키의 단계를 하나라도 낮게 잡았을 때 나오는 값이다.
- 1.85나 1.95는 깊은 노드의 단계를 실제보다 높게 계산한 값이다.

최종 인덱스 노드는 루트 (16 : 22), 자식 (8 : -), (17 : 18), (41 : 58)이다.
1 삽입 시 (8, 11)이 넘쳐 (1)과 (8, 11)로 나뉘고 8이 인덱스 (16)에 올라가 (8 : 16)이 된다.
18 삽입 시 (16, 17)이 (16)과 (17, 18)로 나뉘고 17이 올라가 인덱스가 8, 16, 17로 넘치므로, 가운데 16이 루트로 승격해 루트는 (16 : 22), 왼쪽 인덱스는 (8), (17)로 갈린다.
19 삽입 시 (17, 18)이 (17)과 (18, 19)로 나뉘고 18이 올라가 인덱스가 (17 : 18)이 된다.
- 루트가 (18 : 22)라는 구성은 인덱스 분할 때 16이 루트로 올라가는 과정을 놓친 것이다.
- 자식이 (8 : 11)이라는 구성은 11이 데이터 노드 분할에서 인덱스로 올라간 적이 없으므로 틀렸다.
레드 링크로 연결되지 않은 쌍은 (1, 2)이다.
7, 3, 6, 2, 1, 8, 4를 차례로 삽입하면 루트 6(블랙), 왼쪽 자식 2(레드)와 그 자식 1·3(블랙), 3의 오른쪽 자식 4(레드), 오른쪽 자식 7(블랙)과 그 오른쪽 자식 8(레드)이 된다.
6 삽입 때 이중 회전으로 6이 루트가 되고, 1 삽입 때 2를 중심으로 회전하며, 4 삽입 때 삼촌 1이 레드여서 색 변환으로 2는 레드, 1·3은 블랙이 된다.
- (2, 6): 2가 레드이므로 6에서 2로 가는 링크는 레드이다.
- (3, 4): 4가 레드이므로 레드 링크이다.
- (7, 8): 8이 레드이므로 레드 링크이다.