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

22년 1회차

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

1 / 1

A4정답 포함← → 키 · 드래그로 넘김

7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

22년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

세 개의 노드를 가진 무방향 완전 그래프의 신장 트리(spanning tree)는 최대 몇 가지인가?

정답 및 해설

세 정점 무방향 완전 그래프의 신장 트리는 3가지이다.

신장 트리는 정점 3개를 간선 2개로 잇으므로, 간선 3개 중 하나를 빼는 경우의 수만큼 생긴다. 케일리 공식으로도 $n^{n-2}=3^{1}=3$ 이다.

1가지: 어느 간선을 빼도 서로 다른 트리가 되므로 하나뿐일 수 없다.
2가지: 뺄 수 있는 간선 후보가 3개이므로 부족하다.
4가지: 간선 3개 중 2개를 고르는 경우는 $\binom{3}{2}=3$ 을 넘을 수 없다.

문제 2

다음 트리를 중위 순회한 결과로 옳은 것은?

12, 4, 5, 1, 3, 6, 7

22, 4, 5, 3, 6, 7, 1

34, 2, 5, 1, 6, 3, 7

44, 5, 2, 1, 6, 7, 3

정답 및 해설

중위 순회 결과는 4, 2, 5, 1, 6, 3, 7이다.

중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순으로 방문한다. 루트 1의 왼쪽 서브트리(2를 루트로 4, 5가 자식)는 4, 2, 5, 오른쪽 서브트리(3을 루트로 6, 7이 자식)는 6, 3, 7 순이 되어 둘 사이에 루트 1이 들어간다.

2, 4, 5, 1, 3, 6, 7은 각 서브트리에서 루트를 먼저 방문하고 전체 루트를 가운데 둔 순서로, 중위 순회가 아니다.
2, 4, 5, 3, 6, 7, 1은 루트를 맨 마지막에 방문한 형태로 중위 순회 규칙과 맞지 않는다.
4, 5, 2, 1, 6, 7, 3은 각 서브트리를 후위 순회한 순서로, 서브트리 루트를 자식 사이가 아닌 뒤에 방문했다.

문제 3

다음은 입력 개수

n

에 대한 알고리즘 A～D의 수행시간 복잡도를 나타낸 것이다. 알고리즘 A～D를 수행시간 효율이 좋은 것부터 순서대로 나열한 것은?

알고리즘	수행시간 복잡도
A	$O(n\log n)$
B	$O(2^n)$
C	$O(n^2)$
D	$O(n!)$

1A, C, B, D

2A, C, D, B

3C, A, B, D

4C, A, D, B

정답 및 해설

수행시간 효율이 좋은 순서는 A, C, B, D이다.

증가 속도는 $n\log n \lt n^2 \lt 2^n \lt n!$ 이다. 다항식은 지수보다 느리게, 지수는 팩토리얼보다 느리게 증가한다.

A, C, D, B: $n!$ 이 $2^n$ 보다 빠르게 커지므로 D가 B보다 뒤에 와야 한다.
C, A, B, D: $n^2$ 이 $n\log n$ 보다 크므로 C가 A보다 앞설 수 없다.
C, A, D, B: C·A 순서와 B·D 순서가 모두 뒤바뀌었다.

문제 4

이진 트리에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 공백 이진 트리의 높이를 0으로 본다면, 높이가 5인 이진 트리의 최대 노드 수는 15이다.
ㄴ. 9개의 노드를 가지고 있는 이진 트리는 8개의 간선을 가진다.
ㄷ. 루트 노드의 인덱스를 1로 하는 1차원 배열로 완전 이진 트리를 표현할 때, 인덱스 13인 노드의 부모 노드는 인덱스가 7이다.
ㄹ. 7개 노드로 구성할 수 있는 이진 트리의 최대 높이와 최소 높이의 차는 4이다.

1ㄱ, ㄴ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄷ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

ㄴ: 트리는 노드가 n개이면 간선이 n−1개이므로 9개 노드는 간선 8개다.
ㄹ: 7개 노드의 최대 높이는 한 줄로 늘어선 경우 7, 최소 높이는 완전 이진 트리인 경우 3이므로 차는 4이다.

ㄱ: 높이 5인 이진 트리의 최대 노드 수는 $2^5-1=31$ 이므로 15가 아니다.
ㄷ: 인덱스 i의 부모는 $\lfloor i/2 \rfloor$ 이므로 13의 부모는 6이다.

문제 5

크기가 4인 빈 스택에 다음 연산을 차례로 수행한 후의 스택 상태를 바르게 표현한 것은?

push(3) → push(7) → pop() → push(5) → push(8) →
peek() → push(10) → pop()

정답 및 해설

최종 스택은 아래부터 3, 5, 8이 쌓인 상태이다.

push(3)·push(7) 후 pop()으로 7이 빠져 [3], push(5)·push(8)로 [3, 5, 8]이 된다. peek()은 top을 읽기만 하고 제거하지 않으며, push(10) 후 pop()으로 10이 빠져 [3, 5, 8]이 남는다.

3, 5만 남은 상태: peek()을 삭제 연산으로 오해한 결과다.
5, 8, 10이 남은 상태: 바닥의 3은 꺼낸 적이 없고 10은 마지막 pop()으로 제거된다.
10, 8, 5, 3이 가득 찬 상태: 마지막 pop()을 반영하지 않았다.

문제 6

그림은 정점 A～H 간의 거리를 나타낸 그래프이다. 다익스트라(Dijkstra) 알고리즘을 이용하여 정점 A로부터 다른 모든 정점까지의 최단 경로를 구하고, 각 최단 경로의 거리를 짧은 것부터 순서대로 나열한 것은?

13, 11, 13, 15, 16, 20, 21

23, 11, 13, 15, 16, 21, 22

33, 11, 13, 16, 18, 20, 21

43, 11, 13, 16, 18, 21, 22

정답 및 해설

A로부터의 최단 거리를 오름차순으로 나열하면 3, 11, 13, 15, 16, 20, 21이다.

다익스트라 알고리즘으로 확정 순서를 따라가면 B(3), E(11), C(13)가 먼저 확정된다. 이어 F는 C를 거쳐 13+2=15, H는 E를 거쳐 11+5=16으로 확정된다.

D는 C를 거치면 22이지만 H를 거치면 16+4=20으로 더 짧고, G는 D를 거쳐 20+1=21로 확정된다.

3, 11, 13, 15, 16, 21, 22는 마지막 두 거리가 실제 최단 거리인 D의 20(H 경유), G의 21(D 경유)보다 커서 최단 경로 갱신을 놓친 나열이다.
3, 11, 13, 16, 18, 20, 21은 F를 B 경유 거리(18)로 잡아 C를 거치는 15를 반영하지 못했다.
3, 11, 13, 16, 18, 21, 22는 F와 D·G 모두에서 최단 경로 갱신을 놓친 결과다.

문제 7

다음 데이터를 차례대로 하나씩 입력받아 AVL 트리를 생성할 때, 필요한 회전을 적용 순서대로 바르게 나열한 것은?

6, 7, 8, 2, 1, 5, 4

1LL회전, LR회전, LR회전

2LL회전, LR회전, RL회전

3RR회전, LL회전, LR회전

4RR회전, LL회전, RL회전

정답 및 해설

