王贰家

第一题、单项选择题（每题1分，5道题共5分）
1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿A＿＿＿＿＿条边。
A、n-1 B、n
C、n+1 D、(n+1)/2
2、无向图的邻接矩阵是一个＿＿＿＿A＿＿＿＿。
A、对称矩阵 B、零矩阵
C、对角矩阵 D、上三角矩阵
3、图的深度优先遍历算法类似于二叉树的＿＿＿＿A＿＿＿＿。
A、先序遍历 B、中序遍历
C、后序遍历 D、层序遍历
4、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿B＿＿＿＿＿＿＿。
A、完全图 B、连通图
C、有回路 D、一棵树
5、对＿＿＿＿＿D＿＿＿，用Prim算法求最小生成树较为合适。
A、非连通图 B、连通图
C、稀疏图 D、稠密图
第二题、多项选择题（每题2分，5道题共10分）
1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿＿＿ABD＿＿＿。
A、G肯定不是完全图
B、G肯定不是连通图
C、G中一定有回路
D、G有两个连通分量
2、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿AB＿＿＿＿＿的顶点。
A、入度为0
B、没有前驱
C、出度为0
D、没有后继
3、下列说法中正确的是＿＿＿＿AB＿＿＿＿。
A、无向图中的极大连通子图称为连通分量。
B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
C、图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。
D、有向图的遍历不能采用广度优先搜索方法。
4、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿ABCD＿＿＿。
A、计算邻接矩阵中第i行的元素之和
B、计算邻接矩阵中第i列的元素之和
C、计算邻接矩阵中第i行的非零元个数
D、计算邻接矩阵中第i列的非零元个数
5、下列说法中不正确的有＿＿＿AB＿＿＿＿＿。
A、n个顶点的无向连通图的边数为n(n-1)
B、图的广度优先遍历过程是一个递归过程
C、n个顶点的有向完全图的弧数为n(n-1)
D、有向图的强连通分量是有向图的极大强连通子图
第三题、判断题（每题1分，5道题共5分）
1、任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。F
正确 错误
2、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。T
正确 错误
3、图的深度优先遍历算法类似于二叉树的先序遍历 T
正确 错误
4、对稀疏图，用Prim算法求最小生成树较为合适 F
正确 错误
5、利用拓扑排序，可检测一个有向图中是否存在环 T
正确 错误