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

26년 1회차

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

1 / 1

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

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

26년 1회차

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

문제 1

포인터 변수 L이 단순 연결 리스트의 첫 번째 노드를 가리킬 때, (가)～(다)를 수행하는 각 알고리즘의 시간 복잡도를 바르게 연결한 것은? (단,

n

은 리스트의 노드 개수를 나타낸다)

(가) L이 가리키는 리스트의 노드 순서를 역순으로 변환
(나) 새로운 노드를 L이 가리키는 리스트의 첫 번째 노드가 되도록 삽입
(다) L이 가리키는 리스트의 마지막 노드 삭제

(가) (나) (다)

O(1)

O(1)

O(1)

O(1)

O(n)

O(n)

O(n)

O(1)

O(n)

O(n)

O(n)

O(1)

정답 및 해설

역순 변환은 $O(n)$ , 첫 노드 삽입은 $O(1)$ , 마지막 노드 삭제는 $O(n)$ 이다.

역순 변환은 모든 노드의 링크를 한 번씩 뒤집어야 하므로 노드 수에 비례한다. 맨 앞 삽입은 새 노드의 link를 L로 두고 L을 새 노드로 바꾸면 끝난다.

마지막 노드를 지우려면 그 직전 노드의 link를 NULL로 바꿔야 하는데, 단순 연결 리스트는 뒤로 갈 수 없어 처음부터 끝까지 순회해야 한다.

세 연산 모두 상수 시간이라는 연결은 역순 변환과 마지막 노드 삭제가 전체 순회를 요구하므로 틀리다.
역순 변환을 상수 시간으로, 맨 앞 삽입을 선형 시간으로 본 연결은 두 연산의 비용을 뒤바꾼 것이다.
마지막 노드 삭제를 상수 시간으로 본 연결은 직전 노드를 찾는 순회를 빠뜨린 것이다.

문제 2

다음은 같은 기능을 수행하는 두 함수를 구현한 C 코드이다. 각 함수의 시간 복잡도를 바르게 연결한 것은?

double p1(double x, int n) {
   int i;
   double result = 1.0;

   for(i = 0; i < n; i++)
      result = result * x;
   return result;
}

double p2(double x, int n) {
   if(n == 0)
      return 1;
   else if((n % 2) == 0)
      return p2(x * x, n/2);
   else
      return x * p2(x * x, (n - 1)/2);
}

p1 함수 p2 함수

O(n)

O(1)

O(n)

O(\log n)

O(2^n)

O(n^2)

O(\log n)

O(n\log n)

정답 및 해설

p1은 $O(n)$ , p2는 $O(\log n)$ 이다.

p1은 for문이 $n$ 번 돌며 곱셈을 반복한다. p2는 호출마다 지수를 절반( $n/2$ 또는 $(n-1)/2$ )으로 줄이는 분할 정복 거듭제곱이라 호출 깊이가 $\log_2 n$ 에 비례한다.

p2를 상수 시간으로 본 연결은 지수가 0이 될 때까지 재귀가 반복되는 점을 무시한 것이다.
$O(2^n)$ · $O(n^2)$ 연결은 두 함수 모두 과대평가한 것이다.
$O(\log n)$ · $O(n\log n)$ 연결은 단순 반복인 p1을 과소평가하고 p2를 과대평가한 것이다.

문제 3

다음은 이중 연결 리스트(doubly linked list)를 구현한 C 코드이다. 노드 삭제 함수의 빈칸에 들어갈 내용으로 옳은 것은?

typedef int element;
typedef struct DListNode {
   element data;
   struct DListNode *llink;
   struct DListNode *rlink;
} DListNode;
DListNode *head = NULL;

void init() {
   head = (DListNode*)malloc(sizeof(DListNode));
   head->llink = head->rlink = head;
}

void dinsert(DListNode *inode, DListNode *inserted) {
   inserted->llink = inode;
   inserted->rlink = inode->rlink;
   inode->rlink->llink = inserted;
   inode->rlink = inserted;
}

void ddelete(DListNode *removed) {
   if(removed == head) return;
   removed->llink->rlink = removed->rlink;
   [                  ]
   free(removed);
}

1removed->rlink->llink = removed->llink;

2removed->rlink->llink = removed->rlink;

3removed->llink = removed->rlink->llink;

4removed->rlink = removed->rlink->llink;

정답 및 해설

빈칸에는 removed->rlink->llink = removed->llink;가 들어간다.

이중 연결 리스트에서 노드를 떼어 내려면 왼쪽 이웃의 rlink는 오른쪽 이웃을, 오른쪽 이웃의 llink는 왼쪽 이웃을 가리키도록 양방향 링크를 모두 갱신해야 한다. 앞 줄이 왼쪽 이웃의 rlink를 처리했으므로 빈칸은 오른쪽 이웃의 llink를 처리한다.

오른쪽 이웃의 llink에 removed->rlink를 넣으면 오른쪽 노드가 자기 자신을 가리키게 되어 역방향 연결이 끊긴다.
removed->llink = removed->rlink->llink;는 곧 해제될 노드 자신의 llink만 바꿀 뿐 오른쪽 이웃의 llink는 여전히 삭제된 노드를 가리킨다.
removed->rlink = removed->rlink->llink;도 해제될 노드 자신의 rlink만 바꾸므로 오른쪽 이웃의 역방향 링크가 갱신되지 않는다.

문제 4

2차원 배열 A[1:15][1:20]의 원소 A[10][8]에 대하여, 행 우선 순서 주소와 열 우선 순서 주소를 바르게 연결한 것은? (단, 첫 번째 원소 A[1][1]의 주소는 2000이고, 각 원소의 크기는 1바이트이다)
행 우선 순서 주소 열 우선 순서 주소

12114 2265

22182 2187

32187 2114

42265 2182

정답 및 해설

행 우선 주소는 2187, 열 우선 주소는 2114이다.

배열은 15행 20열이다. 행 우선: $2000 + (10-1)\times 20 + (8-1)$
$= 2000 + 180 + 7 = 2187$

열 우선: $2000 + (8-1)\times 15 + (10-1)$
$= 2000 + 105 + 9 = 2114$

2114·2265 연결은 열 우선 주소 2114를 행 우선 자리에 둔 것이다.
2182·2187 연결은 행 우선 주소 2187을 열 우선 자리에 둔 것이다.
2265·2182 연결은 두 값 모두 위 계산과 맞지 않는다.

문제 5

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

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

node *head = NULL;
node *tail = NULL;

void init() {
   head = (node*)malloc(sizeof(node));
   tail = (node*)malloc(sizeof(node));
   head->next = tail;
   tail->next = tail;
}

int push(int k) {
   node *t;
   if((t = (node*)malloc(sizeof(node))) == NULL) {
      printf("\n Out of memory");
      return -1;
   }
   t->key = k;
   [        (가)        ]
   head->next = t;
   return k;
}

int pop() {
   node *t;
   int i;
   if(head->next == tail) {
      printf("\n Stack underflow");
      return -1;
   }
   t = head->next;
   i = t->key;
   [        (나)        ]
   free(t);
   return i;
}

(가) (나)

1t->next = head; head->next = t->next;

2t->next = head->next; head->next = t->next;

3t->next = head->next; head = t->next;

4t->next = head->next; head->next = t;

정답 및 해설

(가)는 t->next = head->next;, (나)는 head->next = t->next;이다.

push는 새 노드 t를 head 바로 뒤에 끼워 넣으므로, 먼저 t가 기존 첫 노드를 가리키게 한 뒤 head->next = t를 수행한다. pop은 첫 노드 t를 떼어 내므로 head가 t의 다음 노드를 가리키게 한 뒤 t를 해제한다.

(가)를 t->next = head로 쓰면 새 노드가 더미 head를 가리켜 기존 노드들과의 연결이 끊긴다.
(나)를 head = t->next로 쓰면 더미 head 노드 자체가 바뀌어 스택 구조가 깨진다.
(나)에 head->next = t를 쓰면 곧 해제할 t를 계속 가리키게 되어 삭제가 되지 않는다.

문제 6

다음 C 언어로 작성된 함수들의 시간 복잡도에 대한 설명으로 옳은 것은?

void func1(int n) {
   for(int i = 0 ; i < 2 ; i++)
      for(int j = 0 ; j < n ; j++)
         printf("%d\n", j);
}

void func2(int n) {
   for(int i = 0 ; i < 100 ; i++)
      printf("%d\n", i);
}

