數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(更新版)
【正文】 歷該圖，寫出遍歷中結(jié)點(diǎn)的序列，并畫出該圖的一棵最小生成樹，其中表結(jié)點(diǎn)的3個(gè)域各為：頂點(diǎn)號邊上所帶的權(quán)指針v1v2v3v4v54 4 ∧4 18 ∧5 22 ∧5 10 ∧1 161 122 12 1 182 223 163 22 23 44 10 ∧1.2.34.5圖76 連通圖的鄰接表10．已知世界6大城市為：北京（B）紐約（N）巴黎（P）倫敦（L）東京（T）墨西哥城（M）試用由表1給出的交通網(wǎng)確定最小生成樹，并說明所使用的方法及其時(shí)間復(fù)雜度。28．所有關(guān)鍵活動都提前完成，則整個(gè)工程將提前完成。20．有環(huán)圖也能進(jìn)行拓?fù)渑判颉?2．圖的深度優(yōu)先搜索中一般要采用棧來暫時(shí)剛訪問過的頂點(diǎn)。4．對同一個(gè)有向圖，只保存出邊的鄰接表中結(jié)點(diǎn)的數(shù)目總是和只保存入邊的鄰接表中結(jié)點(diǎn)的數(shù)目一樣多。 14．在AOV圖中，頂點(diǎn)表示________,有向邊表示________。6．已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是____________。A．O(n) B．O(ne)C．O(n2) D．O(n3) 29．關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中______。A．由n1條權(quán)值最小的邊構(gòu)成的子圖。A．連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程 B．圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征 C．非連通圖不能用深度優(yōu)先搜索法 D．圖的遍歷要求每一頂點(diǎn)僅被訪問一次17．下列說法中不正確的是______。A．n B．e C．2n D．2e9．對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(有)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為______。第7章 圖一、單項(xiàng)選擇題1．在一個(gè)無向圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的______倍。A．對稱矩陣 B．零矩陣 C．上三角矩陣 D．對角矩陣8．對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(有)向圖，若采用鄰接表表示，則表頭向量的大小為______。A．G肯定不是完全圖 B．G一定不是連通圖C．G中一定有回路 D．G有二個(gè)連通分量16．下列有關(guān)圖遍歷的說法不正確的是______。A．只有一棵 B．有一棵或多棵C．一定有多棵 D．可能不存在24．對于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(gè)________。A．O(n) B．O(n+e)C．O(n2) D．O(ne)28．求最短路徑的Floyd算法的時(shí)間復(fù)雜度為______。5．對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為___________，所有鄰接表中的結(jié)點(diǎn)總數(shù)是__________。 13．Prim算法適用于求_________的網(wǎng)的最小生成樹，Kruskal算法適用于求________的網(wǎng)的最小生成樹。3．鄰接矩陣只儲存了邊的信息，沒有存儲頂點(diǎn)的信息。11．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫時(shí)剛訪問過的頂點(diǎn)。19．只要無向網(wǎng)中有權(quán)值相同的邊，其最小生成樹就可能不是惟一的。27．關(guān)鍵活動不按期完成就會影響整個(gè)工程的完成時(shí)間。（5）對照鄰接表，給出從頂點(diǎn)3出發(fā)的深度優(yōu)先遍歷序列。（2）完成此工程最少需要多少天（設(shè)邊上權(quán)值為天數(shù)）。（5）判斷圖G中是否存在邊i,j。10．假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的所有簡單路徑。15．如圖711是一個(gè)城市連接圖，圖中權(quán)值表示兩城市之間的里程（單位為100km），現(xiàn)要設(shè)計(jì)一條鐵路貫通所有城市（即從一個(gè)任一城市可以到達(dá)其他城市）。19．設(shè)計(jì)一個(gè)算法，判斷有向圖是否存在回
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1