Skip to Content
독학사독학사 2단계자료구조18. 독학사 2단계 자료구조 예상기출문제

이번 문서의 목표: 실제 시험과 비슷한 밀도로 22문항을 시간을 재며 풀어보고, 틀린 문항은 해설의 계산 과정을 손으로 다시 밟아 무엇을 놓쳤는지 정확히 찾아낸다.

재구성 고지: 이 편의 문제는 국가평생교육진흥원이 공개한 특정 회차의 기출문제를 그대로 옮긴 것이 아니다. 국가평생교육진흥원 홈페이지에 공시된 자료구조 과목의 평가영역과 출제방향(참고 자료 참조)을 근거로 재구성한 학습용 예상문제이며, 실제 회차의 문항 수·배점·시험 시간·합격 기준은 매년 달라질 수 있으므로 응시 전 최신 공고를 반드시 확인해야 한다(공고 확인 필요).

이 모의고사 세트의 구성

17편의 기출 분석에서 정리한 정의형·비교형·계산형·추적형 네 유형을 실제 시험처럼 섞어 22문항으로 구성했다. 17편과 다른 예제와 숫자를 사용해 같은 개념을 다른 각도에서 다시 확인할 수 있게 했다. 계산형·추적형 문항은 explanation에 대입부터 답까지 생략 없이 적었으므로, 문제를 먼저 스스로 풀어 본 뒤 해설과 대조하는 방식으로 활용하길 권한다.

문제 14지선다
다음 이중 반복문의 총 실행 횟수와 시간복잡도로 옳은 것은? for i = 1 to n: for j = 1 to i: 문장 실행
문제 24지선다
이진 탐색의 재귀 관계 T(n) = T(n/2) + O(1)에서 시간복잡도가 O(log n)이 되는 이유로 옳은 것은?
문제 34지선다
행과 열이 각각 0부터 4, 0부터 5까지인 2차원 배열 A가 행 우선(row-major) 방식으로 저장되어 있다. 배열의 시작 주소가 100이고 원소 하나의 크기가 4바이트일 때, A[2][3]의 주소는?
문제 44지선다
테일(tail) 포인터를 별도로 유지하지 않는 단순 연결리스트에서, 리스트의 맨 끝에 새 노드를 삽입할 때의 시간복잡도는?
문제 54지선다
원형 이중 연결리스트(circular doubly linked list)가 특히 적합한 활용 사례로 가장 옳은 것은?
문제 64지선다
중위식 (A + B) * (C - D)를 후위식으로 올바르게 변환한 것은?
문제 74지선다
후위식 6 2 3 + - 4 *를 스택으로 계산했을 때 최종 결과는?
문제 84지선다
너비우선탐색(BFS)이 스택이 아니라 큐(queue)를 사용하는 이유로 가장 옳은 것은?
문제 94지선다
배열 [3, 9, 2, 1, 4, 5]를 상향식(build-heap) 방법으로 최대 히프(max-heap)로 만들면 완성되는 배열은?
문제 104지선다
문제 9에서 완성한 최대 히프 9, 4, 5, 1, 3, 2에서 delete-max 연산(루트 삭제)을 한 번 수행한 직후의 배열은?
문제 114지선다
어떤 이진트리의 중위 순회 결과가 J, H, K, G, L, I, M이고 후위 순회 결과가 J, K, H, L, M, I, G일 때, 전위 순회 결과는?
문제 124지선다
빈 이진탐색트리에 45, 20, 60, 15, 30, 50, 70, 25를 이 순서로 삽입했을 때, 값 30의 중위 순회 기준 후속자(다음 노드)는?
문제 134지선다
문제 12의 트리(45, 20, 60, 15, 30, 50, 70, 25를 순서대로 삽입)에서 루트로부터 가장 깊은 노드까지의 간선 수(트리의 높이)는?
문제 144지선다
정점 1, 2, 3, 4, 5와 간선 (1,2), (1,3), (2,4), (3,4), (4,5)로 이루어진 무방향 그래프에서 정점 4의 차수(degree)는?
문제 154지선다
문제 14의 그래프에서 정점 1부터 시작해 번호가 작은 인접 정점을 먼저 방문하는 깊이우선탐색(DFS)의 방문 순서는?
문제 164지선다
문제 14의 그래프에서 정점 1부터 시작해 큐를 이용한 너비우선탐색(BFS)의 방문 순서는?
문제 174지선다
배열 [6, 3, 9, 2, 8, 5, 1]에서 맨 앞 원소 6을 피벗으로 삼아 퀵 정렬의 첫 번째 분할(partition)을 수행하면, 6보다 작은 원소를 왼쪽에 그대로의 상대 순서로 모으고 6보다 큰 원소를 오른쪽에 모은 뒤 피벗을 그 사이에 놓은 결과는?
문제 184지선다
병합 정렬 과정에서 이미 정렬된 두 부분 배열 [2, 5, 8]과 [1, 3, 9]를 병합(merge)한 결과는?
문제 194지선다
배열 [170, 90, 802, 2, 24, 45, 75, 66]은 기수 정렬(radix sort)에서 1의 자리를 기준으로 한 첫 번째 패스가 끝난 상태다. 이어서 10의 자리를 기준으로 두 번째 패스를 수행한 결과는?
문제 204지선다
해시함수 h(k) = k mod 6을 사용하고 체이닝(chaining)으로 충돌을 처리하는 크기 6의 해시테이블에 12, 18, 25, 7, 31, 44를 이 순서로 삽입할 때, 가장 긴 체인이 만들어지는 슬롯과 그 안의 키는?
문제 214지선다
개방 주소법(open addressing)의 선형 조사법(linear probing)에서 1차 군집화(primary clustering)가 발생하는 이유로 가장 옳은 것은?
문제 224지선다
병합 정렬의 재귀 관계 T(n) = 2T(n/2) + O(n)이 O(n log n)이 되는 이유를 재귀 트리로 설명한 것으로 가장 옳은 것은?

