[7급 국가직 자료구조론] 25년 1회차
7급 국가직 자료구조론 기출문제 전 회차를 한 권으로 — PDF 전자책(문제집·정답해설집)
7급 국가직 자료구조론 기출문제

25년 1회차

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

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

25년 1회차

총 25문항 · 객관식 · 정답·해설 포함
문제 1
55개 간선(edge)을 갖는 무방향 완전 그래프의 정점(vertex) 개수는?
18
29
310
411
정답 및 해설

정점이 n개인 무방향 완전 그래프의 간선 수는 n(n−1)2\dfrac{n(n-1)}{2}이므로 간선이 55개이면 정점은 11개이다.

공식: n(n−1)2=55\dfrac{n(n-1)}{2} = 55
대입: n(n−1)=110=11×10n(n-1) = 110 = 11 \times 10
결과: n=11n = 11

  • 정점 8개: 간선은 8×72=28\dfrac{8 \times 7}{2} = 28개이다.
  • 정점 9개: 간선은 9×82=36\dfrac{9 \times 8}{2} = 36개이다.
  • 정점 10개: 간선은 10×92=45\dfrac{10 \times 9}{2} = 45개이다.
문제 2
초기 데이터에 대하여 오름차순 정렬을 2번 연산 수행한 후의 결과가 다음과 같을 때, 사용한 정렬 방법은?
○ 초기 데이터: 21, 3, 18, 33, 9, 15
○ 2번 연산 수행 결과: 3, 18, 21, 33, 9, 15
1삽입 정렬
2선택 정렬
3버블 정렬
4기수 정렬
정답 및 해설

두 차례 수행 뒤 앞쪽 3개(3, 18, 21)만 정렬되고 뒤쪽(33, 9, 15)은 그대로이므로 삽입 정렬이다.

삽입 정렬은 매 단계 다음 원소를 앞쪽 정렬 구간의 제자리에 끼워 넣는다.
1회: 3을 21 앞에 삽입 → 3, 21, 18, 33, 9, 15
2회: 18을 3과 21 사이에 삽입 → 3, 18, 21, 33, 9, 15

  • 선택 정렬: 최솟값을 차례로 앞에 두므로 2회 후 3, 9, 18, 33, 21, 15가 된다.
  • 버블 정렬: 큰 값이 뒤로 밀려나므로 2회 후 3, 18, 9, 15, 21, 33이 된다.
  • 기수 정렬: 일의 자리 분배 후 21, 3, 33, 15, 18, 9가 되고, 십의 자리까지 2회 수행하면 전체가 정렬된다.
문제 3
다음 C 코드로 표현한 알고리즘의 시간 복잡도는?
Algorithm(int n) {
    int i, j, k;
    int sum = 0;
    for(i = 0; i < 1000; i++)
        for(j = 1; j < (n - 500); j++)
            for(k = (n - 100); k < (n + 100); k++)
                sum = sum + i + j + k;
}
1O(1)O(1)
2O(n)O(n)
3O(n2)O(n^2)
4O(n3)O(n^3)
정답 및 해설

바깥 루프는 1000회, 가장 안쪽 루프는 200회로 고정되고 n에 비례하는 것은 가운데 루프뿐이므로 O(n)O(n)이다.

반복 횟수: i 루프 1000회 × j 루프 n−502n-502회(j = 1 ~ n-502) × k 루프 200회
총 연산: 1000×200×(n−502)1000 \times 200 \times (n-502)
상수 계수를 버리면 선형 시간이다.

  • O(1)O(1): j 루프 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • O(n2)O(n^2): k 루프는 n−100n-100부터 n+100n+100 직전까지로 폭이 200으로 고정되어 n에 비례하지 않는다.
  • O(n3)O(n^3): i 루프도 1000회 고정이라 n에 의존하는 루프는 하나뿐이다.
문제 4
이진 트리(binary tree) 중에서 전위 순회(preorder traversal)와 중위 순회(inorder traversal)한 결과가 동일한 것은?
1[그림]
2[그림]
3[그림]
4[그림]
정답 및 해설

전위 순회와 중위 순회 결과가 같은 것은 모든 노드가 오른쪽 자식만 갖는 오른쪽 사향 트리(1 → 2 → 3 → 4 → 5)이다.

전위는 루트 → 왼쪽 → 오른쪽, 중위는 왼쪽 → 루트 → 오른쪽 순서이므로, 왼쪽 서브트리가 하나도 없으면 두 순회 모두 루트 → 오른쪽 순서가 되어 결과가 같다. 이 트리는 두 순회 모두 1, 2, 3, 4, 5이다.

  • 5를 루트로 왼쪽 자식만 이어진 왼쪽 사향 트리: 전위는 5, 4, 3, 2, 1, 중위는 1, 2, 3, 4, 5로 정반대이다.
  • 2를 루트로 왼쪽에 1, 오른쪽에 3 → 4 → 5가 이어진 트리: 전위는 2, 1, 3, 4, 5, 중위는 1, 2, 3, 4, 5로 앞부분이 다르다.
  • 3을 루트로 왼쪽에 2 → 1, 오른쪽에 4 → 5가 있는 트리: 전위는 3, 2, 1, 4, 5, 중위는 1, 2, 3, 4, 5로 다르다.
문제 5
다음 그래프의 인접 행렬이 아래와 같을 때, (가)～(사)에 들어갈 값을 모두 더한 결과는?
abcde
a0(가)110
b(나)000(다)
c100(라)1
d10101
e0(마)1(바)(사)

14
25
36
47
정답 및 해설

(가)~(사)의 합은 6이다.

그래프의 간선은 a-b, a-c, a-d, b-e, c-d, c-e, d-e의 7개이며, 무방향 그래프의 인접 행렬은 대칭이고 자기 자신으로의 간선이 없으면 대각 원소가 0이다.

  • (가)·(나): a와 b가 연결되어 있으므로 둘 다 1이다.
  • (다)·(마): b와 e가 연결되어 있으므로 둘 다 1이다.
  • (라)·(바): c-d, d-e 간선이 있으므로 둘 다 1이다.
  • (사): e 자신으로의 간선이 없으므로 대각 원소는 0이다.

따라서 1이 6개, 0이 1개로 합은 6이다.

문제 6
다음 C 코드에서 power(2.0, 20, 0)를 호출할 때, 변수 c의 마지막 출력값은?
double power(double x, int n, int c)
{
    printf("c : %d\n", c);
    if(n == 0) return 1;
    else if(n % 2 == 0) {
        c++;
        return power(x * x, n / 2, c);
    }
    else {
        c++;
        return x * power(x * x, (n - 1) / 2, c);
    }
}
15
26
37
48
정답 및 해설

호출될 때마다 c를 먼저 출력하고 n이 0이 될 때까지 c를 1씩 늘려 재귀하므로 마지막 출력값은 5이다.

추적 (n, 출력되는 c): (20, 0) → (10, 1) → (5, 2) → (2, 3) → (1, 4) → (0, 5)
n이 0인 호출은 c를 출력한 뒤 c를 늘리지 않고 1을 반환하며 끝난다.

n은 짝수면 절반, 홀수면 (n−1)/2(n-1)/2로 줄어들어 재귀 단계 수는 n의 이진수 자릿수(20 = 10100, 다섯 자리)와 같다.

문제 7
다음 단정도(32비트) IEEE 754 표준 방식으로 표현된 2진수를 10진수 형식으로 옳게 변환한 것은?
0931
11000001101001000000000000000000
110.5
2－10.75
3－20.5
4－20.75
정답 및 해설

부호 비트 1, 지수 131, 가수 01001이므로 값은 -20.5이다.

부호 비트: 1 → 음수
지수 8비트: 10000011 = 131 → 바이어스 127을 빼면 131−127=4131 - 127 = 4
가수 23비트: 0100100…0 → 1.01001(2)1.01001_{(2)}

값: −1.01001(2)×24=−10100.1(2)-1.01001_{(2)} \times 2^{4} = -10100.1_{(2)}
결과: −(16+4+0.5)=−20.5-(16 + 4 + 0.5) = -20.5

  • 10.5: 부호 비트가 1이므로 양수가 될 수 없다.
  • -10.75: 1010.11(2)1010.11_{(2)}이 되어야 하므로 지수가 3이어야 하는데 실제 지수는 4이다.
  • -20.75: 10100.11(2)10100.11_{(2)}이 되어야 하므로 가수가 010011로 끝나야 하는데 실제 가수는 01001 뒤가 모두 0이다.
