C언어로 쉽게 풀어쓴 자료구조 10장 해설(3판/천인국)

소개글

1. 본 파일의 정답 및 해설은 공식 정답이 아닌 직접 풀어서 작성한 것이며 오타, 오답 및 프로그램에 버그가 존재할 수 있으므로 반드시 확인하시길 바랍니다.
2. 간단한 문제는 해설이 생략되었을 수 있습니다.
3. 프로그램의 설명은 주석을 참조하시길 바랍니다.
4. 작성자가 과제로 지정된 문제의 해설만을 작성한것으로 일부 문제가 누락되었을 수 있습니다. 본문내용의 포함된 문제를 반드시 확인하시길 바랍니다.

목차

1. 인접 행렬 adj_mat[ ][ ]에서 ... 되는가?
2. 인접 행렬이 {0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0} ... 그려라.
3. 정점의 개수를 n, 간선의 개수를 e라고 할 때, ... 시간복잡도는?
4. 정점의 개수를 n, 간선의 개수가 e인 그래프를 ... 개수는?
5. 다음 중 큐를 사용하는 알고리즘은?
6. 다음 그래프를 인접 행렬과 인접 리스트로 표현해보자.
7. 다음의 방향 그래프에 대하여 다음 질문에 답하라.
8. 정점 V={1, 2, 3, 4, 5}이고, 간선 ... 방향 그래프를 그려라.
9. 크기가 n X n 인 방향 그래프 a가 n X n ...
10. 만약 그래프가 인접 리스트로 표현되어 있다고 ... 작성하라.
11. 3개, 4개, 5개의 정점으로 된 무방향 완전 그래프를 ... 확인하라.
12. 하드디스크에 파일로 그래프의 인접 행렬이 ... 다음과 같다.
13. 다음의 그래프에 대하여 ... 가정하라.
14. 연결된 그래프 G의 간선들 중에서 그 간선을 제거하면 ... 함수를 작성하라.
15. 다음의 인접 리스트는 어떤 그래프를 표현한 ... 옳은 것은?

본문내용

문제 3.
(2) O(n)
정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있다.

문제 4.
(2) 2e개
정점의 개수가 n, 간선의 개수가 e인 무방향 그래프를 표시하기 위해서는 n개의 연결리스트가 필요하고 n개의 헤더 노드와 2e개의 노드가 필요하다.

문제 5.
(2) 너비 우선 탐색

<중 략>

참고 자료

없음