数据结构图练习题及答案
一 选择题
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 }
