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

깊이가 k인 포화이진트리(full binary tree)의 비단말노드의 개수에서 단말노드의 개수를 뺀 값으로 옳은 것은? (단, k > 0)

다음 ‘하노이타워’ 프로그램을 수행한 결과에서 8번째 줄에 출력되는 문장으로 옳은 것은?

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to)
{
    if( n==1 ) printf("원판 1을 %c에서 %c로 옮긴다. \n", from, to);
    else {
	hanoi_tower(n-1, from, to, tmp);
	printf("원판 %d을 %c에서 %c로 옮긴다. \n", n, from, to);
	hanoi_tower(n-1, tmp, from, to);
    }
}
void main()
{
    hanoi_tower(4, 'A', 'B', 'C');
}

개수가 정해진 자연수를 크기순으로 저장하고 탐색하기에 가장 적절한 자료구조와 탐색방법으로 옳게 짝지어진 것은?

다음 배열에 저장된 데이터에 대해 내림차순으로 히프정렬(heap sorting)을 수행한다. 첫 번째 데이터를 출력하고 히프를 재구성 한 후에 배열의 6번째에 있는 데이터로 옳은 것은? (단, 배열의 첫 번째 인덱스는 1이다)

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

다음 구조체를 갖는 이중 연결 리스트에서 A, B, C는 각각 노드를 가리키는 포인터 변수이다. 노드 B를 삭제하기 위한 명령으로 옳지 않은 것은?

struct Dlist { int data; struct Dlist *left; struct Dlist *right; }; 

다음 정수들을 순서대로 삽입하여 AVL트리를 구성하였다. AVL트리의 구성 과정 중에 사용된 회전방법들로 옳은 것은?

20, 16, 15, 9, 7, 12, 10, 1, 13, 5

다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 것이다. 이에 대한 위상 정렬(topological sorting)의 결과로 옳은 것은? (단, 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑된다)

	a	b	c	d	e	f
a		1	1
b			1	1
c				1	1
d						1
e				1		1
f

다음은 A, B, C, D 네 개의 수가 사용된 후위 표기식이다. 이 수식을 스택을 이용하여 계산할 때, 스택에 여섯 번째로 저장(push)되는 값으로 옳은 것은?

후위 표기식 : A B C ＋ D ＊ －

다음 원형 큐(circular queue)에 대하여 연산들(가 ～ 바)이 차례대로 수행된 후에 큐의 상태로 옳은 것은? (단, front는 0이고 rear는 3이며, 원형 큐의 공백과 만원은 별도의 카운터를 두어서 처리한다)

원형큐 :

0	1	2	3	4
	A	B	C

가. D를 삽입 나. E를 삽입

다. 두 개의 원소를 삭제 라. F를 삽입

마. 하나의 원소를 삭제 바. G를 삽입

이중해싱(double hashing)을 이용하는 크기가 5인 해시테이블(hash table)에 데이터 6, 3, 8, 18이 순서대로 입력된다. 마지막 데이터인 18이 입력될 때 발생하는 충돌의 횟수는? (단, 1차 해싱함수는 h(k) = k mod 5이고, 2차 해싱함수는 h'(k) = 5-(k mod 5) 이다)

완전 이진트리(complete binary tree)를 배열에 저장할 때, 루트 노드를 배열 A[1]에 저장하고 나머지 노드들은 트리의 레벨순서에 따라 왼쪽에서 오른쪽으로 연속적으로 저장한다. 노드 A[k]와 관계된 노드를 찾는 규칙이 바르게 짝지어지지 않은 것은?

다음 C 코드에서 foobar 함수가 하는 일을 올바르게 설명한 것은?

struct list_t {
    int   data;
    struct list_t *link;
};
typedef struct list_t *list_p;
 
void foobar(list_p *ptr, struct list_t *node)
{
    if (*ptr == NULL) {
        *ptr = node;
        node->link = node;
    } else {
        node->link = (*ptr)->link;
        (*ptr)->link = node;
    }
}

다음 정수들을 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 단말 노드(leaf node)에 해당되는 값들로 옳은 것은?

45, 36, 62, 2, 16, 51, 75, 69

크기가 16인 다음 배열 E에 정수가 저장되어 있다.

i	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]	[13]	[14]	[15]
E[i]	3	5	6	8	10	13	15	16	17	21	23	26	27	29	31	33

C언어로 표현된 함수 func를 이용하여 정수 K가 저장된 위치를 검색하려고 한다. func(E, 0, 15, 27)를 호출했을 때, 검색이 완료되기까지 ㉠ 문장이 수행되는 횟수는?

int func(int E[ ], int first, int last, int K)
{
   int mid;
   if (last < first) return –1;
   else { 
      ㉠ mid = (first + last) / 2;   
      if (K == E[mid]) return mid;
      else if (K < E[mid]) return func(E, first, mid-1, K);
      else return func(E, mid+1, last, K);
   }
}

이중 연결 리스트(doubly linked list)에서 포인터 p가 가리키는 노드의 오른쪽에 포인터 newNode가 가리키는 노드를 삽입할 때, 연산의 순서가 바르게 나열된 것은? (단, llink는 왼쪽 노드를 가리키는 포인터이고 rlink는 오른쪽 노드를 가리키는 포인터이다)

ㄱ. p->rlink = newNode;

ㄴ. newNode->llink = p;

ㄷ. newNode->rlink = p->rlink;

ㄹ. p->rlink->llink = newNode;

다음 AOE(Activity On Edge) 네트워크에서 작업의 완료시간을 단축하면 전체 프로젝트의 완료시간이 단축되는 단일 작업으로 옳은 것은?

다음 2－3 트리에 47을 삽입한 결과에 대한 설명으로 옳지 않은 것은?

다음 이진트리를 전위순회(preorder traversal), 중위순회(inorder traversal), 그리고 후위순회(postorder traversal) 순서로 각 노드를 방문하였다. 각각의 순회에서 7번째에 방문한 노드를 순서대로 나열한 것은?

다음 그래프로부터 생성되는 최소 비용 신장 트리(minimum cost spanning tree)의 비용은?

다음은 원형 연결 리스트(circular linked list)의 길이를 구하는 함수이다. 원형 연결 리스트의 마지막 노드를 last가 가리키고 있을 때, ㉠에 들어갈 문장으로 옳은 것은?

int length(listPointer last)
{
	listPointer temp = last;
	int count = 0;
	if (last) {
		for(count = 1;     ㉠    ; count++)
			temp = temp->link;
	}
	return count;
}