數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-wenkub
2023-04-09 03:01:54 本頁面
【正文】 D．按層遍歷14．采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的______算法。A．n B．e C．2n D．2e10．在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有______鄰接點(diǎn)。A．n(n1) B．n(n+l) C．n(nl)/2 D．n(n+l)/26．對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為______。 A．l/2 B．1 C．2 D．42．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的______倍。A．l/2 B．1 C．2 D．43．一個(gè)具有n個(gè)頂點(diǎn)的無向圖最多包含______條邊。A．n B．nn C．n1 D．(nl) (nl)7．無向圖的鄰接矩陣是一個(gè)______。A．入邊 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊11．在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有______鄰接點(diǎn)。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷15．如果無向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)，則下列說法中不正確的是______。A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3 D．v1，v2，v5，v3，v4 234 ∧35 ∧5 ∧4 ∧v1v2v3v4 ∧v5圖71 一個(gè)有向圖的鄰接表19．對(duì)圖72所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問序列______。A．G’為G的連通分量 B．G’為G的無環(huán)子圖C．G’為G的子圖 D．G’為G的極小連通子圖且V’＝V。C．由n1條權(quán)值之和最小的邊構(gòu)成的連通子圖。A．求關(guān)鍵路徑的方法 B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法 D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為______。A．在AOE網(wǎng)中，減少任一關(guān)鍵活動(dòng)的權(quán)值后，整個(gè)工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動(dòng)的權(quán)值和C．在關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必須在關(guān)鍵路徑上D．A和B31．下面說法不正確的是______。4．若無向圖G的頂點(diǎn)度數(shù)最小值大于___________時(shí)，G至少有一條回路。8．對(duì)于n個(gè)頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是__________。12．一個(gè)連通圖的___________是一個(gè)極小連通子圖。16．從源點(diǎn)到匯點(diǎn)長度最長的路徑稱為關(guān)鍵路徑，該路徑上的活動(dòng)稱為________。2．有向圖中各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。6．如果表示有向圖的鄰接矩陣是對(duì)稱矩陣，則該有向圖一定是有向完全圖。10．對(duì)有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個(gè)頂點(diǎn)，則該圖一定是完全圖。14．連通圖的生成樹包含了圖中所有頂點(diǎn)。18．只要無向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是惟一的。22．任何有向無環(huán)圖的結(jié)點(diǎn)都可以排成拓?fù)渑判颍彝負(fù)湫蛄胁晃┮弧?6．在關(guān)鍵路徑的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)未必在關(guān)鍵路徑上。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。 （2）鄰接表 （3）強(qiáng)連通分量（4）對(duì)照鄰接表，給出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷序列。39822
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1