數(shù)據(jù)結(jié)構(gòu)圖練習(xí)試題

1、 范文范例 精心整理圖練習(xí)：1圖中有關(guān)路徑的定義是（ ）。A由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B由不同頂點(diǎn)所形成的序列C由不同邊所形成的序列 D上述定義都不是2設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En23一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（ ）。An-1 Bn Cn+1 Dnlogn；4要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊。An-l Bn Cn+l D2n5n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。An*n n（n） Cn2 Dn*（nl）6一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分

2、量。A0 B1 Cn-1 Dn7在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。A1/2 B2 C1 D48. 下列說(shuō)法不正確的是（ ）。A圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次 C圖的深度遍歷不適用于有向圖B遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D圖的深度遍歷是一個(gè)遞歸過(guò)程9無(wú)向圖G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ）。Aa,b,e,c,d,f Ba,c,

3、f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b10. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B從源點(diǎn)到匯點(diǎn)的最短路徑C最長(zhǎng)回路 D最短回路1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8C9D10A二、判斷題1.樹(shù)中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素。（ ）2在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。（ ）3對(duì)有n個(gè)頂點(diǎn)的無(wú)向圖，其邊數(shù)e與各頂點(diǎn)度數(shù)間滿足下列等式e=。（ ）4. 有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（ ）5. 有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（ ）6強(qiáng)連通圖的各頂點(diǎn)間均

4、可達(dá)。（ ）7鄰接多重表是無(wú)向圖和有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（ ）8. 十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（ ）9用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（ ）10有n個(gè)頂點(diǎn)的無(wú)向圖, 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（ ）11. 有向圖的鄰接矩陣是對(duì)稱(chēng)的。（ ）12無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)矩陣，有向圖的鄰接矩陣一定是非對(duì)稱(chēng)矩陣。（ ）13. 鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無(wú)向圖，而只能使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它。（ ）14. 用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與

5、圖的邊數(shù)無(wú)關(guān)。（ ） 15. 廣度遍歷生成樹(shù)描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。（ ）16任何無(wú)向圖都存在生成樹(shù)。（ ）17. 不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的.（ ）18帶權(quán)無(wú)向圖的最小生成樹(shù)必是唯一的。（ ）19. 最小代價(jià)生成樹(shù)是唯一的。（ ）20一個(gè)網(wǎng)（帶權(quán)圖）都有唯一的最小生成樹(shù)。（ ）21連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。（ ）22帶權(quán)的連通無(wú)向圖的最?。ù鷥r(jià)）生成樹(shù)（支撐樹(shù)）是唯一的。（ ）23帶權(quán)的連通無(wú)向圖的最小代價(jià)生成樹(shù)是唯一的。（ ）24. 最小生成樹(shù)問(wèn)題是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)。（ ）1.2. ×3.×4.

6、5;5.×6.7×8×9.×10. 11×12. ×13. ×14. 15.×16.×17.×18.×19.×20.×21.22. ×23×24三、填空題1.判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是_。2有向圖G的強(qiáng)連通分量是指_。3一個(gè)連通圖的_是一個(gè)極小連通子圖。4具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)。5若用n表示圖中頂點(diǎn)數(shù)目，則有_條邊的無(wú)向圖成為完全圖。6. 設(shè)無(wú)向圖 G 有n 個(gè)頂點(diǎn)和e 條邊，每個(gè)頂點(diǎn)Vi 的度為di（1<=i<

7、=n，則e=_7G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有_個(gè)頂點(diǎn)。8. 在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要_條弧。9在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)_。10設(shè)G為具有N個(gè)頂點(diǎn)的無(wú)向連通圖，則G中至少有_條邊。11n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的條數(shù)至少為_(kāi)。12如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有_棵生成樹(shù)。13N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有_條邊。14構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有_條弧。15有N個(gè)頂點(diǎn)的有向圖，至少需要量_條弧才能保證是連通的。16右圖中的強(qiáng)連通分量的個(gè)數(shù)為（ ）個(gè)。17N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有_個(gè)非零元素

8、。18在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的_；對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的_。19. 在有向圖的鄰接矩陣表示中，計(jì)算第I個(gè)頂點(diǎn)入度的方法是_。20. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為_(kāi)，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為_(kāi)。21. 已知一無(wú)向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為abecd，則采用的是_遍歷方法。答案：1.有n個(gè)頂點(diǎn)，n-1條邊的無(wú)向連通圖2.有向圖的極大強(qiáng)連通子圖3. 生成樹(shù)4. 45 5. n(

9、n-1)/2 6 . 7. 9 8. n 9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N 16. 3 17. 2（N-1） 18. 度 出度 19. 第I列非零元素個(gè)數(shù) 20.n 2e22. 深度優(yōu)先 23.寬度優(yōu)先遍歷 四、 應(yīng)用題1（1）如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，那么G1最多有多少條邊？G1最少有多少條邊？（2）如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？（3）如果G3是一個(gè)具有n個(gè)頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？ 2n個(gè)頂點(diǎn)的無(wú)向連通圖最少有多少

10、條邊？n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊？3 首先將如下圖所示的無(wú)向圖給出其存儲(chǔ)結(jié)構(gòu)的鄰接鏈表表示，然后寫(xiě)出對(duì)其分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果。 31057842169367589421 4給出圖G：（1）畫(huà)出G的鄰接表表示圖；（2）根據(jù)你畫(huà)出的鄰接表，以頂點(diǎn)為根，畫(huà)出G的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。5對(duì)一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些？6考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)（3）根據(jù)普利姆(Prim) 算法，求它的最小生成樹(shù) 從A點(diǎn)開(kāi)始（4）根據(jù)kruskal 算法，求它的最小生成樹(shù) 7考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)（3）根據(jù)普利姆(Prim) 算法，求它的最小生成樹(shù) 從1點(diǎn)開(kāi)始（4）根據(jù)kruskal 算法，求它的最小生成樹(shù)答案：1（1）G1最多n(n-1)/2條邊，最少n-1條邊 (2) G2最多n(n-1)條邊，最少n條邊 (3) G3最多n(n-1)條邊，最少n-1條邊 (注：弱連通有向圖指把有向圖看作無(wú)向圖時(shí)，仍是連通的) 2n-1，n 3深度優(yōu)先遍歷序列：125967384寬度優(yōu)先遍歷序列：123456789注：（1）鄰接表不