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

09년 1회차

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

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

09년 1회차

총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의 1번 위치부터 14번 위치까지 저장되어 있다. 이 배열에서 최대값을 제거하는 연산을 3번 수행한 후, 최대힙의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산 시 가급적 최대힙의 내용 변경을 최소화 한다고 가정한다)
(데이터)
[200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38]
1[72, 63, 62, 60, 52, 38, 37, 22, 16, 11, 5]
2[72, 52, 63, 38, 16, 60, 62, 37, 22, 11, 5]
3[72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]
4[72, 52, 63, 16, 38, 60, 62, 5, 11, 37, 22]
정답 및 해설

세 차례 삭제 후 앞 11칸은 [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]이다.

삭제는 루트를 꺼내고 마지막 원소를 루트로 올린 뒤 더 큰 자식과 교환하며 내려보내는 하향 재정렬로 진행한다.
첫 삭제(200 제거): 38이 192·185와 교환 → [192, 185, 63, 72, 38, 60, 62, 16, 52, 37, 22, 11, 5]
둘째 삭제(192 제거): 5가 185·72·52와 교환 → [185, 72, 63, 52, 38, 60, 62, 16, 5, 37, 22, 11]
셋째 삭제(185 제거): 11이 72·52·16과 교환 → [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]

  • [72, 63, 62, 60, …]처럼 내림차순으로 정렬된 나열: 힙은 부모가 자식보다 크기만 하면 되며, 삭제 연산이 전체를 정렬하지는 않는다.
  • [72, 52, 63, 38, 16, …]으로 시작하는 나열: 38은 첫 삭제에서 다섯째 칸에 자리 잡은 뒤 움직이지 않고, 넷째 칸은 셋째 삭제에서 16이 채운다.
  • 끝이 5, 11, 37, 22인 나열: 11은 두 자식 16과 5 중 큰 16과 교환되어 여덟째 칸에 놓이고, 5는 아홉째 칸에 그대로 남는다.
문제 2
다음과 같은 재귀적(recursive) 그래프 탐색 알고리즘을 반복적(iterative) 알고리즘으로 구현하고자 한다. 그래프가 인접리스트(adjacency list)에 저장되어 있다고 가정할 때, 구현을 위하여 필요한 자료구조와 전체 그래프를 순회(traversal)하는 알고리즘의 시간복잡도(time complexity)를 옳게 나타낸 것은? (단, 정점의 집합은 V, 간선의 집합은 E라고 가정한다)
(알고리즘)
void search( vertex v )
{
visited[v] = 1 ;
for each vertex w adjacent to v
if ( !visited[w] ) search( w ) ;
}
1queue, O( |E| )
2stack, O( ∣V∣2|V|^2 )
3stack, O( |V| + |E| )
4queue, O( ∣V∣2|V|^2 )
정답 및 해설

필요한 자료구조는 스택, 시간복잡도는 O(|V| + |E|)이다.

주어진 알고리즘은 방문하지 않은 인접 정점으로 재귀 호출을 이어 가는 깊이우선탐색이므로, 반복형으로 바꾸면 재귀 호출 스택을 명시적 스택으로 대신한다. 인접리스트에서는 각 정점을 한 번 방문하고 각 간선을 상수 번 검사하므로 정점 수와 간선 수의 합에 비례한다.

  • 큐와 O(|E|)의 조합: 큐는 너비우선탐색에 쓰는 자료구조이며, 정점 방문 비용인 |V| 항도 빠져 있다.
  • 스택과 O(∣V∣2)O(|V|^2)의 조합: 자료구조는 맞지만 제곱 시간은 인접행렬로 표현했을 때의 수행시간이다.
  • 큐와 O(∣V∣2)O(|V|^2)의 조합: 자료구조와 시간복잡도 모두 인접행렬 기반 너비우선탐색에 해당한다.
문제 3
가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?
1그래프에 존재하는 임의의 사이클을 구성하는 간선(edge)들 중 가중치가 가장 작은 간선은 항상 이 그래프의 최소비용 신장트리에 포함된다.
2Dijkstra의 최단경로 알고리즘 수행 결과 생성되는 신장트리는 항상 최소비용 신장트리이다.
3임의의 그래프에 대해 서로 다른 최소비용 신장트리가 항상 두 개 이상 존재한다.
4간선의 가중치 값들이 서로 다르고 최소비용 신장트리가 존재하는 경우, 가중치 값이 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.
정답 및 해설

간선 가중치가 모두 다를 때 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.

최소 간선 e를 뺀 최소비용 신장트리가 있다고 하면, e를 추가해 생긴 사이클에서 e보다 무거운 간선 하나를 빼면 비용이 더 작은 신장트리가 되어 모순이다. 크루스칼 알고리즘이 가장 먼저 선택하는 간선도 이 간선이다.

  • 사이클의 최소 간선이 항상 포함된다는 설명: 사이클 성질은 사이클의 가장 무거운 간선이 제외됨을 보장할 뿐이며, 최소 간선이라도 두 끝점을 더 가벼운 간선들로만 이루어진 다른 경로가 잇고 있으면 빠진다.
  • Dijkstra 결과가 최소비용 신장트리라는 설명: Dijkstra는 시작점에서 각 정점까지의 거리를 최소화하는 최단경로 트리를 만들 뿐, 간선 가중치의 총합을 최소화하지 않는다.
  • 최소비용 신장트리가 항상 두 개 이상이라는 설명: 간선 가중치가 모두 다르면 최소비용 신장트리는 유일하다.
문제 4
그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?
ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다.
ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.
ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 v2v^2개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O(v2v^2)이다.
11 개
22 개
33 개
44 개
정답 및 해설

옳은 문장은 ㄱ, ㅁ의 두 개이다.

무방향 그래프는 간선 (i, j)와 (j, i)가 같으므로 인접행렬이 대칭이다. 인접행렬 기반 너비우선탐색은 정점마다 행 하나(v칸)를 모두 훑으므로 O(v2)O(v^2)이다.

  • 차수의 합: 간선 하나가 양 끝 정점의 차수를 하나씩 올리므로 간선 수의 2배(2e2e)이다.
  • 완전그래프의 간선 수: 서로 다른 두 정점 쌍의 수인 v(v−1)2\dfrac{v(v-1)}{2}개이다.
  • 인접행렬의 메모리: 간선 수와 무관하게 v×vv \times v 행렬이 필요하므로 O(v2)O(v^2)이며, O(v + e)는 인접리스트의 공간이다.
문제 5
해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은?
ㄱ. n개의 자료가 있을 때 자료의 탐색에 걸리는 시간은 O(logn)이다.
ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓(bucket)에 사상(mapping)시킨다.
ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다.
ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다.
ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다.
1ㄴ, ㄷ
2ㄴ, ㅁ
3ㄱ, ㄹ
4ㄹ, ㅁ
정답 및 해설

옳은 것은 ㄹ, ㅁ이다.