void func3(int n) {
   if(n == 0)
      return;
   printf("%d\n", n);
      func3(n/2); ····················(가)
}

1func1 함수는 이중 for 반복문으로 구성되어 시간 복잡도는

O(n^2)

이다.

2func2 함수는 for 반복문으로 구성되어 시간 복잡도는

O(n)

이다.

3func3 함수는 for 반복문이 없어 시간 복잡도는

O(1)

이다.

4(가) 문장을 func2(n/2);으로 수정할 경우, func3 함수의 시간 복잡도는

O(1)

이다.

정답 및 해설

(가)를 func2(n/2)로 바꾸면 func3는 상수 시간 $O(1)$ 이 된다.

수정 후 func3는 출력 한 번과 func2 호출 한 번만 수행하는데, func2는 인자와 무관하게 100회만 반복하므로 전체가 상수 시간이다.

func1의 바깥 반복은 2회로 고정이라 $2n$ 번 출력, 즉 $O(n)$ 이지 $O(n^2)$ 가 아니다.
func2는 반복 횟수가 100으로 고정되어 $O(1)$ 이지 $O(n)$ 이 아니다.
func3는 반복문이 없어도 $n$ 을 절반씩 줄이며 재귀하므로 $O(\log n)$ 이다.

문제 7

다음은 원형 연결 리스트의 메모리 구성이다. 메모리 주소 1500인 위치에 data와 link 항목 내용이 각각 F와 1400인 새 노드를 삽입할 때, 변경되는 내용으로 옳은 것은?

메모리 주소	data	link
1000	A	1300
1100	B	1400
1200	C	1000
1300	D	1100
1400	E	1200

1data 값이 A인 노드의 link 값을 1400으로 변경

2data 값이 B인 노드의 link 값을 1500으로 변경

3data 값이 C인 노드의 link 값을 1400으로 변경

4data 값이 E인 노드의 link 값을 1500으로 변경

정답 및 해설

새 노드는 B 노드와 E 노드 사이에 들어가므로 B 노드의 link를 1500으로 바꾼다.

link를 따라가면 A(1000)→D(1300)→B(1100)→E(1400)→C(1200)→A 순의 원형 리스트다. 새 노드 F의 link가 1400(E)이므로 F는 E 앞에 놓이고, 원래 E를 가리키던 B의 link만 1500으로 바꾸면 B→F→E가 된다.

A 노드의 link를 1400으로 바꾸면 D와 B가 리스트에서 빠지고 F는 연결되지도 않는다.
C 노드의 link를 1400으로 바꾸면 E와 C 사이에 작은 사이클이 생기고 F는 여전히 고립된다.
E 노드의 link를 1500으로 바꾸면 E→F→E 사이클이 생겨 C와 A 쪽 노드가 끊긴다.

문제 8

다음은 크기가 7인 배열로 구현된 원형 덱(deque)의 상태이다. 현재 상태에서 연산 1부터 연산 5까지 순서대로 수행하였을 때, 수행이 완료된 후 원형 덱의 상태는? (단, 현재 상태는 front ＝ 0, rear ＝ 3이다)

[0]	[1]	[2]	[3]	[4]	[5]	[6]
5	2	6	8

연산 1: 맨 뒤에 위치한 데이터 삭제
연산 2: 맨 앞에 위치한 데이터 삭제
연산 3: 맨 뒤에 데이터 3을 삽입
연산 4: 맨 앞에 데이터 1을 삽입
연산 5: 맨 앞에 데이터 4를 삽입

[0]	[1]	[2]	[3]	[4]	[5]	[6]
1	2	6	3			4

[0]	[1]	[2]	[3]	[4]	[5]	[6]
4	1	2	6	3

[0]	[1]	[2]	[3]	[4]	[5]	[6]
1	2	6	3	4

[0]	[1]	[2]	[3]	[4]	[5]	[6]
4	1	2	6			3

정답 및 해설

수행 후 덱은 [0]=1, [1]=2, [2]=6, [3]=3, [6]=4 상태가 된다.

front=0, rear=3을 각각 첫·마지막 원소 위치로 보고 차례로 추적한다.
뒤 삭제: 8 제거, rear=2
앞 삭제: 5 제거, front=1
뒤에 3 삽입: rear=3, [3]=3
앞에 1 삽입: front=0, [0]=1
앞에 4 삽입: front=(0-1+7) mod 7=6, [6]=4

[4]에 4가 놓인 상태는 앞쪽 삽입을 뒤쪽에 넣은 것이라 틀리다.
[0]부터 4, 1, 2, 6, 3이 차례로 놓인 상태는 원형으로 감기지 않고 원소를 오른쪽으로 밀어낸 것이다.
[6]에 3이 놓인 상태는 뒤쪽 삽입을 원형 앞쪽으로 넣은 것이라 틀리다.

문제 9

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

void function(int array[], int idx, int size) {
   for(int i = idx; i < size - 1; i++)
      array[i] = array[i + 1];
}

int main() {
   int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   function(array, 5, 10);
   function(array, 5, 10);

   for(int i = 0; i < 10; i++)
      printf("%d ", array[i]);
   printf("\n");

   return 0;
}

10 1 2 3 4 5 6 7 8 9

20 1 2 3 4 7 8 9 9 9

30 1 2 3 5 5 6 7 8 9

40 1 2 3 5 6 7 8 9 9

정답 및 해설

출력은 0 1 2 3 4 7 8 9 9 9이다.

function은 idx부터 한 칸씩 왼쪽으로 당겨 array[idx]를 지우는 효과를 내며, 마지막 칸은 그대로 남는다.
1회 후: 0 1 2 3 4 6 7 8 9 9
2회 후: 0 1 2 3 4 7 8 9 9 9

원래 배열 그대로라는 출력은 함수가 배열 원본을 수정한다는 점(배열 인자는 포인터 전달)을 놓친 것이다.
4가 사라지고 5가 두 번 나오는 출력은 시작 인덱스를 잘못 잡은 것이다.
5부터 9까지 한 칸만 당겨진 출력은 함수를 한 번만 호출한 경우이며, 시작 인덱스도 어긋난다.

문제 10

이진 탐색 트리의 모든 키를 오름차순으로 정렬한 결과를 일차원 배열 형식으로 출력하기 위해 사용할 수 있는 순회 알고리즘은? (단, 순회 알고리즘은 1회만 수행하고 별도의 정렬 알고리즘은 수행하지 않는다)

1중위 순회

2전위 순회

3후위 순회

4레벨 순회

정답 및 해설

정답은 중위 순회이다.

이진 탐색 트리는 왼쪽 서브트리 < 루트 < 오른쪽 서브트리를 만족하므로, 왼쪽 → 루트 → 오른쪽 순으로 방문하는 중위 순회가 키를 오름차순으로 낸다.

전위 순회는 루트를 왼쪽 서브트리보다 먼저 내므로 오름차순이 되지 않는다.
후위 순회는 루트를 마지막에 내므로 오름차순이 되지 않는다.
레벨 순회는 깊이 순으로 방문해 같은 레벨 안에서만 순서가 유지될 뿐 전체 정렬이 되지 않는다.

문제 11

정점의 개수가 n인 단순 그래프가 트리이기 위한 필요충분조건으로 옳지 않은 것은? (단, n은 3 이상의 정수이다)

1사이클이 없고 연결요소의 개수가 1이다.

2임의의 두 정점 사이에 존재하는 경로의 개수는 1이다.

3간선의 개수가 n－1이고, 차수가 1인 정점의 개수가 2 이상이다.

4사이클이 없지만, 인접하지 않은 임의의 두 정점 사이에 간선을 추가하면 사이클의 개수가 1이 된다.

정답 및 해설

옳지 않은 것은 “간선 n−1개이고 차수 1인 정점이 2개 이상”이라는 조건이다.

간선 수가 n−1이어도 연결성이나 비순환성이 보장되지 않으면 트리가 아니다. 예를 들어 정점 5개 중 3개로 삼각형(간선 3)을 만들고 나머지 2개를 간선 하나로 이으면 간선 4개, 차수 1인 정점 2개지만 사이클이 있고 연결되어 있지 않다.

사이클이 없고 연결요소가 하나라는 것은 트리의 정의 그 자체다.
임의의 두 정점 사이 경로가 정확히 하나라는 것도 트리의 동치 조건이다.
사이클이 없으면서 간선을 하나만 더해도 사이클이 생긴다는 것은 극대 비순환 그래프, 곧 트리의 동치 조건이다.

