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、无向图中的极大连通子图称为连通分量。
B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。 C、图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。 D、有向图的遍历不能采用广度优先搜索方法。
3、下列说法中不正确的有＿＿＿＿＿＿＿＿。
A、n个顶点的无向连通图的边数为n(n-1) B、图的广度优先遍历过程是一个递归过程 C、n个顶点的有向完全图的弧数为n(n-1)
D、有向图的强连通分量是有向图的极大强连通子图
4、下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。
A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。
C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。 D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。
5、有向图中顶点之间关系的特征是：每个顶点可以有＿＿＿＿＿＿＿＿。
A、一个前驱 B、一个后继 C、多个前驱 D、多个后继
第三题、判断题（每题1分，5道题共5分） 1、连通网的最小生成树是唯一的。
正确
错误
2、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。
正确
错误
3、图的深度优先遍历算法类似于二叉树的先序遍历
正确
错误
4、对稀疏图，用Prim算法求最小生成树较为合适
正确
错误
5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。
正确
错误
《数据结构》第07章在线测试
《数据结构》第07章在线测试 剩余时间：4 2:32 答题须知：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、哈希函数有一个性质：函数值应按＿＿＿＿＿＿＿取其值域的每一个值。
A、最小概率 C、平均概率
B、最大概率 D、同等概率
第二题、多项选择题（每题2分，5道题共10分） 1、构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。
A、计算函数的工作量 B、关键字的长度 C、散列表长
D、关键字的分布情况
2、下列关于n个结点的m阶B树的说法中，正确的是＿＿＿＿＿＿＿。
A、树中每个结点最多有m个关键字 B、树中叶子结点的个数为n+1
C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。 D、树中所有叶子结点都在同一层，并且不带任何信息 E、树中每个结点最多有m-1个关键字 F、树中每个结点最多有m+1个关键字
3、影响散列表的平均查找长度的因素有＿＿＿＿＿＿＿。
A、散列函数 B、散列表长 C、装填因子 D、处理冲突的方法
4、在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。
A、只能在表头 B、只能在表尾 C、可以在表头 D、可以在表尾
5、对序列{50，72，43，85，75，20，35，45，30}按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有＿＿＿＿＿＿＿。
A、50 B、43 C、85 D、75 E、20 F、35 G、45 H、30
第三题、判断题（每题1分，5道题共5分）
1、散列表的装填因子越小，发生冲突的可能性越大。
正确
错误
2、折半查找和二叉排序树查找的时间性能相同。
正确
错误
3、给出不同的输入序列构造二叉排序树，一定得到不同的二叉排序树。
正确 错误 4、9阶B树中，除根以外的任意非终端结点中的关键字个数不少于4。 正确 错误 5、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。 正确 错误
《数据结构》第08章在线测试 剩余时间： 37:27 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。 A、折半插入排序 C、快速排序 B、希尔排序 D、堆排序 2、一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿A、{38，40，46，56，79，84} C、{40，38，46，56，79，84} B、{40，38，46，79，56，84} D、{40，38，46，84，56，79} 3、在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。 A、快速排序 C、冒泡排序 B、插入排序 D、堆排序 4、在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿＿＿＿＿＿。 A、堆排序 C、快速排序 B、起泡排序 D、插入排序 5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。 A、O(logn) C、O(n) B、O(nlogn) D、O(n^2) 第二题、多项选择题（每题2分，5道题共10分） 1、下列排序方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。