스택에 다섯 번째로 push되는 값은 B이다.
수식을 전위 표기로 바꾸면 + * - A B C / D E이다. 오른쪽부터 읽으며 피연산자는 push하고, 연산자를 만나면 두 값을 pop해 계산한 결과를 다시 push한다.
push 순서: E → D → (D/E) → C → B → A …
- A: B 다음, 여섯 번째로 push된다.
- D: 두 번째로 push된다.
- E: 가장 먼저(첫 번째로) push된다.
이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 링크를 가진다.
그래서 양방향 순회가 가능하지만, 노드는 메모리에 흩어져 있고 특정 노드에 가려면 링크를 따라가야 한다.
- 연속된 메모리 공간에 저장되는 것은 배열(순차 리스트)의 특징이다.
- 링크가 하나뿐인 것은 단순(단일) 연결 리스트이다.
- 인덱스로 직접 접근하는 임의 접근은 배열의 특징이며, 연결 리스트는 순차적으로 따라가야 한다.
int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return (fib(n-1) + fib(n-2));
}
fib(5)를 호출하면 함수는 총 15회 호출된다.
호출 횟수를 이라 하면 , 이다.
- 7회: 중복 호출을 대부분 빠뜨린 값이다.
- 12회: 재귀 트리의 일부 호출을 누락한 값이다.
- 17회: 실제보다 많이 센 값으로, n이 0 또는 1이면 더 재귀하지 않는다는 점과 맞지 않는다.
색인 순차 탐색의 시간 복잡도는 이므로, 이라는 설명이 옳지 않다.
크기 인 인덱스 테이블을 먼저 탐색한 뒤, 찾은 구간(크기 약 )을 배열에서 순차 탐색하기 때문이다.
- 순차 탐색은 원소를 처음부터 하나씩 비교하므로 이다.
- 인덱스 테이블이 작아지면 인덱스 간격이 커져 배열에서 탐색할 구간이 넓어진다.
- 11개 원소의 이진 탐색은 중간값 11과 비교한 뒤 오른쪽 구간의 중간값 17과 비교하므로 비교는 2회이다.
void func(int arr[], int n, int k) {
int temp[100];
for (int i = 0; i < n; i++)
temp[i] = arr[(i + k) % n];
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}실행 후 배열은 [3, 4, 5, 6, 1, 2]가 된다.
temp[i]에 arr[(i+2)%6]을 담으므로 배열이 왼쪽으로 2칸 회전한다. temp[0]=arr[2]=3, temp[1]=arr[3]=4, …, temp[4]=arr[0]=1, temp[5]=arr[1]=2이다.
- [1, 2, 3, 4, 5, 6]은 회전하지 않은 원래 상태이다.
- [2, 3, 4, 5, 6, 1]은 왼쪽으로 1칸 회전한 결과이다.
- [5, 6, 1, 2, 3, 4]는 오른쪽으로 2칸 회전한 결과이다.
무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 개이다. 따라서 개라는 설명이 옳지 않다.
방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 개가 된다.
- 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 개이다.
- 인접 행렬의 행 는 정점 에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
- 인접 리스트에서 헤드 에 연결된 노드는 에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. 개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 이다.
옳은 것은 ㄱ, ㄷ이다.
높이 인 이진 트리의 최대 노드 수는 이므로 , 즉 이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.
- ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
- ㄹ: 이진 탐색 트리의 평균 검색 시간은 이며, 은 한쪽으로 치우친 최악의 경우이다.
Algorithm(int n) {
int i, j, k, l;
int sum = 0;
for (i = 0; i < 500; i++)
for (j = 0; j < 100; j++)
for (k = 1; k < n; k = k * 2)
for (l = 0; l < 10; l++)
sum = sum + i + j + k + l;
}시간 복잡도는 이다.
i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 회 반복한다.
총 실행 횟수는 이고, 상수를 제거하면 이다.
- : k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
- : k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
- : n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.
• 초기 상태에서 front와 rear은 모두 0을 가리키며, 큐는 공백 상태이다.
• 공백 상태와 포화 상태를 구분하기 위해 항상 한 칸을 비워 두는 방식으로 구현한다.
• enqueue는 데이터를 삽입하는 연산이며, rear을 먼저 한 칸 이동시킨 후 해당 위치에 저장한다.
• dequeue는 데이터를 삭제하는 연산이며, front를 먼저 한 칸 이동시킨 후 해당 데이터를 삭제한다.
dequeue() ⇒ enqueue(D) ⇒ enqueue(E) ⇒ enqueue(F)
모든 연산을 마친 뒤 rear는 인덱스 0을 가리킨다.
enqueue는 , dequeue는 로 이동한다.
A는 1, B는 2, C는 3에 저장되고 dequeue로 front가 1이 된다. D는 4, E는 5, F는 에 저장되며, 이때 다음 칸이 front가 되어 포화 상태가 된다.
- 3: C까지 삽입한 시점의 rear이다.
- 4: D까지 삽입한 시점의 rear이다.
- 5: E까지 삽입한 시점의 rear로, F 삽입 시 원형으로 되돌아가는 것을 반영하지 않은 값이다.
단계 직후 배열은 [3, 12, 17, 27, 80, 42, 91, 95]이다.
단계: (91, 80), (42, 95), (17, 3), (12, 27) 부분 리스트를 각각 정렬하면 [80, 42, 3, 12, 91, 95, 17, 27]이다.
단계: 짝수 위치 (80, 3, 91, 17)은 (3, 17, 80, 91)로, 홀수 위치 (42, 12, 95, 27)은 (12, 27, 42, 95)로 정렬해 합친다.
- [3, 12, 27, 17, 80, 42, 91, 95]: 17과 27의 자리가 바뀌어 부분 리스트가 정렬되지 않았다.
- [80, 42, 3, 12, 91, 95, 17, 27]: 단계까지만 수행한 상태이다.
- [80, 42, 3, 12, 95, 91, 17, 27]: 단계 결과와도 91, 95의 순서가 다르다.
최소 힙은 부모 키값이 자식 키값보다 작거나 같으면 되므로, "항상 작다"고 한 설명이 옳지 않다.
힙은 같은 키값을 허용하므로 최대 힙(부모 ≥ 자식)과 마찬가지로 최소 힙도 등호를 포함한 부모 ≤ 자식 관계를 만족한다.
- 삽입 시 완전 이진 트리를 유지하려면 마지막 노드 다음 자리( 위치)에 원소를 임시로 두고 부모와 비교하며 올라간다.
- 힙의 삭제는 루트 원소를 꺼낸 뒤 마지막 노드를 루트로 옮겨 재정렬한다.
- 배열로 구현하면 노드 의 부모는 처럼 인덱스 계산으로 바로 찾는다.
세 번째로 신장 트리에 포함되는 간선은 (C, D)이다.
크루스칼 알고리즘은 가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 제외한다.
(B, C) 1 선택 → (A, B) 2 선택 → (A, C) 3은 A-B-C 사이클을 만들어 제외 → (C, D) 4 선택.
- (A, B): 두 번째로 포함되는 간선이다.
- (A, C): 사이클을 만들어 제외된다.
- (B, D): 정점 4개의 신장 트리는 간선 3개로 이미 완성되어 선택되지 않는다.
중위 순회: D − B − F − E − A − C − G
후위 순회: D − F − E − B − G − C − A




