郑州大学远程教育数据结构考试

1、数据结构第04章在线测试A、用域变虽表示17 B、用下标为0的数组分量表示17 C、在串值后加结束标记字符厂D、无法明确表示2. 以下关于串的存储方式的说法中正确的是A、定长顺序表示和堆分配表示都是串的顺序存储表示B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间疋C、堆分配表示的串的存储空间是在程序执行过程中动态分配的D、堆分配存储表示时的空串不占用连续的彳储区3. 两个串相等的充分必要条件是17 A.串长相等且各对应位置字符相等B、所含字符集合相同C、所含字符个数相同4. 串的机内表示方法有.17 As定长顺序存储表示 B、堆分配存储表示* C、块链存储表示厂D、散列表示

2、5. 以下关于块链结构的说法正确的是A、结点大小小，则存储密度小B、结点大小小.则存储密度大C、结点大小小则占用存储空间多D、结点大小小.则占用冷储空间少第三题、判断题（每题1分.5道题共5分）1.如果一个串中的所有字符均在另一串中出现，则前者是后者的子串OC正确a错误2、串也有两种存储结构：顺序结构和链式结构。正确C错误3串是n个字母的有限序列（nO） oeC正确a错误4串是元素类型受限制的线性表。正确r错误5s在C语言中用动态分配函数进行管理的自由存储区称为“堆” o正确r错误数据结构第05萃在线测试剩余时间：35:15答题须知：K木卷满分20分。2、答完题后.请一定要单击下而的“交卷”按

3、钮交卷.否则无法记录木试卷的成绩。3. 在交卷之前.不要刷新本网贞，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、按照二叉树的定义.具有3个结点的二叉树有种形态。rrA、3B、 4金C、5D、62.树最适合表示OA.有序数据元素B.无序数据元素“ C、元索之间具有分支层次关系的数据D、元索之间无联系的数据的同种顺序的遍历仍需要栈的支持。A.先序线索树B.中序线索树C、后序线索树D、4、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的先序遍历序列是A、 acbedB、 decabC、 deabcD、 cedba5.对干表达式（ab+c广d/（e

