[7급 국가직 자료구조론] 11년 1회차
7급 국가직 자료구조론 기출문제

11년 1회차

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

1 / 1
A4정답 포함
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

11년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
희소 행렬에 대한 설명으로 옳지 않은 것은?
1대부분의 원소 값이 0으로 구성되어 있다.
22차원 배열로 표현하면 특정 항목의 접근이 용이하다.
3연결 리스트 구조로 표현하더라도 행렬의 덧셈 연산을 할 수 있다.
4연결 리스트 구조로 표현하면 기억공간을 낭비하게 된다.
정답 및 해설

연결 리스트로 희소 행렬을 표현하면 0이 아닌 원소만 저장하므로 오히려 기억공간이 절약된다. 따라서 기억공간을 낭비한다는 설명이 옳지 않다.

희소 행렬은 0이 대부분이라 2차원 배열에 그대로 담으면 0을 저장하는 데 공간이 낭비되고, 이를 피하려고 (행, 열, 값) 형태의 3원소 배열이나 연결 리스트를 쓴다.

  • 대부분의 원소가 0이라는 것이 희소 행렬의 정의이다.
  • 2차원 배열은 첨자로 바로 계산해 접근하므로 특정 항목 접근이 쉽다.
  • 연결 리스트로 표현해도 행·열 순서로 노드를 비교·병합하면 행렬 덧셈이 가능하다.
문제 2
알고리즘이 갖추어야 할 조건으로 옳지 않은 것은?
1적어도 하나 이상의 출력 결과를 생성해야 한다.
2각 명령어들은 명확하고 모호하지 않아야 한다.
3어떤 경우에도 유한 번의 수행 단계 후에는 반드시 종료해야 한다.
4직접 수행 가능한 컴퓨터 프로그래밍 언어로만 작성되어야 한다.
정답 및 해설

알고리즘은 특정 프로그래밍 언어에 묶이지 않으며 자연어·의사코드·순서도 등으로도 기술할 수 있으므로, 프로그래밍 언어로만 작성해야 한다는 설명이 옳지 않다.

알고리즘의 조건은 입력(0개 이상), 출력(1개 이상), 명확성, 유한성, 유효성이다.

  • 하나 이상의 출력을 내야 한다는 것은 출력 조건이다.
  • 명령이 모호하지 않아야 한다는 것은 명확성 조건이다.
  • 유한 단계 후 반드시 종료해야 한다는 것은 유한성 조건이다.
문제 3
다음 자료 구조 중에서 비선형 구조로만 묶은 것은?
ㄱ. 스택(stack)
ㄴ. 트리(tree)
ㄷ. 연결 리스트(linked list)
ㄹ. 그래프(graph)
1ㄱ, ㄴ
2ㄱ, ㄷ
3ㄴ, ㄷ
4ㄴ, ㄹ
정답 및 해설

비선형 구조로만 묶인 것은 트리와 그래프이다.

선형 구조는 원소가 한 줄로 앞뒤 1:1 관계를 이루고, 비선형 구조는 한 원소가 여러 원소와 1:다 또는 다:다 관계를 가진다.

  • 스택은 한쪽 끝에서만 삽입·삭제하는 선형 구조이다.
  • 연결 리스트는 포인터로 원소를 한 줄로 잇는 선형 구조이다.
문제 4
다음 데이터를 순서대로 입력하여 이진 탐색 트리를 만들 경우, 단말(terminal) 노드의 개수는?
13 17 8 26 55 32 21 6 34 22 3 10
14
25
36
47
정답 및 해설

이진 탐색 트리를 만들면 단말 노드는 3, 10, 22, 34의 4개이다.

13을 루트로, 작으면 왼쪽·크면 오른쪽에 넣으면 13의 왼쪽에 8(자식 6, 10), 6의 왼쪽에 3이 붙는다.
13의 오른쪽에는 17 → 26 → 55가 이어지고, 26의 왼쪽에 21(오른쪽 자식 22), 55의 왼쪽에 32(오른쪽 자식 34)가 붙는다.

자식이 없는 노드만 세면 3, 10, 22, 34이며, 6·21·32는 각각 자식이 하나씩 있어 단말 노드가 아니다.

문제 5
다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것은? (단, 각 정렬 방식은 일반적인 경우만 고려한다)
1합병 정렬(merge sort)
2선택 정렬(selection sort)
3버블 정렬(bubble sort)
4히프 정렬(heap sort)
정답 및 해설

추가 기억공간을 가장 많이 요구하는 것은 합병 정렬이다.

합병 정렬은 두 부분 배열을 합칠 때 결과를 담을 임시 배열이 필요해 입력 크기에 비례하는 O(n)O(n)의 추가 공간을 쓴다.

  • 선택 정렬은 제자리에서 교환만 하므로 상수 크기의 추가 공간이면 된다.
  • 버블 정렬도 인접 원소 교환만 하는 제자리 정렬이다.
  • 히프 정렬은 배열 자체를 히프로 만들어 정렬하므로 상수 크기의 추가 공간이면 된다.
문제 6
레드-블랙 트리에 대한 설명으로 옳지 않은 것은? (단, 노드의 개수는 n이다)
1이진 탐색 트리의 일종이며, 각 노드는 레드 또는 블랙의 색상을 부여받는다.
2부모-자식 관계에 있는 두 노드는 동일한 색을 가져서는 안된다.
3레드-블랙 트리의 높이는 항상 O(log⁡n)O(\log n)이 된다.
4삽입과 삭제 연산의 시간 복잡도는 O(log⁡n)O(\log n)이다.
정답 및 해설

