数据结构图练习题及答案

 

一 选择题

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 }