c로 배우는 쉬운 자료구조 개정3판 8단원 연습문제

목차

없음

본문내용

1. 그래프에 관한 다음 설명 중 옳은 문장은 몇 개인가? 2번 2개
ㄱ. 무방향 그래프를 인접 행렬로 표현하면 항상 대칭인 행렬이 된다.
ㄴ. 무방향 그래프에서 모든 정점의 차수를 더하면 간선 수와 같다.
ㄷ. 정점이 v개인 무방향 완전 그래프의 간선 수는 v^2개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접 행렬로 표현하면 필요한 메모리는 O(v+e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비 우선 탐색의 수행 시간은 O(v^2)이다.
2. 그래프는 정점 집합 V와 간선 집합 E로 이루어진다. 정점이 a,b,c 세 개 존재하고 간선이 a와 b사이에 하나, b와 c 사이에 하나 존재한다고 할 때, 정점 집합 V는 V={a,b,c}와 같은 형태로 표현하고 간선 집합 E는 E={(a,b),(b,c)}와 같이 나타낸다고 하자. 정점 집합과 간선 집합을 이용한 그래프 표현으로 옳은 것은?
1번 V={a,b,c,d,e,f},E={(a,b),(b,c),(c,a)}
3. 다음 인접행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?
3번 강력 연결 요소는 두 개이다.
4. 그래프의 깊이 우선 탐색에 대한 설명으로 옳지 않은 것은?
3번 최소비용신장트리를 구하는 크루스칼 알고리즘은 깊이 우선 탐색을 사용한다.
5. 다음 인접 행렬로 표시되는 그래프 G=(V,E)는? (단, False는 from에서 to까지의 간선이없고, True는 from에서 to까지의 간선이 있음을 의미한다.)
2번 V={a,b,c,d},E={,,,,}
6. 다음과 같은 그래프에서 노드 1부터 시작하여 깊이 우선 탐색을 수행할 경우 나타날 수 없는 순서는?
1번 1-2-3-4-5-6-7-8
7. 다음인접 리스트로 표현된 그래프를 깊이 우선 탐색으로 순회하고자 한다. 정점 0부터 시작한 순회 순서는? 3번 0,1,3,2,5,6,4

출처 : 해피캠퍼스