자료구조 10 - Graph(그래프) 연습문제 및 소스코드

소개글

안녕하세요,

[C언어로 쉽게 풀어 쓴 자료구조] (Data structure in C) - 천인국 저, 생능출판사

의 각 단원의 연습 문제 및 중요한 소스코드 입니다.

저는 A+ 학점을 받지 않은 과목의 자료는 올리지 않습니다. 한글파일 및 소스코드가 함께

들어가있습니다. 2010년 자료라 믿고 받으시면 됩니다.

목차

없음

본문내용

01 다음 중 그래프에 대한 설명으로 틀린 것은?
(1) 모든 트리는 그래프라 할 수 있다.
(2) 무방향 그래프의 인접 행렬은 대각선을 중심으로 대칭이다.
(3) 그래프는 정점과 집합과 간선의 집합으로만 정의된다.
(4) 그래프에는 사이클이 존재하면 안된다.

03 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진입 차수를 알고 싶으면 어떻게 하면 되는가?
(1) 인접 행렬의 v번째 행의 값들을 전부 더한다.
(2) 인접 행렬의 v번째 열의 값들을 전부 더한다.
(3) 인접 행렬의 v번째 행의 값들을 전부 더해서 2로 나눈다.
(4) 인접 행렬의 v번째 열의 값들을 전부 더해서 2로 나눈다.

05 최소 비용 스패닝 트리란?
(1) 모든 정점을 연결하는 간선들의 숫자가 최소가 되는 간선들의 집합
(2) 정점과 간선들의 숫자가 같은 트리
(3) 불필요한 정점들은 제거된 트리
(4) 모든 정점을 연결하면서 가중치가 최소가 되는 간선들의 집합

07 정점의 개수를 n, 간선의 개수를 e라고 할 때, 인접 행렬에서 특정 정점의 차수를 계산하는 연산의 시간 복잡도는?
(1) O(log2n) (2) O(n)
(3) O(n+e) (4) O(e)

09 다음 중 큐를 사용하는 알고리즘은?
(1) 깊이 우선 탐색 (2) 너비 우선 탐색
(3) Dijkstra의 최단 경로 알고리즘 (4) Floyd의 최단 경로 알고리즘

참고 자료

없음