5급 공채 2차

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

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

제1문 (15점)

방향 그래프에 대한 다음 물음에 답하시오. (총 15점)
[그림]
  1. (1) 주어진 방향 그래프를 인접 리스트(adjacency list)로 표현하고 각 정점(vertex)의 진입 차수(in-degree)와 진출 차수(out-degree)를 구하시오. (5점)
  2. (2) 저장 공간을 최소한으로 사용하는 인접 리스트로 표현된 방향 그래프에서 임의의 정점 v의 진출 차수를 계산하는 함수에 대해 C언어 형식의 의사 코드(pseudo code)로 제시하고, 제시한 의사 코드의 시간 복잡도를 빅오(Big-Oh) 표기법으로 표현하시오. (5점)
  3. (3) 저장 공간을 최소한으로 사용하는 인접 리스트로 표현된 방향 그래프에서 임의의 정점 v의 진입 차수를 계산하는 함수에 대해 C언어 형식의 의사 코드로 제시하고, 제시한 의사 코드의 시간 복잡도를 빅오 표기법으로 표현하시오. (5점)

제2문 (10점)

<리스트 A>와 <리스트 B>에 대해 퀵 정렬(quick sort)을 수행하고자 한다. 다음 물음에 답하시오. (총 10점)
<리스트 A> 4, 2, 7, 3, 8, 0, 5, 1, 6
<리스트 B> 8, 7, 6, 5, 4, 3, 2, 1, 0
  1. (1) 리스트의 첫 번째 값을 피벗(pivot)으로 선택할 때 <리스트 A>와 <리스트 B> 각각에 대해 퀵 정렬이 수행되는 과정을 보이고, 분할(partition) 함수는 총 몇 번씩 수행되는지 구하시오. (단, 레코드가 하나만 남으면 분할 함수는 더 이상 수행하지 않는다) (4점)
  2. (2) 리스트의 중앙값(median)을 피벗으로 선택할 때 <리스트 A>와 <리스트 B> 각각에 대해 퀵 정렬이 수행되는 과정을 보이고, 분할 함수는 총 몇 번씩 수행되는지 구하시오. (단, 인덱스가 i인 값이 k_{{i}}일 때, 첫번째 값의 인덱스가 l이고 마지막 값의 인덱스가 r인 리스트의 중앙값은 median{k_{{l}}, k_{{( l + r ) / 2}}, k_{{r}}}이다. 그리고 레코드가 하나만 남으면 분할 함수는 더 이상 수행하지 않는다) (4점)
  3. (3) 리스트의 첫 번째 값을 피벗으로 선택하는 방법에 비해 중앙값을 피벗으로 선택하는 방법이 가지는 장점에 대해 설명하시오. (2점)

제3문 (10점)

m개의 동치 쌍(equivalence pairs)과 n개의 변수에 대해 동치 부류(equivalence class)를 구하기 위해, 각 동치 변수의 쌍 <i, j>를 순서대로 읽어 각 변수의 동치를 연결 리스트로 표현하는 방법을 사용하려고 한다. 이를 위해, 노드는 data 필드와 link 필드만으로 구성되고 i번째 변수에 대한 임의 접근을 위해 n개의 리스트 헤드 노드를 저장하는 일차원 배열 var[n]을 사용한다. 그리고 어떤 변수가 이미 출력되었는지를 알려주기 위해 배열 output[n]에 상수 TRUE나 FALSE를 저장한다. 다음 물음에 답하시오. (총 10점)
  1. (1) 연결 리스트와 스택을 사용하여 동치 부류를 출력하는 알고리즘을 C 언어 형식의 의사 코드로 제시하시오. (5점)
  2. (2) 다음 동치 쌍에 대해 각 변수의 동치를 연결 리스트로 표현하고, 동치 부류를 스택을 이용하여 출력할 때 스택의 변화를 순서대로 그리시오. 그리고 최종 출력 결과도 기술하시오. (5점)
    0≡3, 2≡6, 4≡5, 3≡1, 5≡2

제4문 (15점)

다음 설명과 같이 레드－블랙 트리는 2－3－4 트리로 변환하여 표현할 수 있다. 물음에 답하시오. (단, 레드－블랙 트리에서 블랙 노드와 링크는 단일 실선(－), 레드 노드와 링크는 이중 실선(＝)으로 표시한다) (총 15점)
○레드－블랙 트리에서 자식이 모두 블랙인 블랙 노드는 2－3－4 트리에서 이 블랙 노드에 저장된 키가 1개 있는 노드가 되어 자식이 2개 있는 2－노드로 표현된다.
○레드－블랙 트리에서 자식 중 하나만 레드인 블랙 노드는 2－3－4 트리에서 이 블랙 노드에 저장된 키와 자식 중 레드 노드에 저장된 키가 한 노드에 저장되어 자식이 3개 있는 3－노드로 표현된다.
○레드－블랙 트리에서 자식 둘이 모두 레드인 블랙 노드는 2－3－4 트리에서 이 블랙 노드에 저장된 키와 두 자식 노드에 저장된 키 2개가 한 노드에 저장되어 자식이 4개인 4－노드로 표현된다.
  1. (1) 비어 있는 레드－블랙 트리에 데이터 1, 2, 3, 4, 5를 차례대로 하나씩 삽입할 때마다 변경되는 트리를 순서대로 그리시오. (5점)
  2. (2) 1)에서 최종적으로 변경된 레드－블랙 트리를 위의 설명에 따라 2－3－4 트리로 바꾸어 그리시오. (5점)
  3. (3) 2)에서 그린 2－3－4 트리에서 데이터 1이 삭제될 때 2－3－4 트리가 어떻게 변경되는지 나타내고, 변경된 2－3－4 트리와 대응되는 레드－블랙 트리를 그리시오. (5점)