7급 국가직 자료구조론 기출문제 전 회차를 한 권으로 — PDF 전자책(문제집·정답해설집)

23년 1회차

총 25문항 · 객관식 · A4 약 1장

1 / 1

A4정답 포함← → 키 · 드래그로 넘김

7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

23년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

다음 C 코드의 시간 복잡도(time complexity)는?

void func(int n)
{
  int i, j, k = 0;
  for(i = 0; i < (n + 200); i++)
    for(j = 0; j < 300; j++)
      printf("k = %d\n", k++);
}

O(n)

O(n^2)

O(\log_2 n)

O(n\log_2 n)

정답 및 해설

이 코드의 시간 복잡도는 $O(n)$ 이다.

바깥 루프는 $n+200$ 회, 안쪽 루프는 n과 무관하게 항상 300회 돈다. printf 실행 횟수는 $(n+200) \times 300 = 300n + 60000$ 이고, 상수 계수와 상수항을 버리면 n에 비례한다.

$O(n^2)$ : 안쪽 루프도 n에 비례해야 나오는 결과인데, 안쪽은 상수 300회다.
$O(\log_2 n)$ : 반복마다 문제 크기가 절반으로 줄어드는 구조가 아니다.
$O(n\log_2 n)$ : 로그 횟수로 도는 루프가 없으므로 해당하지 않는다.

문제 2

다음 그래프(graph)에 대하여 깊이 우선 탐색(DFS, depth first search)을 하려고 한다. 시작 정점(vertex)이 B일 때, 정점 I는 몇 번째에 방문하는가? (단, B가 첫 번째 방문 정점이고, 탐색 시 인접한 정점들은 알파벳 오름차순으로 방문한다)

정답 및 해설

B에서 알파벳 오름차순으로 깊이 우선 탐색을 하면 B → E → A → C → I 순으로 진행되어, 정점 I는 다섯 번째로 방문된다.

B의 인접 정점 E·F·G 중 E로 먼저 내려가고, E의 인접 정점 A·C·I 중 A를 방문한 뒤 막혀 E로 되돌아온다. 이어 C를 방문하면 C의 미방문 인접 정점 I로 바로 내려간다.

전체 방문 순서는 B, E, A, C, I, F, D, H, G이다.

네 번째로 방문되는 정점은 I가 아니라 C이다.
여덟 번째로 방문되는 정점은 F → D 다음의 H이다.
아홉 번째(마지막)로 방문되는 정점은 G이다.

문제 3

이중 연결 리스트(doubly linked list)에 대한 설명으로 옳지 않은 것은?

1이전 노드와 이후 노드에 대한 링크(link)를 가지고 있어 양방향 탐색이 가능하다.

2단순 연결 리스트(singly linked list)에 비해 기억 장소가 추가로 소요된다.

3이진 트리(binary tree)에 활용이 가능하다.

4다항식(polynomial), 희소 행렬(sparse matrix)을 표현할 수 없다.

정답 및 해설

옳지 않은 설명은 이중 연결 리스트로 다항식·희소 행렬을 표현할 수 없다는 것이다.

연결 리스트는 다항식의 각 항(계수·지수)이나 희소 행렬의 0이 아닌 원소(행·열·값)를 노드로 저장해 표현할 수 있으며, 이중 연결 리스트도 마찬가지다.

양방향 탐색: 노드마다 이전·다음 링크가 있어 앞뒤로 이동할 수 있다(옳음).
추가 기억 장소: 링크 필드가 하나 더 있어 단순 연결 리스트보다 공간이 더 든다(옳음).
이진 트리 활용: 두 링크를 왼쪽·오른쪽 자식 포인터로 쓰면 이진 트리 노드가 된다(옳음).

문제 4

다음은 정점 간의 거리를 표시한 방향 그래프(directed graph)이다. 시작 정점이 0일 때, 정점 3과 정점 4까지 최단 경로의 거리를 바르게 연결한 것은?

정점 3 정점 4

15 7

25 8

38 11

48 12

정답 및 해설

다익스트라 방식으로 구하면 시작 정점 0에서 정점 3까지 5, 정점 4까지 7이다.

0→1은 2, 0→1→2는 2+1=3으로 직행 간선(4)보다 짧다.
정점 3: 0→1→2→3 = 3+2 = 5 (직행 8, 0→1→3의 6보다 짧음)
정점 4: 0→1→2→3→4 = 5+2 = 7

정점 3이 5, 정점 4가 8인 조합은 0→1→3→4(2+4+2) 경로의 거리로 최단이 아니다.
정점 3이 8, 정점 4가 11인 조합은 직행 간선 0→3과 0→1→4(2+9)만 본 값이다.
정점 3이 8, 정점 4가 12인 조합은 시작 정점에서 나가는 직행 간선만 본 값이다.

문제 5

어떤 트리 3개에 대한 모든 노드 개수의 합이 100이면 간선(edge) 개수의 합은?

194

295

396

497

정답 및 해설

간선 개수의 합은 97이다.

노드가 k개인 트리의 간선 수는 항상 k − 1이다. 세 트리의 노드 수를 a, b, c라 하면 간선 합은 $(a-1)+(b-1)+(c-1) = 100 - 3 = 97$ 이다.

96: 노드 합에서 4를 뺀 값으로, 트리가 4개일 때의 간선 수다.
95: 트리가 5개일 때의 간선 수다.
94: 트리가 6개일 때의 간선 수다.

문제 6

다음 하노이 탑 문제를 해결하는 파이썬(Python) 코드의 시간 복잡도는? (단, n은 원판의 개수이고 first, second, third는 기둥 번호이다)

def hanoiT(n, first, second, third):
  if n == 1:
    print("원판1 : %s 에서 %s"%(first, third))
  else:
    hanoiT(n - 1, first, third, second)
    print("원판%d : %s 에서 %s"%(n, first, third))
    hanoiT(n - 1, second, first, third)

O(n)

O(n^2)

O(2^n)

O(\log_2 n)

정답 및 해설

하노이 탑 재귀 코드의 시간 복잡도는 $O(2^n)$ 이다.

원판 n개를 옮기려면 n−1개 이동을 두 차례 재귀 호출하고 원판 하나를 옮기므로 $T(n) = 2T(n-1) + 1$ , $T(1) = 1$ 이다. 이를 풀면 $T(n) = 2^n - 1$ 로, 원판이 하나 늘 때마다 작업량이 두 배가 된다.

$O(n)$ : 재귀 호출이 한 갈래뿐인 $T(n) = T(n-1) + 1$ 의 결과다.
$O(n^2)$ : 한 갈래 재귀에서 호출마다 선형 작업을 할 때의 결과로, 두 갈래로 갈라지는 이 코드보다 훨씬 작다.
$O(\log_2 n)$ : 문제 크기가 절반씩 줄 때의 결과인데, 여기서는 1씩 줄면서 호출이 두 배로 늘어난다.

문제 7

어떤 이진 트리의 전위 순회(preorder traversal)와 중위 순회(inorder traversal)한 순서가 다음과 같을 때, 이 트리의 단말 노드만을 모두 나열한 것은?

○ 전위 순회: A, B, D, E, C, F, G, H, I
○ 중위 순회: E, D, B, A, G, F, H, C, I

1A, D, E

2B, C, D, F

3D, E, F, I

4E, G, H, I

정답 및 해설

단말 노드는 E, G, H, I이다.

전위 순회의 첫 원소 A가 루트이고, 중위 순회에서 A의 왼쪽(E, D, B)이 왼쪽 서브트리, 오른쪽(G, F, H, C, I)이 오른쪽 서브트리다. 같은 방식을 서브트리마다 재귀적으로 적용한다.

