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

24년 1회차

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

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

24년 1회차

총 25문항 · 객관식 · 정답·해설 포함
문제 1
배열로 구현한 최대 힙(max heap)에 키 값 <15, 10, 12, 8, 9, 7, 20>을 차례대로 삽입하였을 때, 값 7이 저장되어 있는 색인(index) 번호는? (단, 배열에 저장되는 키 값의 첫 번째 저장위치 색인 번호는 1이다)
14
25
36
47
정답 및 해설

값 7은 색인 6에 저장된다.

최대 힙은 새 키를 마지막 위치에 넣고 부모보다 크면 위로 교환한다. 15, 10, 12, 8, 9, 7은 교환 없이 색인 1~6에 차례로 들어가므로 7은 색인 6에 놓인다.

마지막 20은 색인 7에 들어간 뒤 부모 12(색인 3), 다시 루트 15(색인 1)와 교환되어 배열은 20, 10, 15, 8, 9, 7, 12가 된다. 이 과정에서 색인 6의 7은 움직이지 않는다.

  • 색인 4에는 8이 그대로 남는다.
  • 색인 5에는 9가 그대로 남는다.
  • 색인 7에는 20과 자리를 바꾼 12가 내려온다.
문제 2
비어 있는 이진 탐색 트리(binary search tree)에 키 값 <7, 5, 1, 8, 3, 6, 0, 9, 4, 2>를 순서대로 삽입한 후, 중위 순회(in-order traversal)한 결과는?
10 1 2 3 4 5 6 7 8 9
20 2 4 3 1 6 5 9 8 7
37 5 1 0 3 2 4 6 8 9
49 8 6 4 2 3 0 1 5 7
정답 및 해설

이진 탐색 트리를 중위 순회하면 키가 오름차순으로 나오므로 결과는 0 1 2 3 4 5 6 7 8 9이다.

BST는 모든 노드에서 왼쪽 서브트리 < 루트 < 오른쪽 서브트리가 성립하고, 중위 순회는 왼쪽 → 루트 → 오른쪽 순으로 방문하므로 삽입 순서와 관계없이 정렬된 순서가 된다.

  • 0 2 4 3 1 6 5 9 8 7은 같은 트리를 후위 순회한 결과이다.
  • 7 5 1 0 3 2 4 6 8 9는 같은 트리를 전위 순회한 결과이다.
  • 9 8 6 4 2 3 0 1 5 7은 오른쪽 서브트리를 먼저 방문하는 후위 순회(오른쪽 → 왼쪽 → 루트) 결과로, 중위 순회와 무관하다.
문제 3
다음 그래프의 정점 A에서 시작하여 다른 모든 정점까지의 최단 경로를 찾고자 한다. 다익스트라(Dijkstra) 알고리즘을 사용하여 찾은 정점 G까지의 최단 경로를 바르게 나열한 것은?

1A → B → F → G
2A → C → F → G
3A → D → F → G
4A → D → F → H → G
정답 및 해설

A에서 G까지의 최단 경로는 A → D → F → H → G(거리 5)이다.

다익스트라를 진행하면 먼저 거리 2인 D가 확정되고, D를 거쳐 F가 2+1=3, G가 2+5=7로 갱신된다. 이어 B(3), F(3)가 확정되며 F를 거쳐 C와 H가 각각 4, G는 3+5=8(갱신 없음)이 된다.

H(4)가 확정되면 H를 거친 G까지의 거리가 4+1=5로 갱신되어 최종 최단 거리가 된다.

  • B와 F를 거쳐 G로 가는 경로: 3+2+5=10으로 더 길다.
  • C와 F를 거쳐 G로 가는 경로: 6+1+5=12로 더 길다.
  • D와 F에서 곧바로 G로 가는 경로: 2+1+5=8로, H를 경유하는 5보다 길다.
문제 4
다음 C 코드에서 밑줄 친 ‘x=x+3;’의 수행 빈도수는? (단, n은 0 이상의 정수이다)
void complexity(int n){
    int i, j, x=0;
    for(i=0; i<=n; i++) {
        for(j=i; j<=n; j++)
            x=x+3;
    }
}
1n(n−1)2\frac{n(n-1)}{2}
2n(n+1)2\frac{n(n+1)}{2}
3(n−1)(n+1)2\frac{(n-1)(n+1)}{2}
4(n+1)(n+2)2\frac{(n+1)(n+2)}{2}
정답 및 해설

밑줄 친 문장의 수행 빈도수는 (n+1)(n+2)2\dfrac{(n+1)(n+2)}{2}이다.

바깥 반복은 i = 0, 1, …, n의 n+1회이고, 안쪽 반복은 j = i부터 n까지이므로 i마다 n−i+1n-i+1회 수행된다.

∑i=0n(n−i+1)=(n+1)+n+⋯+1=(n+1)(n+2)2\sum_{i=0}^{n}(n-i+1) = (n+1)+n+\cdots+1 = \dfrac{(n+1)(n+2)}{2}

  • n(n+1)2\dfrac{n(n+1)}{2}는 1부터 n까지의 합으로, i = 0일 때의 n+1회를 빠뜨린 값이다.
  • n(n−1)2\dfrac{n(n-1)}{2}는 n = 1일 때 0이지만, 실제로는 i = 0에서 2회, i = 1에서 1회로 3회 수행된다.
  • (n−1)(n+1)2\dfrac{(n-1)(n+1)}{2}는 n = 0일 때 음수가 되어 수행 횟수가 될 수 없다(실제는 1회).
문제 5
다음 C 코드로 표현한 알고리즘의 시간 복잡도는?
for(i=1; i<n; i++) {
    MaxData=arr[i];
    for(j=i-1; j>=0; j--) {
        if(arr[j]>MaxData)
            arr[j+1]=arr[j];
        else
            break;
    }
    arr[j+1]=MaxData;
}
1O(log⁡n\log n)
2O(nlog⁡nn\log n)
3O(n2n^2)
4O(n3n^3)
정답 및 해설

주어진 코드는 삽입 정렬이며 시간 복잡도는 O(n2)O(n^2)이다.

바깥 반복은 n-1회이고, 안쪽 반복은 MaxData보다 큰 원소를 한 칸씩 뒤로 미는 동안 최대 i회 수행된다. 역순 입력(최악)에서는 1+2+⋯+(n−1)=n(n−1)21+2+\cdots+(n-1) = \dfrac{n(n-1)}{2}회 비교·이동한다.

  • O(log⁡n)O(\log n)은 탐색 범위를 절반씩 줄이는 이진 탐색 수준으로, 모든 원소를 다뤄야 하는 정렬에는 불가능하다.
  • O(nlog⁡n)O(n\log n)은 병합·힙 정렬 같은 분할 기반 정렬의 복잡도로, 원소를 한 칸씩 옮기는 이 코드의 최악보다 작다.
  • O(n3)O(n^3)은 3중 반복에 해당하며, 이 코드는 2중 반복이다.
문제 6
다음 자료에 대하여 퀵 정렬(quick sort)로 오름차순 정렬을 하고자 한다. 기준값인 피벗(pivot)으로 정렬 대상 자료의 첫 번째 원소를 사용할 때, 두 번째 분할(partition) 연산 수행 후의 결과는?
< 27, 5, 37, 4, 61, 11, 59, 15, 48, 20 >
14 5 11 20 15 27 59 61 48 37
24 5 11 15 20 27 59 61 48 37
34 5 11 15 20 27 59 37 48 61
44 5 11 20 15 27 59 37 48 61
정답 및 해설

두 번째 분할 후 결과는 4 5 11 20 15 27 59 61 48 37이다.

첫 분할(피벗 27)은 왼쪽에서 27보다 큰 값, 오른쪽에서 27보다 작은 값을 찾아 교환한다. 37과 20, 61과 15를 교환한 뒤 두 포인터가 엇갈리면 피벗을 11과 교환해 11 5 20 4 15 | 27 | 59 61 48 37이 된다.

두 번째 분할은 왼쪽 부분 11 5 20 4 15(피벗 11)에서 20과 4를 교환하고, 엇갈린 위치의 4와 피벗을 교환해 4 5 11 20 15가 된다. 오른쪽 부분은 아직 분할 전이므로 59 61 48 37 그대로이다.

  • 4 5 11 15 20 27 59 61 48 37은 20과 15의 순서까지 정리된 상태로, 이후 분할이 더 진행되어야 나온다.
  • 4 5 11 15 20 27 59 37 48 61은 오른쪽 부분이 분할 전인데도 순서가 바뀌어 있다.
  • 4 5 11 20 15 27 59 37 48 61도 왼쪽은 맞지만 분할 전인 오른쪽 부분의 61과 37이 자리를 바꾸어 있다.
문제 7
다음 재귀함수를 호출하는 C 프로그램의 실행 결과는?
#include <stdio.h>
void RecursiveFunc(int n) {
    if(n <= 0)  {
        printf("R-%d ", n);
        return;
    }
    printf("R-%d ", n);
    if(n%2 == 0)
        RecursiveFunc(n-2);
    else
        RecursiveFunc(n-1);

    printf("R-%d ", n);
}

int main(void)
{
    RecursiveFunc(3);
    return 0;
}
1R-3 R-2 R-0
2R-3 R-1 R-0 R-2 R-3
3R-3 R-2 R-0 R-2 R-3
4R-3 R-2 R-1 R-2 R-3
정답 및 해설

출력은 R-3 R-2 R-0 R-2 R-3이다.

RecursiveFunc(3)은 R-3을 출력하고 3이 홀수이므로 RecursiveFunc(2)를 호출한다. 2는 R-2를 출력하고 짝수이므로 RecursiveFunc(0)을 호출하며, 0은 기저 조건(n <= 0)에 걸려 R-0만 출력하고 반환한다.