해싱은 키의 대소 순서를 보존하지 않으므로 최대값을 찾으려면 모든 자료를 확인해야 해 O(n)이 걸린다. 좋은 해시함수는 충돌이 적고 주소에 고르게 분포해야 한다.

  • 탐색 시간 O(log n): 해싱의 평균 탐색 시간은 O(1)이며, O(log n)은 이진탐색이나 균형 탐색트리의 성능이다.
  • 서로 다른 자료가 항상 다른 버켓으로 간다는 설명: 키 공간이 주소 공간보다 커서 서로 다른 키가 같은 주소로 가는 충돌이 생긴다.
  • 적재 밀도가 높을수록 성능이 좋다는 설명: 적재 밀도가 높을수록 충돌이 늘어 탐색 성능이 나빠진다.
문제 6
스택, 큐, 리스트 자료구조에 대한 설명으로 옳지 않은 것은?
1연결리스트는 배열 구조와 비교하여 삽입, 삭제 시간이 많이 걸리고 메모리의 낭비가 많다.
2주로 힙(heap) 구조로 구현되는 우선순위 큐(priority queue)의 데이터 삽입은 임의로 이루어지나, 데이터의 삭제는 가장 큰 값이나 가장 작은 값부터 수행된다.
3스택은 함수 호출, 후위식 연산 등에 유용하게 사용되며, 연결 리스트로 구현할 수 있다.
4큐는 선입선출(First In First Out) 방식의 동작을 수행하므로 잡스케줄링(job scheduling) 등에 유용하게 사용된다.
정답 및 해설

옳지 않은 것은 연결리스트가 배열보다 삽입·삭제가 느리고 메모리 낭비가 많다는 설명이다.

연결리스트는 위치만 알면 링크만 바꿔 삽입·삭제하므로 원소를 밀고 당겨야 하는 배열보다 빠르다. 또 필요할 때마다 노드를 할당하므로 크기를 미리 크게 잡는 배열보다 빈 공간 낭비가 적다.

  • 우선순위 큐: 삽입 순서와 무관하게 우선순위가 가장 높은(최대 또는 최소) 원소부터 삭제되며 주로 힙으로 구현한다.
  • 스택: 후입선출 구조라 함수 호출과 후위식 계산에 쓰이며, 배열과 연결리스트 모두로 구현할 수 있다.
  • 큐: 선입선출 구조라 먼저 들어온 작업을 먼저 처리하는 작업 스케줄링에 쓰인다.
문제 7
깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A - B의 값은? (단, 루트노드의 레벨은 1로 한다)
12k−1+k+12^{k-1} + k + 1
22k−1+k−12^{k-1} + k - 1
32k−k−12^{k} - k - 1
42k−k+12^{k} - k + 1
정답 및 해설

A − B 의 값은 2k−k−12^{k} - k - 1이다.

최대 노드 수는 모든 레벨이 꽉 찬 포화 이진트리일 때로, 레벨 i에 2i−12^{i-1}개씩 있으므로 A=2k−1A = 2^{k} - 1이다.
최소 노드 수는 레벨마다 노드가 하나뿐인 편향 이진트리일 때로 B=kB = k이다.
A−B=(2k−1)−k=2k−k−1A - B = (2^{k} - 1) - k = 2^{k} - k - 1

  • 2k−1+k+12^{k-1} + k + 1: 깊이 1이면 노드가 하나뿐이라 A − B 는 0이어야 하는데 3이 된다.
  • 2k−1+k−12^{k-1} + k - 1: 깊이 1에서 1이 되어 0이 아니므로 맞지 않는다.
  • 2k−k+12^{k} - k + 1: 깊이 1에서 2가 되어 상수항 부호가 틀렸다.
문제 8
6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리(binary search tree)를 만들 때, 만들어진 이진 탐색트리의 높이가 가장 낮은 것은?
11, 2, 3, 5, 4, 6
24, 2, 5, 6, 1, 3
33, 1, 4, 2, 6, 5
42, 1, 3, 4, 6, 5
정답 및 해설

높이가 가장 낮은 것은 4, 2, 5, 6, 1, 3 순서의 삽입이다.

루트 4의 왼쪽에 2, 오른쪽에 5가 오고, 1과 3은 2의 양쪽 자식, 6은 5의 오른쪽 자식이 되어 높이 3(레벨 수 기준)이다. 이는 노드 6개인 이진트리가 가질 수 있는 최소 높이이다.

  • 1, 2, 3, 5, 4, 6: 1→2→3→5로 오른쪽으로만 이어지고 4가 5의 왼쪽에 붙어 높이 5이다.
  • 3, 1, 4, 2, 6, 5: 3→4→6→5 경로가 생겨 높이 4이다.
  • 2, 1, 3, 4, 6, 5: 2→3→4→6→5 경로가 생겨 높이 5이다.
문제 9
다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 데이터 ‘JAN’을 삽입한 결과로 옳은 것은?

1
2
3
4
정답 및 해설

JAN 삽입 후 LR 회전이 일어나 MAR가 새 루트가 되고, 왼쪽에 AUG(자식 APR, JAN), 오른쪽에 MAY(오른쪽 자식 NOV)가 오는 트리가 옳다.

JAN은 MAY보다 작고 AUG보다 크며 MAR보다 작으므로 MAR의 왼쪽 자식으로 들어간다. 이때 MAY의 왼쪽 높이는 3, 오른쪽 높이는 1이 되어 균형인수가 +2가 되고, 삽입 위치가 왼쪽 자식(AUG)의 오른쪽 서브트리이므로 LR 불균형이다.

LR 회전은 AUG를 중심으로 왼쪽 회전한 뒤 MAY를 중심으로 오른쪽 회전하는 것으로, 중간값인 MAR가 위로 올라가고 MAR의 왼쪽 자식 JAN은 AUG의 오른쪽 자식으로 옮겨진다.

  • MAR의 왼쪽에 JAN만 붙이고 루트를 MAY로 둔 트리: 이진 탐색 순서는 맞지만 MAY의 균형인수가 +2로 AVL 조건을 위반한다.
  • JAN을 NOV의 왼쪽 자식으로 둔 트리: JAN은 MAY보다 작으므로 오른쪽 서브트리에 올 수 없어 탐색 순서가 깨진다.
  • JAN을 APR의 오른쪽 자식으로 둔 트리: JAN은 AUG보다 크므로 AUG의 왼쪽 서브트리에 올 수 없고, 균형도 깨진다.
문제 10
다음과 같은 이진트리(binary tree)에서 전위순회(preorder traversal)와 중위순회(inorder traversal)를 했을 때, 두 순회 결과에서 노드 값의 방문 순서가 일치하는 횟수는? (전위순회의 k번째 노드값과 중위순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다)
13 회
24 회
35 회
46 회
정답 및 해설

두 순회 결과를 나란히 비교하면 같은 자리에서 일치하는 노드는 B, E, I, G로 4회이다.

전위순회(루트→왼쪽→오른쪽)는 A, B, D, E, H, C, F, I, J, G 순이고, 중위순회(왼쪽→루트→오른쪽)는 D, B, H, E, A, F, J, I, C, G 순이다.

2번째 B, 4번째 E, 8번째 I, 10번째 G가 같고 나머지 자리는 모두 다르다.

  • 3회: 네 자리 중 하나(예: 마지막 G)를 빠뜨렸을 때 나오는 값이다.
  • 5회: 실제 일치 수보다 많아, 순회 순서를 잘못 구했을 때 나오는 값이다.
  • 6회: H를 E의 오른쪽 자식으로 보는 등 트리 구조를 잘못 읽었을 때 나올 수 있는 값으로, 실제 일치는 4회뿐이다.