왼쪽 서브트리: 전위 B, D, E에서 루트 B, 중위 E, D가 모두 B의 왼쪽이므로 B의 왼쪽 자식 D, D의 왼쪽 자식 E가 된다. 단말은 E.
오른쪽 서브트리: 전위 C, F, G, H, I에서 루트 C, 중위에서 G, F, H는 왼쪽, I는 오른쪽이다. 다시 F를 루트로 G는 왼쪽, H는 오른쪽 자식이 된다. 단말은 G, H, I.

A, B, C, D, F는 자식이 있는 내부 노드이므로 이들이 들어간 나열은 모두 틀리다.

문제 8

다음 비어 있는 크기가 11인 해시 테이블(hash table)에 입력키가 4, 6, 15, 26, 17 순서로 저장되었다. 입력키 26이 저장된 해시 테이블의 주소는? (단, 해시 함수는 h(k) = k mod 11이고, 충돌 해결은 선형 조사법(linear probing)을 사용한다)

해시 테이블 주소	0	1	2	3	4	5	6	7	8	9	10
해시 테이블

정답 및 해설

입력키 26은 해시 테이블 주소 7에 저장된다.

k mod 11로 홈 주소를 구하고, 충돌하면 다음 주소로 한 칸씩 이동한다(선형 조사).

4: 4 mod 11 = 4 → 주소 4
6: 6 mod 11 = 6 → 주소 6
15: 15 mod 11 = 4 → 4 충돌 → 주소 5
26: 26 mod 11 = 4 → 4·5·6이 모두 차 있음 → 주소 7

주소 4는 26의 홈 주소일 뿐 이미 키 4가 차지했고, 주소 6도 키 6이 먼저 들어가 있다.

문제 9

다음은 유클리드 알고리즘(euclidean algorithm)을 사용하여 두 정수의 최대공약수(greatest common divisor)를 구하는 파이썬 프로그램이다. gcd(12, 21)를 실행한 후 count 값과 (가)에 들어갈 내용을 바르게 연결한 것은?

def gcd(m, n):
    global count
    count = count + 1
    if m < n:
        temp = m
        m = n
        n = temp
    if m % n == 0:
        return n
    else:
        return gcd(   (가)   )

count = 0
gcd(12, 21)

count (가)

12 m, m % n

22 n, n % m

33 m, n % m

43 n, m % n

정답 및 해설

count 값은 3이고, (가)에는 n, m % n이 들어간다.

유클리드 알고리즘은 gcd(m, n) = gcd(n, m mod n)이며 나머지가 0이 되면 n이 최대공약수다. 호출을 추적하면 다음과 같다.

gcd(12, 21): count=1, m < n이라 교환해 m=21, n=12 → 21 % 12 = 9 → gcd(12, 9)
gcd(12, 9): count=2 → 12 % 9 = 3 → gcd(9, 3)
gcd(9, 3): count=3 → 9 % 3 = 0 → 3 반환

count가 2인 조합: 실제 호출은 세 차례 일어나므로 맞지 않는다.
m, n % m: 교환 뒤 n < m이므로 n % m = n이 되어 gcd(21, 12)가 끝없이 반복된다.

문제 10

배열(array)로 표현한 이진 트리 중에서 최소 힙(minimum heap)에 해당하지 않는 것은?

11 3 13 7 9 10 20 17 25

21 3 13 9 7 20 17 25 10

31 3 17 7 13 25 20 9 10

41 9 3 17 10 13 7 20 25

정답 및 해설

최소 힙이 아닌 것은 1 3 13 7 9 10 20 17 25이다.

배열을 인덱스 1부터 채우면 인덱스 i의 자식은 $2i$ , $2i+1$ 이고, 최소 힙은 모든 부모 ≤ 자식이어야 한다. 위 배열에서 인덱스 3의 13은 자식(인덱스 6, 7)이 10, 20인데 10 < 13이므로 힙 조건을 어긴다.

1 3 13 9 7 20 17 25 10: 3의 자식 9·7, 13의 자식 20·17, 9의 자식 25·10 모두 부모보다 크다.
1 3 17 7 13 25 20 9 10: 3의 자식 7·13, 17의 자식 25·20, 7의 자식 9·10 모두 조건을 만족한다.
1 9 3 17 10 13 7 20 25: 9의 자식 17·10, 3의 자식 13·7, 17의 자식 20·25 모두 조건을 만족한다.

문제 11

다음 그래프에서 크루스칼 알고리즘(Kruskal algorithm)을 사용하여 만든 최소 비용 신장 트리(minimum cost spanning tree)에 대한 모든 간선의 가중치 합은?

121

225

331

433

정답 및 해설

크루스칼 알고리즘으로 만든 최소 비용 신장 트리의 가중치 합은 25이다.

간선을 가중치 오름차순으로 보며 사이클을 만들지 않는 것만 고르면 A-B(3), A-C(4), A-E(4), F-G(4), A-D(5), E-G(5)로 정점 7개를 잇는 간선 6개가 완성된다.
3+4+4+4+5+5 = 25

21은 불가능한 값이다. 그래프에서 가장 가벼운 간선 6개의 합이 이미 25이므로 신장 트리 비용은 25보다 작을 수 없다.
31은 크루스칼이 선택하지 않는 6 이상의 간선(B-C, C-E, D-G 등)이 포함된 신장 트리의 비용으로 최소가 아니다.
33도 7·8짜리 간선(B-D, E-F, D-F 등)이 섞인 경우의 비용으로 최소가 아니다.

문제 12

다음 treetest() 함수로 만들어지는 트리의 유형은?

typedef struct treeNode {
    int data;
    struct treeNode *left, *right;
} treeNode;

void treetest() {
    treeNode n1 = { 12, NULL, NULL };
    treeNode n2 = { 33, NULL, NULL };
    treeNode n3 = { 21, &n1, &n2 };
    treeNode n4 = { 74, NULL, NULL };
    treeNode n5 = { 67, NULL, &n4 };
    treeNode n6 = { 59, NULL, &n5 };
    treeNode n7 = { 46, &n3, &n6 };
    treeNode* root = &n7;
}

1스레드 이진 트리(threaded binary tree)

2완전 이진 트리(complete binary tree)

3이진 탐색 트리(binary search tree)

4포화 이진 트리(full binary tree)

정답 및 해설

treetest()가 만드는 트리는 이진 탐색 트리이다.

루트 46의 왼쪽은 21(왼쪽 12, 오른쪽 33), 오른쪽은 59 → 67 → 74가 오른쪽 자식으로만 이어진다. 모든 노드에서 왼쪽 서브트리 < 노드 < 오른쪽 서브트리가 성립한다(12 < 21 < 33 < 46 < 59 < 67 < 74).

스레드 이진 트리: 빈 링크가 NULL 그대로이며 중위 선행자·후속자를 가리키는 스레드가 없다.
완전 이진 트리: 59에 왼쪽 자식이 없는데 더 아래 레벨에 노드가 있어 왼쪽부터 빈틈없이 채워지지 않았다.
포화 이진 트리: 노드가 7개지만 4개 레벨에 걸쳐 있어 모든 레벨이 꽉 차 있지 않다.

문제 13

다음 그래프에서 프림 알고리즘(Prim algorithm)을 사용하여 최소 비용 신장 트리를 만들 때, 트리에 네 번째로 포함되는 간선은? (단, 시작 정점은 0이다)

1(0, 1)

2(1, 4)

3(2, 3)

4(4, 5)

정답 및 해설

시작 정점 0에서 프림 알고리즘을 적용하면 네 번째로 추가되는 간선은 (1, 4)이다.