복귀하면서 재귀 호출 뒤의 printf가 실행되어 RecursiveFunc(2)가 R-2, RecursiveFunc(3)이 R-3을 차례로 출력한다.

  • R-3 R-2 R-0은 재귀 호출 뒤에 있는 복귀 시 출력문을 빠뜨린 것이다.
  • R-3 R-1 R-0 R-2 R-3은 홀수 3에서 n-1인 2가 아니라 1로 넘어간 것으로 추적한 결과다.
  • R-3 R-2 R-1 R-2 R-3은 짝수 2에서 n-2인 0이 아니라 1로 넘어간 것으로 추적한 결과다.
문제 8
다음은 병합 정렬(merge sort) 알고리즘을 구현한 파이썬 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
sorted = []

def merge_sort(arr, left, right):
    if left<right:
        middle=(left+right)//2
        merge_sort(arr, left, middle)
        merge_sort(arr, middle+1, right)
        merge(arr, left, middle, right)

def merge(arr, left, middle, right):
    global sorted
    i=left
    j=middle+1
    k=( (가) )
    while i<=middle and ( (나) ):
        if arr[i]<=arr[j]:
            sorted.insert(k, arr[i])
            i=i+1
        else:
            sorted.insert(k, arr[j])
            j=j+1
        k=k+1

    if i>middle:
        sorted[k:k+right-j+1]=arr[j:right+1]
    else:
        sorted[k:k+middle-i+1]=arr[i:middle+1]

    arr[left:right+1]=sorted[left:right+1]
1left / j<=right
2left / k<=right
3middle / j<=right
4middle / k<=right
정답 및 해설

(가)는 left, (나)는 j<=right이다.

병합 결과를 쓰는 위치 k는 마지막에 sorted[left:right+1]을 arr로 복사하므로 구간 시작인 left에서 출발해야 한다. 병합 반복은 왼쪽 구간(i<=middle)과 오른쪽 구간(j<=right)에 모두 원소가 남아 있는 동안만 비교한다.

  • left / k<=right 조합은 오른쪽 구간이 먼저 소진돼도 k<=right가 참이어서 비교가 계속되고 arr[j]가 구간 밖을 읽는다.
  • middle / j<=right 조합은 병합 결과가 구간 중간부터 기록되어 복사 범위 sorted[left:right+1]과 어긋난다.
  • middle / k<=right 조합은 시작 위치와 반복 조건이 모두 틀렸다.
문제 9
다음은 C 언어 구조체를 이용하여 배열과 단순 연결 리스트로 큐를 표현한 것이다.
(가) 배열을 이용한 큐 구조체(나) 연결 리스트를 이용한 큐 구조체
typedef struct _Queue {
    int front;
    int rear;
    int numOfData;
    int queArr[50];
} QType;
typedef struct _node {
    int data;
    struct _node *next;
} Node;
typedef struct _Queue {
    Node *front;
    Node *rear;
    int numOfData;
} QType;

아래의 <조건>에 따라 (가), (나) 각각에 대해 Enqueue 함수를 세 번 호출하고 Dequeue 함수를 한 번 호출한 후, 큐에 할당된 메모리 공간의 크기(byte)를 계산한 값으로 바르게 연결한 것은?
<조 건>
○ 큐 변수는 QType q; 형태로 선언한다.
○ Enqueue 함수는 큐의 front에 데이터를 추가하는 함수로 함수 원형은 void Enqueue(QType *q, int value)이다.
○ Dequeue 함수는 큐의 rear에서 데이터를 삭제하는 함수이며, 함수 원형은 void Dequeue(QType *q)이다.
○ int형 자료의 경우 4바이트, 포인터형 자료의 경우 8바이트의 메모리 공간을 사용한다.
○ Enqueue와 Dequeue 함수에서는 배열 및 연결 리스트 특성에 맞게 필요한 메모리를 할당ㆍ회수하는 동작이 적절히 일어난다.
○ 연결 리스트에서 삭제 연산은 메모리 회수를 포함한다.
○ 구조체 변수를 메모리에 할당할 때 바이트 패딩 없이 할당한다.
124 / 44
224 / 56
3212 / 44
4212 / 56
정답 및 해설

(가)는 212바이트, (나)는 44바이트이다.

배열 큐는 선언 시 QType 크기가 고정되므로 연산과 관계없이 int 3개와 int 배열 50칸으로 4×53=2124 \times 53 = 212바이트이다.

연결 리스트 큐는 QType(포인터 2개 + int 1개) 8×2+4=208 \times 2 + 4 = 20바이트에, 노드(int + 포인터) 4+8=124 + 8 = 12바이트가 남은 노드 수만큼 더해진다. 세 번 삽입·한 번 삭제 후 노드는 2개이므로 20+12×2=4420 + 12 \times 2 = 44바이트이다.

  • 24바이트는 배열 큐의 크기가 될 수 없다. 배열 큐는 삽입 횟수와 관계없이 50칸 배열을 처음부터 포함한다.
  • 56바이트는 삭제된 노드의 메모리 회수를 반영하지 않고 노드 3개분을 더한 값이다.
문제 10
다음 C 프로그램의 실행 결과는? (단, 2차원 배열의 경우 행 우선으로 메모리에 저장된다)
#include <stdio.h>
int main(void)
{
    int i, j, test[3][4];
    for(i=0; i<3; i++)
        for(j=0; j<4; j++)
            test[i][3-j]=i*4+j;
    printf("%d ", *(*(test+1)+5));
}
15
26
39
410
정답 및 해설

출력값은 10이다.

test[i][3-j]=i*4+j는 각 행을 거꾸로 채우므로 배열은 행 0: 3 2 1 0, 행 1: 7 6 5 4, 행 2: 11 10 9 8이 된다.

*(test+1)은 행 1의 시작 주소이고 여기에 5를 더하면, 행 우선 저장에서 선형 위치 1×4+5 = 9인 test[2][1]을 가리킨다. 그 값은 10이다.

  • 9는 값이 아니라 선형 위치를 그대로 답한 것이다.
  • 6은 행 1 안의 test[1][1] 값으로, 오프셋 5가 다음 행으로 넘어간다는 점을 놓친 것이다.
  • 5도 행 1 안의 test[1][2] 값으로 같은 착오다.
문제 11
다음은 구조체 배열에서 최댓값을 찾아 출력하는 C 프로그램이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
#include <stdio.h>
typedef struct _data {
    int value;
} DataType;
DataType *max(DataType *a) {
    int i, max=a[0].value, index=0;
    for(i=0; i<5; i++)
        if(max<a[i].value) {
            max=a[i].value;
            index=i;
        }
    return ( (가) );
}

int main(void)
{
    int i;
    DataType data[5], *result;
    for(i=0; i<5; i++)
        scanf("%d", &data[i].value);

    result=max(data);
    printf("max=%d", ( (나) ));
    return 0;
}
1&a[index] / result->value
2&a[index] / result.value
3a[index] / result->value
4a[index] / (*result).value
정답 및 해설

(가)는 &a[index], (나)는 result->value이다.

max 함수의 반환형이 DataType *이므로 최댓값 원소의 주소를 반환해야 하고, 그 주소를 받은 result도 포인터이므로 멤버는 화살표 연산자로 접근한다.

  • &a[index] / result.value 조합은 포인터인 result에 점(.) 연산자를 써서 컴파일 오류가 난다.
  • a[index] / result->value 조합은 a[index]가 구조체 값 자체여서 포인터 반환형과 맞지 않는다.
  • a[index] / (*result).value 조합은 (나)가 result->value와 같아 옳지만, 반환값 a[index]가 포인터가 아니다.
문제 12
다음 전위 표기식을 후위 표기식으로 변환한 것은?
/ + a b – c d
1a b + c d - /
2a b c d + - /
3a b / c d + -
4a b c d / + -
정답 및 해설

후위 표기식은 a b + c d - /이다.

전위식 / + a b - c d는 연산자 /의 두 피연산자가 (+ a b)와 (- c d)이므로 중위식 (a+b) / (c-d)를 나타낸다. 각 부분을 후위로 바꾸면 a b +와 c d -이고, 마지막에 /를 붙인다.

  • a b c d + - /는 a / (b - (c+d))를 나타내는 다른 식이다.
  • a b / c d + -는 (a/b) - (c+d)를 나타낸다.
  • a b c d / + -는 a - (b + c/d)를 나타낸다.
문제 13
다음은 단순 연결 리스트를 이용하여 스택 자료구조를 구현한 파이썬 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
class Node:
    def __init__(self, data, next):
        self.data=data
        self.next=next

class MyStack:
    def __init__(self):
        self.top=None

    def push(self, data):
        ( (가) )
        self.top=n

    def pop(self):
        if self.top!=None:
            n=self.top
            ( (나) )
            return n.data
1n=Node(data, None) / self.top=n.next.next
2n=Node(data, None) / self.top=self.top.next
3n=Node(data, self.top) / self.top=n.next.next
4n=Node(data, self.top) / self.top=self.top.next
정답 및 해설

(가)는 n=Node(data, self.top), (나)는 self.top=self.top.next이다.

push는 새 노드의 next가 기존 top을 가리키게 만든 뒤 top을 새 노드로 바꿔야 연결이 유지된다. pop은 꺼낼 노드를 n에 보관하고 top을 바로 아래 노드로 옮긴다.

  • Node(data, None) / self.top=n.next.next 조합은 새 노드가 기존 스택과 끊기고, pop에서 노드 하나를 건너뛴다.
  • Node(data, None) / self.top=self.top.next 조합은 pop은 맞지만 push할 때마다 기존 스택이 연결에서 사라진다.
  • Node(data, self.top) / self.top=n.next.next 조합은 push는 맞지만 n이 top이므로 두 칸 아래로 이동해 원소 하나가 사라진다.