문제 8
다음 선형 리스트에서 연산 1과 연산 2가 수행된 후 리스트 상태와 두 연산에 사용된 원소의 총이동 횟수를 바르게 연결한 것은?
[0][1][2][3][4][5][6][7]
ABCDEFG
연산 1: 인덱스 1번에 원소 H 삽입
연산 2: 인덱스 3번 원소 삭제
리스트 상태　　총이동 횟수
1
[0][1][2][3][4][5][6][7]
AHCEFG
　　3
2
[0][1][2][3][4][5][6][7]
AHCEFG
　　3
3
[0][1][2][3][4][5][6][7]
AHBDEFG
　　10
4
[0][1][2][3][4][5][6][7]
AHBDEFG
　　10
정답 및 해설

삽입에서 6회, 삭제에서 4회 원소가 이동하므로 결과는 A, H, B, D, E, F, G이고 총이동 10회이다.

연산 1: 인덱스 1에 H를 넣으려면 B~G 6개를 한 칸씩 뒤로 옮긴다 → A, H, B, C, D, E, F, G (6회)
연산 2: 이제 인덱스 3의 원소는 C이므로 C를 지우고 D~G 4개를 한 칸씩 앞으로 당긴다 → A, H, B, D, E, F, G (4회)

  • A, H, C, 빈칸, E, F, G (3회): H가 B를 덮어써 B가 사라지고, 삭제 후 빈칸도 메우지 않은 상태다.
  • A, H, C, E, F, G (3회): 삽입 때 B를 뒤로 밀지 않고 덮어써 B가 사라진 상태다.
  • A, H, B, 빈칸, D, E, F, G (10회): 삭제 후 뒤 원소를 앞으로 당기지 않아 선형 리스트의 연속성이 깨진 상태다.
문제 9
다음은 힙 정렬(heap sort) 알고리즘을 구현한 C 코드이다. 리스트 L이 (61, 11, 59, 15, 48, 19)로 주어졌을 때, for 문에 관한 설명으로 옳은 것만을 모두 고르면? (단, 리스트 L을 배열로 표현할 때 색인 1부터 저장하고, n은 리스트의 크기를 나타낸다)
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

void heap_sort(int L[], int n){
    int i, temp;
    for(i = n/2; i >= 1; i--)  ······································ (가)
        adjust(L, i, n);
    for(i = n-1; i >= 1; i--) {  ·································· (나)
        SWAP(L[1], L[i+1], temp);
        adjust(L, 1, i);
    }
}

void adjust(int L[], int root, int n) {
    int next = 2 * root;
    int X = L[root];
    while(next <= n) {
        if(next < n && L[next] < L[next + 1])
            next++;
        if(X > L[next]) break;
        L[next / 2] = L[next];
        next *= 2;
    }
    L[next / 2] = X;
}
ㄱ. (가) for 문을 수행한 후 리스트 L에는 (61, 48, 59, 15, 19, 11)이 저장된다.
ㄴ. (나) for 문을 첫 1회 수행한 후 리스트 L에는 (59, 48, 19, 15, 11, 61)이 저장된다.
ㄷ. (나) for 문의 시간 복잡도는 O(nlog⁡n)O(n\log n)이다.
1ㄱ, ㄴ
2ㄱ, ㄷ
3ㄴ, ㄷ
4ㄱ, ㄴ, ㄷ
정답 및 해설

ㄱ은 틀리고 ㄴ과 ㄷ이 옳으므로 옳은 것은 ㄴ, ㄷ이다.

(가) 힙 구성: i=3에서 59와 자식 19 비교 → 그대로. i=2에서 11이 큰 자식 48(L[5])과 자리를 바꾼다. i=1에서 61이 두 자식보다 커서 그대로.
결과: (61, 48, 59, 15, 11, 19)

(나) 첫 회(i=5): L[1]과 L[6] 교환 → (19, 48, 59, 15, 11, 61)
adjust(L, 1, 5): 19가 큰 자식 59와 자리를 바꿈 → (59, 48, 19, 15, 11, 61)

  • ㄱ(틀림): 11은 큰 자식 48과 바뀌어 L[5]에 들어가므로 끝의 두 값은 11, 19 순서다.
  • ㄴ(옳음): 위 추적 결과와 같다.
  • ㄷ(옳음): (나) for 문은 약 n회 반복하고 매번 adjust가 힙 높이 O(log⁡n)O(\log n)만큼 내려가므로 O(nlog⁡n)O(n\log n)이다.
문제 10
다음 8개의 데이터를 순서대로 삽입하여 AVL 트리를 구성하였을 때, 이에 대한 설명으로 옳은 것은?
19, 7, 10, 15, 25, 32, 17, 5
1루트 노드의 번호는 17이다.
2중위 순회했을 때 네 번째 방문하는 노드의 번호는 15이다.
3전위 순회했을 때 세 번째 방문하는 노드의 번호는 10이다.
4후위 순회했을 때 다섯 번째 방문하는 노드의 번호는 32이다.
정답 및 해설

완성된 AVL 트리를 중위 순회하면 네 번째로 방문하는 노드는 15이다.

10 삽입: 19-7-10의 LR 불균형 → 10을 루트로 회전 (왼쪽 7, 오른쪽 19)
32 삽입: 루트 10의 오른쪽이 2 더 높은 RR 불균형 → 10 기준 좌회전으로 19가 루트가 된다.
17, 5 삽입 후에는 균형이 유지된다.

최종 트리: 루트 19, 왼쪽 10(자식 7, 15), 오른쪽 25(오른쪽 자식 32), 7의 왼쪽 5, 15의 오른쪽 17
중위: 5, 7, 10, 15, 17, 19, 25, 32

  • 루트 노드는 17이 아니라 19이다.
  • 전위 순회(19, 10, 7, 5, 15, 17, 25, 32)의 세 번째 노드는 7이다.
  • 후위 순회(5, 7, 17, 15, 10, 32, 25, 19)의 다섯 번째 노드는 10이다.
문제 11
다음 원형 큐에 대해 1부터 7까지 연산을 차례로 수행했을 때, 수행이 완료된 후 큐의 상태는? (단, 현재 상태는 front = 2, rear = 3이다)
[0][1][2][3][4][5]
A
연산 1: 원소 B 삽입
연산 2: 원소 한 개 삭제
연산 3: 원소 C 삽입
연산 4: 원소 D 삽입
연산 5: 원소 두 개 삭제
연산 6: 원소 E 삽입
연산 7: 원소 F 삽입
1
[0][1][2][3][4][5]
AEF
2
[0][1][2][3][4][5]
DFE
3
[0][1][2][3][4][5]
FEA
4
[0][1][2][3][4][5]
DEF
정답 및 해설

연산을 모두 마치면 큐에는 D, E, F가 인덱스 0, 1, 2에 남는다 (front = 5, rear = 2).

front는 첫 원소의 한 칸 앞, rear는 마지막 원소 위치이며 인덱스는 (i+1) mod 6(i+1) \bmod 6으로 순환한다.

B 삽입: rear 4 → 삭제: front 3 (A 제거) → C 삽입: rear 5 → D 삽입: rear 0
두 개 삭제: front 4 (B 제거), front 5 (C 제거) → E 삽입: rear 1 → F 삽입: rear 2

  • A, E, F가 남은 상태: A, B, C는 이미 삭제되었으므로 A가 남을 수 없다.
  • D, F, E가 [0], [4], [5]에 있는 상태: rear는 0 다음 1, 2로 진행하므로 E, F는 [1], [2]에 들어간다.
  • F, E, A가 남은 상태: 인덱스가 거꾸로 진행된 것이며 삭제된 A도 남아 있다.
문제 12
비어 있는 초기 상태의 이진 트리에 다섯 개의 키(1, 2, 3, 4, 5)를 순서대로 하나씩 삽입하면서 레드－블랙 트리를 만든 후, 중위 순회한 결과는?
11, 2, 3, 4, 5
21, 3, 5, 4, 2
32, 1, 3, 5, 4
42, 1, 4, 3, 5
정답 및 해설

레드-블랙 트리는 회전과 재색칠 후에도 이진 탐색 트리 성질을 유지하므로 중위 순회 결과는 항상 오름차순인 1, 2, 3, 4, 5이다.

