數據結構圖練習題及答案

 

一 選擇題

1．圖中有關路徑的定義是（A ）。

A．由頂點和相鄰頂點對構成的邊所形成的序列      B．由不同頂點所形成的序列    C．由不同邊所形成的序列         D．上述定義都不是

2．設無向圖的頂點個數為n，則該圖最多有（B ）條邊。

A．n-1       B．n(n-1)/2      C． n(n+1)/2       D．0     E．n2   

3．一個n個頂點的連通無向圖，其邊的個數至少為（ A ）。

A．n-1       B．n     C．n+1     D．nlog2n 

4．要連通具有n個頂點的有向圖，至少需要（ B ）條邊。

A．n-l    B．n     C．n+l    D．2n

5．n個結點的完全有向圖含有邊的數目（D　　　）。

A．n*n      Ｂ．n（n＋１）    C．n／2     D．n*（n－l）

6．一個有n個結點的圖，最少有（ B ）個連通分量，最多有（D ）個連通分量。

A．0       B．1    C．n-1     D．n     

7．在一個無向圖中，所有頂點的度數之和等于所有邊數（B ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（C ）倍。

A．1/2     B．2   C．1       D．4

8．用有向無環圖描述表達式(A+B)*（（A+B）/A），至少需要頂點的數目為( A )。

A．5      B． 6     C．8      D．9

9．用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是( A )。

A．逆拓撲有序     B．拓撲有序     C．無序的      

10．下面結構中最適于表示稀疏無向圖的是（C ），適于表示稀疏有向圖的是（ BDE ）。

A．鄰接矩陣     B．逆鄰接表    C．鄰接多重表     D．十字鏈表     E．鄰接表 

11．下列哪一種圖的鄰接矩陣是對稱矩陣？（ B ）

A．有向圖     B．無向圖 　   C．AOV網　      D．AOE網

12. 關鍵路徑是事件結點網絡中（ A ）。

A．從源點到匯點的最長路徑   B．從源點到匯點的最短路徑　 C．最長回路     D．最短回路點

 

二、判斷題

1.樹中的結點和圖中的頂點就是指數據結構中的數據元素。（ √ ）

2．在n個結點的無向圖中，若邊數大于n-1,則該圖必是連通圖。（ × ）

3. 有e條邊的無向圖，在鄰接表中有e個結點。（× ）

4. 有向圖中頂點V的度等于其鄰接矩陣中第V行中的1的個數。（ × ）

5．強連通圖的各頂點間均可達。（ √ ）

6．鄰接多重表是無向圖和有向圖的鏈式存儲結構。（ × ）

7. 十字鏈表是無向圖的一種存儲結構。（ × ）

8. 無向圖的鄰接矩陣可用一維數組存儲。（ √ ）

9．用鄰接矩陣法存儲一個圖所需的存儲單元數目與圖的邊數有關。（ × ）

10．有n個頂點的無向圖, 采用鄰接矩陣表示, 圖中的邊數等于鄰接矩陣中非零元素之和的一半。（ √ ）

11. 有向圖的鄰接矩陣是對稱的。（ × ）

12. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數有關，而與圖的邊數無關。（ √ ）

13. 求最小生成樹的普里姆(Prim)算法中邊上的權可正可負。（× ）

14．拓撲排序算法把一個無向圖中的頂點排成一個有序序列。（ × ）

 

三、填空 

1.判斷一個無向圖是一棵樹的條件是有n個頂點，n-1條邊的無向連通圖 。

2．有向圖G的強連通分量是指有向圖的極大強連通子圖 。

3．一個連通圖的生成樹是一個極小連通子圖。

4．具有10個頂點的無向圖，邊的總數最多為45 。

5．若用n表示圖中頂點數目，則有n(n-1)/2 條邊的無向圖成為完全圖。

6．G是一個非連通無向圖，共有28條邊，則該圖至少有9個頂點。

7. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要 n 條弧。

8．在有n個頂點的有向圖中，每個頂點的度最大可達 2(n-1)。

9．設G為具有N個頂點的無向連通圖，則G中至少有N-1 條邊。

10．n個頂點的連通無向圖，其邊的條數至少為n-1。

11．如果含n個頂點的圖形形成一個環，則它有n 棵生成樹。

 

四、應用題

1．（1）．如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？

答：G1最多n(n-1)/2條邊，最少n-1條邊  

 

（2）．如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？

答： G2最多n(n-1)條邊，最少n條邊  

 

（3）．如果G3是一個具有n個頂點的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？

