이 문제들을 다 풀면 graph, tree 정복!

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

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

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

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

D 루트 정점이 존재한다.

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

 

answer B, D

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

 : 간선마다 가중치가 다른 가중치그래프가 있음

루트 정점이 존재한다. X

 : 이것은 트리에 대한 설명

 

 

 

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

answer

3

 

 

Q. 무향 그래프를 인접 행렬(Adjacent Matrix)로 구현할 때 차지하는 메모리의 양은? (V = Vertex, E = Edge)

A V제곱

B V제곱 + E

C V + E

D V + 2E

 

A. V제곱

matrix는 VxV 크기의 표를 만드는 것

 

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

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

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

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

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

 

answer C, D

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

: 이거는 이진트리의 특성이다!

D 순환 구조를 가질 수 있다. X

: 이거는 그래프의 특성

 

 

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

answer 4

트리에서는 depth = height = level 이다.

 

여기서 트리의 height 와 노드의 height는 다른 말이다.

 

그러면 노드 5의 height를 구하라고 한다면 답은 1이 된다.

leaf 노드인 6, 7의 height가 0이고 그 위에 있는 4, 5의 height가 1

 

height와 depth는 반대개념이다.

depth는 루트가 0으로 시작하면 됨.

 

주의할 점은

트리의 높이는 1부터 시작

노드의 높이는 0부터 시작한다는 것!

 

 

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

 

 

answer 4

노드 6, 7, 4, 3 이 leaf이다.

 

 

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

 

answer

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

 

전위순회는 root left right

중위순회는 left root right

후위순회는 left right root

 

그래서 중위순회로 가면

가장 left인 G가 첫번째 시작이 되고 순서대로 왼, 루트, 오 로 간다.

 

 

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

 

 

answer

완전 이진 트리 (Complete Binary Tree)

정 이진 트리 (Full Binary Tree)

 

완전 이진 트리 (Complete Binary Tree): 모든 node들이 level별로 왼쪽부터 채워진 트리

정 이진 트리 (Full Binary Tree): node 의 child가 하나도 없거나, 2개인 트리

포화 이진 트리 (perfect Binary Tree): 양 쪽으로 빈 공간 없이 모든 node가 2개의 자식을 가지고 level도 정확하게 떨어진다.

이것은 완벽한 피라미드 구조

 

 

 

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

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

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

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

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

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

 

answer C E

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

: 완전 이진 트리는 이진 탐색 트리의 종류일 뿐

E 자식 노드의 값 보다 부모 노드의 값이 항상 크다. X (오른쪽이 더 큼)

 

Q. 다음 이진 탐색 트리에서 루트 노드인 21을 삭제 했을 때 새롭게 루트 노드가 되는 값은 무엇인가?

 

 

answer 25

 

21을 삭제한 후의 이진 탐색 트리의 형태는 다음과 같다. 

 

 

삭제 루틴은 3가지로 나뉜다.

삭제할 노드의 자식이 0,1,2개인경우로

0개면? 그냥 삭제하면 끝

1개면? 자기를 지우고 자기 자식을 부모랑 연결

2개면? 왼쪽 서브트리에서 가장 큰값을 찾거나 오른쪽 서브트리에서 가장 작은값을 찾아서 내 자리로 올려놓으면 된다.