문제 14
그림과 같은 이중 연결 리스트(doubly linked list)에서 노드 X의 왼쪽에 노드 Y를 삽입할 때, 연산의 순서를 바르게 나열한 것은? (단, Llink는 왼쪽 노드를 가리키는 포인터 변수이고, Rlink는 오른쪽 노드를 가리키는 포인터 변수이다)

a. X -> Llink -> Rlink = Y
b. Y -> Llink = X -> Llink
c. X -> Llink = Y
d. Y -> Rlink = X

1a → c → b → d
2a → c → d → b
3b → c → a → d
4b → d → a → c
정답 및 해설

올바른 순서는 b → d → a → c이다.

X의 기존 왼쪽 노드 정보(X -> Llink)는 Y를 연결하는 데 계속 필요하므로, X -> Llink를 Y로 바꾸는 연산은 맨 마지막에 해야 한다.

먼저 Y의 두 링크를 채우고(Y의 왼쪽 = X의 기존 왼쪽 노드, Y의 오른쪽 = X), 기존 왼쪽 노드의 Rlink를 Y로 바꾼 뒤, 마지막으로 X의 Llink를 Y로 바꾼다.

  • a → c → b → d: c 직후 X -> Llink가 이미 Y이므로 b에서 Y의 왼쪽 링크가 자기 자신을 가리키게 된다.
  • a → c → d → b: 같은 이유로 b가 Y -> Llink = Y가 되어 기존 왼쪽 노드와의 연결이 끊긴다.
  • b → c → a → d: c 후에 a를 하면 X -> Llink가 Y이므로 Y -> Rlink만 Y로 바뀌고, 기존 왼쪽 노드의 Rlink는 여전히 X를 가리킨다.
문제 15
최소 1개 이상의 노드로 이루어진 원형 연결 리스트(circular linked list)에서 포인터 L이 리스트의 첫 번째 노드를 가리킨다고 할 때, 데이터의 값이 x인 노드를 탐색하여 반환하는 C 코드는?
1
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    while(p!=L) {
        if(p->data==x) return p;
        p=p->link;
    }
    return NULL;
}
2
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    while(p->link!=L) {
        if(p->data==x) return p;
        p=p->link;
    }
    return NULL;
}
3
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    do {
        if(p->data==x) return p;
        p=p->link;
    } while(p!=L);
    return NULL;
}
4
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    do {
        if(p->data==x) return p;
        p=p->link;
    } while(p->link!=L);
    return NULL;
}
정답 및 해설

첫 노드부터 검사한 뒤 p가 다시 L로 돌아오면 멈추는 do-while(p!=L) 형태가 옳다.

원형 연결 리스트는 마지막 노드의 link가 첫 노드 L을 가리키므로 p가 L로 돌아오면 한 바퀴를 다 돈 것이다. 시작점 p가 이미 L이므로 조건 검사를 본문 실행 뒤에 해야 모든 노드를 검사할 수 있다.

  • while(p!=L) 형태는 p=L에서 시작하므로 반복문이 한 번도 실행되지 않아 항상 NULL을 반환한다.
  • while(p->link!=L) 형태는 마지막 노드에 도달하면 검사 전에 반복이 끝나 마지막 노드를 놓친다.
  • do-while(p->link!=L) 형태도 p가 마지막 노드로 이동하는 순간 조건이 거짓이 되어 마지막 노드를 검사하지 못한다.
문제 16
0이 아닌 원소의 개수가 7개인 9 × 12 희소행렬에 대한 설명으로 옳지 않은 것은?
1행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하면, 108개의 배열 원소에 대한 공간이 필요하다.
20이 아닌 원소들에 대한 <행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현하면 14개의 배열 원소에 대한 공간이 필요하다.
3행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하는 것은 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어진다.
4<행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현한 희소행렬에 대하여 전치 행렬을 구하는 방법의 시간 복잡도는 최악의 경우, O(열의 수2×행의 수)O(\text{열의 수}^2 \times \text{행의 수})이다.
정답 및 해설

<행 번호, 열 번호, 값> 쌍 표현에 14개가 필요하다는 설명이 옳지 않다.

이 표현은 0이 아닌 원소 하나당 행 번호·열 번호·값 3개를 저장하므로 7×3=217 \times 3 = 21개가 필요하고, 행렬 크기·원소 수를 담는 머리 행까지 두면 24개가 된다. 14개는 원소당 2개만 센 값이다.

  • 행렬을 그대로 2차원 배열로 두면 9×12=1089 \times 12 = 108개 공간이 필요하다.
  • 108개 중 7개만 0이 아니므로 대부분의 공간이 낭비되어 기억 공간 활용도가 떨어진다.
  • 단순 전치 알고리즘은 열마다 모든 항을 훑어 열의 수 × 항의 수에 비례하고, 최악에는 항의 수가 행의 수 × 열의 수가 되므로 열의 수의 제곱 × 행의 수가 된다.
문제 17
다음 C 코드에서 heapify(a, 7)을 수행한 후 배열 a[]의 내용은? (단, 모든 배열 원소값은 양의 정수로 한정하고, －1은 연산 대상이 아니며, 0은 삭제된 값을 나타낸다)
int a[8]={-1, 1, 2, 3, 6, 4, 7, 5};

int heapify(int *a, int n) {
    int item=a[1], temp=a[n];
    int i=1, j=2;

    a[n]=0,  n=n-1;
    while(j<=n) {
        if(j<n && a[j]>a[j+1]) j++;
        if(temp<a[j]) break;
        else {
            a[i]=a[j];
            i=j;
            j=j*2;
        }
    }
    a[i]=temp;
    return item;
}
1
01234567
－12346570
2
01234567
－12436570
3
01234567
－12345670
4
01234567
－12435670
정답 및 해설

heapify(a, 7) 수행 후 배열은 -1, 2, 4, 3, 6, 5, 7, 0이다.

이 함수는 최소 힙의 루트 삭제이다. 루트 1을 item에 보관하고 마지막 원소 5를 temp로 꺼낸 뒤 a[7]=0, n=6으로 만들고, 루트 자리에서 더 작은 자식과 temp를 비교하며 내려간다.

i=1: 자식 a[2]=2, a[3]=3 중 작은 2가 temp 5보다 작으므로 a[1]=2, i=2
i=2: 자식 a[4]=6, a[5]=4 중 작은 4가 5보다 작으므로 a[2]=4, i=5
j=10 > n이므로 종료하고 a[5]=5를 저장한다.

  • -1, 2, 3, 4, 6, 5, 7, 0은 a[2] 자리에 3이 올라가 있어, i=2에서 자식 6, 4 중 작은 4를 끌어올리는 과정과 맞지 않는다.
  • -1, 2, 3, 4, 5, 6, 7, 0은 완전히 정렬된 상태로, 한 경로만 따라 내려가는 삭제 연산의 결과가 아니다.
  • -1, 2, 4, 3, 5, 6, 7, 0은 temp 5가 a[4]에 들어간 형태로, 더 작은 자식 a[5]=4 쪽으로 내려가야 한다는 점과 맞지 않는다.
문제 18
다음 그래프는 AOE(Activity on Edge) 네트워크를 보여 준다. 정점의 숫자는 공정을 나타내고, 간선 위에 있는 aia_i는 작업을, 괄호 안의 숫자는 그 작업을 수행하는 데 필요한 최소한의 시간을 나타낼 때, 임계 경로의 길이는?

110
211
312
413
정답 및 해설

임계 경로의 길이는 12이며, 경로는 0 → 3 → 6 → 8(a2, a7, a10)이다.

각 정점의 가장 이른 발생 시각은 들어오는 간선 중 최댓값으로 구한다.
1: 5, 2: 3, 3: 4, 4: 3+1=4
5: max(5+2, 4+3)=7, 6: max(4+3, 4+5)=9, 7: 4+2=6

8: max(7+4, 9+3, 6+5)=max(11, 12, 11)=12

  • 10: 0 → 2 → 4 → 6 → 8(3+1+3+3)의 길이로, 가장 긴 경로가 아니다.
  • 11: 0 → 1 → 5 → 8이나 0 → 3 → 7 → 8의 길이로, 가장 긴 경로가 아니다.
  • 13: 13이 되는 경로는 존재하지 않는다.
문제 19
키 값 <2, 6, 3, 4, 5, 1, 7, 8>을 순서대로 삽입해서 레드 블랙 트리를 생성할 때, 단일 회전과 이중 회전이 발생하는 횟수를 바르게 나열한 것은?
11 / 1
21 / 2
32 / 1
42 / 2
정답 및 해설

단일 회전은 1회, 이중 회전은 2회 발생한다.

빨강으로 삽입한 노드의 부모가 빨강일 때, 삼촌이 빨강이면 색 변경만 하고 삼촌이 검정(NIL 포함)이면 회전한다. 삽입 노드·부모·조부모가 일직선이면 단일 회전, 꺾여 있으면 이중 회전이다.

3 삽입: 2 → 6(오른쪽) → 3(왼쪽)으로 꺾이고 삼촌이 없어 이중 회전, 3이 루트가 된다.
4 삽입: 부모 6과 삼촌 2가 모두 빨강이라 색 변경만 한다.
5 삽입: 6 → 4(왼쪽) → 5(오른쪽)로 꺾이고 삼촌이 없어 이중 회전, 5가 4와 6의 부모가 된다.
1·7 삽입: 1은 부모가 검정이라 그대로, 7은 삼촌 4가 빨강이라 색 변경만 한다.
8 삽입: 6 → 7 → 8이 오른쪽 일직선이고 삼촌이 없어 단일 회전한다.

  • 단일 1회·이중 1회로 보면 5 삽입 때의 꺾인 배치에서 일어나는 이중 회전을 빠뜨린 것이다.
  • 단일 2회·이중 1회로 보면 색 변경만으로 해결되는 삽입을 회전으로 센 것이고, 이중 회전도 하나 빠졌다.
  • 단일 2회·이중 2회로 보면 4나 7 삽입처럼 삼촌이 빨강인 경우를 회전으로 센 것이다.
