5. 在乙個具有n個頂點的有向完全圖中,所含的邊數為( b )。
a. nb. n(n-1c. n(n-1)/2 d. n(n+1)/2
6. 在乙個無向圖中,若兩頂點之間的路徑長度為k,則該路徑上的頂點數為( b )。
a. kb. k+1c. k+2d. 2k
7. 對於乙個具有n個頂點的無向連通圖,它包含的連通分量的個數為( b )。
a. 0b. 1c. nd. n+1
8. 若乙個圖中包含有k個連通分量,若要按照深度優先搜尋的方法訪問所有頂點,則必須呼叫( a)次深度優先搜尋遍歷的演算法。
a. kb. 1c. k-1d. k+1
9. 若要把n個頂點連線為乙個連通圖,則至少需要( ac )條邊。
a. nb. n+1c. n-1d. 2n
10. 在乙個具有n個頂點和e條邊的無向圖的鄰接矩陣中,表示邊存在的元素(又稱為有效元素)的個數為( c d )。
a. nb. nec. ed. 2e
11. 在乙個具有n個頂點和e條邊的有向圖的鄰接矩陣中,表示邊存在的元素個數為( c )。
a. nb. nec. ed. 2e
12. 在乙個具有n個頂點和e條邊的無向圖的鄰接表中,邊結點的個數為( d )。
a. nb. nec. ed. 2e
13. 在乙個具有n個頂點和e條邊的有向圖的鄰接表中,儲存頂點單鏈表的表頭指標向量的大小至少為( a )。
a. nb. 2nc. ed. 2e
14. 在乙個無權圖的鄰接表表示中,每個邊結點至少包含( b )域。
a. 1b. 2c. 3d. 4
15. 對於乙個有向圖,若乙個頂點的度為k1,出度為k2,則對應鄰接表中該頂點單鏈表中的邊結點數為( b )。
a. k1b. k2c. k1-k2 d. k1+k2
16. 對於乙個有向圖,若乙個頂點的度為k1,出度為k2,則對應逆鄰接表中該頂點單鏈表中的邊結點數為( c )。
a. k1b. k2c. k1-k2 d. k1+k2
17. 對於乙個無向圖,下面( ba )種說法是正確的。
a. 每個頂點的入度等於出度 b. 每個頂點的度等於其入度與出度之和
c. 每個頂點的入度為0d. 每個頂點的出度為0
18. 在乙個有向圖的鄰接表中,每個頂點單鏈表中結點的個數等於該頂點的( d a )。
a. 出邊數 b. 入邊數 c. 度數d. 度數減1
19. 若乙個圖的邊集為,則從頂點a開始對該圖進行深度優先搜尋,得到的頂點序列可能為( db )。
a. a,b,c,f,d,eb. a,c,f,d,e,b
c. a,b,d,c,f,ed. a,b,d,f,e,c
20. 若乙個圖的邊集為,則從頂點a開始對該圖進行廣度優先搜尋,得到的頂點序列可能為( a d)。
a. a,b,c,d,e,fb. a,b,c,f,d,e
c. a,b,d,c,e,fd. a,c,b,f,d,e
21. 若乙個圖的邊集為,則從頂點1開始對該圖進行深度優先搜尋,得到的頂點序列可能為( a )。
a. 1,2,5,4,3b. 1,2,3,4,5
c. 1,2,5,3,4d. 1,4,3,2,5
22. 若乙個圖的邊集為,則從頂點1開始對該圖進行廣度優先搜尋,得到的頂點序列可能為( ac ).
a. 1,2,3,4,5b. 1,2,4,3,5
c. 1,2,4,5,3d. 1,4,2,5,3
23. 由乙個具有n個頂點的連通圖生成的最小生成樹中,具有( b )條邊。
a. nb. n-1c. n+1d. 2n
24. 已知乙個有向圖的邊集為,則由該圖產生的一種可能的拓撲序列為( a )。
a. a,b,c,d,e b. a,b,d,e,b c. a,c,b,e,d d. a,c,d,b,e
1. 在乙個圖中,所有頂點的度數之和等於所有邊數的___2____倍。
2. 在乙個具有n個頂點的無向完全圖中,包含有____n(n-1)/2__條邊,在乙個具有n個頂點的有向完全圖中,包含有__n(n-1)___條邊。
3. 假定乙個有向圖的頂點集為,邊集為,則出度為0的頂點個數為__2___,入度為1的頂點個數為__6____。
4. 在乙個具有n個頂點的無向圖中,要連通所有頂點則至少需要__n_n-1__條邊。
5. 表示圖的兩種儲存結構為___順序____和____鏈式______。鄰接表和鄰接矩陣
6. 在乙個連通圖中存在著___1__個連通分量。
7. 圖中的一條路徑長度為k,該路徑所含的頂點數為___k+1___。
8. 若乙個圖的頂點集為,邊集為,則該圖含有__3_____個連通分量。
9. 對於乙個具有n個頂點的圖,若採用鄰接矩陣表示,則矩陣大小至少為___n______n___。
10. 對於具有n個頂點和e條邊的有向圖和無向圖,在它們對應的鄰接表中,所含邊結點的個數分別為___2e_和__e____。
11. 在有向圖的鄰接表和逆鄰接表表示中,每個頂點鄰接表分別鏈結著該頂點的所有____出邊__和___入邊___結點。
12. 對於乙個具有n個頂點和e條邊的無向圖,當分別採用鄰接矩陣和鄰接表表示時,求任一頂點度數的時間複雜度分別為____o(ne)o(n)__和___o(n^2)o(e/n)_。 o(n^2),o(e)
13. 假定乙個圖具有n個頂點和e條邊,則採用鄰接矩陣和鄰接表表示時,其相應的空間複雜度分別為_____o(n^2)___和___o(n+e)_____。
14. 乙個圖的邊集為,從頂點a出發進行深度優先搜尋遍歷得到的頂點序列為___acdeb____,從頂點a出發進行廣度優先搜尋遍歷得到的頂點序列為
15. 乙個圖的邊集為,從頂點a出發進行深度優先搜尋遍歷得到的頂點序列為從頂點a出發進行廣度優先搜尋遍歷得到的頂點序列為
16. 圖的____深度__優先搜尋遍歷演算法是一種遞迴演算法,圖的___廣度___優先搜尋遍歷演算法需要使用佇列。
17. 對於乙個具有n個頂點和e條邊的連通圖,其生成樹中的頂點數和邊數分別為____n___和____en-1___。
18. 若乙個連通圖中每個邊上的權值均不同,則得到的最小生成樹是___唯一的__(唯一/不唯一)的。
19. 根據圖的儲存結構進行某種次序的遍歷,得到的頂點序列是唯一(唯一/不唯一)的。
20. 假定乙個有向圖的邊集為,對該圖進行拓撲排序得到的頂點序列為___aebdcf___。
1. 對於乙個無向圖6-11(a),假定採用鄰接矩陣表示,試分別寫出從頂點0出發按深度優先搜尋遍歷得到的頂點序列和按廣度優先搜尋遍歷得到的頂點序列。
2. 對於乙個有向圖6-11(b),假定採用鄰接表表示,並且假定每個頂點單鏈表中的邊結點是按出邊鄰接點序號從大到小的次序鏈結的,試分別寫出從頂點0出發按深度優先搜尋遍歷得到的頂點序列和按廣度優先搜尋遍歷得到的頂點序列。
注:每一種序列都是唯一的,因為都是在儲存結構上得到的
3. 已知乙個無向圖的鄰接矩陣如圖6-12(a)所示,試寫出從頂點0出發分別進行深度優先和廣度優先搜尋遍歷得到的頂點序列。
4. 已知乙個無向圖的鄰接表如圖6-12(b)所示,試寫出從頂點0出發分別進行深度優先和廣度優先搜尋遍歷得到的頂點序列。
5. 已知圖6-13所示的乙個網,按照prim方法,從頂點v1 出發,表示出該網的最小生成樹的產生過程。
6. 已知圖6-13所示的乙個網,按照kruskal方法,表示出該網的最小生成樹的產生過程。
7. 圖6-14所示為乙個有向網圖及其帶權鄰接矩陣,要求對有向圖採用dijkstra演算法,求從v0 到其餘各頂點的最短路徑。
8. 圖6-15給出了乙個具有15個活動、11個事件的工程的aoe網,求關鍵路徑。
建築施工圖結構施工圖複習題
第十章建築施工圖第十一章結構施工圖 複習題一 單選題 第一房屋建築工程圖的基本知識 1 詳圖索引符號中的圓圈直徑是 a 14mm b 12mm c 10mm d 8mm 2 對於 一般用分軸線表達其位置。a 隔牆 b 柱子 c 大樑 d 屋樑 3 定位軸線一般用表示。a 細實線b 粗實線c 細點劃線...
第七章圖習題 資料結構
9.下列說法不正確的是 a 圖的遍歷是從給定的源點出發每乙個頂點僅被訪問一次 b 遍歷的基本演算法有兩種 深度遍歷和廣度遍歷 c 圖的深度遍歷不適用於有向圖 d 圖的深度遍歷是乙個遞迴過程 10 下面哪一方法可以判斷出乙個有向圖是否有環 迴路 a 深度優先遍歷 b.拓撲排序 c.求最短路徑 d.求關...
結構施工圖練習題 很好很實用
結構施工圖練習題 一 選擇題 1 下列表示預應力空心板和構造柱符號的是 b.yt gz 2 某梁的編號為kl2 2a 表示的含義為 a 第2號框架梁,兩跨,一端有懸挑 b 第2號框架梁,兩跨,兩端有懸挑 c 第2號框支梁,兩跨,一端無懸挑 d 第2號框架梁,兩跨 3.某框架柱的配筋為 8 100 2...