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

힙정렬(heap sorting)로 다음 데이터를 내림차순으로 정렬할 때 만들어지는 최초의 힙구조는?

7, 1, 15, 13, 19

다음의 인접행렬로 표시되는 그래프 G = (V, E)는?

(단, False는 from에서 to까지의 간선이 없고, True는 from에서 to까지의 간선이 있음을 의미한다)

to from	a	b	c	d
a	False	False	True	False
b	True	False	False	False
c	False	False	False	True
d	True	False	True	False

다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지도를 그래프로 표현한 것이다. 최소비용 신장 트리를 구하는 Kruskal 알고리즘을 이용하여 초고속철도를 건설하려고 한다. 4번째로 건설해야 할 구간은?

크기가 10인 해시 테이블을 배열을 이용하여 만든다고 가정하자. 해시함수로 h(k) = k mod 10을 사용한다. 여기서 mod는 모듈로(modulo) 함수를 의미한다. 데이터가 다음과 같은 순서로 입력된다고 할 때 발생하는 충돌(collision) 횟수의 총 합으로 옳은 것은? (단, 배열의 인덱스는 [0]~[9]까지이고, 처음에 배열은 비어 있으며, 충돌을 해결하기 위해서는 배열의 다음 빈 공간에 데이터를 입력하는 선형 조사법(linear probe)을 사용한다고 가정한다)

70, 17, 26, 69, 72, 53, 31, 27, 23, 13

다음 이진 탐색트리(binary search tree)에서 루트(root)노드가 삭제된 후의 상태는?

최대힙(max heap)으로 우선순위큐를 구현하려 한다. 우선순위를 나타내는 9개의 데이터가 큐에 다음과 같은 순서대로 삽입되었다. 1개의 데이터가 큐에서 삭제된 후, 재 정렬된 힙에서 가장 마지막 원소는 무엇인가? (단, 숫자가 클수록 우선순위가 높다고 가정한다)

24, 17, 29, 22, 20, 31, 27, 18, 21

다음을 참조하여, 피봇(pivot)값을 이용하는 정렬 방법과 아래의 ㉠ ~ ㉤에 들어갈 값이 올바르게 나열된 것은?

데이터 = {60, 50, 13, 92, 52, 2, 69, 30, 78, 42}

단계1) 피봇값 : ( ㉠ )

－ 왼쪽으로부터 비교 : ( ㉡ )에서 비교 멈춤

－ 오른쪽으로부터 비교 : ( ㉢ )에서 비교 멈춤

－ ( ㉣ )과(와) ( ㉤ )의 저장 위치 교환

정렬 방법 ㉠ ㉡ ㉢ ㉣ ㉤

다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그래프의 간선들 간의 거리를 나타낸다. 표에서 무한대 기호 $\infty$는 해당 간선이 없음을 나타낸다. 정점 A에서 나머지 네 개의 정점들에 도달하기 위한 최단경로들의 합은 얼마인가?

to from	A	B	C	D	E
A	0	2	5	$\infty$	3
B	$\infty$	0	$\infty$	4	10
C	$\infty$	$\infty$	0	6	2
D	$\infty$	$\infty$	$\infty$	0	$\infty$
E	$\infty$	$\infty$	1	2	0

이진 탐색트리(binary search tree) T에서 k보다 큰 키들의 개수를 찾는 클래스 함수 numGreaterThan(T, k)을 작성한다고 가정하자. 트리에 포함된 모든 키들은 상이하고, 각 노드 x는 링크 필드인 left 및 right와 데이터 필드인 data를 가지며, 추가적으로 하나의 데이터 필드 numDesc를 포함한다. numDesc는 x를 루트(root)로 하는 부분 트리에 포함된 모든 키들의 개수로 초기화되어 있다. 아래 코드에서 밑줄 친 부분에 해당되는 문장은 무엇인가?

int numGreaterThan(T, k)
{
   if (T == NULL) return 0;
   else if (T.key <= k) return numGreaterThan(T.right, k);
   else return _________________________________;
}

다음과 같은 순서로 입력되는 데이터에 대해 올바르게 AVL-트리를 구성한 것은?

A

F

E

C

B

D

입력 데이터의 개수 $n$에 대한 시간 복잡도가 가장 큰 것은?