문제 20
다음 이진 트리의 전체 노드 수를 계산하는 C 코드에서 (가)에 들어갈 내용은? (단, n은 최초에 이진 트리 내 루트 노드를 가리키는 포인터 변수이며, TNode는 이진 트리의 노드 구조를 나타낸다)
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
}TNode;

int count_node(TNode *n) {
    if(n==NULL) return 0;
    return ( (가) ) +count_node(n->right);
}
11
2n->data
3count_node(n->left)
41+count_node(n->left)
정답 및 해설

(가)에는 1+count_node(n->left)가 들어간다.

전체 노드 수 = 현재 노드 1개 + 왼쪽 서브트리 노드 수 + 오른쪽 서브트리 노드 수라는 재귀 정의를 그대로 옮긴 것이다. 빈 트리(NULL)는 0을 반환해 재귀가 끝난다.

  • 1만 두면 왼쪽 서브트리를 세지 않아 루트에서 오른쪽으로 이어진 노드만 센다.
  • n->data는 노드에 저장된 문자의 코드값을 더하므로 개수가 아니다.
  • count_node(n->left)만 두면 자기 자신을 세지 않아 모든 호출이 결국 0을 반환한다.
문제 21
다음 탐색 알고리즘을 이용하여 아래 리스트에서 키(key) 34를 찾을 경우, 필요한 반복 연산 횟수는? (단, low 변수에는 0, high 변수에는 15가 전달된다)
int a_search(int list[], int key, int low, int high) {
    int middle;
    while(low<=high) {
        middle=(low+high)/2;
        if(key==list[middle])
            return middle;
        else if(key>list[middle])
            low=middle+1;
        else
            high=middle-1;
    }
    return -1;
}

0123456789101112131415
261113182022272930343841424547
13
24
35
46
정답 및 해설

키 34는 반복 4회 만에 찾는다.

코드는 정렬된 리스트에 대한 이진 탐색이며, 반복마다 middle 값과 비교해 범위를 절반으로 줄인다.

1회: low=0, high=15 → middle=7, list[7]=27 < 34이므로 low=8
2회: low=8, high=15 → middle=11, list[11]=38 > 34이므로 high=10
3회: low=8, high=10 → middle=9, list[9]=30 < 34이므로 low=10
4회: low=10, high=10 → middle=10, list[10]=34로 탐색 성공

  • 3회째 비교 대상은 30이어서 아직 키를 찾지 못한 상태다.
  • 5회는 4회째에 return으로 반복이 끝나므로 나올 수 없다.
  • 6회는 원소 16개에 대한 이진 탐색의 최대 반복 수인 5회보다도 많다.
문제 22
버킷(bucket)이 13개이고 버킷당 슬롯(slot)이 1개인 해시 테이블에 키 값 <7, 20, 3, 19, 45>를 차례대로 저장하고자 한다. 다음 <조건>에 따라 아래 <해시 함수>를 이용하여 작동하는 이중 해싱(double hashing)에서, 마지막 키 값 45의 저장 위치는?
<조 건>
○ 버킷의 인덱스는 0부터 시작한다.
○ h(x)h(x)는 첫 번째 조사 위치를 결정하는 기본 해시 함수이다.
○ f(x)f(x)는 충돌 발생 시 조사 위치 간격을 결정하는 함수이다.
○ 하나의 키 값에 대한 해시 함수 연산 중 충돌이 1번 이상 발생할 경우 ii번째 충돌에 대응하여 hi(x)h_i(x)를 적용한다.

<해시 함수>
h(x)=x mod 13h(x) = x \bmod 13
f(x)=x mod 11f(x) = x \bmod 11
hi(x)=(h(x)+i×f(x)) mod 13h_i(x) = (h(x)+i \times f(x)) \bmod 13
15
27
38
411
정답 및 해설

키 45는 버킷 8에 저장된다.

앞의 키들을 먼저 배치한다.
7: h=7 → 버킷 7
20: h=7 충돌, f=9 → (7+9) mod 13 = 3
3: h=3 충돌, f=3 → (3+3) mod 13 = 6
19: h=6 충돌, f=8 → (6+8) mod 13 = 1

45: h=45 mod 13 = 6에서 충돌하고 f=45 mod 11 = 1이다. h1=(6+1) mod 13=7h_1 = (6+1) \bmod 13 = 7도 차 있으므로 h2=(6+2×1) mod 13=8h_2 = (6+2 \times 1) \bmod 13 = 8에 저장된다.

  • 버킷 7은 첫 재조사 위치지만 이미 키 7이 있다.
  • 버킷 5는 조사 순서 6 → 7 → 8에 나타나지 않는다.
  • 버킷 11도 조사 순서에 나타나지 않는다.
문제 23
다음 그래프에 대한 설명 중 옳은 것만을 모두 고르면?

ㄱ. 가장 긴 단순 경로의 길이는 4이다.
ㄴ. 진입차수가 진출차수보다 큰 정점은 1개이다.
ㄷ. 완전 그래프가 되기 위해 추가로 필요한 간선의 수는 10개이다.
ㄹ. 간선 <A, B>를 제거한 후 위상정렬을 수행하면 B, D, A, E, C, F 또는 B, D, A, C, E, F순으로 정점이 나열된다.

1ㄱ, ㄹ
2ㄴ, ㄷ
3ㄱ, ㄴ, ㄹ
4ㄴ, ㄷ, ㄹ
정답 및 해설

옳은 것은 ㄱ, ㄹ이다.

그래프의 간선은 A→B, A→C, A→E, B→D, D→A, D→E, D→F, C→F, E→F의 9개이다.

  • ㄱ(옳음): B→D→A→E→F처럼 길이 4인 단순 경로가 있다. C와 E는 모두 F로만 나가므로 두 정점을 한 경로에 함께 담을 수 없어 길이 5(정점 6개)는 불가능하다.
  • ㄴ(틀림): 진입차수가 진출차수보다 큰 정점은 E(진입 2, 진출 1)와 F(진입 3, 진출 0)의 2개이다.
  • ㄷ(틀림): 정점 6개의 완전 방향 그래프는 간선 30개로 21개를 더해야 하고, 무방향으로 보아도 15개 중 9쌍이 이미 연결되어 있어 6개가 필요하다. 어느 쪽도 10개가 아니다.
  • ㄹ(옳음): A→B를 지우면 진입차수 0인 B부터 B, D, A 순으로 나오고, 그다음 C와 E가 동시에 진입차수 0이 되어 어느 쪽을 먼저 놓아도 되며 마지막이 F이다.
문제 24
무방향 그래프(undirected graph) G의 인접 행렬(adjacent matrix) 표현을 C 언어의 2차원 배열을 이용하여 다음과 같이 구현했다. 그래프 G의 정점(vertex)이 0, 1, 2, 3, 4, 5, 6의 숫자로 표현될 때, 무방향 그래프 G의 그림으로 옳은 것은?
int G[7][7]={
                { 0, 1, 1, 0, 0, 0, 0 },
                { 1, 0, 1, 1, 0, 0, 0 },
                { 1, 1, 0, 1, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 0 },
                { 0, 0, 1, 1, 1, 0, 1 },
                { 0, 0, 0, 0, 0, 1, 0 }
        };

1[그림]
2[그림]
3[그림]
4[그림]
정답 및 해설

올바른 그림은 간선 0-1, 0-2, 1-2, 1-3, 2-3, 2-5, 3-5, 4-5, 5-6의 9개로 이루어진 그래프이다.

무방향 그래프의 인접 행렬은 대칭이므로 상삼각 부분의 1만 읽으면 간선 목록이 된다. 특히 정점 4는 5와만, 정점 6도 5와만 연결되며 0과 3은 연결되지 않는다.

  • 0과 3이 연결되고 2-4, 3-6 간선이 있는 그림: 행렬의 0행 3열과 2행 4열이 0이므로 틀리다.
  • 2와 4가 연결되고 2-5 간선이 없는 그림: 2행 5열이 1, 2행 4열이 0이므로 틀리다.
  • 0-3, 3-4 간선이 있고 1-2, 2-5 간선이 없는 그림: 행렬과 여러 칸이 어긋난다.
문제 25
다음 방향 그래프(directed graph)에서 노드 A부터 시작하여 깊이 우선 탐색과 너비 우선 탐색을 수행하는 경우, 여섯 번째로 방문하는 노드의 쌍을 바르게 연결한 것은? (단, 노드 A는 첫 번째 방문 노드이고, 인접 노드가 다수일 경우 방문 순서는 알파벳순으로 하며, 탐색 과정에서 도달하지 못하는 경로는 고려하지 않는다)

1C / D
2D / I
3H / H
4I / H
정답 및 해설

여섯 번째 방문 노드는 깊이 우선 탐색이 I, 너비 우선 탐색이 H이다.

그래프의 간선은 A→B, A→D, B→G, C→A, C→H, D→I, E→C, E→F, F→B, G→H, I→H이며, A에서 도달 가능한 노드는 A, B, D, G, H, I뿐이다.

깊이 우선 탐색: A → B → G → H까지 내려간 뒤 되돌아와 D → I 순이므로 A, B, G, H, D, I.
너비 우선 탐색: A의 인접 B, D, 다음 단계로 B의 G와 D의 I, 마지막으로 H이므로 A, B, D, G, I, H.

  • C를 여섯 번째로 보는 경우: C로 들어오는 간선은 E→C뿐이라 A에서 C에 도달할 수 없다.
  • 깊이 우선에서 D를 여섯 번째로 보는 경우: D는 다섯 번째로 방문된다.
  • 깊이 우선에서 H를 여섯 번째로 보는 경우: H는 G 다음 네 번째로 방문된다.
