A、完全图 C、有回路

B、连通图 D、一棵树

5、对＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较为合适。

A、非连通图 C、稀疏图

B、连通图 D、稠密图

第二题、多项选择题（每题2分，5道题共10分）

1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿＿＿＿＿＿。

A、G肯定不是完全图 B、G肯定不是连通图 C、G中一定有回路 D、G有两个连通分量

2、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。

A、入度为0 B、没有前驱 C、出度为0 D、没有后继

3、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿＿＿。

A、一定相同 B、一定不同 C、不一定相同 D、可能相同

4、下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。

A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。

C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。 D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。 5、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。 A、计算邻接矩阵中第i行的元素之和 B、计算邻接矩阵中第i列的元素之和 C、计算邻接矩阵中第i行的非零元个数 D、计算邻接矩阵中第i列的非零元个数 第三题、判断题（每题1分，5道题共5分） 1、若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。 正确 错误 2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。 正确 错误 3、对稀疏图，用Prim算法求最小生成树较为合适 正确 错误 4、利用拓扑排序，可检测一个有向图中是否存在环 正确 错误 5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图。 正确 错误

测试结果如下：

? ? ? ? ? ? ?

1.1 [单选] [对] 一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。

1.2 [单选] [对] 无向图的邻接矩阵是一个＿＿＿＿＿＿＿＿。

1.3 [单选] [对] 图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。 1.4 [单选] [对] 如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿＿＿＿＿＿＿＿。

1.5 [单选] [对] 对＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较为合适。 2.1 [多选] [对] 如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿＿＿＿＿＿。

2.2 [多选] [对] 在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。

? ? ? ? ? ? ? ?

2.3 [多选] [对] 对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿＿＿。

2.4 [多选] [对] 下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。 2.5 [多选] [对] 已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。

3.1 [判断] [对] 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。

3.2 [判断] [对] 在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。

3.3 [判断] [对] 对稀疏图，用Prim算法求最小生成树较为合适 3.4 [判断] [对] 利用拓扑排序，可检测一个有向图中是否存在环

3.5 [判断] [对] 若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图。

《数据结构》第07章在线测试

《数据结构》第07章在线测试 剩余时间：4 9:55 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、＿＿＿＿＿＿＿二叉排序树可得到一个关键字的有序序列。 A、先序遍历 C、后序遍 B、中序遍历 D、层序遍历 2、用折半查找对长度为12的有序表进行查找，则等概率下查找成功时的平均查找长度为＿＿＿＿＿＿＿。 A、35/12 C、39/12 B、37/12 D、43/12 3、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。 A、关键字 C、散列地址 B、元素值 D、含义 4、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。 A、折半 C、分块 B、顺序 D、散列 5、高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。 A、10 C、15

B、12 D、17

第二题、多项选择题（每题2分，5道题共10分）

1、平衡二叉树上结点的平衡因子可以为＿＿＿＿＿＿＿。

A、-2 B、-1 C、0 D、1 E、2

2、构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。

A、计算函数的工作量 B、关键字的长度 C、散列表长 D、关键字的分布情况

3、构造散列表时解决冲突常用的方法有＿＿＿＿＿＿＿。

A、链地址法 B、数字分析法 C、开放定址法 D、平方取中法 E、再哈希法 F、求余法 G、建立公共溢出区

4、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。

A、1

B、2 C、3 D、4 E、6 F、7 G、8 H、9

5、在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。

A、只能在表头 B、只能在表尾 C、可以在表头 D、可以在表尾

第三题、判断题（每题1分，5道题共5分） 1、折半查找和二叉排序树查找的时间性能相同。

正确

错误

2、在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。

正确

错误

3、平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。

正确

错误

4、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。

正确

错误

5、若散列表的装填因子小于1，则可避免冲突的产生

正确

错误

测试结果如下：

?

1.1 [单选] [对] ＿＿＿＿＿＿＿二叉排序树可得到一个关键字的有序序列。