數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)題及答案cs

1、第七章圖一、1.圖2.無(wú)向完全圖3.有向完全圖4.子圖5.連通分量6.圖的遍歷7.圖的最小生成樹(shù)一、填空題8.拓?fù)渑判蛟O(shè) x,y 是圖 G 中的兩頂點(diǎn)，則（x,y）與（y,x）被認(rèn)為邊，但與是的兩條弧。若頂點(diǎn)的偶對(duì)是有序的，此圖為圖，有序偶對(duì)用括號(hào)括起來(lái)；若頂點(diǎn)偶對(duì)是無(wú)序的，此圖為圖，無(wú)序偶對(duì)用括號(hào)括起來(lái)。設(shè) x,yV，若E,則表示有向圖 G 中從 x 到y(tǒng) 的一條，x 稱(chēng)為 點(diǎn)，y 稱(chēng)為點(diǎn)。若（x,y）E，則在無(wú)向圖 G 中x 和y 間有一條。在無(wú)向圖中，若頂點(diǎn) x 與y 間有邊（x,y），則 x 與 y 互稱(chēng)，邊（x,y）稱(chēng)為與頂點(diǎn)x 和 y。一個(gè)具有n 個(gè)頂點(diǎn)的完全無(wú)向圖的邊數(shù)為。一個(gè)具

2、有 n 個(gè)頂點(diǎn)的完全有向圖的弧度數(shù)為。圖的邊或弧附帶的數(shù)值叫。每條邊或弧都帶權(quán)的圖稱(chēng)為或。無(wú)向圖中的頂點(diǎn) V 的度是，記為。若G 是一個(gè)有向圖，則把以頂點(diǎn) V 為終點(diǎn)的弧的數(shù)目稱(chēng)為 V 的，記為；把以頂點(diǎn) V 為始點(diǎn)的弧的數(shù)目稱(chēng)為 V 的，稱(chēng)為。有向圖中頂點(diǎn) V 的度定義為 D（V）=。路徑長(zhǎng)度定義為。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為或。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)為。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)的回路，稱(chēng)為或。在無(wú)向圖中，如果從頂點(diǎn) v 到頂點(diǎn) v有路徑，則稱(chēng) v 和 v是的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn) vi,vjV，且 vi 和vj 都是連通的，則稱(chēng) G 為。連通分

3、量是無(wú)向圖中的連通子圖。11.通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的一個(gè)。12.若連通圖 G 的頂點(diǎn)個(gè)數(shù)為 n，則 G 的生成樹(shù)的邊數(shù)為。如果 G 的一個(gè)子圖 G的邊數(shù)，則 G中一定有環(huán)。相反，如果 G的邊數(shù)，則G一定不連通。 13.無(wú)向圖的鄰接矩陣是一個(gè)矩陣，有向圖的鄰接矩陣不一定是矩陣。14.對(duì)于無(wú)向圖的鄰接矩陣，頂點(diǎn) vi 的度是。對(duì)于有向圖的鄰接矩陣，頂點(diǎn) vi 的出度OD（vi）為，頂點(diǎn) vi 的入度 ID(vi)是。15.圖的結(jié)構(gòu)主要有和兩種。鄰接表表示法是借助來(lái)反映頂點(diǎn)間的鄰接關(guān)系，所以稱(chēng)這個(gè)單鏈表為鄰接表。對(duì)無(wú)向圖，若它有 n 頂點(diǎn) e 條邊，則其鄰接表中需要個(gè)結(jié)點(diǎn)。其中，個(gè)結(jié)

4、點(diǎn)鄰接表，個(gè)結(jié)點(diǎn)頂點(diǎn)表。18.對(duì)有向圖，若它有 n 頂點(diǎn) e 條邊，則其鄰接表中需要個(gè)結(jié)點(diǎn)。其中，個(gè)結(jié)點(diǎn)鄰接表，個(gè)結(jié)點(diǎn)頂點(diǎn)表。在鄰接表上，無(wú)向圖中頂點(diǎn) vi 的度恰為。對(duì)有向圖，頂點(diǎn) vi 的出度是。為了求入度，必須遍歷整個(gè)鄰接表，在所有單鏈表中，其鄰接點(diǎn)域的值為的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn) vi 的入度。遍歷圖的基本方法有優(yōu)先搜索和優(yōu)先搜索兩種。以下是圖的深度優(yōu)先算法，請(qǐng)?jiān)谔幪畛溥m當(dāng)?shù)恼Z(yǔ)句。Dfs(GraphTp g,v)odeTp *p; f(“%d”,v);prvisitedv=1;p=; while(p!=NULL)if(!) Dfs(g,p-adjvex); p=;22.以下是圖的廣度優(yōu)先搜索