레드-블랙 트리에서 금지되는 것은 레드 노드의 자식이 레드인 경우뿐이므로, 부모와 자식이 같은 색이면 안 된다는 설명이 옳지 않다.

블랙 부모 아래 블랙 자식은 허용되며, 루트에서 각 리프까지 경로의 블랙 노드 수가 같다는 조건으로 균형을 유지한다.

  • 레드-블랙 트리는 각 노드에 레드 또는 블랙 색을 부여한 이진 탐색 트리이다.
  • 색 규칙 덕분에 최장 경로가 최단 경로의 2배를 넘지 않아 높이가 로그 수준으로 유지된다.
  • 높이가 로그 수준이므로 삽입·삭제(재색칠·회전 포함)도 로그 시간에 끝난다.
문제 7
비교가 아닌 분배에 의한 정렬(sorting by distribution) 방식으로 옳은 것은?
1기수 정렬(radix sort)
2버블 정렬(bubble sort)
3퀵 정렬(quick sort)
4히프 정렬(heap sort)
정답 및 해설

비교 없이 분배로 정렬하는 방식은 기수 정렬이다.

기수 정렬은 키의 각 자릿값에 따라 레코드를 버킷(큐)에 분배했다가 순서대로 모으는 과정을 자릿수만큼 반복한다.

  • 버블 정렬은 인접한 두 원소를 비교해 교환하는 비교 기반 정렬이다.
  • 퀵 정렬은 피벗과 비교해 분할하는 비교 기반 정렬이다.
  • 히프 정렬은 부모·자식 키를 비교해 히프를 유지하는 비교 기반 정렬이다.
문제 8
다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양, 서울에서 인천, 서울에서 수원, 서울에서 대전까지 각각 최단 경로 값들을 구하고자 한다. 각각 최단 경로 값들의 합으로 옳은 것은? (단, ∞는 두 도시 간의 연결이 없음을 의미한다)
서울안양인천수원대전
서울0102025∞
안양1001513∞
인천201502040
수원251320030
대전∞∞40300
166
285
3106
4110
정답 및 해설

서울에서 각 도시까지의 최단 경로 값의 합은 106이다.

안양: 직행 10
인천: 직행 20 (안양 경유는 10+15=25)
수원: 안양 경유 10+13=23 (직행 25보다 짧음)
대전: 수원 경유 23+30=53 (인천 경유는 20+40=60)

합계: 10+20+23+53=106

  • 직행 거리만 더하거나 일부 경유를 빠뜨리면 다른 값이 나오므로, 경유 경로를 모두 비교해야 한다.
  • 대전은 서울과 직접 연결이 없으므로 반드시 인천 또는 수원을 거친 값 중 작은 것을 택한다.
문제 9
다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim 알고리즘을 이용하여 최소 비용 신장 트리를 구할 때, 4번째로 연결되는 간선(edge)으로 옳은 것은? (단, 시작 노드는 A이다)
1(A, D)
2(B, E)
3(E, F)
4(F, C)
정답 및 해설

A에서 시작한 Prim 알고리즘의 네 번째 간선은 (E, F)이다.

Prim은 이미 선택된 정점 집합과 바깥 정점을 잇는 간선 중 최소 비용 간선을 하나씩 추가한다. 선택 순서는 (A, B) 5 → (B, E) 20 → (E, D) 10 → (E, F) 30 이다.

  • (A, B) 5: 첫 번째로 연결되는 간선이다.
  • (B, E) 20: 두 번째로 연결되는 간선이다.
  • (A, D): D는 세 번째 단계에서 더 싼 (E, D) 10으로 연결되므로 선택되지 않는다.
  • (F, C) 15: F가 들어온 다음인 다섯 번째에 연결되는 간선이다.
문제 10
다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?
1234
10101
21011
31000
40100
1방향 그래프(directed graph)이다.
2간선(edge)의 개수는 7이다.
3강력 연결 요소(strongly connected component)는 2개이다.
4방향 사이클이 존재한다.
정답 및 해설

모든 정점이 서로 도달 가능하므로 강력 연결 요소는 1개이며, 2개라는 설명이 옳지 않다.

간선은 1→2, 1→4, 2→1, 2→3, 2→4, 3→1, 4→2이다. 1→2→3→1과 1→4→2→1의 사이클로 네 정점이 모두 연결된다.

  • (1,3)은 0인데 (3,1)은 1처럼 행렬이 대칭이 아니므로 방향 그래프이다.
  • 행렬의 1을 모두 세면 7이므로 간선은 7개이다.
  • 1→2→1처럼 되돌아오는 경로가 있으므로 방향 사이클이 존재한다.
문제 11
배열 A(2:4, 3:7, 2:5)의 원소 개수로 옳은 것은? (단, 배열의 첫 번째 원소는 A(2, 3, 2)이며, 마지막 원소는 A(4, 7, 5)이다)
124
230
348
460
정답 및 해설

배열의 원소 개수는 각 차원 크기의 곱인 60이다.

각 차원의 크기 = 상한 − 하한 + 1
1차원: 4−2+1=3
2차원: 7−3+1=5
3차원: 5−2+1=4

원소 개수: 3×5×4=603 \times 5 \times 4 = 60

  • 상한만 곱하거나 하한을 빼고 1을 더하지 않으면 더 작은 값이 나온다.
  • 세 차원 중 일부만 곱하면 원소 수가 줄어 잘못된 값이 된다.
문제 12
서브프로그램(subprogram)이 호출될 때 사용되는 자료 구조로 옳은 것은?
1연결 리스트(linked list)
2큐(queue)
3스택(stack)
4히프(heap)
정답 및 해설

서브프로그램 호출에는 스택이 사용된다.

