[정보처리기사] 자료구조 (스택/큐/트리/그래프) 예상문제 1회

문제 1. 스택(Stack)의 동작 원리

스택(Stack)은 데이터를 저장하고 꺼내는 순서에 특징이 있는 선형 자료구조입니다. 다음 중 스택의 입출력 방식을 올바르게 설명한 것은?

1. 먼저 삽입된 데이터가 먼저 삭제된다.
2. 마지막에 삽입된 데이터가 먼저 삭제된다.
3. 임의의 위치에 있는 데이터를 자유롭게 삭제할 수 있다.
4. 삽입과 삭제가 양쪽 끝에서 모두 가능하다.

정답

② 마지막에 삽입된 데이터가 먼저 삭제된다. — 스택은 LIFO(Last In First Out) 구조입니다.

해설

스택은 LIFO(Last In First Out) 원칙을 따릅니다. 데이터 삽입(Push)은 스택의 맨 위(Top)에서 이루어지고, 삭제(Pop)도 같은 Top에서만 수행됩니다. 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.

오답: ① FIFO(First In First Out) 방식으로, 이는 스택이 아닌 큐(Queue)의 동작 방식입니다.
정답: ② LIFO 방식으로, 스택의 핵심 특성을 정확히 설명합니다.
오답: ③ 임의 접근(Random Access)은 배열이나 연결 리스트에서 구현 가능하며, 스택은 Top 위치만 접근합니다.
오답: ④ 양쪽 끝에서 삽입·삭제가 가능한 구조는 덱(Deque, Double-Ended Queue)입니다.

문제 2. 스택 연산 결과 추론

빈 스택에 대해 다음 연산을 순서대로 수행하였습니다. 최종적으로 스택에 남아 있는 데이터를 Top부터 순서대로 나열한 것은?

Push(1) → Push(2) → Push(3) → Pop() → Push(4) → Pop()

1. 4, 3, 2, 1
2. 1, 2
3. 2, 1
4. 3, 2, 1

정답

③ 2, 1 — 두 번의 Pop 이후 스택에 남은 요소는 Top부터 2, 1 순입니다.

해설

연산 과정을 단계별로 추적합니다. Push(1) → [1], Push(2) → [1,2], Push(3) → [1,2,3], Pop() → 3 제거 → [1,2], Push(4) → [1,2,4], Pop() → 4 제거 → [1,2]입니다. Top부터 읽으면 2, 1 순서입니다.

오답: ① Pop 연산을 전혀 고려하지 않은 결과입니다.
오답: ② Bottom부터 읽은 순서로, Top부터 읽은 것과 방향이 반대입니다.
정답: ③ 두 번의 Pop 후 남은 요소를 Top에서부터 올바르게 나열한 결과입니다.
오답: ④ Pop 연산을 한 번만 적용하거나 Push(4)를 누락한 경우의 오류입니다.

문제 3. 큐(Queue)의 활용 사례

큐(Queue)는 FIFO 원칙을 따르는 자료구조로, 다양한 시스템에서 활용됩니다. 다음 중 큐의 특성이 가장 적합하게 활용되는 사례는?

1. 웹 브라우저의 뒤로 가기(Back) 기능 구현
2. 재귀 함수 호출 시 복귀 주소 관리
3. 프린터 스풀(Spool)에서 인쇄 작업 순서 관리
4. 수식의 괄호 짝 검사

정답

③ 프린터 스풀에서 인쇄 작업 순서 관리 — 먼저 요청된 작업이 먼저 처리되는 FIFO 구조가 적합합니다.

해설

큐는 먼저 들어온 데이터가 먼저 처리되는 FIFO 구조입니다. 프린터 스풀은 인쇄 요청이 들어온 순서대로 처리해야 하므로 큐가 최적입니다.

오답: ① 뒤로 가기 기능은 이전 방문 페이지를 역순으로 되돌아가므로 LIFO 구조인 스택을 사용합니다.
오답: ② 재귀 함수의 복귀 주소는 나중에 호출된 함수가 먼저 복귀하므로 스택이 적합합니다.
정답: ③ 요청 순서대로 처리하는 FIFO 특성이 큐와 정확히 일치합니다.
오답: ④ 괄호 짝 검사는 여는 괄호를 저장했다가 닫는 괄호와 대조하는 LIFO 방식이므로 스택을 사용합니다.

문제 4. 이진 트리 전위 순회

아래와 같은 이진 트리가 있습니다. 전위 순회(Preorder Traversal) 방식으로 노드를 방문했을 때 출력 순서로 옳은 것은?

루트: A / A의 왼쪽 자식: B, 오른쪽 자식: C / B의 왼쪽 자식: D, 오른쪽 자식: E / C의 왼쪽 자식: F, 오른쪽 자식: 없음

1. D → B → E → A → F → C
2. A → B → D → E → C → F
3. D → E → B → F → C → A
4. A → B → C → D → E → F

정답

② A → B → D → E → C → F — 전위 순회는 루트 → 왼쪽 → 오른쪽 순서입니다.

해설

전위 순회(Preorder)는 루트(Root) → 왼쪽 서브트리(Left) → 오른쪽 서브트리(Right) 순으로 방문합니다. 루트 A를 먼저 방문하고, 왼쪽 서브트리 B → D → E, 이어서 오른쪽 서브트리 C → F 순으로 방문합니다.

오답: ① 왼쪽 → 루트 → 오른쪽 순서인 중위 순회(Inorder)와 유사하나 정확히 일치하지도 않는 혼합 오류입니다.
정답: ② 루트 → 왼쪽 → 오른쪽의 전위 순회 규칙을 정확히 따른 결과입니다.
오답: ③ 왼쪽 → 오른쪽 → 루트 순서인 후위 순회(Postorder)에 해당합니다.
오답: ④ 같은 레벨의 노드를 좌→우 순으로 방문하는 레벨 순회(Level-order)와 유사하지만 E와 F의 위치가 틀립니다.

문제 5. 그래프 용어와 개념

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조입니다. 다음 그래프 관련 설명 중 옳지 않은 것은?

1. 방향 그래프(Directed Graph)에서 간선은 한 방향으로만 이동할 수 있다.
2. 무방향 그래프에서 정점이 n개이면 최대 간선 수는 n(n-1)/2개이다.
3. 사이클(Cycle)이 없는 연결 그래프를 트리(Tree)라고 한다.
4. 그래프에서 특정 정점에 연결된 간선의 수를 차수(Degree)라 하며, 방향 그래프에서는 진입 차수와 진출 차수를 구분하지 않는다.

정답

④ 방향 그래프에서도 진입 차수(In-degree)와 진출 차수(Out-degree)를 반드시 구분합니다.

해설

방향 그래프(Directed Graph)에서 차수는 진입 차수(In-degree)와 진출 차수(Out-degree)로 구분합니다. 진입 차수는 해당 정점으로 들어오는 간선의 수이고, 진출 차수는 나가는 간선의 수입니다. 따라서 구분하지 않는다는 ④의 설명은 틀렸습니다.

오답: ① 방향 그래프의 간선은 화살표 방향으로만 이동 가능하므로 옳은 설명입니다.
오답: ② 무방향 그래프에서 n개의 정점이 모두 연결된 완전 그래프의 최대 간선 수는 n(n-1)/2이며 옳은 설명입니다.
오답: ③ 사이클이 없는 연결 그래프는 트리의 정의와 일치하므로 옳은 설명입니다.
정답: ④ 방향 그래프에서는 진입·진출 차수를 반드시 구분하므로 옳지 않은 설명입니다.