정답 대조표

1단계 — 정답 번호와 근거를 문항 순서대로 나열

문항정답근거 요약
13등차수열 합 n(n+1)/2, O(n^2)
21절반씩 줄어 log2(n)번 반복
33(2*6+3)*4+100=160
42마지막 노드 탐색에 O(n)
52양방향·순환 재생목록
61괄호 안 연산 각각 먼저
71(6-(2+3))*4=4
82FIFO가 레벨별 방문 보장
91상향식 히프 만들기 결과
102delete-max 후 down-heapify
111후위 마지막이 루트, 복원
122중위 순회상 30 다음이 45
13345→20→30→25, 간선 3개
143(2,4),(3,4),(4,5) 세 간선
1511,2,4,3,5 깊이 우선
1631,2,3,4,5 너비 우선
172작은 값·큰 값 발견 순 정리
182두 배열 비교 병합 결과
19210의 자리 기준 재배치
2021번 슬롯 세 개로 최다
212순차 탐사가 군집을 키움
222레벨수 log n, 레벨당 n

2단계 — 재확인 방법

이 표만 외우지 말고, 각 행의 근거 요약을 보고 왜 그 계산이 나오는지 직접 다시 유도해 본다. 특히 9번, 10번, 11번, 19번, 20번처럼 여러 단계를 거치는 추적형 문제는 중간 단계를 하나라도 건너뛰면 다른 정답이 나올 수 있으므로, 표 위의 각 문항 해설과 대조하며 자신의 풀이 과정을 한 줄씩 맞춰본다.

핵심 정리

  • 계산·추적형 문제는 답을 암산으로 맞히려 하지 말고, 배열 상태나 트리 구조를 단계마다 직접 적으며 진행해야 실수를 줄일 수 있다.
  • 히프·해싱·정렬 패스는 각각 규칙(부모-자식 비교, 나머지 연산과 충돌 처리, 비교 후 교환)이 다르므로 서로 헷갈리지 않도록 문제마다 어떤 규칙을 적용하는지 먼저 확인한다.
  • 트리 순회 세 가지 결과 중 두 가지가 주어지면 나머지 하나를 복원할 수 있어야 하며, 이때 항상 전위(또는 후위)에서 루트를 먼저 찾고 중위에서 좌우를 나누는 순서로 접근한다.
  • 오답 선택지들은 대개 계산 과정 중 한 단계(교환 누락, 순서 반전, 비교 대상 착각)를 빠뜨렸을 때 나오는 값이므로, 오답까지 확인하면 자신이 실수하기 쉬운 지점을 미리 파악할 수 있다.

참고 자료

Last updated on
17. 독학사 2단계 자료구조 기출 분석