자료구조 단원 모의 문제 · 정보처리기사

20단원 '자료구조'의 여섯 레슨에서 6문제를 냈고, 끝에 실기 꼴 3문제가 있습니다. 코드의 출력은 Python 3.15로 돌린 결과입니다. 출력을 쓰는 문제는 줄바꿈까지 그대로 씁니다. 실기 꼴은 종이에 답을 끝까지 쓴 뒤 펼치세요. 띄어쓰기만 다르면 같은 답입니다.

문제 1

다음 (가)~(라) 가운데 선형 구조만 모두 고른 것을 고르세요.

(가) 데크
(나) 원형 연결 리스트
(다) 그래프
(라) 스택
① (라)
② (가)·(라)
③ (나)·(라)
④ (가)·(나)·(라)

정답

④ — 선형인지는 한 자료 뒤에 이어지는 자료가 몇 개인지로 가릅니다. 데크는 양 끝에서 넣고 빼지만 칸마다 다음 칸이 하나인 한 줄입니다. 원형 연결 리스트도 마지막 노드가 첫 노드를 가리킬 뿐, 노드마다 다음 노드는 하나입니다. 넷 가운데 한 정점에 여러 정점이 이어지는 그래프만 비선형 구조입니다.

① 데크와 원형 연결 리스트를 모두 비선형으로 봤습니다. 끝이 둘이어도, 끝에서 처음으로 돌아와도 다음 자료가 하나면 선형입니다.
② 원형 연결 리스트를 비선형으로 봤습니다. 마지막 노드에서 첫 노드로 돌아오는 길을 그래프의 사이클처럼 봤지만, 노드마다 다음 노드가 하나인 한 줄입니다.
③ 데크를 비선형으로 봤습니다. 양 끝이 모두 열려 있어도 한 줄로 늘어선 선형 구조입니다.

다시 볼 레슨: 자료구조의 분류 · 연결 리스트

문제 2

다음 가운데 스택이 아니라 큐로 처리해야 차례가 맞는 일을 고르세요.

① 함수 main이 f를, f가 g를 불렀습니다. g가 끝나면 f로, f가 끝나면 main으로 돌아갈 자리를 꺼냅니다.
② 지도 앱이 출발역에서 한 정거장 거리의 역을 모두 살핀 뒤에야 두 정거장 거리의 역을 살핍니다.
③ 계산기가 후위 식 4 2 3 * +를 왼쪽부터 읽어 값을 구합니다.
④ 미로 찾기 프로그램이 막다른 길에 닿으면 가장 최근에 지난 갈림길로 돌아가 다른 길을 고릅니다.

정답

② — 가까운 역을 모두 본 뒤 그다음 거리로 넓히려면, 먼저 찾은 역의 이웃부터 살펴야 합니다. 찾은 차례대로 꺼내는 큐를 쓰는 너비 우선 탐색입니다.

① 부른 차례대로 돌아간다고 봤습니다. 돌아갈 자리는 마지막에 부른 g의 것부터 꺼내므로, 나중에 넣은 것이 먼저 나오는 스택입니다.
③ 식을 왼쪽부터 읽으니 들어온 차례대로 꺼낸다고 봤습니다. 연산자를 만나면 가장 나중에 넣은 두 수 3과 2를 꺼내 계산하므로 스택입니다.
④ 지나온 갈림길을 처음 것부터 되짚는다고 봤습니다. 가장 최근에 지난 갈림길부터 돌아가므로 스택을 쓰는 깊이 우선 탐색입니다.

다시 볼 레슨: 스택과 큐 · 그래프와 탐색

문제 3

다음 코드가 찍는 값을 위에서부터 차례로 고르세요.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(7)
b = Node(3)
c = Node(9)
d = Node(5)
a.next = b
b.next = c
c.next = d
head = a
p = head.next
p.next = p.next.next
head = head.next
while head is not None:
    print(head.data)
    head = head.next

① 3, 5
② 3, 9
③ 7, 3, 5
④ 7, 3, 9

정답

① — 실행 결과는 이렇습니다.

실행 결과

3
5

p는 head 다음 노드인 3입니다. p.next = p.next.next는 3의 다음 칸이 9를 건너 5를 가리키게 해 9가 빠집니다. 그다음 head = head.next가 head를 3으로 옮기므로 읽기는 3에서 시작하고, 7은 아무 화살표도 받지 않습니다.

② 빠지는 노드를 p.next.next인 5로 봤습니다. 바뀌는 것은 p의 다음 칸이라, 건너뛰어 빠지는 노드는 p 바로 다음의 9입니다.
③ head를 옮겨도 읽기는 처음 만든 노드 7에서 시작한다고 봤습니다. 값은 늘 head가 가리키는 노드에서 출발해 화살표를 따라 읽습니다.
④ 두 오해가 겹쳤습니다. 빠지는 노드는 9이고, 읽기는 옮긴 head인 3에서 시작합니다.