트리에 인접한 간선 중 최소 가중치를 차례로 고르면 (0, 2) 1 → (2, 1) 2 → (0, 3) 3 → (1, 4) 7 → (4, 5) 4 순이다.

세 간선을 추가한 뒤 트리는 {0, 1, 2, 3}이고, 바깥으로 나가는 후보는 (1, 4) 7, (2, 4) 8, (3, 5) 9뿐이어서 가중치 7인 (1, 4)가 선택된다.

간선 (0, 1)은 두 정점이 이미 트리에 있어 사이클을 만들므로 선택되지 않는다.
간선 (2, 3)도 두 정점이 이미 트리에 포함되어 사이클을 만든다.
간선 (4, 5)는 정점 4가 트리에 들어온 뒤 다섯 번째로 추가된다.

문제 14

다음 그래프에서 정점 A부터 너비 우선 탐색(BFS, breadth first search)을 사용하여 나올 수 있는 결과로 옳지 않은 것은?

1A B C D E F

2A C B D F E

3A C F B E D

4A D C B F E

정답 및 해설

너비 우선 탐색은 같은 깊이의 정점을 모두 방문한 뒤 다음 깊이로 내려가므로, A C F B E D는 나올 수 없는 결과이다.

A와 인접한 B·C·D를 모두 방문하기 전에 깊이 2인 F를 방문했기 때문이다. 또한 깊이 2의 순서는 깊이 1에서 부모가 큐에 들어간 순서를 따라야 한다.

A B C D E F: B·C·D 순으로 방문했으므로 B의 자식 E, C의 자식 F 순서가 맞다.
A C B D F E: C·B·D 순으로 방문했으므로 C의 자식 F가 B의 자식 E보다 먼저 온다.
A D C B F E: D·C·B 순으로 방문했으므로 F, E 순서가 맞다.

문제 15

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

void func(int *array, int size) {
  int *p = array;
  *p = 100;
  *(p + 2) = 100;
  p = p + 1;
}

int main(int argc, char *argv[]) {
  int array[5] = { 2, 4, 6, 8, 10 };
  func(array, 5);
  for(int i = 0; i < 5; i++)
    printf("%d ", array[i]);
  printf("\n");
  return 0;
 }

1100 4 6 8 100

2100 4 6 100 10

3100 4 100 8 10

4100 100 68 8 10

정답 및 해설

실행 결과는 100 4 100 8 10이다.

func의 p는 array[0]을 가리키므로 *p = 100은 array[0]을, *(p + 2) = 100은 array[2]를 바꾼다. 마지막 p = p + 1은 지역 포인터만 옮길 뿐 배열 값에는 영향이 없다.

100 4 6 8 100: 마지막 원소 array[4]는 수정되지 않는다.
100 4 6 100 10: p + 2는 array[3]이 아니라 array[2]이다.
100 100 68 8 10: array[1]은 대입 대상이 아니며 원소 값이 이어 붙는 일도 없다.

문제 16

다음 인접 행렬(adjacency matrix)로 표현된 그래프에 대해 위상 정렬(topological sort)을 수행한 후, 위상 순서(topological order)에서 마지막에 위치하는 정점은? (단, 위상 정렬 과정에서 선택 가능한 정점이 여러 개인 경우 가장 작은 숫자의 정점을 선택한다)

시작 정점 ＼ 도착 정점	0	1	2	3	5	6	7
0		1		1		1
1			1
2
3		1
4	1		1		1
5						1
6				1			1
7				1

정답 및 해설

위상 순서의 마지막 정점은 2이다.

진입 차수가 0인 정점을 고르고 그 진출 간선을 지우는 과정을 반복한다. 처음 진입 차수가 0인 정점은 4뿐이며, 전체 순서는 4 → 0 → 5 → 6 → 7 → 3 → 1 → 2이다.

4 제거 → 0, 5의 진입 차수가 0 → 작은 0 선택
0 제거 → 후보는 5뿐 → 5 제거 후 6의 진입 차수가 0
6 제거 → 7 선택, 7 제거 후 3의 진입 차수가 0
3 제거 → 1 선택, 1 제거 후 2 선택

정점 2는 1과 4에서 들어오는 간선만 있고 나가는 간선이 없어 가장 늦게 남는다. 1·3·6은 모두 2보다 앞서 선택된다.

문제 17

다음 C 코드에 10개의 노드로 이루어진 이중 연결 리스트를 입력하여 수행한 후, 이중 연결 리스트에 남아 있는 노드의 개수는? (단, 10개 노드 입력 후 수행 시 start는 첫 번째 노드를 가리킨다)

typedef struct node {
  int key;
  struct node *prev, *next;
} node;

void foobar(node *start) {
    node *current = start;
    int iseven = 0;
    while(current != NULL) {
      if(iseven == 1) {
        current->prev->next = current->next;
        if(current->next != NULL)
          current->next->prev = current->prev;
      }
      current = current->next;
      iseven = 1 - iseven;
    }
}

410

정답 및 해설

수행 후 남는 노드는 5개이다.

iseven은 0과 1을 번갈아 가지며, 1일 때 현재 노드의 앞뒤 노드를 직접 연결해 현재 노드를 건너뛰게(삭제) 만든다. 첫 노드는 iseven = 0이므로 남는다.

삭제된 노드의 next는 그대로라 current = current->next로 다음 노드에 정상 진행하므로, 두 번째·네 번째·…·열 번째의 짝수째 노드 다섯 개가 삭제되고 홀수째 다섯 개가 남는다.

6개: 열 번째 노드도 짝수째라 삭제되므로 남는 수는 다섯이다.
8개: 두 개만 지우는 경우인데, 반복은 리스트 끝까지 계속된다.
10개: 삭제가 없는 경우인데, iseven이 번갈아 1이 되므로 삭제가 일어난다.

문제 18

다음 미로 찾기 문제를 스택(stack)을 이용하여 해결하고자 한다. 출발점에서 시작하여 도착점까지 가기 위해 필요한 push 연산 횟수와 pop 연산 횟수는? (단, 출발점, 도착점 좌표에 대해서는 push 연산 횟수에서 제외한다)

0	1	0	1
1	0	1	0
0	0	1	1
1	0	0	0

출발 → (0, 0) 칸, (3, 3) 칸 → 도착
방위: 위쪽 N, 아래쪽 S, 왼쪽 W, 오른쪽 E
○ 출발점은 (0, 0), 도착점은 (3, 3)이다.
○ 출발점에서 현재 좌표까지 이동 경로는 push 연산으로 현재 좌표를 스택에 저장하고, 직전 좌표로 돌아가는 경로는 pop 연산으로 현재 좌표를 스택에서 삭제하는 방법으로 만들어진다.
○ 미로의 크기는 4 × 4 2차원 배열로 구성되었고, 1은 장벽, 0은 통과할 수 있는 길이다. 4 × 4 2차원 배열 외부는 모두 장벽으로 간주하여 이 배열을 벗어날 수 없다고 가정한다.
○ 각 좌표에서 이전에 이동했던 좌표를 제외하고, N(북)에서 NE(북동), E(동), SE(남동), S(남), SW(남서), W(서), NW(북서) 순서로 검색하여 가장 먼저 찾은 이동 가능한 좌표로 이동한다. 주위 좌표가 모두 벽이거나 방문했던 곳일 경우 직전 좌표로 돌아간다.

push pop

13 0

24 0

35 2

46 2

정답 및 해설

규칙대로 탐색하면 push는 5회, pop은 2회 필요하다.

(0, 0)에서 SE (1, 1) push → NE (0, 2) push → SE (1, 3) push. (1, 3)은 주위가 모두 벽이거나 방문한 곳이라 pop하고, (0, 2)도 더 갈 곳이 없어 pop한다.

