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

21년 1회차

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

1 / 1

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

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

21년 1회차

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

문제 1

다음 탐색 알고리즘에 대한 설명으로 옳지 않은 것은?

int a_search(int list[], int key, int n) {
  int i;
  for(i=0; i<n; i++)
    if(list[i]==key) return i;
  return -1;
}

1탐색에 성공하면 키 값의 인덱스를 반환한다.

2최선의 경우, 시간 복잡도는 빅오 표기법으로 O(1)이다.

3최악의 경우, 시간 복잡도는 빅오 표기법으로 O(n)이다.

4평균적인 경우, 시간 복잡도는 빅오 표기법으로 O((n＋1)/2)이다.

정답 및 해설

평균 시간 복잡도를 O((n+1)/2)로 적은 설명이 옳지 않다. 빅오 표기법은 상수 계수를 버리므로 평균의 경우도 O(n)으로 써야 한다.

순차 탐색의 평균 비교 횟수가 (n+1)/2회인 것은 맞지만, 점근 표기로는 n에 비례할 뿐이다.

일치하는 원소를 만나면 return i로 그 인덱스를 반환하므로, 성공 시 인덱스를 반환한다는 설명은 옳다.
첫 원소가 key이면 비교 1회로 끝나므로 최선의 경우 O(1)은 옳다.
key가 맨 끝에 있거나 없으면 n회 비교하므로 최악의 경우 O(n)은 옳다.

문제 2

다음 C 코드의 실행 결과는?

#include <stdio.h>
int func (int n) {
  if(n <= 1) return 2;
  return func (n-1) + n;
}
int main (int argc, char* argv[]) {
  printf("%d\n", func (10) );
  return 0;
}

155

256

358

460

정답 및 해설

func(10)은 56을 출력한다. func(n)=func(n-1)+n이고 기저값 func(1)=2이다.

전개하면 $func(10) = 2 + (2 + 3 + \cdots + 10)$
$2 + 3 + \cdots + 10 = 54$ 이므로 결과는 $2 + 54 = 56$ 이다.

55는 기저값을 1로 잘못 보고 1부터 10까지 더한 값이다.

문제 3

다음 그래프에 대해 위상 정렬(topological sort) 알고리즘을 수행했을 때 생성되는 위상 순서 중 옳지 않은 것은?

10, 1, 2, 3, 4, 5, 6

20, 1, 3, 2, 4, 5, 6

30, 2, 4, 5, 1, 3, 6

40, 2, 5, 1, 3, 4, 6

정답 및 해설

위상 순서로 옳지 않은 것은 0, 2, 4, 5, 1, 3, 6이다.

위상 순서는 모든 간선 u→v 에 대해 u가 v보다 앞에 와야 한다. 정점 4는 1과 2 모두에서 들어오는 간선을 가지므로 1과 2가 출력된 뒤에야 나올 수 있는데, 이 순서는 1보다 4를 먼저 두어 간선 1→4를 어긴다.

0, 1, 2, 3, 4, 5, 6: 모든 정점이 선행 정점 뒤에 놓여 올바른 위상 순서이다.
0, 1, 3, 2, 4, 5, 6: 3은 1 뒤, 4는 1·2 뒤, 6은 3·4·5 뒤에 있어 올바르다.
0, 2, 5, 1, 3, 4, 6: 5는 2 뒤, 4는 1·2 뒤에 오며 6이 마지막이므로 올바르다.

문제 4

다음과 같이 배열을 이용하여 스택 자료구조를 정의하였다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

#define MAX 10
int stack[MAX];
int top = -1;
int push(int t) {
  if (top >= MAX - 1) {
    printf("\n Stack overflow.");
    return -1;
  }
  stack[ ㉠ ] = t;
  return t;
}
int pop(void) {
  if (top < 0) {
    printf("\n Stack underflow.");
    return -1;
  }
  return stack[ ㉡ ];
}

㉠　　㉡

1++top　　--top

2++top　　top--

3top++　　--top

4top++　　top--

정답 및 해설

㉠에는 ++top, ㉡에는 top--이 들어간다. top은 -1에서 시작해 항상 맨 위 원소의 위치를 가리킨다.

push는 top을 먼저 1 늘린 뒤 그 자리에 저장하고(전위 증가), pop은 현재 top의 값을 꺼낸 뒤 top을 줄인다(후위 감소).

㉠ ++top, ㉡ --top 조합은 pop이 top을 먼저 줄인 뒤 읽어 맨 위가 아닌 바로 아래 원소를 반환한다.
㉠ top++, ㉡ top-- 조합은 첫 push가 stack[-1]에 저장해 배열 범위를 벗어난다.
㉠ top++, ㉡ --top 조합은 push와 pop 양쪽 모두 접근 위치가 한 칸씩 어긋난다.

문제 5

차수가 4이고 높이가 4인 m원 탐색 트리가 가질 수 있는 노드의 최대 수는? (단, 루트 노드만 있는 경우 트리의 높이는 1이다)

121

251

385

4255

정답 및 해설

노드의 최대 수는 85개이다. 차수가 4인 m원 탐색 트리는 각 노드가 최대 4개의 자식을 가지므로 레벨마다 노드 수가 4배씩 늘어난다.

높이 4(루트만 있을 때 높이 1)이면 $1 + 4 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85$ 이다.

21은 높이 3까지만 더한 값(1+4+16)이다.
255는 노드 수 85에 노드당 최대 키 수 3을 곱한 키의 최대 개수로, 노드 수가 아니다.

문제 6

다음은 이진트리를 전위 순회하여 얻어진 전위표기식이다. 이 트리에 대한 설명으로 옳지 않은 것은?

＋ / * 6 2 － 3 1 * ＋ 5 8 － 7 4

1연산식의 최종 결과는 45이다.

2트리로 재구성하면 루트 노드는 ＋이다.

3트리로 재구성하여 중위 순회하면 6*2/3－1＋5＋8*7－4이다.

4트리로 재구성하여 후위 순회하면 62*31/－58＋74－*＋이다.

정답 및 해설

후위 순회 결과를 62*31/-58+74-*+로 적은 설명이 옳지 않다. 올바른 후위 순회는 6 2 * 3 1 - / 5 8 + 7 4 - * +로, 3 1 다음에 -가 먼저 와야 한다.

전위식을 재구성하면 루트 +의 왼쪽 서브트리는 (6*2)/(3-1), 오른쪽 서브트리는 (5+8)*(7-4)이다.

12/2=6, 13×3=39이므로 연산식의 최종 결과 45는 옳다.
전위식의 첫 기호가 루트이므로 루트 노드가 +라는 설명은 옳다.
중위 순회는 괄호 없이 왼쪽·루트·오른쪽 순으로 나열하므로 6*2/3-1+5+8*7-4가 되어 옳다.

문제 7

이진트리의 성질에 대한 설명으로 옳은 것은? (단, 루트 노드의 레벨은 0이고, 차수가 0인 노드의 개수는

n_0

, 차수가 1인 노드의 개수는

n_1

, 차수가 2인 노드의 개수는

n_2

로 한다)

1이진트리에서 단말노드의 개수를

n_0

이라 할 때,

n_2

와의 관계식

n_0 = n_2 + 1

을 만족한다.

2깊이가 k인 이진트리가 가질 수 있는 노드의 최대 개수는

2^{(k+1)}

이다(k ≥ 0).

3이진트리의 레벨 j에 있는 노드의 최대 개수는

2^{(j-1)}

개이다(j ≥ 0).

4이진트리의 전체 노드 개수는

n_0 + n_1 + n_2 - 1

개이다.

정답 및 해설

단말 노드 수와 차수 2인 노드 수의 관계식 $n_0 = n_2 + 1$ 이 옳다.

전체 노드 수를 n이라 하면 $n = n_0 + n_1 + n_2$ 이다.
루트를 뺀 모든 노드가 간선을 하나씩 받으므로 $n - 1 = n_1 + 2n_2$ 이다.
두 식을 연립하면 $n_0 = n_2 + 1$ 을 얻는다.

루트 레벨이 0일 때 깊이 k인 이진트리의 최대 노드 수는 $2^{k+1} - 1$ 이므로, 1을 빼지 않은 설명은 틀리다.
레벨 j의 최대 노드 수는 $2^{j}$ 개이므로 $2^{j-1}$ 은 틀리다.
전체 노드 수는 $n_0 + n_1 + n_2$ 이며 1을 뺄 이유가 없다.

문제 8

