數(shù)據(jù)結(jié)構(gòu)-第七章圖：習(xí)題(共13頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第七章圖：習(xí)題習(xí)    題一、選擇題    1設(shè)完全無向圖的頂點個數(shù)為n，則該圖有(  )條邊。    A. n-l    B. n(n-l)/2      C.n(n+l)/2    D. n(n-l)    2在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的(  )倍。    A.3

2、60;   B.2    C.1    D.1/2    3有向圖的一個頂點的度為該頂點的(  )。    A.入度    B. 出度    C.入度與出度之和    D.(入度+出度)/2    4在無向圖G (V，E)中，如果圖中任意兩個頂點vi、vj (vi、vjV，vivj)都的，則稱該圖是(  )。 

3、;   A.強(qiáng)連通圖    B.連通圖    C.非連通圖    D.非強(qiáng)連通圖    5若采用鄰接矩陣存儲具有n個頂點的一個無向圖，則該鄰接矩陣是一個(  )。    A.上三角矩陣    B.稀疏矩陣    C.對角矩陣    D.對稱矩陣    6若采用鄰接矩陣存儲具有n個頂點的一個有向圖，頂

4、點vi的出度等于鄰接矩陣    A.第i列元素之和    B.第i行元素之和減去第i列元素之和    C.第i行元素之和    D.第i行元素之和加上第i列元素之和     7對于具有e條邊的無向圖，它的鄰接表中有(  )個邊結(jié)點。    A.e-l    B.e    C.2(e-l)    D. 2e&#

5、160;   8對于含有n個頂點和e條邊的無向連通圖，利用普里姆Prim算法產(chǎn)生最小生成時間復(fù)雜性為(  )，利用克魯斯卡爾Kruskal算法產(chǎn)生最小生成樹（假設(shè)邊已經(jīng)按權(quán)的次序排序），其時間復(fù)雜性為(  )。    A. O(n2)    B. O(n*e)    C. O(n*logn)    D.O(e)    9對于一個具有n個頂點和e條邊的有向圖，拓?fù)渑判蚩偟臅r間花費(fèi)為O(  )

6、0;   A.n    B.n+l    C.n-l    D.n+e    10在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的(  )生成樹中。    A.最小    B.任何     C.廣度優(yōu)先    D.深度優(yōu)先二、填空題    1在一個具有n個頂點的無向完全圖中，包含有_條邊；

7、在一個具有n個有向完全圖中，包含有_條邊。    2對于無向圖，頂點vi的度等于其鄰接矩陣_ 的元素之和。    3對于一個具有n個頂點和e條邊的無向圖，在其鄰接表中，含有_個邊對于一個具有n個頂點和e條邊的有向圖，在其鄰接表中，含有_個弧結(jié)點。    4十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，實際上是將_和_結(jié)合起來的一種鏈表。    5在構(gòu)造最小生成樹時，克魯斯卡爾算法是一種按_的次序選擇合適的邊來構(gòu)造最小生成樹的方法；普里姆算法是按逐個將_的方式來構(gòu)造最小生成樹的另一種方

8、法。    6對用鄰接表表示的圖進(jìn)行深度優(yōu)先遍歷時，其時間復(fù)雜度為一；對用鄰接表表示的圖進(jìn)行廣度優(yōu)先遍歷時，其時間復(fù)雜度為_。    7對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)為_ ，邊數(shù)為_。    8在執(zhí)行拓?fù)渑判虻倪^程中，當(dāng)某個頂點的入度為零時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減1。為了避免重復(fù)檢測頂點的入度是否為零，需要設(shè)立一個_來存放入度為零的頂點。三、簡答題    l回答以下問題：    (1)有n個頂

9、點的無向連通圖最多需要多少條邊？最少需要多少條邊？    (2)表示一個具有1000個頂點、1000條邊的無向圖的鄰接矩陣有多少個矩陣元素？有多少非零元素？是否為稀疏矩陣？    2題圖7-1為一有向圖，按要求回答問題：    (1)寫出各頂點的入度、出度和度。    (2)給出該圖的鄰接矩陣。    (3)給出該圖的鄰接表。    (4)給出該圖的十字鏈表。3題圖7-2為一無向圖，請按要求回答問題： &#

10、160;  (1)畫出該圖的鄰接表。    (2)畫出該圖的鄰接多重表。    (3)分別寫出從頂點1出發(fā)按深度優(yōu)先搜索遍歷算法得到的頂點序列和按廣度優(yōu)先搜索  遍歷算法得到的頂點序列。             4題圖7-3為一帶權(quán)無向圖，請按要求回答問題。(1)    畫出該圖的鄰接矩陣，并按普里姆算法求其最小生成樹。(2)畫出該圖的鄰接表，并按克魯斯卡爾算法求其最