1(루트, 흑) → 2(적) → 3 삽입 시 적색 연속으로 좌회전해 2가 루트 → 4 삽입 시 삼촌 1이 적색이라 재색칠 → 5 삽입 시 3 기준 좌회전으로 4가 3과 5의 부모가 된다.
최종 형태: 루트 2, 왼쪽 1, 오른쪽 4(자식 3, 5)

  • 1, 3, 5, 4, 2: 최종 트리의 후위 순회 결과다.
  • 2, 1, 3, 5, 4: 오름차순이 아니므로 이진 탐색 트리의 중위 순회가 될 수 없다.
  • 2, 1, 4, 3, 5: 최종 트리의 전위 순회 결과다.
문제 13
다음 이진 트리에 대해 전위, 중위, 후위 순회(postorder traversal)를 수행할 때, 각 순회 5번째 노드를 바르게 연결한 것은?

전위　　중위　　후위
1E　　H　　E
2G　　E　　H
3H　　E　　E
4H　　B　　I
정답 및 해설

다섯째 노드는 전위 H, 중위 E, 후위 E이다.

트리는 A의 왼쪽 자식 B, 오른쪽 자식 C이고, B 아래 D(자식 G, H)와 E(오른쪽 자식 I), C의 오른쪽 자식 F(자식 J, K)로 이루어진다.

전위: A, B, D, G, H, E, I, C, F, J, K
중위: G, D, H, B, E, I, A, C, J, F, K
후위: G, H, D, I, E, B, J, K, F, C, A

  • E, H, E 조합: 전위의 다섯째는 E가 아니라 H이고, 중위의 다섯째도 H가 아니라 E이다.
  • G, E, H 조합: G는 전위 넷째, H는 후위 둘째이다.
  • H, B, I 조합: B는 중위 넷째, I는 후위 넷째이다.
문제 14
다음 C 코드를 사용하여 배열을 선언하였고 arr[0][0][0]의 주소를 α라고 할 때, arr[3][4][2]의 행 우선 순서 주소는?
char arr[6][5][4];
1α ＋ 34
2α ＋ 78
3α ＋ 96
4α ＋ 112
정답 및 해설

행 우선 순서에서 arr[3][4][2]는 시작 주소로부터 78바이트 떨어져 있으므로 주소는 α + 78이다.

공식: 오프셋 = (i×5×4+j×4+k)×1(i \times 5 \times 4 + j \times 4 + k) \times 1 (char는 1바이트)
대입: 3×20+4×4+23 \times 20 + 4 \times 4 + 2
결과: 60+16+2=7860 + 16 + 2 = 78

  • α + 34: arr[1][3][2]의 위치이다.
  • α + 96: arr[4][4][0]의 위치이다.
  • α + 112: arr[5][3][0]의 위치이다.
문제 15
다음은 정렬된 정수 배열에 대한 이진 탐색(binary search)을 구현한 C 코드이다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?
int BSearch(int data[], int size, int target) {
    int mid, left = 0, right = size - 1;
    while(left <= right) {
        mid = [ (가) ];
        if(target == data[mid]) return mid;
        else if(target > data[mid]) left = [ (나) ];
        else right = [ (다) ];
    }
    return -1;
}
(가)　　(나)　　(다)
1(left+right) // 2　　mid-1　　mid+1
2right-(left-right) // 2　　mid　　left
3(left+right) / 2　　mid+1　　mid-1
4left+(right-left) / 2　　right　　mid
정답 및 해설

중간 인덱스는 (left+right) / 2이고, 찾는 값이 크면 left = mid+1, 작으면 right = mid-1로 범위를 줄인다.

C에서 정수끼리의 /는 몫만 남기는 정수 나눗셈이다. 이미 비교한 mid는 다음 범위에서 제외해야 범위가 매번 줄어 반복이 끝난다.

  • (left+right) // 2, mid-1, mid+1: C에서 //는 주석 기호이고, 찾는 값이 클 때 left를 mid-1로 두면 탐색 방향이 반대가 된다.
  • right-(left-right) // 2, mid, left: 중간값 식이 틀렸고, left = mid로 두면 범위가 줄지 않아 무한 반복될 수 있다.
  • left+(right-left) / 2, right, mid: 중간값 식은 맞지만 left = right, right = mid로는 범위를 올바르게 좁히지 못한다.
문제 16
다음 파이썬 프로그램의 실행 결과는?
class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next
class SinglyLinkedList:
    def __init__(self):
        self.head = None
    def func1(self, data):
        node = self.head
        self.head = Node(data, node)
    def func2(self, data):
        if self.head is None: self.func1(data)
        else :
            node = self.head
            while node.next is not None: node = node.next
            node.next = Node(data, None)
    def func3(self, pos):
        if pos < 0: return None
        node = self.head
        while pos > 0 and node != None:
            node = node.next
            pos -= 1
        return node
    def showList(self):
        node = self.head
        while node :
            print(node.data, end=' ')
            node = node.next

myList = SinglyLinkedList()
myList.func1(1); myList.func2(2)
myList.func1(3); myList.func2(4)
myList.func2(myList.func3(0).data)
myList.showList()
11 2 3 4
22 3 4 1
33 1 2 4 3
43 3 1 2 4
정답 및 해설

최종 리스트를 출력하면 3 1 2 4 3이다.

func1은 맨 앞 삽입, func2는 맨 뒤 삽입, func3(pos)은 head에서 pos칸 이동한 노드를 반환한다.

func1(1) → 1
func2(2) → 1 2
func1(3) → 3 1 2
func2(4) → 3 1 2 4
func3(0)은 head 노드(데이터 3)이므로 func2(3) → 3 1 2 4 3

  • 1 2 3 4: 원소가 4개뿐이어서 마지막 func2 호출로 추가된 노드가 빠졌다.
  • 2 3 4 1: 원소가 4개뿐이고 삽입 순서와도 맞지 않는다.
  • 3 3 1 2 4: 마지막 3을 맨 앞에 붙인 결과지만 func2는 맨 뒤에 붙인다.
문제 17
다음 C 프로그램의 실행 결과는?
#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int value;
    struct ListNode* next;
} ListNode;

int func(ListNode* p, int n) {
    int i, sum = 0;
    for(i = 0; i < n; i++) {
        sum += p->value;
        p = p->next;
    }
    return sum;
}

int main() {
    int i, s, SIZE = 5;
    ListNode* p[SIZE];
    for(i = 0; i < SIZE; i++) {
        p[i] = (ListNode*)malloc(sizeof(ListNode));
        p[i]->value = i;
    }
    for(i = 0; i < SIZE-1; i++)
        p[i]->next = p[i+1];
    p[SIZE-1]->next = p[0];
    s = func(p[4], 7);
    printf("%d", s);

    return 0;
}
114
215
316
417
정답 및 해설

원형 연결 리스트에서 값 4인 노드부터 7개 노드의 값을 더하면 14이다.

p[i]의 value는 i이고 p[4]의 next가 p[0]이라 원형으로 이어진다.
방문 값: 4, 0, 1, 2, 3, 4, 0
합: 4+0+1+2+3+4+0=144+0+1+2+3+4+0 = 14