문제 12

다음과 같이 6개의 키값으로 구성된 4개의 입력 배열 데이터 (가)～(라)를 각각 순서대로 삽입하여 4개의 AVL 트리를 생성하였다. 생성된 모든 트리에 공통으로 존재하는 리프 노드 키값으로 옳은 것은?

(가)	4	1	2	8	5	9
(나)	1	2	8	5	9	4
(다)	9	8	4	2	1	5
(라)	9	8	1	5	4	2

정답 및 해설

네 AVL 트리에 공통인 리프 키는 9이다.

각각 삽입·회전을 추적한 결과다(루트(왼쪽, 오른쪽) 형식).
(가): 5(2(1, 4), 8(−, 9)) → 리프 1, 4, 9
(나): 5(2(1, 4), 8(−, 9)) → 리프 1, 4, 9
(다): 4(2(1, −), 8(5, 9)) → 리프 1, 5, 9
(라): 4(1(−, 2), 8(5, 9)) → 리프 2, 5, 9

네 트리 모두에 리프로 남는 키는 9뿐이다.

2는 (라)에서만 리프이고 나머지에서는 내부 노드다.
4는 (가)·(나)에서는 리프지만 (다)·(라)에서는 루트다.
5는 (다)·(라)에서는 리프지만 (가)·(나)에서는 루트다.

문제 13

선형 조사법(linear probing)을 사용하는 해시 테이블에서 버킷(bucket)을 삭제할 때, 빈 버킷(empty bucket)으로 비워 두지 않고 삭제했음을 표시하는 이유는? (단, 버킷 내 슬롯(slot) 수는 1이다)

11차 군집 현상이 발생하지 않게 한다.

2해시 테이블의 전체 크기를 자동으로 기존 크기의 두 배로 확장 시킨다.

3충돌로 인해 원래 해시 주소와는 다른 주소에 저장된 레코드에 대한 탐색이 가능하게 한다.

4해시 테이블에 저장된 모든 레코드의 키값이 항상 오름차순으로 정렬된 상태가 되도록 유지시킨다.

정답 및 해설

삭제 표시를 남기는 이유는 충돌로 다른 주소에 밀려 저장된 레코드를 계속 탐색할 수 있게 하기 위해서다.

선형 조사법의 탐색은 빈 버킷을 만나면 “없음”으로 종료한다. 중간 버킷을 그냥 비우면 그 뒤로 밀려 저장된 레코드에 도달하기 전에 탐색이 끊기므로, 삭제 표시를 두어 탐색은 건너가고 삽입은 재사용하게 한다.

1차 군집은 선형 조사 자체의 성질이라 삭제 표시로 막을 수 없다.
테이블 크기 확장(재해싱)은 적재율에 따른 별도 처리로 삭제 표시와 무관하다.
해시 테이블은 키 순서를 유지하는 구조가 아니므로 오름차순 정렬과 관계없다.

문제 14

다음 C 언어로 구현한 sort 함수에서 (가) 문장이 수행되는 횟수가 가장 작은 배열 arr의 입력내용은? (단, n ＝ 5이다)

void sort(int arr[], int n) {
   int i, key, j;
   for(i = 1; i < n; i++) {
      key = arr[i];
      j = i - 1;
      while(j >= 0 && arr[j] < key) {
         arr[j + 1] = arr[j]; ···········(가)
         j = j - 1;
      }
      arr[j + 1] = key;
   }
}

11, 2, 3, 4, 5

25, 3, 4, 7, 6

38, 3, 10, 7, 2

410, 9, 8, 7, 6

정답 및 해설

(가)가 가장 적게 수행되는 입력은 10, 9, 8, 7, 6이다.

조건이 arr[j] < key이므로 이 함수는 내림차순 삽입 정렬이고, (가)의 수행 횟수는 앞 원소가 뒤 원소보다 작은 쌍의 수와 같다.

1, 2, 3, 4, 5는 모든 쌍이 앞이 작아 10회로 최대다.
5, 3, 4, 7, 6은 (5,7)(5,6)(3,4)(3,7)(3,6)(4,7)(4,6)의 7회다.
8, 3, 10, 7, 2는 (8,10)(3,10)(3,7)의 3회다.
10, 9, 8, 7, 6은 이미 내림차순이라 0회다.

문제 15

단순 그래프의 인접 행렬 표현이 인접 리스트 표현보다 점근적으로 빠른 연산으로 옳은 것은? (단, 인접 행렬에서 임의의 정점 v의 행 또는 열의 접근 시간과 인접 리스트에서 임의의 정점 v의 인접 리스트의 접근 시간은 모두 상수이다)

1특정 정점의 차수 계산

2그래프 전체의 간선 개수 세기

3특정 정점에서 시작하는 너비 우선 탐색

4특정 두 정점 사이의 간선 존재 여부 확인

정답 및 해설

인접 행렬이 더 빠른 연산은 두 정점 사이의 간선 존재 여부 확인이다.

인접 행렬은 원소 하나만 보면 되어 $O(1)$ 이지만, 인접 리스트는 한 정점의 리스트를 훑어야 하므로 그 정점의 차수에 비례한다.

특정 정점의 차수 계산은 행렬에서 한 행 전체( $O(n)$ )를 봐야 하고 리스트는 차수만큼만 보면 된다.
전체 간선 개수 세기는 행렬이 $O(n^2)$ , 리스트가 $O(n+e)$ 로 리스트가 유리하다.
너비 우선 탐색도 행렬은 $O(n^2)$ , 리스트는 $O(n+e)$ 로 리스트가 유리하다.

문제 16

다음 그래프에 대한 깊이 우선 탐색(depth first search)을 수행할 때 가능한 정점들의 방문 순서는?

1A, B, F, C, D, E

2C, A, B, D, E, F

3D, F, E, B, A, C

4E, F, A, B, D, C

정답 및 해설

가능한 방문 순서는 D, F, E, B, A, C이다. 그림의 간선은 C→A, A→B, A→D, B→F, C→F, D→E, D→F, E→B, E→F이다.

D에서 출발해 F를 방문하면 F는 나가는 간선이 없어 D로 돌아오고, 다음 인접 정점 E를 방문한다. E→B로 B를 방문한 뒤 B의 인접 정점 F는 이미 방문했으므로 되돌아온다. D에서 도달할 수 없는 A, C는 새 시작 정점으로 차례로 방문하면 되므로 유효한 DFS 순서다.

A, B, F, C, D, E: F에서 A로 되돌아오면 A의 미방문 인접 정점 D를 먼저 방문해야 하는데 C로 넘어가므로 불가능하다.
C, A, B, D, E, F: B의 인접 정점 F가 미방문인데 B에서 F로 가지 않고 D로 넘어가므로 불가능하다.
E, F, A, B, D, C: F에서 E로 되돌아오면 E의 미방문 인접 정점 B를 먼저 방문해야 하는데 A로 넘어가므로 불가능하다.

문제 17

2－3 트리에 대한 설명으로 옳은 것은?

12－3 트리가 항상 완전 균형 트리를 유지하는 것은 아니다.

22－3 트리의 삽입은 B 트리와 달리 리프 노드 외에서도 발생한다.

33－노드에 저장된 키값들은 그 노드의 모든 자식 노드의 키값보다 크다.

43－노드를 2개의 2－노드로 표현하여 2－3 트리를 레드－블랙 트리로 만들 수 있다.

문제 18

n

개의 버킷(bucket)으로 구성된 비어있는 해시 테이블에 다음 <조건>에 따라 해시 함수

h(x)=x \bmod n

을 사용하여 키값 <1, 20, 2, 35, 18>을 차례대로 삽입할 때, 발생하는 전체 충돌 횟수가 가장 많은

n

값은?

<조 건>
○

n

은 자연수이다.
○ 버킷 내 슬롯(slot) 수는 1이다.
○ 버킷의 인덱스는 0부터 시작한다.
○ 충돌 해결 방법으로 선형 조사법(linear probing)을 사용한다.
○ 각 키값의 삽입과정에서 발생하는 충돌 횟수가 k(k는 0 이상의 정수)일 때 전체 충돌 횟수가 k만큼 증가한다.

313

417

정답 및 해설

전체 충돌 횟수가 가장 많은 것은 $n=17$ 일 때(7회)이다.

각 $n$ 에 대해 1, 20, 2, 35, 18 순으로 넣으며 이미 찬 버킷을 만난 횟수를 센다.

