그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?ㄱ. 무방향… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?
ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다.
ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.
ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 v2v^2개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O(v2v^2)이다.
1
1 개
2
2 개
3
3 개
4
4 개
해설

옳은 문장은 ㄱ, ㅁ의 두 개이다.

무방향 그래프는 간선 (i, j)와 (j, i)가 같으므로 인접행렬이 대칭이다. 인접행렬 기반 너비우선탐색은 정점마다 행 하나(v칸)를 모두 훑으므로 O(v2)O(v^2)이다.

  • 차수의 합: 간선 하나가 양 끝 정점의 차수를 하나씩 올리므로 간선 수의 2배(2e2e)이다.
  • 완전그래프의 간선 수: 서로 다른 두 정점 쌍의 수인 v(v−1)2\dfrac{v(v-1)}{2}개이다.
  • 인접행렬의 메모리: 간선 수와 무관하게 v×vv \times v 행렬이 필요하므로 O(v2)O(v^2)이며, O(v + e)는 인접리스트의 공간이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 09년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기