5、算法，請(qǐng)?jiān)谔幪畛溥m當(dāng)?shù)恼Z(yǔ)句。 Bfs(GraphTp g,v)QueptrTp Q;odeTp *p;InitQueue(&Q);prf(“%d”,v);visitedv=1;while(!EmptyQueue(Q); p=g.adjlistv. while(p!=NULL)arc;if(!visitedp-adjvex)prf(“%d”,p-adjvex);visited-adjvex=1; EnQueue(&Q,p-adjvex);深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是；廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是。任何連通圖的連通分量只有一個(gè)，即。對(duì)具有 n 個(gè)頂點(diǎn)

6、的圖其生成樹(shù)有且僅有條邊，即生成樹(shù)是圖的邊數(shù)的連通圖。一個(gè)圖的的表示法是惟一的，而表示法是不惟一的。對(duì)無(wú)向圖，其鄰接矩陣是一個(gè)關(guān)于對(duì)稱(chēng)的矩陣。28.在有向圖的鄰接矩陣上，由第 i 行個(gè)結(jié)點(diǎn)的入度。到第個(gè)結(jié)點(diǎn)的出度，而由第 j 列到第29.的有向圖，其全部頂點(diǎn)有可能排成一個(gè)拓?fù)湫蛄小?0.一個(gè)有向圖 G中若有弧,、和,則在圖 G的拓?fù)湫蛄兄校旤c(diǎn)Vi、Vj和 Vk 的相對(duì)位置為。二、單項(xiàng)選擇題1.設(shè)有無(wú)向圖 G=（V，E）和 G=（V,E）,如 G為G 的生成樹(shù)，則下面不正確的說(shuō)法是（）G為G 的子圖G為G 的極小連通子圖且 V=V 2.任何一個(gè)帶權(quán)的無(wú)向連通圖的最小生成樹(shù)（G為G 的連通分量G

7、是G 的無(wú)環(huán)子圖）只有一棵3.設(shè)圖G 采用鄰接表有一棵或多棵一定有多棵可能不存在，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為（）O(n)O(n+e)O(n*n)O(n*e)4.含n 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（）1 n/2 n-1n5一有向圖 G 的鄰接表出發(fā)，所得到的頂點(diǎn)序列是結(jié)構(gòu)如圖單項(xiàng)選擇 5 所示?，F(xiàn)按深度優(yōu)先遍歷算法，從頂點(diǎn) V1（）V1,V3, V2 ,V4, V5V1, V3, V4, V2, V5 V1,V2,V3, V4, V5）倍。4V1,V3,V4,V5 ,V26.在無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的（0.5127.在有向圖中，所有頂點(diǎn)的入度之和是所有頂

8、點(diǎn)出度之和的（）倍。4（）0.5在圖的鄰接表先根遍歷在圖的鄰接表先根遍歷 1 2結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類(lèi)似于二叉樹(shù)上的（按層次遍歷（按層次遍歷） 中根遍歷 后根遍歷結(jié)構(gòu)上執(zhí)行廣度優(yōu)先搜索遍歷類(lèi)似于二叉樹(shù)上的）中根遍歷后根遍歷10判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒?，還可以利用（）求關(guān)鍵路徑方法求最短路徑的 Dijkstra 方法廣度優(yōu)先遍歷方法深度優(yōu)先遍歷方法在圖單項(xiàng)選擇中，從頂點(diǎn) V1 出發(fā)，按廣度優(yōu)先遍歷圖的頂點(diǎn)序列是V1 V3 V5 V4 V2 V6 V7 V1 V2 V4 V7 V6 V5 V3 V1 V5 V3 V4 V2 V7 V6 V1在圖單項(xiàng)選擇中，從頂點(diǎn)

