7급 국가직 자료구조론 2019년 기출문제

m원 탐색 트리(m-way search tree)에 대한 설명으로 옳지 않은 것은?

다음은 C 언어로 구현한 원형 큐(circular queue) 삽입 알고리즘이다. ㉠, ㉡에 들어갈 내용으로 옳은 것은?

#define MAX_QUEUE_SIZE 10
int queue[MAX_QUEUE_SIZE];
int front = rear = -1;

void addq(int front, int *rear, int item) {
           ㉠        
   if (         ㉡          ) {
      printf(“Queue is full!!\n”); 
      return -1;
   }
   queue[*rear] = item;
}

㉠ ㉡

다음 그래프를 Kruskal 알고리즘을 이용하여 최소 비용 신장 트리로 만들 때 선택되지 않는 간선은? (단, 알고리즘은 노드 A에서 시작한다)

다음은 이진 트리(binary tree)이다. 매개변수 ptr로 함수 func를 호출하였을 때, 결과 값은? (단, ptr은 루트 노드에 대한 포인터이다)

struct node {
    int data;
    struct node *left;
    struct node *right;
};
int func(struct node *ptr) {
    if (ptr == NULL)
       return 0;
    else if (ptr->left == NULL
		     && ptr->right == NULL)
       return 1;
    else
       return (ptr->data + func(ptr->left)
		              + func(ptr->right));
}

$n\times n$ 하삼각 행렬은 총 $n(n+1)/2$개의 원소를 갖는다. 원소 $a_{ij}$ (1 ≦ i ≦ j ≦ n)가 최소 공간을 사용하도록 1차원 배열 $b[k]$에 행우선순서(row-major order)로 저장했을 때, 하삼각 행렬의 원소 $a_{ij}$가 저장될 배열 $b[k]$의 색인 $k$를 계산하는 식으로 옳은 것은? (단, $i$는 행 색인 값, $j$는 열 색인 값으로 하고, 1차원 배열 $b$에는 하삼각 행렬의 0 값은 저장되지 않으며, $b$의 색인 $k$의 값은 0부터 시작한다)

정방 행렬(square matrix) 중에서 대각선보다 위의 모든 원소가 0인 경우를 특별히 하삼각 행렬(lower triangular matrix)이라 하며, 다음은 $4\times 4$ 하삼각 행렬의 예이다. (단, $a_{ij}$는 0이 아닌 어떤 실수 값을 의미하고, 0은 반드시 0이어야 함을 의미한다)

$\left[\begin{array}{cccc}{a}_{11}& 0& 0& 0\\ a_{21}& a_{22}& 0& 0\\ a_{31}& a_{32}& a_{33}& 0\\ a_{41}& a_{42}& a_{43}& a_{44}\end{array}\right]$

다음과 같은 방향 그래프에 대하여 Dijkstra의 알고리즘을 적용하여 최단경로를 구하고자 한다. 노드 a에서 시작하여 노드 f로 가는 최단 경로를 찾아 가는 과정에서 노드 a에서부터 다른 노드까지 최단 경로를 차례로 알게 된다. 이 과정에서 알게 되는 최단 경로의 노드 순서로 옳은 것은?

다음과 같이 배열에 저장된 데이터에 대하여 내림차순으로 히프 정렬(heap sort)을 수행할 때, 첫 번째 데이터를 출력하고 히프를 재구성 한 후에 배열의 여섯 번째에 있는 값은? (단, 배열의 첫 번째 색인 값은 1이다)

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
21	37	22	17	11	30	5	10	9

6개 외부 노드의 가중치가 각각 q₁ ＝ 3, q₂ ＝ 4, q₃ ＝ 6, q₄ ＝ 8, q₅ ＝ 10, q₆ ＝ 15인 허프만 트리의 설명으로 옳은 것은? (단, 허프만 트리는 ${\sum }_{1\le i\le n}^{}{q}_i{d}_i$가 최소가 되는 트리로서, $q_i$는 외부 노드의 가중치이고 $d_i$는 루트 노드에서부터 외부 노드까지의 거리이며, n은 외부 노드의 수이다)

다음과 같이 배열에 저장된 입력 자료들을 퀵 정렬(quick sort)로 오름차순 정렬하고자 한다. 정렬과정에서 단계별 정렬 순서로 나타날 수 없는 것은? (단, 피봇(pivot)은 마지막 레코드로 선택한다)

15

3

1

35

20

4

18

26

다음과 같이 중위 표기법(infix notation)으로 되어 있는 수식을 후위 표기법(postfix notation)으로 변환하기 위해 스택을 이용한다. 변환 과정에서 스택에 토큰이 가장 많이 쌓여 있을 때의 스택 내 연산자 토큰 수는?

a*(b-c*d)/e

그래프에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 무방향 그래프(undirected graph)를 인접행렬(adjacency matrix)로 표현하면 주대각선을 중심으로 상위 행렬과 하위 행렬이 대칭이 된다.

ㄴ. 사이클이 없고 n － 1개의 간선(edge)을 갖는 연결 그래프(connected graph)를 트리(tree)라고 한다.

ㄷ. n개의 정점(vertex)을 가진 방향 그래프의 최대 간선 수는 $\frac{n(n+1)}{2}$ 개이다.