다음 C 언어 코드를 실행한 후 5번째 및 7번째 줄에 출력되는 문장으로 옳은 것은?

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to) {
  if( n==1 )
     printf("disk 1 from %c to %c\n", from, to);
  else {
     hanoi(n-1, from, to, tmp);
     printf("disk %d from %c to %c\n", n, from, to);
     hanoi(n-1, tmp, from, to);
  }
}

int main(int argc, char* argv[]) {
  hanoi(3, 'A', 'B', 'C');
}

5번째 줄　　7번째 줄

1disk 1 from B to A　　disk 1 from A to C

2disk 1 from C to B　　disk 2 from B to C

3disk 2 from A to B　　disk 3 from A to C

4disk 3 from A to C　　disk 2 from B to C

정답 및 해설

다섯째 줄은 disk 1 from B to A, 일곱째 줄은 disk 1 from A to C이다.

hanoi(3, A, B, C)는 원판 2개를 A→B로 옮기고(첫째~셋째 줄), disk 3을 A→C로 옮긴 뒤(넷째 줄), 원판 2개를 B→C로 옮긴다(다섯째~일곱째 줄).

전체 출력: disk 1 from A to C
disk 2 from A to B
disk 1 from C to B
disk 3 from A to C
disk 1 from B to A
disk 2 from B to C
disk 1 from A to C

disk 1 from C to B와 disk 2 from B to C는 각각 셋째 줄과 여섯째 줄 출력이다.
disk 2 from A to B와 disk 3 from A to C는 각각 둘째 줄과 넷째 줄 출력이다.
disk 3 from A to C와 disk 2 from B to C는 각각 넷째 줄과 여섯째 줄 출력이다.

문제 9

다음과 같이 이중연결리스트를 이용하여 큐 자료구조를 정의하였다. add는 큐의 삽입 알고리즘이고, delete는 큐의 삭제 알고리즘이다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

typedef struct _dnode {
  int key;
  struct _dnode *prev, *next;
} dnode;
dnode *head = (dnode*)malloc(sizeof(dnode));
dnode *tail = (dnode*)malloc(sizeof(dnode));
head->prev = head;   head->next = tail;
tail->prev = head;   tail->next = tail;

int add(int k) {
  dnode *t = (dnode*)malloc(sizeof(dnode));
  if (t == NULL) {
    printf("\n Out of memory.");
    return -1;
  }
  t->key = k;
  ( ㉠ )
  tail->prev = t;  t->next = tail;
  return k;
}

int delete(void) {
  dnode *t; int i;
  t = head->next;
  if (t == tail) {
    printf("\n Queue underflow.");
    return -1;
  }
  i = t->key;
  ( ㉡ )
  free(t);  return i;
}

1㉠ tail->prev = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next->prev = head;

2㉠ tail->prev->next = t; t->prev = tail->prev->next;
㉡ head->next = t->next; t->next->prev = head;

3㉠ tail->prev->next = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next = head;

4㉠ tail->prev->next = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next->prev = head;

정답 및 해설

㉠은 tail->prev->next = t; t->prev = tail->prev;, ㉡은 head->next = t->next; t->next->prev = head;이다.

add는 tail 바로 앞에 t를 끼우므로, tail->prev를 바꾸기 전에 기존 마지막 노드의 next와 t의 prev를 먼저 연결해야 한다. delete는 첫 노드 t를 빼고 head와 t의 다음 노드를 양방향으로 잇는다.

㉠에서 tail->prev = t를 먼저 실행하면 t->prev가 t 자신이 되고, 기존 마지막 노드의 next도 갱신되지 않는다.
㉠에서 t->prev = tail->prev->next로 쓰면 직전 문장으로 그 값이 이미 t이므로 t->prev가 자기 자신을 가리킨다.
㉡에서 t->next = head로 쓰면 새 첫 노드의 prev가 해제될 t를 계속 가리켜 역방향 연결이 깨진다.

문제 10

다항식에서 하나의 항을 표현하기 위해 다음과 같은 구조체 poly를 정의하였다. 이 구조체를 이용하여

A(x) = 3x^{14} + 2x^{8} + 1

과

B(x) = 8x^{14} - 4x^{9} + 10x^{3}

을 저장하는 데 필요한 최소의 메모리 용량(byte)은? (단, 정수(int)를 표현하는 데 2 byte를 사용하고, 실수(float)를 표현하는 데 4 byte를 사용하며, 다항식의 모든 항은 poly 구조체를 이용하여 저장한다)

struct poly{
    int exp;
    float coef;
};

122

224

336

438

정답 및 해설

필요한 최소 메모리는 36 byte이다. 0이 아닌 항만 poly 구조체로 저장하면 A(x) 3개, B(x) 3개로 모두 6개 항이다.

구조체 1개: $2 + 4 = 6\,\mathrm{byte}$
전체: $6 \times 6 = 36\,\mathrm{byte}$

24는 계수(float)만 6개 저장한 크기로, 지수(int)를 빠뜨린 값이다.

문제 11

다음은 행렬 연산을 하는 C 코드와 transpose함수 호출 후 행렬의 상태이다. ㉠에 들어갈 코드로 옳은 것은?

#include <stdio.h>
#define R 3
#define C 3
void transpose(int A[R][C], int B[R][C]) {
  for(int r = 0; r < R; r++)
   for(int c = 0; c < C; c++)
     ( ㉠ )
}
int main(int argc, char* argv[]) {
  int array1[R][C] = {{1,2,3},{4,5,6},{7,8,9}};
  int array2[R][C] = {0};
  transpose(array1, array2);
  return 0;
}
transpose함수 호출 후 행렬의 상태:
         1 2 3                 1 4 7
array1:  4 5 6       array2:  2 5 8
         7 8 9                 3 6 9

1A[c][r] = B[c][r];

2B[c][r] = A[c][r];

3A[c][r] = B[r][c];

4B[c][r] = A[r][c];

정답 및 해설

㉠에는 B[c][r] = A[r][c];가 들어간다. 전치 행렬은 원래 행렬의 행과 열을 맞바꾼 것이므로 A의 (r, c) 원소를 B의 (c, r) 위치에 옮긴다.

예를 들어 A[0][1]=2가 B[1][0]에 들어가 array2의 둘째 행 첫 값이 2가 된다.

A[c][r] = B[c][r];는 원본 A를 0으로 채워진 B로 덮어쓸 뿐 B는 그대로 0이다.
B[c][r] = A[c][r];는 같은 위치끼리 복사하므로 전치가 아니라 단순 복사가 된다.
A[c][r] = B[r][c];는 결과를 A에 쓰므로 array2가 바뀌지 않는다.

문제 12

열 우선(column major) 순서로 저장되는 3차원 배열 student[2][3][4]가 있을 때, 첫 번째 원소인 student[0][0][0]의 주소가 1024이면 student[1][2][2]의 주소는? (단, 배열 student의 각 원소의 크기는 24byte이고, 저장 순서는 [0][0][0],…,[0][2][3],[1][0][0],…,[1][2][3] 순서로 저장한다)

11168

21192

31504

41528

정답 및 해설

student[1][2][2]의 주소는 1504이다. 첫 첨자(면) 순으로 저장하되, 각 면의 3×4 행렬 안에서는 열 우선으로 저장되는 구조로 계산한다.

한 면의 원소 수: $3 \times 4 = 12$ , 면 안의 열 하나는 원소 3개
오프셋: $1 \times 12 + 2 \times 3 + 2 = 20$

주소: $1024 + 20 \times 24 = 1024 + 480 = 1504$

문제 13

다음 C 코드에서 함수 A와 B는 최대 공약수를 구하는 함수이다. 함수 B가 함수 A와 같은 결과를 출력하도록 ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

int A(int x, int y){
  int r;
  while (y != 0){
    r = x % y;  x = y;  y = r;
  }
  return x;
}

int B(int x, int y) {
  int r;
  if ( ㉠ ) return x;
  else {
    r = x % y;
    return ( ㉡ )
  }
}

㉠　　㉡

1y==0　　B(y, r);

2y==0　　B(r, y);

3y!=0　　B(y, r);

4y!=0　　B(r, y);

정답 및 해설

㉠은 y==0, ㉡은 B(y, r);이다. 함수 A의 반복문을 재귀로 옮긴 유클리드 호제법이다.

A는 y가 0이 될 때까지 (x, y) ← (y, x % y)로 갱신한 뒤 x를 반환한다. 따라서 재귀에서도 y가 0이면 x를 반환하고, 아니면 r = x % y를 구해 B(y, r)을 호출한다.

