5급 공채 2차

2020년 5급 공채 기술 2차 자료구조론(필수)

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

제1문 (10점)

다음은 C언어로 구현한 이진트리(Binary Tree) 순회프로그램이다. 물음에 답하시오. (총 10점)
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
}TreeNode;
Ⓐ
TreeNode n1= {1, NULL, NULL };
TreeNode n2= {4, &n1, NULL };
TreeNode n3= {16, NULL, NULL };
TreeNode n4= {25, NULL, NULL };
TreeNode n5= {20, &n3, &n4 };
TreeNode n6= {15, &n2, &n5 };
TreeNode *root= &n6;

Ⓑ
inorder( TreeNode *root ) { }
preorder( TreeNode *root ) { }
postorder( TreeNode *root ) { }

void main()
{
inorder(root);
preorder(root);
postorder(root);
}
TreeNode n1= {1, NULL, NULL };
TreeNode n2= {4, &n1, NULL };
TreeNode n3= {16, NULL, NULL };
TreeNode n4= {25, NULL, NULL };
TreeNode n5= {20, &n3, &n4 };
TreeNode n6= {15, &n2, &n5 };
TreeNode *root= &n6;
inorder( TreeNode *root ) { }
preorder( TreeNode *root ) { }
postorder( TreeNode *root ) { }
  1. (1) Ⓐ부분을 통하여 만들어지는 트리구조를 표현하시오. (4점)
  2. (2) 중위순회(inorder), 전위순회(preorder), 후위순회(postorder)를 C언어의 순환호출(재귀함수)과 printf문을 이용하여 구현하고자 할 때 Ⓑ부분을 작성하시오. (6점)

제2문 (20점)

가중치 그래프에 대한 다음 물음에 답하시오. (총 20점)
[그림]
  1. (1) 위 그래프를 인접 행렬(adjacency matrix)로 표현하시오. (6점)
  2. (2) v1 노드를 시작점으로 하는 깊이우선 신장트리를 그리시오. (단, 가중치는 무시하며, 노드 방문은 노드 번호가 작은 것부터 방문한다) (6점)
  3. (3) v1 노드를 시작점으로 하여 Prim 알고리즘에 따라 최소비용 신장트리를 구성할 때 선택되는 간선(edge)들을 순서에 따라 나열하고, 이때 얻어지는 최소비용 신장트리를 그리시오. (8점)

제3문 (20점)

서로 다른 정수 n개를 저장하고 있는 이진탐색트리가 있다. 트리의 각 노드 구조는 그림과 같다.
p
data
leftright

이때 data는 키(key)로 사용되는 정수이고, 세 개의 포인터 p, left, right는 각각 해당 노드의 부모노드, 왼쪽자식, 오른쪽자식을 가리킨다.
예를 들어 (a)의 이진탐색트리는 (b)와 같이 구현할 수 있다.
(b)에서 ‘/’는 NULL 주소를 의미한다. 물음에 답하시오. (총 20점)
(a)
[그림]

(b)
[그림]
  1. (1) 루트노드가 v인 이진탐색트리에 저장된 정수들 중 최소 정수를 저장하고 있는 노드를 찾는 알고리즘 AAA의 의사코드(pseudocode)를 작성하고 복잡도를 분석하시오. (8점)
  2. (2) 이진탐색트리의 어떤 노드 v에 정수 k가 저장되어 있다고 하자. 트리에 저장된 모든 정수를 오름차순으로 정렬했을 때, k 다음의 정수를 저장한 노드를 k의 successor라 한다. 1)에서 설계한 알고리즘 AAA를 이용하여, 주어진 노드 v의 successor를 찾는 알고리즘 BBB의 의사코드를 작성하고, 복잡도를 분석하시오. (단, k가 트리에 저장된 정수들 중 최대 정수이면 NULL을 반환한다) (12점)

제4문 (20점)

자연수 n을 입력받아 while문의 반복 횟수를 출력하는 알고리즘이다. 다음 물음에 답하시오. (총 20점)
input n;
i ← n;
cnt ← 0;
while i > 0 do
j ← n;
while j > i do
print i, j;
j ← j – 1;
cnt ← cnt + 1;
end while
i ← i – 1;
end while
print cnt;
  1. (1) 변수 n에 5를 입력하였을 경우, 변수 i와 j의 값이 변화하는 과정과 마지막으로 출력되는 변수 cnt의 값을 보이시오. (8점)
  2. (2) 이 알고리즘의 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하고, 복잡도의 계산 과정을 보이시오. (12점)

제5문 (30점)

크기가 n인 배열 A[1..n]의 원소는 양의 정수이고, 마지막 원소 A[n]은 배열 A[1..n-1]의 모든 원소보다 크다. 배열 A에 대해 배열 B[i](1≤i< n)는 다음과 같이 정의된다.
B[i] = min{ k : i < k and A[i] < A[k] }

배열 A[1..n]이 주어졌을 때, 배열 B[1..n-1]을 계산하는 프로그램을 작성하고자 한다. 다음 물음에 답하시오. (총 30점)
  1. (1) 배열 A가 다음과 같을 때, 배열 B[1..8]을 구하시오. (8점)
    A[1..9] ＝
    123456789
    420415108101399
  2. (2) 최악의 경우에 Θ(n2) 시간이 필요한 프로그램의 의사코드(pseudocode)를 작성하시오. (8점)
  3. (3) 스택을 사용하여 O(n) 시간을 필요로 하는 프로그램의 의사코드를 작성하시오. (단, 아래 스택 연산은 이미 구현되어 있다) (14점)
    －push(k): k를 스택에 삽입
    －pop(): 스택의 가장 위 원소를 삭제하고, 그 값을 리턴
    －top(): 스택의 가장 위 원소 리턴. 원소는 삭제하지 않음
    －empty(): 스택이 비었으면 참