數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(完整版)
【正文】 j是否有邊相連的方法是__________，求任意一個頂點的度的方法是___________。A．從源點到匯點的最長路徑 B．從源點到匯點的最短路徑C．最長的回路 D．最短的回路30．下面說法不正確的是______。 B．由n1條權(quán)值之和最小的邊構(gòu)成的子圖。A．無向圖中的極大連通子圖稱為連通分量 B．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 D．有向圖的遍歷不可采用廣度優(yōu)先搜索方法18．一個有向圖G的鄰接表存儲如下圖71所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點v1出發(fā)，所得到的頂點序列是______。A．n B．e C．2n D．2e10．在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有______鄰接點。 A．l/2 B．1 C．2 D．42．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的______倍。A．n B．nn C．n1 D．(nl) (nl)7．無向圖的鄰接矩陣是一個______。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷15．如果無向圖G必須進行二次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確的是______。A．G’為G的連通分量 B．G’為G的無環(huán)子圖C．G’為G的子圖 D．G’為G的極小連通子圖且V’＝V。A．求關(guān)鍵路徑的方法 B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法 D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時間復(fù)雜度為______。4．若無向圖G的頂點度數(shù)最小值大于___________時，G至少有一條回路。12．一個連通圖的___________是一個極小連通子圖。2．有向圖中各頂點的入度之和等于各頂點的出度之和。10．對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個頂點，則該圖一定是完全圖。18．只要無向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是惟一的。26．在關(guān)鍵路徑的活動都是關(guān)鍵活動，而關(guān)鍵活動未必在關(guān)鍵路徑上。 （2）鄰接表 （3）強連通分量（4）對照鄰接表，給出從頂點1出發(fā)的深度優(yōu)先遍歷序列。14．如圖79所示的AOE網(wǎng)，求：（1）每項活動ai最早開始時間e(ai)和最遲開始時間l(ai)。（4）計算圖G中出度為0的頂點數(shù)。9．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到v的長度為1的所有簡單路徑。14．采用堆排序來實現(xiàn)Kruskal算法，并說明時間復(fù)雜度O(elog2e)的理由。若有向圖中存在一個頂點v，從v可以通過路徑到達圖中其他所有頂點，則稱v為該有向圖的根。 。20．對于一個使用鄰接表存儲的帶權(quán)有向圖G。設(shè)計一個算法，求出最小代價。11．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，從如圖710所示的無向圖G中找出滿足如下條件的一條路徑：（1）給定起點vi和終點vj。3．設(shè)計一個將鄰接表轉(zhuǎn)換為鄰接矩陣的算法。（3）哪些是關(guān)鍵活動a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某項活動，當(dāng)其提高速度后能使整個工程縮短工期？圖79五、算法設(shè)計題1．假設(shè)圖G采用鄰接表存儲，分別設(shè)計實現(xiàn)以下要求的算法：（1）求出圖G中每個頂點的入度。143256圖75 一個有向圖8．什么樣的圖其最小生成樹是惟一的？9．已知帶權(quán)連通圖G(V,E)鄰接表如圖76所示，請畫出該圖，并分別以深度優(yōu)先和廣度優(yōu)先遍
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1