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

數(shù)據(jù)結(jié)構(gòu)圖練習(xí)試題數(shù)據(jù)結(jié)構(gòu)圖練習(xí)試題數(shù)據(jù)結(jié)構(gòu)圖練習(xí)試題資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)圖練習(xí)試題版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：圖練習(xí)：1．圖中有關(guān)路徑的定義是（）。A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B．由不同頂點(diǎn)所形成的序列C．由不同邊所形成的序列D．上述定義都不是2．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n23．一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（）。A．n-1B．nC．n+1D．nlogn；4．要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。A．n-lB．nC．n+lD．2n5．n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（）個(gè)連通分量，最多有（）個(gè)連通分量。A．0B．1C．n-1D．n7．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。A．1/2B．2C．1D．48.下列說法不正確的是（）。A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次C．圖的深度遍歷不適用于有向圖B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷D．圖的深度遍歷是一個(gè)遞歸過程9．無向圖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)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b10.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。A．從源點(diǎn)到匯點(diǎn)的最長路徑B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長回路D．最短回路8C9D10A二、判斷題1.樹中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素。（）2．在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。（）3．對有n個(gè)頂點(diǎn)的無向圖，其邊數(shù)e與各頂點(diǎn)度數(shù)間滿足下列等式e=。（）4.有e條邊的無向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（）5.有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（）6．強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（）7．鄰接多重表是無向圖和有向圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)。（）8.十字鏈表是無向圖的一種存儲結(jié)構(gòu)。（）9．用鄰接矩陣法存儲一個(gè)圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。（）10．有n個(gè)頂點(diǎn)的無向圖,采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（）11.有向圖的鄰接矩陣是對稱的。（）12．無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。（）13.鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權(quán)的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它。（）14.用鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（）15.廣度遍歷生成樹描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。（）16．任何無向圖都存在生成樹。（）17.不同的求最小生成樹的方法最后得到的生成樹是相同的.（）18．帶權(quán)無向圖的最小生成樹必是唯一的。（）19.最小代價(jià)生成樹是唯一的。（）20．一個(gè)網(wǎng)（帶權(quán)圖）都有唯一的最小生成樹。（）21．連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹是唯一的。（）22．帶權(quán)的連通無向圖的最?。ù鷥r(jià)）生成樹（支撐樹）是唯一的。（）23．帶權(quán)的連通無向圖的最小代價(jià)生成樹是唯一的。（）24.最小生成樹問題是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹。（）1.√2.×3.×4.×5.×6.√7×8×9.×10.√11×12.×13.×14.√15.×16.×17.×18.×19.×20.×21.√22.×23×24√三、填空題1.判斷一個(gè)無向圖是一棵樹的條件是______。2．有向圖G的強(qiáng)連通分量是指______。3．一個(gè)連通圖的______是一個(gè)極小連通子圖。4．具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為______。5．若用n表示圖中頂點(diǎn)數(shù)目，則有_______條邊的無向圖成為完全圖。6.設(shè)無向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)Vi的度為di（1<=i<=n〉，則e=______7．G是一個(gè)非連通無向圖，共有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)的無向連通圖，則G中至少有______條邊。11．n個(gè)頂點(diǎn)的連通無向圖，其邊的條數(shù)至少為______。12．如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有______棵生成樹。13．N個(gè)頂點(diǎn)的連通圖的生成樹含有______條邊。14．構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有______條弧。 15．有N個(gè)頂點(diǎn)的有向圖，至少需要量______條弧才能保證是連通的。16．右圖中的強(qiáng)連通分量的個(gè)數(shù)為（）個(gè)。17．N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有_______個(gè)非零元素。18．在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對于無向圖來說等于該頂點(diǎn)的______；對于有向圖來說等于該頂點(diǎn)的______。19.在有向圖的鄰接矩陣表示中，計(jì)算第I個(gè)頂點(diǎn)入度的方法是______。20.對于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖的鄰接表的表示，則表頭向量大小為______，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為______。21.已知一無向圖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開始遍歷圖，得到的序列為abecd，則采用的是______遍歷方法。答案：1.有n個(gè)頂點(diǎn)，n-1條邊的無向連通圖2.有向圖的極大強(qiáng)連通子圖3.生成樹4.455.n(n-1)/26.7.98.n9.2(n-1)10.N-111.n-112.n13.N-114.n15.N16.317.2（N-1）18.度出度19.第I列非零元素個(gè)數(shù)2e22.深度優(yōu)先23.寬度優(yōu)先遍歷四、應(yīng)用題1．（1）．如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無向圖，那么G1最多有多少條邊G1最少有多少條邊（2）．如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊G2最少有多少條邊（3）．如果G3是一個(gè)具有n個(gè)頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊G3最少有多少條邊2．n個(gè)頂點(diǎn)的無向連通圖最少有多少條邊n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊3．首先將如下圖所示的無向圖給出其存儲結(jié)構(gòu)的鄰接鏈表表示，然后寫出對其分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果。3105310578421693675894214．給出圖G：（1）．畫出G的鄰接表表示圖；（2）．根據(jù)你畫出的鄰接表，以頂點(diǎn)①為根，畫出G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。5．對一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些？

6．考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹（3）根據(jù)普利姆(Prim)算法，求它的最小生成樹從A點(diǎn)開始（4）根據(jù)kruskal算法，求它的最小生成樹7．考慮下圖：(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹（3）根據(jù)普利姆(Prim)算法，求它的最小生成樹從1點(diǎn)開始（4）根據(jù)kruskal算法，求它的最小生成樹答案：1．（1）G1最多n(n-1)/2條邊，最少n-1條邊(2)G2最多n(n-1)條邊，最少n條邊(3)G3最多n(n-1)條邊，最少n-1條邊(注：弱連通有向圖指把有向圖看作無向圖時(shí)，仍是連通的)2．n-1，n