$n=5$ : 1→1, 20→0, 2→2, 35는 0·1·2에서 충돌해 3에 저장(3회), 18은 3에서 충돌해 4에 저장(1회) → 총 4회
$n=7$ : 1, 6, 2, 0, 4로 모두 다른 버킷 → 0회
$n=13$ : 1, 7, 2, 9, 5로 모두 다른 버킷 → 0회
$n=17$ : 1→1, 20→3, 2→2, 35는 1·2·3에서 충돌해 4에 저장(3회), 18은 1·2·3·4에서 충돌해 5에 저장(4회) → 총 7회

문제 19

다음 그래프의 최소 비용 신장 트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?

1사이클이 있어 최소 비용 신장 트리가 존재하지 않는다.

2가중치가 가장 큰 간선은 최소 비용 신장 트리에 포함되지 않는다.

3모든 간선 가중치가 서로 달라 최소 비용 신장 트리의 개수는 1이다.

4두 정점 B와 D 사이의 최단 경로는 최소 비용 신장 트리에 포함된다.

정답 및 해설

간선 가중치가 모두 달라 최소 비용 신장 트리는 유일하므로 개수가 1이라는 설명이 옳다.

간선은 E–F 1, C–D 2, A–B 3, A–C 4, B–D 5, B–C 6, D–E 7이다. 크루스칼 알고리즘으로 가중치 순서대로 고르면 E–F, C–D, A–B, A–C를 채택하고, B–D와 B–C는 사이클을 만들어 버리며, D–E를 채택해 총비용 17의 트리가 된다.

사이클이 있어도 연결 그래프이면 신장 트리는 항상 존재하므로 존재하지 않는다는 설명은 틀리다.
가중치가 가장 큰 D–E 간선은 E, F를 나머지와 잇는 유일한 간선(브리지)이라 반드시 포함된다.
B와 D 사이의 최단 경로는 직접 간선 B–D(비용 5)인데, 이 간선은 트리에 포함되지 않는다(트리 경로 B–A–C–D는 비용 9).

문제 20

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

1G1, G2, G3, G4, G5, G6, G7, G8

2G1, G2, G3, G4, G5, G8, G6, G7

3G1, G3, G2, G4, G6, G5, G8, G7

4G1, G4, G3, G2, G7, G6, G5, G8

정답 및 해설

G6보다 G8이 먼저 나오는 순서는 위상 순서가 될 수 없다. 그림에 G6→G8 간선이 있기 때문이다.

간선은 G1→G2, G1→G3, G1→G4, G2→G5, G2→G6, G2→G8, G3→G6, G4→G6, G4→G7, G5→G8, G6→G8이다. 위상 순서에서는 모든 간선의 시작 정점이 끝 정점보다 앞에 있어야 하며, G8은 G2, G5, G6가 모두 나온 뒤에야 올 수 있다.

G1, G2, G3, G4, G5, G6, G7, G8: 모든 간선의 선후 관계를 만족한다.
G1, G3, G2, G4, G6, G5, G8, G7: G6 앞에 G2·G3·G4가, G8 앞에 G2·G5·G6가 모두 있어 유효하다.
G1, G4, G3, G2, G7, G6, G5, G8: G7은 G4 뒤, G6는 G2·G3·G4 뒤, G8은 마지막이라 유효하다.

문제 21

다음 C 언어로 구현한 arraySort 함수에서 재귀 호출 횟수의 최댓값이 가장 큰 배열 arr의 입력내용은? (단, arraySort 함수의 최초 호출 시 low 변수와 high 변수는 배열 arr의 첫 번째와 마지막 데이터의 인덱스이다)

#define SWAP(x,y) {int temp = x; x = y; y = temp;}

int splitArray(int arr[], int low, int high) {
   int pi = (low + high)/2;
   SWAP(arr[pi], arr[high]);
   int pivot = arr[high];

   int i = low - 1;
   for(int j = low; j < high; j++) {
      if(arr[j] < pivot) {
         i++;
         SWAP(arr[i], arr[j]);
      }
   }
   SWAP(arr[high], arr[i + 1]);
   return i + 1;
}

void arraySort(int arr[], int low, int high) {
   if(low < high) {
      int pi = splitArray(arr, low, high);
      arraySort(arr, low, pi - 1);
      arraySort(arr, pi + 1, high);
   }
}

11, 2, 3, 4, 5, 6, 7, 8, 9, 10

22, 4, 6, 8, 10, 5, 3, 7, 1, 9

33, 6, 2, 8, 5, 10, 7, 1, 9, 4

410, 9, 8, 7, 6, 5, 4, 3, 2, 1

정답 및 해설

재귀 호출 횟수가 가장 큰 입력은 2, 4, 6, 8, 10, 5, 3, 7, 1, 9이다.

splitArray는 가운데 원소를 피벗으로 쓴다. 이 입력은 매 분할마다 피벗이 구간의 최댓값이나 최솟값이 되어 한쪽 부분 배열이 비는 최악 분할이 반복되고, 재귀 깊이가 9까지 내려가 호출 수도 18회로 가장 많다.

이미 오름차순인 배열은 가운데 원소가 중앙값이라 균등 분할되어 재귀 깊이 3, 호출 12회다.
3, 6, 2, 8, 5, 10, 7, 1, 9, 4 역시 분할이 비교적 고르게 나뉘어 재귀 깊이 3, 호출 12회다.
내림차순 배열도 가운데 원소가 중앙값 부근이라 재귀 깊이 4, 호출 12회에 그친다.

문제 22

다음은 후위 표기식을 스택을 이용하여 사칙연산을 하는 알고리즘을 구현한 C 프로그램이다. 출력 결과가 12인 프로그램의 실행에 대한 설명으로 옳은 것만을 모두 고르면?

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  50

typedef int Item;
Item stack[MAX_STACK_SIZE];
int top;

void reset_stack() { top = -1; }

void push(Item elm) { stack[++top] = elm; }

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

Item calc_exp(char *exp) {
   int x, y, z, current, i = 0;
   reset_stack();
   while(exp[i] != '$') {
      current = exp[i++];
      if(current >= '0' && current <= '9')
         push([  (가)  ]);
      else if(current == '+' || current == '-' ||
              current == '*' || current == '/') {
         [  (나)  ] = pop();
         [  (다)  ] = pop();
         switch(current) {
            case '+': z = x + y; break;
            case '-': z = x - y; break;
            case '*': z = x * y; break;
            case '/': z = x / y;
         }
         push(z);
      }
   }
   return pop();
}

int main() {
   char exp[20] = "2 3 4 + * 6 3 / - $";
   printf("%d\n", calc_exp(exp));
   return 0;
}

ㄱ. (가)에 들어갈 내용은 current이다.
ㄴ. (나)에 들어갈 내용은 y이고 (다)에 들어갈 내용은 x이다.
ㄷ. 프로그램을 실행하는 동안 pop 함수의 총호출 횟수는 8회이다.
ㄹ. 프로그램을 실행하는 동안 push 함수의 총호출 횟수는 9회이다.

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄹ

4ㄱ, ㄴ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

2 3 4 + * 6 3 / − 는 $2\times(3+4) - 6/3 = 14 - 2 = 12$ 이다. 숫자 5개를 push하고, 연산자 4개마다 pop 2회·push 1회를 하며, 마지막에 결과를 pop 1회 한다.

ㄱ: current는 문자 코드이므로 숫자 값으로 바꾸려면 current - '0'을 push해야 한다(틀림).
ㄴ: 먼저 꺼낸 값이 오른쪽 피연산자이므로 y를 먼저, x를 나중에 꺼내야 x − y, x / y가 맞다(옳음).
ㄷ: pop은 연산자 4개 × 2회 + 최종 1회 = 9회이므로 8회가 아니다(틀림).
ㄹ: push는 숫자 5회 + 연산 결과 4회 = 9회다(옳음).

문제 23

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

typedef struct {
   int id;
   char name[10];
} Student;

void func(Student *dest, Student *src){
   dest = src;
}

int main() {
   Student st_a = {1, "AAA"}, st_b = {2, "BBB"};
   Student *st_arr[3] = {&st_a, &st_b, &st_b};

   func(st_arr[2], st_arr[0]);
   st_arr[2]->name[0] = 'X';

   for(int i = 0; i < 3; i++)
      printf("%s ", st_arr[i]->name);

   return 0;
}

1AAA XBB XBB

2AAA BBB XBB

3AAA BBB XAA

