Graph, Tree, Binary Search Tree

1. 그래프에 대한 설명으로 틀린 것을 모두 고르면?

① 정점(vertex)과 간선(edge)으로 이루어져 있다.

② 간선이 방향을 가지는 방향 그래프와, 간선에 방향이 없는 무향 그래프로 나뉜다.

③ 순환 구조를 가질 수 있다.

④ 루트 정점이 존재한다.

⑤ 그래프의 간선은 모두 같은 가중치 값을 가져야 한다.

④ 루트 정점이 존재한다.

⑤ 그래프의 간선은 모두 같은 가중치 값을 가져야 한다.

 

2. 정점의 개수가 5개인 방향 그래프의 최대 간선 개수는?

(단, 자기 간선, self edge, self loop는 없다고 가정한다)

① 5

② 10

③ 20

④ 25

③ 20

 

3. 다음 그래프에서 Vertex C의 in degree와 out degree의 합은?

① 1

② 2

③ 3

④ 4

⑤ 5

 

 

 

③ 3

 

4. 그래프를 인접 행렬(Adjacent Matrix)로 구현할 때의 공간 복잡도는?

(V = Vertex, E = Edge)

① O(V²)

② O(V² + E)

③ O(V + E)

④ O(V + 2E)

① O(V²)

 

5. 그래프를 인접 리스트(Adjacent List)로 구현할 때의 공간 복잡도는?

(V = Vertex, E = Edge)

① O(V²)

② O(V² + E)

③ O(V + E)

④ O(V + 2E)

⑤

③ O(V + E)

 

6. 그래프의 시간 복잡도와 관련하여 각 빈칸에 들어갈 말로 가장 적합한 것을 고르시오.

   - 정점의 추가는 () 방식이 효율적이다.

   - 정점의 삭제는 () 방식이 효율적이다.

   - 간선의 추가와 삭제가 빈번히 일어나는 경우에는 () 방식이 효율적이다.

① 인접 행렬, 인접 리스트, 인접 리스트 

② 인접 행렬, 인접 리스트, 인접 행렬

③ 인접 리스트, 인접 행렬, 인접 행렬

④ 인접 리스트, 인접 리스트, 인접 행렬

⑤ 인접 리스트, 인접 행렬, 인접 리스트

④ 인접 리스트, 인접 리스트, 인접 행렬

 

7. 다음 중 트리의 특성이 아닌 것을 모두 고르면?

① 트리는 그래프의 한 종류이다.

② 하나의 부모 노드만 가질 수 있다.

③ 순환 구조를 가질 수 있다.

④ 자식 노드는 최대 2개까지 가질 수 있다.

③ 순환 구조를 가질 수 있다.

④ 자식 노드는 최대 2개까지 가질 수 있다.

 

8. 다음과 같은 트리의 높이(height)는?

① 1

② 2

③ 3

④ 4

⑤ 5

③ 3

 

9. 다음과 같은 트리의 리프(leaf) 노드 개수는?

① 1

② 2

③ 3

④ 4

⑤ 5

④ 4

 

10. 다음과 같은 트리를 "중위순회"한 결과는?

① A-B-D-G-H-E-C-F

② G-D-H-B-E-A-C-F

③ G-H-D-E-B-F-C-A

④ B-A-C-G-D-H-E-F

② G-D-H-B-E-A-C-F

 

11. 다음과 같은 이진 트리에 해당하는 이진 트리의 종류를 모두 고르면?

① 정 이진 트리(Full Binary Tree)

② 완전 이진 트리(Complete Binary Tree)

③ 포화 이진 트리(Perfect Binary Tree)

② 완전 이진 트리(Complete Binary Tree)

 

12. 다음 이진 탐색 트리에 대한 설명 중 틀린 것을 모두 고르면?

① 자식 노드를 최대 2개까지 가질 수 있다.

② 항상 왼쪽 서브트리에는 작은 값이, 오른쪽 서브트리에는 큰 값이 존재한다.

③ 이진 탐색 트리는 항상 완전 이진 트리이다.

④ 원하는 값을 찾기 위해서 최대 트리의 높이만큼의 탐색이 필요하다.

⑤ 자식 노드의 값 보다 부모 노드의 값이 항상 크다.

③ 이진 탐색 트리는 항상 완전 이진 트리이다.

⑤ 자식 노드의 값 보다 부모 노드의 값이 항상 크다.

 

13. 이진 탐색 트리를 정렬하여 출력하기 위한 순회 방법은?

① Pre-order Traversal (전위순회)

② In-order Traversal (중위순회)

③ Post-order Traversal (후위순회)

④ None of the above

② In-order Traversal (중위순회)

 

14. 이진 탐색 트리에서 child가 2개인 노드를 삭제하는 방법은 일반적으로 2가지가 있다.

이 방법을 적용하여 이진 탐색 트리에서 21을 삭제했을 때,

새로운 루트 노드가 되는 값은 각각 무엇인가? (순서무관)

① 17, 40

② 19, 25

③ 11, 49

④ 19, 49

⑤ 11, 25

② 19, 25

 

15. 이진 탐색 트리에서 노드의 추가(insertion), 삭제(delection), 조회(retrieval)의 시간 복잡도를 순서대로 나열한 것은?

① O(logN), O(logN), O(N)

② O(logN), O(N), O(logN)

③ O(N), O(N), O(N)

④ O(logN), O(logN),O(logN)

③ O(N), O(N), O(N)