2021 군무원 7급 자료구조론 문제 정답 - 2021.7.24.

 

자료구조론_7급(최종)정답(2021-07-25 / 298.0KB / 740회)

 

 자료구조론(7급) 5 - 1 자 료 구 조 론 ( 7급 ) (과목코드 : 080) 2021년 군무원 채용시험 응시번호 : 성명 : 1. 함수 또는 수식들의 복잡도에 대한 설명 중 가장 적절하지 않은 것은? ①    는   이다. ② 함수      는   이다. ③ 함수  log      는  log 이다. ④      는   이다. 2. 재귀(recursion) 알고리즘과 for 문 또는 while 문을 사용하는 반복(iteration) 알고리즘에 대한 설명 중 가장 적절한 것은? ① 반복 알고리즘은 대체로 재귀 알고리즘에 비 해 시 간 적 으 로 나 공 간 적 으 로 매 우 비효율적이다. ② 재귀 알고리즘은 반드시 큐(queue)의 개념이 필요하다. ③ 이진 탐색을 하는 반복 알고리즘의 최악의 경우 수행 시간은 log 이고, 재귀 알고리즘의 최악의 경우 수행 시간은 이다. ④ 재귀 알고리즘은 재귀 호출(recursive call)을 사용한 알고리즘으로서 오버헤드(overhead), 즉 부가적인 기억 공간이 필요할 수 있다. 3. 다음은 AVL트리를 이용하여 우선순위 큐(priority queue)를 구현할 때, 최소값 찾기(findMin), 최소값 제거(deleteMin) 및 삽입(insert) 연산에 대한 최악의 경우 시간 복잡도를 차례대로 나열한 것이다. 가장 적절한 것은? (단, 작은 값이 높은 우선순위를 갖는다고 가정한다.) ① log - log - log ②  - log - log ③  - log -  ④ log - log -  4. 키(key) 값의 순서(ordering)와 가장 관련이 없는 것은? ① 이진 탐색 ② 선형보간 탐색 ③ 해싱 ④ AVL트리 5. 다음과 같은 원형 연결리스트(circular linked list) C에 대한 설명 중 가장 옳은 것은? (단, 노드는 data와 link필드로 이루어져 있고, C는 리스트의 마지막 노드를 가리키는 포인터이며, 은 노드의 개수임.) …. C ① 이 리스트를 큐로 사용하려면 C를 rear로 하고, C → link를 front로 한다. ② 이 리스트의 제일 왼쪽 노드를 제거하는데 시간이 걸린다. ③ 이 리스트의 제일 오른쪽에 새로운 노드를 삽입하는데 시간이 걸린다. ④ C의 바로 앞 노드를 찾는데 시간이 걸린다. 6. 스택에 정수 1, 2, ... , 을 순서대로 push하면서 임의로 pop을 하게 되면 여러 가지 수열을 얻을 수 있다. 예를 들어,   일 때 push(1), pop(), push(2), pop() 연산을 차례대로 하면 수열 (1, 2)를 얻을 수 있고, push(1), push(2), pop(), pop() 연산을 차례대로 하면 수열 (2, 1)을 얻을 수 있다. 이와 같은 방법에 의해 수열을 얻을 때 다음 중에서   인 경우 얻을 수 없는 수열은? ① (1, 2, 4, 3) ② (3, 4, 2, 1) ③ (3, 2, 1, 4) ④ (4, 2, 3, 1) 자료구조론(7급) 5 - 2 7. 그래프의 특성에 대한 설명 중 가장 적절하지 않은 것은? (단, 한 정점 에서 로의 간선은 허용하지 않으며, 서로 다른 두 정점 사이의 간선은 최대 1개이다.) ① 정점이 5개, 간선이 10개인 무향그래프 (undirected graph)에서 각 정점의 차수 (degree)의 합은 20이다. ② 정점이 4개, 간선이 10개인 유향그래프 (directed graph)에서 각 정점의 진출 차수의 합은 10이다. ③ 정점이 6개인 무향그래프의 간선의 최대 수는 30개이다. ④ 정점이 5개인 유향그래프의 간선의 최대 수는 20개이다. 8. 노드의 필드가 *lchild, data, *rchild인 연결 리스트로 구현된 다음 그림의 이진트리를 함수 mystery_Order()에 의해 운행할 때 방문되는 노드 순서가 맞는 것은? (단, 초기 호출시 t는 루트인 노드 A를 가리킨다.) void mystery_Order (treePointer t) { if (t) { mystery_Order(t->lchild); printf("%c", t->data); mystery_Order(t->rchild); printf("%c", t->data); } } A B F C E G D H ① C D D C B E E B A G H H G F F A ② A B C D D C E E B A F G H H G F ③ A B C D E F G H D C E B H G F A ④ C C D D E E B B A A G G H H F F 9. 추상자료형(abstract data type)에 대한 설명 중 가장 적절하지 않은 것은? ① 추상자료형은 자료(data)와 연산(operation)으로 구성된다. ② 추상자료형은 자료구조의 효율적인 구현 방법을 명시하여야 한다. ③ 추상자료형은 객체지향언어의 클래스(class)의 개념과 유사하다. ④ 추상자료형은 수학에서 대수 구조(algebraic structure)의 개념과 유사하다. 10. 아래 유향그래프에 대한 위상순서(topological order)를 계산하려 한다. 다음 중 가장 적절하지 않은 것은? ① 정점 G가 8번째인 위상순서가 존재한다. ② 정점 B가 5번째인 위상순서가 존재한다. ③ 정점 F가 7번째인 위상순서가 존재한다. ④ 정점 D가 3번째인 위상순서가 존재한다. 11. 다음은 어느 이중해싱(double hashing)의 1차 해시함수 와 2차 해시함수 이다.    mod       mod  이를 이용하여 크기 13인 테이블(배열) 에 보기의 키들이 차례로 입력되었다. 이때 [5], [8], [11]에 저장된 값들이 맞게 표시된 번호를 고르시오. (단, 배열 는 키들을 입력받기 전에 모든 원소가 0으로 초기화되어 있다.) 43, 23, 24, 37, 42, 30, 73 ① 42, 73, 24 ② 42, 0, 24 ③ 43, 73, 23 ④ 43, 0, 23 자료구조론(7급) 5 - 3 12. 해싱의 오버플로우(overflow) 처리기법에 대한 설명 중 가장 적절하지 않은 것은? ① 체이닝(chaining)은 버킷을 연결 리스트로 구현하는 오버플로우(overflow) 처리 기법이다. ② 재해싱(rehashing)은 해시 테이블 크기를 늘려서 테이블에 저장된 모든 원소에 대해서 해시값을 재계산한 후 다시 새로운 해시 테이블에 저장해야 하므로 시간이 많이 걸린다. ③ 선형 조사법(linear probing)은 군집 현상 (clustering)이 발생하므로 해시 테이블의 탐색 연산을 위해서는 매우 효율적이다. ④ 이차 조사법(quadratic probing)은 선형 조사법보다는 군집 현상이 덜 발생한다. 13. 노드 개수가 이고 방향 에지(간선)의 개수가 인 방향 그래프(directed graph)를 인접 리스트(adjacency list)로 표현할 때 필요한 기억 공간을 과 의 함수로 표시한 것으로 가장 적절한 것은? ①  ②    ③  ×  ④     14. 정렬 알고리즘에 대한 설명 중 가장 적절하지 않은 것은? ① 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘은 점근분석 시 최악수행시간이 같다. ② 삽입정렬, 힙정렬(heap sort), 퀵정렬은 제자리 정렬(in-place sorting) 구현이 가능하다. ③ 합병정렬(merge sort), 힙정렬, 기수정렬(radix sort) 알고리즘은 원소 간 대소비교를 통해 정렬하는 알고리즘 중 최적알고리즘이다. ④ 선택정렬 알고리즘은 최악수행시간과 평균 수행시간이 같다. 15. 다음 그래프 를 너비우선 탐색(breadth-first search)으로 운행했을 때 정점의 탐색 순서가 맞는 것은? (단, 탐색은 정점 v1부터 시작하며 인접한 정점이 여러 개 있을 때는 정점의 번 호 가 작은 것부터 우선 방문한다.) ① v1-v2-v9-v3-v8-v7-v4-v6-v5 ② v1-v2-v3-v4-v5-v6-v7-v8-v9 ③ v1-v2-v9-v3-v8-v7-v4-v5-v6 ④ v1-v2-v3-v8-v9-v4-v5-v6-v7 16. 다음 그래프에 대해 Prim 알고리즘을 적용하였다. 정점 A에서 시작했을 때의 설명 중 가장 적절하지 않은 것은? ① Prim 알고리즘은 그리디(greedy) 알고리즘이다. ② A에서 시작했을 때 다음으로 선택되는 3개의 정점은 차례로 B, E, H이다. ③ A를 포함하여 선택된 정점이 5개일 때 다음으로 선택되는 정점은 F이다. ④ 최종결과의 가중치는 37이다. 자료구조론(7급) 5 - 4 17. 보기의 중위표기법 수식을 후위표기법으로 옳게 변환한 것은?    ×  ①    ×  ②  × ③    × ④  × 18. 자료구조의 탐색 연산과 최악의 경우 시간 복잡도를 짝지은 것 중 가장 적절하지 않은 것은? (단, 은 전체 데이터의 개수임.) ① 선형보간 탐색(linear interpolation search) - loglog ② 이진탐색트리에서의 탐색 연산 -  ③ AVL트리에서의 탐색 연산 - log ④ 2-3트리에서의 최소값 탐색 연산 - log 19. 다음의 정렬 방법 중 분할정복(divide-andconquer)의 개념을 이용한 정렬 방법만 골라놓은 것으로 가장 적절한 것은? (가) 삽입 정렬 (나) 퀵 정렬 (다) 힙 정렬 (라) 병합 정렬 (마) 기수(radix) 정렬 (바) 버블 정렬 ① (가), (바) ② (나), (라) ③ (다), (라) ④ (라), (마) 20. 초기에 비어있는 이진탐색트리에 노드 값이 40, 60, 50, 20, 25, 70, 55, 52, 10 순으로 삽입된다고 가정한다. 이 이진탐색트리에서 루트 노드값 40을 삭제하여 다시 이진탐색트리를 효율적으로 재구성한다고 할 때 루트 노드가 될 수 있는 값은? ① 25 또는 52 ② 25 또는 50 ③ 20 또는 60 ④ 20 또는 52 21. 이진트리 의 높이 를 왼쪽 부분트리  의 높이 과 오른쪽 부분트리 의 높이  을 이용하여 재귀적으로 정의할 때 다음의 빈칸 ㈎에 맞는 사항은? (단, 가 NULL인 경우의 높이를 0으로 하고, 루트 노드의 레벨을 1로 가정한다.)    if      ( ㈎ ) if  ≠  ①        ② ∣   ∣   ③ max     ④ min      22. 레드블랙트리(red-black tree)에 대한 설명 중 가장 적절하지 않은 것은? ① 모든 리프노드(NIL)는 블랙노드이다. ② 부모 노드와 자식 노드는 동일한 색일 수 없다. ③ 루트는 블랙노드이다. ④ 모든 리프에서 루트까지 가는 경로에서 만나는 블랙노드의 수는 같다. 23. 수식  ×      × 가 이진트리에 저장 되어 있을 때의 설명으로 가장 적절한 것은? ① 가 저장된 노드는 가 저장된 노드와 깊이가 같다. ② 이 트리를 중위순회(inorder traversal)하면 2가 저장된 노드는 6번째로 방문한다. ③ 이 트리를 중위순회하면 7번째로 방문하는 노드에는 ×가 저장되어 있다. ④ 내부노드는 네 개이며, 모두 연산자들을 저장하고 있다. 자료구조론(7급) 5 - 5 24. 원소값의 비교(comparison)에 의해 정렬하는 문제에 대한 시간 복잡도의 하한선(lower bound)에 관한 설명 중 가장 적절한 것은? ① 최악의 경우 시간 복잡도에 대한 하한선은 결정트리의 외부 경로길이(external path length)에 반비례한다. ② 원소값의 비교에 의해서 정렬하는 알고리즘은 항상 결정트리(decision tree) 모델로 나타낼 수 있다. ③ 최악의 경우 시간 복잡도에 대한 하한선은  이다. ④ 평균적인 경우 시간 복잡도에 대한 하한선은   이다. 25. 다음은 오름차순으로 안정 정렬(stable sorting)을 하는 삽입 정렬 알고리즘의 일부를 C언어 형태로 나타낸 것이다. 빈칸 (가), (나)에 가장 적절한 것은? (단, 정렬하고자 하는 배열 list[]는 전역 변수임.) void insertion_sort (int n) { int n; int i, j, temp; for (i=1; i=0 && (가); j--) (나); list[j+1] = temp; } } ① (가) temp list[j] (나) list[j] = list[j+1] ③ (가) temp < list[j] (나) list[j+1] = list[j] ④ (가) temp >= list[j] (나) list[j] = list[j+1]