11、小生成樹。  5題圖7-4是一帶權(quán)有向圖，試采用狄杰斯特拉Dijkstra算法求從頂點1到其他各項點的最短路徑，要求給出整個計算過程。   6題圖7-5為一個帶權(quán)有向圖    (1)給出該圖的鄰接矩陣。    (2)請用弗洛伊德算法求出各頂點對之間的最短路徑長度，要求寫出其相應(yīng)的矩陣序列。    7對于有向無環(huán)圖，    (1)敘述求拓?fù)溆行蛐蛄械牟襟E。    (2)對于題圖7-6所示的有向圖，寫出它的4個不同的拓?fù)?/p>

12、有序序列。    8題圖7-7是一個AOE網(wǎng)，試求：    (1)每項活動的最早開始時間和最遲開始時間。    (2)完成整個工程至少需要多少天。    (3)哪些是關(guān)鍵活動。    (4)是否存在某些活動，當(dāng)提高其速度后能使整個工期縮短。   四、算法設(shè)計題    1編寫一個算法，判斷圖G中是否存在從頂點vi到vj的長度為k的簡單路徑。    2以鄰接表作為圖的存儲

13、結(jié)構(gòu)，編寫實現(xiàn)連通圖G的深度優(yōu)先搜索遍歷（從頂點v出發(fā)）的非遞歸函數(shù)。    3給定n個村莊之間的交通圖。若村莊i與村莊j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值Wij表示這條道路的長度?，F(xiàn)打算在這n個村莊中選定一個村莊建一所醫(yī)院。試編寫一個算法，求出該醫(yī)院應(yīng)建在哪個村莊，才能使距離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短。4編寫一個函數(shù)，計算給定的有向圖的鄰接矩陣的每對頂點之間的最短路徑。第七章 圖第7章圖一、選擇題（參考答案）：1B    2B    3C    &

14、#160; 4B    5D6. C    7D    8A,D    9D    10.A二、填空題（參考答案）1n(n-l)/2, n(n-l)。      2第i行。3. 2e, e0                 

15、60;4鄰接表，逆鄰接表。5權(quán)值遞增，頂點連通。    6O(e)，O(e)。7n，n-l。                 8棧。三、簡答題1回答以下問題：    (1)有n個頂點的無向連通圖最多需要多少條邊？最少需要多少條邊？    (2)表示一個具有1000個頂點、1000條邊的無向圖的鄰接矩陣有多少個矩陣元素？有多少非零元素？是否為稀疏矩陣

16、？    【解答】(l)有n個頂點的無向連通圖最多有n(n-l)/2條邊（構(gòu)成一個無向完全圖的情況）;最少有n-l條邊（n個頂點是連通的）。    (2)這樣的矩陣共有l(wèi)OOO*1000=個矩陣元素，因為有1000條邊，所以有2000非零元素，因此該矩陣是稀疏矩陣。    2題圖7-1為一有向圖，按要求回答問題：題圖7-1    (1)寫出各頂點的入度、出度和度。    (2)給出該圖的鄰接矩陣。    (3)給出該

17、圖的鄰接表。    (4)給出該圖的十字鏈表?！窘獯稹?l)各頂點入度、出度和度如下表所示。    (2)鄰接矩陣如下所示。0    0    0    0    0    01    0    0    1    0    00 

18、;   1    0    0    0    10    0    1    0    1    11    0    0    0    0    01&#

19、160;   1    0    0    1    0    (3)鄰接表如下所示。    (4)十字接表如下所示。    3題圖7-2為一無向圖，請按要求回答問題：    (1)畫出該圖的鄰接表。    (2)畫出該圖的鄰接多重表。    (3)分別寫出從頂點l出發(fā)按深度優(yōu)先

20、搜索遍歷算法得到的頂點序列和按廣度優(yōu)先搜索遍歷算法得到的頂點序列。題圖7-2    【解答】(1)鄰接表如下所示。(2)多重鄰接表如下所示。(3)從頂點1出發(fā)，深度優(yōu)先搜索遍歷序列為：;廣度優(yōu)先搜索遍歷序列為：。4題圖7-3為一帶權(quán)無向圖，請按要求回答問題：(1)畫出該圖的鄰接矩陣，并按普里姆算法求其最小生成樹。(2)畫出該圖的鄰接表，并按克魯斯卡爾算法求其最小生成樹?！窘獯稹?1)按普里姆算法其最小生成樹如下所示。    (2)按克魯斯卡爾算法其最小生成樹如下所示。5題圖7-4是一帶權(quán)有向圖，試采用狄杰斯特拉Dijkstra算法求從