4XAA BBB XAA

정답 및 해설

출력은 AAA XBB XBB이다.

func는 포인터 값을 값으로 전달받아 지역 변수 dest만 바꾸므로 st_arr[2]는 여전히 &st_b를 가리킨다. 따라서 st_arr[2]->name[0] = 'X'는 st_b의 이름을 XBB로 바꾸고, 같은 st_b를 가리키는 st_arr[1]도 XBB를 출력한다.

AAA BBB XBB는 st_arr[1]과 st_arr[2]가 같은 구조체를 가리킨다는 점을 놓친 것이다.
AAA BBB XAA는 func가 st_arr[2]를 &st_a로 바꾼다고 본 것인데, 포인터 자체의 값 전달이라 바뀌지 않는다.
XAA BBB XAA 역시 func가 호출자의 포인터를 바꾼다고 잘못 본 결과다.

문제 24

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

int count = 0;

void new_hanoi(int n, char from, char tmp, char to) {
   if (n <= 2)
      count += n;
   else {
      new_hanoi(n - 2, from, to, tmp);
      count += 2;
      new_hanoi(n - 2, tmp, from, to);
   }
}

int main() {
   new_hanoi(9, 'A', 'B', 'C');
   printf("%d", count);
   return 0;
}

131

246

362

4511

정답 및 해설

출력은 46이다.

count 증가량을 $f(n)$ 이라 하면 $f(n)=n\ (n\le 2)$ , $f(n)=2f(n-2)+2$ 이다.

$f(1)=1$
$f(3)=2\times 1+2=4$
$f(5)=2\times 4+2=10$
$f(7)=2\times 10+2=22$
$f(9)=2\times 22+2=46$

따라서 출력은 46이다.

31은 원판 5개 일반 하노이 이동 횟수( $2^5-1$ ) 같은 값으로, 이 재귀식과 무관하다.
62는 위 재귀식으로 얻어지지 않는 값이다.
511은 원판 9개 일반 하노이 이동 횟수( $2^9-1$ )로, 두 개씩 줄이는 이 함수와 다르다.

문제 25

다음은 입력 배열 데이터 data 내에 찾고자 하는 값 key와 같은 값이 저장된 모든 배열 원소의 인덱스를 배열로 반환하는 search 함수를 포함한 Java 프로그램이다. 출력 결과가 (12:2,13:0,23:3,43:1)인 프로그램의 실행에 대한 설명으로 옳은 것만을 모두 고르면?

public class SearchAlgorithm {
   private static int[] index_list;
   private static int size;
   private static void reset() {
      index_list = new int[1];
      size = 0;
   }
   private static void resize(int newsize) {
      int[] nlist = new int[newsize];
      for(int i = 0; i < size; i++)
         nlist[i] = index_list[i];
      index_list = nlist;
   }
   private static void insert_index(int index) {
      if(size == index_list.length) resize(2 * size);
      index_list[[  (가)  ]] = index;
   }
   public static int[] search(int[] data, int key) {
      [  (나)  ];
      for(int i = 0; i < data.length; i++)
         if(data[i] == key) insert_index(i);
      int[] result_list = new int[size];
      for(int i = 0; i < result_list.length; i++)
         result_list[i] = index_list[i];
      return result_list;
   }
   public static void main(String[] args) {
      int[] data = {12, 45, 23, 43, 23, 54, 12, 23};
      int[] keys = {12, 13, 23, 43};
      String index_f = "(";
      for(int i = 0; i < keys.length; i++) {
         int key = keys[i];
         int[] indexs = search(data, key);
         index_f += key + ":" + indexs.length;
         if(i != keys.length - 1) index_f += ",";
      }
      System.out.println(index_f + ")");
      return;
   }
}

ㄱ. (가)에 들어갈 내용은 ++size이다.
ㄴ. (나)에 들어갈 내용은 reset()이다.
ㄷ. 프로그램을 실행하는 동안 resize 함수의 총호출 횟수는 4회이다.
ㄹ. 프로그램을 실행하는 동안 insert_index 함수의 총호출 횟수는 6회이다.

1ㄱ, ㄷ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄱ, ㄴ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

search마다 reset()으로 길이 1 배열·size 0에서 시작하고, insert_index는 index_list[size++]에 저장해야 한다. 키별 일치 개수는 12가 2개, 13이 0개, 23이 3개, 43이 1개다.

ㄱ: ++size이면 첫 삽입부터 index_list[1]에 접근해 범위를 벗어나므로 (가)는 size++여야 한다(틀림).
ㄴ: 키마다 결과를 새로 모으려면 탐색 전에 reset()이 필요하다(옳음).
ㄷ: resize는 키 12에서 1회(길이 1→2), 키 23에서 2회(1→2, 2→4)로 총 3회다(틀림).
ㄹ: insert_index는 일치 개수의 합 2+0+3+1=6회 호출된다(옳음).

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

26년 1회차

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

문제 1

포인터 변수 L이 단순 연결 리스트의 첫 번째 노드를 가리킬 때, (가)～(다)를 수행하는 각 알고리즘의 시간 복잡도를 바르게 연결한 것은? (단,

n

은 리스트의 노드 개수를 나타낸다)

(가) (나) (다)

O(1)

O(1)

O(1)

O(1)

O(n)

O(n)

O(n)

O(1)

O(n)

O(n)

O(n)

O(1)

정답 및 해설

역순 변환은 $O(n)$ , 첫 노드 삽입은 $O(1)$ , 마지막 노드 삭제는 $O(n)$ 이다.

역순 변환은 모든 노드의 링크를 한 번씩 뒤집어야 하므로 노드 수에 비례한다. 맨 앞 삽입은 새 노드의 link를 L로 두고 L을 새 노드로 바꾸면 끝난다.

마지막 노드를 지우려면 그 직전 노드의 link를 NULL로 바꿔야 하는데, 단순 연결 리스트는 뒤로 갈 수 없어 처음부터 끝까지 순회해야 한다.

세 연산 모두 상수 시간이라는 연결은 역순 변환과 마지막 노드 삭제가 전체 순회를 요구하므로 틀리다.
역순 변환을 상수 시간으로, 맨 앞 삽입을 선형 시간으로 본 연결은 두 연산의 비용을 뒤바꾼 것이다.
마지막 노드 삭제를 상수 시간으로 본 연결은 직전 노드를 찾는 순회를 빠뜨린 것이다.

문제 2

다음은 같은 기능을 수행하는 두 함수를 구현한 C 코드이다. 각 함수의 시간 복잡도를 바르게 연결한 것은?

double p1(double x, int n) {
   int i;
   double result = 1.0;

   for(i = 0; i < n; i++)
      result = result * x;
   return result;
}

double p2(double x, int n) {
   if(n == 0)
      return 1;
   else if((n % 2) == 0)
      return p2(x * x, n/2);
   else
      return x * p2(x * x, (n - 1)/2);
}

p1 함수 p2 함수

O(n)

O(1)

O(n)

O(\log n)

O(2^n)

O(n^2)

O(\log n)

O(n\log n)

정답 및 해설

p1은 $O(n)$ , p2는 $O(\log n)$ 이다.

p2를 상수 시간으로 본 연결은 지수가 0이 될 때까지 재귀가 반복되는 점을 무시한 것이다.
$O(2^n)$ · $O(n^2)$ 연결은 두 함수 모두 과대평가한 것이다.
$O(\log n)$ · $O(n\log n)$ 연결은 단순 반복인 p1을 과소평가하고 p2를 과대평가한 것이다.

문제 3

다음은 이중 연결 리스트(doubly linked list)를 구현한 C 코드이다. 노드 삭제 함수의 빈칸에 들어갈 내용으로 옳은 것은?

typedef int element;
typedef struct DListNode {
   element data;
   struct DListNode *llink;
   struct DListNode *rlink;
} DListNode;
DListNode *head = NULL;

void init() {
   head = (DListNode*)malloc(sizeof(DListNode));
   head->llink = head->rlink = head;
}

void dinsert(DListNode *inode, DListNode *inserted) {
   inserted->llink = inode;
   inserted->rlink = inode->rlink;
   inode->rlink->llink = inserted;
   inode->rlink = inserted;
}

void ddelete(DListNode *removed) {
   if(removed == head) return;
   removed->llink->rlink = removed->rlink;
   [                  ]
   free(removed);
}

1removed->rlink->llink = removed->llink;

2removed->rlink->llink = removed->rlink;