7급 국가직 자료구조론 기출문제모두CBT · moducbt.com
24년 1회차
총 25문항 · 객관식 · 정답·해설 포함
문제 1
배열로 구현한 최대 힙(max heap)에 키 값 <15, 10, 12, 8, 9, 7, 20>을 차례대로 삽입하였을 때, 값 7이 저장되어 있는 색인(index) 번호는? (단, 배열에 저장되는 키 값의 첫 번째 저장위치 색인 번호는 1이다)
14
25
36
47
정답 및 해설

값 7은 색인 6에 저장된다.

최대 힙은 새 키를 마지막 위치에 넣고 부모보다 크면 위로 교환한다. 15, 10, 12, 8, 9, 7은 교환 없이 색인 1~6에 차례로 들어가므로 7은 색인 6에 놓인다.

마지막 20은 색인 7에 들어간 뒤 부모 12(색인 3), 다시 루트 15(색인 1)와 교환되어 배열은 20, 10, 15, 8, 9, 7, 12가 된다. 이 과정에서 색인 6의 7은 움직이지 않는다.

  • 색인 4에는 8이 그대로 남는다.
  • 색인 5에는 9가 그대로 남는다.
  • 색인 7에는 20과 자리를 바꾼 12가 내려온다.
문제 2
비어 있는 이진 탐색 트리(binary search tree)에 키 값 <7, 5, 1, 8, 3, 6, 0, 9, 4, 2>를 순서대로 삽입한 후, 중위 순회(in-order traversal)한 결과는?
10 1 2 3 4 5 6 7 8 9
20 2 4 3 1 6 5 9 8 7
37 5 1 0 3 2 4 6 8 9
49 8 6 4 2 3 0 1 5 7
정답 및 해설

이진 탐색 트리를 중위 순회하면 키가 오름차순으로 나오므로 결과는 0 1 2 3 4 5 6 7 8 9이다.

BST는 모든 노드에서 왼쪽 서브트리 < 루트 < 오른쪽 서브트리가 성립하고, 중위 순회는 왼쪽 → 루트 → 오른쪽 순으로 방문하므로 삽입 순서와 관계없이 정렬된 순서가 된다.

  • 0 2 4 3 1 6 5 9 8 7은 같은 트리를 후위 순회한 결과이다.
  • 7 5 1 0 3 2 4 6 8 9는 같은 트리를 전위 순회한 결과이다.
  • 9 8 6 4 2 3 0 1 5 7은 오른쪽 서브트리를 먼저 방문하는 후위 순회(오른쪽 → 왼쪽 → 루트) 결과로, 중위 순회와 무관하다.
문제 3
다음 그래프의 정점 A에서 시작하여 다른 모든 정점까지의 최단 경로를 찾고자 한다. 다익스트라(Dijkstra) 알고리즘을 사용하여 찾은 정점 G까지의 최단 경로를 바르게 나열한 것은?

1A → B → F → G
2A → C → F → G
3A → D → F → G
4A → D → F → H → G
정답 및 해설

A에서 G까지의 최단 경로는 A → D → F → H → G(거리 5)이다.

다익스트라를 진행하면 먼저 거리 2인 D가 확정되고, D를 거쳐 F가 2+1=3, G가 2+5=7로 갱신된다. 이어 B(3), F(3)가 확정되며 F를 거쳐 C와 H가 각각 4, G는 3+5=8(갱신 없음)이 된다.

H(4)가 확정되면 H를 거친 G까지의 거리가 4+1=5로 갱신되어 최종 최단 거리가 된다.

  • B와 F를 거쳐 G로 가는 경로: 3+2+5=10으로 더 길다.
  • C와 F를 거쳐 G로 가는 경로: 6+1+5=12로 더 길다.
  • D와 F에서 곧바로 G로 가는 경로: 2+1+5=8로, H를 경유하는 5보다 길다.
문제 4
다음 C 코드에서 밑줄 친 ‘x=x+3;’의 수행 빈도수는? (단, n은 0 이상의 정수이다)
void complexity(int n){
    int i, j, x=0;
    for(i=0; i<=n; i++) {
        for(j=i; j<=n; j++)
            x=x+3;
    }
}
1n(n−1)2\frac{n(n-1)}{2}
2n(n+1)2\frac{n(n+1)}{2}
3(n−1)(n+1)2\frac{(n-1)(n+1)}{2}
4(n+1)(n+2)2\frac{(n+1)(n+2)}{2}
정답 및 해설

밑줄 친 문장의 수행 빈도수는 (n+1)(n+2)2\dfrac{(n+1)(n+2)}{2}이다.

바깥 반복은 i = 0, 1, …, n의 n+1회이고, 안쪽 반복은 j = i부터 n까지이므로 i마다 n−i+1n-i+1회 수행된다.

∑i=0n(n−i+1)=(n+1)+n+⋯+1=(n+1)(n+2)2\sum_{i=0}^{n}(n-i+1) = (n+1)+n+\cdots+1 = \dfrac{(n+1)(n+2)}{2}

  • n(n+1)2\dfrac{n(n+1)}{2}는 1부터 n까지의 합으로, i = 0일 때의 n+1회를 빠뜨린 값이다.
  • n(n−1)2\dfrac{n(n-1)}{2}는 n = 1일 때 0이지만, 실제로는 i = 0에서 2회, i = 1에서 1회로 3회 수행된다.
  • (n−1)(n+1)2\dfrac{(n-1)(n+1)}{2}는 n = 0일 때 음수가 되어 수행 횟수가 될 수 없다(실제는 1회).
문제 5
다음 C 코드로 표현한 알고리즘의 시간 복잡도는?
for(i=1; i<n; i++) {
    MaxData=arr[i];
    for(j=i-1; j>=0; j--) {
        if(arr[j]>MaxData)
            arr[j+1]=arr[j];
        else
            break;
    }
    arr[j+1]=MaxData;
}
1O(log⁡n\log n)
2O(nlog⁡nn\log n)
3O(n2n^2)
4O(n3n^3)
정답 및 해설

주어진 코드는 삽입 정렬이며 시간 복잡도는 O(n2)O(n^2)이다.

바깥 반복은 n-1회이고, 안쪽 반복은 MaxData보다 큰 원소를 한 칸씩 뒤로 미는 동안 최대 i회 수행된다. 역순 입력(최악)에서는 1+2+⋯+(n−1)=n(n−1)21+2+\cdots+(n-1) = \dfrac{n(n-1)}{2}회 비교·이동한다.

  • O(log⁡n)O(\log n)은 탐색 범위를 절반씩 줄이는 이진 탐색 수준으로, 모든 원소를 다뤄야 하는 정렬에는 불가능하다.
  • O(nlog⁡n)O(n\log n)은 병합·힙 정렬 같은 분할 기반 정렬의 복잡도로, 원소를 한 칸씩 옮기는 이 코드의 최악보다 작다.
  • O(n3)O(n^3)은 3중 반복에 해당하며, 이 코드는 2중 반복이다.
문제 6
다음 자료에 대하여 퀵 정렬(quick sort)로 오름차순 정렬을 하고자 한다. 기준값인 피벗(pivot)으로 정렬 대상 자료의 첫 번째 원소를 사용할 때, 두 번째 분할(partition) 연산 수행 후의 결과는?
< 27, 5, 37, 4, 61, 11, 59, 15, 48, 20 >
14 5 11 20 15 27 59 61 48 37
24 5 11 15 20 27 59 61 48 37
34 5 11 15 20 27 59 37 48 61
44 5 11 20 15 27 59 37 48 61
정답 및 해설

두 번째 분할 후 결과는 4 5 11 20 15 27 59 61 48 37이다.

첫 분할(피벗 27)은 왼쪽에서 27보다 큰 값, 오른쪽에서 27보다 작은 값을 찾아 교환한다. 37과 20, 61과 15를 교환한 뒤 두 포인터가 엇갈리면 피벗을 11과 교환해 11 5 20 4 15 | 27 | 59 61 48 37이 된다.

두 번째 분할은 왼쪽 부분 11 5 20 4 15(피벗 11)에서 20과 4를 교환하고, 엇갈린 위치의 4와 피벗을 교환해 4 5 11 20 15가 된다. 오른쪽 부분은 아직 분할 전이므로 59 61 48 37 그대로이다.

  • 4 5 11 15 20 27 59 61 48 37은 20과 15의 순서까지 정리된 상태로, 이후 분할이 더 진행되어야 나온다.
  • 4 5 11 15 20 27 59 37 48 61은 오른쪽 부분이 분할 전인데도 순서가 바뀌어 있다.
  • 4 5 11 20 15 27 59 37 48 61도 왼쪽은 맞지만 분할 전인 오른쪽 부분의 61과 37이 자리를 바꾸어 있다.
문제 7
다음 재귀함수를 호출하는 C 프로그램의 실행 결과는?
#include <stdio.h>
void RecursiveFunc(int n) {
    if(n <= 0)  {
        printf("R-%d ", n);
        return;
    }
    printf("R-%d ", n);
    if(n%2 == 0)
        RecursiveFunc(n-2);
    else
        RecursiveFunc(n-1);

    printf("R-%d ", n);
}

int main(void)
{
    RecursiveFunc(3);
    return 0;
}
1R-3 R-2 R-0
2R-3 R-1 R-0 R-2 R-3
3R-3 R-2 R-0 R-2 R-3
4R-3 R-2 R-1 R-2 R-3
정답 및 해설

출력은 R-3 R-2 R-0 R-2 R-3이다.

RecursiveFunc(3)은 R-3을 출력하고 3이 홀수이므로 RecursiveFunc(2)를 호출한다. 2는 R-2를 출력하고 짝수이므로 RecursiveFunc(0)을 호출하며, 0은 기저 조건(n <= 0)에 걸려 R-0만 출력하고 반환한다.

