各章習(xí)題-第八章試題

數(shù)據(jù)結(jié)構(gòu)課程（本科） A.頂 B. C. D.權(quán)在無向圖中定義頂點(diǎn)vi與vj之間的路徑為從vi到達(dá)vj的一個(gè) A.頂點(diǎn)序 B.邊序 C.權(quán)值總 D.邊的條 A.權(quán) B.頂 C. D.邊與頂點(diǎn) A.n- B.n(n- C. D.n(n-n個(gè)頂點(diǎn)的連通圖至少有 A.n- B. C. D. )倍A. B. C. D.若采用鄰接矩陣法一個(gè)n個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè) )A.上三角矩 B.稀疏矩 C.對(duì)角矩 D.對(duì)稱矩 A.先 B.中 C.后 D.層 A.先 B.中 C.后 D.層在用Kruskal算法求解帶權(quán)連通圖的最小（代價(jià)）生成樹時(shí)，通常采用一個(gè)（ A.位向 B. C.并查 D.生成樹頂點(diǎn)集在用Kruskal算法求解帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹時(shí)，選擇權(quán)值最小的邊的原則是該邊不能在 A.重 B.有向 C.回 D.權(quán)值重復(fù)的 A.非 B.非 C.非 D.非在通圖中進(jìn)行深度優(yōu)先搜索得到一棵深度優(yōu)先生成樹，樹根結(jié)點(diǎn)是關(guān)節(jié)點(diǎn)的充要條件是它至少 ）。A. B. C. D.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表作為其表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間 A. B. C. D. A. B. C. D.設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖，如果V1V2，E1E2，則稱 G1是G2的子 B.G2是G1的子C.G1是G2的連通分 D.G2是G1的連通分 入 B.出C.入度與出度之 D.(入度﹢出度 A.極 B.連 C.極小連 D.無n(n＞1)個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有 n- B. n(n- D.n(n-在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的 A.某個(gè)最 B.任何最 C.廣度優(yōu) 對(duì)于具有e條邊的無向圖，它的鄰接表中有 A.e- B. C.2(e- D.對(duì)于的帶權(quán)有向圖，從頂點(diǎn)1到頂點(diǎn)5的最短路徑為 A.1,4, B.1,2,3, C.1,4,3, D.1,2,4,3,22 A.n- B. C.n(n- D.n(n-一個(gè)有n個(gè)頂點(diǎn)和n條邊的無向圖一定是 A.連通 B.不連通 C.無環(huán) D.有環(huán) A. B.n(n- C. D.n(n- B.求一個(gè)頂點(diǎn)的鄰接C.進(jìn)行圖的深度優(yōu)先遍 D.進(jìn)行圖的廣度優(yōu)先遍 A. B. C. D. A.無 D.稠密設(shè)一個(gè)有n個(gè)頂點(diǎn)和e A. B. C. D. A. B.隊(duì) C.二叉 D.參考答案：1.6.2.7.3.8.4.9.5.10.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30. 關(guān)n(n﹥0)個(gè)頂點(diǎn)的無向圖最多 條邊n(n﹥0)個(gè)頂點(diǎn)的連通無向圖最少 0103G的鄰接矩陣為10

0，則圖G一定 向圖0n(n﹥0)個(gè)頂點(diǎn)的連通無向圖各頂點(diǎn)的度之和最少 GVE)，V{V0V1V2V3}E{(V0V1V0V2V0V3V1V3)}V0 GVE)，VPQ,RST},EPQPR<Q,SRT>}PG n(n﹥0)個(gè)頂點(diǎn)的無向圖中頂點(diǎn)的度的最大值 個(gè)。(n﹥0)個(gè)頂點(diǎn)的連通無向圖的生成樹至少 條邊101個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N有100條邊，其中權(quán)值為1,2,3,4,5,6,7,8,9,10的邊各10條，則網(wǎng)絡(luò)N的 在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時(shí)只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè) 求解帶權(quán)連通圖最小生成樹的Prim算法適合于 圖的情形，而Kruskal算法適合于 求解最短路徑的Dijkstra算法適用于各邊上的權(quán)值 參考答 1.非有無3.n(n-1)/2,4.n-有6.2(n-7.4，V0V1V3V2（V0V2V1V3V0V2V3V18.PQRST9.n-10.11.12.n-13.14.15.16.17.非負(fù) 18.非零（或值為1的對(duì)通圖進(jìn)行一次深度優(yōu)先搜索 nn≥1)n-1nn≥1)個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有n n個(gè)頂點(diǎn)、enn-1sortingAOE網(wǎng)絡(luò)中，可能同時(shí)存在幾條關(guān)鍵路徑，稱所有關(guān)鍵路徑都需通過的有向邊為橋。如果加速這參考答案：1.否是是5.6.是是否10.是否否否是否是否是是是否是是否是否設(shè)連通圖G。試畫出該圖對(duì)應(yīng)的鄰接矩陣表示，并給出對(duì)它執(zhí)行從頂點(diǎn)V0開始的廣度優(yōu)先 設(shè)連通圖G。試畫出該圖及其對(duì)應(yīng)的鄰接表表示，并給出對(duì)它執(zhí)行從V0開始的深度優(yōu)先搜 設(shè)連通圖G試畫出從頂點(diǎn)V0出發(fā)的深度優(yōu)先生成樹圖G中哪幾個(gè)頂點(diǎn)是關(guān)節(jié)（即 設(shè)連通圖G⑩①⑨⑧⑦⑩①⑨⑧ ① 設(shè)有向圖G。試畫出從頂點(diǎn)V0開始進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的DFS生成森林BFS生成森林。 表示圖的另法是使用關(guān)聯(lián)矩陣INC[][]。其中，一行對(duì)應(yīng)于一個(gè)頂點(diǎn)，一列對(duì)應(yīng)于一條邊。因ADJ=INCINCTI，其中，INCTINC的轉(zhuǎn)置矩陣，I是單位矩陣。nnC=AB定義為cijaik公式中的定義為按位加，定義為按位乘03124567設(shè)有通網(wǎng)絡(luò)。試按如下格式，應(yīng)用Kruskal算法給出在構(gòu)造最小生成樹過程中順序選661061872353424 5() ) ) ) ) )設(shè)有通網(wǎng)絡(luò)。試采用prim算法從頂點(diǎn)0開始構(gòu)造最小生成樹（寫出加入生成樹頂點(diǎn)S和選擇邊Edge的順序）009172 364850 ，)0 ，)0 ，)0 ，)0 ，)0Dijkstra算法可簡述如下將連通網(wǎng)所有的邊以方便的次序逐條加入到初TT中的邊構(gòu)G0590600③ ③ 選擇的 去掉的（頂點(diǎn) （,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,）（,,） 有八項(xiàng)活動(dòng),每項(xiàng)活動(dòng)要求的前驅(qū)如下活前A0,A2,A5,AOV網(wǎng)絡(luò),AOE44614655070p1,p2,p6p1p2,p3p6,p4p3p2p6,p4p5,p1<p3,p5<p6。符號(hào)“<”表示“領(lǐng)先于”的關(guān)系。例如，p2<p6表示p2p6才bcbcdefgG11110001110000000100000001000100100100000010G.Edge00執(zhí)行廣度優(yōu)先搜索的結(jié)果為V0V1V3V2V4V7V6V5V8，搜索結(jié)果不唯一G∧8∧∧8∧67∧633∧22∧1∧∧∧126∧76∧745678執(zhí)行深度優(yōu)先搜索的結(jié)果為V0V1V4V3V6V7V8V2V5GV0 G中的關(guān)節(jié)點(diǎn)為V1V2V3V6(1)(2)(1,103,44,55,6)②的另一分支引一條邊，并將與結(jié)點(diǎn)連結(jié)起來，⑨⑧⑩①⑨⑧⑩①②③④⑤④⑤為根的深度優(yōu)先生成樹（不唯一 為根的廣度優(yōu)先生成樹②③①②③ 當(dāng)圖中的頂點(diǎn)個(gè)數(shù)等于邊的條數(shù)時(shí)，ADJINC*INCT-I成立。G對(duì)應(yīng)的鄰接矩陣為001 11ADJ00000

