1 일반 리스트 L ＝ (e1, e2, …, en)에서 head(L)은 첫 번째 원소인 e1이고, tail(L)은 첫 번째 원소를 제외한 나머지 리스트 (e2, …,en)으로 정의된다고 할 때, 일반 리스트 L ＝ ((a, (b, c)), (d, e), ((f, g), h))에서 head(tail(head(L)))의 값은?
| ① |
b |
|
② |
c |
| ③ |
(b, c) |
|
④ |
(d, e) |
2 어떤 이진 트리(binary tree)를 전위 순회(preorder traversal)한 결과는 1, 2, 3, 4, 5, 6, 7, 8, 9이고, 중위 순회(inorder traversal)한 결과는 2, 3, 1, 5, 4, 7, 8, 6, 9라고 할 때, 이 이진 트리는?
3 다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive transitive closure) 행렬 D*를 인접 행렬로 바르게 표현한 것은?
5 각각 1,000개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 대해 ‘갑’과 ‘을’의 두 가지 정렬 기법으로 정렬을 수행했을 때 다음과 같은 시간이 소요되었다. ‘갑’과 ‘을’이 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 힙 정렬(Heap Sort) 중의 하나라면, 바르게 나열된 것은?
| | 갑 | 을 |
| ① | 퀵 정렬 | 합병 정렬 |
| ② | 힙 정렬 | 퀵 정렬 |
| ③ | 합병 정렬 | 퀵 정렬 |
| ④ | 합병 정렬 | 힙 정렬 |
6 다음과 같은 그래프에서 Sollin 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구하려고 한다. Sollin 알고리즘의 시작 단계에서는 하나의 정점으로 이루어진 트리들로 구성된 포리스트(forest)에서 각 트리의 최소 비용 간선(edge)을 선택하게 된다. 하나의 정점으로 이루어진 트리에 대한 최소 비용 간선을 선택할 때, 선택되는 간선이 아닌 것은?
| ① |
(A, B) |
|
② |
(B, E) |
| ③ |
(C, F) |
|
④ |
(D, E) |
7 다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색 (Depth First Search)을 수행할 경우 나타날 수 없는 순서는?
- ① 1 － 2 － 3 － 4 － 5 － 6 － 7 － 8
- ② 1 － 2 － 3 － 4 － 6 － 7 － 5 － 8
- ③ 1 － 2 － 3 － 4 － 6 － 5 － 7 － 8
- ④ 1 － 2 － 3 － 4 － 5 － 7 － 8 － 6
8 크기가 7( M ＝ 7)인 해시 테이블(hash table)에 이중 해싱(double hashing) 기법을 사용하여 데이터를 삽입한다고 하자. 첫 번째 해시 함수(hash function)는 ㉠이고, 충돌이 발생할 경우 사용하는 두 번째 해시 함수는 ㉡이다. 이러한 해시 함수를 사용하여 다음과 같은 탐색 키들을 차례대로 삽입한다고 할 때, 삽입이 완료된 후 해시 테이블의 상태는?
9 다음은 이진 탐색 트리(binary search tree)에서 최소 키 값을 가지는 노드에 대한 포인터를 반환하는 함수를 C 언어로 구현한 프로그램의 일부이다. ( 가)와 ( 나 )부분에 해당되는 문장이 바르게 나열된 것은?
| | (가) | (나) |
| ① | return T; | return T→Left; |
| ② | return T→Right; | return T→Left; |
| ③ | return T; | return FindMin(T→Left); |
| ④ | return FindMin(T→Right); | return FindMin(T→Left); |
10 AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 이른 시간(earliest time)과 가장 늦은 시간(latest time)을 각각 나타내는 early(i)와 late(i)를 구하고자 한다. 가장 이른 사건 발생 시간 (earliest event occurrence time)을 earliest 라고 하고, 가장 늦은 사건 발생 시간(latest event occurrence time)을 latest 라고 할 때, 작업 ㉠가 간선 k , l 로 표현된다면, 다음 식으로부터 early(i)와 late(i)를 구할 수 있다. 다음과 같은 AOE 네트워크에서 early(i)와 Iate(i)를 구한 결과 중 옳지 않은 것은?
- ① early (3) ＝6, late (3) ＝10
- ② early (5) ＝10, late (5) ＝10
- ③ early (7) ＝7, late (7) ＝12
- ④ early (9) ＝14, late (9) ＝14