ㄹ. 경로를 구성하는 간선의 수를 길이라고 할 때, 방향 그래프에서 사이클(cycle)의 길이는 항상 3 이상이다.

일반 리스트(general list) $L=(e_1,e_2,...,e_n)$에 대해, 함수 head(L)은 첫 번째 원소인 $e_1$을 반환하고, 함수 tail(L)은 리스트 $(e_2,e_3,...,e_n)$를 반환한다고 할 때, 다음과 같은 리스트 A에 대한 함수의 수행 결과 중 문자 ‘c’를 반환하는 것은?

A = ((a, b), c, d)

다음은 단순 연결 리스트(singly linked list)에서 특정 값(value)을 가진 노드의 개수를 반환하는 C 함수이다. ㉠, ㉡에 들어갈 내용으로 옳은 것은?

struct node {
   int data;
   struct node *link;
};
int countNode(struct node *ptr, int value) 
{
   int count = 0;
   while (         ㉠         ) {
      if ( ptr->data == value ) count++;
                ㉡         
   }
   return count;
}

㉠ ㉡

다음은 Fibonacci 수열을 계산하는 C 함수이다. 함수 fibonacci(4)를 호출하였을 때 화면에 출력되는 숫자의 순서로 옳은 것은?

int fibonacci( int n )
{
   printf(“%d∖n”, n);

   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( fibonacci( n - 1 )
		                    + fibonacci( n - 2 ) );
}

다음은 이진 탐색을 수행하는 C 함수이다. 이 함수를 사용하여 0부터 20까지의 정수가 차례대로 저장되어 있는 배열 b에 대한 이진 탐색을 수행할 때, key 값과 a[middle] 값을 비교하는 횟수가 다른 것은? (단, 배열의 색인은 0부터 시작한다)

int binarySearch(int *a, int key, int low, 				  int high)
{
   int middle;
   while (low <= high) {
      middle = (low + high) / 2;
      if (key == a[middle]) 
         return middle;
      else if (key > a[middle]) 
         low = middle + 1;
      else 
         high = middle - 1;
   }
   return -1;
}

시간 복잡도 함수에 대한 점근 표기법으로 옳은 것만을 모두 고르면?

ㄱ. n²ⁿ + 6·2ⁿ = 𝜪(n2ⁿ⁾

ㄴ. n²/log n = 𝜣(n2⁾

ㄷ. n³2ⁿ + 6n²3ⁿ = 𝜪(n2²n⁾

ㄹ. 6n³ + log n = 𝜪(n3⁾

다음 그래프에는 음의 가중치가 존재한다. 이 그래프에서, 노드 A에서 노드 F로의 최단 경로를 구하고자 할 때, 최소 비용은?

다음은 단순 연결 리스트(singly linked list) L에서 리스트의 원소를 역순으로 바꾸는 함수이다. 함수에서 ㉠ 부분에 들어갈 프로그램 코드(code)로 옳은 것은?

typedef struct node{
   struct node *link;
   char data;
} listNode;
typedef struct{
   listNode *head;
} linkedList;

void reverse(linkedList *L)  
{  
   listNode *p, *q, *r;
   p = L->head; 
   q = r = NULL; 
   while ( p != NULL)  {
      r = q;
      q = p;
      p = p->link;
            ㉠        
   }
   L->head = q;
}

주어진 정수 배열 {26, 13, 77, 61, 35, 11, 8, 48, 15, 19}에 대한 합병 정렬(merge sort)의 순환 알고리즘(recursive algorithm)을 다음과 같이 구현하였다. 이 프로그램의 수행 과정에서 형성되는 배열의 순서로 옳지 않은 것은?

#include <stdio.h>
#define MAX 10
void merge( int list[], int temp[], int left, 		         int middle, int right)
{
    int i=left, j=middle+1, k=left, t;
    for( ; i <= middle && j <= right ;  ) {
          if( list[i] <= list[j] )
		temp[k] = list[i++];
          else
		temp[k] = list[j++];
          k += 1;
     }
     if( i > middle ) {
         for( t = j ; t <= right ;)
		temp[k++] = list[t++];
     } else {
         for( t = i ; t <= middle ;)
		temp[k++] = list[t++];
     }
     for( t = left ; t <= right ; t++ )
          list[t] = temp[t];
}

void mergeSort( int list[], int temp[], int left, 		       int right)
{
     int middle = 0;
     if( left < right ) {
          middle = (left+right)/2;
          mergeSort(list, temp, left, middle);
          mergeSort(list, temp, middle+1, right);

          merge(list, temp, left, middle, right);
     }
}

int main(){
     int source[10]={26, 13, 77, 61, 35, 11, 8, 			   48, 15, 19}; 
     int temp[10] = {0x0,};

     mergeSort(source, temp, 0, 9);
}

다음은 노드의 차수가 5인 B－트리의 현재 상태를 표현한 것이다. 현 상태에서 값 9를 삭제하였을 때, 결과 트리에 존재하는 노드 수를 종류별로 옳게 나타낸 것은? (단, n－노드란 (n － 1)개의 키를 저장한 노드를 의미한다)

2－노드 3－노드 4－노드 5－노드