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

다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의 1번 위치부터 14번 위치까지 저장되어 있다. 이 배열에서 최대값을 제거하는 연산을 3번 수행한 후, 최대힙의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산 시 가급적 최대힙의 내용 변경을 최소화 한다고 가정한다)

(데이터)

[200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38]

다음과 같은 재귀적(recursive) 그래프 탐색 알고리즘을 반복적(iterative) 알고리즘으로 구현하고자 한다. 그래프가 인접리스트(adjacency list)에 저장되어 있다고 가정할 때, 구현을 위하여 필요한 자료구조와 전체 그래프를 순회(traversal)하는 알고리즘의 시간복잡도(time complexity)를 옳게 나타낸 것은? (단, 정점의 집합은 V, 간선의 집합은 E라고 가정한다)

(알고리즘)
void search( vertex v ) 
{
    visited[v] = 1 ; 
    for each vertex w adjacent to v 
       if ( !visited[w] )   search( w ) ; 
}

가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?

그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?

ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다.

ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.

ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 v²개이다.

ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.

ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O(v²)이다.

해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은?

ㄱ. n개의 자료가 있을 때 자료의 탐색에 걸리는 시간은 O(logn)이다.

ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓(bucket)에 사상(mapping)시킨다.

ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다.

ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다.

ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다.

스택, 큐, 리스트 자료구조에 대한 설명으로 옳지 않은 것은?

깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A － B의 값은? (단, 루트노드의 레벨은 1로 한다)

6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리(binary search tree)를 만들 때, 만들어진 이진 탐색트리의 높이가 가장 낮은 것은?

다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 데이터 ‘JAN’을 삽입한 결과로 옳은 것은?

다음과 같은 이진트리(binary tree)에서 전위순회(preorder traversal)와 중위순회(inorder traversal)를 했을 때, 두 순회 결과에서 노드 값의 방문 순서가 일치하는 횟수는? (전위순회의 k번째 노드값과 중위순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다)

점근적 표기법(asymptotic notation)에 관한 사칙연산으로 옳지 않은 것은?

배열 A에 오름차순으로 저장된 데이터를 이진탐색(binary search) 하기 위하여 반복적(iterative) 알고리즘을 이용하여 기술하였다. ㉠, ㉡에 들어갈 적당한 명령은?

procedure BINARYSEARCH(A, n, x, j)
   lower ← 1 ; upper ← n ;
   while lower ≤ upper do
      mid ← the middle element;
      case
          : x > A(mid):        ㉠        ;
          : x < A(mid):        ㉡        ;
          : else : j ← mid ; return;
            end
   end
   j ← 0 ;
end

㉠ ㉡

다음 데이터를 퀵정렬 (quick sort)하려고 한다. 퀵정렬 1단계 과정이 끝난 후, 피봇키(pivot key)를 중심으로 좌측에는 피봇키보다 작은 수, 우측에는 피봇키보다 큰 수들로 데이터가 분할된 상태를 올바르게 나타낸 것은? (단, 피봇키는 가장 왼쪽에 있는 값으로 한다)

(초기데이터)

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

8

1

4

9

6

3

5

2

7

0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

K [1 : 2, 1 : 3, 1 : 2]로 선언된 3차원 배열을 행 우선순서(row major order)로 1차원 배열에 저장했을 때, 9번째에 저장되는 요소는?

다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 모든 원소들의 값이 0인 행렬을 상삼각 행렬(upper triangular matrix)이라고 한다.

A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가?

다음 전위식(preorder expression)으로 표현된 수식을 후위식(postorder expression)으로 변환하였다. 변환된 수식의 4번째 연산자는?

(전위식) － + － AB * / CDEF

스택을 일차원 배열 stack[0 : 99]를 이용하여 구현하고자 한다. top 변수의 초기값은 － 1로 설정하며, top이 － 1이면 스택은 비어있다는 것을 나타낸다. C 언어를 이용하여 스택에 데이터를 추가하는 함수 push()와 삭제하는 함수 pop()을 다음과 같이 작성하였을 때, ㉠과 ㉡에 들어갈 내용은?

 void push(int * top, int data) { // 스택에 data를 추가
    if ( * top >= 99) { stack _ full() ; return ; }
     ㉠;
}

 int pop(int * top) { // 스택에서 데이터를 삭제 후 반환
    if ( * top == － 1) { return stack _ empty() ; }
     ㉡;
}

㉠ ㉡

원형 연결리스트(circular linked list)의 길이를 계산하기 위한 C함수를 작성하려고 한다. 밑줄 친 ㉠과 ㉡부분에 알맞은 명령은?(단, 원형 연결리스트의 길이는 노드의 개수로 정의하고, 원형 연결리스트의 시작 포인터는 ptr이라고 가정한다)

struct list_node {
      char data ;
      struct list _ node * link;
 }
typedef struct list_node * list _ pointer;
int CListLength(list_pointer ptr){
  list _ pointer temp ; 
  int count = 0 ; 
  if (   ㉠   ) { 
    temp = ptr ; 
    do { count + + ; 
    } while (    ㉡    ) ; 
  } 
  return count; 
}

㉠ ㉡

n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결리스트(singly linked list)로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?

자료들이 단순 연결리스트(singly linked list)에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은?

메모리주소	data	link
2000	A	2020
2010	B	2030
2020	C	2010
2030	D	0