2009 국가직 7급 자료구조론 문제 정답

 

자료구조론정답(2021-03-30 / 260.0KB / 195회)

 

 자료구조론 봉 책형 1 쪽 자료구조론 문 1. 다음과 같이 14개의 정수가 최대힙(max heap)을 표현하는 배열의 1번 위치부터 14번 위치까지 저장되어 있다. 이 배열에서 최대값을 제거하는 연산을 3번 수행한 후, 최대힙의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산 시 가급적 최대힙의 내용 변경을 최소화 한다고 가정한다) (데이터) [200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38] ① [72, 63, 62, 60, 52, 38, 37, 22, 16, 11, 5] ② [72, 52, 63, 38, 16, 60, 62, 37, 22, 11, 5] ③ [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22] ④ [72, 52, 63, 16, 38, 60, 62, 5, 11, 37, 22] 문 2. 다음과 같은 재귀적(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 ) ; } ① queue, O( |E| ) ② stack, O( |V|2 ) ③ stack, O( |V| + |E| ) ④ queue, O( |V|2 ) 문 3. 가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은? ① 그래프에 존재하는 임의의 사이클을 구성하는 간선(edge)들 중 가중치가 가장 작은 간선은 항상 이 그래프의 최소비용 신장 트리에 포함된다. ② Dijkstra의 최단경로 알고리즘 수행 결과 생성되는 신장트리는 항상 최소비용 신장트리이다. ③ 임의의 그래프에 대해 서로 다른 최소비용 신장트리가 항상 두 개 이상 존재한다. ④ 간선의 가중치 값들이 서로 다르고 최소비용 신장트리가 존재하는 경우, 가중치 값이 가장 작은 간선은 항상 최소비용 신장트리에 포함된다. 문 4. 그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가? ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다. ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다. ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 v 2개 이다. ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현 하면 필요한 메모리는 O(v + e)이다. ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O(v2)이다. ① 1 개 ② 2 개 ③ 3 개 ④ 4 개 문 5. 해싱(hashing)에 관한 다음 설명 중 옳은 것만으로 묶은 것은? ㄱ. n개의 자료가 있을 때 자료의 탐색에 걸리는 시간은 O(logn)이다. ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓 (bucket)에 사상(mapping)시킨다. ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다. ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다. ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다. ① ㄴ, ㄷ ② ㄴ, ㅁ ③ ㄱ, ㄹ ④ ㄹ, ㅁ 문 6. 스택, 큐, 리스트 자료구조에 대한 설명으로 옳지 않은 것은? ① 연결리스트는 배열 구조와 비교하여 삽입, 삭제 시간이 많이 걸리고 메모리의 낭비가 많다. ② 주로 힙(heap) 구조로 구현되는 우선순위 큐(priority queue)의 데이터 삽입은 임의로 이루어지나, 데이터의 삭제는 가장 큰 값이나 가장 작은 값부터 수행된다. ③ 스택은 함수 호출, 후위식 연산 등에 유용하게 사용되며, 연결 리스트로 구현할 수 있다. ④ 큐는 선입선출(First In First Out) 방식의 동작을 수행하므로 잡스케줄링(job scheduling) 등에 유용하게 사용된다. 문 7. 깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A － B의 값은? (단, 루트노드의 레벨은 1로 한다) ① 2 k-1 + k + 1 ② 2 k-1 + k － 1 ③ 2 k － k － 1 ④ 2 k － k + 1 문 8. 6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리 (binary search tree)를 만들 때, 만들어진 이진 탐색트리의 높이가 가장 낮은 것은? ① 1, 2, 3, 5, 4, 6 ② 4, 2, 5, 6, 1, 3 ③ 3, 1, 4, 2, 6, 5 ④ 2, 1, 3, 4, 6, 5 자료구조론 봉 책형 2 쪽 문 9. 다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 데이터 ‘JAN’을 삽입한 결과로 옳은 것은? MAY AUG NOV APR MAR ① MAY AUG NOV APR MAR JAN ② MAY AUG NOV APR MAR JAN ③ MAR AUG MAY APR JAN NOV ④ MAY AUG NOV APR MAR JAN 문 10. 다음과 같은 이진트리(binary tree)에서 전위순회(preorder traversal)와 중위순회(inorder traversal)를 했을 때, 두 순회 결과에서 노드 값의 방문 순서가 일치하는 횟수는? (전위순회의 k번째 노드값과 중위순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다) A B C D E F G H I J ① 3 회 ② 4 회 ③ 5 회 ④ 6 회 문 11. 점근적 표기법(asymptotic notation)에 관한 사칙연산으로 옳지 않은 것은? ① O(n) + O(n) ＝ O(n) ② O(n2) + O(nlogn) ＝ O(n2) ③ O(n2) + O(n) ＝ O(n2) ④ O(logn) ․ O(n2) ＝ O(n2) 문 12. 배열 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 ㉠ ㉡ ① lower ← mid + 1 upper ← mid - 1 ② upper ← mid + 1 lower ← mid - 1 ③ lower ← mid - 1 upper ← mid + 1 ④ upper ← mid - 1 lower ← mid + 1 문 13. 다음 데이터를 퀵정렬 (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] ① 7 1 4 6 3 5 2 0 8 9 ② 7 1 4 0 6 3 5 2 8 9 ③ 2 1 4 0 6 3 5 7 8 9 ④ 0 1 4 2 6 3 5 7 8 9 문 14. K[1: 2, 1: 3, 1: 2]로 선언된 3차원 배열을 행 우선순서(row major order)로 1차원 배열에 저장했을 때, 9번째에 저장되는 요소는? ① K(1, 2, 2) ② K(1, 3, 2) ③ K(2, 2, 1) ④ K(2, 3, 2) 자료구조론 봉 책형 3 쪽 문 15. 다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 모든 원소들의 값이 0인 행렬을 상삼각 행렬(upper triangular matrix) 이라고 한다. X X X X X X X X X X X X X X X X X X X X X X X X X X X non 0 0 A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가? ① B[4998] ② B[4999] ③ B[5000] ④ B[5001] 문 16. 다음 전위식(preorder expression)으로 표현된 수식을 후위식 (postorder expression)으로 변환하였다. 변환된 수식의 4번째 연산자는? (전위식) － + － AB * / CDEF ① * 연산자 ② + 연산자 ③ － 연산자 ④ / 연산자 문 17. 스택을 일차원 배열 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() ; } ㉡; } ㉠ ㉡ ① stack[*top++] return stack[--*top] ② stack[*top++] return stack[*top--] ③ stack[++*top] return stack[*top--] ④ stack[++*top] return stack[--*top] 문 18. 원형 연결리스트(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; } ㉠ ㉡ ① !ptr temp->link != ptr ② ptr temp=temp->link, temp != ptr ③ !ptr temp=temp->link, temp == ptr ④ ptr temp->link == ptr 문 19. n개의 데이터로 구성된 선형 리스트(linear list)를 단순 연결리스트 (singly linked list)로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은? ① 포인터가 가리키는 노드의 다음 노드를 리스트에서 삭제 ② 리스트의 길이를 출력 ③ 포인터값이 주어진 임의의 노드 앞에 새로운 노드 추가 ④ 마지막 노드의 데이터를 출력 문 20. 자료들이 단순 연결리스트(singly linked list)에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은? 메모리주소 data link 2000 A 2020 2010 B 2030 2020 C 2010 2030 D 0 ① A의 link → 2030 ② B의 link → 2010 ③ B의 link → 2020 ④ C의 link → 2030