체크 포인트 [Data Structure Part III]

dlrbwls0302·2021년 1월 22일
0

1번 문제

해설

A가 맞는 이유는 그래프는 정점(vertex)와 간선(edge)로 이루어져 있기 때문이다.

B가 맞는 이유는 그래프에는 무(방)향 그래프(undirected graph)와 방향 그래프(directed graph)가 있기 때문이다.

C가 맞는 이유는 그래프가 순환 구조를 가질 수 있다.

D가 틀린 이유는 루트 정점이 없기 때문이다. 루트 정점은 트리나 이진 탐색 트리 구조에 있다.

E가 틀린 이유는 간선은 모두 같은 가중치 값을 갖지 않기 때문이다.

각각의 간선은 다른 가중치 값을 가지고 있다.


2번 문제

해설

정점의 개수가 5개이면 간선의 개수는 10개 인데 만약 무방향 그래프라면 간선은 bidirectional이고 따라서 10 x 2가 되기 때문에 20이라고 할 수 있다.


4

번 문제

해설

V개의 노드를 표현하기 위해선 V * V개 만큼의 공간이 필요하므로 공간 복잡도는 O(V^2)이다. 참고로 인접 리스트의 공간 복잡도는 O(V+E)이다.


11번 문제

해설

정 이진 트리는 모든 레벨에서 노드들이 꽉 채워진(leaf를 제외한) 모습을 가지고 있다. 완전 이진 트리는 왼쪽 노드부터 채워져있고 마지막 레벨을 제외하고 모두 자식 노드가 있으면 완전 이진 트리이다. 따라서 그림은 정 이진 트리와 완전 이진 트리에 해당한다.


15번 문제

해설

이진 탐색 트리에서 시간 복잡도는 O(n)인데 때에 따라서 O(log n)이 될 수도 있다.

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글