세 순회를 모두 만족하는 트리는 E의 왼쪽 자식이 F, C의 오른쪽 자식이 G인 구조이다.
전위 순회의 첫 노드 A가 루트이고, 중위 순회에서 A의 왼쪽(D B F E)이 왼쪽 서브트리, 오른쪽(C G)이 오른쪽 서브트리가 된다. 왼쪽 서브트리는 전위상 B가 루트로 D가 왼쪽, F·E가 오른쪽에 오며, 전위 E−F·중위 F−E이므로 F는 E의 왼쪽 자식이다.
오른쪽 서브트리는 전위 C−G, 중위 C−G이므로 G는 C의 오른쪽 자식이고, 후위 순회 D−F−E−B−G−C−A로도 확인된다.
- G가 C의 왼쪽 자식인 구조는 중위 순회가 G−C 순서가 되어 맞지 않는다.
- F가 E의 오른쪽 자식인 구조는 중위 순회가 E−F 순서가 되어 맞지 않는다.
- E가 B의 왼쪽, D가 B의 오른쪽에 있는 구조는 전위 순회가 A−B−E−F−D… 가 되어 맞지 않는다.
void deleteNode(linkedList_h* CL, listNode* old) {
listNode* pre;
if (CL->head == NULL) return;
if (CL->head->link == CL->head) {
free(CL->head);
CL->head = NULL;
return;
}
else if (old == NULL) return;
else {
pre = CL->head;
while (pre->link != old) {
pre = pre->link;
}
( (가) )
if (old == CL->head) {
( (나) )
}
free(old);
}
}(가)는 pre->link = old->link;, (나)는 CL->head = old->link;이다.
pre는 old의 바로 앞 노드이므로 pre의 링크를 old의 다음 노드로 바꿔 old를 리스트에서 떼어낸다. old가 head였다면 순서를 유지하도록 old의 다음 노드를 새 head로 지정한다.
- old->link = pre->link: 삭제할 노드의 링크만 바뀌고 pre는 여전히 old를 가리켜 연결이 끊기지 않는다.
- (나)에서 head를 pre로 바꾸는 경우: 마지막 노드가 첫 노드가 되어 기존 순서가 바뀐다.
- pre = old->link: 지역 변수만 바뀔 뿐 리스트의 링크는 그대로이다.