문제 11
점근적 표기법(asymptotic notation)에 관한 사칙연산으로 옳지 않은 것은?
1O(n) + O(n) = O(n)
2O(n2)+O(nlog⁡n)=O(n2)O(n^2) + O(n\log n) = O(n^2)
3O(n2)+O(n)=O(n2)O(n^2) + O(n) = O(n^2)
4O(log⁡n)⋅O(n2)=O(n2)O(\log n) \cdot O(n^2) = O(n^2)
정답 및 해설

옳지 않은 것은 O(log⁡n)⋅O(n2)=O(n2)O(\log n) \cdot O(n^2) = O(n^2)이다.

빅오의 곱은 각 함수를 곱하므로 O(log⁡n)⋅O(n2)=O(n2log⁡n)O(\log n) \cdot O(n^2) = O(n^2 \log n)이 된다. n2log⁡nn^2 \log n은 n2n^2보다 빠르게 증가하므로 O(n2)O(n^2)로 줄일 수 없다. 반면 덧셈은 가장 빠르게 증가하는 항만 남는다.

  • O(n) + O(n) = O(n): 상수배 차이는 무시되므로 성립한다.
  • O(n2)+O(nlog⁡n)=O(n2)O(n^2) + O(n\log n) = O(n^2): nlog⁡nn\log n이 n2n^2보다 느리게 증가하므로 성립한다.
  • O(n2)+O(n)=O(n2)O(n^2) + O(n) = O(n^2): 차수가 큰 항만 남으므로 성립한다.
문제 12
배열 A에 오름차순으로 저장된 데이터를 이진탐색(binary search)하기 위하여 반복적(iterative) 알고리즘을 이용하여 기술하였다. ㉠, ㉡에 들어갈 적당한 명령은?
procedure BINARYSEARCH(A, n, x, j)
lower ← 1 ; upper ← n ;
while lower ≤ upper do
mid ← the middle element;
case
: x > A(mid):    ㉠   ;
: x < A(mid):    ㉡   ;
: else : j ← mid ; return;
end
end
j ← 0 ;
end
1lower ← mid + 1 / upper ← mid - 1
2upper ← mid + 1 / lower ← mid - 1
3lower ← mid - 1 / upper ← mid + 1
4upper ← mid - 1 / lower ← mid + 1
정답 및 해설

㉠은 lower ← mid + 1, ㉡은 upper ← mid - 1이다.

x가 A(mid)보다 크면 찾는 값은 mid 오른쪽에 있으므로 하한을 mid 다음으로 올리고, 작으면 왼쪽에 있으므로 상한을 mid 앞으로 내린다. mid는 이미 비교했으므로 ±1로 제외해야 구간이 줄어 반복이 끝난다.

  • upper ← mid + 1 / lower ← mid - 1: x가 클 때 상한을 건드려 왼쪽 구간을 남기므로 찾는 값을 놓친다.
  • lower ← mid - 1 / upper ← mid + 1: 갱신할 변수는 맞지만 ±1 방향이 반대라 mid가 구간에 다시 포함되므로, lower와 upper가 같아진 뒤에도 구간이 줄지 않아 반복이 끝나지 않을 수 있다.
  • upper ← mid - 1 / lower ← mid + 1: x가 클 때 오른쪽이 아닌 왼쪽 구간을 남겨 찾는 값을 놓친다.
문제 13
다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 과정이 끝난 후, 피봇키(pivot key)를 중심으로 좌측에는 피봇키보다 작은 수, 우측에는 피봇키보다 큰 수들로 데이터가 분할된 상태를 올바르게 나타낸 것은? (단, 피봇키는 가장 왼쪽에 있는 값으로 한다)
(초기데이터)
[0][1][2][3][4][5][6][7][8][9]
8149635270

(보기의 인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9])
17 1 4 6 3 5 2 0 8 9
27 1 4 0 6 3 5 2 8 9
32 1 4 0 6 3 5 7 8 9
40 1 4 2 6 3 5 7 8 9
정답 및 해설

1단계 분할 결과는 7 1 4 0 6 3 5 2 8 9이다.

피봇 8을 두고 왼쪽 포인터 i는 8보다 큰 값, 오른쪽 포인터 j는 8보다 작은 값을 찾아 교환한다.
i는 9([3]), j는 0([9])에서 멈춰 교환 → 8 1 4 0 6 3 5 2 7 9
다시 i는 9([9]), j는 7([8])에서 멈추고 두 포인터가 엇갈린다.
마지막으로 피봇과 j 위치의 7을 교환 → 7 1 4 0 6 3 5 2 8 9

  • 7 1 4 6 3 5 2 0 8 9: 9와 0의 교환이 반영되지 않아 0이 [3]에 오지 않았다.
  • 2 1 4 0 6 3 5 7 8 9: 피봇은 j 위치의 7과 교환되므로 [0]에는 7, [7]에는 2가 그대로 있어야 한다.
  • 0 1 4 2 6 3 5 7 8 9: [0]에는 7, [3]에는 0, [7]에는 2가 와야 하므로 교환 결과와 맞지 않는다.
문제 14
K[1:2, 1:3, 1:2]로 선언된 3차원 배열을 행 우선순서(row major order)로 1차원 배열에 저장했을 때, 9번째에 저장되는 요소는?
1K(1, 2, 2)
2K(1, 3, 2)
3K(2, 2, 1)
4K(2, 3, 2)
정답 및 해설

아홉째로 저장되는 요소는 K(2, 2, 1)이다.

행 우선순서에서는 마지막 첨자가 가장 빨리 변한다. 첫째 첨자 하나당 3 × 2 = 6개, 둘째 첨자 하나당 2개가 묶인다.
pos(i,j,k)=(i−1)×6+(j−1)×2+(k−1)+1\mathrm{pos}(i,j,k) = (i-1)\times 6 + (j-1)\times 2 + (k-1) + 1
pos(2,2,1)=6+2+0+1=9\mathrm{pos}(2,2,1) = 6 + 2 + 0 + 1 = 9

  • K(1, 2, 2): 0+2+1+1=40 + 2 + 1 + 1 = 4로 넷째이다.
  • K(1, 3, 2): 0+4+1+1=60 + 4 + 1 + 1 = 6으로 여섯째이다.
  • K(2, 3, 2): 6+4+1+1=126 + 4 + 1 + 1 = 12로 마지막 열두째이다.
문제 15
다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 모든 원소들의 값이 0인 행렬을 상삼각 행렬(upper triangular matrix)이라고 한다.

A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가?
1B[4998]
2B[4999]
3B[5000]
4B[5001]
정답 및 해설

A[90][93]은 B[4998]에 저장된다.

상삼각행렬을 행 우선으로 저장하면 i행에는 열 i부터 99까지 100−i개의 원소가 있으므로, A[i][j]의 위치는 앞선 0~(i−1)행의 원소 수 합에 (j−i)를 더한 값이다.