호출 시 복귀 주소·매개변수·지역 변수를 활성 레코드로 쌓고, 가장 나중에 호출된 것부터 먼저 복귀하는 후입선출(LIFO) 구조이기 때문이다.

  • 연결 리스트는 원소를 포인터로 잇는 구조일 뿐 호출·복귀 순서를 관리하는 구조가 아니다.
  • 큐는 선입선출 구조라 나중 호출이 먼저 복귀하는 흐름과 맞지 않는다.
  • 히프는 우선순위 큐 구현용 트리 구조이다.
문제 13
N개의 노드를 가진 완전 이진 트리(complete binary tree)에 대한 설명으로 옳지 않은 것은? (단, 루트 노드의 높이는 1로 한다)
1단말(terminal) 노드의 개수는 비단말(non-terminal) 노드의 개수와 같거나 하나가 더 많다.
2높이가 K라면 노드 개수 N의 범위는 2K−1≤N≤2K−12^{K-1} \le N \le 2^{K}-1이다.
3포화 이진 트리(full binary tree)는 완전 이진 트리의 일종이다.
4완전 이진 트리를 최악으로 구성할 경우 높이는 N이다.
정답 및 해설

완전 이진 트리는 왼쪽부터 빈틈없이 채우므로 높이가 ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1로 제한되며, 높이가 N이 된다는 설명이 옳지 않다.

높이가 N이 되는 경우는 노드가 한쪽으로만 이어진 편향 이진 트리로, 완전 이진 트리가 될 수 없다.

  • 완전 이진 트리의 단말 노드 수는 N/2의 올림, 비단말 노드 수는 내림이므로 같거나 하나 더 많다.
  • 높이 K일 때 최소는 마지막 레벨에 노드가 하나인 경우, 최대는 모든 레벨이 꽉 찬 경우이므로 제시된 범위가 성립한다.
  • 포화 이진 트리는 모든 레벨이 꽉 찬 트리로 완전 이진 트리의 조건을 만족한다.
문제 14
아래 중위 표기식을 후위 표기식으로 표현할 때 옳은 것은?
중위 표기식: a * (b - c / 5) + (d - 8 * e / 5)
1a b c 5 / * - d 8 - e * 5 / +
2a b c 5 / - * d 8 e * 5 / - +
3a b * c 5 / - + d 8 - e * 5 /
4a b c 5 - / * d 8 e 5 - * / +
정답 및 해설

후위 표기식은 a b c 5 / − * d 8 e * 5 / − +이다.

앞부분 a*(b−c/5): 괄호 안 c/5 → c 5 /, 이어서 b − → b c 5 / −, 마지막으로 a와 곱해 a b c 5 / − *

뒷부분 (d−8*e/5): 8*e → 8 e *, 그 결과 /5 → 8 e * 5 /, d에서 빼면 d 8 e * 5 / −
두 부분을 +로 결합하면 완성된다.

  • c 5 / 뒤에 뺄셈보다 a와의 곱셈을 먼저 적용한 식은 괄호 (b−c/5)를 무시한 것이다.
  • a와 b를 먼저 곱하는 식은 괄호 안을 먼저 계산해야 한다는 규칙에 어긋난다.
  • c 5 − 처럼 나눗셈보다 뺄셈을 먼저 쓴 식은 연산자 우선순위가 뒤바뀐 것이다.
문제 15
연결 리스트(linked list)에 대한 설명으로 옳지 않은 것은? (단, 연결 리스트의 크기는 N이다)
1다음(next) 원소의 장소나 주소를 저장하기 위한 기억공간이 추가로 필요하다.
2자료가 연결된 순서대로 기억공간에 저장된다.
3특정 자료를 검색하는데 걸리는 시간은 O(N)O(N)이다.
4삭제할 노드의 이전 노드 위치를 알 경우 삭제 시간은 O(1)O(1)이다.
정답 및 해설

연결 리스트의 노드는 기억공간의 임의 위치에 흩어져 저장되고 포인터로 순서를 나타내므로, 연결 순서대로 저장된다는 설명이 옳지 않다.

논리적 순서와 물리적 저장 순서가 일치하는 것은 배열(순차 리스트)의 특징이다.

  • 각 노드는 다음 노드 주소를 담는 링크 필드가 필요하므로 추가 공간이 든다.
  • 임의 접근이 불가능해 처음부터 차례로 따라가야 하므로 검색은 선형 시간이다.
  • 이전 노드를 알면 링크 하나만 바꾸면 되므로 삭제는 상수 시간이다.
문제 16
다음 히프(heap) 트리에 45와 60을 순서대로 삽입한다. 이어서 루트 노드를 삭제한 후, 새로운 루트 노드에서 오른쪽 자식 노드의 값으로 옳은 것은?
130
245
350
460
정답 및 해설

삽입·삭제 후 새 루트 50의 오른쪽 자식은 30이다.

45는 마지막 위치(30의 자식)에 들어가 30, 40과 차례로 교환되어 루트의 왼쪽 자식이 된다. 이어 60은 20의 자식 자리에 들어가 20, 30, 50과 교환되어 루트가 되고, 50은 루트의 오른쪽 자식으로 내려온다.

루트 60을 삭제하면 마지막 노드 20이 루트로 올라온 뒤 더 큰 자식과 교환하며 내려간다. 자식 45·50 중 50과 교환, 다시 자식 30·10 중 30과 교환되므로 새 루트 50의 오른쪽 자식은 30이 된다.

  • 45: 새 루트의 왼쪽 자식이다.
  • 50: 새 루트 자체의 값이다.
  • 60: 삭제된 이전 루트의 값이다.