y==0과 B(r, y) 조합은 다음 호출에서 x % y가 다시 r이 되어 같은 호출이 반복되므로 끝나지 않는다.
y!=0과 B(y, r) 조합은 y가 0이 아니면 곧바로 x를 반환하고, y가 0이면 0으로 나누는 나머지 연산을 수행한다.
y!=0과 B(r, y) 조합은 종료 조건과 인자 순서가 모두 틀려 최대공약수를 구하지 못한다.

문제 14

C 언어에서 배열과 연결리스트에 대한 설명으로 옳지 않은 것은?

1일반적으로 두 개의 정수형 데이터 세트 {1,2,3}과 {4,5,6,7,8}을 합병하여 {1,2,3,4,5,6,7,8}로 만드는 연산을 수행할 경우, 두 데이터 세트의 자료구조를 연결리스트로 만들면, 정수형 배열로 만드는 것보다 시간 복잡도를 낮게 구현할 수 있다.

2일반적으로 정수형 데이터 세트 {1,2,3,4}를 {4,1,2,3}으로 변경하는 연산을 수행할 경우, 해당 데이터 세트의 자료구조를 연결리스트로 만들면, 정수형 배열로 만드는 것보다 더 빠르게 수행시킬 수 있다.

3일반적으로 정수형 데이터 세트 {1,2,3,4}를 {2,3,4,5}로 각 요소에 ＋1 연산을 수행할 경우, 데이터 세트의 자료구조를 연결 리스트로 만들면, 정수형 배열로 만드는 것보다 메모리를 적게 차지한다.

4일반적으로 정수형 데이터 세트 {1,2,3,4}를 {0,1,2,3,4}로 새로운 값을 추가하는 연산을 수행할 경우, 데이터 세트의 자료구조를 연결리스트로 만들면, 정수형 배열로 만드는 것보다 더 빠르게 연산을 수행시킬 수 있다.

정답 및 해설

각 요소에 +1을 하는 경우 연결리스트가 배열보다 메모리를 적게 차지한다는 설명이 옳지 않다. 연결리스트는 노드마다 다음 노드를 가리키는 포인터를 추가로 저장하므로 같은 개수의 정수를 담으면 배열보다 메모리를 더 쓴다.

대신 연결리스트는 삽입·연결·재배치를 포인터 변경만으로 처리할 수 있어, 원소 이동이나 복사가 필요한 배열보다 유리하다.

두 집합의 합병은 앞 리스트의 마지막 노드를 뒤 리스트의 첫 노드에 연결하면 되지만 배열은 원소를 새 공간에 복사해야 하므로, 연결리스트 쪽이 시간 복잡도가 낮다.
{1,2,3,4}를 {4,1,2,3}으로 바꾸는 것은 마지막 노드를 떼어 앞에 붙이면 되므로, 모든 원소를 한 칸씩 밀어야 하는 배열보다 빠르다.
맨 앞에 0을 추가하는 것은 새 노드를 head 앞에 연결하면 끝나지만 배열은 기존 원소를 모두 뒤로 옮겨야 하므로 연결리스트가 빠르다.

문제 15

다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것은?

<조 건>
○ LSD(Least Significant Digit)는 가장 낮은 자릿수이고, MSD(Most Significant Digit)는 가장 높은 자릿수이다. 135의 경우 LSD 위치의 값은 5이고 MSD 위치의 값은 1이다.
○ 버킷은 10개 큐로 구현한다.
○ list는 배열로 구현하며 초깃값은 (437, 125, 85, 7, 632, 194)이고 n은 6이다.

RadixSort(list, n) {
  for(d ← LSD의 위치에서 MSD위치로 한 자리씩 이동){
    for(i ← list의 0번째 원소부터 n-1까지 반복){
      list의 i번째 원소를 d의 위칫값에 따라 0번부터
      9번 사이의 버킷에 삽입한다.
    }
    for(b ← 0번 버킷부터 9번 버킷까지 반복){
      b번째 버킷에서 원소들을 순차적으로 읽어서 list에
      재배정한다.
    }
    ㉠list의 원소를 순서대로 출력한다.
  }
}

17　85　125　194　437　632

27　125　632　437　85　194

3632　194　125　85　437　7

4632　194　125　437　85　7

정답 및 해설

두 번째 출력은 7 125 632 437 85 194이다. LSD 기수 정렬은 일의 자리, 십의 자리 순으로 버킷에 나누었다가 같은 버킷 안의 순서를 유지하며 다시 모은다.

1회차(일의 자리): 632(2), 194(4), 125·85(5), 437·7(7)
→ 632 194 125 85 437 7
2회차(십의 자리): 7(0), 125(2), 632·437(3), 85(8), 194(9)
→ 7 125 632 437 85 194

632 194 125 85 437 7은 일의 자리만 처리한 첫 번째 출력이다.
7 85 125 194 437 632는 백의 자리까지 마친 세 번째(최종) 출력이다.
632 194 125 437 85 7은 어느 단계의 출력과도 일치하지 않는다.

문제 16

데이터 <1, 3, 5, 7, 8, 10, 9>를 차례대로 하나씩 입력받아 이진 탐색 트리와 AVL 트리를 각각 만들었을 때, 두 트리 간의 높이 차는?

정답 및 해설

두 트리의 높이 차는 4이다. 거의 정렬된 순서로 넣으면 이진 탐색 트리는 한쪽으로 치우치지만, AVL 트리는 회전으로 균형을 유지한다.

이진 탐색 트리: 1→3→5→7→8→10이 오른쪽으로 이어지고 9는 10의 왼쪽 자식이 되어 높이 7(루트 높이 1 기준)이다.

AVL 트리: 5 삽입 시 1에서, 8 삽입 시 5에서, 10 삽입 시 3에서 각각 RR 회전하고, 9 삽입 시 8에서 RL 회전한다. 최종 형태는 루트 7, 왼쪽 3(1, 5), 오른쪽 9(8, 10)로 높이 3이다.

따라서 높이 차는 $7 - 3 = 4$ 이다.

문제 17

초기 빈 상태의 트리에 다섯 개의 키 <1, 5, 3, 2, 6>를 차례대로 입력받아 디지털 탐색 트리를 만든 후, 전위 순회한 결과로 옳은 것은? (단, 각 키는 3비트 이진수로 표현한다)

11, 3, 2, 5, 6

21, 3, 5, 2, 6

31, 5, 2, 6, 3

41, 5, 3, 2, 6

정답 및 해설

전위 순회 결과는 1, 3, 2, 5, 6이다. 디지털 탐색 트리는 키를 노드에 저장하며, 내려갈 때마다 키의 비트를 최상위 비트부터 하나씩 보아 0이면 왼쪽, 1이면 오른쪽으로 간다.

1(001): 루트
5(101): 첫 비트 1 → 1의 오른쪽
3(011): 첫 비트 0 → 1의 왼쪽
2(010): 첫 비트 0으로 3에 도달, 둘째 비트 1 → 3의 오른쪽
6(110): 첫 비트 1로 5에 도달, 둘째 비트 1 → 5의 오른쪽

루트 → 왼쪽 서브트리(3, 2) → 오른쪽 서브트리(5, 6) 순으로 방문하면 1, 3, 2, 5, 6이다.

1, 3, 5, 2, 6은 같은 트리를 레벨 순으로 방문한 결과이다.
1, 5, 3, 2, 6은 키의 입력 순서 그대로이다.

문제 18

입력받은 수식의 괄호쌍이 맞는지 스택

S

를 이용하여 판단하는 알고리즘 DDD를 작성하였다. 수식에 존재하는 괄호는 소괄호 ‘()’이며, 다른 괄호는 수식에 존재하지 않는다. 수식의 길이는 n이며, 배열 X에 저장되어 입력된다. 알고리즘 DDD는 X를 입력받아 X에 저장된 수식의 괄호쌍이 맞으면 true, 그렇지 않으면 false를 반환하는 함수이다. ㉠～㉢에 들어갈 코드를 바르게 연결한 것은? (단,

S.push(c)

는 스택

S

에 문자

c

를 삽입하는 연산,

S.pop()

은

S

에서 삭제하는 연산,

S.empty()

는

S

가 비어 있으면 true, 아니면 false를 반환하는 함수이다)

Algorithm DDD(X, n)
Let S be an empty stack
for i←0 to n−1 do
  if X[i] = ‘(’ then
    S.push(X[i])
  else if X[i] = ‘)’ then
    if S.empty() then
      ( ㉠ )
    end if
    S.pop()
  end if
end for
if S.empty() then
  ( ㉡ )
else
  ( ㉢ )
end if

㉠　　㉡　　㉢

1return true　　return true　　return false