회전은 RR회전, LL회전, LR회전 순서로 일어난다.

6, 7, 8 삽입 시 6에서 오른쪽-오른쪽으로 치우쳐 RR회전 → 루트 7, 자식 6·8.
2, 1 삽입 시 6에서 왼쪽-왼쪽으로 치우쳐 LL회전 → 7의 왼쪽이 2(자식 1·6).

5는 6의 왼쪽에 붙어 루트 7의 왼쪽 높이 3, 오른쪽 높이 1이 되고 경로가 왼쪽-오른쪽이므로 LR회전 → 루트 6, 왼쪽 2(자식 1·5), 오른쪽 7(오른쪽 자식 8). 마지막 4는 5의 왼쪽에 붙지만 모든 노드의 균형 인수가 ±1 이내라 회전이 없다.

LL회전, LR회전, LR회전: 처음 6, 7, 8은 오른쪽으로 치우치므로 첫 회전은 RR이다.
LL회전, LR회전, RL회전: 첫 회전이 RR이어야 하고 4 삽입 때는 회전이 없다.
RR회전, LL회전, RL회전: 5의 삽입 경로는 왼쪽 후 오른쪽이므로 RL이 아니라 LR이다.

문제 8

다음 C 코드는 원형 연결 리스트에 속한 모든 노드의 값들을 더하여 출력한다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

#include <stdio.h>
#include <malloc.h>
typedef struct Node {
    struct Node *a;
    int b;
} Node;

int listSum(Node *p) {
    int sum = 0;
    Node *s = p;
    do {
        sum += [ (가) ];
        p = [ (나) ];
    } while ( [ (다) ] );
    return sum;
}

int main() {
    int MAX = 5;
    int i, s;
    Node *p[MAX];

    for( i = 0; i < MAX; i++) {
        p[i] = (Node*)malloc(sizeof(Node));
        p[i]->b = i+1;
    }
    for( i = 0; i < MAX-1; i++)
        p[i]->a = p[i+1];
    p[MAX-1]->a = p[0];
    s = listSum(p[0]);
    printf("Sum = %d", s);
}

(가)　　(나)　　(다)

1p.b　　p.a　　p != NULL

2p->a　　p->b　　p != s

3p->b　　p->a　　p != NULL

4(*p).b　　(*p).a　　p != s

정답 및 해설

(가) p->b, (나) p->a, (다) p != s이며, 이를 (*p).b, (*p).a 로 표기한 조합이 맞다.

b는 값, a는 다음 노드 포인터이고 포인터의 멤버 접근 p->b는 (*p).b와 같다. 원형 리스트는 끝이 NULL이 아니라 처음 노드로 돌아오므로, 출발 노드 s로 되돌아올 때 멈춰야 한다.

p.b, p.a, p != NULL: p는 포인터라 점 연산자로 멤버에 접근할 수 없고, NULL을 만나지 않아 끝나지 않는다.
p->a, p->b, p != s: 값 멤버와 링크 멤버가 뒤바뀌었다.
p->b, p->a, p != NULL: 원형 리스트에는 NULL이 없어 무한 반복한다.

문제 9

다음 C 코드를 수행하면 4개의 값이 출력된다. 출력 값 중 나머지 3개와 다른 값을 출력하는 C 코드의 라인 번호는?

라인 번호	C 코드
1	#include <stdio.h>
2
3	int main() {
4	int array[] = {0,1,2};
5	int *p = array+2;
6
7	printf("%d\n", *(p-1));
8	printf("%d\n", *p-1);
9	printf("%d\n", *(p--));
10	printf("%d\n", *p);
11	}

410

정답 및 해설

나머지와 다른 값을 출력하는 것은 *(p--)를 출력하는 줄이다.

p는 array+2로 값 2를 가리킨다. *(p-1)은 array[1]인 1, *p-1은 2−1인 1이다. *(p--)는 후위 감소라 현재 위치의 2를 출력한 뒤 p가 array+1로 옮겨지고, 이어지는 *p는 1이다.

*(p-1): 한 칸 앞 원소의 값 1을 출력한다.
*p-1: 역참조가 먼저라 2에서 1을 뺀 1을 출력한다.
마지막 *p: 앞 줄의 감소가 반영되어 1을 출력한다.

문제 10

다음 tree_height() 함수는 이진 트리의 루트 노드를 매개변수로 받아 트리의 높이를 반환한다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

int tree_height (node *ptr) {
    int left_h, right_h;
    if (ptr == NULL)
        return 0;
    else {
        left_h = tree_height(ptr->left);
        right_h = tree_height(ptr->right);
        if ( [ (가) ] )
            return [ (나) ] ;
        else
            return [ (다) ] ;
    }
}

(가)　　(나)　　(다)

1left_h > right_h　　left_h　　right_h

2left_h > right_h　　left_h + 1　　right_h + 1

3left_h < right_h　　left_h　　right_h

4left_h < right_h　　left_h + 1　　right_h + 1

정답 및 해설

(가) left_h > right_h, (나) left_h + 1, (다) right_h + 1이다.

트리 높이는 두 서브트리 높이 중 큰 값에 현재 노드 1을 더한 것이다. 왼쪽이 더 크면 left_h + 1, 아니면 right_h + 1을 반환한다.

left_h > right_h, left_h, right_h: 현재 노드를 더하지 않아 어떤 트리든 높이가 0이 된다.
left_h < right_h, left_h, right_h: 작은 쪽을 고르고 1도 더하지 않는다.
left_h < right_h, left_h + 1, right_h + 1: 조건이 뒤집혀 더 낮은 서브트리 기준으로 높이를 반환한다.

문제 11

10개의 정점을 가진 무방향 그래프가 가질 수 있는 간선의 최대 개수는? (단, 각 정점에서 자기 자신으로의 간선은 허용하지 않고, 두 정점 사이의 간선은 최대 1개이다)

142

243

344

445

정답 및 해설

간선의 최대 개수는 45개이다.

자기 간선과 중복 간선이 없으면 서로 다른 두 정점 쌍마다 간선이 최대 하나다. 완전 그래프의 간선 수는 $\dfrac{n(n-1)}{2}=\dfrac{10\times 9}{2}=45$ 이다.

42: 정점 쌍 수보다 3개 적어 최대가 아니다.
43: 정점 쌍 수보다 2개 적어 최대가 아니다.
44: 연결되지 않은 정점 쌍이 하나 남아 최대가 아니다.

문제 12

회문(palindrome)은 영어 단어 radar와 같이 순서를 거꾸로 뒤집어도 원본과 동일한 단어를 의미한다. 다음 C 코드의 isPalindrome() 함수는 입력 문자열이 회문인 경우 1을 반환하고, 그렇지 않을 경우는 0을 반환한다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?

#include <stdio.h>
char stack[100];
int top = -1;

void push(char ch) {stack[++top] = ch;}

char pop() {return stack[top--];}

int isEmpty() {return top == -1;}

int isPalindrome(char *str) {
    int i;
    for ( i = 0; str[i]; i++ )
        [ (가) ] ;

    for ( i = 0; !isEmpty(); i++ )
        if ( [ (나) ] )
            return 0;
    return 1;
}

int main() {
    char input[100];
    scanf("%s", input);
    printf("%s",
        isPalindrome(input) ? "True" : "False");
}