21、頂點l到其他各頂點的最短路徑，要求 給出整個計算過程。    【解答】(1)初值：s=1），dist=0，20，15，（頂點1到其他各項點的權(quán)值），path=1，1，1，    -l，-1，-1）(頂點l到其他各項點有弧存在時為1，否則為-1)。    (2)在V-S中找最近（dist最?。┑捻旤c3，加入S中，即s=l，3），并重新計算頂點l到達(dá)頂點2，4，5和6的距離，修改相應(yīng)的dist值：    dist2=mindist2,  dist3+cost32=min

22、20,  15+4=19;    dist6l=mindist6, dist3+cost36=Inin，15+10=25;    則有dist=0，19，15，25，path=l，3，1，-l，-l，3。    (3)在V-S中找出最近的頂點4，加入S中，即s=1，3，2，并重新計算頂點1到達(dá)頂點4，5和6的距離，修改相應(yīng)的dist值：    dist5-mindist5,   dist2+ cost25)-min，19+10=29, 

23、   則有dist=0,19,15, ，29,25），path=l,3,l，-1,2,3.    (4)在V-S中找出最近的頂點6，加入S中，即s1，3，2，6），并重新計算頂點l到達(dá)頂點4和5的距離，修改相應(yīng)的dist值：    dist4=mindist4, dist6+cost64)=min.,25+4=29,    則有dist=0, 19, 15, 29, 29, 25, path=l,3,1,6,2,3。    (5)在V-S中找出最近的頂點4

24、，加入S中，即s：l，3，2，6，4，并重新計算頂點l到達(dá)頂點5的距離，此時不需要修改dist值，則有dist=0，19，15，29，29，25），path=l，3，  l，6，2，  3。    (6)在V-S中找出最近的頂點5，加入S中，即s口=l，3，2，6，4，5。此時S中包含了圖的所有頂點，算法結(jié)束。最終dist=0，19，15，29，29，25），path=1，3，l，6，2，  3。    由此得到：    從頂點1到頂點2的最短路徑長度為：19 &#

25、160;  最短路徑為：2<-3<-1    從頂點l到頂點3的最短路徑長度為：15    最短路徑為：3<-1    從頂點l到頂點4的最短路徑長度為：29    最短路徑為：4<-6<-3<-1    從頂點l到頂點5的最短路徑長度為：29    最短路徑為：5<-2<-3<-l    從頂點l到頂點6的最短路徑長度為：

26、25    最短路徑為：6<-3<-1    6題圖7-5為一個帶權(quán)有向圖，    (1)給出該圖的鄰接矩陣。    (2)請用弗洛伊德算法求出各頂點對之間的最短路徑長度，要求寫出其相應(yīng)的矩陣序列。    【解答】(1)鄰接矩陣如下：0   10      15   0    6   3 

27、60;   0   4   8    2   0  (2)采用弗洛伊德算法求最短路徑的過程如下：7對于有向無環(huán)圖，   (1)敘述求拓?fù)溆行蛐蛄械牟襟E。   (2)對于題圖7-6所示的有向圖，寫出它的4個不同的拓?fù)溆行蛐蛄小?#160;   【解答】(1)參見7.6節(jié)的介紹。    (2)它的4個不同的拓?fù)溆行蛐蛄惺牵海?#160;   8題圖7-7是一個AOE網(wǎng)，

28、試求：    (l)每項活動的最早開始時間和最遲開始時間。    (2)完成整個工程至少需要多少天（設(shè)弧上權(quán)值為天數(shù)）。    (3)哪些是關(guān)鍵活動。    (4)是否存在某些活動，當(dāng)提高其速度后能使整個工期縮短。    【解答】(1)所有活動的最早開始時間e(i)、最遲開始時間l(i)以及d(i)=1(i)一e(i)，如下所示。    (2)完成此工程最少需要23天。    (3)從以

29、上計算得出關(guān)鍵活動為：a2，a4，a6，a8，a9，aio，a12，a13和a14。    (4)存在a2，a4，al4活動，當(dāng)其提高速度后能使整個工程縮短工期。    四、算法設(shè)計題    1編寫一個算法，判斷圖G中是否存在從頂點vi到vj的長度為k的簡單路徑。    【解答】采用深度優(yōu)先遍歷算法來判斷圖G中是否存在從頂點vi到vj的長度為k的簡單路徑。其中，變量n用于記錄經(jīng)過的頂點數(shù)，當(dāng)n=k+l時，表示路徑長度為k;suc記錄是否成功地找到了所求路徑。算法如下所示。&#