9、V1 出發(fā),廣度遍歷圖的頂點(diǎn)序列是（V4 V7 V2 V6 V5（）V3）V1 V5 V3 V4 V2 V6 V7 V1 V5 V3 V4 V2 V7 V6 V1 V7 V2 V6 V413.設(shè)有 6 個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（ ）條邊能確保是V5V3 V1通圖。V2 V4 V7 V6 V5 V3（） 5 6 7 814.以下說(shuō)法正確的是連通圖的生成樹(shù)，是該連通圖的一個(gè)極小連通子圖。無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，有向圖的鄰接矩陣一定是不對(duì)稱(chēng)的。任何一個(gè)有向圖，其全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄?。有回路的圖不能進(jìn)行拓?fù)渑判颉?5 以下說(shuō)法錯(cuò)誤的是（）（）用相鄰矩陣法一個(gè)圖時(shí)，在不考慮壓縮的情況下，所

10、占用的空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。鄰接表法只能用于有向圖的，而相鄰矩陣法對(duì)于有向圖和無(wú)向圖的都適用。無(wú)向圖的相鄰矩陣是對(duì)稱(chēng)的，因此只要相鄰矩陣的下（或上）三角部分就可以了用相鄰矩陣 A 表示圖，判定任意兩個(gè)結(jié)點(diǎn) Vi 和 Vj 之間是否有長(zhǎng)度為 m 的路徑相連，則只要檢查 A 的第 i 行第 j 列的元素是否為 0 即可。16以下說(shuō)法正確的是連通分量是無(wú)向圖中的極小連通子圖。強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。（）在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn) a 在頂點(diǎn) b 之前，則圖中必有一條弧。對(duì)有向圖 G,如果從任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能該圖一定是完全圖。四、

11、簡(jiǎn)答及應(yīng)用到每個(gè)頂點(diǎn)，則123簡(jiǎn)述圖的鄰接矩陣表示的類(lèi)型定義簡(jiǎn)述圖的鄰接表的類(lèi)型定義。給出無(wú)向圖簡(jiǎn)答題 3 中g(shù)1 的鄰接矩陣和鄰接表。分別給出圖簡(jiǎn)答題 3 中 g2 的鄰接矩陣、鄰接表和逆鄰接表。分別給出圖簡(jiǎn)答題 3 中 g3 從 v5 出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點(diǎn)序列。求出圖簡(jiǎn)答題 6-1 的連通分量。求出帶權(quán)圖簡(jiǎn)答題 7-1 的最小生成樹(shù)寫(xiě)出有向圖簡(jiǎn)答題 8-1 的拓?fù)渑判蛐蛄?。給出網(wǎng)圖簡(jiǎn)答題 9-1 的鄰接矩陣表示。已知連通網(wǎng)的鄰接矩陣如下，試畫(huà)出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹(shù)。11對(duì)于圖簡(jiǎn)答題 11-1 從其鄰接表中回答下列問(wèn)題：（1）（2）（3）圖中有

12、多少條?。繄D中是否存在從 i 到j(luò) 的?。咳绾吻箜旤c(diǎn) i 的出度？12圖簡(jiǎn)答題 11-1 所示為一有向圖，請(qǐng)給出該圖的下述要求：（1）（2）（3）（4）每個(gè)頂點(diǎn)的入/出度。鄰接矩陣。鄰接表。逆鄰接表。拓?fù)渑判虻慕Y(jié)果不是唯一的，對(duì)圖簡(jiǎn)答題 13-1 進(jìn)行拓?fù)渑判颍噷?xiě)出其中任意 5 個(gè)不同的拓?fù)渑判蛄?。?duì)m 個(gè)頂點(diǎn)的無(wú)向圖 G，采用鄰接矩陣，如何判別下列有關(guān)問(wèn)題：（1）（2）（3）圖中有多少條邊？任意兩個(gè)頂點(diǎn) i 和j 是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？15.已知圖 G 的鄰接表如圖簡(jiǎn)答題 15-1 所試，頂點(diǎn) V1 為出發(fā)點(diǎn)，完成要求：（1）（2）（3）（4）深度優(yōu)先搜索的頂點(diǎn)序列；廣度優(yōu)先搜索的頂點(diǎn)序列；由深度優(yōu)先搜索得到的一棵生成樹(shù)；由廣度優(yōu)先搜索得到的一棵生成樹(shù)。Vertexfi16.設(shè)有一無(wú)向圖 G=(V,E),其中 V=1,2,3,4,5,6,E=(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),( 3,5)。按上述順序輸入后，畫(huà)出其相應(yīng)的鄰接表；在該鄰接表上，從頂點(diǎn) 4 開(kāi)始，寫(xiě)出 DFS 序列和 BFS 序列。17圖簡(jiǎn)答題 17-1 所示為一無(wú)向連通網(wǎng)絡(luò)，先要求根據(jù) prim 算法