∑k=089(100−k)=90×100−89×902=9000−4005=4995\sum_{k=0}^{89}(100-k) = 90 \times 100 - \dfrac{89 \times 90}{2} = 9000 - 4005 = 4995
4995+(93−90)=49984995 + (93 - 90) = 4998

  • B[4999]: 위치를 1부터 센 것처럼 하나를 더한 값이다.
  • B[5000]: 행 내부 오프셋 (j−i)=3 대신 다른 값을 더하는 등 위치 계산을 잘못한 값이다.
  • B[5001]: 앞선 행들의 원소 수 합 4995에 오프셋을 잘못 더한 값으로, 실제 위치보다 3칸 뒤이다.
문제 16
다음 전위식(preorder expression)으로 표현된 수식을 후위식(postorder expression)으로 변환하였다. 변환된 수식의 4번째 연산자는?
(전위식) - + - AB * / CDEF
1* 연산자
2+ 연산자
3- 연산자
4/ 연산자
정답 및 해설

후위식의 넷째 연산자는 + 연산자이다.

전위식을 연산자와 두 피연산자 단위로 묶으면 ((A − B) + (C / D) * E) − F 구조이다. 이를 후위식으로 바꾸면 A B − C D / E * + F −이고, 연산자 순서는 −, /, *, +, − 이다.

  • * 연산자: 셋째로 나온다.
  • − 연산자: 첫째와 다섯째에 나오며 넷째가 아니다.
  • / 연산자: 둘째로 나온다.
문제 17
스택을 일차원 배열 stack[0 : 99]를 이용하여 구현하고자 한다. top 변수의 초기값은 -1로 설정하며, top이 -1이면 스택은 비어있다는 것을 나타낸다. C 언어를 이용하여 스택에 데이터를 추가하는 함수 push()와 삭제하는 함수 pop()을 다음과 같이 작성하였을 때, ㉠과 ㉡에 들어갈 내용은?
void push(int *top, int data) { // 스택에 data를 추가
if ( *top >= 99) { stack_full() ; return ; }
㉠;
}
int pop(int *top) { // 스택에서 데이터를 삭제 후 반환
if ( *top == -1) { return stack_empty() ; }
㉡;
}
1stack[*top++] / return stack[--*top]
2stack[*top++] / return stack[*top--]
3stack[++*top] / return stack[*top--]
4stack[++*top] / return stack[--*top]
정답 및 해설

㉠은 stack[++*top](top을 먼저 올린 뒤 저장), ㉡은 return stack[*top--](현재 top 값을 반환한 뒤 내림)이다.

top은 마지막 원소의 위치를 가리키고 빈 스택에서 −1이므로, push는 top을 하나 올린 칸에 저장해야 stack[0]부터 채워진다. pop은 지금 top 칸의 값을 꺼낸 뒤 top을 내려야 한다. 엄밀한 C 문법에서는 후위 --가 *보다 먼저 결합하므로 의도대로 동작하려면 stack[(*top)--]처럼 괄호를 써야 한다.

  • stack[*top++] / return stack[--*top]: push가 올리기 전 위치(빈 스택이면 −1)에 저장해 범위를 벗어나고, pop은 꼭대기 아래 칸의 값을 반환한다.
  • stack[*top++] / return stack[*top--]: pop은 맞지만 push가 올리기 전 위치에 저장한다.
  • stack[++*top] / return stack[--*top]: push는 맞지만 pop이 꼭대기가 아닌 그 아래 칸의 값을 반환한다.
문제 18
원형 연결리스트(circular linked list)의 길이를 계산하기 위한 C함수를 작성하려고 한다. 밑줄 친 ㉠과 ㉡부분에 알맞은 명령은? (단, 원형 연결리스트의 길이는 노드의 개수로 정의하고, 원형 연결리스트의 시작 포인터는 ptr이라고 가정한다)
struct list_node {
char data ;
struct list_node *link;
}
typedef struct list_node *list_pointer;
int CListLength(list_pointer ptr){
list_pointer temp ;
int count = 0 ;
if (  ㉠  ) {
temp = ptr ;
do { count + + ;
} while (  ㉡  ) ;
}
return count;
}
1!ptr / temp->link != ptr
2ptr / temp=temp->link, temp != ptr
3!ptr / temp=temp->link, temp == ptr
4ptr / temp->link == ptr
정답 및 해설

㉠은 ptr, ㉡은 temp=temp->link, temp != ptr이다.

리스트가 비어 있지 않을 때(ptr가 NULL이 아닐 때)만 세기 시작하고, do-while 안에서 개수를 센 뒤 temp를 다음 노드로 옮겨 시작 노드로 돌아오면 멈춘다. 쉼표 연산자는 앞의 이동을 수행한 뒤 뒤의 비교 결과를 조건으로 쓴다.

  • !ptr / temp->link != ptr: 빈 리스트일 때만 세려 해 NULL 접근이 생기고, temp도 이동하지 않는다.
  • !ptr / temp=temp->link, temp == ptr: 시작 조건이 반대이고, 시작 노드로 돌아왔을 때 오히려 반복을 계속하는 반대 조건이다.
  • ptr / temp->link == ptr: temp를 옮기지 않아 노드 수를 셀 수 없다(노드가 하나면 무한 반복, 여럿이면 1을 반환).
문제 19
n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결리스트(singly linked list)로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?
1포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제
2리스트의 길이를 출력
3포인터값이 주어진 임의의 노드 앞에 새로운 노드 추가
4마지막 노드의 데이터를 출력
정답 및 해설

시간 복잡도가 가장 낮은 연산은 포인터가 가리키는 노드의 다음 노드 삭제로 O(1)이다.

가리키는 노드의 링크를 다음 노드의 링크로 바꾸기만 하면 되므로 탐색이 필요 없다. 나머지 연산은 단순 연결리스트에서 리스트를 처음부터 따라가야 해 O(n)이다.

  • 리스트 길이 출력: 길이를 따로 저장하지 않으면 모든 노드를 세어야 한다.
  • 주어진 노드 앞에 새 노드 추가: 단순 연결리스트에는 앞 노드로 가는 링크가 없어 선행 노드를 처음부터 찾아야 한다.
  • 마지막 노드의 데이터 출력: 꼬리 포인터가 없으면 끝까지 따라가야 한다.
문제 20
자료들이 단순 연결리스트(singly linked list)에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은?
메모리주소datalink
2000A2020
2010B2030
2020C2010
2030D0
1A의 link → 2030
2B의 link → 2010
3B의 link → 2020
4C의 link → 2030
정답 및 해설

B를 삭제하면 C의 link가 2030으로 바뀐다.

link를 따라가면 A(2000) → C(2020) → B(2010) → D(2030) 순서이므로 B의 선행 노드는 C이다. C의 link를 B의 다음 노드 주소인 2030으로 바꾸면 B가 리스트에서 빠진다.

  • A의 link → 2030: B뿐 아니라 C까지 리스트에서 빠진다.
  • B의 link → 2010: 삭제할 노드의 링크를 바꾸는 것은 의미가 없고, C가 여전히 B를 가리킨다.
  • B의 link → 2020: C가 여전히 B를 가리키며 C와 B 사이에 순환이 생긴다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