다시 볼 레슨: 연결 리스트

문제 4

노드가 12개인 완전 이진 트리가 있습니다. 루트의 레벨을 1로 셀 때, 이 트리의 (가) 높이와 (나) 단말 노드 수로 알맞은 것을 고르세요.

① (가) 3 · (나) 5
② (가) 3 · (나) 6
③ (가) 4 · (나) 5
④ (가) 4 · (나) 6

정답

④ — 레벨 1~3을 꽉 채우면 1 + 2 + 4 = 7개이고, 남은 5개가 레벨 4에 왼쪽부터 들어가 높이는 4입니다. 레벨 4의 다섯은 레벨 3의 앞 세 노드에 둘·둘·하나씩 매달리고, 레벨 3의 넷째 노드는 자식이 없습니다. 단말 노드는 레벨 4의 다섯에 그 노드 하나를 더한 6개입니다. 차수 2인 노드가 5개(레벨 1~2의 셋과 레벨 3의 앞 둘)이니, 단말 노드 = 차수 2인 노드 + 1과도 맞습니다.

① 높이를 레벨 0부터 센 값으로 봤고, 단말 노드도 맨 아래 층에서만 셌습니다.
② 단말 노드는 맞게 셌지만 높이를 레벨 0부터 센 값으로 봤습니다. 문제는 루트를 레벨 1로 셉니다.
③ 높이는 맞게 구했지만 단말 노드를 맨 아래 층에서만 셌습니다. 레벨 3의 넷째 노드도 자식이 없어 단말입니다.

다시 볼 레슨: 트리

문제 5

후위 식 A B C - * D +와 같은 계산을 나타내는 중위 식을 고르세요.

① A * B - C + D
② A * (B - C) + D
③ (A - B) * C + D
④ A - B * C + D

정답

② — 후위 식은 왼쪽부터 읽으며 값을 쌓고, 연산자를 만나면 바로 앞에 쌓인 두 값을 묶습니다. -가 B와 C를 묶어 B − C, *가 A와 그 결과를 묶어 A * (B − C), +가 다시 그 결과와 D를 묶습니다. B − C를 먼저 계산해야 하니 중위 식에서는 괄호가 있어야 합니다.

① 묶는 차례는 맞게 따랐지만 괄호를 뺐습니다. 괄호가 없으면 A * B를 먼저 계산하는 식이 되어, 후위 식으로는 A B * C - D +입니다.
③ -를 맨 앞의 A와 B에 걸었습니다. 연산자는 바로 앞에 쌓인 두 값을 묶으므로 -는 B와 C를 묶습니다. 이 식의 후위 식은 A B - C * D +입니다.
④ 두 오해가 겹쳤습니다. -를 A와 B 사이에 두고 괄호도 뺐습니다. 이 식의 후위 식은 A B C * - D +입니다.

다시 볼 레슨: 이진 트리 순회와 수식 표기 · 스택과 큐

문제 6

다음 무방향 그래프를 A에서 출발해 깊이 우선 탐색합니다. 이웃이 여럿이면 알파벳이 앞선 정점부터 갑니다. 방문 차례로 알맞은 것을 고르세요.

정점	이웃
A	B, F, G
B	A, C, D
C	B, E, G
D	B
E	C
F	A, G
G	A, C, F

① A B C E D F G
② A B C E F G D
③ A B C E G F D
④ A B F G C D E

정답

③ — A에서 B, C를 거쳐 E로 들어가면, E는 C 말고 이웃이 없어 막힙니다. 지나온 길을 거꾸로 밟아 C로 돌아가면 아직 안 간 G가 남아 있어 G로, 다시 G에서 F로 갑니다. F에서 막혀 G, C, B 차례로 되돌아가다가 B의 남은 이웃 D를 방문합니다.

① 막히자 지나온 길과 상관없이, 아직 안 간 정점 가운데 글자가 가장 앞선 D로 건너뛰었습니다. 되돌아갈 곳은 지나온 길에서 가장 최근에 지난 C입니다.
② 막히자 출발 정점 A로 돌아가 남은 이웃 F로 갔습니다. 지나온 길은 마지막에 지난 정점부터 거꾸로 꺼내므로, E 다음에는 C로 돌아갑니다.
④ 출발 정점의 이웃을 모두 방문한 뒤 그 이웃들의 이웃으로 넓혀 가는 너비 우선 탐색의 차례입니다. 깊이 우선 탐색은 B에서 멈추지 않고 C와 E로 들어갑니다.

다시 볼 레슨: 그래프와 탐색

문제 7 (실기)

(가)·(나)의 찾는 방법을 영문 약어로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

(가) 백신 프로그램이 폴더 속 파일을 검사합니다. 폴더를 하나 열면 그 안의 하위 폴더로 계속 들어가고, 더 들어갈 곳이 없으면 바로 위 폴더로 돌아와 아직 열지 않은 하위 폴더를 엽니다.
(나) SNS가 친구를 추천합니다. 나와 바로 이어진 사람을 모두 살핀 뒤에야, 그 사람들과 이어진 사람을 살핍니다.

