数据结构第7章例题与答案

时间：2021-01-13 17:36:39 计算机等级我要投稿

数据结构第7章例题与答案

　第七章图
一、选择题
1．图中有关路径的定义是（）。【北方交通大学 2001 一、24 （2分）】
a．由顶点和相邻顶点序偶构成的边所形成的序列 b．由不同顶点所形成的序列
c．由不同边所形成的序列 d．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（）条边。
a．n-1 b．n(n-1)/2 c． n(n+1)/2 d．0 e．n2
【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】
【北京航空航天大学 1999 一、7 （2分）】
3．一个n个顶点的连通无向图，其边的.个数至少为（）。【浙江大学 1999 四、4 (4分)】
a．n-1 b．n c．n+1 d．nlogn；
4．要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学 2000 一、6(2分）】
a．n-l b．n c．n+l d．2n
5．n个结点的完全有向图含有边的数目（　　　）。【中山大学 1998 二、9 （2分）】
a．n*n ｂ．n（n＋１） c．n／2 d．n*（n－l）
6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。
a．0 b．1 c．n-1 d．n
【北京邮电大学 2000 二、5 （20/8分）】
7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学 2001 二、3 （2分）】
a．1/2 b．2 c．1 d．4
8．用有向无环图描述表达式(a+b)*（（a+b）/a），至少需要顶点的数目为( )。【中山大学1999一、14】
a．5 b．6 c．8 d．9
9．用dfs遍历一个无环有向图，并在dfs算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
a．逆拓扑有序 b．拓扑有序 c．无序的【中科院软件所 1998】
10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。
a．邻接矩阵 b．逆邻接表 c．邻接多重表 d．十字链表 e．邻接表
【北京工业大学 2001 一、3 (2分)】
11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】
a．有向图 b．无向图 c．aov网 d．aoe网
12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】
①．a．9 b．3 c．6 d．1 e．以上答案均不正确
②．a．5 b．4 c．3 d．2 e．以上答案均不正确
③．a．5 b．4 c．3 d．2 e．以上答案均不正确
13．当一个有n个顶点的图用邻接矩阵a表示时，顶点vi的度是（）。【南京理工大学1998一、4(2分）】
14．用相邻矩阵a表示图，判定任意两个顶点vi和vj之间是否有长度为m 的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。【武汉大学 2000 二、7】
a．ma b．a c．am d．am-1
15. 下列说法不正确的是（）。【青岛大学 2002 二、9 （2分）】
a．图的遍历是从给定的源点出发每一个顶点仅被访问一次 c．图的深度遍历不适用于有向图
b．遍历的基本算法有两种：深度遍历和广度遍历 d．图的深度遍历是一个递归过程
16．无向图g=(v,e),其中：v={a,b,c,d,e,f},e={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。【南京理工大学 2001 一、14 （1.5分）】
a．a,b,e,c,d,f b．a,c,f,e,b,d c．a,e,b,c,f,d d．a,e,d,f,c,b
17. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）
【南京理工大学 2000 一、20 （1.5分）】
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
a．5个 b．4个 c．3个 d．2个

http://jianlimoban.c321.cn/

【数据结构第7章例题与答案】相关文章：