3차원 배열 A(1:5, 2:4, 1:3)를 1차원 배열 B(1:45)에 행우선으로 저장하는 경우 A(2, 3, 2)가 저장되는 B의 인덱스는?

값이 0인 원소들의 비율이 90%인 1,000 × 1,000 희소 행렬 표현에 관한 설명 중 옳은 것은?

스택(stack) S와 원형 큐(circular queue) Q의 초기 배열 상태가 다음과 같다고 가정하자. 여기서 T는 스택의 top을, R과 F는 큐의 rear와 front를 각각 나타낸다. 단, 스택에 관한 클래스 함수 push( )는 스택에 삽입, pop( )은 스택의 top이 가리키는 값을 삭제, top( )은 스택의 top이 가리키는 값을 반환한다. 큐에 관한 클래스 함수 front( )는 큐의 front가 가리키는 값의 반환, remove( )는 큐에서 front가 가리키는 값의 삭제를 나타낸다.

		T								R			F
S :	3	6						Q :	2				7	4

다음 문장들이 순서대로 실행된 후 S와 Q의 상태는?

S.push(Q.front()); S.push(S.top()); S.pop();

Q.remove(); S.push(Q.front());

①

S :

3

6

Q :

2

7

4

②

S :

3

6

7

Q :

2

4

③

S :

3

6

7

4

Q :

2

7

4

④

S :

3

6

7

4

Q :

2

4

큐(queue)를 연결리스트로 구현하는 경우 일반적으로 front와 rear 등 2개의 포인터를 사용한다. 만약 리스트의 포인터를 하나밖에 사용할 수 없다면 가장 효율적인 구조는? (단, 큐에 A, B, C, D의 순서로 입력되었고, 역원형리스트는 데이터가 입력된 순서의 역순으로 만든 원형리스트를 의미한다고 가정한다)

다음 C 함수에 대하여 F(L, 0, n-1)를 수행할 경우 시간 복잡도는?

int F(int L[ ], int p, int q)
{
   if (p<q)
   { int r, f1, f2;
     r = (p+q)/2;
     f1 = 2＊F(L, p, r);  
     f2 = 2＊F(L, r+1, q);
     return f1+f2;
   }
   else if (p == q)
      return L[p]＊L[p];
   else
      return 0;
}

다음과 같이 정렬된 데이터에서 이진탐색(binary search)을 수행하는 경우 비교 횟수가 가장 많은 데이터는?

(단, 배열의 인덱스는 내림(floor)함수를 적용하여 구한다)

4, 6, 11, 12, 15, 17, 18, 20, 21

여러 명의 고객이 한 개의 창구를 이용하여 서비스를 받으려고 한다. 사용자들이 서비스를 받기 위해 대기하는 구조로서 큐를 사용한다. 이미 서비스를 받고 있는 고객이 있다면, 큐에서 기다려야 한다. 다음과 같은 순서로 다섯 개의 서비스 요청이 동시에 도착했을 때 이미 서비스를 받고 있던 고객은 없다고 가정한다. 다음 ㉠ ~ ㉢의 각 항목에 대한 값이 올바르게 짝지어진 것은?

(단, 사각형 내의 숫자는 서비스 요청을 수행하는데 소요되는 시간을 의미한다)

10

5

8

50

1

㉠ 위와 같은 순서로 고객들이 동시에 서비스를 신청할 때 모든 고객이 큐에서 대기하는 전체 시간

㉡ 최소 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간

㉢ 최대 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간

㉠ ㉡ ㉢ ㉠ ㉡ ㉢

다음과 같은 인접리스트로 표현된 그래프에 대해 노드 2를 시작 정점으로 너비우선탐색(breadth first search)을 수행했을 때 노드들의 방문 순서를 올바르게 나열한 것은?

다음 재귀(recursion) 함수는 이진트리의 루트(root)를 가리키는 포인터를 사용하여 특정한 작업을 수행한다. 구체적으로 어떤 작업을 수행하는가?

typedef struct node_struct {
    int data; 
    struct node_struct ＊left, ＊right;
} node_t;
void JOB_Tree(node_t ＊root) {
    node_t ＊temp;
    if (root == NULL) return;
    temp = root->right;
    root->right = root->left;  root->left = temp;
    JOB_Tree(root->left); JOB_Tree(root->right); 
}