문제 18
인접 행렬로 표현된 방향 그래프 중 위상 정렬이 불가능한 것은?
1[0100001000010000]\begin{bmatrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
2[0011001100010000]\begin{bmatrix}0 & 0 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
3[0111001100010000]\begin{bmatrix}0 & 1 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
4[0101001010010000]\begin{bmatrix}0 & 1 & 0 & 1\\0 & 0 & 1 & 0\\1 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
정답 및 해설

3행 1열이 1인 행렬은 1→2→3→1의 사이클을 포함하므로 위상 정렬이 불가능하다.

위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 행 i, 열 j의 1을 간선 i→j로 읽을 때 대각선 아래가 모두 0인 상삼각 행렬은 번호가 큰 정점에서 작은 정점으로 가는 간선이 없어 사이클이 생기지 않는다.

  • 1→2→3→4의 한 줄 경로 행렬: 상삼각이므로 1, 2, 3, 4 순으로 정렬된다.
  • 1과 2가 각각 3, 4로, 3이 4로 가는 행렬: 상삼각이므로 위상 정렬이 가능하다.
  • 번호가 작은 정점에서 큰 정점으로 모든 간선이 있는 행렬: 상삼각이므로 위상 정렬이 가능하다.
문제 19
다음 C 프로그램의 실행 결과는?
#include <stdio.h>
int func(int key, int low, int high, int* list) {
    list[high+1] = key;
    int i = 0;
    for(i = low; list[i] != key; i++);
    if(i == (high+1)) return -1;
    return i;
}

int main(int argc, char* argv[]) {
    int list[100] = {1, 2, 3, 4, 5, 6, 7};
    printf("%d\n", func(3, 4, 6, list));

    return 0;
}
1－1
20
33
44
정답 및 해설

찾는 키 3이 탐색 범위(인덱스 4~6)에 없으므로 보초 위치에서 멈추고 -1을 반환한다.

list[high+1] = list[7]에 key 3을 보초(sentinel)로 넣는다.
i=4부터: list[4]=5, list[5]=6, list[6]=7, list[7]=3 → i=7에서 멈춤
i == high+1이므로 -1 반환

  • 0: 탐색은 인덱스 4부터 시작하므로 0이 반환될 수 없다.
  • 3: 함수는 키 값이 아니라 찾은 인덱스를 반환한다.
  • 4: 시작 인덱스 low이며 list[4]는 5라 키와 다르다.
문제 20
다음 수식을 후위 표기법(postfix notation)으로 변환한 후, 스택을 이용하여 계산하려고 한다. 계산 과정에서 스택에 일곱 번째로 삽입(push)하는 값은?
(A － B) * C － (D ＋ E) / F
1C
2D
3E
4(D ＋ E)
정답 및 해설

후위식은 A B - C * D E + F / - 이고, 계산 중 일곱 번째로 push되는 값은 E이다.

피연산자는 push하고, 연산자는 두 값을 pop해 계산한 결과를 다시 push한다.
push 순서: A → B → A-B → C → (A-B)*C → D → E → D+E → F → (D+E)/F → 최종값

  • C: 네 번째로 push된다.
  • D: 여섯 번째로 push된다.
  • (D + E): 여덟 번째로 push된다.
문제 21
다음 C 프로그램의 출력 결과는?
#include <stdio.h>
#include <stdlib.h>
void processArray(int* array, int size) {
    int i = 0;
    for(i = 0; i < size; i++) {
        array[i] += i * 2;
    }
}
void modifyArray(int* array) {
    *(array + 1) = 10;
    *(array + 3) = 20;
}
int main() {
    int i = 0;
    int sum = 0;
    int size = 5;
    int* array = (int*)malloc(size * sizeof(int));
    for(i = 0; i < size; i++) {
        array[i] = i;
    }
    processArray(array, size);
    modifyArray(array);
    for(i = 0; i < size; i++) {
        sum += array[i];
    }
    free(array);
    printf("Sum: %d\n", sum);
    return 0;
}
1Sum: 40
2Sum: 48
3Sum: 50
4Sum: 52
정답 및 해설

배열은 최종적으로 0, 10, 6, 20, 12가 되어 합은 48이다.

초기화: 0, 1, 2, 3, 4
processArray (각 원소에 2i를 더함): 0, 3, 6, 9, 12
modifyArray (포인터 연산으로 array[1]=10, array[3]=20): 0, 10, 6, 20, 12
합: 0+10+6+20+12=480+10+6+20+12 = 48

modifyArray가 processArray 뒤에 호출되므로 array[1]과 array[3]은 덮어쓴 값 10, 20이 최종값이다.

문제 22
다음은 정점 간의 거리를 표시한 방향 그래프이다. 경로의 길이와 상관없이 이동 가능한 모든 정점 사이의 최단 경로 합은?

157
258
359
460
정답 및 해설

도달 가능한 모든 정점 쌍의 최단 경로 합은 57이다.

간선은 A→B 3, A→C 6, A→F 5, B→D 4, C→D 1, C→F 3, D→F 1, E→A 7, E→C 1이다. 출발 정점별로 최단 거리를 구해 더한다.

  • A에서: B 3, C 6, D 7(A→B→D 또는 A→C→D), F 5로 합 21이다.
  • B에서: D 4, F 5(B→D→F)로 합 9이다.
  • C에서: D 1, F 2(C→D→F가 직행 3보다 짧음)로 합 3이다.
  • D에서: F 1이고, F에서는 나가는 간선이 없어 0이다.
  • E에서: A 7, C 1, D 2(E→C→D), F 3(E→C→D→F), B 10(E→A→B)으로 합 23이다.

전체 합은 21+9+3+1+23=57이다.

문제 23
data가 이중 연결 리스트(doubly linked list)에 다음과 같이 구성되어 있을 때, 데이터 A를 삭제한 후 변경된 내용으로 옳은 것은?
memory addressdataleft_linkright_link
1000A10201030
1010B1030NULL
1020CNULL1000
1030D10001010
1B의 right_link → 1030, C의 left_link → 1020
2B의 right_link → 1030, D의 left_link → 1020
3C의 right_link → 1020, D의 left_link → 1030
4C의 right_link → 1030, D의 left_link → 1020
정답 및 해설

리스트 순서는 C → A → D → B이므로 A를 지우면 C의 right_link는 1030, D의 left_link는 1020으로 바뀐다.

C(1020)의 left_link가 NULL이라 C가 첫 노드이고, 링크를 따라가면 C(1020) ↔ A(1000) ↔ D(1030) ↔ B(1010)이다.
A 삭제: A의 앞 노드 C가 A의 다음 노드 D(1030)를, D가 A의 앞 노드 C(1020)를 가리키게 한다.

  • B의 right_link를 1030, C의 left_link를 1020으로 바꾸는 것: B는 A와 이웃하지 않으며 C가 자기 자신을 가리키게 된다.
  • B의 right_link를 1030, D의 left_link를 1020으로 바꾸는 것: D 쪽은 맞지만 B는 마지막 노드라 right_link가 NULL로 유지된다.
  • C의 right_link를 1020, D의 left_link를 1030으로 바꾸는 것: 두 노드가 각각 자기 자신을 가리키게 된다.
문제 24
다음 키값을 순서대로 삽입하여 B－트리를 구성할 때, 노드 오버플로(overflow)로 인한 노드 분할 횟수는? (단, 차수는 3이다)
1, 5, 7, 11, 13, 15, 17, 19
11
22
33
44
정답 및 해설

차수 3인 B-트리(노드당 키 최대 2개)에 차례로 넣으면 7, 13, 17 삽입 때 분할이 일어나고 17에서는 루트까지 연쇄 분할되어 총 4회이다.

7 삽입: [1, 5, 7] 오버플로 → 5를 올려 분할 (1회)
13 삽입: [7, 11, 13] 오버플로 → 11을 올려 루트 [5, 11] (2회)
17 삽입: [13, 15, 17] 오버플로 → 15를 올려 루트 [5, 11, 15]가 다시 오버플로 (3회) → 11을 올려 새 루트 생성 (4회)
19 삽입: [17, 19]로 들어가 분할 없음

  • 1회: 7 삽입 때의 첫 분할만 센 값이다.
  • 2회: 13 삽입까지의 분할만 센 값이다.
  • 3회: 17 삽입 때 루트로 번지는 연쇄 분할을 빠뜨린 값이다.
문제 25
다음 조건에서 데이터가 순서대로 해시 테이블에 입력된다고 할 때, 원래 계산된 버킷(bucket)에 저장되지 않는 데이터의 개수는? (단, 충돌(collision)로 인한 오버플로 발생 시, 선형 조사법(linear probing)으로 처리한다)
○ 버킷 크기: 13
○ 슬롯(slot) 크기: 2
○ 해시 함수: h(k) = k mod 13
21, 33, 8, 19, 76, 58, 27, 83, 30, 44, 7, 73, 2, 66, 85
11
22
33
44
정답 및 해설

버킷 7과 8이 가득 찬 뒤 들어온 73과 85만 다른 버킷으로 밀려나므로 2개이다.

해시값(k mod 13): 21→8, 33→7, 8→8, 19→6, 76→11, 58→6, 27→1, 83→5, 30→4, 44→5, 7→7, 73→8, 2→2, 66→1, 85→7
슬롯이 2개이므로 한 버킷에 2개까지 저장된다.

73: 버킷 8(21, 8)이 가득 차 선형 조사로 버킷 9에 저장
85: 버킷 7(33, 7)과 버킷 8이 가득 차 버킷 9에 저장
나머지는 같은 해시값이 2개 이하라 원래 버킷에 저장된다.

7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
25년 1회차
총 25문항 · 객관식 · 정답·해설 포함
문제 1
55개 간선(edge)을 갖는 무방향 완전 그래프의 정점(vertex) 개수는?
18
29
310
411
정답 및 해설

정점이 n개인 무방향 완전 그래프의 간선 수는 n(n−1)2\dfrac{n(n-1)}{2}이므로 간선이 55개이면 정점은 11개이다.

공식: n(n−1)2=55\dfrac{n(n-1)}{2} = 55
대입: n(n−1)=110=11×10n(n-1) = 110 = 11 \times 10
결과: n=11n = 11

  • 정점 8개: 간선은 8×72=28\dfrac{8 \times 7}{2} = 28개이다.
  • 정점 9개: 간선은 9×82=36\dfrac{9 \times 8}{2} = 36개이다.
  • 정점 10개: 간선은 10×92=45\dfrac{10 \times 9}{2} = 45개이다.
문제 2
초기 데이터에 대하여 오름차순 정렬을 2번 연산 수행한 후의 결과가 다음과 같을 때, 사용한 정렬 방법은?
○ 초기 데이터: 21, 3, 18, 33, 9, 15
○ 2번 연산 수행 결과: 3, 18, 21, 33, 9, 15
1삽입 정렬
2선택 정렬
3버블 정렬
4기수 정렬
정답 및 해설

두 차례 수행 뒤 앞쪽 3개(3, 18, 21)만 정렬되고 뒤쪽(33, 9, 15)은 그대로이므로 삽입 정렬이다.

삽입 정렬은 매 단계 다음 원소를 앞쪽 정렬 구간의 제자리에 끼워 넣는다.
1회: 3을 21 앞에 삽입 → 3, 21, 18, 33, 9, 15
2회: 18을 3과 21 사이에 삽입 → 3, 18, 21, 33, 9, 15

  • 선택 정렬: 최솟값을 차례로 앞에 두므로 2회 후 3, 9, 18, 33, 21, 15가 된다.
  • 버블 정렬: 큰 값이 뒤로 밀려나므로 2회 후 3, 18, 9, 15, 21, 33이 된다.
  • 기수 정렬: 일의 자리 분배 후 21, 3, 33, 15, 18, 9가 되고, 십의 자리까지 2회 수행하면 전체가 정렬된다.
문제 3
다음 C 코드로 표현한 알고리즘의 시간 복잡도는?
Algorithm(int n) {
    int i, j, k;
    int sum = 0;
    for(i = 0; i < 1000; i++)
        for(j = 1; j < (n - 500); j++)
            for(k = (n - 100); k < (n + 100); k++)
                sum = sum + i + j + k;
}
1O(1)O(1)
2O(n)O(n)
3O(n2)O(n^2)
4O(n3)O(n^3)
정답 및 해설

바깥 루프는 1000회, 가장 안쪽 루프는 200회로 고정되고 n에 비례하는 것은 가운데 루프뿐이므로 O(n)O(n)이다.

반복 횟수: i 루프 1000회 × j 루프 n−502n-502회(j = 1 ~ n-502) × k 루프 200회
총 연산: 1000×200×(n−502)1000 \times 200 \times (n-502)
상수 계수를 버리면 선형 시간이다.

  • O(1)O(1): j 루프 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • O(n2)O(n^2): k 루프는 n−100n-100부터 n+100n+100 직전까지로 폭이 200으로 고정되어 n에 비례하지 않는다.
  • O(n3)O(n^3): i 루프도 1000회 고정이라 n에 의존하는 루프는 하나뿐이다.
문제 4
이진 트리(binary tree) 중에서 전위 순회(preorder traversal)와 중위 순회(inorder traversal)한 결과가 동일한 것은?
1[그림]
2[그림]
3[그림]
4[그림]
정답 및 해설

전위 순회와 중위 순회 결과가 같은 것은 모든 노드가 오른쪽 자식만 갖는 오른쪽 사향 트리(1 → 2 → 3 → 4 → 5)이다.

전위는 루트 → 왼쪽 → 오른쪽, 중위는 왼쪽 → 루트 → 오른쪽 순서이므로, 왼쪽 서브트리가 하나도 없으면 두 순회 모두 루트 → 오른쪽 순서가 되어 결과가 같다. 이 트리는 두 순회 모두 1, 2, 3, 4, 5이다.

  • 5를 루트로 왼쪽 자식만 이어진 왼쪽 사향 트리: 전위는 5, 4, 3, 2, 1, 중위는 1, 2, 3, 4, 5로 정반대이다.
  • 2를 루트로 왼쪽에 1, 오른쪽에 3 → 4 → 5가 이어진 트리: 전위는 2, 1, 3, 4, 5, 중위는 1, 2, 3, 4, 5로 앞부분이 다르다.
  • 3을 루트로 왼쪽에 2 → 1, 오른쪽에 4 → 5가 있는 트리: 전위는 3, 2, 1, 4, 5, 중위는 1, 2, 3, 4, 5로 다르다.
문제 5
다음 그래프의 인접 행렬이 아래와 같을 때, (가)～(사)에 들어갈 값을 모두 더한 결과는?
abcde
a0(가)110
b(나)000(다)
c100(라)1
d10101
e0(마)1(바)(사)

14
25
36
47
정답 및 해설

(가)~(사)의 합은 6이다.

그래프의 간선은 a-b, a-c, a-d, b-e, c-d, c-e, d-e의 7개이며, 무방향 그래프의 인접 행렬은 대칭이고 자기 자신으로의 간선이 없으면 대각 원소가 0이다.

  • (가)·(나): a와 b가 연결되어 있으므로 둘 다 1이다.
  • (다)·(마): b와 e가 연결되어 있으므로 둘 다 1이다.
  • (라)·(바): c-d, d-e 간선이 있으므로 둘 다 1이다.
  • (사): e 자신으로의 간선이 없으므로 대각 원소는 0이다.

따라서 1이 6개, 0이 1개로 합은 6이다.

문제 6
다음 C 코드에서 power(2.0, 20, 0)를 호출할 때, 변수 c의 마지막 출력값은?
double power(double x, int n, int c)
{
    printf("c : %d\n", c);
    if(n == 0) return 1;
    else if(n % 2 == 0) {
        c++;
        return power(x * x, n / 2, c);
    }
    else {
        c++;
        return x * power(x * x, (n - 1) / 2, c);
    }
}
15
26
37
48
정답 및 해설

호출될 때마다 c를 먼저 출력하고 n이 0이 될 때까지 c를 1씩 늘려 재귀하므로 마지막 출력값은 5이다.

추적 (n, 출력되는 c): (20, 0) → (10, 1) → (5, 2) → (2, 3) → (1, 4) → (0, 5)
n이 0인 호출은 c를 출력한 뒤 c를 늘리지 않고 1을 반환하며 끝난다.

n은 짝수면 절반, 홀수면 (n−1)/2(n-1)/2로 줄어들어 재귀 단계 수는 n의 이진수 자릿수(20 = 10100, 다섯 자리)와 같다.

문제 7
다음 단정도(32비트) IEEE 754 표준 방식으로 표현된 2진수를 10진수 형식으로 옳게 변환한 것은?
0931
11000001101001000000000000000000
110.5
2－10.75
3－20.5
4－20.75
정답 및 해설

부호 비트 1, 지수 131, 가수 01001이므로 값은 -20.5이다.

부호 비트: 1 → 음수
지수 8비트: 10000011 = 131 → 바이어스 127을 빼면 131−127=4131 - 127 = 4
가수 23비트: 0100100…0 → 1.01001(2)1.01001_{(2)}

값: −1.01001(2)×24=−10100.1(2)-1.01001_{(2)} \times 2^{4} = -10100.1_{(2)}
결과: −(16+4+0.5)=−20.5-(16 + 4 + 0.5) = -20.5

  • 10.5: 부호 비트가 1이므로 양수가 될 수 없다.
  • -10.75: 1010.11(2)1010.11_{(2)}이 되어야 하므로 지수가 3이어야 하는데 실제 지수는 4이다.
  • -20.75: 10100.11(2)10100.11_{(2)}이 되어야 하므로 가수가 010011로 끝나야 하는데 실제 가수는 01001 뒤가 모두 0이다.
문제 8
다음 선형 리스트에서 연산 1과 연산 2가 수행된 후 리스트 상태와 두 연산에 사용된 원소의 총이동 횟수를 바르게 연결한 것은?
[0][1][2][3][4][5][6][7]
ABCDEFG
연산 1: 인덱스 1번에 원소 H 삽입
연산 2: 인덱스 3번 원소 삭제
리스트 상태　　총이동 횟수
1
[0][1][2][3][4][5][6][7]
AHCEFG
　　3
2
[0][1][2][3][4][5][6][7]
AHCEFG
　　3
3
[0][1][2][3][4][5][6][7]
AHBDEFG
　　10
4
[0][1][2][3][4][5][6][7]
AHBDEFG
　　10
정답 및 해설

삽입에서 6회, 삭제에서 4회 원소가 이동하므로 결과는 A, H, B, D, E, F, G이고 총이동 10회이다.

연산 1: 인덱스 1에 H를 넣으려면 B~G 6개를 한 칸씩 뒤로 옮긴다 → A, H, B, C, D, E, F, G (6회)
연산 2: 이제 인덱스 3의 원소는 C이므로 C를 지우고 D~G 4개를 한 칸씩 앞으로 당긴다 → A, H, B, D, E, F, G (4회)

  • A, H, C, 빈칸, E, F, G (3회): H가 B를 덮어써 B가 사라지고, 삭제 후 빈칸도 메우지 않은 상태다.
  • A, H, C, E, F, G (3회): 삽입 때 B를 뒤로 밀지 않고 덮어써 B가 사라진 상태다.
  • A, H, B, 빈칸, D, E, F, G (10회): 삭제 후 뒤 원소를 앞으로 당기지 않아 선형 리스트의 연속성이 깨진 상태다.
문제 9
다음은 힙 정렬(heap sort) 알고리즘을 구현한 C 코드이다. 리스트 L이 (61, 11, 59, 15, 48, 19)로 주어졌을 때, for 문에 관한 설명으로 옳은 것만을 모두 고르면? (단, 리스트 L을 배열로 표현할 때 색인 1부터 저장하고, n은 리스트의 크기를 나타낸다)
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

void heap_sort(int L[], int n){
    int i, temp;
    for(i = n/2; i >= 1; i--)  ······································ (가)
        adjust(L, i, n);
    for(i = n-1; i >= 1; i--) {  ·································· (나)
        SWAP(L[1], L[i+1], temp);
        adjust(L, 1, i);
    }
}

void adjust(int L[], int root, int n) {
    int next = 2 * root;
    int X = L[root];
    while(next <= n) {
        if(next < n && L[next] < L[next + 1])
            next++;
        if(X > L[next]) break;
        L[next / 2] = L[next];
        next *= 2;
    }
    L[next / 2] = X;
}
ㄱ. (가) for 문을 수행한 후 리스트 L에는 (61, 48, 59, 15, 19, 11)이 저장된다.
ㄴ. (나) for 문을 첫 1회 수행한 후 리스트 L에는 (59, 48, 19, 15, 11, 61)이 저장된다.
ㄷ. (나) for 문의 시간 복잡도는 O(nlog⁡n)O(n\log n)이다.
1ㄱ, ㄴ
2ㄱ, ㄷ
3ㄴ, ㄷ
4ㄱ, ㄴ, ㄷ
정답 및 해설

ㄱ은 틀리고 ㄴ과 ㄷ이 옳으므로 옳은 것은 ㄴ, ㄷ이다.

(가) 힙 구성: i=3에서 59와 자식 19 비교 → 그대로. i=2에서 11이 큰 자식 48(L[5])과 자리를 바꾼다. i=1에서 61이 두 자식보다 커서 그대로.
결과: (61, 48, 59, 15, 11, 19)

(나) 첫 회(i=5): L[1]과 L[6] 교환 → (19, 48, 59, 15, 11, 61)
adjust(L, 1, 5): 19가 큰 자식 59와 자리를 바꿈 → (59, 48, 19, 15, 11, 61)

  • ㄱ(틀림): 11은 큰 자식 48과 바뀌어 L[5]에 들어가므로 끝의 두 값은 11, 19 순서다.
  • ㄴ(옳음): 위 추적 결과와 같다.
  • ㄷ(옳음): (나) for 문은 약 n회 반복하고 매번 adjust가 힙 높이 O(log⁡n)O(\log n)만큼 내려가므로 O(nlog⁡n)O(n\log n)이다.
문제 10
다음 8개의 데이터를 순서대로 삽입하여 AVL 트리를 구성하였을 때, 이에 대한 설명으로 옳은 것은?
19, 7, 10, 15, 25, 32, 17, 5
1루트 노드의 번호는 17이다.
2중위 순회했을 때 네 번째 방문하는 노드의 번호는 15이다.
3전위 순회했을 때 세 번째 방문하는 노드의 번호는 10이다.
4후위 순회했을 때 다섯 번째 방문하는 노드의 번호는 32이다.
정답 및 해설

완성된 AVL 트리를 중위 순회하면 네 번째로 방문하는 노드는 15이다.

10 삽입: 19-7-10의 LR 불균형 → 10을 루트로 회전 (왼쪽 7, 오른쪽 19)
32 삽입: 루트 10의 오른쪽이 2 더 높은 RR 불균형 → 10 기준 좌회전으로 19가 루트가 된다.
17, 5 삽입 후에는 균형이 유지된다.

최종 트리: 루트 19, 왼쪽 10(자식 7, 15), 오른쪽 25(오른쪽 자식 32), 7의 왼쪽 5, 15의 오른쪽 17
중위: 5, 7, 10, 15, 17, 19, 25, 32

  • 루트 노드는 17이 아니라 19이다.
  • 전위 순회(19, 10, 7, 5, 15, 17, 25, 32)의 세 번째 노드는 7이다.
  • 후위 순회(5, 7, 17, 15, 10, 32, 25, 19)의 다섯 번째 노드는 10이다.
문제 11
다음 원형 큐에 대해 1부터 7까지 연산을 차례로 수행했을 때, 수행이 완료된 후 큐의 상태는? (단, 현재 상태는 front = 2, rear = 3이다)
[0][1][2][3][4][5]
A
연산 1: 원소 B 삽입
연산 2: 원소 한 개 삭제
연산 3: 원소 C 삽입
연산 4: 원소 D 삽입
연산 5: 원소 두 개 삭제
연산 6: 원소 E 삽입
연산 7: 원소 F 삽입
1
[0][1][2][3][4][5]
AEF
2
[0][1][2][3][4][5]
DFE
3
[0][1][2][3][4][5]
FEA
4
[0][1][2][3][4][5]
DEF
정답 및 해설

연산을 모두 마치면 큐에는 D, E, F가 인덱스 0, 1, 2에 남는다 (front = 5, rear = 2).

front는 첫 원소의 한 칸 앞, rear는 마지막 원소 위치이며 인덱스는 (i+1) mod 6(i+1) \bmod 6으로 순환한다.

B 삽입: rear 4 → 삭제: front 3 (A 제거) → C 삽입: rear 5 → D 삽입: rear 0
두 개 삭제: front 4 (B 제거), front 5 (C 제거) → E 삽입: rear 1 → F 삽입: rear 2

  • A, E, F가 남은 상태: A, B, C는 이미 삭제되었으므로 A가 남을 수 없다.
  • D, F, E가 [0], [4], [5]에 있는 상태: rear는 0 다음 1, 2로 진행하므로 E, F는 [1], [2]에 들어간다.
  • F, E, A가 남은 상태: 인덱스가 거꾸로 진행된 것이며 삭제된 A도 남아 있다.
문제 12
비어 있는 초기 상태의 이진 트리에 다섯 개의 키(1, 2, 3, 4, 5)를 순서대로 하나씩 삽입하면서 레드－블랙 트리를 만든 후, 중위 순회한 결과는?
11, 2, 3, 4, 5
21, 3, 5, 4, 2
32, 1, 3, 5, 4
42, 1, 4, 3, 5
정답 및 해설

레드-블랙 트리는 회전과 재색칠 후에도 이진 탐색 트리 성질을 유지하므로 중위 순회 결과는 항상 오름차순인 1, 2, 3, 4, 5이다.

1(루트, 흑) → 2(적) → 3 삽입 시 적색 연속으로 좌회전해 2가 루트 → 4 삽입 시 삼촌 1이 적색이라 재색칠 → 5 삽입 시 3 기준 좌회전으로 4가 3과 5의 부모가 된다.
최종 형태: 루트 2, 왼쪽 1, 오른쪽 4(자식 3, 5)

  • 1, 3, 5, 4, 2: 최종 트리의 후위 순회 결과다.
  • 2, 1, 3, 5, 4: 오름차순이 아니므로 이진 탐색 트리의 중위 순회가 될 수 없다.
  • 2, 1, 4, 3, 5: 최종 트리의 전위 순회 결과다.
문제 13
다음 이진 트리에 대해 전위, 중위, 후위 순회(postorder traversal)를 수행할 때, 각 순회 5번째 노드를 바르게 연결한 것은?

전위　　중위　　후위
1E　　H　　E
2G　　E　　H
3H　　E　　E
4H　　B　　I
정답 및 해설

다섯째 노드는 전위 H, 중위 E, 후위 E이다.

트리는 A의 왼쪽 자식 B, 오른쪽 자식 C이고, B 아래 D(자식 G, H)와 E(오른쪽 자식 I), C의 오른쪽 자식 F(자식 J, K)로 이루어진다.

전위: A, B, D, G, H, E, I, C, F, J, K
중위: G, D, H, B, E, I, A, C, J, F, K
후위: G, H, D, I, E, B, J, K, F, C, A

  • E, H, E 조합: 전위의 다섯째는 E가 아니라 H이고, 중위의 다섯째도 H가 아니라 E이다.
  • G, E, H 조합: G는 전위 넷째, H는 후위 둘째이다.
  • H, B, I 조합: B는 중위 넷째, I는 후위 넷째이다.
문제 14
다음 C 코드를 사용하여 배열을 선언하였고 arr[0][0][0]의 주소를 α라고 할 때, arr[3][4][2]의 행 우선 순서 주소는?
char arr[6][5][4];
1α ＋ 34
2α ＋ 78
3α ＋ 96
4α ＋ 112
정답 및 해설

행 우선 순서에서 arr[3][4][2]는 시작 주소로부터 78바이트 떨어져 있으므로 주소는 α + 78이다.

공식: 오프셋 = (i×5×4+j×4+k)×1(i \times 5 \times 4 + j \times 4 + k) \times 1 (char는 1바이트)
대입: 3×20+4×4+23 \times 20 + 4 \times 4 + 2
결과: 60+16+2=7860 + 16 + 2 = 78

  • α + 34: arr[1][3][2]의 위치이다.
  • α + 96: arr[4][4][0]의 위치이다.
  • α + 112: arr[5][3][0]의 위치이다.
문제 15
다음은 정렬된 정수 배열에 대한 이진 탐색(binary search)을 구현한 C 코드이다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?
int BSearch(int data[], int size, int target) {
    int mid, left = 0, right = size - 1;
    while(left <= right) {
        mid = [ (가) ];
        if(target == data[mid]) return mid;
        else if(target > data[mid]) left = [ (나) ];
        else right = [ (다) ];
    }
    return -1;
}
(가)　　(나)　　(다)
1(left+right) // 2　　mid-1　　mid+1
2right-(left-right) // 2　　mid　　left
3(left+right) / 2　　mid+1　　mid-1
4left+(right-left) / 2　　right　　mid
정답 및 해설

중간 인덱스는 (left+right) / 2이고, 찾는 값이 크면 left = mid+1, 작으면 right = mid-1로 범위를 줄인다.

C에서 정수끼리의 /는 몫만 남기는 정수 나눗셈이다. 이미 비교한 mid는 다음 범위에서 제외해야 범위가 매번 줄어 반복이 끝난다.

  • (left+right) // 2, mid-1, mid+1: C에서 //는 주석 기호이고, 찾는 값이 클 때 left를 mid-1로 두면 탐색 방향이 반대가 된다.
  • right-(left-right) // 2, mid, left: 중간값 식이 틀렸고, left = mid로 두면 범위가 줄지 않아 무한 반복될 수 있다.
  • left+(right-left) / 2, right, mid: 중간값 식은 맞지만 left = right, right = mid로는 범위를 올바르게 좁히지 못한다.
문제 16
다음 파이썬 프로그램의 실행 결과는?
class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next
class SinglyLinkedList:
    def __init__(self):
        self.head = None
    def func1(self, data):
        node = self.head
        self.head = Node(data, node)
    def func2(self, data):
        if self.head is None: self.func1(data)
        else :
            node = self.head
            while node.next is not None: node = node.next
            node.next = Node(data, None)
    def func3(self, pos):
        if pos < 0: return None
        node = self.head
        while pos > 0 and node != None:
            node = node.next
            pos -= 1
        return node
    def showList(self):
        node = self.head
        while node :
            print(node.data, end=' ')
            node = node.next

myList = SinglyLinkedList()
myList.func1(1); myList.func2(2)
myList.func1(3); myList.func2(4)
myList.func2(myList.func3(0).data)
myList.showList()
11 2 3 4
22 3 4 1
33 1 2 4 3
43 3 1 2 4
정답 및 해설

최종 리스트를 출력하면 3 1 2 4 3이다.

func1은 맨 앞 삽입, func2는 맨 뒤 삽입, func3(pos)은 head에서 pos칸 이동한 노드를 반환한다.

func1(1) → 1
func2(2) → 1 2
func1(3) → 3 1 2
func2(4) → 3 1 2 4
func3(0)은 head 노드(데이터 3)이므로 func2(3) → 3 1 2 4 3

  • 1 2 3 4: 원소가 4개뿐이어서 마지막 func2 호출로 추가된 노드가 빠졌다.
  • 2 3 4 1: 원소가 4개뿐이고 삽입 순서와도 맞지 않는다.
  • 3 3 1 2 4: 마지막 3을 맨 앞에 붙인 결과지만 func2는 맨 뒤에 붙인다.
문제 17
다음 C 프로그램의 실행 결과는?
#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int value;
    struct ListNode* next;
} ListNode;