문제 17
이중 연결 리스트에서 노드 p의 다음(next) 노드가 q이고 노드 q의 이전(prev) 노드가 p인 경우, 인접한 p, q 노드의 위치를 서로 바꾸는 연산의 순서로 옳은 것은? (단, p, q 노드는 모두 연결 리스트의 처음 노드나 마지막 노드가 아니라고 가정한다)
ㄱ. p → prev → next = q;
ㄴ. q → next → prev = p;
ㄷ. p → prev = q;
ㄹ. q → next = p;
ㅁ. q → prev = p → prev;
ㅂ. p → next = q → next;
1ㄱ→ㄴ→ㄷ→ㄹ→ㅁ→ㅂ
2ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ
3ㄱ→ㄴ→ㅂ→ㄹ→ㄷ→ㅁ
4ㄷ→ㄹ→ㅁ→ㅂ→ㄱ→ㄴ
정답 및 해설

올바른 순서는 ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ이다.

p의 앞 노드를 A, q의 뒤 노드를 B라 하면 먼저 A.next=q(ㄱ), B.prev=p(ㄴ)로 바깥 연결을 바꾸고, 아직 남아 있는 p.prev와 q.next를 이용해 q.prev=A(ㅁ), p.next=B(ㅂ)를 설정한다.
마지막으로 p.prev=q(ㄷ), q.next=p(ㄹ)로 둘을 맞붙이면 A↔q↔p↔B가 된다.

  • ㄷ·ㄹ을 ㅁ보다 먼저 하면 p.prev가 이미 q로 바뀌어 q.prev가 자기 자신을 가리키게 된다.
  • ㅂ→ㄹ→ㄷ→ㅁ 순서도 ㅁ 시점에 p.prev가 q이므로 같은 오류가 생긴다.
  • ㄷ·ㄹ부터 하면 A와 B의 주소를 잃어 바깥 노드의 링크를 고칠 수 없다.
문제 18
단순 연결 리스트(singly linked list) L에서, 특정 노드 p 바로 뒤에 새로운 노드 new를 삽입하기 위한 연산 insertAfter의 의사코드가 다음과 같다. ㉠에 들어갈 내용으로 옳은 것은?
Algorithm insertAfter(L, p, new)
if L = NULL
then L ← new;
else
( ㉠ )
end if
return;
1p.next ← new; new.next ← p.next;
2new.next ← p.next; p.next ← new;
3new.next ← p; p.next ← new;
4p.next ← new; new.next ← p;
정답 및 해설

㉠에는 new.next ← p.next; p.next ← new;가 들어간다.

먼저 new가 p의 원래 다음 노드를 가리키게 해 뒤쪽 연결을 보존한 뒤, p가 new를 가리키게 해야 링크 손실 없이 삽입된다.

  • p.next를 먼저 new로 바꾸면 원래 다음 노드 주소를 잃어 new.next가 자기 자신을 가리키게 된다.
  • new.next를 p로 두면 new 뒤에 다시 p가 와서 순환이 생기고 나머지 노드가 끊긴다.
  • p.next를 new로, new.next를 p로 두면 p와 new 사이에 사이클이 생기고 뒤쪽 리스트를 잃는다.
문제 19
어떤 이진 트리에서 중위 순회(inorder traversal)와 전위 순회(preorder traversal)를 수행한 결과가 다음과 같다. 이 이진 트리의 단말(terminal) 노드로 옳지 않은 것은?
중위 순회: C I H B A E G D
전위 순회: A H C I B D E G
1B
2C
3G
4I
정답 및 해설

트리를 복원하면 단말 노드는 I, B, G이며, C는 자식 I를 가진 비단말 노드이다.

전위 첫 원소 A가 루트이고, 중위에서 A 왼쪽 C I H B, 오른쪽 E G D로 나뉜다.
왼쪽은 H가 루트로 왼쪽에 C(오른쪽 자식 I), 오른쪽에 B가 붙고, 오른쪽은 D가 루트로 왼쪽에 E(오른쪽 자식 G)가 붙는다.

  • B는 H의 오른쪽 자식으로 자식이 없는 단말 노드이다.
  • G는 E의 오른쪽 자식으로 자식이 없는 단말 노드이다.
  • I는 C의 오른쪽 자식으로 자식이 없는 단말 노드이다.
문제 20
차수(degree)가 3인 B-트리의 초기 상태가 다음과 같다. 키의 값 35와 40이 순서대로 추가된 후, 35가 삭제될 때 B-트리에 대한 설명으로 옳지 않은 것은?
135가 추가되면 루트 노드는 키의 값 20과 35를 갖는다.
240이 추가되면 40은 키의 값 50을 가진 노드에 추가된다.
335가 삭제되면 자식 노드의 키가 부모 노드로 이동한다.
4최종 결과 트리의 높이는 초기상태 트리의 높이와 다르다.
정답 및 해설

최종 트리의 높이는 초기 상태와 같으므로, 높이가 다르다는 설명이 옳지 않다.

초기 트리는 루트 20, 리프 [10, 15]와 [30, 50]이다. 35를 넣으면 리프 [30, 35, 50]이 넘쳐 분할되고 중간값 35가 루트로 올라가 루트 [20, 35], 리프 [10, 15]·[30]·[50]이 된다. 40은 [50] 노드에 들어가 [40, 50]이 된다.

35를 삭제하면 내부 노드 키이므로 자식 노드의 키(후속키 40)가 부모로 올라와 루트 [20, 40], 리프 [10, 15]·[30]·[50]이 되며, 높이는 2로 그대로이다.

  • 35 추가 후 루트가 20과 35를 갖는다는 설명은 분할 결과와 맞다.
  • 40이 키 50을 가진 노드에 추가된다는 설명은 맞다.
  • 35 삭제 시 자식 노드의 키가 부모로 이동한다는 설명은 맞다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