복귀하면서 재귀 호출 뒤의 printf가 실행되어 RecursiveFunc(2)가 R-2, RecursiveFunc(3)이 R-3을 차례로 출력한다.

  • R-3 R-2 R-0은 재귀 호출 뒤에 있는 복귀 시 출력문을 빠뜨린 것이다.
  • R-3 R-1 R-0 R-2 R-3은 홀수 3에서 n-1인 2가 아니라 1로 넘어간 것으로 추적한 결과다.
  • R-3 R-2 R-1 R-2 R-3은 짝수 2에서 n-2인 0이 아니라 1로 넘어간 것으로 추적한 결과다.
문제 8
다음은 병합 정렬(merge sort) 알고리즘을 구현한 파이썬 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
sorted = []

def merge_sort(arr, left, right):
    if left<right:
        middle=(left+right)//2
        merge_sort(arr, left, middle)
        merge_sort(arr, middle+1, right)
        merge(arr, left, middle, right)

def merge(arr, left, middle, right):
    global sorted
    i=left
    j=middle+1
    k=( (가) )
    while i<=middle and ( (나) ):
        if arr[i]<=arr[j]:
            sorted.insert(k, arr[i])
            i=i+1
        else:
            sorted.insert(k, arr[j])
            j=j+1
        k=k+1

    if i>middle:
        sorted[k:k+right-j+1]=arr[j:right+1]
    else:
        sorted[k:k+middle-i+1]=arr[i:middle+1]

    arr[left:right+1]=sorted[left:right+1]
1left / j<=right
2left / k<=right
3middle / j<=right
4middle / k<=right
정답 및 해설

(가)는 left, (나)는 j<=right이다.

병합 결과를 쓰는 위치 k는 마지막에 sorted[left:right+1]을 arr로 복사하므로 구간 시작인 left에서 출발해야 한다. 병합 반복은 왼쪽 구간(i<=middle)과 오른쪽 구간(j<=right)에 모두 원소가 남아 있는 동안만 비교한다.

  • left / k<=right 조합은 오른쪽 구간이 먼저 소진돼도 k<=right가 참이어서 비교가 계속되고 arr[j]가 구간 밖을 읽는다.
  • middle / j<=right 조합은 병합 결과가 구간 중간부터 기록되어 복사 범위 sorted[left:right+1]과 어긋난다.
  • middle / k<=right 조합은 시작 위치와 반복 조건이 모두 틀렸다.
문제 9
다음은 C 언어 구조체를 이용하여 배열과 단순 연결 리스트로 큐를 표현한 것이다.
(가) 배열을 이용한 큐 구조체(나) 연결 리스트를 이용한 큐 구조체
typedef struct _Queue {
    int front;
    int rear;
    int numOfData;
    int queArr[50];
} QType;
typedef struct _node {
    int data;
    struct _node *next;
} Node;
typedef struct _Queue {
    Node *front;
    Node *rear;
    int numOfData;
} QType;

아래의 <조건>에 따라 (가), (나) 각각에 대해 Enqueue 함수를 세 번 호출하고 Dequeue 함수를 한 번 호출한 후, 큐에 할당된 메모리 공간의 크기(byte)를 계산한 값으로 바르게 연결한 것은?
<조 건>
○ 큐 변수는 QType q; 형태로 선언한다.
○ Enqueue 함수는 큐의 front에 데이터를 추가하는 함수로 함수 원형은 void Enqueue(QType *q, int value)이다.
○ Dequeue 함수는 큐의 rear에서 데이터를 삭제하는 함수이며, 함수 원형은 void Dequeue(QType *q)이다.
○ int형 자료의 경우 4바이트, 포인터형 자료의 경우 8바이트의 메모리 공간을 사용한다.
○ Enqueue와 Dequeue 함수에서는 배열 및 연결 리스트 특성에 맞게 필요한 메모리를 할당ㆍ회수하는 동작이 적절히 일어난다.
○ 연결 리스트에서 삭제 연산은 메모리 회수를 포함한다.
○ 구조체 변수를 메모리에 할당할 때 바이트 패딩 없이 할당한다.
124 / 44
224 / 56
3212 / 44
4212 / 56
정답 및 해설

(가)는 212바이트, (나)는 44바이트이다.

배열 큐는 선언 시 QType 크기가 고정되므로 연산과 관계없이 int 3개와 int 배열 50칸으로 4×53=2124 \times 53 = 212바이트이다.

연결 리스트 큐는 QType(포인터 2개 + int 1개) 8×2+4=208 \times 2 + 4 = 20바이트에, 노드(int + 포인터) 4+8=124 + 8 = 12바이트가 남은 노드 수만큼 더해진다. 세 번 삽입·한 번 삭제 후 노드는 2개이므로 20+12×2=4420 + 12 \times 2 = 44바이트이다.

  • 24바이트는 배열 큐의 크기가 될 수 없다. 배열 큐는 삽입 횟수와 관계없이 50칸 배열을 처음부터 포함한다.
  • 56바이트는 삭제된 노드의 메모리 회수를 반영하지 않고 노드 3개분을 더한 값이다.
문제 10
다음 C 프로그램의 실행 결과는? (단, 2차원 배열의 경우 행 우선으로 메모리에 저장된다)
#include <stdio.h>
int main(void)
{
    int i, j, test[3][4];
    for(i=0; i<3; i++)
        for(j=0; j<4; j++)
            test[i][3-j]=i*4+j;
    printf("%d ", *(*(test+1)+5));
}
15
26
39
410
정답 및 해설

출력값은 10이다.

test[i][3-j]=i*4+j는 각 행을 거꾸로 채우므로 배열은 행 0: 3 2 1 0, 행 1: 7 6 5 4, 행 2: 11 10 9 8이 된다.

*(test+1)은 행 1의 시작 주소이고 여기에 5를 더하면, 행 우선 저장에서 선형 위치 1×4+5 = 9인 test[2][1]을 가리킨다. 그 값은 10이다.

  • 9는 값이 아니라 선형 위치를 그대로 답한 것이다.
  • 6은 행 1 안의 test[1][1] 값으로, 오프셋 5가 다음 행으로 넘어간다는 점을 놓친 것이다.
  • 5도 행 1 안의 test[1][2] 값으로 같은 착오다.
문제 11
다음은 구조체 배열에서 최댓값을 찾아 출력하는 C 프로그램이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
#include <stdio.h>
typedef struct _data {
    int value;
} DataType;
DataType *max(DataType *a) {
    int i, max=a[0].value, index=0;
    for(i=0; i<5; i++)
        if(max<a[i].value) {
            max=a[i].value;
            index=i;
        }
    return ( (가) );
}

int main(void)
{
    int i;
    DataType data[5], *result;
    for(i=0; i<5; i++)
        scanf("%d", &data[i].value);

    result=max(data);
    printf("max=%d", ( (나) ));
    return 0;
}
1&a[index] / result->value
2&a[index] / result.value
3a[index] / result->value
4a[index] / (*result).value
정답 및 해설

(가)는 &a[index], (나)는 result->value이다.

max 함수의 반환형이 DataType *이므로 최댓값 원소의 주소를 반환해야 하고, 그 주소를 받은 result도 포인터이므로 멤버는 화살표 연산자로 접근한다.

  • &a[index] / result.value 조합은 포인터인 result에 점(.) 연산자를 써서 컴파일 오류가 난다.
  • a[index] / result->value 조합은 a[index]가 구조체 값 자체여서 포인터 반환형과 맞지 않는다.
  • a[index] / (*result).value 조합은 (나)가 result->value와 같아 옳지만, 반환값 a[index]가 포인터가 아니다.
문제 12
다음 전위 표기식을 후위 표기식으로 변환한 것은?
/ + a b – c d
1a b + c d - /
2a b c d + - /
3a b / c d + -
4a b c d / + -
정답 및 해설

후위 표기식은 a b + c d - /이다.

전위식 / + a b - c d는 연산자 /의 두 피연산자가 (+ a b)와 (- c d)이므로 중위식 (a+b) / (c-d)를 나타낸다. 각 부분을 후위로 바꾸면 a b +와 c d -이고, 마지막에 /를 붙인다.

  • a b c d + - /는 a / (b - (c+d))를 나타내는 다른 식이다.
  • a b / c d + -는 (a/b) - (c+d)를 나타낸다.
  • a b c d / + -는 a - (b + c/d)를 나타낸다.
문제 13
다음은 단순 연결 리스트를 이용하여 스택 자료구조를 구현한 파이썬 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
class Node:
    def __init__(self, data, next):
        self.data=data
        self.next=next

class MyStack:
    def __init__(self):
        self.top=None

    def push(self, data):
        ( (가) )
        self.top=n

    def pop(self):
        if self.top!=None:
            n=self.top
            ( (나) )
            return n.data
1n=Node(data, None) / self.top=n.next.next
2n=Node(data, None) / self.top=self.top.next
3n=Node(data, self.top) / self.top=n.next.next
4n=Node(data, self.top) / self.top=self.top.next
정답 및 해설

(가)는 n=Node(data, self.top), (나)는 self.top=self.top.next이다.

push는 새 노드의 next가 기존 top을 가리키게 만든 뒤 top을 새 노드로 바꿔야 연결이 유지된다. pop은 꺼낼 노드를 n에 보관하고 top을 바로 아래 노드로 옮긴다.

  • Node(data, None) / self.top=n.next.next 조합은 새 노드가 기존 스택과 끊기고, pop에서 노드 하나를 건너뛴다.
  • Node(data, None) / self.top=self.top.next 조합은 pop은 맞지만 push할 때마다 기존 스택이 연결에서 사라진다.
  • Node(data, self.top) / self.top=n.next.next 조합은 push는 맞지만 n이 top이므로 두 칸 아래로 이동해 원소 하나가 사라진다.