(1, 1)로 돌아와 남은 방향을 검색하면 S (2, 1) push → SE (3, 2) push → E (3, 3) 도착(도착점은 push 제외)이다.

push 3회·pop 0회: (1, 3)·(0, 2)의 막다른 길에서 되돌아오는 pop 2회가 반드시 생기므로 pop이 0일 수 없다.
push 4회·pop 0회: 마찬가지로 되돌아오는 과정이 빠져 있고, push도 실제 5회보다 적다.
push 6회·pop 2회: pop은 맞지만 push 대상이 아닌 도착점 (3, 3)까지 센 값이다.

문제 19

다음은 이중 연결 리스트를 이용하여 덱(deque)을 구현한 파이썬 코드이다. (가) ～ (라)에 들어갈 내용을 A ～ F에서 바르게 연결한 것은?

class DQNode:
   def __init__(self, data, left, right):
      self.data = data
      self.left = left
      self.right = right

class DoublyLinkedDQ:
   def __init__(self):
      self.front = None
      self.rear = None

   def insertFront(self, data):
      node = DQNode(data, None, self.front)
      if self.front == None:
         self.front = node
         self.rear = self.front
      else:
         (가)
         (나)

   def deleteRear(self):
      if self.front != None:
         data = self.rear.data
         (다)
         if self.rear == None:
            (라)
         else:
            self.rear.right = None
         return data

A. self.front = node
B. self.front = self.rear
C. self.front.left = node
D. self.front.right = node
E. self.rear = self.rear.left
F. self.rear = self.rear.right

(가) (나) (다) (라)

1A C F A

2C A E B

3C A F D

4D C E C

정답 및 해설

(가)는 self.front.left = node, (나)는 self.front = node, (다)는 self.rear = self.rear.left, (라)는 self.front = self.rear이다.

insertFront: 새 노드의 right는 이미 기존 front를 가리키므로, 기존 front의 left를 새 노드로 연결한 뒤 front를 새 노드로 옮긴다. 순서가 바뀌면 기존 front를 잃는다.

deleteRear: rear를 왼쪽 노드로 옮기고, 그 값이 None이면 노드가 하나뿐이었으므로 front도 None(현재 rear 값)으로 만든다. 아니면 새 rear의 right 연결을 끊는다.

(가)에서 front를 먼저 새 노드로 바꾸는 조합은 기존 front 참조를 잃고, rear를 right로 옮기면 항상 None이 되어 덱이 깨진다.
(다)를 self.rear = self.rear.right로 두는 조합은 rear의 right가 항상 None이라 삭제 후 연결이 맞지 않는다.
(가)를 self.front.right = node로 두는 조합은 새 노드가 front의 왼쪽에 붙어야 하므로 연결 방향이 반대이다.

문제 20

다음 C 프로그램의 실행 결과는?

#include <stdio.h>
typedef struct stack {
  int data[10]; int top;
} stack;
stack s1, s2;

void push(stack *ss, int i) {
  ss->top = ss->top + 1;
  ss->data[ss->top] = i;
}

int pop(stack *ss) {
  return ss->data[ss->top--];
}

int size(stack *ss) {
  return ((ss->top) + 1);
}

void push2(int n) {
  push(&s1, n);
}

int pop2() {
  if(size(&s2) == 0) {
    int s = size(&s1);
    for(int i = 0; i < s; i++)
      push(&s2, pop(&s1));
  }
  return pop(&s2);
}

int main(int argc, char **argv) {
  s1.top = s2.top = -1;
  push2(1);  push2(2);  push2(3);
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  push2(4);  push2(5);
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  return 0;
}

11 2 3 4 5

22 1 5 4 3

33 2 5 4 1

45 4 3 2 1

정답 및 해설

실행 결과는 1 2 3 4 5이다.

push2는 항상 s1에 넣고, pop2는 s2가 비었을 때만 s1의 원소를 모두 옮긴 뒤 s2에서 꺼낸다. 옮기면서 순서가 뒤집히므로 두 스택이 큐(FIFO)처럼 동작한다.

1, 2, 3 삽입 후 pop2: s2가 비어 s1의 3, 2, 1을 차례로 옮김 → s2 맨 위 1 출력
다음 pop2: s2에 남은 2 출력
4, 5를 s1에 삽입 후 pop2: s2에 3이 남아 있어 옮기지 않고 3 출력
다음 pop2: s2가 비어 s1의 5, 4를 옮김 → 4 출력, 마지막 pop2 → 5 출력

5 4 3 2 1 같은 후입선출 순서나 일부만 뒤집힌 순서는 s2가 빌 때만 옮기는 규칙을 무시한 결과다.

문제 21

다음 데이터를 비어 있는 AVL(Adelson-Velskii, Landis) 트리에 순서대로 삽입할 때, 완전 이진 트리에 해당하는 것만을 모두 고른 것은?

ㄱ. 1, 2, 4, 3, 6, 5
ㄴ. 2, 1, 5, 4, 6, 3
ㄷ. 3, 1, 4, 2, 5, 6
ㄹ. 4, 1, 2, 3, 6, 5

1ㄱ, ㄴ

2ㄱ, ㄹ

3ㄴ, ㄷ

4ㄷ, ㄹ

정답 및 해설

완전 이진 트리가 되는 것은 ㄱ, ㄹ이다.

삽입 후 균형 인수의 절댓값이 2가 되면 회전한다. 최종 트리는 다음과 같다(괄호 안은 왼쪽, 오른쪽 자식).

ㄱ: 1, 2, 4에서 RR 회전 → 2(1, 4), 3·6 삽입 후 5에서 루트 2가 불균형 → RR 회전 → 4(2(1, 3), 6(5, –)): 마지막 레벨이 왼쪽부터 채워져 완전 이진 트리
ㄴ: 2(1, 5(4, 6))에 3 삽입 시 루트에서 RL 회전 → 4(2(1, 3), 5(–, 6)): 5의 왼쪽이 비고 오른쪽만 있어 완전 이진 트리가 아님
ㄷ: 3(1(–, 2), 4(–, 5))에 6 삽입 시 4에서 RR 회전 → 3(1(–, 2), 5(4, 6)): 1의 왼쪽이 비어 완전 이진 트리가 아님
ㄹ: 4, 1, 2에서 LR 회전 → 2(1, 4), 3·6 삽입 후 5에서 RR 회전 → 4(2(1, 3), 6(5, –)): 완전 이진 트리

문제 22

다음 데이터를 비어 있는 2-3 트리에 순서대로 삽입하였다. 8을 삭제한 후, 트리에서 레벨 1의 값을 나열하면? (단, 루트 노드의 레벨은 0이다)

20, 14, 35, 17, 23, 10, 5, 8, 27, 31

110, 20

214, 27

38, 20, 27

417, 20, 27

정답 및 해설

8을 삭제한 뒤 레벨 1의 값은 14, 27이다.

삽입을 마치면 루트 [14], 레벨 1 [8]·[20, 27], 레벨 2 [5]·[10]·[17]·[23]·[31, 35]가 된다(8 삽입 때 [5, 8, 10]과 루트 [8, 14, 20]이 연쇄 분할되어 14가 새 루트가 되고, 27 삽입 때 27이 [20]으로 올라감).

8은 내부 노드이므로 중위 후속자 10과 교체해 단말에서 지운다. 빈 단말의 형제 [5]는 키가 하나라 빌려줄 수 없어 병합해 [5, 10]이 되고 부모가 빈다. 그 형제 [20, 27]은 키가 둘이므로 재분배해 루트의 14가 내려오고 20이 루트로 올라가며 17은 14의 오른쪽 자식이 된다. 결과는 루트 [20], 레벨 1 [14]·[27]이다.