중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.
그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 개이고, 전체 포인터 개 중 빈 포인터는 개이다.
중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 개이다.
- 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
- 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
- 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.

5를 삽입하면 루트 30에서 왼쪽-왼쪽 방향으로 불균형이 생기므로 LL 회전을 수행한다.
그림의 트리는 루트 30의 왼쪽에 20(자식 10, 25), 오른쪽에 40이 있다. 5는 30→20→10을 거쳐 10의 왼쪽 자식으로 삽입된다.
삽입 후 30의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 균형 인수가 +2이고, 불균형 노드 30에서 삽입 위치까지 왼쪽→왼쪽으로 내려가므로 20을 축으로 오른쪽 회전하는 LL 유형이다. 회전 후 20이 루트가 되고 왼쪽에 10(자식 5), 오른쪽에 30(자식 25, 40)이 온다.
- RR 회전은 불균형 노드의 오른쪽-오른쪽에 삽입된 경우에 쓴다.
- LR 회전은 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우에 쓴다.
- RL 회전은 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우에 쓴다.

가능한 위상 순서는 모두 5가지이다.
그래프의 간선은 A→B, A→C, B→D, C→D, C→E, D→F, E→F이다. 진입 차수가 0인 정점은 A뿐이므로 A가 맨 앞, 모든 경로가 끝나는 F가 맨 뒤에 고정된다.
가운데 B, C, D, E는 D가 B·C 뒤에, E가 C 뒤에 와야 한다. B로 시작하면 B−C−D−E, B−C−E−D의 2가지, C로 시작하면 C−B−D−E, C−B−E−D, C−E−B−D의 3가지가 있어 합은 5가지이다.
- 3가지는 C로 시작하는 경우만 센 값이다.
- 4가지는 C−E−B−D처럼 E가 B보다 먼저 오는 순서를 빠뜨린 값이다.
- 6가지는 가능한 5가지보다 많아, 간선 제약을 어기는 순서를 포함해야만 나오는 값이다.
2단계 직후 배열은 [3, 17, 423, 124, 227, 80, 691, 95]이다.
1단계(일의 자리): 0→80, 1→691, 3→423·3, 4→124, 5→95, 7→17·227 순으로 모아 [80, 691, 423, 3, 124, 95, 17, 227]이 된다.
2단계(십의 자리, 같은 자릿값은 앞 단계 순서 유지): 0→3, 1→17, 2→423·124·227, 8→80, 9→691·95 순으로 모은다.
- [3, 17, 124, 227, 423, 80, 691, 95]: 십의 자리가 2인 원소를 백의 자리 기준으로 미리 정렬해 앞 단계 순서를 지키지 않았다.
- [17, 3, 227, 423, 124, 80, 95, 691]: 십의 자리가 0인 3보다 1인 17을 앞에 두어 십의 자리 기준 정렬이 아니다.
- [17, 3, 423, 227, 124, 80, 95, 691]: 역시 17이 3보다 앞서 있어 2단계 결과가 될 수 없다.
int adj[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
int visited[5] = { 0, };
int order[5];
int cnt = 0;
void dfs(int v) {
visited[v] = 1;
order[v] = ++cnt;
for (int i = 0; i < 5; i++) {
if (adj[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}order[2]는 5, order[3]은 3이다.
인접 행렬을 인덱스 순서로 검사하며 방문하지 않은 정점이 있으면 즉시 재귀한다.
dfs(0): order[0]=1 → dfs(1): order[1]=2 → dfs(3): order[3]=3, 더 갈 곳이 없어 복귀 → dfs(4): order[4]=4 → dfs(2): order[2]=5.
- order[2]: 2, order[3]: 4 — 정점 2는 1→4를 거친 뒤 마지막에 방문되므로 두 번째가 될 수 없다.
- order[2]: 3, order[3]: 4 — 0과 가까운 정점부터 차례로 방문하는 너비 우선 탐색의 순서이다.
- order[2]: 5, order[3]: 4 — 정점 1에서 인덱스가 작은 3을 4보다 먼저 방문하므로 order[3]은 3이다.
가장 긴 체인은 인덱스 5, 길이 3이다.
13→5, 25→1, 6→6, 21→5, 14→6, 29→5, 8→0이므로 버킷 5에 13·21·29의 3개가 연결된다.
- 인덱스 0, 길이 2: 버킷 0에는 8 하나만 저장된다.
- 인덱스 5, 길이 4: 버킷 5의 키는 3개뿐이다.
- 인덱스 6, 길이 2: 6·14의 2개로 가장 긴 체인이 아니다.