정답

받는 답: (가) DFS · (나) BFS

(가)의 실마리는 '한 갈래로 끝까지 들어가고, 막히면 바로 위로 돌아온다', (나)는 '바로 이어진 사람을 모두 살핀 뒤에 그다음'입니다.

같은 이름의 다른 꼴: (가) 깊이 우선 탐색 · Depth First Search, (나) 너비 우선 탐색 · Breadth First Search — 한글 이름과 원어입니다. 문제가 영문 약어로 물었습니다.
틀리는 꼴 BFS — (가)에: 가까운 것을 모두 먼저 살피고 넓혀 갑니다. (가)는 하위 폴더 하나를 끝까지 파고든 뒤에 돌아옵니다.
틀리는 꼴 DFS — (나)에: 한 사람의 친구의 친구를 끝까지 따라간 뒤에 돌아옵니다. (나)는 바로 이어진 사람을 모두 본 다음에 넓힙니다.

다시 볼 레슨: 그래프와 탐색

문제 8 (실기)

(가)·(나)에 쓰인 자료구조의 이름을 한글로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

(가) 키보드로 친 글자를 칸 16개짜리 배열에 담아 두었다가, 먼저 친 글자부터 꺼내 화면에 찍습니다. 15번 칸까지 쓰고 나면, 앞에서 꺼내 비운 0번 칸부터 다시 이어 담습니다.
(나) 문서 편집기가 작업 기록을 한 줄로 남깁니다. 새 작업은 줄의 한쪽 끝에 붙이고, 실행 취소를 누르면 같은 끝에서 가장 최근 기록을 꺼냅니다. 기록이 100개를 넘으면 반대쪽 끝에서 가장 오래된 기록을 버립니다.

정답

받는 답: (가) 원형 큐 · (나) 데크

(가)의 실마리는 '먼저 친 글자부터 꺼낸다'와 '끝 칸 다음에 비운 0번 칸으로 이어 담는다', (나)는 '한쪽 끝에서 넣고 빼면서, 반대쪽 끝에서도 버린다'입니다.

같은 이름의 다른 꼴: (가) Circular Queue · (나) Deque — 영문입니다. 문제가 한글로 물었습니다.
틀리는 꼴 큐 — (가)에: 먼저 넣은 것이 먼저 나오는 것은 맞지만, 끝 칸 다음을 첫 칸으로 이어 비운 칸을 다시 쓰는 것이 원형 큐입니다.
틀리는 꼴 원형 연결 리스트 — (가)에: 노드를 포인터로 이어 마지막 노드가 첫 노드를 가리키게 한 리스트입니다. (가)는 배열의 칸 번호를 돌려 씁니다.
틀리는 꼴 스택 — (나)에: 한쪽 끝에서만 넣고 빼면 스택이지만, (나)는 반대쪽 끝에서도 기록을 뺍니다. 양 끝을 모두 쓰면 데크입니다.

다시 볼 레슨: 스택과 큐

문제 9 (실기)

다음 코드의 실행 결과를 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

class Node:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None

def walk(n):
    if n is None:
        return 0
    a = walk(n.left)
    print(n.v, end='')
    b = walk(n.right)
    if a + b == 0:
        return 1
    return a + b

root = Node('P')
root.left = Node('Q')
root.right = Node('R')
root.left.right = Node('S')
root.right.left = Node('T')
root.right.right = Node('U')
root.left.right.left = Node('V')
k = walk(root)
print()
print(k)

정답

받는 답:

실행 결과

QVSPTRU
3

print가 두 재귀 호출 사이에 있어 첫 줄은 중위 순회입니다. P의 왼쪽 서브트리부터 읽는데, Q는 왼쪽 자식이 없어 Q를 먼저 적고 오른쪽 S의 서브트리로 갑니다. V는 S의 왼쪽 자식이라 S보다 먼저 적힙니다. 그다음 P, 오른쪽 서브트리의 T R U입니다.

walk는 자식이 없는 노드에서 1을, 자식이 있는 노드에서는 두 서브트리가 돌려준 값의 합을 돌려줍니다. 그래서 k는 단말 노드 V, T, U의 수 3입니다.

틀리는 꼴 QSVPTRU와 3: V를 S의 오른쪽 자식으로 봤습니다. root.left.right.left는 S의 왼쪽 자식입니다.
틀리는 꼴 PQSVRTU와 3: print가 두 호출 앞에 있는 전위 순회로 읽었습니다.
틀리는 꼴 QVSPTRU와 7: 노드마다 1을 더한다고 봤습니다. 자식이 있는 노드는 1을 더하지 않고 a + b만 돌려줍니다.

다시 볼 레슨: 이진 트리 순회와 수식 표기 · 트리