10, 20: 10은 병합된 단말 [5, 10]에 있고, 20은 루트로 올라간다.
8, 20, 27: 8은 삭제된 키이며 20은 루트로 올라간다.
17, 20, 27: 17은 단말 노드인 레벨 2에 남는다.

문제 23

숫자 분석법(digit analysis)은 모든 키 값이 미리 알려져 있을 때 유용한 해시 함수이다. 키 집합이 다음과 같을 때, 숫자 분석법을 이용하여 십진수 두 자리의 주소를 생성하고자 한다. 두 자리 주소에 들어갈 자릿수로 가장 적절한 것은?

0001	1006	2011	3016	4021	5026	6031	7036	8041	9046
0002	1007	2012	3017	4022	5027	6032	7037	8042	9047
0003	1008	2013	3018	4023	5028	6033	7038	8043	9048
0004	1009	2014	3019	4024	5029	6034	7039	8044	9049
0005	1010	2015	3020	4025	5030	6035	7040	8045	9050

1100의 자릿수, 1의 자릿수

2100의 자릿수, 10의 자릿수

31000의 자릿수, 1의 자릿수

41000의 자릿수, 10의 자릿수

정답 및 해설

가장 적절한 자릿수는 1000의 자릿수와 1의 자릿수이다.

숫자 분석법은 키의 자릿수별 분포를 조사해 0~9가 고르게 나오는 자리를 주소로 고른다. 50개 키에서 1000의 자리와 1의 자리는 0~9가 각각 다섯 차례씩 고르게 나타나고, 두 자리를 조합하면 50개 키의 주소가 모두 달라 충돌도 없다.

100의 자릿수와 1의 자릿수: 100의 자리는 모든 키에서 0이라 사실상 한 자리만 쓰는 셈이다.
100의 자릿수와 10의 자릿수: 100의 자리는 항상 0이고 10의 자리도 치우쳐 충돌이 많다.
1000의 자릿수와 10의 자릿수: 10의 자리는 0~5만 나오고 빈도도 고르지 않아 1의 자리보다 분포가 나쁘다.

문제 24

다음 파이썬 프로그램의 실행 결과는?

import queue

values=queue.Queue()
for i in range(20):
   if i % 3 == 0:
      values.put(i)
   elif i % 4 == 0:
      values.get()
   elif i % 5 == 0:
      values.get()
print(values.get(), values.get())

115

218

315 18

412 15 18

정답 및 해설

실행 결과는 15 18이다.

i가 3의 배수이면 put, 아니면서 4의 배수 또는 5의 배수이면 get(맨 앞 삭제)을 한다. 조건을 위에서부터 검사하므로 12처럼 3과 4의 공배수는 put만 한다.

i=0, 3: put → [0, 3] / i=4: get → [3] / i=5: get → []
i=6: put → [6] / i=8: get → [] / i=9: put → [9] / i=10: get → []
i=12, 15: put → [12, 15] / i=16: get → [15] / i=18: put → [15, 18]

마지막 print는 get을 두 차례 호출해 15와 18을 차례로 출력하므로, 값 하나나 세 개를 출력하는 결과는 맞지 않는다.

문제 25

다음 트리는 노드에서 키와 값이 무엇인지 알 수는 없지만 이진 탐색 트리라고 가정했을 때, 이에 대한 설명으로 옳지 않은 것은? (단, 루트 노드만 있는 경우에 트리 높이는 0이다)

1트리의 높이는 4이다.

2AVL 트리에 해당한다.

3C 노드의 중위 후속자(inorder successor)는 M 노드이다.

4높이를 증가시키지 않고 트리에 추가할 수 있는 최대 노드 수는 18개이다.

정답 및 해설

C의 중위 후속자는 오른쪽 서브트리에서 가장 왼쪽 노드인 K이므로, M이라는 설명이 옳지 않다.

C의 오른쪽 자식 G에서 왼쪽 자식을 끝까지 따라가면 K에 도달한다. M은 L의 오른쪽 자식으로 C 서브트리에서 가장 큰 노드이다.

트리의 높이: A-C-G-L-M 경로가 간선 4개로 가장 길어 높이 4가 맞다.
AVL 여부: 모든 노드에서 좌우 서브트리 높이 차가 1 이하이다(A는 2와 3, C는 1과 2, G는 0과 1).
추가 가능 노드 수: 높이 4인 이진 트리의 최대 노드 수는 $2^{5}-1=31$ 이고 현재 노드가 13개이므로 18개를 더 넣을 수 있다.

7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

23년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

다음 C 코드의 시간 복잡도(time complexity)는?

void func(int n)
{
  int i, j, k = 0;
  for(i = 0; i < (n + 200); i++)
    for(j = 0; j < 300; j++)
      printf("k = %d\n", k++);
}

O(n)

O(n^2)

O(\log_2 n)

O(n\log_2 n)

정답 및 해설

이 코드의 시간 복잡도는 $O(n)$ 이다.

$O(n^2)$ : 안쪽 루프도 n에 비례해야 나오는 결과인데, 안쪽은 상수 300회다.
$O(\log_2 n)$ : 반복마다 문제 크기가 절반으로 줄어드는 구조가 아니다.
$O(n\log_2 n)$ : 로그 횟수로 도는 루프가 없으므로 해당하지 않는다.

문제 2

정답 및 해설

B에서 알파벳 오름차순으로 깊이 우선 탐색을 하면 B → E → A → C → I 순으로 진행되어, 정점 I는 다섯 번째로 방문된다.

전체 방문 순서는 B, E, A, C, I, F, D, H, G이다.

네 번째로 방문되는 정점은 I가 아니라 C이다.
여덟 번째로 방문되는 정점은 F → D 다음의 H이다.
아홉 번째(마지막)로 방문되는 정점은 G이다.

문제 3

이중 연결 리스트(doubly linked list)에 대한 설명으로 옳지 않은 것은?

1이전 노드와 이후 노드에 대한 링크(link)를 가지고 있어 양방향 탐색이 가능하다.

2단순 연결 리스트(singly linked list)에 비해 기억 장소가 추가로 소요된다.

3이진 트리(binary tree)에 활용이 가능하다.

4다항식(polynomial), 희소 행렬(sparse matrix)을 표현할 수 없다.

정답 및 해설

옳지 않은 설명은 이중 연결 리스트로 다항식·희소 행렬을 표현할 수 없다는 것이다.

양방향 탐색: 노드마다 이전·다음 링크가 있어 앞뒤로 이동할 수 있다(옳음).
추가 기억 장소: 링크 필드가 하나 더 있어 단순 연결 리스트보다 공간이 더 든다(옳음).
이진 트리 활용: 두 링크를 왼쪽·오른쪽 자식 포인터로 쓰면 이진 트리 노드가 된다(옳음).

문제 4

15 7

25 8

38 11

48 12

정답 및 해설

다익스트라 방식으로 구하면 시작 정점 0에서 정점 3까지 5, 정점 4까지 7이다.

0→1은 2, 0→1→2는 2+1=3으로 직행 간선(4)보다 짧다.
정점 3: 0→1→2→3 = 3+2 = 5 (직행 8, 0→1→3의 6보다 짧음)
정점 4: 0→1→2→3→4 = 5+2 = 7

정점 3이 5, 정점 4가 8인 조합은 0→1→3→4(2+4+2) 경로의 거리로 최단이 아니다.
정점 3이 8, 정점 4가 11인 조합은 직행 간선 0→3과 0→1→4(2+9)만 본 값이다.
정점 3이 8, 정점 4가 12인 조합은 시작 정점에서 나가는 직행 간선만 본 값이다.