3removed->llink = removed->rlink->llink;

4removed->rlink = removed->rlink->llink;

정답 및 해설

빈칸에는 removed->rlink->llink = removed->llink;가 들어간다.

오른쪽 이웃의 llink에 removed->rlink를 넣으면 오른쪽 노드가 자기 자신을 가리키게 되어 역방향 연결이 끊긴다.
removed->llink = removed->rlink->llink;는 곧 해제될 노드 자신의 llink만 바꿀 뿐 오른쪽 이웃의 llink는 여전히 삭제된 노드를 가리킨다.
removed->rlink = removed->rlink->llink;도 해제될 노드 자신의 rlink만 바꾸므로 오른쪽 이웃의 역방향 링크가 갱신되지 않는다.

문제 4

12114 2265

22182 2187

32187 2114

42265 2182

정답 및 해설

행 우선 주소는 2187, 열 우선 주소는 2114이다.

배열은 15행 20열이다. 행 우선: $2000 + (10-1)\times 20 + (8-1)$
$= 2000 + 180 + 7 = 2187$

열 우선: $2000 + (8-1)\times 15 + (10-1)$
$= 2000 + 105 + 9 = 2114$

2114·2265 연결은 열 우선 주소 2114를 행 우선 자리에 둔 것이다.
2182·2187 연결은 행 우선 주소 2187을 열 우선 자리에 둔 것이다.
2265·2182 연결은 두 값 모두 위 계산과 맞지 않는다.

문제 5

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

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

node *head = NULL;
node *tail = NULL;

void init() {
   head = (node*)malloc(sizeof(node));
   tail = (node*)malloc(sizeof(node));
   head->next = tail;
   tail->next = tail;
}

int push(int k) {
   node *t;
   if((t = (node*)malloc(sizeof(node))) == NULL) {
      printf("\n Out of memory");
      return -1;
   }
   t->key = k;
   [        (가)        ]
   head->next = t;
   return k;
}

int pop() {
   node *t;
   int i;
   if(head->next == tail) {
      printf("\n Stack underflow");
      return -1;
   }
   t = head->next;
   i = t->key;
   [        (나)        ]
   free(t);
   return i;
}

(가) (나)

1t->next = head; head->next = t->next;

2t->next = head->next; head->next = t->next;

3t->next = head->next; head = t->next;

4t->next = head->next; head->next = t;

정답 및 해설

(가)는 t->next = head->next;, (나)는 head->next = t->next;이다.

(가)를 t->next = head로 쓰면 새 노드가 더미 head를 가리켜 기존 노드들과의 연결이 끊긴다.
(나)를 head = t->next로 쓰면 더미 head 노드 자체가 바뀌어 스택 구조가 깨진다.
(나)에 head->next = t를 쓰면 곧 해제할 t를 계속 가리키게 되어 삭제가 되지 않는다.

문제 6

다음 C 언어로 작성된 함수들의 시간 복잡도에 대한 설명으로 옳은 것은?

void func1(int n) {
   for(int i = 0 ; i < 2 ; i++)
      for(int j = 0 ; j < n ; j++)
         printf("%d\n", j);
}

void func2(int n) {
   for(int i = 0 ; i < 100 ; i++)
      printf("%d\n", i);
}

void func3(int n) {
   if(n == 0)
      return;
   printf("%d\n", n);
      func3(n/2); ····················(가)
}

1func1 함수는 이중 for 반복문으로 구성되어 시간 복잡도는

O(n^2)

이다.

2func2 함수는 for 반복문으로 구성되어 시간 복잡도는

O(n)

이다.

3func3 함수는 for 반복문이 없어 시간 복잡도는

O(1)

이다.

4(가) 문장을 func2(n/2);으로 수정할 경우, func3 함수의 시간 복잡도는

O(1)

이다.

정답 및 해설

(가)를 func2(n/2)로 바꾸면 func3는 상수 시간 $O(1)$ 이 된다.

수정 후 func3는 출력 한 번과 func2 호출 한 번만 수행하는데, func2는 인자와 무관하게 100회만 반복하므로 전체가 상수 시간이다.

func1의 바깥 반복은 2회로 고정이라 $2n$ 번 출력, 즉 $O(n)$ 이지 $O(n^2)$ 가 아니다.
func2는 반복 횟수가 100으로 고정되어 $O(1)$ 이지 $O(n)$ 이 아니다.
func3는 반복문이 없어도 $n$ 을 절반씩 줄이며 재귀하므로 $O(\log n)$ 이다.

문제 7

메모리 주소	data	link
1000	A	1300
1100	B	1400
1200	C	1000
1300	D	1100
1400	E	1200

1data 값이 A인 노드의 link 값을 1400으로 변경

2data 값이 B인 노드의 link 값을 1500으로 변경

3data 값이 C인 노드의 link 값을 1400으로 변경

4data 값이 E인 노드의 link 값을 1500으로 변경

정답 및 해설

새 노드는 B 노드와 E 노드 사이에 들어가므로 B 노드의 link를 1500으로 바꾼다.

A 노드의 link를 1400으로 바꾸면 D와 B가 리스트에서 빠지고 F는 연결되지도 않는다.
C 노드의 link를 1400으로 바꾸면 E와 C 사이에 작은 사이클이 생기고 F는 여전히 고립된다.
E 노드의 link를 1500으로 바꾸면 E→F→E 사이클이 생겨 C와 A 쪽 노드가 끊긴다.

문제 8

[0]	[1]	[2]	[3]	[4]	[5]	[6]
5	2	6	8

[0]	[1]	[2]	[3]	[4]	[5]	[6]
1	2	6	3			4

[0]	[1]	[2]	[3]	[4]	[5]	[6]
4	1	2	6	3

[0]	[1]	[2]	[3]	[4]	[5]	[6]
1	2	6	3	4

[0]	[1]	[2]	[3]	[4]	[5]	[6]
4	1	2	6			3

정답 및 해설

수행 후 덱은 [0]=1, [1]=2, [2]=6, [3]=3, [6]=4 상태가 된다.

[4]에 4가 놓인 상태는 앞쪽 삽입을 뒤쪽에 넣은 것이라 틀리다.
[0]부터 4, 1, 2, 6, 3이 차례로 놓인 상태는 원형으로 감기지 않고 원소를 오른쪽으로 밀어낸 것이다.
[6]에 3이 놓인 상태는 뒤쪽 삽입을 원형 앞쪽으로 넣은 것이라 틀리다.

문제 9

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

void function(int array[], int idx, int size) {
   for(int i = idx; i < size - 1; i++)
      array[i] = array[i + 1];
}

int main() {
   int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   function(array, 5, 10);
   function(array, 5, 10);

   for(int i = 0; i < 10; i++)
      printf("%d ", array[i]);
   printf("\n");

   return 0;
}

10 1 2 3 4 5 6 7 8 9

20 1 2 3 4 7 8 9 9 9

30 1 2 3 5 5 6 7 8 9

40 1 2 3 5 6 7 8 9 9

정답 및 해설

출력은 0 1 2 3 4 7 8 9 9 9이다.

function은 idx부터 한 칸씩 왼쪽으로 당겨 array[idx]를 지우는 효과를 내며, 마지막 칸은 그대로 남는다.
1회 후: 0 1 2 3 4 6 7 8 9 9
2회 후: 0 1 2 3 4 7 8 9 9 9

원래 배열 그대로라는 출력은 함수가 배열 원본을 수정한다는 점(배열 인자는 포인터 전달)을 놓친 것이다.
4가 사라지고 5가 두 번 나오는 출력은 시작 인덱스를 잘못 잡은 것이다.
5부터 9까지 한 칸만 당겨진 출력은 함수를 한 번만 호출한 경우이며, 시작 인덱스도 어긋난다.

문제 10

1중위 순회

2전위 순회

3후위 순회

4레벨 순회

정답 및 해설

정답은 중위 순회이다.

전위 순회는 루트를 왼쪽 서브트리보다 먼저 내므로 오름차순이 되지 않는다.
후위 순회는 루트를 마지막에 내므로 오름차순이 되지 않는다.
레벨 순회는 깊이 순으로 방문해 같은 레벨 안에서만 순서가 유지될 뿐 전체 정렬이 되지 않는다.

문제 11

정점의 개수가 n인 단순 그래프가 트리이기 위한 필요충분조건으로 옳지 않은 것은? (단, n은 3 이상의 정수이다)

1사이클이 없고 연결요소의 개수가 1이다.

