數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-在線瀏覽
2025-05-12 03:01本頁(yè)面
【正文】 ___。A．無(wú)向圖中的極大連通子圖稱為連通分量 B．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn) C．圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn) D．有向圖的遍歷不可采用廣度優(yōu)先搜索方法18．一個(gè)有向圖G的鄰接表存儲(chǔ)如下圖71所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是______。A．1，2，4，3，5，7，6 B．1，2，4，3，5，6，7C．1，2，4，5，6，3，7 D．1，2，3，4，5，7，61654327 圖72 一個(gè)無(wú)向圖20．對(duì)圖72所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行廣度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)序列______。A．極小連通子圖 B．極小子圖C．極大連通子圖 D．極大子圖22．設(shè)無(wú)向圖 G=(V, E) 和G’= (V’, E’)，如果 G’為G的生成樹(shù)，則下列說(shuō)法中不正確的是______。A．只有一棵 B．有一棵或多棵C．一定有多棵 D．可能不存在24．對(duì)于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹(shù)是指圖中任意一個(gè)________。 B．由n1條權(quán)值之和最小的邊構(gòu)成的子圖。D．由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的生成樹(shù)。A．是個(gè)有根有向圖 B．是個(gè)強(qiáng)連通圖C．含有多個(gè)入度為0的頂點(diǎn) D．含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量26．判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用____。A．O(n) B．O(n+e)C．O(n2) D．O(ne)28．求最短路徑的Floyd算法的時(shí)間復(fù)雜度為_(kāi)_____。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長(zhǎng)的回路 D．最短的回路30．下面說(shuō)法不正確的是______。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C．所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D．某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成二、填空題1．對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向圖G最多有_________條邊。3．對(duì)于具有n個(gè)頂點(diǎn)的有向圖，每個(gè)頂點(diǎn)的度最大可達(dá)___________。5．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為_(kāi)__________，所有鄰接表中的結(jié)點(diǎn)總數(shù)是__________。7．對(duì)于n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是__________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是___________。9．無(wú)向圖的連通分量是指___________。v1v2v3v4 ∧v5v6 ∧234 ∧35 ∧6 ∧4 63 ∧圖73 圖G的鄰接表11．n個(gè)頂點(diǎn)連通圖的生成樹(shù)一定有__________條邊。 13．Prim算法適用于求_________的網(wǎng)的最小生成樹(shù)，Kruskal算法適用于求________的網(wǎng)的最小生成樹(shù)。15．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。 17．Dijkstra算法從源點(diǎn)到其它各頂點(diǎn)的路徑長(zhǎng)度按________次序依次產(chǎn)生，該算法在邊上的權(quán)出現(xiàn)_________情況時(shí)，不能正確產(chǎn)生最短路徑。三、判斷題1．具有n個(gè)頂點(diǎn)的無(wú)向圖至多有n（n1）條邊。3．鄰接矩陣只儲(chǔ)存了邊的信息，沒(méi)有存儲(chǔ)頂點(diǎn)的信息。5．如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無(wú)向圖。7．如果表示某個(gè)圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。9．強(qiáng)連通分量是有向圖的極大連通子圖。11．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫時(shí)剛訪問(wèn)過(guò)的頂點(diǎn)。13．有向圖的遍歷不可采用廣度優(yōu)先搜索方法。15．設(shè)G為
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1