2018년 5급 공채 기술 2차 자료구조론(선택)

문제 5개 · 50점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.

제1문 (10점)

아래 구조체로 정의된 노드들로 구성된 단순 연결 리스트를 역순으로 만드는 함수인 reverse()를 구현하려고 한다. 다음 물음에 답하시오. (총 10점)

typedef struct node_t {
int key;
struct node_t *link;
} node_t;

(1) 순회 포인터인 p, q, r과 반복문으로 구현된 아래의 reverse() 함수에서 ㉠부분의 코드를 완성하시오. (5점)
node_t *reverse(node_t *head)
{
node_t *p, *q, *r;
p = head;
q = NULL;
while (p != NULL){

( ㉠ )

}
return q;
}
( ㉠ )
(2) 아래의 reverseR() 함수에서 ㉡부분의 코드를 재귀(recursive) 함수로 완성하시오. (5점)
node_t *reverseR(node_t *head)
{
node_t *first, *rest;

if (head == NULL) return NULL;
first = head;
rest = first->link;
if (rest == NULL) return head;

( ㉡ )

}
( ㉡ )

제2문 (10점)

아래 그림에 대해 Prim 알고리즘을 적용하여 최소신장트리(Minimum Spanning Tree)를 구하고자 한다. 다음 물음에 답하시오. (총 10점)
[그림]

(1) 최소신장트리는 V_{{1}}에서 시작하며, 최소신장트리에 추가되는 정점은 최소 Heap을 이용하여 결정한다. 최소신장트리에 정점을 추가할 때마다 추가될 정점을 결정하기 위한 최소 Heap과 결정된 정점이 추가된 최소신장트리를 각각 그림으로 제시하시오. (단, Heap에 입력되는 정점은 V_{{첨 자}}(가중치) －예를 들어 V_{{1}}에서 V_{{5}}를 Heap에 입력할 경우 V_{{5}} ( 2 )가 됨－ 형태를 가지며, 입력되는 정점의 가중치로 Heap의 구조를 형성한다. 그리고 Heap에 입력되는 정점들의 순서는 입력되는 정점의 첨자 순으로 하며 Heap에서 부모와 자식의 노드 교환을 위한 조건은 ‘자식→가중치＜부모→가중치’이다) (5점)
(2) 최소신장트리가 생성되는 동안 생성된 최소 Heap에서의 정점의 가중치가 한 번이라도 변경된 모든 정점을 나열하고, 1)에 의해 생성된 최소신장트리의 가중치를 제시하시오. (5점)

제3문 (10점)

레드블랙 트리(Red－Black Tree)에 대한 다음 물음에 답하시오. (총 10점)

(1) 아래의 레드블랙 트리에서 11과 10이 순서대로 삽입했을 경우, 결과를 각각 그림으로 설명하시오. (단, 루트노드와 외부노드는 모두 블랙노드임. 가는 실선은 블랙링크를 표시하며, 블랙링크에 연결된 자식노드는 블랙노드임을 나타냄. 굵은 실선은 레드링크를 표시하며 레드링크에 연결된 자식노드는 레드노드임을 가정함) (5점)
[그림]
(2) Red－Black 트리에 기반하여 주어진 숫자의 전체 오름차순에서의 순위를 구하는 Order－Statistic 트리를 구현하고자 한다. 이를 위하여 일반적인 Red－Black 트리에 어떠한 정보를 추가로 저장하여야 하는지 설명하고, 이를 이용하여 주어진 순위를 갖는 노드를 반환하는 Select 함수와 주어진 노드의 순위를 반환하는 Rank 함수의 의사코드(Pseudo Code)를 제시하시오. (5점)
○Select(root, i) // root는 Red－Black 트리의 루트노드, i은 주어진 순위 값임
○Rank(root, x) // root는 Red－Black 트리의 루트노드, x는 주어진 노드임

제4문 (10점)

아래 이진트리(Binary Tree)에 대해 다음 물음에 답하시오. (총 10점)
[그림]

(1) 재귀적으로 중위순회(Inorder Traversal)하였을 경우 노드의 출력 순서와 스택(Stack)의 변화 과정을 그림으로 제시하시오. (단, 스택에 자료가 삽입(push)되고 삭제(pop)되는 위치를 가리키는 인덱스 포인터를 top이라 가정한다) (5점)
[그림]
(2) 아래 실행결과처럼 이진트리의 좌측 자식노드(Left Child)와 우측 자식노드(Right Child)를 교환하는 swap_tree() 알고리즘을 C언어로 작성하고, 트리의 노드 수가 n이라고 할 때, 시간 복잡도(Time Complexity)를 빅 오(Big－Oh) 표기법으로 표현하시오. (5점)
typedef struct bi_tree {
char id;
NODE *Lchild;
NODE *Rchild;
} NODE;

void swap_tree(NODE *T) {
NODE *tmp;
... // 필요한 코드를 작성
// 추가적인 변수 선언은 불필요함
return;
}

<실행결과>
[그림]

제5문 (10점)

아래는 배열의 데이터 값을 정렬하는 퀵정렬(Quick Sort)의 C프로그램이다. 다음 물음에 답하시오. (단, SWAP()함수는 배열의 두 수를 교환하는 함수이다) (총 10점)

void quickSort(int data[], int left, int right)
{
if(left<right) {
int q;

( ㉠ )

}
}

int partition(int data[], int left, int right)
{ int pivot, i;
int low, high;

low = left; high = right+1;
pivot = data[left];
do{ do low++;
while(low<=right && data[low]<pivot);
do high--;
while(high>=left && data[high]>pivot);

if(low<high) SWAP(data[low], data[high]);
} while(low<high);

SWAP(data[left], data[high]);
return high;
}

( ㉠ )

(1) 재귀(Recursive) 함수를 이용하여 ㉠부분에 들어갈 코드를 기술하시오. (2점)
(2) 배열 A[]를 퀵정렬을 이용하여 정렬하는 과정과 퀵정렬이 배열 A[]에 대하여 최악의 시간 복잡도(Time Complexity)가 나오는 이유를 설명하시오. (3점)
A[10]＝{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
(3) 2)의 문제점을 개선하기 위한 방법을 제시하고, int do_sort(int data[], int left, int right)를 작성한 후 do_sort() 함수를 이용하여 피봇을 선정하도록 함수 partition()을 수정하시오. (5점)

	<실행결과>

[그림]