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

 

자료구조론정답(2021-03-04 / 344.9KB / 252회)

 

 자료구조론 공 책형 1 쪽 자료구조론 문 1. 힙정렬(heap sorting)로 다음 데이터를 내림차순으로 정렬할 때 만들어지는 최초의 힙구조는? 7, 1, 15, 13, 19 ① 1 7 13 15 19 ② 13 7 15 1 19 ③ 19 13 15 7 1 ④ 7 1 15 13 19 문 2. 다음의 인접행렬로 표시되는 그래프 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 ① V = {a, b, c, d}, E = {,,,,} ② V = {a, b, c, d}, E = {,,,,} ③ V = {a, b, c, d}, E = {,,,,} ④ V = {a, b, c, d}, E = {,,,,} 문 3. 다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설 하기 위한 지도를 그래프로 표현한 것이다. 최소비용 신장 트리를 구하는 Kruskal 알고리즘을 이용하여 초고속철도를 건설하려고 한다. 4번째로 건설해야 할 구간은? 서울 인천 대전 포항 목포 진주 부산 4 9 13 11 8 10 9 4 14 7 3 ① 포항 ↔ 부산 ② 진주 ↔ 부산 ③ 서울 ↔ 인천 ④ 인천 ↔ 목포 문 4. 크기가 10인 해시 테이블을 배열을 이용하여 만든다고 가정하자. 해시함수로 h(k)=k mod 10을 사용한다. 여기서 mod는 모듈로 (modulo) 함수를 의미한다. 데이터가 다음과 같은 순서로 입력 된다고 할 때 발생하는 충돌(collision) 횟수의 총 합으로 옳은 것은? (단, 배열의 인덱스는 [0]~[9]까지이고, 처음에 배열은 비어 있으며, 충돌을 해결하기 위해서는 배열의 다음 빈 공간에 데이터를 입력하는 선형 조사법(linear probe)을 사용한다고 가정한다) 70, 17, 26, 69, 72, 53, 31, 27, 23, 13 ① 3 ② 4 ③ 5 ④ 6 문 5. 다음 이진 탐색트리(binary search tree)에서 루트(root)노드가 삭제된 후의 상태는? 52 23 10 47 63 84 90 54 77 58 61 ① 54 23 10 47 58 63 84 90 77 61 ② 61 47 23 10 54 58 63 84 90 77 ③ 58 23 10 47 54 61 84 90 63 77 ④ 84 23 10 47 54 63 90 58 77 61 자료구조론 공 책형 2 쪽 문 6. 최대힙(max heap)으로 우선순위큐를 구현하려 한다. 우선 순위를 나타내는 9개의 데이터가 큐에 다음과 같은 순서대로 삽입되었다. 1개의 데이터가 큐에서 삭제된 후, 재 정렬된 힙에서 가장 마지막 원소는 무엇인가? (단, 숫자가 클수록 우선순위가 높다고 가정한다) 24, 17, 29, 22, 20, 31, 27, 18, 21 ① 17 ② 18 ③ 20 ④ 21 문 7. 다음을 참조하여, 피봇(pivot)값을 이용하는 정렬 방법과 아래의 ㉠ ~ ㉤에 들어갈 값이 올바르게 나열된 것은? 데이터 = {60, 50, 13, 92, 52, 2, 69, 30, 78, 42} 단계1) 피봇값 : ( ㉠ ) － 왼쪽으로부터 비교 : ( ㉡ )에서 비교 멈춤 － 오른쪽으로부터 비교 : ( ㉢ )에서 비교 멈춤 － ( ㉣ )과(와) ( ㉤ )의 저장 위치 교환 정렬 방법 ㉠ ㉡ ㉢ ㉣ ㉤ ① 퀵 정렬 52 60 42 60 42 ② 쉘 정렬 52 60 42 60 42 ③ 퀵 정렬 60 92 42 92 42 ④ 쉘 정렬 60 92 42 92 42 문 8. 다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그래프의 간선들 간의 거리를 나타낸다. 표에서 무한대 기호 ∞는 해당 간선이 없음을 나타낸다. 정점 A에서 나머지 네 개의 정점 들에 도달하기 위한 최단경로들의 합은 얼마인가? to from A B C D E A 0 2 5 ∞ 3 B ∞ 0 ∞ 4 10 C ∞ ∞ 0 6 2 D ∞ ∞ ∞ 0 ∞ E ∞ ∞ 1 2 0 ① 12 ② 14 ③ 15 ④ 16 문 9. 이진 탐색트리(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 right; root->right = root->left; root->left = temp; JOB_Tree(root->left); JOB_Tree(root->right); } ① 트리의 루트를 중심으로 좌우 대칭 이동 ② 트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 복사 ③ 트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 이동 ④ 트리의 루트를 중심으로 오른쪽 자식 트리를 왼쪽 자식 트리로 이동