문제 14
그림과 같은 이중 연결 리스트(doubly linked list)에서 노드 X의 왼쪽에 노드 Y를 삽입할 때, 연산의 순서를 바르게 나열한 것은? (단, Llink는 왼쪽 노드를 가리키는 포인터 변수이고, Rlink는 오른쪽 노드를 가리키는 포인터 변수이다)

a. X -> Llink -> Rlink = Y
b. Y -> Llink = X -> Llink
c. X -> Llink = Y
d. Y -> Rlink = X

1a → c → b → d
2a → c → d → b
3b → c → a → d
4b → d → a → c
정답 및 해설

올바른 순서는 b → d → a → c이다.

X의 기존 왼쪽 노드 정보(X -> Llink)는 Y를 연결하는 데 계속 필요하므로, X -> Llink를 Y로 바꾸는 연산은 맨 마지막에 해야 한다.

먼저 Y의 두 링크를 채우고(Y의 왼쪽 = X의 기존 왼쪽 노드, Y의 오른쪽 = X), 기존 왼쪽 노드의 Rlink를 Y로 바꾼 뒤, 마지막으로 X의 Llink를 Y로 바꾼다.

  • a → c → b → d: c 직후 X -> Llink가 이미 Y이므로 b에서 Y의 왼쪽 링크가 자기 자신을 가리키게 된다.
  • a → c → d → b: 같은 이유로 b가 Y -> Llink = Y가 되어 기존 왼쪽 노드와의 연결이 끊긴다.
  • b → c → a → d: c 후에 a를 하면 X -> Llink가 Y이므로 Y -> Rlink만 Y로 바뀌고, 기존 왼쪽 노드의 Rlink는 여전히 X를 가리킨다.
문제 15
최소 1개 이상의 노드로 이루어진 원형 연결 리스트(circular linked list)에서 포인터 L이 리스트의 첫 번째 노드를 가리킨다고 할 때, 데이터의 값이 x인 노드를 탐색하여 반환하는 C 코드는?
1
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    while(p!=L) {
        if(p->data==x) return p;
        p=p->link;
    }
    return NULL;
}
2
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    while(p->link!=L) {
        if(p->data==x) return p;
        p=p->link;
    }
    return NULL;
}
3
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    do {
        if(p->data==x) return p;
        p=p->link;
    } while(p!=L);
    return NULL;
}
4
ListNode *searchCList(ListNode *L, int x) {
    ListNode *p=L;
    do {
        if(p->data==x) return p;
        p=p->link;
    } while(p->link!=L);
    return NULL;
}
정답 및 해설

첫 노드부터 검사한 뒤 p가 다시 L로 돌아오면 멈추는 do-while(p!=L) 형태가 옳다.

원형 연결 리스트는 마지막 노드의 link가 첫 노드 L을 가리키므로 p가 L로 돌아오면 한 바퀴를 다 돈 것이다. 시작점 p가 이미 L이므로 조건 검사를 본문 실행 뒤에 해야 모든 노드를 검사할 수 있다.

  • while(p!=L) 형태는 p=L에서 시작하므로 반복문이 한 번도 실행되지 않아 항상 NULL을 반환한다.
  • while(p->link!=L) 형태는 마지막 노드에 도달하면 검사 전에 반복이 끝나 마지막 노드를 놓친다.
  • do-while(p->link!=L) 형태도 p가 마지막 노드로 이동하는 순간 조건이 거짓이 되어 마지막 노드를 검사하지 못한다.
문제 16
0이 아닌 원소의 개수가 7개인 9 × 12 희소행렬에 대한 설명으로 옳지 않은 것은?
1행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하면, 108개의 배열 원소에 대한 공간이 필요하다.
20이 아닌 원소들에 대한 <행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현하면 14개의 배열 원소에 대한 공간이 필요하다.
3행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하는 것은 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어진다.
4<행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현한 희소행렬에 대하여 전치 행렬을 구하는 방법의 시간 복잡도는 최악의 경우, O(열의 수2×행의 수)O(\text{열의 수}^2 \times \text{행의 수})이다.
정답 및 해설

<행 번호, 열 번호, 값> 쌍 표현에 14개가 필요하다는 설명이 옳지 않다.

이 표현은 0이 아닌 원소 하나당 행 번호·열 번호·값 3개를 저장하므로 7×3=217 \times 3 = 21개가 필요하고, 행렬 크기·원소 수를 담는 머리 행까지 두면 24개가 된다. 14개는 원소당 2개만 센 값이다.

  • 행렬을 그대로 2차원 배열로 두면 9×12=1089 \times 12 = 108개 공간이 필요하다.
  • 108개 중 7개만 0이 아니므로 대부분의 공간이 낭비되어 기억 공간 활용도가 떨어진다.
  • 단순 전치 알고리즘은 열마다 모든 항을 훑어 열의 수 × 항의 수에 비례하고, 최악에는 항의 수가 행의 수 × 열의 수가 되므로 열의 수의 제곱 × 행의 수가 된다.
문제 17
다음 C 코드에서 heapify(a, 7)을 수행한 후 배열 a[]의 내용은? (단, 모든 배열 원소값은 양의 정수로 한정하고, －1은 연산 대상이 아니며, 0은 삭제된 값을 나타낸다)
int a[8]={-1, 1, 2, 3, 6, 4, 7, 5};

int heapify(int *a, int n) {
    int item=a[1], temp=a[n];
    int i=1, j=2;

    a[n]=0,  n=n-1;
    while(j<=n) {
        if(j<n && a[j]>a[j+1]) j++;
        if(temp<a[j]) break;
        else {
            a[i]=a[j];
            i=j;
            j=j*2;
        }
    }
    a[i]=temp;
    return item;
}
1
01234567
－12346570
2
01234567
－12436570
3
01234567
－12345670
4
01234567
－12435670
정답 및 해설

heapify(a, 7) 수행 후 배열은 -1, 2, 4, 3, 6, 5, 7, 0이다.

이 함수는 최소 힙의 루트 삭제이다. 루트 1을 item에 보관하고 마지막 원소 5를 temp로 꺼낸 뒤 a[7]=0, n=6으로 만들고, 루트 자리에서 더 작은 자식과 temp를 비교하며 내려간다.

i=1: 자식 a[2]=2, a[3]=3 중 작은 2가 temp 5보다 작으므로 a[1]=2, i=2
i=2: 자식 a[4]=6, a[5]=4 중 작은 4가 5보다 작으므로 a[2]=4, i=5
j=10 > n이므로 종료하고 a[5]=5를 저장한다.

  • -1, 2, 3, 4, 6, 5, 7, 0은 a[2] 자리에 3이 올라가 있어, i=2에서 자식 6, 4 중 작은 4를 끌어올리는 과정과 맞지 않는다.
  • -1, 2, 3, 4, 5, 6, 7, 0은 완전히 정렬된 상태로, 한 경로만 따라 내려가는 삭제 연산의 결과가 아니다.
  • -1, 2, 4, 3, 5, 6, 7, 0은 temp 5가 a[4]에 들어간 형태로, 더 작은 자식 a[5]=4 쪽으로 내려가야 한다는 점과 맞지 않는다.
문제 18
다음 그래프는 AOE(Activity on Edge) 네트워크를 보여 준다. 정점의 숫자는 공정을 나타내고, 간선 위에 있는 aia_i는 작업을, 괄호 안의 숫자는 그 작업을 수행하는 데 필요한 최소한의 시간을 나타낼 때, 임계 경로의 길이는?

110
211
312
413
정답 및 해설

임계 경로의 길이는 12이며, 경로는 0 → 3 → 6 → 8(a2, a7, a10)이다.

각 정점의 가장 이른 발생 시각은 들어오는 간선 중 최댓값으로 구한다.
1: 5, 2: 3, 3: 4, 4: 3+1=4
5: max(5+2, 4+3)=7, 6: max(4+3, 4+5)=9, 7: 4+2=6

8: max(7+4, 9+3, 6+5)=max(11, 12, 11)=12

  • 10: 0 → 2 → 4 → 6 → 8(3+1+3+3)의 길이로, 가장 긴 경로가 아니다.
  • 11: 0 → 1 → 5 → 8이나 0 → 3 → 7 → 8의 길이로, 가장 긴 경로가 아니다.
  • 13: 13이 되는 경로는 존재하지 않는다.
문제 19
키 값 <2, 6, 3, 4, 5, 1, 7, 8>을 순서대로 삽입해서 레드 블랙 트리를 생성할 때, 단일 회전과 이중 회전이 발생하는 횟수를 바르게 나열한 것은?
11 / 1
21 / 2
32 / 1
42 / 2
정답 및 해설

단일 회전은 1회, 이중 회전은 2회 발생한다.

빨강으로 삽입한 노드의 부모가 빨강일 때, 삼촌이 빨강이면 색 변경만 하고 삼촌이 검정(NIL 포함)이면 회전한다. 삽입 노드·부모·조부모가 일직선이면 단일 회전, 꺾여 있으면 이중 회전이다.

3 삽입: 2 → 6(오른쪽) → 3(왼쪽)으로 꺾이고 삼촌이 없어 이중 회전, 3이 루트가 된다.
4 삽입: 부모 6과 삼촌 2가 모두 빨강이라 색 변경만 한다.
5 삽입: 6 → 4(왼쪽) → 5(오른쪽)로 꺾이고 삼촌이 없어 이중 회전, 5가 4와 6의 부모가 된다.
1·7 삽입: 1은 부모가 검정이라 그대로, 7은 삼촌 4가 빨강이라 색 변경만 한다.
8 삽입: 6 → 7 → 8이 오른쪽 일직선이고 삼촌이 없어 단일 회전한다.

  • 단일 1회·이중 1회로 보면 5 삽입 때의 꺾인 배치에서 일어나는 이중 회전을 빠뜨린 것이다.
  • 단일 2회·이중 1회로 보면 색 변경만으로 해결되는 삽입을 회전으로 센 것이고, 이중 회전도 하나 빠졌다.
  • 단일 2회·이중 2회로 보면 4나 7 삽입처럼 삼촌이 빨강인 경우를 회전으로 센 것이다.