int func(ListNode* p, int n) {
    int i, sum = 0;
    for(i = 0; i < n; i++) {
        sum += p->value;
        p = p->next;
    }
    return sum;
}

int main() {
    int i, s, SIZE = 5;
    ListNode* p[SIZE];
    for(i = 0; i < SIZE; i++) {
        p[i] = (ListNode*)malloc(sizeof(ListNode));
        p[i]->value = i;
    }
    for(i = 0; i < SIZE-1; i++)
        p[i]->next = p[i+1];
    p[SIZE-1]->next = p[0];
    s = func(p[4], 7);
    printf("%d", s);

    return 0;
}
114
215
316
417
정답 및 해설

원형 연결 리스트에서 값 4인 노드부터 7개 노드의 값을 더하면 14이다.

p[i]의 value는 i이고 p[4]의 next가 p[0]이라 원형으로 이어진다.
방문 값: 4, 0, 1, 2, 3, 4, 0
합: 4+0+1+2+3+4+0=144+0+1+2+3+4+0 = 14

문제 18
인접 행렬로 표현된 방향 그래프 중 위상 정렬이 불가능한 것은?
1[0100001000010000]\begin{bmatrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
2[0011001100010000]\begin{bmatrix}0 & 0 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
3[0111001100010000]\begin{bmatrix}0 & 1 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
4[0101001010010000]\begin{bmatrix}0 & 1 & 0 & 1\\0 & 0 & 1 & 0\\1 & 0 & 0 & 1\\0 & 0 & 0 & 0\end{bmatrix}
정답 및 해설

3행 1열이 1인 행렬은 1→2→3→1의 사이클을 포함하므로 위상 정렬이 불가능하다.

위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 행 i, 열 j의 1을 간선 i→j로 읽을 때 대각선 아래가 모두 0인 상삼각 행렬은 번호가 큰 정점에서 작은 정점으로 가는 간선이 없어 사이클이 생기지 않는다.

  • 1→2→3→4의 한 줄 경로 행렬: 상삼각이므로 1, 2, 3, 4 순으로 정렬된다.
  • 1과 2가 각각 3, 4로, 3이 4로 가는 행렬: 상삼각이므로 위상 정렬이 가능하다.
  • 번호가 작은 정점에서 큰 정점으로 모든 간선이 있는 행렬: 상삼각이므로 위상 정렬이 가능하다.
문제 19
다음 C 프로그램의 실행 결과는?
#include <stdio.h>
int func(int key, int low, int high, int* list) {
    list[high+1] = key;
    int i = 0;
    for(i = low; list[i] != key; i++);
    if(i == (high+1)) return -1;
    return i;
}

int main(int argc, char* argv[]) {
    int list[100] = {1, 2, 3, 4, 5, 6, 7};
    printf("%d\n", func(3, 4, 6, list));

    return 0;
}
1－1
20
33
44
정답 및 해설

찾는 키 3이 탐색 범위(인덱스 4~6)에 없으므로 보초 위치에서 멈추고 -1을 반환한다.

list[high+1] = list[7]에 key 3을 보초(sentinel)로 넣는다.
i=4부터: list[4]=5, list[5]=6, list[6]=7, list[7]=3 → i=7에서 멈춤
i == high+1이므로 -1 반환

  • 0: 탐색은 인덱스 4부터 시작하므로 0이 반환될 수 없다.
  • 3: 함수는 키 값이 아니라 찾은 인덱스를 반환한다.
  • 4: 시작 인덱스 low이며 list[4]는 5라 키와 다르다.
문제 20
다음 수식을 후위 표기법(postfix notation)으로 변환한 후, 스택을 이용하여 계산하려고 한다. 계산 과정에서 스택에 일곱 번째로 삽입(push)하는 값은?
(A － B) * C － (D ＋ E) / F
1C
2D
3E
4(D ＋ E)
정답 및 해설

후위식은 A B - C * D E + F / - 이고, 계산 중 일곱 번째로 push되는 값은 E이다.

피연산자는 push하고, 연산자는 두 값을 pop해 계산한 결과를 다시 push한다.
push 순서: A → B → A-B → C → (A-B)*C → D → E → D+E → F → (D+E)/F → 최종값

  • C: 네 번째로 push된다.
  • D: 여섯 번째로 push된다.
  • (D + E): 여덟 번째로 push된다.
문제 21
다음 C 프로그램의 출력 결과는?
#include <stdio.h>
#include <stdlib.h>
void processArray(int* array, int size) {
    int i = 0;
    for(i = 0; i < size; i++) {
        array[i] += i * 2;
    }
}
void modifyArray(int* array) {
    *(array + 1) = 10;
    *(array + 3) = 20;
}
int main() {
    int i = 0;
    int sum = 0;
    int size = 5;
    int* array = (int*)malloc(size * sizeof(int));
    for(i = 0; i < size; i++) {
        array[i] = i;
    }
    processArray(array, size);
    modifyArray(array);
    for(i = 0; i < size; i++) {
        sum += array[i];
    }
    free(array);
    printf("Sum: %d\n", sum);
    return 0;
}
1Sum: 40
2Sum: 48
3Sum: 50
4Sum: 52
정답 및 해설

배열은 최종적으로 0, 10, 6, 20, 12가 되어 합은 48이다.

초기화: 0, 1, 2, 3, 4
processArray (각 원소에 2i를 더함): 0, 3, 6, 9, 12
modifyArray (포인터 연산으로 array[1]=10, array[3]=20): 0, 10, 6, 20, 12
합: 0+10+6+20+12=480+10+6+20+12 = 48

modifyArray가 processArray 뒤에 호출되므로 array[1]과 array[3]은 덮어쓴 값 10, 20이 최종값이다.

문제 22
다음은 정점 간의 거리를 표시한 방향 그래프이다. 경로의 길이와 상관없이 이동 가능한 모든 정점 사이의 최단 경로 합은?

157
258
359
460
정답 및 해설

도달 가능한 모든 정점 쌍의 최단 경로 합은 57이다.

간선은 A→B 3, A→C 6, A→F 5, B→D 4, C→D 1, C→F 3, D→F 1, E→A 7, E→C 1이다. 출발 정점별로 최단 거리를 구해 더한다.

  • A에서: B 3, C 6, D 7(A→B→D 또는 A→C→D), F 5로 합 21이다.
  • B에서: D 4, F 5(B→D→F)로 합 9이다.
  • C에서: D 1, F 2(C→D→F가 직행 3보다 짧음)로 합 3이다.
  • D에서: F 1이고, F에서는 나가는 간선이 없어 0이다.
  • E에서: A 7, C 1, D 2(E→C→D), F 3(E→C→D→F), B 10(E→A→B)으로 합 23이다.

전체 합은 21+9+3+1+23=57이다.

문제 23
data가 이중 연결 리스트(doubly linked list)에 다음과 같이 구성되어 있을 때, 데이터 A를 삭제한 후 변경된 내용으로 옳은 것은?
memory addressdataleft_linkright_link
1000A10201030
1010B1030NULL
1020CNULL1000
1030D10001010
1B의 right_link → 1030, C의 left_link → 1020
2B의 right_link → 1030, D의 left_link → 1020
3C의 right_link → 1020, D의 left_link → 1030
4C의 right_link → 1030, D의 left_link → 1020
정답 및 해설

리스트 순서는 C → A → D → B이므로 A를 지우면 C의 right_link는 1030, D의 left_link는 1020으로 바뀐다.

C(1020)의 left_link가 NULL이라 C가 첫 노드이고, 링크를 따라가면 C(1020) ↔ A(1000) ↔ D(1030) ↔ B(1010)이다.
A 삭제: A의 앞 노드 C가 A의 다음 노드 D(1030)를, D가 A의 앞 노드 C(1020)를 가리키게 한다.

  • B의 right_link를 1030, C의 left_link를 1020으로 바꾸는 것: B는 A와 이웃하지 않으며 C가 자기 자신을 가리키게 된다.
  • B의 right_link를 1030, D의 left_link를 1020으로 바꾸는 것: D 쪽은 맞지만 B는 마지막 노드라 right_link가 NULL로 유지된다.
  • C의 right_link를 1020, D의 left_link를 1030으로 바꾸는 것: 두 노드가 각각 자기 자신을 가리키게 된다.
문제 24
다음 키값을 순서대로 삽입하여 B－트리를 구성할 때, 노드 오버플로(overflow)로 인한 노드 분할 횟수는? (단, 차수는 3이다)
1, 5, 7, 11, 13, 15, 17, 19
11
22
33
44
정답 및 해설

차수 3인 B-트리(노드당 키 최대 2개)에 차례로 넣으면 7, 13, 17 삽입 때 분할이 일어나고 17에서는 루트까지 연쇄 분할되어 총 4회이다.

7 삽입: [1, 5, 7] 오버플로 → 5를 올려 분할 (1회)
13 삽입: [7, 11, 13] 오버플로 → 11을 올려 루트 [5, 11] (2회)
17 삽입: [13, 15, 17] 오버플로 → 15를 올려 루트 [5, 11, 15]가 다시 오버플로 (3회) → 11을 올려 새 루트 생성 (4회)
19 삽입: [17, 19]로 들어가 분할 없음

  • 1회: 7 삽입 때의 첫 분할만 센 값이다.
  • 2회: 13 삽입까지의 분할만 센 값이다.
  • 3회: 17 삽입 때 루트로 번지는 연쇄 분할을 빠뜨린 값이다.
문제 25
다음 조건에서 데이터가 순서대로 해시 테이블에 입력된다고 할 때, 원래 계산된 버킷(bucket)에 저장되지 않는 데이터의 개수는? (단, 충돌(collision)로 인한 오버플로 발생 시, 선형 조사법(linear probing)으로 처리한다)
○ 버킷 크기: 13
○ 슬롯(slot) 크기: 2
○ 해시 함수: h(k) = k mod 13
21, 33, 8, 19, 76, 58, 27, 83, 30, 44, 7, 73, 2, 66, 85
11
22
33
44
정답 및 해설

버킷 7과 8이 가득 찬 뒤 들어온 73과 85만 다른 버킷으로 밀려나므로 2개이다.

해시값(k mod 13): 21→8, 33→7, 8→8, 19→6, 76→11, 58→6, 27→1, 83→5, 30→4, 44→5, 7→7, 73→8, 2→2, 66→1, 85→7
슬롯이 2개이므로 한 버킷에 2개까지 저장된다.

73: 버킷 8(21, 8)이 가득 차 선형 조사로 버킷 9에 저장
85: 버킷 7(33, 7)과 버킷 8이 가득 차 버킷 9에 저장
나머지는 같은 해시값이 2개 이하라 원래 버킷에 저장된다.