11년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
희소 행렬에 대한 설명으로 옳지 않은 것은?
1대부분의 원소 값이 0으로 구성되어 있다.
22차원 배열로 표현하면 특정 항목의 접근이 용이하다.
3연결 리스트 구조로 표현하더라도 행렬의 덧셈 연산을 할 수 있다.
4연결 리스트 구조로 표현하면 기억공간을 낭비하게 된다.
정답 및 해설

연결 리스트로 희소 행렬을 표현하면 0이 아닌 원소만 저장하므로 오히려 기억공간이 절약된다. 따라서 기억공간을 낭비한다는 설명이 옳지 않다.

희소 행렬은 0이 대부분이라 2차원 배열에 그대로 담으면 0을 저장하는 데 공간이 낭비되고, 이를 피하려고 (행, 열, 값) 형태의 3원소 배열이나 연결 리스트를 쓴다.

  • 대부분의 원소가 0이라는 것이 희소 행렬의 정의이다.
  • 2차원 배열은 첨자로 바로 계산해 접근하므로 특정 항목 접근이 쉽다.
  • 연결 리스트로 표현해도 행·열 순서로 노드를 비교·병합하면 행렬 덧셈이 가능하다.
문제 2
알고리즘이 갖추어야 할 조건으로 옳지 않은 것은?
1적어도 하나 이상의 출력 결과를 생성해야 한다.
2각 명령어들은 명확하고 모호하지 않아야 한다.
3어떤 경우에도 유한 번의 수행 단계 후에는 반드시 종료해야 한다.
4직접 수행 가능한 컴퓨터 프로그래밍 언어로만 작성되어야 한다.
정답 및 해설

알고리즘은 특정 프로그래밍 언어에 묶이지 않으며 자연어·의사코드·순서도 등으로도 기술할 수 있으므로, 프로그래밍 언어로만 작성해야 한다는 설명이 옳지 않다.

알고리즘의 조건은 입력(0개 이상), 출력(1개 이상), 명확성, 유한성, 유효성이다.

  • 하나 이상의 출력을 내야 한다는 것은 출력 조건이다.
  • 명령이 모호하지 않아야 한다는 것은 명확성 조건이다.
  • 유한 단계 후 반드시 종료해야 한다는 것은 유한성 조건이다.
문제 3
다음 자료 구조 중에서 비선형 구조로만 묶은 것은?
ㄱ. 스택(stack)
ㄴ. 트리(tree)
ㄷ. 연결 리스트(linked list)
ㄹ. 그래프(graph)
1ㄱ, ㄴ
2ㄱ, ㄷ
3ㄴ, ㄷ
4ㄴ, ㄹ
정답 및 해설

비선형 구조로만 묶인 것은 트리와 그래프이다.

선형 구조는 원소가 한 줄로 앞뒤 1:1 관계를 이루고, 비선형 구조는 한 원소가 여러 원소와 1:다 또는 다:다 관계를 가진다.

  • 스택은 한쪽 끝에서만 삽입·삭제하는 선형 구조이다.
  • 연결 리스트는 포인터로 원소를 한 줄로 잇는 선형 구조이다.
문제 4
다음 데이터를 순서대로 입력하여 이진 탐색 트리를 만들 경우, 단말(terminal) 노드의 개수는?
13 17 8 26 55 32 21 6 34 22 3 10
14
25
36
47
정답 및 해설

이진 탐색 트리를 만들면 단말 노드는 3, 10, 22, 34의 4개이다.

13을 루트로, 작으면 왼쪽·크면 오른쪽에 넣으면 13의 왼쪽에 8(자식 6, 10), 6의 왼쪽에 3이 붙는다.
13의 오른쪽에는 17 → 26 → 55가 이어지고, 26의 왼쪽에 21(오른쪽 자식 22), 55의 왼쪽에 32(오른쪽 자식 34)가 붙는다.

자식이 없는 노드만 세면 3, 10, 22, 34이며, 6·21·32는 각각 자식이 하나씩 있어 단말 노드가 아니다.

문제 5
다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것은? (단, 각 정렬 방식은 일반적인 경우만 고려한다)
1합병 정렬(merge sort)
2선택 정렬(selection sort)
3버블 정렬(bubble sort)
4히프 정렬(heap sort)
정답 및 해설

추가 기억공간을 가장 많이 요구하는 것은 합병 정렬이다.

합병 정렬은 두 부분 배열을 합칠 때 결과를 담을 임시 배열이 필요해 입력 크기에 비례하는 O(n)O(n)의 추가 공간을 쓴다.

  • 선택 정렬은 제자리에서 교환만 하므로 상수 크기의 추가 공간이면 된다.
  • 버블 정렬도 인접 원소 교환만 하는 제자리 정렬이다.
  • 히프 정렬은 배열 자체를 히프로 만들어 정렬하므로 상수 크기의 추가 공간이면 된다.
문제 6
레드-블랙 트리에 대한 설명으로 옳지 않은 것은? (단, 노드의 개수는 n이다)
1이진 탐색 트리의 일종이며, 각 노드는 레드 또는 블랙의 색상을 부여받는다.
2부모-자식 관계에 있는 두 노드는 동일한 색을 가져서는 안된다.
3레드-블랙 트리의 높이는 항상 O(log⁡n)O(\log n)이 된다.
4삽입과 삭제 연산의 시간 복잡도는 O(log⁡n)O(\log n)이다.
정답 및 해설

레드-블랙 트리에서 금지되는 것은 레드 노드의 자식이 레드인 경우뿐이므로, 부모와 자식이 같은 색이면 안 된다는 설명이 옳지 않다.

