郑州大学远程教育数据结构考试课件doc.docx

1、郑州大学远程教育数据结构考试课件doc数据结构第 04 章在线测试数据结构第 04 章在线测试 剩余时间： 43:12答题须知： 1、本卷满分 20 分。2 、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3 、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题 1 分，5 道题共 5 分）1 、若串 Sabcdef ，则其非空子串数目为。A、6 B、12C、21 D、222 、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是。A、字符 B、字符串C、数字 D、字母3 、设有三个串， s1How, s2 are, s3 you,

2、则这三个串连接后得到的结果串是。A、Howareyou B、How are youC、How are you. D、 How are you4 、串是一种特殊的线性表，其特殊性体现在。A、可以顺序存储 B、数据元素是一个字符C、可以链接存储 D、数据元素可以是多个字符5 、空格串的长度为。A、0 B、1C、串中空格的个数 D、第二题、多项选择题（每题 2 分，5 道题共 10 分）1 、在定长顺序存储表示中，对串长的表示方法有。A、用域变量表示B、用下标为 0 的数组分量表示C、在串值后加结束标记字符D、无法明确表示2 、以下关于串的存储方式的说法中正确的是。A、定长顺序表示和堆分配表示都是串

3、的顺序存储表示B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间C、堆分配表示的串的存储空间是在程序执行过程中动态分配的D、堆分配存储表示时的空串不占用连续的存储区3 、两个串相等的充分必要条件是。A、串长相等且各对应位置字符相等B、所含字符集合相同C、所含字符个数相同D、串值相等4 、串的机内表示方法有。A、定长顺序存储表示B、堆分配存储表示C、块链存储表示D、散列表示5 、以下关于块链结构的说法正确的是。A、结点大小小，则存储密度小B、结点大小小，则存储密度大C、结点大小小，则占用存储空间多D、结点大小小，则占用存储空间少第三题、判断题（每题1 分， 5 道题共 5 分）

4、1 、如果一个串中的所有字符均在另一串中出现，则前者是后者的子串。正确错误2 、串也有两种存储结构：顺序结构和链式结构。正确错误3 、串是 n 个字母的有限序列（ n 0）。正确 错误4 、串是元素类型受限制的线性表。正确 错误5 、在 C语言中，用动态分配函数进行管理的自由存储区称为“堆”。正确 错误交卷数据结构第 05 章在线测试 剩余时间： 35:15答题须知： 1、本卷满分 20 分。2 、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3 、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题 1 分，5 道题共 5 分）1 、按照