09년 1회차
총 20문항 · 객관식 · 정답·해설 포함
문제 1
다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의 1번 위치부터 14번 위치까지 저장되어 있다. 이 배열에서 최대값을 제거하는 연산을 3번 수행한 후, 최대힙의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산 시 가급적 최대힙의 내용 변경을 최소화 한다고 가정한다)
(데이터)
[200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38]
1[72, 63, 62, 60, 52, 38, 37, 22, 16, 11, 5]
2[72, 52, 63, 38, 16, 60, 62, 37, 22, 11, 5]
3[72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]
4[72, 52, 63, 16, 38, 60, 62, 5, 11, 37, 22]
정답 및 해설

세 차례 삭제 후 앞 11칸은 [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]이다.

삭제는 루트를 꺼내고 마지막 원소를 루트로 올린 뒤 더 큰 자식과 교환하며 내려보내는 하향 재정렬로 진행한다.
첫 삭제(200 제거): 38이 192·185와 교환 → [192, 185, 63, 72, 38, 60, 62, 16, 52, 37, 22, 11, 5]
둘째 삭제(192 제거): 5가 185·72·52와 교환 → [185, 72, 63, 52, 38, 60, 62, 16, 5, 37, 22, 11]
셋째 삭제(185 제거): 11이 72·52·16과 교환 → [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]

  • [72, 63, 62, 60, …]처럼 내림차순으로 정렬된 나열: 힙은 부모가 자식보다 크기만 하면 되며, 삭제 연산이 전체를 정렬하지는 않는다.
  • [72, 52, 63, 38, 16, …]으로 시작하는 나열: 38은 첫 삭제에서 다섯째 칸에 자리 잡은 뒤 움직이지 않고, 넷째 칸은 셋째 삭제에서 16이 채운다.
  • 끝이 5, 11, 37, 22인 나열: 11은 두 자식 16과 5 중 큰 16과 교환되어 여덟째 칸에 놓이고, 5는 아홉째 칸에 그대로 남는다.
문제 2
다음과 같은 재귀적(recursive) 그래프 탐색 알고리즘을 반복적(iterative) 알고리즘으로 구현하고자 한다. 그래프가 인접리스트(adjacency list)에 저장되어 있다고 가정할 때, 구현을 위하여 필요한 자료구조와 전체 그래프를 순회(traversal)하는 알고리즘의 시간복잡도(time complexity)를 옳게 나타낸 것은? (단, 정점의 집합은 V, 간선의 집합은 E라고 가정한다)
(알고리즘)
void search( vertex v )
{
visited[v] = 1 ;
for each vertex w adjacent to v
if ( !visited[w] ) search( w ) ;
}
1queue, O( |E| )
2stack, O( ∣V∣2|V|^2 )
3stack, O( |V| + |E| )
4queue, O( ∣V∣2|V|^2 )
정답 및 해설

필요한 자료구조는 스택, 시간복잡도는 O(|V| + |E|)이다.

주어진 알고리즘은 방문하지 않은 인접 정점으로 재귀 호출을 이어 가는 깊이우선탐색이므로, 반복형으로 바꾸면 재귀 호출 스택을 명시적 스택으로 대신한다. 인접리스트에서는 각 정점을 한 번 방문하고 각 간선을 상수 번 검사하므로 정점 수와 간선 수의 합에 비례한다.

  • 큐와 O(|E|)의 조합: 큐는 너비우선탐색에 쓰는 자료구조이며, 정점 방문 비용인 |V| 항도 빠져 있다.
  • 스택과 O(∣V∣2)O(|V|^2)의 조합: 자료구조는 맞지만 제곱 시간은 인접행렬로 표현했을 때의 수행시간이다.
  • 큐와 O(∣V∣2)O(|V|^2)의 조합: 자료구조와 시간복잡도 모두 인접행렬 기반 너비우선탐색에 해당한다.
문제 3
가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?
1그래프에 존재하는 임의의 사이클을 구성하는 간선(edge)들 중 가중치가 가장 작은 간선은 항상 이 그래프의 최소비용 신장트리에 포함된다.
2Dijkstra의 최단경로 알고리즘 수행 결과 생성되는 신장트리는 항상 최소비용 신장트리이다.
3임의의 그래프에 대해 서로 다른 최소비용 신장트리가 항상 두 개 이상 존재한다.
4간선의 가중치 값들이 서로 다르고 최소비용 신장트리가 존재하는 경우, 가중치 값이 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.
정답 및 해설

간선 가중치가 모두 다를 때 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.

최소 간선 e를 뺀 최소비용 신장트리가 있다고 하면, e를 추가해 생긴 사이클에서 e보다 무거운 간선 하나를 빼면 비용이 더 작은 신장트리가 되어 모순이다. 크루스칼 알고리즘이 가장 먼저 선택하는 간선도 이 간선이다.

  • 사이클의 최소 간선이 항상 포함된다는 설명: 사이클 성질은 사이클의 가장 무거운 간선이 제외됨을 보장할 뿐이며, 최소 간선이라도 두 끝점을 더 가벼운 간선들로만 이루어진 다른 경로가 잇고 있으면 빠진다.
  • Dijkstra 결과가 최소비용 신장트리라는 설명: Dijkstra는 시작점에서 각 정점까지의 거리를 최소화하는 최단경로 트리를 만들 뿐, 간선 가중치의 총합을 최소화하지 않는다.
  • 최소비용 신장트리가 항상 두 개 이상이라는 설명: 간선 가중치가 모두 다르면 최소비용 신장트리는 유일하다.
문제 4
그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?
ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다.
ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.
ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 v2v^2개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O(v2v^2)이다.
11 개
22 개
33 개
44 개
정답 및 해설

옳은 문장은 ㄱ, ㅁ의 두 개이다.

무방향 그래프는 간선 (i, j)와 (j, i)가 같으므로 인접행렬이 대칭이다. 인접행렬 기반 너비우선탐색은 정점마다 행 하나(v칸)를 모두 훑으므로 O(v2)O(v^2)이다.

  • 차수의 합: 간선 하나가 양 끝 정점의 차수를 하나씩 올리므로 간선 수의 2배(2e2e)이다.
  • 완전그래프의 간선 수: 서로 다른 두 정점 쌍의 수인 v(v−1)2\dfrac{v(v-1)}{2}개이다.
  • 인접행렬의 메모리: 간선 수와 무관하게 v×vv \times v 행렬이 필요하므로 O(v2)O(v^2)이며, O(v + e)는 인접리스트의 공간이다.
문제 5
해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은?
ㄱ. n개의 자료가 있을 때 자료의 탐색에 걸리는 시간은 O(logn)이다.
ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓(bucket)에 사상(mapping)시킨다.
ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다.
ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다.
ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다.
1ㄴ, ㄷ
2ㄴ, ㅁ
3ㄱ, ㄹ
4ㄹ, ㅁ
정답 및 해설

옳은 것은 ㄹ, ㅁ이다.