블랙 부모 아래 블랙 자식은 허용되며, 루트에서 각 리프까지 경로의 블랙 노드 수가 같다는 조건으로 균형을 유지한다.

  • 레드-블랙 트리는 각 노드에 레드 또는 블랙 색을 부여한 이진 탐색 트리이다.
  • 색 규칙 덕분에 최장 경로가 최단 경로의 2배를 넘지 않아 높이가 로그 수준으로 유지된다.
  • 높이가 로그 수준이므로 삽입·삭제(재색칠·회전 포함)도 로그 시간에 끝난다.
문제 7
비교가 아닌 분배에 의한 정렬(sorting by distribution) 방식으로 옳은 것은?
1기수 정렬(radix sort)
2버블 정렬(bubble sort)
3퀵 정렬(quick sort)
4히프 정렬(heap sort)
정답 및 해설

비교 없이 분배로 정렬하는 방식은 기수 정렬이다.

기수 정렬은 키의 각 자릿값에 따라 레코드를 버킷(큐)에 분배했다가 순서대로 모으는 과정을 자릿수만큼 반복한다.

  • 버블 정렬은 인접한 두 원소를 비교해 교환하는 비교 기반 정렬이다.
  • 퀵 정렬은 피벗과 비교해 분할하는 비교 기반 정렬이다.
  • 히프 정렬은 부모·자식 키를 비교해 히프를 유지하는 비교 기반 정렬이다.
문제 8
다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양, 서울에서 인천, 서울에서 수원, 서울에서 대전까지 각각 최단 경로 값들을 구하고자 한다. 각각 최단 경로 값들의 합으로 옳은 것은? (단, ∞는 두 도시 간의 연결이 없음을 의미한다)
서울안양인천수원대전
서울0102025∞
안양1001513∞
인천201502040
수원251320030
대전∞∞40300
166
285
3106
4110
정답 및 해설

서울에서 각 도시까지의 최단 경로 값의 합은 106이다.

안양: 직행 10
인천: 직행 20 (안양 경유는 10+15=25)
수원: 안양 경유 10+13=23 (직행 25보다 짧음)
대전: 수원 경유 23+30=53 (인천 경유는 20+40=60)

합계: 10+20+23+53=106

  • 직행 거리만 더하거나 일부 경유를 빠뜨리면 다른 값이 나오므로, 경유 경로를 모두 비교해야 한다.
  • 대전은 서울과 직접 연결이 없으므로 반드시 인천 또는 수원을 거친 값 중 작은 것을 택한다.
문제 9
다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim 알고리즘을 이용하여 최소 비용 신장 트리를 구할 때, 4번째로 연결되는 간선(edge)으로 옳은 것은? (단, 시작 노드는 A이다)
1(A, D)
2(B, E)
3(E, F)
4(F, C)
정답 및 해설

A에서 시작한 Prim 알고리즘의 네 번째 간선은 (E, F)이다.

Prim은 이미 선택된 정점 집합과 바깥 정점을 잇는 간선 중 최소 비용 간선을 하나씩 추가한다. 선택 순서는 (A, B) 5 → (B, E) 20 → (E, D) 10 → (E, F) 30 이다.

  • (A, B) 5: 첫 번째로 연결되는 간선이다.
  • (B, E) 20: 두 번째로 연결되는 간선이다.
  • (A, D): D는 세 번째 단계에서 더 싼 (E, D) 10으로 연결되므로 선택되지 않는다.
  • (F, C) 15: F가 들어온 다음인 다섯 번째에 연결되는 간선이다.
문제 10
다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?
1234
10101
21011
31000
40100
1방향 그래프(directed graph)이다.
2간선(edge)의 개수는 7이다.
3강력 연결 요소(strongly connected component)는 2개이다.
4방향 사이클이 존재한다.
정답 및 해설

모든 정점이 서로 도달 가능하므로 강력 연결 요소는 1개이며, 2개라는 설명이 옳지 않다.

간선은 1→2, 1→4, 2→1, 2→3, 2→4, 3→1, 4→2이다. 1→2→3→1과 1→4→2→1의 사이클로 네 정점이 모두 연결된다.

  • (1,3)은 0인데 (3,1)은 1처럼 행렬이 대칭이 아니므로 방향 그래프이다.
  • 행렬의 1을 모두 세면 7이므로 간선은 7개이다.
  • 1→2→1처럼 되돌아오는 경로가 있으므로 방향 사이클이 존재한다.
문제 11
배열 A(2:4, 3:7, 2:5)의 원소 개수로 옳은 것은? (단, 배열의 첫 번째 원소는 A(2, 3, 2)이며, 마지막 원소는 A(4, 7, 5)이다)
124
230
348
460
정답 및 해설

배열의 원소 개수는 각 차원 크기의 곱인 60이다.

각 차원의 크기 = 상한 − 하한 + 1
1차원: 4−2+1=3
2차원: 7−3+1=5
3차원: 5−2+1=4

원소 개수: 3×5×4=603 \times 5 \times 4 = 60

  • 상한만 곱하거나 하한을 빼고 1을 더하지 않으면 더 작은 값이 나온다.
  • 세 차원 중 일부만 곱하면 원소 수가 줄어 잘못된 값이 된다.
문제 12
서브프로그램(subprogram)이 호출될 때 사용되는 자료 구조로 옳은 것은?
1연결 리스트(linked list)
2큐(queue)
3스택(stack)
4히프(heap)
정답 및 해설

서브프로그램 호출에는 스택이 사용된다.

