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

후위 표기법(postfix notation)으로 표현된 다음 수식의 계산 결과는?

2 3 + 2 * 2 1 + 3 / -

노드의 개수가 177인 완전 이진 트리(complete binary tree)에서 마지막 레벨(level)에 위치한 노드의 개수는? (단, 루트 노드는 첫 번째 레벨에 위치한다)

다음 C 언어 함수를 이용하여 asterisk(9)를 수행할 때 출력되는 ‘*’의 개수는?

#include <stdio.h>

void asterisk(int i)
{
   if(i > 1){
      asterisk(i/3);
      asterisk(i/3);
   }
   printf("*");
}

가장 낮은 자릿수(LSD : Least Significant Digit) 우선 방식의 기수 정렬(radix sort)을 이용하여, 다음과 같이 배열에 저장된 10진수 데이터를 오름차순으로 정렬하고자 한다. 오른쪽에서 두 번째 자릿수(digit) 기준의 정렬 단계 후에 위치 [3]에 있는 데이터로 옳은 것은? (단, 각 단계별 정렬의 기준이 되는 자릿수는 0에서 9까지의 값을 가진다)

위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
데이터	307	424	132	216	241	835	546	630

해시 테이블 HT의 크기는 11이고 0부터 10까지의 인덱스를 가진다. 해시 함수 h(x)는 제산 함수로서 h(x) ＝ x mod 11로 표현된다. 충돌 해결책으로는 이차 조사법(quadratic probing)을 사용한다. 해싱을 통해 해시 테이블에 저장할 레코드들의 키 값 순서는 다음과 같다. 마지막 레코드가 저장되는 해시 테이블 위치는? (단, 첫 번째 레코드가 저장되기 전에 해시 테이블은 비어 있고, 해시 테이블 버킷(bucket)당 슬롯(slot) 수는 1개이다)

51, 27, 70, 55, 13, 2, 37, 23, 33

시작 정점이 A일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS : Depth First Search) 및 너비 우선 탐색(BFS : Breadth First Search)의 방문 순서로 옳은 것은? (단, 인접한 정점들은 알파벳 순서로 방문한다)

다음 C 프로그램의 실행 결과로 첫 번째 줄에 출력되는 값과 두 번째 줄에 출력되는 값의 차이 값은? (단, int로 선언된 정수형 변수는 4바이트를 차지하고 char로 선언된 문자형 변수는 1바이트를 차지한다)

#include <stdio.h>

void main()
{
   struct node {
      int id;
      char name[8];
      int score;
   } A[10];

   printf("%d\n", &A[0]);
   printf("%d\n", &A[4]);
}

다음 AVL 트리에 정수 23을 삽입하면 AVL 트리로서의 균형이 깨진다. 회전을 통해 이 트리를 AVL 트리로 변환한 후에 전위순회(preorder traversal)를 수행하였을 때 노드 방문 순서는?

다음 가중 그래프(weighted graph)는 9개의 정점과 1부터 19까지의 가중치(비용)를 갖는 19개의 간선으로 구성되어 있다. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선을 순서대로 나열한 것은?

허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19개 문자로 구성된 문자열을 압축하였다. 압축된 문자열에 사용된 비트 수는?

a

b

a

b

a

d

c

d

a

b

a

c

d

a

b

c

d

d

e

C 언어에서 행 우선(row major) 순서로 저장되는 2차원 배열 a[4][5]가 있을 때, 나타내는 원소가 다른 것은?

다음 알고리즘의 시간 복잡도를 빅세타($\Theta$) 표기법으로 표현한 것은? (단, n > 0)

int iterate(int n)
{
   int i, count = 0;
   for (i = 1; i < n; i *= 2) 
      count++;
   return count;
}

다음은 동적 메모리 할당을 통해 구조체 공간을 확보하고 이름과 학번을 입력받아 구조체에 저장하는 C 언어 함수이다. ㉠, ㉡에 들어갈 내용으로 옳게 짝지어진 것은?

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

struct student{
   char name[20];
   int id;
};

struct student *alloc()
{
   struct student *p;
   p =        ㉠        ;
   if(p==NULL){
      printf("Memory allocation error.");
      return p;
   }
   printf("Student name?\n");
   gets(p->name);
   printf("Student id?\n");
   scanf("%d",    ㉡   );
   return p;
}

㉠ ㉡

다음 그래프의 위상 정렬(topological sorting) 결과로 나올 수 있는 위상 순서(topological order)로 옳지 않은 것은?

공백 상태인 이진 탐색 트리(binary search tree)에 1부터 5까지의 정수를 삽입하고자 한다. 삽입 결과, 이진 탐색 트리의 높이가 가장 낮은 삽입 순서는?

다음 최대 힙(max heap)에 13을 삽입하는 연산을 수행한 후에 루트 노드를 삭제하는 연산을 수행하였다. 그 결과, 루트 노드의 오른쪽 자식 노드의 값으로 옳은 것은? (단, 삽입 및 삭제 연산은 최대 힙으로의 복원 과정을 포함한다)

다음은 구현하고자 하는 원형 큐(circular queue)에 대한 <조건>과 <설명>이다. <설명>의 괄호 안에 들어갈 수로 옳게 짝지어진 것은?

	<조 건>
○ 크기가 6이고 인덱스가 0부터 5까지인 배열로 구현된다. ○ 공백 상태에서만 front와 rear의 값이 서로 같으며, 그 외에는 값이 서로 다르다. ○ (front + 1) mod 6은 다음에 삭제할 원소 위치를 가리킨다. ○ (rear + 1) mod 6은 다음에 삽입할 원소 위치를 가리킨다.

	<설 명>
○ 최대 ( ㉠ )개의 원소를 저장할 수 있다. ○ front = 5이고 rear = 3인 경우 저장된 원소 수는 ( ㉡ )개이다. ○ front = ( ㉢ )이고 rear = 2인 경우는 포화 상태를 의미한다.

㉠ ㉡ ㉢

다음 C 언어 함수를 이용하여 do_something(660, 735)를 수행한 결과 값은?

unsigned int do_something(unsigned int x, unsigned int y)
{
   while (y!=0) {
      int temp;
      temp = x % y;
      x = y;
      y = temp;
   }
   return x;
}

다음 이진 트리에 대하여 전위순회(preorder traversal), 중위순회(inorder traversal), 후위순회(postorder traversal)를 수행하였다. 3가지 순회 방법 중 2가지 이상에서 방문 순서가 동일한 노드 수는? (예를 들어, 3개의 노드 A, B, C를 갖는 이진 트리에서 전위순회 : B-A-C, 중위순회 : A-B-C, 후위순회 : A-C-B의 결과를 얻었다면, 중위순회 및 후위순회에서 노드 A에 대한 방문 순서가 동일하고 전위순회 및 중위순회에서 노드 C에 대한 방문 순서가 동일하므로, 2가지 이상에서 방문 순서가 동일한 노드 수는 2개 이다)

Dijkstra 알고리즘을 이용하여 다음 그래프의 정점 A에서 각 정점으로의 최단경로를 구할 때, 최단경로 발견 순서가 정점 G 바로 다음인 정점은? (단, 간선 옆의 수는 각 정점들 사이의 거리를 나타낸다)