5、二叉树的定义，具有 3 个结点的二叉树有种形态。A、3 B、4C、5 D、62 、树最适合表示。A、有序数据元素 B、无序数据元素C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据3 、的同种顺序的遍历仍需要栈的支持。A、先序线索树 B、中序线索树C、后序线索树 D、4 、已知二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac, 则它的先序遍历序列是。A、acbed B、decabC、deabc D、cedba5 、对于表达式 (a-b+c)*d/(e+f), 其前缀表达式为。错A、/*+-abcd+ef B、a-b+c*d/e+fC、/*-a+bcd+ef D、ab-

6、c+d*ef+/第二题、多项选择题（每题 2 分，5 道题共 10 分）1 、下列关于完全二叉树的叙述中，正确的有。A、完全二叉树一定是满二叉树B、满二叉树一定是完全二叉树C、完全二叉树中要么没有结点的度为 1，要么只可能有一个结点的度为 1D、只有一个结点的度为 1 的二叉树一定是完全二叉树2 、下列关于树和二叉树的叙述中，正确的有。A、森林和二叉树之间可以相互转换B、树和二叉树之间可以相互转换C、二叉树的子树有左右之分，而树的子树没有左右之分D、二叉树结点的最大度数为 2，而树的结点的最大度数没有限制3 、森林的遍历方式有A、先序遍历B、中序遍历C、后序遍历D、层序遍历4 、先序序列和中序

7、序列相同的二叉树有。A、空二叉树B、左单支树C、右单支树D、根树5 、将一个有 50 个结点的完全二叉树按层序编号（根编号为 1），则编号为 25 的结点。A、有左孩子B、有右孩子C、无左孩子D、无右孩子第三题、判断题（每题 1 分，5 道题共 5 分）1 、n 个叶子的 Huffman 树共有 2n-1 个结点。正确 错误2 、二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。正确 错误3 、将一棵树转换成相应的二叉树后，二叉树的根结点肯定没有左子树。正确 错误4 、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。正确 错误5 、给定二叉树的先序和后序遍历序列，可以

8、唯一的确定这棵二叉树。正确 错误数据结构第 06 章在线测试 剩余时间： 47:27答题须知： 1、本卷满分 20 分。2 、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3 、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题 1 分，5 道题共 5 分）1 、一个有 n 个顶点的无向图若是连通图，则至少有条边。A、n-1 B、nC、n+1 D、(n+1)/22 、4 个顶点的无向完全图有条边。 错A、6 B、12C、16 D、203 、一个无向连通图的生成树是含有该连通图所有顶点的。A、极大连通子图 B、极大子图C、极小连通子图 D、

9、极小子图4 、对，用克鲁斯卡尔算法求最小生成树较为合适。A、非连通图 B、连通图C、稀疏图 D、稠密图5 、对，用 Prim 算法求最小生成树较为合适。A、非连通图 B、连通图C、稀疏图 D、稠密图第二题、多项选择题（每题 2 分，5 道题共 10 分）1 、如果对无向图 G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是。A、G肯定不是完全图B、G肯定不是连通图C、G中一定有回路D、G有两个连通分量2 、下列说法中正确的是。A、无向图中的极大连通子图称为连通分量。B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。C、图的深度优先搜索中一般要采用队列来暂存刚访问过的

10、顶点。D、有向图的遍历不能采用广度优先搜索方法。3 、下列说法中不正确的有。A、n 个顶点的无向连通图的边数为 n(n-1)B、图的广度优先遍历过程是一个递归过程C、n 个顶点的有向完全图的弧数为 n(n-1)D、有向图的强连通分量是有向图的极大强连通子图4 、下列关于最短路径的说法中，正确的有。A、Dijkstra 算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到 O(n) 。C、求图中每一对顶点间最短路径的 Floyd 算法的时间复杂度为 O(n3) 。D、求图中每一对顶点间的最短路径也

11、可用 Dijkstra 算法实现。5 、有向图中顶点之间关系的特征是：每个顶点可以有。A、一个前驱B、一个后继C、多个前驱D、多个后继第三题、判断题（每题 1 分，5 道题共 5 分）1 、连通网的最小生成树是唯一的。正确 错误2 、Dijkstra 算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。正确 错误3 、图的深度优先遍历算法类似于二叉树的先序遍历正确 错误4 、对稀疏图，用 Prim 算法求最小生成树较为合适正确 错误5 、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。正确 错误数据结构第 07 章在线测试数据结构第

12、 07 章在线测试 剩余时间： 42:32答题须知： 1、本卷满分 20 分。2 、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3 、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题 1 分，5 道题共 5 分）1 、对线性表进行折半查找时，要求线性表必须。A、以顺序方式存储 B、以链式方式存储C、以顺序方式存储且表中元素按关键字有序排列 D、以链式方式存储且表中元素按关键字有序排列2 、用折半查找对长度为 12 的有序表进行查找，则等概率下查找成功时的平均查找长度为。A、35/12 B、37/12C、39/12 D、43/123 、

13、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的相同。A、关键字 B、元素值C、散列地址 D、含义4 、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用查找方法。A、折半 B、顺序C、分块 D、散列5 、哈希函数有一个性质：函数值应按取其值域的每一个值。A、最小概率 B、最大概率C、平均概率 D、同等概率第二题、多项选择题（每题 2 分，5 道题共 10 分）1 、构造散列函数时通常考虑的因素有。A、计算函数的工作量B、关键字的长度C、散列表长D、关键字的分布情况2 、下列关于 n 个结点的 m阶 B 树的说法中，正确的是。A、树中每个结点最多有 m个关键字B

14、、树中叶子结点的个数为 n+1C、在 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、50B、43C、85D、75E、2

15、0F、35G、45H、30第三题、判断题（每题 1 分，5 道题共 5 分）1 、散列表的装填因子越小，发生冲突的可能性越大。正确 错误2 、折半查找和二叉排序树查找的时间性能相同。正确 错误3 、给出不同的输入序列构造二叉排序树，一定得到不同的二叉排序树。正确 错误4 、9 阶 B 树中，除根以外的任意非终端结点中的关键字个数不少于 4。正确 错误5 、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。正确 错误数据结构第 08 章在线测试 剩余时间： 37:27答题须知： 1、本卷满分 20 分。2 、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3

16、 、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题 1 分，5 道题共 5 分）1 、下列方法中，是稳定的排序方法。A、折半插入排序 B、希尔排序C、快速排序 D、堆排序2 、一组记录的关键字序列为 46 ，79，56，38，40，84 ，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是A、38 ，40，46，56，79，84 B、40 ，38，46，79，56，84C、40 ，38，46，56，79，84 D、40 ，38，46，84，56，793 、在下列排序方法中，平均情况下占用内存量最大的是方法。A、快速排序 B、插入排序C、冒泡排序 D、堆

17、排序4 、在下列排序方法中，在待排序的数据有序时 , 花费时间反而最多的是。A、堆排序 B、起泡排序C、快速排序 D、插入排序5 、对 n 个记录的序列进行堆排序，最坏情况下的时间复杂度为。A、O(logn) B、O(nlogn)C、O(n) D、O(n2)第二题、多项选择题（每题 2 分，5 道题共 10 分）1 、下列排序方法中，是稳定的排序方法。A、简单选择排序B、起泡排序C、快速排序D、直接插入排序E、折半插入排序2 、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是。A、简单选择排序B、起泡排序C、快速排序D、直接插入排序E、堆排序3 、下列排序方法中，空间复杂

18、度为 O(1) 的排序方法有。A、堆排序B、快速排序C、直接插入排序D、冒泡排序4 、下列排序方法中，在最坏情况下算法的时间复杂度为 O(n2) 的有。A、堆排序B、快速排序C、希尔排序D、冒泡排序5 、下列排序方法中，不稳定的排序方法有。A、希尔排序B、快速排序C、堆排序D、直接插入排序第三题、判断题（每题 1 分，5 道题共 5 分）1 、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。正确 错误2 、在一个大顶堆中，最小元素不一定在最后。正确 错误3 、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近 O(n) 。正确 错误4 、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。正确 错误5 、在初始数据表为逆序时，冒泡排序所执行的比较次数最多。正确 错误