2return false　　return true　　return false

3return true　　return false　　return true

4return false　　return false　　return true

정답 및 해설

㉠ return false, ㉡ return true, ㉢ return false이다.

‘(’는 스택에 넣고 ‘)’를 만나면 짝이 되는 ‘(’를 꺼낸다. ‘)’를 만났는데 스택이 비어 있으면 짝 없는 닫는 괄호이므로 즉시 false이고, 끝까지 읽은 뒤 스택이 비어 있으면 true, 남아 있으면 닫히지 않은 ‘(’가 있으므로 false이다.

㉠ true, ㉡ true, ㉢ false 조합은 ‘)(’처럼 닫는 괄호가 먼저 나오는 식을 맞다고 판단한다.
㉠ true, ㉡ false, ㉢ true 조합은 판정이 정반대가 되어 올바른 식 ‘()’에 false를 반환한다.
㉠ false, ㉡ false, ㉢ true 조합은 스택이 비었을 때와 남았을 때의 판정을 뒤바꿔 ‘()’에 false, ‘((’에 true를 반환한다.

문제 19

다음과 같은 2－3－4 트리에 키 6과 7을 차례로 삽입한 이후의 트리 상태에 대한 설명으로 옳은 것은?

12－노드 1개, 3－노드 1개, 4－노드 2개로 구성된다.

2루트 노드는 4－노드이다.

3가장 왼쪽의 리프 노드는 4－노드이다.

4가장 오른쪽의 리프 노드는 4－노드이다.

정답 및 해설

삽입 후 가장 왼쪽 리프 [1, 3, 4]는 4-노드로 그대로 남는다.

키 6은 오른쪽 리프 [8, 9]에 들어가 [6, 8, 9]가 된다. 키 7을 삽입하면서 내려갈 때 4-노드 [6, 8, 9]를 만나므로 가운데 키 8을 부모로 올려 분할하고, 7은 [6]에 들어가 [6, 7]이 된다.

결과는 루트 [5, 8](3-노드), 리프 [1, 3, 4](4-노드)·[6, 7](3-노드)·[9](2-노드)이다.

2-노드 1개, 3-노드 1개, 4-노드 2개라는 설명: 실제로는 3-노드가 2개, 4-노드가 1개이다.
루트가 4-노드라는 설명: 루트는 키 5와 8을 가진 3-노드이다.
가장 오른쪽 리프가 4-노드라는 설명: 가장 오른쪽 리프는 키 9 하나뿐인 2-노드이다.

문제 20

다음 행렬은 그래프(graph)를 인접 행렬(adjacency matrix)로 나타낸 것이다. 이 그래프에서 솔린 알고리즘(Sollin algorithm)을 이용하여 최소 비용 신장 트리(minimum spanning tree)를 찾고자 한다. 알고리즘 수행 과정에서 나타나는 부분 그래프에 해당하지 않는 것은? (단, 부분 그래프는 간선의 집합으로 표현하며, 간선은 그래프에 포함된 두 정점 v, k에 대응하여 (v, k)의 형태로 표현한다)

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

1{ (0, 5) }

2{ (1, 3), (3, 4) }

3{ (3, 4) }

4{ (1, 2), (2, 6) }

정답 및 해설

간선 집합 {(1, 3), (3, 4)}는 솔린 알고리즘 수행 중 나타나지 않는다. 트리 {3, 4}에서 밖으로 나가는 최소 간선은 (1, 3)=12가 아니라 (4, 6)=11이어서, (1, 3)은 어느 단계에서도 선택되지 않는다.

1단계(각 정점의 최소 간선): 0·5 → (0, 5)=8, 1·2 → (1, 2)=5, 3·4 → (3, 4)=7, 6 → (2, 6)=6
→ 트리 {0, 5}, {1, 2, 6}, {3, 4}
2단계(각 트리의 최소 간선): {0, 5}와 {1, 2, 6} → (5, 6)=9, {3, 4} → (4, 6)=11
→ 최종: (0, 5), (1, 2), (2, 6), (3, 4), (5, 6), (4, 6)

{(0, 5)}는 1단계에서 정점 0과 5가 고른 간선으로 만들어진 부분 그래프다.
{(3, 4)}는 1단계에서 정점 3과 4가 고른 간선으로 만들어진 부분 그래프다.
{(1, 2), (2, 6)}은 1단계에서 정점 1·2·6이 고른 간선으로 이루어진 부분 그래프다.

문제 21

다음은 방향그래프를 인접 리스트로 표현한 것이다. 이 그래프에 대한 설명으로 옳지 않은 것은?

정점	인접 리스트
0	[1 \| 50] → [2 \| 45] → [3 \| 10 \| NULL]
1	[2 \| 10] → [3 \| 15 \| NULL]
2	[4 \| 30 \| NULL]
3	[0 \| 20] → [4 \| 15 \| NULL]
4	[1 \| 20] → [2 \| 35 \| NULL]
5	[4 \| 3 \| NULL]

1모든 사이클 경로는 (0,3,0), (2,4,2), (0,1,3,0), (1,2,4,1), (1,3,4,1), (0,2,4,1,3,0)이고, 그 경로에 각각 대응하는 길이는 2, 2, 3, 3, 3, 5이다.

2각 정점(0,1,2,3,4,5)에 각각 대응되는 진입차수는 1, 2, 3, 2, 3, 0이다.

3각 정점(0,1,2,3,4,5)에 각각 대응되는 인접한 정점의 집합은 {1,2}, {2,3}, {4}, {0,4}, {1,2}, {4,2}이다.

4각 정점(0,1,2,3,4,5)에서 각각 대응되는 진출차수는 3, 2, 1, 2, 2, 1이다.

정답 및 해설

옳지 않은 것은 인접한 정점의 집합에 대한 설명이다.

리스트를 간선으로 옮기면 0→1, 0→2, 0→3, 1→2, 1→3, 2→4, 3→0, 3→4, 4→1, 4→2, 5→4이다. 따라서 정점 0의 인접 정점은 {1, 2, 3}, 정점 5의 인접 정점은 {4}뿐인데 각각 {1, 2}, {4, 2}로 잘못 적었다.

사이클 경로 설명: 3→0 으로 돌아오는 사이클 3개와 0을 지나지 않는 사이클 3개가 제시된 6개와 정확히 일치하고, 길이(간선 수)도 2, 2, 3, 3, 3, 5로 맞다.
진입차수 설명: 각 정점으로 들어오는 간선 수가 1, 2, 3, 2, 3, 0으로 맞다.
진출차수 설명: 각 리스트의 노드 수가 3, 2, 1, 2, 2, 1로 맞다.

문제 22

승자 트리는 단말 노드(leaf node)에서부터 시작해서, 가장 작은 키 값을 갖는 노드(승자)를 찾아 부모로 올려서 루트 노드로부터 가장 작은 값을 찾아내는 방식이다. 승자 트리의 단말 노드에는 정렬된 배열(run)이 각각 달려 있고, 이 run에서 첫 번째 값을 읽어 가장 작은 값을 올려 내는 방식으로 모든 run을 비우면서 값을 정렬하게 된다. 8개의 run이 있는 아래 승자 트리에서 6, 8, 9 순서대로 3개의 레코드를 출력하고 난 뒤 run이 생략된 승자 트리의 형태로 옳은 것은?

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

3개 출력 후의 승자 트리는 루트 10, 둘째 레벨 10·11, 셋째 레벨 10·15·11·17, 단말 10·20·20·15·11·12·90·17인 형태이다.

값이 출력된 단말은 자기 run의 다음 값으로 교체된다. 6이 나간 자리는 15, 8이 나간 자리는 11, 9가 나간 자리는 12가 되고, 나머지 단말은 그대로이다.

형제끼리 작은 값을 올리면 min(10,20)=10, min(20,15)=15, min(11,12)=11, min(90,17)=17, 다음 레벨은 10과 11, 루트는 10이 된다.

루트가 11이고 첫 단말이 17인 트리: 단말 10은 아직 출력되지 않았으므로 17로 바뀔 수 없다.
루트 10에 다섯째 단말이 13인 트리: 8이 나간 run의 다음 값은 13이 아니라 11이다.
루트 12에 다섯째 단말이 16인 트리: 단말 10이 남아 있어야 하고, 11은 아직 출력되지 않았다.

문제 23

다음 코드는 C 언어를 이용하여 주어진 연결 리스트 구조의 데이터에 대한 삽입 정렬 함수를 구현한 것이다. ㉠～㉤에 들어갈 코드를 바르게 연결한 것은?

typedef struct _node {
  int data;
  struct _node *next;
}node;

void Insert(node **headRef, node *newNode) {
  if (*headRef == NULL ||
      (*headRef)->data >= newNode->data) {
    newNode->next = *headRef;
    *headRef = newNode;
  }
  else {
    node *current = *headRef;
    while (current->next != NULL &&
           current->next->data < newNode->data){
           ( ㉠ )
    }
    ( ㉡ )
    ( ㉢ )
  }
}

void Sort(node **headRef) {
  node *result = NULL, *current = *headRef;
  node *next;
  while (current!=NULL) {
    ( ㉣ )
    Insert(&result, current);
    ( ㉤ )
  }
  *headRef = result;
}

A : current->next = current;
B : current = current->next;
C : current->next = newNode;
D : next = current->next;
E : current->next = next;
F : current = next;
G : newNode->next = current->next;

㉠　　㉡　　㉢　　㉣　　㉤

1A　　D　　E　　F　　G

2B　　G　　C　　D　　F

3C　　E　　B　　A　　D

4E　　G　　B　　F　　A

정답 및 해설

㉠~㉤은 차례로 B, G, C, D, F이다. Insert는 newNode가 들어갈 자리의 직전 노드를 찾아 끼우고, Sort는 원래 리스트에서 노드를 하나씩 떼어 정렬된 result에 삽입한다.

Insert: 다음 노드 값이 newNode보다 작은 동안 current = current->next(B)로 전진한다. 멈춘 뒤 newNode->next = current->next(G)로 뒤쪽을 먼저 잇고, current->next = newNode(C)로 앞쪽을 연결한다.

Sort: Insert가 current->next를 바꾸므로 그 전에 next = current->next(D)로 다음 노드를 먼저 저장하고, 삽입 후 current = next(F)로 이동한다.

㉠에 current->next = current(A)를 넣으면 노드가 자기 자신을 가리켜 while문이 끝나지 않는다.
㉠에 current->next = newNode(C)를 넣으면 탐색 도중 연결을 덮어써 뒤쪽 노드를 잃는다.
㉠에 current->next = next(E)를 넣으면 Insert 안에 없는 변수 next를 쓰게 되어 성립하지 않는다.

문제 24

단순 무방향 그래프(simple undirected graph) G가 주어졌을 때, 정점(vertex)의 중복 방문을 허용하되, 간선(edge)의 중복은 허용하지 않는 경로(path)를 트레일(trail)이라고 한다. 그래프의 모든 간선들을 단 한 번씩만 통과하되 출발점과 도착점이 일치하지 않는 것을 오일러 트레일(Euler trail)이라고 할 때, 다음 그래프 중에서 오일러 트레일이 존재하지 않는 그래프는?

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

오일러 트레일이 없는 것은 왼쪽 세로선에 V자 두 개가 붙은 그래프이다.

연결 그래프에 출발점과 도착점이 다른 오일러 트레일이 있으려면 홀수 차수 정점이 정확히 2개여야 한다. 이 그래프는 왼쪽 위 꼭짓점(3), 왼쪽 가운데 정점(5), 왼쪽 아래 꼭짓점(3), 오른쪽 가운데 정점(3)으로 홀수 차수 정점이 4개이다.

바깥·안쪽 사각형 두 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이라 홀수 정점이 2개이다.
대각선이 들어간 3×3 격자 그래프: 위쪽 가운데 정점과 왼쪽 가운데 정점만 차수 5라 홀수 정점이 2개이다.
사각형 세 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이고 안쪽 교차점은 모두 차수 4라 홀수 정점이 2개이다.

문제 25

비어 있는 레드－블랙(red-black) 트리에 <19, 18, 2, 15, 6, 13, 7>을 순서대로 입력한 결과 생성되는 레드-블랙 트리로 옳은 것은? (단, 점선 노드는 레드 노드, 점선 링크는 레드 링크이며, 실선 노드는 블랙 노드, 실선 링크는 블랙 링크이고, 리프 노드에 연결된 사각형의 단말은 외부 노드를 의미한다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

완성되는 트리는 루트 18(블랙), 왼쪽 6(레드)·오른쪽 19(블랙), 6의 자식 2·13(블랙), 13의 자식 7·15(레드)인 형태이다.

19, 18 삽입 후 2가 들어오면 삼촌이 없어 우회전으로 18이 루트가 된다. 15 삽입 시 삼촌 19가 레드라 색만 바꾸고, 6 삽입 시 2–15–6 꺾임을 이중 회전해 6(블랙) 아래 2·15(레드)가 된다.

13 삽입 시 삼촌 2가 레드라 재색칠로 6이 레드, 2·15가 블랙이 되고, 7 삽입 시 15–13–7 일직선이므로 15에서 우회전해 13(블랙) 아래 7·15(레드)가 된다.

루트가 7인 트리: 7은 마지막에 들어와 회전이 15에서만 일어나므로 루트로 올라가지 않는다.
루트가 13인 완전 균형 트리: 2 삽입 때 18이 루트가 된 뒤로는 루트에서 회전이 일어나지 않아 18이 끝까지 루트로 남는다.
루트가 15인 트리: 15를 루트로 올리는 회전이 일어나지 않으며 7은 13의 왼쪽 레드 자식이 된다.

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

21년 1회차

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

문제 1

다음 탐색 알고리즘에 대한 설명으로 옳지 않은 것은?

int a_search(int list[], int key, int n) {
  int i;
  for(i=0; i<n; i++)
    if(list[i]==key) return i;
  return -1;
}

1탐색에 성공하면 키 값의 인덱스를 반환한다.

2최선의 경우, 시간 복잡도는 빅오 표기법으로 O(1)이다.

3최악의 경우, 시간 복잡도는 빅오 표기법으로 O(n)이다.

4평균적인 경우, 시간 복잡도는 빅오 표기법으로 O((n＋1)/2)이다.

정답 및 해설

평균 시간 복잡도를 O((n+1)/2)로 적은 설명이 옳지 않다. 빅오 표기법은 상수 계수를 버리므로 평균의 경우도 O(n)으로 써야 한다.

순차 탐색의 평균 비교 횟수가 (n+1)/2회인 것은 맞지만, 점근 표기로는 n에 비례할 뿐이다.

일치하는 원소를 만나면 return i로 그 인덱스를 반환하므로, 성공 시 인덱스를 반환한다는 설명은 옳다.
첫 원소가 key이면 비교 1회로 끝나므로 최선의 경우 O(1)은 옳다.
key가 맨 끝에 있거나 없으면 n회 비교하므로 최악의 경우 O(n)은 옳다.

문제 2

다음 C 코드의 실행 결과는?

#include <stdio.h>
int func (int n) {
  if(n <= 1) return 2;
  return func (n-1) + n;
}
int main (int argc, char* argv[]) {
  printf("%d\n", func (10) );
  return 0;
}

155

256

358

460

정답 및 해설

func(10)은 56을 출력한다. func(n)=func(n-1)+n이고 기저값 func(1)=2이다.

전개하면 $func(10) = 2 + (2 + 3 + \cdots + 10)$
$2 + 3 + \cdots + 10 = 54$ 이므로 결과는 $2 + 54 = 56$ 이다.

55는 기저값을 1로 잘못 보고 1부터 10까지 더한 값이다.

문제 3

다음 그래프에 대해 위상 정렬(topological sort) 알고리즘을 수행했을 때 생성되는 위상 순서 중 옳지 않은 것은?

10, 1, 2, 3, 4, 5, 6

20, 1, 3, 2, 4, 5, 6

30, 2, 4, 5, 1, 3, 6

40, 2, 5, 1, 3, 4, 6

정답 및 해설

위상 순서로 옳지 않은 것은 0, 2, 4, 5, 1, 3, 6이다.

0, 1, 2, 3, 4, 5, 6: 모든 정점이 선행 정점 뒤에 놓여 올바른 위상 순서이다.
0, 1, 3, 2, 4, 5, 6: 3은 1 뒤, 4는 1·2 뒤, 6은 3·4·5 뒤에 있어 올바르다.
0, 2, 5, 1, 3, 4, 6: 5는 2 뒤, 4는 1·2 뒤에 오며 6이 마지막이므로 올바르다.

문제 4

다음과 같이 배열을 이용하여 스택 자료구조를 정의하였다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

#define MAX 10
int stack[MAX];
int top = -1;
int push(int t) {
  if (top >= MAX - 1) {
    printf("\n Stack overflow.");
    return -1;
  }
  stack[ ㉠ ] = t;
  return t;
}
int pop(void) {
  if (top < 0) {
    printf("\n Stack underflow.");
    return -1;
  }
  return stack[ ㉡ ];
}

㉠　　㉡

1++top　　--top

2++top　　top--

3top++　　--top

4top++　　top--

정답 및 해설

㉠에는 ++top, ㉡에는 top--이 들어간다. top은 -1에서 시작해 항상 맨 위 원소의 위치를 가리킨다.

push는 top을 먼저 1 늘린 뒤 그 자리에 저장하고(전위 증가), pop은 현재 top의 값을 꺼낸 뒤 top을 줄인다(후위 감소).

㉠ ++top, ㉡ --top 조합은 pop이 top을 먼저 줄인 뒤 읽어 맨 위가 아닌 바로 아래 원소를 반환한다.
㉠ top++, ㉡ top-- 조합은 첫 push가 stack[-1]에 저장해 배열 범위를 벗어난다.
㉠ top++, ㉡ --top 조합은 push와 pop 양쪽 모두 접근 위치가 한 칸씩 어긋난다.

문제 5

차수가 4이고 높이가 4인 m원 탐색 트리가 가질 수 있는 노드의 최대 수는? (단, 루트 노드만 있는 경우 트리의 높이는 1이다)

121

251

385

4255

정답 및 해설

노드의 최대 수는 85개이다. 차수가 4인 m원 탐색 트리는 각 노드가 최대 4개의 자식을 가지므로 레벨마다 노드 수가 4배씩 늘어난다.

높이 4(루트만 있을 때 높이 1)이면 $1 + 4 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85$ 이다.

21은 높이 3까지만 더한 값(1+4+16)이다.
255는 노드 수 85에 노드당 최대 키 수 3을 곱한 키의 최대 개수로, 노드 수가 아니다.

문제 6

다음은 이진트리를 전위 순회하여 얻어진 전위표기식이다. 이 트리에 대한 설명으로 옳지 않은 것은?

＋ / * 6 2 － 3 1 * ＋ 5 8 － 7 4

1연산식의 최종 결과는 45이다.

2트리로 재구성하면 루트 노드는 ＋이다.

3트리로 재구성하여 중위 순회하면 6*2/3－1＋5＋8*7－4이다.

4트리로 재구성하여 후위 순회하면 62*31/－58＋74－*＋이다.

정답 및 해설

후위 순회 결과를 62*31/-58+74-*+로 적은 설명이 옳지 않다. 올바른 후위 순회는 6 2 * 3 1 - / 5 8 + 7 4 - * +로, 3 1 다음에 -가 먼저 와야 한다.

전위식을 재구성하면 루트 +의 왼쪽 서브트리는 (6*2)/(3-1), 오른쪽 서브트리는 (5+8)*(7-4)이다.

12/2=6, 13×3=39이므로 연산식의 최종 결과 45는 옳다.
전위식의 첫 기호가 루트이므로 루트 노드가 +라는 설명은 옳다.
중위 순회는 괄호 없이 왼쪽·루트·오른쪽 순으로 나열하므로 6*2/3-1+5+8*7-4가 되어 옳다.

문제 7

이진트리의 성질에 대한 설명으로 옳은 것은? (단, 루트 노드의 레벨은 0이고, 차수가 0인 노드의 개수는

n_0

, 차수가 1인 노드의 개수는

n_1

, 차수가 2인 노드의 개수는

n_2

로 한다)

1이진트리에서 단말노드의 개수를

n_0

이라 할 때,

n_2

와의 관계식

n_0 = n_2 + 1

을 만족한다.

2깊이가 k인 이진트리가 가질 수 있는 노드의 최대 개수는

2^{(k+1)}

이다(k ≥ 0).

3이진트리의 레벨 j에 있는 노드의 최대 개수는

2^{(j-1)}

개이다(j ≥ 0).

4이진트리의 전체 노드 개수는

n_0 + n_1 + n_2 - 1

개이다.

정답 및 해설

단말 노드 수와 차수 2인 노드 수의 관계식 $n_0 = n_2 + 1$ 이 옳다.

루트 레벨이 0일 때 깊이 k인 이진트리의 최대 노드 수는 $2^{k+1} - 1$ 이므로, 1을 빼지 않은 설명은 틀리다.
레벨 j의 최대 노드 수는 $2^{j}$ 개이므로 $2^{j-1}$ 은 틀리다.
전체 노드 수는 $n_0 + n_1 + n_2$ 이며 1을 뺄 이유가 없다.

문제 8

다음 C 언어 코드를 실행한 후 5번째 및 7번째 줄에 출력되는 문장으로 옳은 것은?

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to) {
  if( n==1 )
     printf("disk 1 from %c to %c\n", from, to);
  else {
     hanoi(n-1, from, to, tmp);
     printf("disk %d from %c to %c\n", n, from, to);
     hanoi(n-1, tmp, from, to);
  }
}

int main(int argc, char* argv[]) {
  hanoi(3, 'A', 'B', 'C');
}

5번째 줄　　7번째 줄

1disk 1 from B to A　　disk 1 from A to C

2disk 1 from C to B　　disk 2 from B to C

3disk 2 from A to B　　disk 3 from A to C

4disk 3 from A to C　　disk 2 from B to C

정답 및 해설

다섯째 줄은 disk 1 from B to A, 일곱째 줄은 disk 1 from A to C이다.

hanoi(3, A, B, C)는 원판 2개를 A→B로 옮기고(첫째~셋째 줄), disk 3을 A→C로 옮긴 뒤(넷째 줄), 원판 2개를 B→C로 옮긴다(다섯째~일곱째 줄).

전체 출력: disk 1 from A to C
disk 2 from A to B
disk 1 from C to B
disk 3 from A to C
disk 1 from B to A
disk 2 from B to C
disk 1 from A to C

disk 1 from C to B와 disk 2 from B to C는 각각 셋째 줄과 여섯째 줄 출력이다.
disk 2 from A to B와 disk 3 from A to C는 각각 둘째 줄과 넷째 줄 출력이다.
disk 3 from A to C와 disk 2 from B to C는 각각 넷째 줄과 여섯째 줄 출력이다.

문제 9

typedef struct _dnode {
  int key;
  struct _dnode *prev, *next;
} dnode;
dnode *head = (dnode*)malloc(sizeof(dnode));
dnode *tail = (dnode*)malloc(sizeof(dnode));
head->prev = head;   head->next = tail;
tail->prev = head;   tail->next = tail;

int add(int k) {
  dnode *t = (dnode*)malloc(sizeof(dnode));
  if (t == NULL) {
    printf("\n Out of memory.");
    return -1;
  }
  t->key = k;
  ( ㉠ )
  tail->prev = t;  t->next = tail;
  return k;
}

int delete(void) {
  dnode *t; int i;
  t = head->next;
  if (t == tail) {
    printf("\n Queue underflow.");
    return -1;
  }
  i = t->key;
  ( ㉡ )
  free(t);  return i;
}

1㉠ tail->prev = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next->prev = head;

2㉠ tail->prev->next = t; t->prev = tail->prev->next;
㉡ head->next = t->next; t->next->prev = head;

3㉠ tail->prev->next = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next = head;

4㉠ tail->prev->next = t; t->prev = tail->prev;
㉡ head->next = t->next; t->next->prev = head;

정답 및 해설

㉠은 tail->prev->next = t; t->prev = tail->prev;, ㉡은 head->next = t->next; t->next->prev = head;이다.

㉠에서 tail->prev = t를 먼저 실행하면 t->prev가 t 자신이 되고, 기존 마지막 노드의 next도 갱신되지 않는다.
㉠에서 t->prev = tail->prev->next로 쓰면 직전 문장으로 그 값이 이미 t이므로 t->prev가 자기 자신을 가리킨다.
㉡에서 t->next = head로 쓰면 새 첫 노드의 prev가 해제될 t를 계속 가리켜 역방향 연결이 깨진다.

문제 10

다항식에서 하나의 항을 표현하기 위해 다음과 같은 구조체 poly를 정의하였다. 이 구조체를 이용하여

A(x) = 3x^{14} + 2x^{8} + 1

과

B(x) = 8x^{14} - 4x^{9} + 10x^{3}

struct poly{
    int exp;
    float coef;
};

122

224

336

438

정답 및 해설

필요한 최소 메모리는 36 byte이다. 0이 아닌 항만 poly 구조체로 저장하면 A(x) 3개, B(x) 3개로 모두 6개 항이다.

구조체 1개: $2 + 4 = 6\,\mathrm{byte}$
전체: $6 \times 6 = 36\,\mathrm{byte}$

24는 계수(float)만 6개 저장한 크기로, 지수(int)를 빠뜨린 값이다.

문제 11

다음은 행렬 연산을 하는 C 코드와 transpose함수 호출 후 행렬의 상태이다. ㉠에 들어갈 코드로 옳은 것은?

#include <stdio.h>
#define R 3
#define C 3
void transpose(int A[R][C], int B[R][C]) {
  for(int r = 0; r < R; r++)
   for(int c = 0; c < C; c++)
     ( ㉠ )
}
int main(int argc, char* argv[]) {
  int array1[R][C] = {{1,2,3},{4,5,6},{7,8,9}};
  int array2[R][C] = {0};
  transpose(array1, array2);
  return 0;
}
transpose함수 호출 후 행렬의 상태:
         1 2 3                 1 4 7
array1:  4 5 6       array2:  2 5 8
         7 8 9                 3 6 9

1A[c][r] = B[c][r];

2B[c][r] = A[c][r];

3A[c][r] = B[r][c];

4B[c][r] = A[r][c];

정답 및 해설

㉠에는 B[c][r] = A[r][c];가 들어간다. 전치 행렬은 원래 행렬의 행과 열을 맞바꾼 것이므로 A의 (r, c) 원소를 B의 (c, r) 위치에 옮긴다.

예를 들어 A[0][1]=2가 B[1][0]에 들어가 array2의 둘째 행 첫 값이 2가 된다.

A[c][r] = B[c][r];는 원본 A를 0으로 채워진 B로 덮어쓸 뿐 B는 그대로 0이다.
B[c][r] = A[c][r];는 같은 위치끼리 복사하므로 전치가 아니라 단순 복사가 된다.
A[c][r] = B[r][c];는 결과를 A에 쓰므로 array2가 바뀌지 않는다.

문제 12

11168

21192

31504

41528

정답 및 해설

student[1][2][2]의 주소는 1504이다. 첫 첨자(면) 순으로 저장하되, 각 면의 3×4 행렬 안에서는 열 우선으로 저장되는 구조로 계산한다.

한 면의 원소 수: $3 \times 4 = 12$ , 면 안의 열 하나는 원소 3개
오프셋: $1 \times 12 + 2 \times 3 + 2 = 20$

주소: $1024 + 20 \times 24 = 1024 + 480 = 1504$

문제 13

다음 C 코드에서 함수 A와 B는 최대 공약수를 구하는 함수이다. 함수 B가 함수 A와 같은 결과를 출력하도록 ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?

int A(int x, int y){
  int r;
  while (y != 0){
    r = x % y;  x = y;  y = r;
  }
  return x;
}

int B(int x, int y) {
  int r;
  if ( ㉠ ) return x;
  else {
    r = x % y;
    return ( ㉡ )
  }
}

㉠　　㉡

1y==0　　B(y, r);

2y==0　　B(r, y);

3y!=0　　B(y, r);

4y!=0　　B(r, y);

정답 및 해설

㉠은 y==0, ㉡은 B(y, r);이다. 함수 A의 반복문을 재귀로 옮긴 유클리드 호제법이다.

A는 y가 0이 될 때까지 (x, y) ← (y, x % y)로 갱신한 뒤 x를 반환한다. 따라서 재귀에서도 y가 0이면 x를 반환하고, 아니면 r = x % y를 구해 B(y, r)을 호출한다.

y==0과 B(r, y) 조합은 다음 호출에서 x % y가 다시 r이 되어 같은 호출이 반복되므로 끝나지 않는다.
y!=0과 B(y, r) 조합은 y가 0이 아니면 곧바로 x를 반환하고, y가 0이면 0으로 나누는 나머지 연산을 수행한다.
y!=0과 B(r, y) 조합은 종료 조건과 인자 순서가 모두 틀려 최대공약수를 구하지 못한다.

문제 14

C 언어에서 배열과 연결리스트에 대한 설명으로 옳지 않은 것은?

정답 및 해설

대신 연결리스트는 삽입·연결·재배치를 포인터 변경만으로 처리할 수 있어, 원소 이동이나 복사가 필요한 배열보다 유리하다.

두 집합의 합병은 앞 리스트의 마지막 노드를 뒤 리스트의 첫 노드에 연결하면 되지만 배열은 원소를 새 공간에 복사해야 하므로, 연결리스트 쪽이 시간 복잡도가 낮다.
{1,2,3,4}를 {4,1,2,3}으로 바꾸는 것은 마지막 노드를 떼어 앞에 붙이면 되므로, 모든 원소를 한 칸씩 밀어야 하는 배열보다 빠르다.
맨 앞에 0을 추가하는 것은 새 노드를 head 앞에 연결하면 끝나지만 배열은 기존 원소를 모두 뒤로 옮겨야 하므로 연결리스트가 빠르다.

문제 15

다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것은?

RadixSort(list, n) {
  for(d ← LSD의 위치에서 MSD위치로 한 자리씩 이동){
    for(i ← list의 0번째 원소부터 n-1까지 반복){
      list의 i번째 원소를 d의 위칫값에 따라 0번부터
      9번 사이의 버킷에 삽입한다.
    }
    for(b ← 0번 버킷부터 9번 버킷까지 반복){
      b번째 버킷에서 원소들을 순차적으로 읽어서 list에
      재배정한다.
    }
    ㉠list의 원소를 순서대로 출력한다.
  }
}

17　85　125　194　437　632

27　125　632　437　85　194

3632　194　125　85　437　7

4632　194　125　437　85　7

정답 및 해설

1회차(일의 자리): 632(2), 194(4), 125·85(5), 437·7(7)
→ 632 194 125 85 437 7
2회차(십의 자리): 7(0), 125(2), 632·437(3), 85(8), 194(9)
→ 7 125 632 437 85 194

632 194 125 85 437 7은 일의 자리만 처리한 첫 번째 출력이다.
7 85 125 194 437 632는 백의 자리까지 마친 세 번째(최종) 출력이다.
632 194 125 437 85 7은 어느 단계의 출력과도 일치하지 않는다.

문제 16

데이터 <1, 3, 5, 7, 8, 10, 9>를 차례대로 하나씩 입력받아 이진 탐색 트리와 AVL 트리를 각각 만들었을 때, 두 트리 간의 높이 차는?

정답 및 해설

두 트리의 높이 차는 4이다. 거의 정렬된 순서로 넣으면 이진 탐색 트리는 한쪽으로 치우치지만, AVL 트리는 회전으로 균형을 유지한다.

이진 탐색 트리: 1→3→5→7→8→10이 오른쪽으로 이어지고 9는 10의 왼쪽 자식이 되어 높이 7(루트 높이 1 기준)이다.

따라서 높이 차는 $7 - 3 = 4$ 이다.

문제 17

11, 3, 2, 5, 6

21, 3, 5, 2, 6

31, 5, 2, 6, 3

41, 5, 3, 2, 6

정답 및 해설

루트 → 왼쪽 서브트리(3, 2) → 오른쪽 서브트리(5, 6) 순으로 방문하면 1, 3, 2, 5, 6이다.

1, 3, 5, 2, 6은 같은 트리를 레벨 순으로 방문한 결과이다.
1, 5, 3, 2, 6은 키의 입력 순서 그대로이다.

문제 18

입력받은 수식의 괄호쌍이 맞는지 스택

S

S.push(c)

는 스택

S

에 문자

c

를 삽입하는 연산,

S.pop()

은

S

에서 삭제하는 연산,

S.empty()

는

S

가 비어 있으면 true, 아니면 false를 반환하는 함수이다)

Algorithm DDD(X, n)
Let S be an empty stack
for i←0 to n−1 do
  if X[i] = ‘(’ then
    S.push(X[i])
  else if X[i] = ‘)’ then
    if S.empty() then
      ( ㉠ )
    end if
    S.pop()
  end if
end for
if S.empty() then
  ( ㉡ )
else
  ( ㉢ )
end if

㉠　　㉡　　㉢

1return true　　return true　　return false

2return false　　return true　　return false

3return true　　return false　　return true

4return false　　return false　　return true

정답 및 해설

㉠ return false, ㉡ return true, ㉢ return false이다.

㉠ true, ㉡ true, ㉢ false 조합은 ‘)(’처럼 닫는 괄호가 먼저 나오는 식을 맞다고 판단한다.
㉠ true, ㉡ false, ㉢ true 조합은 판정이 정반대가 되어 올바른 식 ‘()’에 false를 반환한다.
㉠ false, ㉡ false, ㉢ true 조합은 스택이 비었을 때와 남았을 때의 판정을 뒤바꿔 ‘()’에 false, ‘((’에 true를 반환한다.

문제 19

다음과 같은 2－3－4 트리에 키 6과 7을 차례로 삽입한 이후의 트리 상태에 대한 설명으로 옳은 것은?

12－노드 1개, 3－노드 1개, 4－노드 2개로 구성된다.

2루트 노드는 4－노드이다.

3가장 왼쪽의 리프 노드는 4－노드이다.

4가장 오른쪽의 리프 노드는 4－노드이다.

정답 및 해설

삽입 후 가장 왼쪽 리프 [1, 3, 4]는 4-노드로 그대로 남는다.

결과는 루트 [5, 8](3-노드), 리프 [1, 3, 4](4-노드)·[6, 7](3-노드)·[9](2-노드)이다.

2-노드 1개, 3-노드 1개, 4-노드 2개라는 설명: 실제로는 3-노드가 2개, 4-노드가 1개이다.
루트가 4-노드라는 설명: 루트는 키 5와 8을 가진 3-노드이다.
가장 오른쪽 리프가 4-노드라는 설명: 가장 오른쪽 리프는 키 9 하나뿐인 2-노드이다.

문제 20

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

1{ (0, 5) }

2{ (1, 3), (3, 4) }

3{ (3, 4) }

4{ (1, 2), (2, 6) }

정답 및 해설

{(0, 5)}는 1단계에서 정점 0과 5가 고른 간선으로 만들어진 부분 그래프다.
{(3, 4)}는 1단계에서 정점 3과 4가 고른 간선으로 만들어진 부분 그래프다.
{(1, 2), (2, 6)}은 1단계에서 정점 1·2·6이 고른 간선으로 이루어진 부분 그래프다.

문제 21

다음은 방향그래프를 인접 리스트로 표현한 것이다. 이 그래프에 대한 설명으로 옳지 않은 것은?

정점	인접 리스트
0	[1 \| 50] → [2 \| 45] → [3 \| 10 \| NULL]
1	[2 \| 10] → [3 \| 15 \| NULL]
2	[4 \| 30 \| NULL]
3	[0 \| 20] → [4 \| 15 \| NULL]
4	[1 \| 20] → [2 \| 35 \| NULL]
5	[4 \| 3 \| NULL]

1모든 사이클 경로는 (0,3,0), (2,4,2), (0,1,3,0), (1,2,4,1), (1,3,4,1), (0,2,4,1,3,0)이고, 그 경로에 각각 대응하는 길이는 2, 2, 3, 3, 3, 5이다.

2각 정점(0,1,2,3,4,5)에 각각 대응되는 진입차수는 1, 2, 3, 2, 3, 0이다.

3각 정점(0,1,2,3,4,5)에 각각 대응되는 인접한 정점의 집합은 {1,2}, {2,3}, {4}, {0,4}, {1,2}, {4,2}이다.

4각 정점(0,1,2,3,4,5)에서 각각 대응되는 진출차수는 3, 2, 1, 2, 2, 1이다.

정답 및 해설

옳지 않은 것은 인접한 정점의 집합에 대한 설명이다.

사이클 경로 설명: 3→0 으로 돌아오는 사이클 3개와 0을 지나지 않는 사이클 3개가 제시된 6개와 정확히 일치하고, 길이(간선 수)도 2, 2, 3, 3, 3, 5로 맞다.
진입차수 설명: 각 정점으로 들어오는 간선 수가 1, 2, 3, 2, 3, 0으로 맞다.
진출차수 설명: 각 리스트의 노드 수가 3, 2, 1, 2, 2, 1로 맞다.

문제 22

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

3개 출력 후의 승자 트리는 루트 10, 둘째 레벨 10·11, 셋째 레벨 10·15·11·17, 단말 10·20·20·15·11·12·90·17인 형태이다.

값이 출력된 단말은 자기 run의 다음 값으로 교체된다. 6이 나간 자리는 15, 8이 나간 자리는 11, 9가 나간 자리는 12가 되고, 나머지 단말은 그대로이다.

형제끼리 작은 값을 올리면 min(10,20)=10, min(20,15)=15, min(11,12)=11, min(90,17)=17, 다음 레벨은 10과 11, 루트는 10이 된다.

루트가 11이고 첫 단말이 17인 트리: 단말 10은 아직 출력되지 않았으므로 17로 바뀔 수 없다.
루트 10에 다섯째 단말이 13인 트리: 8이 나간 run의 다음 값은 13이 아니라 11이다.
루트 12에 다섯째 단말이 16인 트리: 단말 10이 남아 있어야 하고, 11은 아직 출력되지 않았다.

문제 23

typedef struct _node {
  int data;
  struct _node *next;
}node;

void Insert(node **headRef, node *newNode) {
  if (*headRef == NULL ||
      (*headRef)->data >= newNode->data) {
    newNode->next = *headRef;
    *headRef = newNode;
  }
  else {
    node *current = *headRef;
    while (current->next != NULL &&
           current->next->data < newNode->data){
           ( ㉠ )
    }
    ( ㉡ )
    ( ㉢ )
  }
}

void Sort(node **headRef) {
  node *result = NULL, *current = *headRef;
  node *next;
  while (current!=NULL) {
    ( ㉣ )
    Insert(&result, current);
    ( ㉤ )
  }
  *headRef = result;
}

A : current->next = current;
B : current = current->next;
C : current->next = newNode;
D : next = current->next;
E : current->next = next;
F : current = next;
G : newNode->next = current->next;

㉠　　㉡　　㉢　　㉣　　㉤

1A　　D　　E　　F　　G

2B　　G　　C　　D　　F

3C　　E　　B　　A　　D

4E　　G　　B　　F　　A

정답 및 해설

Sort: Insert가 current->next를 바꾸므로 그 전에 next = current->next(D)로 다음 노드를 먼저 저장하고, 삽입 후 current = next(F)로 이동한다.

㉠에 current->next = current(A)를 넣으면 노드가 자기 자신을 가리켜 while문이 끝나지 않는다.
㉠에 current->next = newNode(C)를 넣으면 탐색 도중 연결을 덮어써 뒤쪽 노드를 잃는다.
㉠에 current->next = next(E)를 넣으면 Insert 안에 없는 변수 next를 쓰게 되어 성립하지 않는다.

문제 24

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

오일러 트레일이 없는 것은 왼쪽 세로선에 V자 두 개가 붙은 그래프이다.

바깥·안쪽 사각형 두 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이라 홀수 정점이 2개이다.
대각선이 들어간 3×3 격자 그래프: 위쪽 가운데 정점과 왼쪽 가운데 정점만 차수 5라 홀수 정점이 2개이다.
사각형 세 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이고 안쪽 교차점은 모두 차수 4라 홀수 정점이 2개이다.

문제 25

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

완성되는 트리는 루트 18(블랙), 왼쪽 6(레드)·오른쪽 19(블랙), 6의 자식 2·13(블랙), 13의 자식 7·15(레드)인 형태이다.

루트가 7인 트리: 7은 마지막에 들어와 회전이 15에서만 일어나므로 루트로 올라가지 않는다.
루트가 13인 완전 균형 트리: 2 삽입 때 18이 루트가 된 뒤로는 루트에서 회전이 일어나지 않아 18이 끝까지 루트로 남는다.
루트가 15인 트리: 15를 루트로 올리는 회전이 일어나지 않으며 7은 13의 왼쪽 레드 자식이 된다.

정점	인접 리스트
0	[1 \| 50] → [2 \| 45] → [3 \| 10 \| NULL]
1	[2 \| 10] → [3 \| 15 \| NULL]
2	[4 \| 30 \| NULL]
3	[0 \| 20] → [4 \| 15 \| NULL]
4	[1 \| 20] → [2 \| 35 \| NULL]
5	[4 \| 3 \| NULL]

정점	인접 리스트
0	[1 \| 50] → [2 \| 45] → [3 \| 10 \| NULL]
1	[2 \| 10] → [3 \| 15 \| NULL]
2	[4 \| 30 \| NULL]
3	[0 \| 20] → [4 \| 15 \| NULL]
4	[1 \| 20] → [2 \| 35 \| NULL]
5	[4 \| 3 \| NULL]

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0

정점	0	1	2	3	4	5	6
0	0	20	15	∞	∞	8	∞
1	20	0	5	12	∞	∞	∞
2	15	5	0	25	35	28	6
3	∞	12	25	0	7	∞	∞
4	∞	∞	35	7	0	∞	11
5	8	∞	28	∞	∞	0	9
6	∞	∞	6	∞	11	9	0