231001000000101001

5600000 0110110 001001001110

011110 10INC0INC010001003001000104000100015000010006000001117

34001001

6780000000 0000 0(始頂點(diǎn)號(hào)，終頂點(diǎn)號(hào)，權(quán)值0(1)(2)12 3(4)((4)(5)450 9)0, 5)0,1, 7)0,1,3, 6)0,1,3,2, 7)0,1,3,2,4,009757 6

001059506601

選擇的 去掉的（頂點(diǎn) （21）（,,）（51）（,,）（61）（,,）（62）（61）（64）（,,）（65）（65）（54）（62）（429）（54）（325）（,,）（436）（429）AOV 一個(gè)拓?fù)渑判蛐蛄袨锳0,A1,A4,A2,A5,A3,A6,A7。注意拓?fù)渑判蚪Y(jié)果不唯一。原新

000 00Edge0000

230110000000000000

5610000 0000001 001010001000AOE44614655頂 邊<1,2><1,3><3,2><2,5><3,5><2,4><4,6>00關(guān)鍵活動(dòng)為<1,3>,<3,2>,<2,5<5,6>，它們組成關(guān)鍵路徑。這些關(guān)鍵活動(dòng)中任一個(gè)提前完成，整個(gè)工程就整個(gè)工程最早在43天完成。由關(guān)鍵活動(dòng)組成的AOV網(wǎng)絡(luò)44614655070Dijkstra算法求從頂點(diǎn)V0Path和最短路徑長度Len步動(dòng)14—∞7—∞選487—∞參照V1調(diào)2487—∞選487參照V3調(diào)3487選487參照V2調(diào)4487選Gp1,p2,p4,p3,p5,p6p1,p4,p2,p3,p5,p6p4,p5,p1,p3,p2,bcbcef0111100100A000111100000110constintMaxVertices=structGraph{ intEdge[MaxVertices][MaxVertices];//有向圖鄰接距陣intCurrentNode; int }intunknown(inti){intd=0;for(intj=0;j<CurrentNode;j++){if(Edge[i][j]!=0)d++;if(Edge[j][i]!=0)}return}GraphGG.unknown3) A constintMaxVertices=structGraph{ intEdge[MaxVertices][MaxVertices];//有向圖鄰接距陣intCurrentNode; int }voidunknown(inti){intd,j;d=for(j=0;j<CurrentNode;j++)if(Edge[i][j]){ Edge[i][j]=0;if(Edge[j][i]){ Edge[j][i]=0;}CurrentEdges-=}GraphGG.unknown(3)后該圖的鄰接矩陣，并說明該算法的structEdge int float Edge*template<classType>structVertex{ Typedata;Edgetemplate<classType>structGraph{ int int int } voidFindDegree()int Edge*p=for(i=0;i<NumVertices;i++)Degree[i]= for(i=0;i<NumVertices;i++)for(p=NodeTable[i].adj;p!=NULL;p=p->link) }structEdge int float Edge*template<classType>structVertex{ Typedata;Edgetemplate<classType>structGraph{ int int int } voidFindDegree(inti)intdeg,j;Edge*p=NULL;deg=0;for(j=0;j<NumVertices;j++)p=while )p=p-if(p==NULL)}if(p!=NULL }return}structEdge int float Edge*template<classType>structVertex{ Typedata;EdgetemplateclassType>structGraph int int int } voidDeletEdge(inti)intde=0,j; Edge*p,*q;if(i>=NumVertices){cout<<"錯(cuò)誤輸入"<< exit(1);for(j=0;j<NumVertices;j++)p=while {q= p=p->link;if(p!=NULL)if(p!=NodeTable[j].adj)q->link=p->link; delete}}NumEdges=NumEdges-}#define constintMaxVertices=template<classType>structAdjMatrixType*NodeTable; floatarr[Maxvertices][MaxVertices]; int int structEdge int float Edge*template<classType>structVertex{ Typedata;Edgetemplate<classType>structAdjTable{ int int } AdjTable<Type>*convertM() EdgeA->NodeTable=newA->NumEdges=for(inti=0;i<NumVertices;i++)A->NodeTable[i].adj= for(intj=0;j<NumVertices;j++)if(arr[i][j]!=INFINITY&&arr[i][j]!=0)e=newEdge;e->dest=j;e- e->link=A- }}return}#define constintMaxVertices=template<classType>structAdjMatrixType* float int int structEdge int float Edge*template<classType>structVertex{ Typedata;Edgetemplate<classType>structAdjTable{ int int } AdjMatrix<Type>*convertAL() inti,j;EdgeA->NodeTable=newA->arr=newfloat[Maxvertices][MaxVertices];A->NumEdges=NumEdges;A->NumVertices=NumVertices;for(i=0;i<NumVertices;i++){for(j=0;j<NumVertices;j++)A->arr[i][j]= }for(i=0;i<NumVertices;i++)p=NodeTable[i].adj;while(p!=NULL)

}}}structEdge int float Edge* Typedata;Edgetemplate<classType>structGraph{ Vertex<Type>*NodeTable; Vertex<Type>*OppositNodeTable; int int } voidconvertM()int Edge*p,for(i=0;i<NumVertices;i++){OppositNodeTable[i].adj=NULL;}for(i=0;i<NumVertices;i++)p=NodeTable[i].adj;while(p!=NULL)q=newEdge;q->dest=i;q->cost=p- }}}(1)執(zhí)行操作后的返回值是5 //2(2)算法的功能是計(jì)算有向圖中一個(gè)頂點(diǎn)的度。 //2分 //2執(zhí)行操作G.unknown(3)后，圖的鄰接矩陣 //30110100000A000010000000000算法的功能是從圖中刪除所有與某個(gè)頂點(diǎn)相關(guān)的邊。//3(1)//2(2)Degree[p-//2(3)//2((23) (1)p!=NULL&&p->dest!=//3(2)//3 (1)p!=NULL&&p->dest!=//3(2)NodeTable[j].adj=p-//3 (1)//2(2)//2//2 (1)//2(2)p-//2(3)p=p-//2 = //3pp //3template<classType>intAdjTable<Type>::GetNeighbor(intvtemplate<classType>AdjTable<Type>::Ad