문제 20
다음 이진 트리의 전체 노드 수를 계산하는 C 코드에서 (가)에 들어갈 내용은? (단, n은 최초에 이진 트리 내 루트 노드를 가리키는 포인터 변수이며, TNode는 이진 트리의 노드 구조를 나타낸다)
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
}TNode;

int count_node(TNode *n) {
    if(n==NULL) return 0;
    return ( (가) ) +count_node(n->right);
}
11
2n->data
3count_node(n->left)
41+count_node(n->left)
정답 및 해설

(가)에는 1+count_node(n->left)가 들어간다.

전체 노드 수 = 현재 노드 1개 + 왼쪽 서브트리 노드 수 + 오른쪽 서브트리 노드 수라는 재귀 정의를 그대로 옮긴 것이다. 빈 트리(NULL)는 0을 반환해 재귀가 끝난다.

  • 1만 두면 왼쪽 서브트리를 세지 않아 루트에서 오른쪽으로 이어진 노드만 센다.
  • n->data는 노드에 저장된 문자의 코드값을 더하므로 개수가 아니다.
  • count_node(n->left)만 두면 자기 자신을 세지 않아 모든 호출이 결국 0을 반환한다.
문제 21
다음 탐색 알고리즘을 이용하여 아래 리스트에서 키(key) 34를 찾을 경우, 필요한 반복 연산 횟수는? (단, low 변수에는 0, high 변수에는 15가 전달된다)
int a_search(int list[], int key, int low, int high) {
    int middle;
    while(low<=high) {
        middle=(low+high)/2;
        if(key==list[middle])
            return middle;
        else if(key>list[middle])
            low=middle+1;
        else
            high=middle-1;
    }
    return -1;
}

0123456789101112131415
261113182022272930343841424547
13
24
35
46
정답 및 해설

키 34는 반복 4회 만에 찾는다.

코드는 정렬된 리스트에 대한 이진 탐색이며, 반복마다 middle 값과 비교해 범위를 절반으로 줄인다.

1회: low=0, high=15 → middle=7, list[7]=27 < 34이므로 low=8
2회: low=8, high=15 → middle=11, list[11]=38 > 34이므로 high=10
3회: low=8, high=10 → middle=9, list[9]=30 < 34이므로 low=10
4회: low=10, high=10 → middle=10, list[10]=34로 탐색 성공

  • 3회째 비교 대상은 30이어서 아직 키를 찾지 못한 상태다.
  • 5회는 4회째에 return으로 반복이 끝나므로 나올 수 없다.
  • 6회는 원소 16개에 대한 이진 탐색의 최대 반복 수인 5회보다도 많다.
문제 22
버킷(bucket)이 13개이고 버킷당 슬롯(slot)이 1개인 해시 테이블에 키 값 <7, 20, 3, 19, 45>를 차례대로 저장하고자 한다. 다음 <조건>에 따라 아래 <해시 함수>를 이용하여 작동하는 이중 해싱(double hashing)에서, 마지막 키 값 45의 저장 위치는?
<조 건>
○ 버킷의 인덱스는 0부터 시작한다.
○ h(x)h(x)는 첫 번째 조사 위치를 결정하는 기본 해시 함수이다.
○ f(x)f(x)는 충돌 발생 시 조사 위치 간격을 결정하는 함수이다.
○ 하나의 키 값에 대한 해시 함수 연산 중 충돌이 1번 이상 발생할 경우 ii번째 충돌에 대응하여 hi(x)h_i(x)를 적용한다.

<해시 함수>
h(x)=x mod 13h(x) = x \bmod 13
f(x)=x mod 11f(x) = x \bmod 11
hi(x)=(h(x)+i×f(x)) mod 13h_i(x) = (h(x)+i \times f(x)) \bmod 13
15
27
38
411
정답 및 해설

키 45는 버킷 8에 저장된다.

앞의 키들을 먼저 배치한다.
7: h=7 → 버킷 7
20: h=7 충돌, f=9 → (7+9) mod 13 = 3
3: h=3 충돌, f=3 → (3+3) mod 13 = 6
19: h=6 충돌, f=8 → (6+8) mod 13 = 1

45: h=45 mod 13 = 6에서 충돌하고 f=45 mod 11 = 1이다. h1=(6+1) mod 13=7h_1 = (6+1) \bmod 13 = 7도 차 있으므로 h2=(6+2×1) mod 13=8h_2 = (6+2 \times 1) \bmod 13 = 8에 저장된다.

  • 버킷 7은 첫 재조사 위치지만 이미 키 7이 있다.
  • 버킷 5는 조사 순서 6 → 7 → 8에 나타나지 않는다.
  • 버킷 11도 조사 순서에 나타나지 않는다.
문제 23
다음 그래프에 대한 설명 중 옳은 것만을 모두 고르면?

ㄱ. 가장 긴 단순 경로의 길이는 4이다.
ㄴ. 진입차수가 진출차수보다 큰 정점은 1개이다.
ㄷ. 완전 그래프가 되기 위해 추가로 필요한 간선의 수는 10개이다.
ㄹ. 간선 <A, B>를 제거한 후 위상정렬을 수행하면 B, D, A, E, C, F 또는 B, D, A, C, E, F순으로 정점이 나열된다.

1ㄱ, ㄹ
2ㄴ, ㄷ
3ㄱ, ㄴ, ㄹ
4ㄴ, ㄷ, ㄹ
정답 및 해설

옳은 것은 ㄱ, ㄹ이다.

그래프의 간선은 A→B, A→C, A→E, B→D, D→A, D→E, D→F, C→F, E→F의 9개이다.

  • ㄱ(옳음): B→D→A→E→F처럼 길이 4인 단순 경로가 있다. C와 E는 모두 F로만 나가므로 두 정점을 한 경로에 함께 담을 수 없어 길이 5(정점 6개)는 불가능하다.
  • ㄴ(틀림): 진입차수가 진출차수보다 큰 정점은 E(진입 2, 진출 1)와 F(진입 3, 진출 0)의 2개이다.
  • ㄷ(틀림): 정점 6개의 완전 방향 그래프는 간선 30개로 21개를 더해야 하고, 무방향으로 보아도 15개 중 9쌍이 이미 연결되어 있어 6개가 필요하다. 어느 쪽도 10개가 아니다.
  • ㄹ(옳음): A→B를 지우면 진입차수 0인 B부터 B, D, A 순으로 나오고, 그다음 C와 E가 동시에 진입차수 0이 되어 어느 쪽을 먼저 놓아도 되며 마지막이 F이다.
문제 24
무방향 그래프(undirected graph) G의 인접 행렬(adjacent matrix) 표현을 C 언어의 2차원 배열을 이용하여 다음과 같이 구현했다. 그래프 G의 정점(vertex)이 0, 1, 2, 3, 4, 5, 6의 숫자로 표현될 때, 무방향 그래프 G의 그림으로 옳은 것은?
int G[7][7]={
                { 0, 1, 1, 0, 0, 0, 0 },
                { 1, 0, 1, 1, 0, 0, 0 },
                { 1, 1, 0, 1, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 0 },
                { 0, 0, 1, 1, 1, 0, 1 },
                { 0, 0, 0, 0, 0, 1, 0 }
        };

1[그림]
2[그림]
3[그림]
4[그림]
정답 및 해설

올바른 그림은 간선 0-1, 0-2, 1-2, 1-3, 2-3, 2-5, 3-5, 4-5, 5-6의 9개로 이루어진 그래프이다.

무방향 그래프의 인접 행렬은 대칭이므로 상삼각 부분의 1만 읽으면 간선 목록이 된다. 특히 정점 4는 5와만, 정점 6도 5와만 연결되며 0과 3은 연결되지 않는다.

  • 0과 3이 연결되고 2-4, 3-6 간선이 있는 그림: 행렬의 0행 3열과 2행 4열이 0이므로 틀리다.
  • 2와 4가 연결되고 2-5 간선이 없는 그림: 2행 5열이 1, 2행 4열이 0이므로 틀리다.
  • 0-3, 3-4 간선이 있고 1-2, 2-5 간선이 없는 그림: 행렬과 여러 칸이 어긋난다.
문제 25
다음 방향 그래프(directed graph)에서 노드 A부터 시작하여 깊이 우선 탐색과 너비 우선 탐색을 수행하는 경우, 여섯 번째로 방문하는 노드의 쌍을 바르게 연결한 것은? (단, 노드 A는 첫 번째 방문 노드이고, 인접 노드가 다수일 경우 방문 순서는 알파벳순으로 하며, 탐색 과정에서 도달하지 못하는 경로는 고려하지 않는다)

1C / D
2D / I
3H / H
4I / H
정답 및 해설

여섯 번째 방문 노드는 깊이 우선 탐색이 I, 너비 우선 탐색이 H이다.

그래프의 간선은 A→B, A→D, B→G, C→A, C→H, D→I, E→C, E→F, F→B, G→H, I→H이며, A에서 도달 가능한 노드는 A, B, D, G, H, I뿐이다.

깊이 우선 탐색: A → B → G → H까지 내려간 뒤 되돌아와 D → I 순이므로 A, B, G, H, D, I.
너비 우선 탐색: A의 인접 B, D, 다음 단계로 B의 G와 D의 I, 마지막으로 H이므로 A, B, D, G, I, H.

  • C를 여섯 번째로 보는 경우: C로 들어오는 간선은 E→C뿐이라 A에서 C에 도달할 수 없다.
  • 깊이 우선에서 D를 여섯 번째로 보는 경우: D는 다섯 번째로 방문된다.
  • 깊이 우선에서 H를 여섯 번째로 보는 경우: H는 G 다음 네 번째로 방문된다.