해싱은 키의 대소 순서를 보존하지 않으므로 최대값을 찾으려면 모든 자료를 확인해야 해 O(n)이 걸린다. 좋은 해시함수는 충돌이 적고 주소에 고르게 분포해야 한다.

  • 탐색 시간 O(log n): 해싱의 평균 탐색 시간은 O(1)이며, O(log n)은 이진탐색이나 균형 탐색트리의 성능이다.
  • 서로 다른 자료가 항상 다른 버켓으로 간다는 설명: 키 공간이 주소 공간보다 커서 서로 다른 키가 같은 주소로 가는 충돌이 생긴다.
  • 적재 밀도가 높을수록 성능이 좋다는 설명: 적재 밀도가 높을수록 충돌이 늘어 탐색 성능이 나빠진다.
문제 6
스택, 큐, 리스트 자료구조에 대한 설명으로 옳지 않은 것은?
1연결리스트는 배열 구조와 비교하여 삽입, 삭제 시간이 많이 걸리고 메모리의 낭비가 많다.
2주로 힙(heap) 구조로 구현되는 우선순위 큐(priority queue)의 데이터 삽입은 임의로 이루어지나, 데이터의 삭제는 가장 큰 값이나 가장 작은 값부터 수행된다.
3스택은 함수 호출, 후위식 연산 등에 유용하게 사용되며, 연결 리스트로 구현할 수 있다.
4큐는 선입선출(First In First Out) 방식의 동작을 수행하므로 잡스케줄링(job scheduling) 등에 유용하게 사용된다.
정답 및 해설

옳지 않은 것은 연결리스트가 배열보다 삽입·삭제가 느리고 메모리 낭비가 많다는 설명이다.

연결리스트는 위치만 알면 링크만 바꿔 삽입·삭제하므로 원소를 밀고 당겨야 하는 배열보다 빠르다. 또 필요할 때마다 노드를 할당하므로 크기를 미리 크게 잡는 배열보다 빈 공간 낭비가 적다.

  • 우선순위 큐: 삽입 순서와 무관하게 우선순위가 가장 높은(최대 또는 최소) 원소부터 삭제되며 주로 힙으로 구현한다.
  • 스택: 후입선출 구조라 함수 호출과 후위식 계산에 쓰이며, 배열과 연결리스트 모두로 구현할 수 있다.
  • 큐: 선입선출 구조라 먼저 들어온 작업을 먼저 처리하는 작업 스케줄링에 쓰인다.
문제 7
깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A - B의 값은? (단, 루트노드의 레벨은 1로 한다)
12k−1+k+12^{k-1} + k + 1
22k−1+k−12^{k-1} + k - 1
32k−k−12^{k} - k - 1
42k−k+12^{k} - k + 1
정답 및 해설

A − B 의 값은 2k−k−12^{k} - k - 1이다.

최대 노드 수는 모든 레벨이 꽉 찬 포화 이진트리일 때로, 레벨 i에 2i−12^{i-1}개씩 있으므로 A=2k−1A = 2^{k} - 1이다.
최소 노드 수는 레벨마다 노드가 하나뿐인 편향 이진트리일 때로 B=kB = k이다.
A−B=(2k−1)−k=2k−k−1A - B = (2^{k} - 1) - k = 2^{k} - k - 1

  • 2k−1+k+12^{k-1} + k + 1: 깊이 1이면 노드가 하나뿐이라 A − B 는 0이어야 하는데 3이 된다.
  • 2k−1+k−12^{k-1} + k - 1: 깊이 1에서 1이 되어 0이 아니므로 맞지 않는다.
  • 2k−k+12^{k} - k + 1: 깊이 1에서 2가 되어 상수항 부호가 틀렸다.
문제 8
6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리(binary search tree)를 만들 때, 만들어진 이진 탐색트리의 높이가 가장 낮은 것은?
11, 2, 3, 5, 4, 6
24, 2, 5, 6, 1, 3
33, 1, 4, 2, 6, 5
42, 1, 3, 4, 6, 5
정답 및 해설

높이가 가장 낮은 것은 4, 2, 5, 6, 1, 3 순서의 삽입이다.

루트 4의 왼쪽에 2, 오른쪽에 5가 오고, 1과 3은 2의 양쪽 자식, 6은 5의 오른쪽 자식이 되어 높이 3(레벨 수 기준)이다. 이는 노드 6개인 이진트리가 가질 수 있는 최소 높이이다.

  • 1, 2, 3, 5, 4, 6: 1→2→3→5로 오른쪽으로만 이어지고 4가 5의 왼쪽에 붙어 높이 5이다.
  • 3, 1, 4, 2, 6, 5: 3→4→6→5 경로가 생겨 높이 4이다.
  • 2, 1, 3, 4, 6, 5: 2→3→4→6→5 경로가 생겨 높이 5이다.
문제 9
다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 데이터 ‘JAN’을 삽입한 결과로 옳은 것은?

1
2
3
4
정답 및 해설

JAN 삽입 후 LR 회전이 일어나 MAR가 새 루트가 되고, 왼쪽에 AUG(자식 APR, JAN), 오른쪽에 MAY(오른쪽 자식 NOV)가 오는 트리가 옳다.

JAN은 MAY보다 작고 AUG보다 크며 MAR보다 작으므로 MAR의 왼쪽 자식으로 들어간다. 이때 MAY의 왼쪽 높이는 3, 오른쪽 높이는 1이 되어 균형인수가 +2가 되고, 삽입 위치가 왼쪽 자식(AUG)의 오른쪽 서브트리이므로 LR 불균형이다.

LR 회전은 AUG를 중심으로 왼쪽 회전한 뒤 MAY를 중심으로 오른쪽 회전하는 것으로, 중간값인 MAR가 위로 올라가고 MAR의 왼쪽 자식 JAN은 AUG의 오른쪽 자식으로 옮겨진다.

  • MAR의 왼쪽에 JAN만 붙이고 루트를 MAY로 둔 트리: 이진 탐색 순서는 맞지만 MAY의 균형인수가 +2로 AVL 조건을 위반한다.
  • JAN을 NOV의 왼쪽 자식으로 둔 트리: JAN은 MAY보다 작으므로 오른쪽 서브트리에 올 수 없어 탐색 순서가 깨진다.
  • JAN을 APR의 오른쪽 자식으로 둔 트리: JAN은 AUG보다 크므로 AUG의 왼쪽 서브트리에 올 수 없고, 균형도 깨진다.
문제 10
다음과 같은 이진트리(binary tree)에서 전위순회(preorder traversal)와 중위순회(inorder traversal)를 했을 때, 두 순회 결과에서 노드 값의 방문 순서가 일치하는 횟수는? (전위순회의 k번째 노드값과 중위순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다)
13 회
24 회
35 회
46 회
정답 및 해설

두 순회 결과를 나란히 비교하면 같은 자리에서 일치하는 노드는 B, E, I, G로 4회이다.

전위순회(루트→왼쪽→오른쪽)는 A, B, D, E, H, C, F, I, J, G 순이고, 중위순회(왼쪽→루트→오른쪽)는 D, B, H, E, A, F, J, I, C, G 순이다.

2번째 B, 4번째 E, 8번째 I, 10번째 G가 같고 나머지 자리는 모두 다르다.

  • 3회: 네 자리 중 하나(예: 마지막 G)를 빠뜨렸을 때 나오는 값이다.
  • 5회: 실제 일치 수보다 많아, 순회 순서를 잘못 구했을 때 나오는 값이다.
  • 6회: H를 E의 오른쪽 자식으로 보는 등 트리 구조를 잘못 읽었을 때 나올 수 있는 값으로, 실제 일치는 4회뿐이다.
