數(shù)據(jù)結構第六章圖練習題及答案詳細解析版_第1頁
已閱讀1頁,還剩18頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、圖1.填空題填空題⑴設無向圖設無向圖G中頂點數(shù)為中頂點數(shù)為n,則圖,則圖G至少有(至少有()條邊,至多有()條邊,至多有()條邊;若)條邊;若G為有向圖,則至少有為有向圖,則至少有()條邊,至多有()條邊,至多有()條邊。)條邊?!窘獯稹俊窘獯稹?,n(n1)2n(n1)2,0,n(n1)n(n1)【分析】圖的頂點集合是有窮非空的,而邊集可以是空集;邊數(shù)達到最多的圖稱為完全圖,在完全圖中,【分析】圖的頂點集合是有窮非空的,而邊集可以是空

2、集;邊數(shù)達到最多的圖稱為完全圖,在完全圖中,任意兩個頂點之間都存在邊。任意兩個頂點之間都存在邊。⑵任何連通圖的連通分量只有一個,即是(任何連通圖的連通分量只有一個,即是()。)?!窘獯稹科渥陨怼窘獯稹科渥陨恝菆D的存儲結構主要有兩種,分別是(圖的存儲結構主要有兩種,分別是()和()和()。)?!窘獯稹苦徑泳仃嚕徑颖怼窘獯稹苦徑泳仃?,鄰接表【分析】這是最常用的兩種存儲結構,此外,還有十字鏈表、鄰接多重表、邊集數(shù)組等?!痉治觥窟@是最常用的兩

3、種存儲結構,此外,還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷已知無向圖已知無向圖G的頂點數(shù)為的頂點數(shù)為n,邊數(shù)為,邊數(shù)為e,其,其鄰接表鄰接表表示的空間復雜度為(表示的空間復雜度為()。)?!窘獯稹浚稀窘獯稹浚?ne)(ne)【分析】在無向圖的鄰接表中,頂點表有【分析】在無向圖的鄰接表中,頂點表有n個結點,邊表有個結點,邊表有2e2e個結點,共有個結點,共有n2en2e個結點,其空間復雜個結點,其空間復雜度為O度為O(n2e)=(n2e)

4、=O(ne)(ne)。⑸已知一個有向圖的鄰接矩陣表示,計算第已知一個有向圖的鄰接矩陣表示,計算第j個頂點的個頂點的入度入度的方法是(的方法是()。)。【解答】求第【解答】求第j列的所有元素之和列的所有元素之和⑹有向圖有向圖G用鄰接矩陣用鄰接矩陣A[n][n]A[n][n]存儲,其第存儲,其第i行的所有元素之和等于頂點行的所有元素之和等于頂點i的(的()。)?!窘獯稹砍龆取窘獯稹砍龆娶苙個頂點的個頂點的強連通圖強連通圖至少有(至少有()條

5、邊,其形狀是()條邊,其形狀是()。)。AnBn1n1Cn1n1Dn(n1)n(n1)E無回路無回路F有回路有回路G環(huán)狀環(huán)狀H樹狀樹狀【解答】【解答】A,G⑶含n個頂點的連通圖中的任意一條簡單路徑,其長度不可能超過(個頂點的連通圖中的任意一條簡單路徑,其長度不可能超過()。)。A1Bn2n2Cn1n1Dn【解答】【解答】C【分析】若超過【分析】若超過n1n1,則路徑中必存在重復的頂點。,則路徑中必存在重復的頂點。⑷對于一個具有對于一個具

6、有n個頂點的無向圖,若采用鄰接矩陣存儲,則該矩陣的大小是(個頂點的無向圖,若采用鄰接矩陣存儲,則該矩陣的大小是()。)。AnB(n1)2(n1)2Cn1n1Dn2n2【解答】【解答】D⑸圖的生成樹(圖的生成樹(),),n個頂點的生成樹有(個頂點的生成樹有()條邊。)條邊。A唯一唯一B不唯一不唯一C唯一性不能確定唯一性不能確定DnEn11Fn1n1【解答】【解答】C,F(xiàn)⑹設無向圖設無向圖G=(VG=(VE)E)和GG=(V=(VEE),如

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論