문제 5

어떤 트리 3개에 대한 모든 노드 개수의 합이 100이면 간선(edge) 개수의 합은?

194

295

396

497

정답 및 해설

간선 개수의 합은 97이다.

노드가 k개인 트리의 간선 수는 항상 k − 1이다. 세 트리의 노드 수를 a, b, c라 하면 간선 합은 $(a-1)+(b-1)+(c-1) = 100 - 3 = 97$ 이다.

96: 노드 합에서 4를 뺀 값으로, 트리가 4개일 때의 간선 수다.
95: 트리가 5개일 때의 간선 수다.
94: 트리가 6개일 때의 간선 수다.

문제 6

다음 하노이 탑 문제를 해결하는 파이썬(Python) 코드의 시간 복잡도는? (단, n은 원판의 개수이고 first, second, third는 기둥 번호이다)

def hanoiT(n, first, second, third):
  if n == 1:
    print("원판1 : %s 에서 %s"%(first, third))
  else:
    hanoiT(n - 1, first, third, second)
    print("원판%d : %s 에서 %s"%(n, first, third))
    hanoiT(n - 1, second, first, third)

O(n)

O(n^2)

O(2^n)

O(\log_2 n)

정답 및 해설

하노이 탑 재귀 코드의 시간 복잡도는 $O(2^n)$ 이다.

$O(n)$ : 재귀 호출이 한 갈래뿐인 $T(n) = T(n-1) + 1$ 의 결과다.
$O(n^2)$ : 한 갈래 재귀에서 호출마다 선형 작업을 할 때의 결과로, 두 갈래로 갈라지는 이 코드보다 훨씬 작다.
$O(\log_2 n)$ : 문제 크기가 절반씩 줄 때의 결과인데, 여기서는 1씩 줄면서 호출이 두 배로 늘어난다.

문제 7

어떤 이진 트리의 전위 순회(preorder traversal)와 중위 순회(inorder traversal)한 순서가 다음과 같을 때, 이 트리의 단말 노드만을 모두 나열한 것은?

○ 전위 순회: A, B, D, E, C, F, G, H, I
○ 중위 순회: E, D, B, A, G, F, H, C, I

1A, D, E

2B, C, D, F

3D, E, F, I

4E, G, H, I

정답 및 해설

단말 노드는 E, G, H, I이다.

왼쪽 서브트리: 전위 B, D, E에서 루트 B, 중위 E, D가 모두 B의 왼쪽이므로 B의 왼쪽 자식 D, D의 왼쪽 자식 E가 된다. 단말은 E.
오른쪽 서브트리: 전위 C, F, G, H, I에서 루트 C, 중위에서 G, F, H는 왼쪽, I는 오른쪽이다. 다시 F를 루트로 G는 왼쪽, H는 오른쪽 자식이 된다. 단말은 G, H, I.

A, B, C, D, F는 자식이 있는 내부 노드이므로 이들이 들어간 나열은 모두 틀리다.

문제 8

해시 테이블 주소	0	1	2	3	4	5	6	7	8	9	10
해시 테이블

정답 및 해설

입력키 26은 해시 테이블 주소 7에 저장된다.

k mod 11로 홈 주소를 구하고, 충돌하면 다음 주소로 한 칸씩 이동한다(선형 조사).

4: 4 mod 11 = 4 → 주소 4
6: 6 mod 11 = 6 → 주소 6
15: 15 mod 11 = 4 → 4 충돌 → 주소 5
26: 26 mod 11 = 4 → 4·5·6이 모두 차 있음 → 주소 7

주소 4는 26의 홈 주소일 뿐 이미 키 4가 차지했고, 주소 6도 키 6이 먼저 들어가 있다.

문제 9

def gcd(m, n):
    global count
    count = count + 1
    if m < n:
        temp = m
        m = n
        n = temp
    if m % n == 0:
        return n
    else:
        return gcd(   (가)   )

count = 0
gcd(12, 21)

count (가)

12 m, m % n

22 n, n % m

33 m, n % m

43 n, m % n

정답 및 해설

count 값은 3이고, (가)에는 n, m % n이 들어간다.

유클리드 알고리즘은 gcd(m, n) = gcd(n, m mod n)이며 나머지가 0이 되면 n이 최대공약수다. 호출을 추적하면 다음과 같다.

gcd(12, 21): count=1, m < n이라 교환해 m=21, n=12 → 21 % 12 = 9 → gcd(12, 9)
gcd(12, 9): count=2 → 12 % 9 = 3 → gcd(9, 3)
gcd(9, 3): count=3 → 9 % 3 = 0 → 3 반환

count가 2인 조합: 실제 호출은 세 차례 일어나므로 맞지 않는다.
m, n % m: 교환 뒤 n < m이므로 n % m = n이 되어 gcd(21, 12)가 끝없이 반복된다.

문제 10

배열(array)로 표현한 이진 트리 중에서 최소 힙(minimum heap)에 해당하지 않는 것은?

11 3 13 7 9 10 20 17 25

21 3 13 9 7 20 17 25 10

31 3 17 7 13 25 20 9 10

41 9 3 17 10 13 7 20 25

정답 및 해설

최소 힙이 아닌 것은 1 3 13 7 9 10 20 17 25이다.

1 3 13 9 7 20 17 25 10: 3의 자식 9·7, 13의 자식 20·17, 9의 자식 25·10 모두 부모보다 크다.
1 3 17 7 13 25 20 9 10: 3의 자식 7·13, 17의 자식 25·20, 7의 자식 9·10 모두 조건을 만족한다.
1 9 3 17 10 13 7 20 25: 9의 자식 17·10, 3의 자식 13·7, 17의 자식 20·25 모두 조건을 만족한다.

문제 11

다음 그래프에서 크루스칼 알고리즘(Kruskal algorithm)을 사용하여 만든 최소 비용 신장 트리(minimum cost spanning tree)에 대한 모든 간선의 가중치 합은?

121

225

331

433

정답 및 해설

크루스칼 알고리즘으로 만든 최소 비용 신장 트리의 가중치 합은 25이다.

21은 불가능한 값이다. 그래프에서 가장 가벼운 간선 6개의 합이 이미 25이므로 신장 트리 비용은 25보다 작을 수 없다.
31은 크루스칼이 선택하지 않는 6 이상의 간선(B-C, C-E, D-G 등)이 포함된 신장 트리의 비용으로 최소가 아니다.
33도 7·8짜리 간선(B-D, E-F, D-F 등)이 섞인 경우의 비용으로 최소가 아니다.

문제 12

다음 treetest() 함수로 만들어지는 트리의 유형은?

typedef struct treeNode {
    int data;
    struct treeNode *left, *right;
} treeNode;

void treetest() {
    treeNode n1 = { 12, NULL, NULL };
    treeNode n2 = { 33, NULL, NULL };
    treeNode n3 = { 21, &n1, &n2 };
    treeNode n4 = { 74, NULL, NULL };
    treeNode n5 = { 67, NULL, &n4 };
    treeNode n6 = { 59, NULL, &n5 };
    treeNode n7 = { 46, &n3, &n6 };
    treeNode* root = &n7;
}

1스레드 이진 트리(threaded binary tree)

2완전 이진 트리(complete binary tree)

3이진 탐색 트리(binary search tree)

4포화 이진 트리(full binary tree)

정답 및 해설

treetest()가 만드는 트리는 이진 탐색 트리이다.