2임의의 두 정점 사이에 존재하는 경로의 개수는 1이다.

3간선의 개수가 n－1이고, 차수가 1인 정점의 개수가 2 이상이다.

4사이클이 없지만, 인접하지 않은 임의의 두 정점 사이에 간선을 추가하면 사이클의 개수가 1이 된다.

정답 및 해설

옳지 않은 것은 “간선 n−1개이고 차수 1인 정점이 2개 이상”이라는 조건이다.

사이클이 없고 연결요소가 하나라는 것은 트리의 정의 그 자체다.
임의의 두 정점 사이 경로가 정확히 하나라는 것도 트리의 동치 조건이다.
사이클이 없으면서 간선을 하나만 더해도 사이클이 생긴다는 것은 극대 비순환 그래프, 곧 트리의 동치 조건이다.

문제 12

(가)	4	1	2	8	5	9
(나)	1	2	8	5	9	4
(다)	9	8	4	2	1	5
(라)	9	8	1	5	4	2

정답 및 해설

네 AVL 트리에 공통인 리프 키는 9이다.

네 트리 모두에 리프로 남는 키는 9뿐이다.

2는 (라)에서만 리프이고 나머지에서는 내부 노드다.
4는 (가)·(나)에서는 리프지만 (다)·(라)에서는 루트다.
5는 (다)·(라)에서는 리프지만 (가)·(나)에서는 루트다.

문제 13

11차 군집 현상이 발생하지 않게 한다.

2해시 테이블의 전체 크기를 자동으로 기존 크기의 두 배로 확장 시킨다.

3충돌로 인해 원래 해시 주소와는 다른 주소에 저장된 레코드에 대한 탐색이 가능하게 한다.

4해시 테이블에 저장된 모든 레코드의 키값이 항상 오름차순으로 정렬된 상태가 되도록 유지시킨다.

정답 및 해설

삭제 표시를 남기는 이유는 충돌로 다른 주소에 밀려 저장된 레코드를 계속 탐색할 수 있게 하기 위해서다.

1차 군집은 선형 조사 자체의 성질이라 삭제 표시로 막을 수 없다.
테이블 크기 확장(재해싱)은 적재율에 따른 별도 처리로 삭제 표시와 무관하다.
해시 테이블은 키 순서를 유지하는 구조가 아니므로 오름차순 정렬과 관계없다.

문제 14

다음 C 언어로 구현한 sort 함수에서 (가) 문장이 수행되는 횟수가 가장 작은 배열 arr의 입력내용은? (단, n ＝ 5이다)

void sort(int arr[], int n) {
   int i, key, j;
   for(i = 1; i < n; i++) {
      key = arr[i];
      j = i - 1;
      while(j >= 0 && arr[j] < key) {
         arr[j + 1] = arr[j]; ···········(가)
         j = j - 1;
      }
      arr[j + 1] = key;
   }
}

11, 2, 3, 4, 5

25, 3, 4, 7, 6

38, 3, 10, 7, 2

410, 9, 8, 7, 6

정답 및 해설

(가)가 가장 적게 수행되는 입력은 10, 9, 8, 7, 6이다.

조건이 arr[j] < key이므로 이 함수는 내림차순 삽입 정렬이고, (가)의 수행 횟수는 앞 원소가 뒤 원소보다 작은 쌍의 수와 같다.

1, 2, 3, 4, 5는 모든 쌍이 앞이 작아 10회로 최대다.
5, 3, 4, 7, 6은 (5,7)(5,6)(3,4)(3,7)(3,6)(4,7)(4,6)의 7회다.
8, 3, 10, 7, 2는 (8,10)(3,10)(3,7)의 3회다.
10, 9, 8, 7, 6은 이미 내림차순이라 0회다.

문제 15

1특정 정점의 차수 계산

2그래프 전체의 간선 개수 세기

3특정 정점에서 시작하는 너비 우선 탐색

4특정 두 정점 사이의 간선 존재 여부 확인

정답 및 해설

인접 행렬이 더 빠른 연산은 두 정점 사이의 간선 존재 여부 확인이다.

인접 행렬은 원소 하나만 보면 되어 $O(1)$ 이지만, 인접 리스트는 한 정점의 리스트를 훑어야 하므로 그 정점의 차수에 비례한다.

특정 정점의 차수 계산은 행렬에서 한 행 전체( $O(n)$ )를 봐야 하고 리스트는 차수만큼만 보면 된다.
전체 간선 개수 세기는 행렬이 $O(n^2)$ , 리스트가 $O(n+e)$ 로 리스트가 유리하다.
너비 우선 탐색도 행렬은 $O(n^2)$ , 리스트는 $O(n+e)$ 로 리스트가 유리하다.

문제 16

다음 그래프에 대한 깊이 우선 탐색(depth first search)을 수행할 때 가능한 정점들의 방문 순서는?

1A, B, F, C, D, E

2C, A, B, D, E, F

3D, F, E, B, A, C

4E, F, A, B, D, C

정답 및 해설

가능한 방문 순서는 D, F, E, B, A, C이다. 그림의 간선은 C→A, A→B, A→D, B→F, C→F, D→E, D→F, E→B, E→F이다.

A, B, F, C, D, E: F에서 A로 되돌아오면 A의 미방문 인접 정점 D를 먼저 방문해야 하는데 C로 넘어가므로 불가능하다.
C, A, B, D, E, F: B의 인접 정점 F가 미방문인데 B에서 F로 가지 않고 D로 넘어가므로 불가능하다.
E, F, A, B, D, C: F에서 E로 되돌아오면 E의 미방문 인접 정점 B를 먼저 방문해야 하는데 A로 넘어가므로 불가능하다.

문제 17

2－3 트리에 대한 설명으로 옳은 것은?

12－3 트리가 항상 완전 균형 트리를 유지하는 것은 아니다.

22－3 트리의 삽입은 B 트리와 달리 리프 노드 외에서도 발생한다.

33－노드에 저장된 키값들은 그 노드의 모든 자식 노드의 키값보다 크다.

43－노드를 2개의 2－노드로 표현하여 2－3 트리를 레드－블랙 트리로 만들 수 있다.

문제 18

n

개의 버킷(bucket)으로 구성된 비어있는 해시 테이블에 다음 <조건>에 따라 해시 함수

h(x)=x \bmod n

을 사용하여 키값 <1, 20, 2, 35, 18>을 차례대로 삽입할 때, 발생하는 전체 충돌 횟수가 가장 많은

n

값은?

<조 건>
○

n

313

417

정답 및 해설

전체 충돌 횟수가 가장 많은 것은 $n=17$ 일 때(7회)이다.

각 $n$ 에 대해 1, 20, 2, 35, 18 순으로 넣으며 이미 찬 버킷을 만난 횟수를 센다.

$n=5$ : 1→1, 20→0, 2→2, 35는 0·1·2에서 충돌해 3에 저장(3회), 18은 3에서 충돌해 4에 저장(1회) → 총 4회
$n=7$ : 1, 6, 2, 0, 4로 모두 다른 버킷 → 0회
$n=13$ : 1, 7, 2, 9, 5로 모두 다른 버킷 → 0회
$n=17$ : 1→1, 20→3, 2→2, 35는 1·2·3에서 충돌해 4에 저장(3회), 18은 1·2·3·4에서 충돌해 5에 저장(4회) → 총 7회

문제 19

다음 그래프의 최소 비용 신장 트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?

1사이클이 있어 최소 비용 신장 트리가 존재하지 않는다.

2가중치가 가장 큰 간선은 최소 비용 신장 트리에 포함되지 않는다.

3모든 간선 가중치가 서로 달라 최소 비용 신장 트리의 개수는 1이다.

4두 정점 B와 D 사이의 최단 경로는 최소 비용 신장 트리에 포함된다.

정답 및 해설

간선 가중치가 모두 달라 최소 비용 신장 트리는 유일하므로 개수가 1이라는 설명이 옳다.

사이클이 있어도 연결 그래프이면 신장 트리는 항상 존재하므로 존재하지 않는다는 설명은 틀리다.
가중치가 가장 큰 D–E 간선은 E, F를 나머지와 잇는 유일한 간선(브리지)이라 반드시 포함된다.
B와 D 사이의 최단 경로는 직접 간선 B–D(비용 5)인데, 이 간선은 트리에 포함되지 않는다(트리 경로 B–A–C–D는 비용 9).

문제 20

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

1G1, G2, G3, G4, G5, G6, G7, G8