호출 시 복귀 주소·매개변수·지역 변수를 활성 레코드로 쌓고, 가장 나중에 호출된 것부터 먼저 복귀하는 후입선출(LIFO) 구조이기 때문이다.

  • 연결 리스트는 원소를 포인터로 잇는 구조일 뿐 호출·복귀 순서를 관리하는 구조가 아니다.
  • 큐는 선입선출 구조라 나중 호출이 먼저 복귀하는 흐름과 맞지 않는다.
  • 히프는 우선순위 큐 구현용 트리 구조이다.
문제 13
N개의 노드를 가진 완전 이진 트리(complete binary tree)에 대한 설명으로 옳지 않은 것은? (단, 루트 노드의 높이는 1로 한다)
1단말(terminal) 노드의 개수는 비단말(non-terminal) 노드의 개수와 같거나 하나가 더 많다.
2높이가 K라면 노드 개수 N의 범위는 2K−1≤N≤2K−12^{K-1} \le N \le 2^{K}-1이다.
3포화 이진 트리(full binary tree)는 완전 이진 트리의 일종이다.
4완전 이진 트리를 최악으로 구성할 경우 높이는 N이다.
정답 및 해설

완전 이진 트리는 왼쪽부터 빈틈없이 채우므로 높이가 ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1로 제한되며, 높이가 N이 된다는 설명이 옳지 않다.

높이가 N이 되는 경우는 노드가 한쪽으로만 이어진 편향 이진 트리로, 완전 이진 트리가 될 수 없다.

  • 완전 이진 트리의 단말 노드 수는 N/2의 올림, 비단말 노드 수는 내림이므로 같거나 하나 더 많다.
  • 높이 K일 때 최소는 마지막 레벨에 노드가 하나인 경우, 최대는 모든 레벨이 꽉 찬 경우이므로 제시된 범위가 성립한다.
  • 포화 이진 트리는 모든 레벨이 꽉 찬 트리로 완전 이진 트리의 조건을 만족한다.
문제 14
아래 중위 표기식을 후위 표기식으로 표현할 때 옳은 것은?
중위 표기식: a * (b - c / 5) + (d - 8 * e / 5)
1a b c 5 / * - d 8 - e * 5 / +
2a b c 5 / - * d 8 e * 5 / - +
3a b * c 5 / - + d 8 - e * 5 /
4a b c 5 - / * d 8 e 5 - * / +
정답 및 해설

후위 표기식은 a b c 5 / − * d 8 e * 5 / − +이다.

앞부분 a*(b−c/5): 괄호 안 c/5 → c 5 /, 이어서 b − → b c 5 / −, 마지막으로 a와 곱해 a b c 5 / − *

뒷부분 (d−8*e/5): 8*e → 8 e *, 그 결과 /5 → 8 e * 5 /, d에서 빼면 d 8 e * 5 / −
두 부분을 +로 결합하면 완성된다.

  • c 5 / 뒤에 뺄셈보다 a와의 곱셈을 먼저 적용한 식은 괄호 (b−c/5)를 무시한 것이다.
  • a와 b를 먼저 곱하는 식은 괄호 안을 먼저 계산해야 한다는 규칙에 어긋난다.
  • c 5 − 처럼 나눗셈보다 뺄셈을 먼저 쓴 식은 연산자 우선순위가 뒤바뀐 것이다.
문제 15
연결 리스트(linked list)에 대한 설명으로 옳지 않은 것은? (단, 연결 리스트의 크기는 N이다)
1다음(next) 원소의 장소나 주소를 저장하기 위한 기억공간이 추가로 필요하다.
2자료가 연결된 순서대로 기억공간에 저장된다.
3특정 자료를 검색하는데 걸리는 시간은 O(N)O(N)이다.
4삭제할 노드의 이전 노드 위치를 알 경우 삭제 시간은 O(1)O(1)이다.
정답 및 해설

연결 리스트의 노드는 기억공간의 임의 위치에 흩어져 저장되고 포인터로 순서를 나타내므로, 연결 순서대로 저장된다는 설명이 옳지 않다.

논리적 순서와 물리적 저장 순서가 일치하는 것은 배열(순차 리스트)의 특징이다.

  • 각 노드는 다음 노드 주소를 담는 링크 필드가 필요하므로 추가 공간이 든다.
  • 임의 접근이 불가능해 처음부터 차례로 따라가야 하므로 검색은 선형 시간이다.
  • 이전 노드를 알면 링크 하나만 바꾸면 되므로 삭제는 상수 시간이다.
문제 16
다음 히프(heap) 트리에 45와 60을 순서대로 삽입한다. 이어서 루트 노드를 삭제한 후, 새로운 루트 노드에서 오른쪽 자식 노드의 값으로 옳은 것은?
130
245
350
460
정답 및 해설

삽입·삭제 후 새 루트 50의 오른쪽 자식은 30이다.

45는 마지막 위치(30의 자식)에 들어가 30, 40과 차례로 교환되어 루트의 왼쪽 자식이 된다. 이어 60은 20의 자식 자리에 들어가 20, 30, 50과 교환되어 루트가 되고, 50은 루트의 오른쪽 자식으로 내려온다.

루트 60을 삭제하면 마지막 노드 20이 루트로 올라온 뒤 더 큰 자식과 교환하며 내려간다. 자식 45·50 중 50과 교환, 다시 자식 30·10 중 30과 교환되므로 새 루트 50의 오른쪽 자식은 30이 된다.

  • 45: 새 루트의 왼쪽 자식이다.
  • 50: 새 루트 자체의 값이다.
  • 60: 삭제된 이전 루트의 값이다.