30、160;   #define Max<一個大于頂點數(shù)的常量>    int  visited Max，    /全局變量    int exist (ALGraph *g,int  vi; int  Vj, intk)        int i，suc;    for（i=O;i<g->n;i十+）    /置初值

31、    visited i =0;    suc=0; n=0;    dfs (g, vi, Vj, suc,k);    return suc;        void dfs (ALGraph *g,int V,int  Vj, int  &suc, int k)        ArcNode *p;  

32、  Visited v =l;    n+;    if (n=k+lv=vj)suc=l;  /找到了滿足題意的路徑    if(n<k+1)    p=g->adj listv ->firstarc;    while(p!=NULL&& suc=0)    if (visitedp->adj vex =0)    dfs

33、(g, p->adjvex, Vj, suc,k)j    n-;        p=p->nextarc;                2以鄰接表作為圖的存儲結(jié)構(gòu)，編寫實現(xiàn)連通圖G的深度優(yōu)先搜索遍歷（從頂點v出發(fā)）的非遞歸函數(shù)。    【算法基本思想】第一步，首先訪問圖G的指定起始頂點v;第二步，從v出發(fā)，訪問一個與V鄰接且未被訪問的頂點p，

34、再從頂點p出發(fā)，訪問與p鄰接且未被訪問的頂點q，如此重復(fù)，直到找不到未訪問過的鄰接頂點為止;第三步，退回到尚有未被訪問過的鄰接點的頂點，從該頂點出發(fā)，重復(fù)第二、三步，直到所有被訪問過的頂點的鄰接點都已被訪問為止。為此，用一個棧保存被訪問過的結(jié)點，以便回溯查找已被訪問結(jié)點的未被訪問過的鄰接點。具體函數(shù)如下：    #define MAXVEX 100    /定義頂點數(shù)的最大值    Void dfs  (Adj List g，int v，int n)    /n表示

35、頂點數(shù)        Struct  ArcNode   *stackMAXVEX,*p;    int  visited MAXVEX, top=0,i;    for (i-0，i<n，i+)   visitedti =0;    /結(jié)點訪問標(biāo)志均置為O    printf(¨%dn¨，v);   

36、 p=gvfirstarc;    while  (top>0|p)        while (p)    if (visitedp->adj vex =0)    p=p->nextarc    /查找下一鄰接點    else       printf(¨%dn¨, p->adj

37、vex);    visited p->adjvex =l;    top+;    /將訪問過的結(jié)點入棧    stacktop =p;    p=g p->adj veX.firstarc;        if (top>0)       p=stack top;    top-;

38、60;   /退錢，回溯查找已被訪問結(jié)點的未被訪問過的鄰接點    p=p->nextarc;                3給定n個村莊之間的交通圖。若村莊i與村莊j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值Wij表示這條道路的長度?，F(xiàn)打算在這n個村莊中選擇一個村莊建一所醫(yī)院。試編寫一個算法，求出該醫(yī)院應(yīng)建在哪個村莊，才能使距離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短。    將n個

39、村莊的交通圖用鄰接矩陣A表示。    【算法思路】先應(yīng)用弗洛伊德算法計算每對頂點之間的最短路徑;然后找出從每一個頂點到其他各頂點的最短路徑中最長的路徑;最后在這n條最長路徑中找出最短的一條。算法如下：    #define n<村莊個數(shù)>    int maxminpath (float An n)        int i,j,k;    float s.min=10000;  &#

40、160; /最短路徑長度min置初值10000    for(k=O;k<n;k+)    /應(yīng)用弗洛伊德算法計算每對村莊之間的最短路徑    for(i=O;i<n;i+)    for(j=0;j<n;j+)    if (Aik+Akj<Aij)    Aij=Aik+Akj;    k=-l;    f。r(i=O; i<

41、;n;i+)    /對每個村莊循環(huán)一次    s=0;    f。r(j=0;j<n;j+)    /求l村莊到其他村莊最長的一條最短路徑    if(Aij>s)    s=Aij;    if (s<min)    /在各最長路徑中選最短的一條，將該村莊放在k中    k=i;  &#

42、160; min=s;            return k：        4編寫一個函數(shù)計算給定的有向圖的鄰接矩陣的每對頂點之間的最短路徑。本題實質(zhì)上就是狄杰斯特拉算法。    【算法思想】假設(shè)原點為v：    (l)置集合s的初態(tài)為空。    (2)把頂點v放入集合s中。    (3)確定從v開始的n-l條路徑。    (4)選擇最短距離的頂點u。    (5)把頂點u加入集合s中。    (6)更改距離。    【解答】具體實現(xiàn)如下：    #define MAXVEX 100    /定義頂點數(shù)的最大值&