數據結構-第七章圖：習題(共13頁)

1、精選優(yōu)質文檔-傾情為你奉上第七章圖：習題習    題一、選擇題    1設完全無向圖的頂點個數為n，則該圖有(  )條邊。    A. n-l    B. n(n-l)/2      C.n(n+l)/2    D. n(n-l)    2在一個無向圖中，所有頂點的度數之和等于所有邊數的(  )倍。    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.強連通圖    B.連通圖    C.非連通圖    D.非強連通圖    5若采用鄰接矩陣存儲具有n個頂點的一個無向圖，則該鄰接矩陣是一個(  )。    A.上三角矩陣    B.稀疏矩陣    C.對角矩陣    D.對稱矩陣    6若采用鄰接矩陣存儲具有n個頂點的一個有向圖，頂

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

5、160;   8對于含有n個頂點和e條邊的無向連通圖，利用普里姆Prim算法產生最小生成時間復雜性為(  )，利用克魯斯卡爾Kruskal算法產生最小生成樹（假設邊已經按權的次序排序），其時間復雜性為(  )。    A. O(n2)    B. O(n*e)    C. O(n*logn)    D.O(e)    9對于一個具有n個頂點和e條邊的有向圖，拓撲排序總的時間花費為O(  )

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

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

8、法。    6對用鄰接表表示的圖進行深度優(yōu)先遍歷時，其時間復雜度為一；對用鄰接表表示的圖進行廣度優(yōu)先遍歷時，其時間復雜度為_。    7對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數為_ ，邊數為_。    8在執(zhí)行拓撲排序的過程中，當某個頂點的入度為零時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減1。為了避免重復檢測頂點的入度是否為零，需要設立一個_來存放入度為零的頂點。三、簡答題    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為一帶權無向圖，請按要求回答問題。(1)    畫出該圖的鄰接矩陣，并按普里姆算法求其最小生成樹。(2)畫出該圖的鄰接表，并按克魯斯卡爾算法求其最

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

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

13、結構，編寫實現連通圖G的深度優(yōu)先搜索遍歷（從頂點v出發(fā)）的非遞歸函數。    3給定n個村莊之間的交通圖。若村莊i與村莊j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權值Wij表示這條道路的長度?，F打算在這n個村莊中選定一個村莊建一所醫(yī)院。試編寫一個算法，求出該醫(yī)院應建在哪個村莊，才能使距離醫(yī)院最遠的村莊到醫(yī)院的路程最短。4編寫一個函數，計算給定的有向圖的鄰接矩陣的每對頂點之間的最短路徑。第七章 圖第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權值遞增，頂點連通。    6O(e)，O(e)。7n，n-l。                 8棧。三、簡答題1回答以下問題：    (1)有n個頂點的無向連通圖最多需要多少條邊？最少需要多少條邊？    (2)表示一個具有1000個頂點、1000條邊的無向圖的鄰接矩陣有多少個矩陣元素？有多少非零元素？是否為稀疏矩陣

16、？    【解答】(l)有n個頂點的無向連通圖最多有n(n-l)/2條邊（構成一個無向完全圖的情況）;最少有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為一帶權無向圖，請按要求回答問題：(1)畫出該圖的鄰接矩陣，并按普里姆算法求其最小生成樹。(2)畫出該圖的鄰接表，并按克魯斯卡爾算法求其最小生成樹?！窘獯稹?1)按普里姆算法其最小生成樹如下所示。    (2)按克魯斯卡爾算法其最小生成樹如下所示。5題圖7-4是一帶權有向圖，試采用狄杰斯特拉Dijkstra算法求從

21、頂點l到其他各頂點的最短路徑，要求 給出整個計算過程。    【解答】(1)初值：s=1），dist=0，20，15，（頂點1到其他各項點的權值），path=1，1，1，    -l，-1，-1）(頂點l到其他各項點有弧存在時為1，否則為-1)。    (2)在V-S中找最近（dist最?。┑捻旤c3，加入S中，即s=l，3），并重新計算頂點l到達頂點2，4，5和6的距離，修改相應的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到達頂點4，5和6的距離，修改相應的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到達頂點4和5的距離，修改相應的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到達頂點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中包含了圖的所有頂點，算法結束。最終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為一個帶權有向圖，    (1)給出該圖的鄰接矩陣。    (2)請用弗洛伊德算法求出各頂點對之間的最短路徑長度，要求寫出其相應的矩陣序列。    【解答】(1)鄰接矩陣如下：0   10      15   0    6   3 

27、60;   0   4   8    2   0  (2)采用弗洛伊德算法求最短路徑的過程如下：7對于有向無環(huán)圖，   (1)敘述求拓撲有序序列的步驟。   (2)對于題圖7-6所示的有向圖，寫出它的4個不同的拓撲有序序列。    【解答】(1)參見7.6節(jié)的介紹。    (2)它的4個不同的拓撲有序序列是：，。    8題圖7-7是一個AOE網，

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

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

30、160;   #define Max<一個大于頂點數的常量>    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以鄰接表作為圖的存儲結構，編寫實現連通圖G的深度優(yōu)先搜索遍歷（從頂點v出發(fā)）的非遞歸函數。    【算法基本思想】第一步，首先訪問圖G的指定起始頂點v;第二步，從v出發(fā)，訪問一個與V鄰接且未被訪問的頂點p，

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

35、頂點數        Struct  ArcNode   *stackMAXVEX,*p;    int  visited MAXVEX, top=0,i;    for (i-0，i<n，i+)   visitedti =0;    /結點訪問標志均置為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+;    /將訪問過的結點入棧    stacktop =p;    p=g p->adj veX.firstarc;        if (top>0)       p=stack top;    top-;

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

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

40、160; /最短路徑長度min置初值10000    for(k=O;k<n;k+)    /應用弗洛伊德算法計算每對村莊之間的最短路徑    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編寫一個函數計算給定的有向圖的鄰接矩陣的每對頂點之間的最短路徑。本題實質上就是狄杰斯特拉算法。    【算法思想】假設原點為v：    (l)置集合s的初態(tài)為空。    (2)把頂點v放入集合s中。    (3)確定從v開始的n-l條路徑。    (4)選擇最短距離的頂點u。    (5)把頂點u加入集合s中。    (6)更改距離。    【解答】具體實現如下：    #define MAXVEX 100    /定義頂點數的最大值&