문제 17
이중 연결 리스트에서 노드 p의 다음(next) 노드가 q이고 노드 q의 이전(prev) 노드가 p인 경우, 인접한 p, q 노드의 위치를 서로 바꾸는 연산의 순서로 옳은 것은? (단, p, q 노드는 모두 연결 리스트의 처음 노드나 마지막 노드가 아니라고 가정한다)
ㄱ. p → prev → next = q;
ㄴ. q → next → prev = p;
ㄷ. p → prev = q;
ㄹ. q → next = p;
ㅁ. q → prev = p → prev;
ㅂ. p → next = q → next;
1ㄱ→ㄴ→ㄷ→ㄹ→ㅁ→ㅂ
2ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ
3ㄱ→ㄴ→ㅂ→ㄹ→ㄷ→ㅁ
4ㄷ→ㄹ→ㅁ→ㅂ→ㄱ→ㄴ
정답 및 해설

올바른 순서는 ㄱ→ㄴ→ㅁ→ㅂ→ㄷ→ㄹ이다.

p의 앞 노드를 A, q의 뒤 노드를 B라 하면 먼저 A.next=q(ㄱ), B.prev=p(ㄴ)로 바깥 연결을 바꾸고, 아직 남아 있는 p.prev와 q.next를 이용해 q.prev=A(ㅁ), p.next=B(ㅂ)를 설정한다.
마지막으로 p.prev=q(ㄷ), q.next=p(ㄹ)로 둘을 맞붙이면 A↔q↔p↔B가 된다.

  • ㄷ·ㄹ을 ㅁ보다 먼저 하면 p.prev가 이미 q로 바뀌어 q.prev가 자기 자신을 가리키게 된다.
  • ㅂ→ㄹ→ㄷ→ㅁ 순서도 ㅁ 시점에 p.prev가 q이므로 같은 오류가 생긴다.
  • ㄷ·ㄹ부터 하면 A와 B의 주소를 잃어 바깥 노드의 링크를 고칠 수 없다.
문제 18
단순 연결 리스트(singly linked list) L에서, 특정 노드 p 바로 뒤에 새로운 노드 new를 삽입하기 위한 연산 insertAfter의 의사코드가 다음과 같다. ㉠에 들어갈 내용으로 옳은 것은?
Algorithm insertAfter(L, p, new)
if L = NULL
then L ← new;
else
( ㉠ )
end if
return;
1p.next ← new; new.next ← p.next;
2new.next ← p.next; p.next ← new;
3new.next ← p; p.next ← new;
4p.next ← new; new.next ← p;
정답 및 해설

㉠에는 new.next ← p.next; p.next ← new;가 들어간다.

먼저 new가 p의 원래 다음 노드를 가리키게 해 뒤쪽 연결을 보존한 뒤, p가 new를 가리키게 해야 링크 손실 없이 삽입된다.

  • p.next를 먼저 new로 바꾸면 원래 다음 노드 주소를 잃어 new.next가 자기 자신을 가리키게 된다.
  • new.next를 p로 두면 new 뒤에 다시 p가 와서 순환이 생기고 나머지 노드가 끊긴다.
  • p.next를 new로, new.next를 p로 두면 p와 new 사이에 사이클이 생기고 뒤쪽 리스트를 잃는다.
문제 19
어떤 이진 트리에서 중위 순회(inorder traversal)와 전위 순회(preorder traversal)를 수행한 결과가 다음과 같다. 이 이진 트리의 단말(terminal) 노드로 옳지 않은 것은?
중위 순회: C I H B A E G D
전위 순회: A H C I B D E G
1B
2C
3G
4I
정답 및 해설

트리를 복원하면 단말 노드는 I, B, G이며, C는 자식 I를 가진 비단말 노드이다.

전위 첫 원소 A가 루트이고, 중위에서 A 왼쪽 C I H B, 오른쪽 E G D로 나뉜다.
왼쪽은 H가 루트로 왼쪽에 C(오른쪽 자식 I), 오른쪽에 B가 붙고, 오른쪽은 D가 루트로 왼쪽에 E(오른쪽 자식 G)가 붙는다.

  • B는 H의 오른쪽 자식으로 자식이 없는 단말 노드이다.
  • G는 E의 오른쪽 자식으로 자식이 없는 단말 노드이다.
  • I는 C의 오른쪽 자식으로 자식이 없는 단말 노드이다.
문제 20
차수(degree)가 3인 B-트리의 초기 상태가 다음과 같다. 키의 값 35와 40이 순서대로 추가된 후, 35가 삭제될 때 B-트리에 대한 설명으로 옳지 않은 것은?
135가 추가되면 루트 노드는 키의 값 20과 35를 갖는다.
240이 추가되면 40은 키의 값 50을 가진 노드에 추가된다.
335가 삭제되면 자식 노드의 키가 부모 노드로 이동한다.
4최종 결과 트리의 높이는 초기상태 트리의 높이와 다르다.
정답 및 해설

최종 트리의 높이는 초기 상태와 같으므로, 높이가 다르다는 설명이 옳지 않다.

초기 트리는 루트 20, 리프 [10, 15]와 [30, 50]이다. 35를 넣으면 리프 [30, 35, 50]이 넘쳐 분할되고 중간값 35가 루트로 올라가 루트 [20, 35], 리프 [10, 15]·[30]·[50]이 된다. 40은 [50] 노드에 들어가 [40, 50]이 된다.

35를 삭제하면 내부 노드 키이므로 자식 노드의 키(후속키 40)가 부모로 올라와 루트 [20, 40], 리프 [10, 15]·[30]·[50]이 되며, 높이는 2로 그대로이다.

  • 35 추가 후 루트가 20과 35를 갖는다는 설명은 분할 결과와 맞다.
  • 40이 키 50을 가진 노드에 추가된다는 설명은 맞다.
  • 35 삭제 시 자식 노드의 키가 부모로 이동한다는 설명은 맞다.