4、+f）,其前缀表达式为.rA. /*+-abcd+efB. ab+Ld/e+f(?C、/*-a+bcd+efrD、ab-c+dMef+/第二题、多项选择题（每题2分，5道题共10分）K下列关于完全二叉树的叙述中，正确的有。厂A.完全二叉树一定是满二叉树厂B.满二叉树一定是完全二叉树厂C、完全二叉树中要么没有结点的度为1,要么只可能有一个结点的度为1厂D、只有一个结点的度为1的二叉树一定是完全二叉树2、下列关于树和二叉树的叙述中，正确的有。A、傑林和二叉树之间可以相互转换B、树和二叉树之间可以相互转换17 C、 叉树的子树有左右之分，而树的子树没有左右之分D、二叉树结点的最大度数为2而树的结点的

5、锻大度数没有限制3.傑林的遍历方式有A、先序遍历B. 中序遍历C、后序遍历D、层序遍历4先序序列和中序序列相同的：叉树有As空二叉树B、左单支树C、右单支树17 D、根树5.将个有50个结点的完全二叉树按层序编号（根编号为1则编号为25的结点.A、有左孩于B. 有右孩子C、无左孩子D、无右孩子第三题.判断题（每题1分.5道题共5分）lx n个叶子的Huffman树共有2nJ个结点。“正确r错误正确2. 二叉树的先.中.后序遍历序列中叶于结点的相对顺序不会发生改变。错误3. 将一棵树转换成相应的二叉树后.二叉树的根结点肯定没有左子树。r 正确e错误4. 二叉树的先序遍历序列中.任总一个结点均处在

6、其孩子结点的前面。正确r错误5. 给定二叉树的先序和后序遍历序列.可以唯一的确定这棵二叉树。c(*正确错误数据结构第06疏在线测试剩余时间:47:27B.连通图D、稠密图A、非连通图C、稀疏图第二题、笫项选择题(每题2分，5道题共10分)K如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点.则下列说法中正确的是.厂A、G肯定不是完全图厂B、G肯定不是连通图厂C、G中一定有回路厂D、G有两个连通分址2.下列说法中正确的是o厂A、无向图中的极大连通子图称为连通分址。B、图的广度优先捜索中一般要采用队列來暂存刚访问过的顶点。 厂C、图的深度优先搜索中一般要采用队列來暂存刚访问过的顶点。 厂

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

8、 有向图中顶点之何关系的特征是：每个顶点可以有。厂A、一个前驱厂B、一个后继17 C、多个前驱D、笫个后继第三题、判断题（每题1分.5道题共5分）1.连通网的最小生成树是唯一的。C正确错误2.Dijkstra算法是按路径长度递増的顺序依次产生从某-固定源点到其他幹顶点之间的灵短路径。C正确错误3图的深度优先遍历算法类似于二叉树的先序遍历“正确C错误4s对稀疏图，用Prim算法求昴小生成树较为合适C正确错误5.若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图。正确锚误数据结构第07章在线测试数据结构第07章在线测试剩余时间：42:32答题须知：K本卷满分20分。

9、2、答完题后，请一定要单击下而的“交卷”按钮交卷.否则无法记录木试卷的成绩。3.在交卷之前.不要刷新木网贞.否则你的答题结果将会被清空。第一题、収项选择题（每题1分，5道题共5分）K对线性表进行折半査找时.要求线性表必须OC A.以顺序方式存储C B.以链式方式存储C、以顺序方式存储且表中元素按关键字有序排列 r D、以链式方式存储且表中元素按关键字有序排列2、用折半查找对长度为12的有序表进行査找，则等概率下査找成功时的平均査找长度为OcB、 37/12A、 35/12C、 39/12D、 43/123.用链地址法处理冲突构造的散列表中，每个地址暇元所链接的同义词表的相同。A. 关键字C B

10、.元素值C、散列地址C D.含义4、如果要求一个线性表既能较快的査找，又能适应动态变化的婆求.可以采用査找方法。r A、折半r B、顺序 c、分块r D、散列5.哈希函数有一个性质：函数值应按取其值域的每一个值。r A.最小概率r B、最大槪率rD.同等槪率1C、平均概率第二题、多项选择题（每题2分，5道题共10分）1、构造散列函数时通常考虑的因素有OA、计算函数的工作量B、关键字的长度C、散列表长D、关键字的分布悄况2、卜列关：n个结点的m阶B树的说法中正确的是.A、树中每个结点最多有m个关键字B、树中叶子结点的个数为n+117C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进

11、行的过程。D、树中所有叶子结点都在同一层，并且不带任何信息E、树中每个结点最多有m-1个关键字厂F、树中每个结点最多有m+1个关键字3.影响散列表的平均査找长度的1大1素有。17A、散列函数厂B、散列表长C、装填因子D、处理冲突的方法4.在顺序表的顺序查找算法中.监视哨的付宜。厂A.只能在表头厂B.只能在表尾17C、可以在表头Dx可以在表尾5.对序列50. 72 43, 85. 75. 20. 35. 45. 30按顺序建二叉排序树.则在树中须比较3次方可査找成功的元素有OrA. 50厂B. 43厂C. 85厂D、75rE. 20rF、35厂G、45Hx 30第三题、判断题（每题1分，5道題共

12、5分）K散列表的装填因子越小.发生冲突的可能性越大。r正确金错误2.折半査找和二叉排序树査找的时间性能相同。正确*错误3. 给出不同的输入序列构造二叉排序树，一定得到不同的二叉排序树。C正确错误4. 9阶B树中.除根以外的任总非终端结点中的关键字个数不少于4。金正确错误5. 在分块查找中对索引表的查找呪可用顺序查找法.也可用折半查找法。正确错误数据结构第08 &在线测试则余时间：37:27答题须知：1.木卷满分20分。2、答完题后.请一定耍单击下面的“交卷”按钮交卷.否则无法记录木试卷的成绩。3、在交卷之前.不要刷新木网页.否则你的答题结果将会被清空。第一题.单项选择题（每题1分，5道題共5分

13、）1、下列方法中.是稳定的排序方法。A、折半插入排序B、希尔排序C、快速排序C D.堆排序2. 一组记录的关键字序列为46, 79, 56, 3& 40. 84,则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是.2 A、 38, 40, 46, 56, 79, 84B. 40, 3& 46, 79, 56, 84C、40, 38. 46, 56. 79. 84D、40. 38. 46, 84. 56. 79,、在下列排序方法中.平均情况下占用内存虽战大的是方法。厂A、快速排序3 B、插入排序厂C、冒泡排序r D、堆排序、在下列排序方法中，在待排序的数据有序时.花费时间反而最多的是。A

14、.堆排序C B.起泡排序C、快速排序D、插入排序5、对n个记录的序列进行堆排序，最坏情况下的时间复朵度为A、O(logn)B、O(nlogn)C、O(n)D、0(22)第二题.多项选择题（每题2分.5道題共10分）1、下列排序方法中.是稳定的排序方法。厂A、简单选择排序PB.起泡排序厂C、快速排序厂D、直接插入排序E.折半插入排序在下列排序方法中.每一趟排序结束后都能选出一个元素放在其最终位宜上的是17A、简单选择排序PB.起泡排序17C、快速排序厂D、直接插入排序17 E、堆排序3、下列排序方法中.空间复朵度为0(1)的排序方法有A、堆排序B. 快速排序C. 直接插入排序D、冒泡排序4、下列排序方法中.在瑕坏情况下算法的时间复朵度为0(22)的有A、堆排序B. 快速排序Cx希尔排序D、冒泡排序5. F列排序方法中，不稳定的排序方法有A