스레드 이진 트리: 빈 링크가 NULL 그대로이며 중위 선행자·후속자를 가리키는 스레드가 없다.
완전 이진 트리: 59에 왼쪽 자식이 없는데 더 아래 레벨에 노드가 있어 왼쪽부터 빈틈없이 채워지지 않았다.
포화 이진 트리: 노드가 7개지만 4개 레벨에 걸쳐 있어 모든 레벨이 꽉 차 있지 않다.

문제 13

다음 그래프에서 프림 알고리즘(Prim algorithm)을 사용하여 최소 비용 신장 트리를 만들 때, 트리에 네 번째로 포함되는 간선은? (단, 시작 정점은 0이다)

1(0, 1)

2(1, 4)

3(2, 3)

4(4, 5)

정답 및 해설

시작 정점 0에서 프림 알고리즘을 적용하면 네 번째로 추가되는 간선은 (1, 4)이다.

트리에 인접한 간선 중 최소 가중치를 차례로 고르면 (0, 2) 1 → (2, 1) 2 → (0, 3) 3 → (1, 4) 7 → (4, 5) 4 순이다.

세 간선을 추가한 뒤 트리는 {0, 1, 2, 3}이고, 바깥으로 나가는 후보는 (1, 4) 7, (2, 4) 8, (3, 5) 9뿐이어서 가중치 7인 (1, 4)가 선택된다.

간선 (0, 1)은 두 정점이 이미 트리에 있어 사이클을 만들므로 선택되지 않는다.
간선 (2, 3)도 두 정점이 이미 트리에 포함되어 사이클을 만든다.
간선 (4, 5)는 정점 4가 트리에 들어온 뒤 다섯 번째로 추가된다.

문제 14

다음 그래프에서 정점 A부터 너비 우선 탐색(BFS, breadth first search)을 사용하여 나올 수 있는 결과로 옳지 않은 것은?

1A B C D E F

2A C B D F E

3A C F B E D

4A D C B F E

정답 및 해설

너비 우선 탐색은 같은 깊이의 정점을 모두 방문한 뒤 다음 깊이로 내려가므로, A C F B E D는 나올 수 없는 결과이다.

A와 인접한 B·C·D를 모두 방문하기 전에 깊이 2인 F를 방문했기 때문이다. 또한 깊이 2의 순서는 깊이 1에서 부모가 큐에 들어간 순서를 따라야 한다.

A B C D E F: B·C·D 순으로 방문했으므로 B의 자식 E, C의 자식 F 순서가 맞다.
A C B D F E: C·B·D 순으로 방문했으므로 C의 자식 F가 B의 자식 E보다 먼저 온다.
A D C B F E: D·C·B 순으로 방문했으므로 F, E 순서가 맞다.

문제 15

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

void func(int *array, int size) {
  int *p = array;
  *p = 100;
  *(p + 2) = 100;
  p = p + 1;
}

int main(int argc, char *argv[]) {
  int array[5] = { 2, 4, 6, 8, 10 };
  func(array, 5);
  for(int i = 0; i < 5; i++)
    printf("%d ", array[i]);
  printf("\n");
  return 0;
 }

1100 4 6 8 100

2100 4 6 100 10

3100 4 100 8 10

4100 100 68 8 10

정답 및 해설

실행 결과는 100 4 100 8 10이다.

func의 p는 array[0]을 가리키므로 *p = 100은 array[0]을, *(p + 2) = 100은 array[2]를 바꾼다. 마지막 p = p + 1은 지역 포인터만 옮길 뿐 배열 값에는 영향이 없다.

100 4 6 8 100: 마지막 원소 array[4]는 수정되지 않는다.
100 4 6 100 10: p + 2는 array[3]이 아니라 array[2]이다.
100 100 68 8 10: array[1]은 대입 대상이 아니며 원소 값이 이어 붙는 일도 없다.

문제 16

시작 정점 ＼ 도착 정점	0	1	2	3	5	6	7
0		1		1		1
1			1
2
3		1
4	1		1		1
5						1
6				1			1
7				1

정답 및 해설

위상 순서의 마지막 정점은 2이다.

4 제거 → 0, 5의 진입 차수가 0 → 작은 0 선택
0 제거 → 후보는 5뿐 → 5 제거 후 6의 진입 차수가 0
6 제거 → 7 선택, 7 제거 후 3의 진입 차수가 0
3 제거 → 1 선택, 1 제거 후 2 선택

정점 2는 1과 4에서 들어오는 간선만 있고 나가는 간선이 없어 가장 늦게 남는다. 1·3·6은 모두 2보다 앞서 선택된다.

문제 17

typedef struct node {
  int key;
  struct node *prev, *next;
} node;

void foobar(node *start) {
    node *current = start;
    int iseven = 0;
    while(current != NULL) {
      if(iseven == 1) {
        current->prev->next = current->next;
        if(current->next != NULL)
          current->next->prev = current->prev;
      }
      current = current->next;
      iseven = 1 - iseven;
    }
}

410

정답 및 해설

수행 후 남는 노드는 5개이다.

iseven은 0과 1을 번갈아 가지며, 1일 때 현재 노드의 앞뒤 노드를 직접 연결해 현재 노드를 건너뛰게(삭제) 만든다. 첫 노드는 iseven = 0이므로 남는다.

6개: 열 번째 노드도 짝수째라 삭제되므로 남는 수는 다섯이다.
8개: 두 개만 지우는 경우인데, 반복은 리스트 끝까지 계속된다.
10개: 삭제가 없는 경우인데, iseven이 번갈아 1이 되므로 삭제가 일어난다.

문제 18

0	1	0	1
1	0	1	0
0	0	1	1
1	0	0	0

push pop

13 0

24 0

35 2

46 2

정답 및 해설

규칙대로 탐색하면 push는 5회, pop은 2회 필요하다.

(0, 0)에서 SE (1, 1) push → NE (0, 2) push → SE (1, 3) push. (1, 3)은 주위가 모두 벽이거나 방문한 곳이라 pop하고, (0, 2)도 더 갈 곳이 없어 pop한다.

(1, 1)로 돌아와 남은 방향을 검색하면 S (2, 1) push → SE (3, 2) push → E (3, 3) 도착(도착점은 push 제외)이다.

push 3회·pop 0회: (1, 3)·(0, 2)의 막다른 길에서 되돌아오는 pop 2회가 반드시 생기므로 pop이 0일 수 없다.
push 4회·pop 0회: 마찬가지로 되돌아오는 과정이 빠져 있고, push도 실제 5회보다 적다.
push 6회·pop 2회: pop은 맞지만 push 대상이 아닌 도착점 (3, 3)까지 센 값이다.

문제 19

다음은 이중 연결 리스트를 이용하여 덱(deque)을 구현한 파이썬 코드이다. (가) ～ (라)에 들어갈 내용을 A ～ F에서 바르게 연결한 것은?

class DQNode:
   def __init__(self, data, left, right):
      self.data = data
      self.left = left
      self.right = right

class DoublyLinkedDQ:
   def __init__(self):
      self.front = None
      self.rear = None

   def insertFront(self, data):
      node = DQNode(data, None, self.front)
      if self.front == None:
         self.front = node
         self.rear = self.front
      else:
         (가)
         (나)

   def deleteRear(self):
      if self.front != None:
         data = self.rear.data
         (다)
         if self.rear == None:
            (라)
         else:
            self.rear.right = None
         return data

A. self.front = node
B. self.front = self.rear
C. self.front.left = node
D. self.front.right = node
E. self.rear = self.rear.left
F. self.rear = self.rear.right

(가) (나) (다) (라)

1A C F A

2C A E B

3C A F D

4D C E C

정답 및 해설

(가)는 self.front.left = node, (나)는 self.front = node, (다)는 self.rear = self.rear.left, (라)는 self.front = self.rear이다.