문제 11
점근적 표기법(asymptotic notation)에 관한 사칙연산으로 옳지 않은 것은?
1O(n) + O(n) = O(n)
2O(n2)+O(nlog⁡n)=O(n2)O(n^2) + O(n\log n) = O(n^2)
3O(n2)+O(n)=O(n2)O(n^2) + O(n) = O(n^2)
4O(log⁡n)⋅O(n2)=O(n2)O(\log n) \cdot O(n^2) = O(n^2)
정답 및 해설

옳지 않은 것은 O(log⁡n)⋅O(n2)=O(n2)O(\log n) \cdot O(n^2) = O(n^2)이다.

빅오의 곱은 각 함수를 곱하므로 O(log⁡n)⋅O(n2)=O(n2log⁡n)O(\log n) \cdot O(n^2) = O(n^2 \log n)이 된다. n2log⁡nn^2 \log n은 n2n^2보다 빠르게 증가하므로 O(n2)O(n^2)로 줄일 수 없다. 반면 덧셈은 가장 빠르게 증가하는 항만 남는다.

  • O(n) + O(n) = O(n): 상수배 차이는 무시되므로 성립한다.
  • O(n2)+O(nlog⁡n)=O(n2)O(n^2) + O(n\log n) = O(n^2): nlog⁡nn\log n이 n2n^2보다 느리게 증가하므로 성립한다.
  • O(n2)+O(n)=O(n2)O(n^2) + O(n) = O(n^2): 차수가 큰 항만 남으므로 성립한다.
문제 12
배열 A에 오름차순으로 저장된 데이터를 이진탐색(binary search)하기 위하여 반복적(iterative) 알고리즘을 이용하여 기술하였다. ㉠, ㉡에 들어갈 적당한 명령은?
procedure BINARYSEARCH(A, n, x, j)
lower ← 1 ; upper ← n ;
while lower ≤ upper do
mid ← the middle element;
case
: x > A(mid):    ㉠   ;
: x < A(mid):    ㉡   ;
: else : j ← mid ; return;
end
end
j ← 0 ;
end
1lower ← mid + 1 / upper ← mid - 1
2upper ← mid + 1 / lower ← mid - 1
3lower ← mid - 1 / upper ← mid + 1
4upper ← mid - 1 / lower ← mid + 1
정답 및 해설

㉠은 lower ← mid + 1, ㉡은 upper ← mid - 1이다.

x가 A(mid)보다 크면 찾는 값은 mid 오른쪽에 있으므로 하한을 mid 다음으로 올리고, 작으면 왼쪽에 있으므로 상한을 mid 앞으로 내린다. mid는 이미 비교했으므로 ±1로 제외해야 구간이 줄어 반복이 끝난다.

  • upper ← mid + 1 / lower ← mid - 1: x가 클 때 상한을 건드려 왼쪽 구간을 남기므로 찾는 값을 놓친다.
  • lower ← mid - 1 / upper ← mid + 1: 갱신할 변수는 맞지만 ±1 방향이 반대라 mid가 구간에 다시 포함되므로, lower와 upper가 같아진 뒤에도 구간이 줄지 않아 반복이 끝나지 않을 수 있다.
  • upper ← mid - 1 / lower ← mid + 1: x가 클 때 오른쪽이 아닌 왼쪽 구간을 남겨 찾는 값을 놓친다.
문제 13
다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 과정이 끝난 후, 피봇키(pivot key)를 중심으로 좌측에는 피봇키보다 작은 수, 우측에는 피봇키보다 큰 수들로 데이터가 분할된 상태를 올바르게 나타낸 것은? (단, 피봇키는 가장 왼쪽에 있는 값으로 한다)
(초기데이터)
[0][1][2][3][4][5][6][7][8][9]
8149635270

(보기의 인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9])
17 1 4 6 3 5 2 0 8 9
27 1 4 0 6 3 5 2 8 9
32 1 4 0 6 3 5 7 8 9
40 1 4 2 6 3 5 7 8 9
정답 및 해설

1단계 분할 결과는 7 1 4 0 6 3 5 2 8 9이다.

피봇 8을 두고 왼쪽 포인터 i는 8보다 큰 값, 오른쪽 포인터 j는 8보다 작은 값을 찾아 교환한다.
i는 9([3]), j는 0([9])에서 멈춰 교환 → 8 1 4 0 6 3 5 2 7 9
다시 i는 9([9]), j는 7([8])에서 멈추고 두 포인터가 엇갈린다.
마지막으로 피봇과 j 위치의 7을 교환 → 7 1 4 0 6 3 5 2 8 9

  • 7 1 4 6 3 5 2 0 8 9: 9와 0의 교환이 반영되지 않아 0이 [3]에 오지 않았다.
  • 2 1 4 0 6 3 5 7 8 9: 피봇은 j 위치의 7과 교환되므로 [0]에는 7, [7]에는 2가 그대로 있어야 한다.
  • 0 1 4 2 6 3 5 7 8 9: [0]에는 7, [3]에는 0, [7]에는 2가 와야 하므로 교환 결과와 맞지 않는다.
문제 14
K[1:2, 1:3, 1:2]로 선언된 3차원 배열을 행 우선순서(row major order)로 1차원 배열에 저장했을 때, 9번째에 저장되는 요소는?
1K(1, 2, 2)
2K(1, 3, 2)
3K(2, 2, 1)
4K(2, 3, 2)
정답 및 해설

아홉째로 저장되는 요소는 K(2, 2, 1)이다.

행 우선순서에서는 마지막 첨자가 가장 빨리 변한다. 첫째 첨자 하나당 3 × 2 = 6개, 둘째 첨자 하나당 2개가 묶인다.
pos(i,j,k)=(i−1)×6+(j−1)×2+(k−1)+1\mathrm{pos}(i,j,k) = (i-1)\times 6 + (j-1)\times 2 + (k-1) + 1
pos(2,2,1)=6+2+0+1=9\mathrm{pos}(2,2,1) = 6 + 2 + 0 + 1 = 9

  • K(1, 2, 2): 0+2+1+1=40 + 2 + 1 + 1 = 4로 넷째이다.
  • K(1, 3, 2): 0+4+1+1=60 + 4 + 1 + 1 = 6으로 여섯째이다.
  • K(2, 3, 2): 6+4+1+1=126 + 4 + 1 + 1 = 12로 마지막 열두째이다.
문제 15
다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 모든 원소들의 값이 0인 행렬을 상삼각 행렬(upper triangular matrix)이라고 한다.

A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가?
1B[4998]
2B[4999]
3B[5000]
4B[5001]
정답 및 해설

A[90][93]은 B[4998]에 저장된다.

상삼각행렬을 행 우선으로 저장하면 i행에는 열 i부터 99까지 100−i개의 원소가 있으므로, A[i][j]의 위치는 앞선 0~(i−1)행의 원소 수 합에 (j−i)를 더한 값이다.

