[C언어로 쉽게 풀어쓴 자료구조] 10장

01 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가?

(1) 인접 행렬의 v번째 행의 값들을 전부 더한다.

(2) 인접 행렬의 v번째 열의 값들을 전부 더한다.

(3) 인접 행렬의 v번째 행의 값들을 전부 더해서 2로 나눈다.

(4) 인접 행렬의 v번째 열의 값들을 전부 더해서 2로 나눈다.

 

02 인접 행렬이 {0,1,0,0},{1,0,0,0}{0,1,0,0},{0,1,0,0} 이라면 여기에 대응되는 인접 리스트를 그려라.

 

03 정점의 개수를 n, 간선의 개수를 e라고 할 때, 인접 행렬에서 특정 정점의 차수를 계산하는 연산의 시간 복잡도는?

(a) O(log₂n)

(b) O(n)

(c) O(n+e)

(d) O(e)

 

04 정점의 개수를 n, 간선의 개수가 e인 그래프를 인접 리스트로 표현하였을 경우, 인접 리스트 상의 총 노드의 개수는?

(1)e개

(2)2e개

(3)n개

(4)2n개

 

05 다음 중 큐를 사용하는 알고리즘은?

(1) 깊이 우선 탐색

(2) 너비 우선 탐색

(3) 최단 거리 알고리즘

(4) 최소 비용 신장 트리

 

06 다음 그래프를 인접 행렬과 인접 리스트로 표현해보자.

07 다음의 방향 그래프에 대하여 다음 질문에 답하라.

(1) 각 정점의 진입차수와 진출차수

(2) 각 정점에 인접한 정점들의 집합

(3) 인접 행렬 표현

(4) 인접 리스트 표현

(5) 모든 사이클과 그 길이

 

08 정점 V={1,2,3,4,5}이고, 간선 E={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,5>,<3, 1>, <3, 2>, <3,4>, <3,5>,<4,2>,<5,1>,<5,3>} 으로 정의되는 방향 그래프를 그려라.

 

09크기가 n x n 인 방향 그래프 a가 n x n 인접 배열을 사용하여 표현되어 있다.

(1) 주어진 정점의 진출차수(out-degree)을 계산하는 함수를 작성하라. 진출차수란 어떤 정점에서 출발하여 외부가 나가는 간선의 개수이다. 이 함수의 시간 복잡도는?

(2) 주어진 정점의 진입차수(in-degree)을 계산하는 함수를 작성하라. 진입차수란 어떤 정점으로 들어오는 간선의 개수이다. 이 함수의 시간 복잡도는?

(3) 그래프 안에 있는 간선들의 개수를 계산하는 함수를 작성하라. 이 함수의 시간 복잡도는?

 

10 만약 그래프가 인접 리스트로 표현되어 있다고 가정하고 앞의 문제를 다시 작성하라

 

11 3개, 4개, 5개의 정점으로 된 무방향 완전 그래프를 그려보라. n개의 정점을 갖는 완전 그래프의 간선의 개수가 n(n-1)/2인지를 확인하라.

 

12 하드 디스크에 파일로 그래프의 인접 행렬이 저장되어있다고 가정하고 다음과 같은 함수를 작성하라. 그래프 파일의 형식은 다음과 같다.

4

0 1 1 1  /*정점의 개수*/

1 0 1 1 /*인접 행렬 */

1 1 0 1

1 1 1 0

 

read_graph_mat (GraphType * g, char *name) : 이름이 name인 그래프 파일을 읽어서 그래프 g의 인접 행렬에 저장

write_graph_mat(GraphType* g, char *name) : 그래프 g의 인접 행렬을 이름이 name인 그래프 파일에 저장

 

13 다음의 그래프에 대하여 답하라. 그래프는 인접행렬로 표현되어 있다고 가정하라

(1) 정점 3에서 출발하여 깊이 우선탐색했을 경우의 방문 순서

(2) 정점 6에서 춟라하여 깊이 우선탐색했을 경우 방문 순서

(3) 정점 3에서 출발하여 너비 우선 탐색했을 경우 방문순서

(4) 정점 6에서 출발하여 너비 우선탐색했을 경우의 방문순서

 

14 연결된 그래프 G의 간선들 중에서 그 간선을 제거하면 연결이 끊어지는 간선(u,v)를 브리지(bridge)라고 한다. 주어진 그래프에서 브리지를 찾아내는 함수를 작성하라.

 

15 다음의 인접리스트는 어떤 그래프를 표현한 것이다. 이 그래프를 정점 A에서부터 깊이 우선 탐색할 때, 정점이 방문되는 순서로 옳은 것은?