(가)에서 front를 먼저 새 노드로 바꾸는 조합은 기존 front 참조를 잃고, rear를 right로 옮기면 항상 None이 되어 덱이 깨진다.
(다)를 self.rear = self.rear.right로 두는 조합은 rear의 right가 항상 None이라 삭제 후 연결이 맞지 않는다.
(가)를 self.front.right = node로 두는 조합은 새 노드가 front의 왼쪽에 붙어야 하므로 연결 방향이 반대이다.

문제 20

다음 C 프로그램의 실행 결과는?

#include <stdio.h>
typedef struct stack {
  int data[10]; int top;
} stack;
stack s1, s2;

void push(stack *ss, int i) {
  ss->top = ss->top + 1;
  ss->data[ss->top] = i;
}

int pop(stack *ss) {
  return ss->data[ss->top--];
}

int size(stack *ss) {
  return ((ss->top) + 1);
}

void push2(int n) {
  push(&s1, n);
}

int pop2() {
  if(size(&s2) == 0) {
    int s = size(&s1);
    for(int i = 0; i < s; i++)
      push(&s2, pop(&s1));
  }
  return pop(&s2);
}

int main(int argc, char **argv) {
  s1.top = s2.top = -1;
  push2(1);  push2(2);  push2(3);
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  push2(4);  push2(5);
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  printf("%d  ", pop2());
  return 0;
}

11 2 3 4 5

22 1 5 4 3

33 2 5 4 1

45 4 3 2 1

정답 및 해설

실행 결과는 1 2 3 4 5이다.

1, 2, 3 삽입 후 pop2: s2가 비어 s1의 3, 2, 1을 차례로 옮김 → s2 맨 위 1 출력
다음 pop2: s2에 남은 2 출력
4, 5를 s1에 삽입 후 pop2: s2에 3이 남아 있어 옮기지 않고 3 출력
다음 pop2: s2가 비어 s1의 5, 4를 옮김 → 4 출력, 마지막 pop2 → 5 출력

5 4 3 2 1 같은 후입선출 순서나 일부만 뒤집힌 순서는 s2가 빌 때만 옮기는 규칙을 무시한 결과다.

문제 21

다음 데이터를 비어 있는 AVL(Adelson-Velskii, Landis) 트리에 순서대로 삽입할 때, 완전 이진 트리에 해당하는 것만을 모두 고른 것은?

ㄱ. 1, 2, 4, 3, 6, 5
ㄴ. 2, 1, 5, 4, 6, 3
ㄷ. 3, 1, 4, 2, 5, 6
ㄹ. 4, 1, 2, 3, 6, 5

1ㄱ, ㄴ

2ㄱ, ㄹ

3ㄴ, ㄷ

4ㄷ, ㄹ

정답 및 해설

완전 이진 트리가 되는 것은 ㄱ, ㄹ이다.

삽입 후 균형 인수의 절댓값이 2가 되면 회전한다. 최종 트리는 다음과 같다(괄호 안은 왼쪽, 오른쪽 자식).

ㄱ: 1, 2, 4에서 RR 회전 → 2(1, 4), 3·6 삽입 후 5에서 루트 2가 불균형 → RR 회전 → 4(2(1, 3), 6(5, –)): 마지막 레벨이 왼쪽부터 채워져 완전 이진 트리
ㄴ: 2(1, 5(4, 6))에 3 삽입 시 루트에서 RL 회전 → 4(2(1, 3), 5(–, 6)): 5의 왼쪽이 비고 오른쪽만 있어 완전 이진 트리가 아님
ㄷ: 3(1(–, 2), 4(–, 5))에 6 삽입 시 4에서 RR 회전 → 3(1(–, 2), 5(4, 6)): 1의 왼쪽이 비어 완전 이진 트리가 아님
ㄹ: 4, 1, 2에서 LR 회전 → 2(1, 4), 3·6 삽입 후 5에서 RR 회전 → 4(2(1, 3), 6(5, –)): 완전 이진 트리

문제 22

다음 데이터를 비어 있는 2-3 트리에 순서대로 삽입하였다. 8을 삭제한 후, 트리에서 레벨 1의 값을 나열하면? (단, 루트 노드의 레벨은 0이다)

20, 14, 35, 17, 23, 10, 5, 8, 27, 31

110, 20

214, 27

38, 20, 27

417, 20, 27

정답 및 해설

8을 삭제한 뒤 레벨 1의 값은 14, 27이다.

10, 20: 10은 병합된 단말 [5, 10]에 있고, 20은 루트로 올라간다.
8, 20, 27: 8은 삭제된 키이며 20은 루트로 올라간다.
17, 20, 27: 17은 단말 노드인 레벨 2에 남는다.

문제 23

0001	1006	2011	3016	4021	5026	6031	7036	8041	9046
0002	1007	2012	3017	4022	5027	6032	7037	8042	9047
0003	1008	2013	3018	4023	5028	6033	7038	8043	9048
0004	1009	2014	3019	4024	5029	6034	7039	8044	9049
0005	1010	2015	3020	4025	5030	6035	7040	8045	9050

1100의 자릿수, 1의 자릿수

2100의 자릿수, 10의 자릿수

31000의 자릿수, 1의 자릿수

41000의 자릿수, 10의 자릿수

정답 및 해설

가장 적절한 자릿수는 1000의 자릿수와 1의 자릿수이다.

100의 자릿수와 1의 자릿수: 100의 자리는 모든 키에서 0이라 사실상 한 자리만 쓰는 셈이다.
100의 자릿수와 10의 자릿수: 100의 자리는 항상 0이고 10의 자리도 치우쳐 충돌이 많다.
1000의 자릿수와 10의 자릿수: 10의 자리는 0~5만 나오고 빈도도 고르지 않아 1의 자리보다 분포가 나쁘다.

문제 24

다음 파이썬 프로그램의 실행 결과는?

import queue

values=queue.Queue()
for i in range(20):
   if i % 3 == 0:
      values.put(i)
   elif i % 4 == 0:
      values.get()
   elif i % 5 == 0:
      values.get()
print(values.get(), values.get())

115

218

315 18

412 15 18

정답 및 해설

실행 결과는 15 18이다.

i=0, 3: put → [0, 3] / i=4: get → [3] / i=5: get → []
i=6: put → [6] / i=8: get → [] / i=9: put → [9] / i=10: get → []
i=12, 15: put → [12, 15] / i=16: get → [15] / i=18: put → [15, 18]

마지막 print는 get을 두 차례 호출해 15와 18을 차례로 출력하므로, 값 하나나 세 개를 출력하는 결과는 맞지 않는다.

문제 25

1트리의 높이는 4이다.

2AVL 트리에 해당한다.

3C 노드의 중위 후속자(inorder successor)는 M 노드이다.

4높이를 증가시키지 않고 트리에 추가할 수 있는 최대 노드 수는 18개이다.

정답 및 해설

C의 중위 후속자는 오른쪽 서브트리에서 가장 왼쪽 노드인 K이므로, M이라는 설명이 옳지 않다.

C의 오른쪽 자식 G에서 왼쪽 자식을 끝까지 따라가면 K에 도달한다. M은 L의 오른쪽 자식으로 C 서브트리에서 가장 큰 노드이다.

트리의 높이: A-C-G-L-M 경로가 간선 4개로 가장 길어 높이 4가 맞다.
AVL 여부: 모든 노드에서 좌우 서브트리 높이 차가 1 이하이다(A는 2와 3, C는 1과 2, G는 0과 1).
추가 가능 노드 수: 높이 4인 이진 트리의 최대 노드 수는 $2^{5}-1=31$ 이고 현재 노드가 13개이므로 18개를 더 넣을 수 있다.