∑k=089(100−k)=90×100−89×902=9000−4005=4995\sum_{k=0}^{89}(100-k) = 90 \times 100 - \dfrac{89 \times 90}{2} = 9000 - 4005 = 4995
4995+(93−90)=49984995 + (93 - 90) = 4998

  • B[4999]: 위치를 1부터 센 것처럼 하나를 더한 값이다.
  • B[5000]: 행 내부 오프셋 (j−i)=3 대신 다른 값을 더하는 등 위치 계산을 잘못한 값이다.
  • B[5001]: 앞선 행들의 원소 수 합 4995에 오프셋을 잘못 더한 값으로, 실제 위치보다 3칸 뒤이다.
문제 16
다음 전위식(preorder expression)으로 표현된 수식을 후위식(postorder expression)으로 변환하였다. 변환된 수식의 4번째 연산자는?
(전위식) - + - AB * / CDEF
1* 연산자
2+ 연산자
3- 연산자
4/ 연산자
정답 및 해설

후위식의 넷째 연산자는 + 연산자이다.

전위식을 연산자와 두 피연산자 단위로 묶으면 ((A − B) + (C / D) * E) − F 구조이다. 이를 후위식으로 바꾸면 A B − C D / E * + F −이고, 연산자 순서는 −, /, *, +, − 이다.

  • * 연산자: 셋째로 나온다.
  • − 연산자: 첫째와 다섯째에 나오며 넷째가 아니다.
  • / 연산자: 둘째로 나온다.
문제 17
스택을 일차원 배열 stack[0 : 99]를 이용하여 구현하고자 한다. top 변수의 초기값은 -1로 설정하며, top이 -1이면 스택은 비어있다는 것을 나타낸다. C 언어를 이용하여 스택에 데이터를 추가하는 함수 push()와 삭제하는 함수 pop()을 다음과 같이 작성하였을 때, ㉠과 ㉡에 들어갈 내용은?
void push(int *top, int data) { // 스택에 data를 추가
if ( *top >= 99) { stack_full() ; return ; }
㉠;
}
int pop(int *top) { // 스택에서 데이터를 삭제 후 반환
if ( *top == -1) { return stack_empty() ; }
㉡;
}
1stack[*top++] / return stack[--*top]
2stack[*top++] / return stack[*top--]
3stack[++*top] / return stack[*top--]
4stack[++*top] / return stack[--*top]
정답 및 해설

㉠은 stack[++*top](top을 먼저 올린 뒤 저장), ㉡은 return stack[*top--](현재 top 값을 반환한 뒤 내림)이다.

top은 마지막 원소의 위치를 가리키고 빈 스택에서 −1이므로, push는 top을 하나 올린 칸에 저장해야 stack[0]부터 채워진다. pop은 지금 top 칸의 값을 꺼낸 뒤 top을 내려야 한다. 엄밀한 C 문법에서는 후위 --가 *보다 먼저 결합하므로 의도대로 동작하려면 stack[(*top)--]처럼 괄호를 써야 한다.

  • stack[*top++] / return stack[--*top]: push가 올리기 전 위치(빈 스택이면 −1)에 저장해 범위를 벗어나고, pop은 꼭대기 아래 칸의 값을 반환한다.
  • stack[*top++] / return stack[*top--]: pop은 맞지만 push가 올리기 전 위치에 저장한다.
  • stack[++*top] / return stack[--*top]: push는 맞지만 pop이 꼭대기가 아닌 그 아래 칸의 값을 반환한다.
문제 18
원형 연결리스트(circular linked list)의 길이를 계산하기 위한 C함수를 작성하려고 한다. 밑줄 친 ㉠과 ㉡부분에 알맞은 명령은? (단, 원형 연결리스트의 길이는 노드의 개수로 정의하고, 원형 연결리스트의 시작 포인터는 ptr이라고 가정한다)
struct list_node {
char data ;
struct list_node *link;
}
typedef struct list_node *list_pointer;
int CListLength(list_pointer ptr){
list_pointer temp ;
int count = 0 ;
if (  ㉠  ) {
temp = ptr ;
do { count + + ;
} while (  ㉡  ) ;
}
return count;
}
1!ptr / temp->link != ptr
2ptr / temp=temp->link, temp != ptr
3!ptr / temp=temp->link, temp == ptr
4ptr / temp->link == ptr
정답 및 해설

㉠은 ptr, ㉡은 temp=temp->link, temp != ptr이다.

리스트가 비어 있지 않을 때(ptr가 NULL이 아닐 때)만 세기 시작하고, do-while 안에서 개수를 센 뒤 temp를 다음 노드로 옮겨 시작 노드로 돌아오면 멈춘다. 쉼표 연산자는 앞의 이동을 수행한 뒤 뒤의 비교 결과를 조건으로 쓴다.

  • !ptr / temp->link != ptr: 빈 리스트일 때만 세려 해 NULL 접근이 생기고, temp도 이동하지 않는다.
  • !ptr / temp=temp->link, temp == ptr: 시작 조건이 반대이고, 시작 노드로 돌아왔을 때 오히려 반복을 계속하는 반대 조건이다.
  • ptr / temp->link == ptr: temp를 옮기지 않아 노드 수를 셀 수 없다(노드가 하나면 무한 반복, 여럿이면 1을 반환).
문제 19
n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결리스트(singly linked list)로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?
1포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제
2리스트의 길이를 출력
3포인터값이 주어진 임의의 노드 앞에 새로운 노드 추가
4마지막 노드의 데이터를 출력
정답 및 해설

시간 복잡도가 가장 낮은 연산은 포인터가 가리키는 노드의 다음 노드 삭제로 O(1)이다.

가리키는 노드의 링크를 다음 노드의 링크로 바꾸기만 하면 되므로 탐색이 필요 없다. 나머지 연산은 단순 연결리스트에서 리스트를 처음부터 따라가야 해 O(n)이다.

  • 리스트 길이 출력: 길이를 따로 저장하지 않으면 모든 노드를 세어야 한다.
  • 주어진 노드 앞에 새 노드 추가: 단순 연결리스트에는 앞 노드로 가는 링크가 없어 선행 노드를 처음부터 찾아야 한다.
  • 마지막 노드의 데이터 출력: 꼬리 포인터가 없으면 끝까지 따라가야 한다.
문제 20
자료들이 단순 연결리스트(singly linked list)에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은?
메모리주소datalink
2000A2020
2010B2030
2020C2010
2030D0
1A의 link → 2030
2B의 link → 2010
3B의 link → 2020
4C의 link → 2030
정답 및 해설

B를 삭제하면 C의 link가 2030으로 바뀐다.

link를 따라가면 A(2000) → C(2020) → B(2010) → D(2030) 순서이므로 B의 선행 노드는 C이다. C의 link를 B의 다음 노드 주소인 2030으로 바꾸면 B가 리스트에서 빠진다.

  • A의 link → 2030: B뿐 아니라 C까지 리스트에서 빠진다.
  • B의 link → 2010: 삭제할 노드의 링크를 바꾸는 것은 의미가 없고, C가 여전히 B를 가리킨다.
  • B의 link → 2020: C가 여전히 B를 가리키며 C와 B 사이에 순환이 생긴다.