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