答：G3最多n(n-1)條邊，最少n-1條邊 (注：弱連通有向圖指把有向圖看作無向圖時，仍是連通的)   

 

2．n個頂點的無向連通圖最少有多少條邊？n個頂點的有向連通圖最少有多少條邊？

答：n-1，n  

 

3．證明：具有n個頂點和多于n-1條邊的無向連通圖G一定不是樹。

答：證明：具有n個頂點n-1條邊的無向連通圖是自由樹，即沒有確定根結點的樹，每個結點均可當根。若邊數多于n-1條，因一條邊要連接兩個結點，則必因加上這一條邊而使兩個結點多了一條通路，即形成回路。形成回路的連通圖不再是樹（在圖論中樹定義為無回路的連通圖）。  

 

4．證明對有向圖的頂點適當的編號，可使其鄰接矩陣為下三角形且主對角線為全0的充要條件是該圖為無環圖。

答：證明：該有向圖頂點編號的規律是讓弧尾頂點的編號大于弧頭頂點的編號。由于不允許從某頂點發出并回到自身頂點的弧，所以鄰接矩陣主對角元素均為0。先證明該命題的充分條件。由于弧尾頂點的編號均大于弧頭頂點的編號，在鄰接矩陣中，非零元素（A[i][j]=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現弧頭頂點編號大于弧尾頂點編號的弧，否則，就必然存在環路。（對該類有向無環圖頂點編號，應按頂點出度順序編號。）  

五、算法設計題

1．設無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該圖的算法。（設頂點值用1～n或0～n-1編號）

答： void CreatGraph (AdjList g)

    //建立有n個頂點和m 條邊的無向圖的鄰接表存儲結構

    {int n,m;

     scanf("%d%d",&n,&m);

        for (i =1,i<=n;i++)//輸入頂點信息,建立頂點向量

        {scanf(&g[i].vertex); g[i].firstarc=null;}

        for (k=1;k<=m;k++)//輸入邊信息

    {scanf(&v1,&v2);//輸入兩個頂點

    i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //頂點定位

    p=(ArcNode *)malloc(sizeof(ArcNode));//申請邊結點

    p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//將邊結點鏈入

        p=(ArcNode *)malloc(sizeof(ArcNode));

    p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p;

    }

    }//算法CreatGraph結束  

 

2．給出以十字鏈表作存儲結構，建立圖的算法，輸入(i,j,v)其中i,j為頂點號，v為權值。

答： void CreatOrthList(OrthList g)

    //建立有向圖的十字鏈表存儲結構

    {int i,j,v; //假定權值為整型

    scanf("%d",&n);

        for(i=1,i<=n;i++) //建立頂點向量

    { scanf(&g[i].vertex); g[i].firstin=null; g[i].firstout=null;}

    scanf("%d%d%d",&i,&j,&v);

    while (i && j && v) //當輸入i,j,v之一為0時,結束算法運行

    {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申請結點

    p->headvex=j; p->tailvex=i; p->weight=v; //弧結點中權值域

    p->headlink=g[j].firstin; g[j].firstin=p;

         p->tailink=g[i].firstout; g[i].firstout=p;

    scanf("%d%d%d",&i,&j,&v);

     } }算法結束

    [算法討論] 本題已假定輸入的i和j是頂點號,否則,頂點的信息要輸入,且用頂點定位函數求出頂點在頂點向量中的下標。圖建立時，若已知邊數（如上面1和2題），可以用for循環；若不知邊數，可用while循環（如本題），規定輸入特殊數（如本題的零值）時結束運行。本題中數值設為整型，否則應以和數值類型相容的方式輸入。  

 

3．設有向G圖有n個點(用1,2,…,n表示),e條邊,寫一算法根據其鄰接表生成其反向鄰接表,要求算法復雜性為O(n+e)。

答：void InvertAdjList(AdjList gin,gout）

    //將有向圖的出度鄰接表改為按入度建立的逆鄰接表

     {for (i=1;i<=n;i++)//設有向圖有n個頂點，建逆鄰接表的頂點向量。

         {gin[i].vertex=gout[i].vertex; gin.firstarc=null; }

     for (i=1;i<=n;i++) //鄰接表轉為逆鄰接表。

     {p=gout[i].firstarc;//取指向鄰接表的指針。

     while (p!=null)

         { j=p->adjvex;

         s=(ArcNode *)malloc(sizeof(ArcNode));//申請結點空間。

         s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s;

         p=p->next;//下一個鄰接點。

         }//while

     }//for }