2G1, G2, G3, G4, G5, G8, G6, G7

3G1, G3, G2, G4, G6, G5, G8, G7

4G1, G4, G3, G2, G7, G6, G5, G8

정답 및 해설

G6보다 G8이 먼저 나오는 순서는 위상 순서가 될 수 없다. 그림에 G6→G8 간선이 있기 때문이다.

G1, G2, G3, G4, G5, G6, G7, G8: 모든 간선의 선후 관계를 만족한다.
G1, G3, G2, G4, G6, G5, G8, G7: G6 앞에 G2·G3·G4가, G8 앞에 G2·G5·G6가 모두 있어 유효하다.
G1, G4, G3, G2, G7, G6, G5, G8: G7은 G4 뒤, G6는 G2·G3·G4 뒤, G8은 마지막이라 유효하다.

문제 21

#define SWAP(x,y) {int temp = x; x = y; y = temp;}

int splitArray(int arr[], int low, int high) {
   int pi = (low + high)/2;
   SWAP(arr[pi], arr[high]);
   int pivot = arr[high];

   int i = low - 1;
   for(int j = low; j < high; j++) {
      if(arr[j] < pivot) {
         i++;
         SWAP(arr[i], arr[j]);
      }
   }
   SWAP(arr[high], arr[i + 1]);
   return i + 1;
}

void arraySort(int arr[], int low, int high) {
   if(low < high) {
      int pi = splitArray(arr, low, high);
      arraySort(arr, low, pi - 1);
      arraySort(arr, pi + 1, high);
   }
}

11, 2, 3, 4, 5, 6, 7, 8, 9, 10

22, 4, 6, 8, 10, 5, 3, 7, 1, 9

33, 6, 2, 8, 5, 10, 7, 1, 9, 4

410, 9, 8, 7, 6, 5, 4, 3, 2, 1

정답 및 해설

재귀 호출 횟수가 가장 큰 입력은 2, 4, 6, 8, 10, 5, 3, 7, 1, 9이다.

이미 오름차순인 배열은 가운데 원소가 중앙값이라 균등 분할되어 재귀 깊이 3, 호출 12회다.
3, 6, 2, 8, 5, 10, 7, 1, 9, 4 역시 분할이 비교적 고르게 나뉘어 재귀 깊이 3, 호출 12회다.
내림차순 배열도 가운데 원소가 중앙값 부근이라 재귀 깊이 4, 호출 12회에 그친다.

문제 22

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  50

typedef int Item;
Item stack[MAX_STACK_SIZE];
int top;

void reset_stack() { top = -1; }

void push(Item elm) { stack[++top] = elm; }

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

Item calc_exp(char *exp) {
   int x, y, z, current, i = 0;
   reset_stack();
   while(exp[i] != '$') {
      current = exp[i++];
      if(current >= '0' && current <= '9')
         push([  (가)  ]);
      else if(current == '+' || current == '-' ||
              current == '*' || current == '/') {
         [  (나)  ] = pop();
         [  (다)  ] = pop();
         switch(current) {
            case '+': z = x + y; break;
            case '-': z = x - y; break;
            case '*': z = x * y; break;
            case '/': z = x / y;
         }
         push(z);
      }
   }
   return pop();
}

int main() {
   char exp[20] = "2 3 4 + * 6 3 / - $";
   printf("%d\n", calc_exp(exp));
   return 0;
}

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄹ

4ㄱ, ㄴ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

2 3 4 + * 6 3 / − 는 $2\times(3+4) - 6/3 = 14 - 2 = 12$ 이다. 숫자 5개를 push하고, 연산자 4개마다 pop 2회·push 1회를 하며, 마지막에 결과를 pop 1회 한다.

ㄱ: current는 문자 코드이므로 숫자 값으로 바꾸려면 current - '0'을 push해야 한다(틀림).
ㄴ: 먼저 꺼낸 값이 오른쪽 피연산자이므로 y를 먼저, x를 나중에 꺼내야 x − y, x / y가 맞다(옳음).
ㄷ: pop은 연산자 4개 × 2회 + 최종 1회 = 9회이므로 8회가 아니다(틀림).
ㄹ: push는 숫자 5회 + 연산 결과 4회 = 9회다(옳음).

문제 23

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

typedef struct {
   int id;
   char name[10];
} Student;

void func(Student *dest, Student *src){
   dest = src;
}

int main() {
   Student st_a = {1, "AAA"}, st_b = {2, "BBB"};
   Student *st_arr[3] = {&st_a, &st_b, &st_b};

   func(st_arr[2], st_arr[0]);
   st_arr[2]->name[0] = 'X';

   for(int i = 0; i < 3; i++)
      printf("%s ", st_arr[i]->name);

   return 0;
}

1AAA XBB XBB

2AAA BBB XBB

3AAA BBB XAA

4XAA BBB XAA

정답 및 해설

출력은 AAA XBB XBB이다.

AAA BBB XBB는 st_arr[1]과 st_arr[2]가 같은 구조체를 가리킨다는 점을 놓친 것이다.
AAA BBB XAA는 func가 st_arr[2]를 &st_a로 바꾼다고 본 것인데, 포인터 자체의 값 전달이라 바뀌지 않는다.
XAA BBB XAA 역시 func가 호출자의 포인터를 바꾼다고 잘못 본 결과다.

문제 24

다음 C 프로그램의 실행 결과는?

#include <stdio.h>

int count = 0;

void new_hanoi(int n, char from, char tmp, char to) {
   if (n <= 2)
      count += n;
   else {
      new_hanoi(n - 2, from, to, tmp);
      count += 2;
      new_hanoi(n - 2, tmp, from, to);
   }
}

int main() {
   new_hanoi(9, 'A', 'B', 'C');
   printf("%d", count);
   return 0;
}

131

246

362

4511

정답 및 해설

출력은 46이다.

count 증가량을 $f(n)$ 이라 하면 $f(n)=n\ (n\le 2)$ , $f(n)=2f(n-2)+2$ 이다.

$f(1)=1$
$f(3)=2\times 1+2=4$
$f(5)=2\times 4+2=10$
$f(7)=2\times 10+2=22$
$f(9)=2\times 22+2=46$

따라서 출력은 46이다.

31은 원판 5개 일반 하노이 이동 횟수( $2^5-1$ ) 같은 값으로, 이 재귀식과 무관하다.
62는 위 재귀식으로 얻어지지 않는 값이다.
511은 원판 9개 일반 하노이 이동 횟수( $2^9-1$ )로, 두 개씩 줄이는 이 함수와 다르다.

문제 25

public class SearchAlgorithm {
   private static int[] index_list;
   private static int size;
   private static void reset() {
      index_list = new int[1];
      size = 0;
   }
   private static void resize(int newsize) {
      int[] nlist = new int[newsize];
      for(int i = 0; i < size; i++)
         nlist[i] = index_list[i];
      index_list = nlist;
   }
   private static void insert_index(int index) {
      if(size == index_list.length) resize(2 * size);
      index_list[[  (가)  ]] = index;
   }
   public static int[] search(int[] data, int key) {
      [  (나)  ];
      for(int i = 0; i < data.length; i++)
         if(data[i] == key) insert_index(i);
      int[] result_list = new int[size];
      for(int i = 0; i < result_list.length; i++)
         result_list[i] = index_list[i];
      return result_list;
   }
   public static void main(String[] args) {
      int[] data = {12, 45, 23, 43, 23, 54, 12, 23};
      int[] keys = {12, 13, 23, 43};
      String index_f = "(";
      for(int i = 0; i < keys.length; i++) {
         int key = keys[i];
         int[] indexs = search(data, key);
         index_f += key + ":" + indexs.length;
         if(i != keys.length - 1) index_f += ",";
      }
      System.out.println(index_f + ")");
      return;
   }
}

1ㄱ, ㄷ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄱ, ㄴ, ㄹ

정답 및 해설

옳은 것은 ㄴ, ㄹ이다.

ㄱ: ++size이면 첫 삽입부터 index_list[1]에 접근해 범위를 벗어나므로 (가)는 size++여야 한다(틀림).
ㄴ: 키마다 결과를 새로 모으려면 탐색 전에 reset()이 필요하다(옳음).
ㄷ: resize는 키 12에서 1회(길이 1→2), 키 23에서 2회(1→2, 2→4)로 총 3회다(틀림).
ㄹ: insert_index는 일치 개수의 합 2+0+3+1=6회 호출된다(옳음).