(가)　　(나)

1push(str[i])　　str[i] == pop()

2push(str[i])　　str[i] != pop()

3push(str[top-i])　　str[i] == pop()

4push(str[top-i])　　str[i] != pop()

정답 및 해설

(가) push(str[i]), (나) str[i] != pop()이다.

첫 반복에서 문자를 모두 스택에 넣으면 pop() 순서는 문자열의 역순이 된다. 두 번째 반복은 앞에서부터 읽은 문자와 역순 문자를 비교해, 하나라도 다르면 0을, 끝까지 같으면 1을 반환한다.

push(str[i]), str[i] == pop(): 같은 문자일 때 0을 반환해 회문을 거짓으로 판정한다.
push(str[top-i]), str[i] == pop(): top이 -1부터 시작해 엉뚱한 위치를 넣고, 비교 조건도 반대다.
push(str[top-i]), str[i] != pop(): 문자를 차례대로 넣지 못해 역순 비교가 성립하지 않는다.

문제 13

다음 C 코드는 이진 탐색을 이용하여 정수 데이터를 탐색하는 함수이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, key는 찾고자 하는 값, a[]는 오름차순으로 정렬된 정수 배열, n은 배열의 크기이다)

int search(int key, int a[], int n) {
    int mid;
    int left = 0;
    int right = n-1;
    while ([ (가) ]) {
        mid = (right + left) / 2;
        if (key == a[mid]) return mid;
        if ([ (나) ]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

(가)　　(나)

1left < right　　key < a[mid]

2left < right　　key > a[mid]

3left <= right　　key < a[mid]

4left <= right　　key > a[mid]

정답 및 해설

(가) left <= right, (나) key < a[mid]이다.

원소 하나만 남은 left == right 구간도 검사해야 하므로 등호가 필요하다. key가 a[mid]보다 작으면 왼쪽 절반에 있으므로 right = mid - 1로 구간을 줄인다.

left < right, key < a[mid]: 원소 하나가 남은 구간을 검사하지 않아 찾지 못하는 경우가 생긴다.
left < right, key > a[mid]: 등호 누락에 더해 구간을 반대 방향으로 줄인다.
left <= right, key > a[mid]: key가 클 때 오른쪽 끝을 줄여 탐색 방향이 뒤집힌다.

문제 14

다음 C 코드는 반복구조를 이용하여 n번째 피보나치 수를 구하는 함수이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, n은 0 이상의 정수이다)

int fibonacci(int n){
    int x = 0, y = 1, z = 0;
    if (n < 2) return n;
    while ([ (가) ]) {
        [ (나) ] ;
        x = y;
        y = z;
    }
    return z;
}

(가)　　(나)

1n-- > 1　　z = x + y

2n-- > 1　　z = x - y

3n-- >= 1　　z = x + y

4n-- <= 1　　z = x - y

정답 및 해설

(가) n-- > 1, (나) z = x + y이다.

피보나치 수는 앞 두 수의 합이므로 z = x + y 후 x, y를 한 칸씩 민다. n이 2 이상이면 반복은 n−1회 돌아야 하며, n-- > 1은 n=2에서 한 번 돌아 1을, n=3에서 두 번 돌아 2를 반환한다.

n-- > 1, z = x - y: 두 수의 차는 피보나치 수가 아니다.
n-- >= 1, z = x + y: n=2에서 두 번 돌아 2를 반환하므로 한 항 더 진행된다.
n-- <= 1, z = x - y: n이 2 이상이면 조건이 처음부터 거짓이라 반복하지 않는다.

문제 15

다음 설명에 해당하는 노드 수 A, B, C의 합은? (단, 트리의 높이는 트리의 최대 레벨을 의미하며, 루트 노드의 레벨을 1로 한다)

○ A ＝ 높이가 5인 완전 이진 트리가 가질 수 있는 최소 노드 수
○ B ＝ 높이가 6인 포화 이진 트리의 노드 수
○ C ＝ 높이가 7인 완전 이진 트리가 가질 수 있는 최대 노드 수

1142

2206

3209

4222

정답 및 해설

A, B, C의 합은 206이다.

A: 높이 5인 완전 이진 트리의 최소는 4레벨까지 포화되고 5레벨에 노드 하나인 경우로 $2^4=16$
B: 높이 6인 포화 이진 트리는 $2^6-1=63$
C: 높이 7인 완전 이진 트리의 최대는 포화 상태로 $2^7-1=127$

합계는 $16+63+127=206$ 이다.

142: C를 높이 6 기준인 63으로 잡은 값과 같아 맞지 않는다.
209: B, C가 정해져 있으므로 A가 19여야 하지만 최소 노드 수는 16이다.
222: A를 $2^5=32$ 로 잡은 값으로, 높이 5의 최소 노드 수가 아니다.

문제 16

다음 그래프에 대하여 Sollin 알고리즘으로 최소 비용 신장 트리를 구하고자 한다. 각 노드가 하나의 트리로 구성된 초기 상태에서 한 단계 처리한 이후의 결과로 두 개의 트리로 구성된 포리스트(forest)가 만들어졌을 때, 각 트리의 가중치 합 중 큰 값은?

212

313

416

정답 및 해설

한 단계 처리 후 두 트리의 가중치 합은 9와 16이므로 큰 값은 16이다.

Sollin 알고리즘은 각 트리(초기에는 각 노드)가 자신에 연결된 최소 가중치 간선을 하나씩 동시에 선택한다. A는 A-B(6), B와 E는 B-E(3), C와 D는 C-D(4), F는 F-C(5), G는 G-F(7)를 고른다.

그 결과 A-B-E 트리(6+3=9)와 C-D-F-G 트리(4+5+7=16)의 두 트리로 된 포리스트가 만들어진다.

9는 두 트리 중 작은 쪽인 A-B-E 트리의 가중치 합이다.
12는 D-F 간선의 가중치로, 각 노드의 최소 간선이 아니어서 이 단계에서 선택되지 않는다.
13은 어느 트리의 합과도 맞지 않는 값이다.

문제 17

비어있는 레드 블랙 트리(red black tree)에 차례대로 키(key) 값 1, 3, 2, 4, 5, 6을 넣고 완성한 레드 블랙 트리를 전위 순회한 결과는? (단, 키를 저장하고 있는 노드만 순회하고, 순회 결과에서 키 값 뒤에 B를 붙이면 블랙 노드, R을 붙이면 레드 노드임을 나타낸다)

12B, 1B, 4R, 3B, 5B, 6R

22B, 1R, 4R, 3B, 5B, 6R

34B, 2R, 1B, 3B, 5B, 6R

44B, 2R, 1B, 3R, 5B, 6R

정답 및 해설

완성된 레드 블랙 트리의 전위 순회는 2B, 1B, 4R, 3B, 5B, 6R이다.

1(B), 3(R) 삽입 후 2를 넣으면 부모 3이 레드이고 삼촌이 없어 회전(오른쪽 후 왼쪽)하여 2B(1R, 3R)가 된다.
4 삽입 시 부모 3과 삼촌 1이 모두 레드라 색 변경: 1B, 3B, 루트 2는 블랙 유지.
5 삽입 시 부모 4는 레드, 삼촌이 없어 3에서 왼쪽 회전 → 4B(3R, 5R).
6 삽입 시 부모 5와 삼촌 3이 레드라 색 변경 → 3B, 5B, 4R.

최종 트리는 루트 2B, 왼쪽 1B, 오른쪽 4R(자식 3B·5B), 5B의 오른쪽 6R이다.

2B, 1R, 4R, 3B, 5B, 6R: 4 삽입 때 색 변경으로 1은 블랙이 된다.
4B, 2R, 1B, 3B, 5B, 6R: 루트가 바뀌는 회전은 2 삽입 때뿐이라 루트는 2로 유지된다.
4B, 2R, 1B, 3R, 5B, 6R: 루트가 2이고, 3은 마지막 색 변경에서 블랙이 된다.

문제 18

그림과 같은 원형 연결 리스트 myCLL을 만들기 위해 다음 파이썬 코드를 작성하였다. (가)～(다)에 들어갈 코드를 A～D에서 바르게 연결한 것은?

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

class CircularLinkedList:
    def __init__(self):
        self.last = None

    def insert(self, data):
        n = Node(data, None)
        if self.last is None:
            n.next = n
            self.last = n
        else:
            [ (가) ]
            [ (나) ]
            [ (다) ]

myCLL = CircularLinkedList()
myCLL.insert(1)
myCLL.insert(2)
myCLL.insert(3)

A. n.next = self.last
B. n.next = self.last.next
C. self.last = n
D. self.last.next = n

(가)　　(나)　　(다)

1A　　C　　D

2A　　D　　C

3B　　C　　D

4B　　D　　C

정답 및 해설

(가)는 n.next = self.last.next, (나)는 self.last.next = n, (다)는 self.last = n 이 들어가 B, D, C 순이다.

self.last 가 마지막 노드를 가리키므로 self.last.next 는 첫 노드다. 새 노드를 끝에 붙이려면 먼저 새 노드가 첫 노드를 가리키게 하고, 기존 마지막 노드가 새 노드를 가리키게 한 뒤, 마지막으로 last 를 새 노드로 옮긴다.

예를 들어 insert(3) 시 3→1 연결, 2→3 연결, last=3 이 되어 그림처럼 1→2→3→1 원형이 되고 last 는 3을 가리킨다.

(가)에 n.next = self.last 를 두면 새 노드가 첫 노드가 아닌 기존 마지막 노드를 가리켜 원형 순서가 깨진다.
(나)에 self.last = n 을 먼저 실행하면 기존 마지막 노드를 잃어, 이어지는 self.last.next = n 이 새 노드 자신을 가리키게 만든다.

문제 19

다음 C 코드는 단순 연결 리스트를 이용하여 스택의 pop() 함수를 구현한 것이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?

struct stack {
    int data;
    struct stack* link;
};
struct stack* top = NULL;
int pop(){
    struct stack* temp = top;
    int item;
    if (!temp){
        printf("Stack is empty.\n");
        exit(1);
    }
    item = temp->data;
    [ (가) ] ;
    free(temp);
    [ (나) ] ;
}

(가)　　(나)

1temp = temp->link　　return item

2temp = temp->link　　return top->data

3top = temp->link　　return item

4top = temp->link　　return top->data

정답 및 해설

(가) top = temp->link, (나) return item이다.

pop은 top을 다음 노드로 옮긴 뒤 원래 top 노드(temp)를 해제하고, 미리 저장해 둔 item을 반환해야 한다.

temp = temp->link, return item: temp가 다음 노드로 바뀌어 엉뚱한 노드를 해제하고 top도 갱신되지 않는다.
temp = temp->link, return top->data: top이 갱신되지 않고 엉뚱한 노드를 해제한다.
top = temp->link, return top->data: 꺼낸 값이 아니라 새 top의 값을 반환하며, 스택이 비면 NULL을 참조한다.

문제 20

다음 조건에 따라 공백 해시 테이블에 키(key) 값 12, 15, 25, 34, 37, 75, 62, 33, 47, 55, 21, 42, 53을 순서대로 삽입할 때, 충돌 횟수가 가장 많은 키 값은? (단, 해시 함수 또는 선형 조사법을 적용하여 찾아간 버킷에 빈 슬롯이 없을 때마다 충돌이 발생한 것으로 본다)

○ 해시 함수: h(x) ＝ x mod 13
○ 충돌 해결책: 선형 조사법(linear probing)
○ 해시 테이블의 크기: 13개 버킷(0부터 12까지 인덱스를 가짐)
○ 해시 테이블 버킷당 슬롯 수: 1개

121

242

353

462

정답 및 해설

충돌 횟수가 가장 많은 키는 21이다.

h(x) = x mod 13과 선형 조사로 넣으면 12→12, 15→2, 25→12 충돌 후 0, 34→8, 37→11, 75→10, 62→10부터 4회 충돌 후 1, 33→7, 47→8에서 1회 충돌 후 9, 55→3이다.

21은 8부터 9, 10, 11, 12, 0, 1, 2, 3이 모두 차 있어 9회 충돌 후 4에 들어간다. 이어 42는 3·4에서 2회 충돌 후 5, 53은 1부터 5까지 5회 충돌 후 6에 들어간다.

42: 2회 충돌에 그친다.
53: 5회 충돌이다.
62: 4회 충돌이다.

문제 21

다음 C 코드의 reverseList()는 단순 연결 리스트에 있는 노드의 순서를 역순으로 만드는 함수이다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

struct node {
    int data;
    struct node *link;
} *head;

void reverseList() {
    struct node *prevNode, *curNode;
    prevNode = head;
    curNode = head;
    head = NULL;

    while ( [ (가) ] ) {
        curNode = curNode->link;
        prevNode->link = head;
        [ (나) ] ;
        [ (다) ] ;
    }
}

(가)　　(나)　　(다)

1curNode != NULL　　head = curNode　　curNode = prevNode

2curNode != NULL　　head = prevNode　　prevNode = curNode

3head != NULL　　head = curNode　　curNode = prevNode

4head != NULL　　head = prevNode　　prevNode = curNode

정답 및 해설

(가) curNode != NULL, (나) head = prevNode, (다) prevNode = curNode이다.

prevNode는 이번에 뒤집을 노드, curNode는 다음 노드를 미리 잡아 두는 포인터, head는 이미 뒤집힌 부분의 첫 노드이다. 반복마다 prevNode의 링크를 head로 돌리고, head를 prevNode로, prevNode를 curNode로 한 칸씩 전진시킨다.

a→b→c를 추적하면 head가 a, b, c로 바뀌며 c→b→a가 되고, curNode가 NULL이 된 반복에서 마지막 노드까지 처리된 뒤 종료한다.

curNode != NULL, head = curNode, curNode = prevNode: head가 아직 뒤집지 않은 노드를 가리키고 포인터가 앞으로 나아가지 않는다.
head != NULL, head = curNode, curNode = prevNode: 시작 시 head가 NULL이라 반복이 실행되지 않는다.
head != NULL, head = prevNode, prevNode = curNode: 갱신 순서는 맞지만 시작 시 head가 NULL이라 반복에 들어가지 못한다.

문제 22

다음 배열에 대하여, 위치 값이 증가함에 따라 키(key) 값도 이에 정비례하여 증가한다는 가정으로 탐색 위치를 계산하는 보간 탐색을 수행할 때, 키 45를 찾을 때까지 탐색 위치를 계산한 횟수는? (단, 탐색 위치 계산 시 소수점 이하는 버린다)

위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]
키	2	3	4	7	13	18	22	27	32	42	45	70	72

정답 및 해설

키 45를 찾을 때까지 탐색 위치는 3회 계산된다.

보간 탐색의 위치 공식은 $low+\dfrac{(key-a[low])(high-low)}{a[high]-a[low]}$ 이다.

첫 계산: $0+\dfrac{43\times 12}{70}\approx 7.37$ → 위치 7, 키 27이 작으므로 low = 8
두 번째: $8+\dfrac{13\times 4}{40}=9.3$ → 위치 9, 키 42가 작으므로 low = 10
세 번째: $10+\dfrac{0\times 2}{27}=10$ → 위치 10에서 45를 찾는다.

2회: 두 번째로 계산한 위치의 키는 42로 아직 찾지 못했다.
4회: 세 번째 계산에서 이미 45를 찾는다.
5회: 세 번째 계산에서 탐색이 끝나므로 더 늘어날 수 없다.

문제 23

다음 C 코드는 쉘 정렬을 구현한 것이다. 코드의 출력 결과는?

#include <stdio.h>
void sort(int arr[], int n) {
  int count = 1;
  int i, j, k, h, val;
  for (h = n/2; h > 0; h /= 2) {
    for (i = 0; i < h; i++)  {
      for (j = i+h; j < n; j += h) {
        val = arr[j];
        k = j;
        while (k > h-1 && arr[k-h] > val) {
          arr[k] = arr[k-h];
          k -= h;
        }
        arr[k] = val;

        if (count == 5)
          for (int t = 0; t < 6; t++)
            printf("%d ", arr[t]);
        count++;
      }
    }
  }
}

int main() {
    int a[6] = {5, 9, 2, 3, 6, 7};
    sort(a, 6);
}

12 3 5 6 9 7

22 3 6 5 9 7

33 6 2 5 9 7

43 9 2 5 6 7

정답 및 해설

count가 5일 때 출력되는 배열은 2 3 6 5 9 7이다.

간격 h=3: 5·3 정렬로 3 9 2 5 6 7(count 1), 9·6 정렬로 3 6 2 5 9 7(count 2), 2·7은 그대로(count 3).
간격 h=1: 6 삽입은 이동 없음(count 4), 2 삽입은 맨 앞까지 이동해 2 3 6 5 9 7(count 5)이 되어 이때 출력한다.

2 3 5 6 9 7: 5까지 삽입한 count 6 이후의 상태다.
3 6 2 5 9 7: 간격 3 단계가 끝난 count 3·4 시점의 상태다.
3 9 2 5 6 7: count 1 직후의 상태다.

문제 24

루트 노드의 인덱스를 1로 하는 1차원 배열을 이용하여 최대 힙(max heap)을 구현한 후, 다음 데이터를 차례대로 하나씩 힙에 삽입하였다. 이후 힙 삭제 연산을 1회 수행한 후 배열의 인덱스 6에 저장된 데이터는?

15, 8, 10, 18, 22, 13, 26, 7

210

313

415

정답 및 해설

삭제 후 인덱스 6에 저장된 데이터는 10이다.

삽입 과정에서 18은 8·15와, 22는 15·18과, 13은 10과, 26은 13·22와 교환되며 올라가 힙은 [26, 18, 22, 8, 15, 10, 13, 7]이 된다.

삭제 시 루트 26을 빼고 마지막 7을 루트로 옮긴 뒤 더 큰 자식과 교환한다: 7↔22, 이어 7↔13. 결과는 [22, 18, 13, 8, 15, 10, 7]이고 인덱스 6은 10 그대로이다.

8: 인덱스 4에 있다.
13: 재배치로 인덱스 3으로 올라간다.
15: 인덱스 5에 있다.

문제 25

행 우선 순서로 저장되는 C 언어 2차원 배열 char a[3][5]가 선언되고 초기화되었을 때, a[2][3]과 다른 값을 가지는 것은?

1*(a+5*2+3)

2*(&a[0][0]+5*2+3)

3(a[0]+5*2)[3]

4(*(a+2))[3]

정답 및 해설

a[2][3]과 값이 다른 것은 *(a+5*2+3)이다.

a는 문자 5개짜리 행을 가리키는 포인터라 a+1은 한 행씩 이동한다. 따라서 a+13은 배열 범위 밖의 13행 뒤를 가리키고, 역참조 결과도 문자 값이 아니라 행 배열(주소)이다.

*(&a[0][0]+5*2+3): 문자 포인터에서 13칸 이동하므로 행 우선 저장에서 a[2][3]이다.
(a[0]+5*2)[3]: a[0]은 문자 포인터이므로 13칸 뒤 원소, 곧 a[2][3]이다.
(*(a+2))[3]: *(a+2)는 a[2]이므로 a[2][3]과 같다.

7급 국가직 자료구조론 기출문제모두CBT · moducbt.com

22년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

세 개의 노드를 가진 무방향 완전 그래프의 신장 트리(spanning tree)는 최대 몇 가지인가?

정답 및 해설

세 정점 무방향 완전 그래프의 신장 트리는 3가지이다.

신장 트리는 정점 3개를 간선 2개로 잇으므로, 간선 3개 중 하나를 빼는 경우의 수만큼 생긴다. 케일리 공식으로도 $n^{n-2}=3^{1}=3$ 이다.

1가지: 어느 간선을 빼도 서로 다른 트리가 되므로 하나뿐일 수 없다.
2가지: 뺄 수 있는 간선 후보가 3개이므로 부족하다.
4가지: 간선 3개 중 2개를 고르는 경우는 $\binom{3}{2}=3$ 을 넘을 수 없다.

문제 2

다음 트리를 중위 순회한 결과로 옳은 것은?

12, 4, 5, 1, 3, 6, 7

22, 4, 5, 3, 6, 7, 1

34, 2, 5, 1, 6, 3, 7

44, 5, 2, 1, 6, 7, 3

정답 및 해설

중위 순회 결과는 4, 2, 5, 1, 6, 3, 7이다.

2, 4, 5, 1, 3, 6, 7은 각 서브트리에서 루트를 먼저 방문하고 전체 루트를 가운데 둔 순서로, 중위 순회가 아니다.
2, 4, 5, 3, 6, 7, 1은 루트를 맨 마지막에 방문한 형태로 중위 순회 규칙과 맞지 않는다.
4, 5, 2, 1, 6, 7, 3은 각 서브트리를 후위 순회한 순서로, 서브트리 루트를 자식 사이가 아닌 뒤에 방문했다.

문제 3

다음은 입력 개수

n

에 대한 알고리즘 A～D의 수행시간 복잡도를 나타낸 것이다. 알고리즘 A～D를 수행시간 효율이 좋은 것부터 순서대로 나열한 것은?

알고리즘	수행시간 복잡도
A	$O(n\log n)$
B	$O(2^n)$
C	$O(n^2)$
D	$O(n!)$

1A, C, B, D

2A, C, D, B

3C, A, B, D

4C, A, D, B

정답 및 해설

수행시간 효율이 좋은 순서는 A, C, B, D이다.

증가 속도는 $n\log n \lt n^2 \lt 2^n \lt n!$ 이다. 다항식은 지수보다 느리게, 지수는 팩토리얼보다 느리게 증가한다.

A, C, D, B: $n!$ 이 $2^n$ 보다 빠르게 커지므로 D가 B보다 뒤에 와야 한다.
C, A, B, D: $n^2$ 이 $n\log n$ 보다 크므로 C가 A보다 앞설 수 없다.
C, A, D, B: C·A 순서와 B·D 순서가 모두 뒤바뀌었다.

문제 4

이진 트리에 대한 설명으로 옳은 것만을 모두 고르면?

1ㄱ, ㄴ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄷ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

ㄱ: 높이 5인 이진 트리의 최대 노드 수는 $2^5-1=31$ 이므로 15가 아니다.
ㄷ: 인덱스 i의 부모는 $\lfloor i/2 \rfloor$ 이므로 13의 부모는 6이다.

문제 5

크기가 4인 빈 스택에 다음 연산을 차례로 수행한 후의 스택 상태를 바르게 표현한 것은?

push(3) → push(7) → pop() → push(5) → push(8) →
peek() → push(10) → pop()

정답 및 해설

최종 스택은 아래부터 3, 5, 8이 쌓인 상태이다.

3, 5만 남은 상태: peek()을 삭제 연산으로 오해한 결과다.
5, 8, 10이 남은 상태: 바닥의 3은 꺼낸 적이 없고 10은 마지막 pop()으로 제거된다.
10, 8, 5, 3이 가득 찬 상태: 마지막 pop()을 반영하지 않았다.

문제 6

13, 11, 13, 15, 16, 20, 21

23, 11, 13, 15, 16, 21, 22

33, 11, 13, 16, 18, 20, 21

43, 11, 13, 16, 18, 21, 22

정답 및 해설

A로부터의 최단 거리를 오름차순으로 나열하면 3, 11, 13, 15, 16, 20, 21이다.

다익스트라 알고리즘으로 확정 순서를 따라가면 B(3), E(11), C(13)가 먼저 확정된다. 이어 F는 C를 거쳐 13+2=15, H는 E를 거쳐 11+5=16으로 확정된다.

D는 C를 거치면 22이지만 H를 거치면 16+4=20으로 더 짧고, G는 D를 거쳐 20+1=21로 확정된다.

3, 11, 13, 15, 16, 21, 22는 마지막 두 거리가 실제 최단 거리인 D의 20(H 경유), G의 21(D 경유)보다 커서 최단 경로 갱신을 놓친 나열이다.
3, 11, 13, 16, 18, 20, 21은 F를 B 경유 거리(18)로 잡아 C를 거치는 15를 반영하지 못했다.
3, 11, 13, 16, 18, 21, 22는 F와 D·G 모두에서 최단 경로 갱신을 놓친 결과다.

문제 7

다음 데이터를 차례대로 하나씩 입력받아 AVL 트리를 생성할 때, 필요한 회전을 적용 순서대로 바르게 나열한 것은?

6, 7, 8, 2, 1, 5, 4

1LL회전, LR회전, LR회전

2LL회전, LR회전, RL회전

3RR회전, LL회전, LR회전

4RR회전, LL회전, RL회전

정답 및 해설

회전은 RR회전, LL회전, LR회전 순서로 일어난다.

6, 7, 8 삽입 시 6에서 오른쪽-오른쪽으로 치우쳐 RR회전 → 루트 7, 자식 6·8.
2, 1 삽입 시 6에서 왼쪽-왼쪽으로 치우쳐 LL회전 → 7의 왼쪽이 2(자식 1·6).

LL회전, LR회전, LR회전: 처음 6, 7, 8은 오른쪽으로 치우치므로 첫 회전은 RR이다.
LL회전, LR회전, RL회전: 첫 회전이 RR이어야 하고 4 삽입 때는 회전이 없다.
RR회전, LL회전, RL회전: 5의 삽입 경로는 왼쪽 후 오른쪽이므로 RL이 아니라 LR이다.

문제 8

다음 C 코드는 원형 연결 리스트에 속한 모든 노드의 값들을 더하여 출력한다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

#include <stdio.h>
#include <malloc.h>
typedef struct Node {
    struct Node *a;
    int b;
} Node;

int listSum(Node *p) {
    int sum = 0;
    Node *s = p;
    do {
        sum += [ (가) ];
        p = [ (나) ];
    } while ( [ (다) ] );
    return sum;
}

int main() {
    int MAX = 5;
    int i, s;
    Node *p[MAX];

    for( i = 0; i < MAX; i++) {
        p[i] = (Node*)malloc(sizeof(Node));
        p[i]->b = i+1;
    }
    for( i = 0; i < MAX-1; i++)
        p[i]->a = p[i+1];
    p[MAX-1]->a = p[0];
    s = listSum(p[0]);
    printf("Sum = %d", s);
}

(가)　　(나)　　(다)

1p.b　　p.a　　p != NULL

2p->a　　p->b　　p != s

3p->b　　p->a　　p != NULL

4(*p).b　　(*p).a　　p != s

정답 및 해설

(가) p->b, (나) p->a, (다) p != s이며, 이를 (*p).b, (*p).a 로 표기한 조합이 맞다.

p.b, p.a, p != NULL: p는 포인터라 점 연산자로 멤버에 접근할 수 없고, NULL을 만나지 않아 끝나지 않는다.
p->a, p->b, p != s: 값 멤버와 링크 멤버가 뒤바뀌었다.
p->b, p->a, p != NULL: 원형 리스트에는 NULL이 없어 무한 반복한다.

문제 9

다음 C 코드를 수행하면 4개의 값이 출력된다. 출력 값 중 나머지 3개와 다른 값을 출력하는 C 코드의 라인 번호는?

라인 번호	C 코드
1	#include <stdio.h>
2
3	int main() {
4	int array[] = {0,1,2};
5	int *p = array+2;
6
7	printf("%d\n", *(p-1));
8	printf("%d\n", *p-1);
9	printf("%d\n", *(p--));
10	printf("%d\n", *p);
11	}

410

정답 및 해설

나머지와 다른 값을 출력하는 것은 *(p--)를 출력하는 줄이다.

*(p-1): 한 칸 앞 원소의 값 1을 출력한다.
*p-1: 역참조가 먼저라 2에서 1을 뺀 1을 출력한다.
마지막 *p: 앞 줄의 감소가 반영되어 1을 출력한다.

문제 10

다음 tree_height() 함수는 이진 트리의 루트 노드를 매개변수로 받아 트리의 높이를 반환한다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

int tree_height (node *ptr) {
    int left_h, right_h;
    if (ptr == NULL)
        return 0;
    else {
        left_h = tree_height(ptr->left);
        right_h = tree_height(ptr->right);
        if ( [ (가) ] )
            return [ (나) ] ;
        else
            return [ (다) ] ;
    }
}

(가)　　(나)　　(다)

1left_h > right_h　　left_h　　right_h

2left_h > right_h　　left_h + 1　　right_h + 1

3left_h < right_h　　left_h　　right_h

4left_h < right_h　　left_h + 1　　right_h + 1

정답 및 해설

(가) left_h > right_h, (나) left_h + 1, (다) right_h + 1이다.

트리 높이는 두 서브트리 높이 중 큰 값에 현재 노드 1을 더한 것이다. 왼쪽이 더 크면 left_h + 1, 아니면 right_h + 1을 반환한다.

left_h > right_h, left_h, right_h: 현재 노드를 더하지 않아 어떤 트리든 높이가 0이 된다.
left_h < right_h, left_h, right_h: 작은 쪽을 고르고 1도 더하지 않는다.
left_h < right_h, left_h + 1, right_h + 1: 조건이 뒤집혀 더 낮은 서브트리 기준으로 높이를 반환한다.

문제 11

142

243

344

445

정답 및 해설

간선의 최대 개수는 45개이다.

자기 간선과 중복 간선이 없으면 서로 다른 두 정점 쌍마다 간선이 최대 하나다. 완전 그래프의 간선 수는 $\dfrac{n(n-1)}{2}=\dfrac{10\times 9}{2}=45$ 이다.

42: 정점 쌍 수보다 3개 적어 최대가 아니다.
43: 정점 쌍 수보다 2개 적어 최대가 아니다.
44: 연결되지 않은 정점 쌍이 하나 남아 최대가 아니다.

문제 12

#include <stdio.h>
char stack[100];
int top = -1;

void push(char ch) {stack[++top] = ch;}

char pop() {return stack[top--];}

int isEmpty() {return top == -1;}

int isPalindrome(char *str) {
    int i;
    for ( i = 0; str[i]; i++ )
        [ (가) ] ;

    for ( i = 0; !isEmpty(); i++ )
        if ( [ (나) ] )
            return 0;
    return 1;
}

int main() {
    char input[100];
    scanf("%s", input);
    printf("%s",
        isPalindrome(input) ? "True" : "False");
}

(가)　　(나)

1push(str[i])　　str[i] == pop()

2push(str[i])　　str[i] != pop()

3push(str[top-i])　　str[i] == pop()

4push(str[top-i])　　str[i] != pop()

정답 및 해설

(가) push(str[i]), (나) str[i] != pop()이다.

push(str[i]), str[i] == pop(): 같은 문자일 때 0을 반환해 회문을 거짓으로 판정한다.
push(str[top-i]), str[i] == pop(): top이 -1부터 시작해 엉뚱한 위치를 넣고, 비교 조건도 반대다.
push(str[top-i]), str[i] != pop(): 문자를 차례대로 넣지 못해 역순 비교가 성립하지 않는다.

문제 13

int search(int key, int a[], int n) {
    int mid;
    int left = 0;
    int right = n-1;
    while ([ (가) ]) {
        mid = (right + left) / 2;
        if (key == a[mid]) return mid;
        if ([ (나) ]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

(가)　　(나)

1left < right　　key < a[mid]

2left < right　　key > a[mid]

3left <= right　　key < a[mid]

4left <= right　　key > a[mid]

정답 및 해설

(가) left <= right, (나) key < a[mid]이다.

원소 하나만 남은 left == right 구간도 검사해야 하므로 등호가 필요하다. key가 a[mid]보다 작으면 왼쪽 절반에 있으므로 right = mid - 1로 구간을 줄인다.

left < right, key < a[mid]: 원소 하나가 남은 구간을 검사하지 않아 찾지 못하는 경우가 생긴다.
left < right, key > a[mid]: 등호 누락에 더해 구간을 반대 방향으로 줄인다.
left <= right, key > a[mid]: key가 클 때 오른쪽 끝을 줄여 탐색 방향이 뒤집힌다.

문제 14

다음 C 코드는 반복구조를 이용하여 n번째 피보나치 수를 구하는 함수이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, n은 0 이상의 정수이다)

int fibonacci(int n){
    int x = 0, y = 1, z = 0;
    if (n < 2) return n;
    while ([ (가) ]) {
        [ (나) ] ;
        x = y;
        y = z;
    }
    return z;
}

(가)　　(나)

1n-- > 1　　z = x + y

2n-- > 1　　z = x - y

3n-- >= 1　　z = x + y

4n-- <= 1　　z = x - y

정답 및 해설

(가) n-- > 1, (나) z = x + y이다.

n-- > 1, z = x - y: 두 수의 차는 피보나치 수가 아니다.
n-- >= 1, z = x + y: n=2에서 두 번 돌아 2를 반환하므로 한 항 더 진행된다.
n-- <= 1, z = x - y: n이 2 이상이면 조건이 처음부터 거짓이라 반복하지 않는다.

문제 15

다음 설명에 해당하는 노드 수 A, B, C의 합은? (단, 트리의 높이는 트리의 최대 레벨을 의미하며, 루트 노드의 레벨을 1로 한다)

1142

2206

3209

4222

정답 및 해설

A, B, C의 합은 206이다.

합계는 $16+63+127=206$ 이다.

142: C를 높이 6 기준인 63으로 잡은 값과 같아 맞지 않는다.
209: B, C가 정해져 있으므로 A가 19여야 하지만 최소 노드 수는 16이다.
222: A를 $2^5=32$ 로 잡은 값으로, 높이 5의 최소 노드 수가 아니다.

문제 16

212

313

416

정답 및 해설

한 단계 처리 후 두 트리의 가중치 합은 9와 16이므로 큰 값은 16이다.

그 결과 A-B-E 트리(6+3=9)와 C-D-F-G 트리(4+5+7=16)의 두 트리로 된 포리스트가 만들어진다.

9는 두 트리 중 작은 쪽인 A-B-E 트리의 가중치 합이다.
12는 D-F 간선의 가중치로, 각 노드의 최소 간선이 아니어서 이 단계에서 선택되지 않는다.
13은 어느 트리의 합과도 맞지 않는 값이다.

문제 17

12B, 1B, 4R, 3B, 5B, 6R

22B, 1R, 4R, 3B, 5B, 6R

34B, 2R, 1B, 3B, 5B, 6R

44B, 2R, 1B, 3R, 5B, 6R

정답 및 해설

완성된 레드 블랙 트리의 전위 순회는 2B, 1B, 4R, 3B, 5B, 6R이다.

최종 트리는 루트 2B, 왼쪽 1B, 오른쪽 4R(자식 3B·5B), 5B의 오른쪽 6R이다.

2B, 1R, 4R, 3B, 5B, 6R: 4 삽입 때 색 변경으로 1은 블랙이 된다.
4B, 2R, 1B, 3B, 5B, 6R: 루트가 바뀌는 회전은 2 삽입 때뿐이라 루트는 2로 유지된다.
4B, 2R, 1B, 3R, 5B, 6R: 루트가 2이고, 3은 마지막 색 변경에서 블랙이 된다.

문제 18

그림과 같은 원형 연결 리스트 myCLL을 만들기 위해 다음 파이썬 코드를 작성하였다. (가)～(다)에 들어갈 코드를 A～D에서 바르게 연결한 것은?

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

class CircularLinkedList:
    def __init__(self):
        self.last = None

    def insert(self, data):
        n = Node(data, None)
        if self.last is None:
            n.next = n
            self.last = n
        else:
            [ (가) ]
            [ (나) ]
            [ (다) ]

myCLL = CircularLinkedList()
myCLL.insert(1)
myCLL.insert(2)
myCLL.insert(3)

A. n.next = self.last
B. n.next = self.last.next
C. self.last = n
D. self.last.next = n

(가)　　(나)　　(다)

1A　　C　　D

2A　　D　　C

3B　　C　　D

4B　　D　　C

정답 및 해설

(가)는 n.next = self.last.next, (나)는 self.last.next = n, (다)는 self.last = n 이 들어가 B, D, C 순이다.

예를 들어 insert(3) 시 3→1 연결, 2→3 연결, last=3 이 되어 그림처럼 1→2→3→1 원형이 되고 last 는 3을 가리킨다.

(가)에 n.next = self.last 를 두면 새 노드가 첫 노드가 아닌 기존 마지막 노드를 가리켜 원형 순서가 깨진다.
(나)에 self.last = n 을 먼저 실행하면 기존 마지막 노드를 잃어, 이어지는 self.last.next = n 이 새 노드 자신을 가리키게 만든다.

문제 19

다음 C 코드는 단순 연결 리스트를 이용하여 스택의 pop() 함수를 구현한 것이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?

struct stack {
    int data;
    struct stack* link;
};
struct stack* top = NULL;
int pop(){
    struct stack* temp = top;
    int item;
    if (!temp){
        printf("Stack is empty.\n");
        exit(1);
    }
    item = temp->data;
    [ (가) ] ;
    free(temp);
    [ (나) ] ;
}

(가)　　(나)

1temp = temp->link　　return item

2temp = temp->link　　return top->data

3top = temp->link　　return item

4top = temp->link　　return top->data

정답 및 해설

(가) top = temp->link, (나) return item이다.

pop은 top을 다음 노드로 옮긴 뒤 원래 top 노드(temp)를 해제하고, 미리 저장해 둔 item을 반환해야 한다.

temp = temp->link, return item: temp가 다음 노드로 바뀌어 엉뚱한 노드를 해제하고 top도 갱신되지 않는다.
temp = temp->link, return top->data: top이 갱신되지 않고 엉뚱한 노드를 해제한다.
top = temp->link, return top->data: 꺼낸 값이 아니라 새 top의 값을 반환하며, 스택이 비면 NULL을 참조한다.

문제 20

121

242

353

462

정답 및 해설

충돌 횟수가 가장 많은 키는 21이다.

21은 8부터 9, 10, 11, 12, 0, 1, 2, 3이 모두 차 있어 9회 충돌 후 4에 들어간다. 이어 42는 3·4에서 2회 충돌 후 5, 53은 1부터 5까지 5회 충돌 후 6에 들어간다.

42: 2회 충돌에 그친다.
53: 5회 충돌이다.
62: 4회 충돌이다.

문제 21

다음 C 코드의 reverseList()는 단순 연결 리스트에 있는 노드의 순서를 역순으로 만드는 함수이다. (가)～(다)에 들어갈 내용을 바르게 연결한 것은?

struct node {
    int data;
    struct node *link;
} *head;

void reverseList() {
    struct node *prevNode, *curNode;
    prevNode = head;
    curNode = head;
    head = NULL;

    while ( [ (가) ] ) {
        curNode = curNode->link;
        prevNode->link = head;
        [ (나) ] ;
        [ (다) ] ;
    }
}

(가)　　(나)　　(다)

1curNode != NULL　　head = curNode　　curNode = prevNode

2curNode != NULL　　head = prevNode　　prevNode = curNode

3head != NULL　　head = curNode　　curNode = prevNode

4head != NULL　　head = prevNode　　prevNode = curNode

정답 및 해설

(가) curNode != NULL, (나) head = prevNode, (다) prevNode = curNode이다.

a→b→c를 추적하면 head가 a, b, c로 바뀌며 c→b→a가 되고, curNode가 NULL이 된 반복에서 마지막 노드까지 처리된 뒤 종료한다.

curNode != NULL, head = curNode, curNode = prevNode: head가 아직 뒤집지 않은 노드를 가리키고 포인터가 앞으로 나아가지 않는다.
head != NULL, head = curNode, curNode = prevNode: 시작 시 head가 NULL이라 반복이 실행되지 않는다.
head != NULL, head = prevNode, prevNode = curNode: 갱신 순서는 맞지만 시작 시 head가 NULL이라 반복에 들어가지 못한다.

문제 22

위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]
키	2	3	4	7	13	18	22	27	32	42	45	70	72

정답 및 해설

키 45를 찾을 때까지 탐색 위치는 3회 계산된다.

보간 탐색의 위치 공식은 $low+\dfrac{(key-a[low])(high-low)}{a[high]-a[low]}$ 이다.

2회: 두 번째로 계산한 위치의 키는 42로 아직 찾지 못했다.
4회: 세 번째 계산에서 이미 45를 찾는다.
5회: 세 번째 계산에서 탐색이 끝나므로 더 늘어날 수 없다.

문제 23

다음 C 코드는 쉘 정렬을 구현한 것이다. 코드의 출력 결과는?

#include <stdio.h>
void sort(int arr[], int n) {
  int count = 1;
  int i, j, k, h, val;
  for (h = n/2; h > 0; h /= 2) {
    for (i = 0; i < h; i++)  {
      for (j = i+h; j < n; j += h) {
        val = arr[j];
        k = j;
        while (k > h-1 && arr[k-h] > val) {
          arr[k] = arr[k-h];
          k -= h;
        }
        arr[k] = val;

        if (count == 5)
          for (int t = 0; t < 6; t++)
            printf("%d ", arr[t]);
        count++;
      }
    }
  }
}

int main() {
    int a[6] = {5, 9, 2, 3, 6, 7};
    sort(a, 6);
}

12 3 5 6 9 7

22 3 6 5 9 7

33 6 2 5 9 7

43 9 2 5 6 7

정답 및 해설

count가 5일 때 출력되는 배열은 2 3 6 5 9 7이다.

2 3 5 6 9 7: 5까지 삽입한 count 6 이후의 상태다.
3 6 2 5 9 7: 간격 3 단계가 끝난 count 3·4 시점의 상태다.
3 9 2 5 6 7: count 1 직후의 상태다.

문제 24

15, 8, 10, 18, 22, 13, 26, 7

210

313

415

정답 및 해설

삭제 후 인덱스 6에 저장된 데이터는 10이다.

삽입 과정에서 18은 8·15와, 22는 15·18과, 13은 10과, 26은 13·22와 교환되며 올라가 힙은 [26, 18, 22, 8, 15, 10, 13, 7]이 된다.

8: 인덱스 4에 있다.
13: 재배치로 인덱스 3으로 올라간다.
15: 인덱스 5에 있다.

문제 25

행 우선 순서로 저장되는 C 언어 2차원 배열 char a[3][5]가 선언되고 초기화되었을 때, a[2][3]과 다른 값을 가지는 것은?

1*(a+5*2+3)

2*(&a[0][0]+5*2+3)

3(a[0]+5*2)[3]

4(*(a+2))[3]

정답 및 해설

a[2][3]과 값이 다른 것은 *(a+5*2+3)이다.

*(&a[0][0]+5*2+3): 문자 포인터에서 13칸 이동하므로 행 우선 저장에서 a[2][3]이다.
(a[0]+5*2)[3]: a[0]은 문자 포인터이므로 13칸 뒤 원소, 곧 a[2][3]이다.
(*(a+2))[3]: *(a+2)는 a[2]이므로 a[2][3]과 같다.