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

数据结构 第 04 章在线测试 数据结构 第 04 章在线测试剩余时间 43 12 答题须知 1 本卷满分 20 分 2 答完题后 请一定要单击下面的 交卷 按钮交卷 否则无法记录本试卷的成绩 3 在交卷之前 不要刷新本网页 否则你的答题结果将会被清空 第一题 单项选择题 每题 1 分 5 道题共 5 分 1 若串 S abcdef 则其非空子串数目为 A 6B 12 C 21D 22 2 字符串是一种特殊的线性表 其特殊性在于它的数据元素只能是 A 字符B 字符串 C 数字D 字母 3 设有三个串 s1 How s2 are s3 you 则这三个串连接后得到的结果串是 A Howareyou B How are you C How are you D How are you 4 串是一种特殊的线性表 其特殊性体现在 A 可以顺序存储B 数据元素是一个字符 C 可以链接存储D 数据元素可以是多个字符 5 空格串的长度为 A 0B 1 C 串中空格的个数D 第二题 多项选择题 每题 2 分 5 道题共 10 分 1 在定长顺序存储表示中 对串长的表示方法有 A 用域变量表示 B 用下标为 0 的数组分量表示 C 在串值后加结束标记字符 D 无法明确表示 2 以下关于串的存储方式的说法中正确的是 A 定长顺序表示和堆分配表示都是串的顺序存储表示 B 定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间 C 堆分配表示的串的存储空间是在程序执行过程中动态分配的 D 堆分配存储表示时的空串不占用连续的存储区 3 两个串相等的充分必要条件是 A 串长相等且各对应位置字符相等 B 所含字符集合相同 C 所含字符个数相同 D 串值相等 4 串的机内表示方法有 A 定长顺序存储表示 B 堆分配存储表示 C 块链存储表示 D 散列表示 5 以下关于块链结构的说法正确的是 A 结点大小小 则存储密度小 B 结点大小小 则存储密度大 C 结点大小小 则占用存储空间多 D 结点大小小 则占用存储空间少 第三题 判断题 每题 1 分 5 道题共 5 分 1 如果一个串中的所有字符均在另一串中出现 则前者是后者的子串 正确错误 2 串也有两种存储结构 顺序结构和链式结构 正确错误 3 串是 n 个字母的有限序列 n 0 正确错误 4 串是元素类型受限制的线性表 正确错误 5 在 C 语言中 用动态分配函数进行管理的自由存储区称为 堆 正确错误 交卷 数据结构 第 05 章在线测试剩余时间 35 15 答题须知 1 本卷满分 20 分 2 答完题后 请一定要单击下面的 交卷 按钮交卷 否则无法记录本试卷的成绩 3 在交卷之前 不要刷新本网页 否则你的答题结果将会被清空 第一题 单项选择题 每题 1 分 5 道题共 5 分 1 按照二叉树的定义 具有 3 个结点的二叉树有 种形态 A 3B 4 C 5D 6 2 树最适合表示 A 有序数据元素B 无序数据元素 C 元素之间具有分支层次关系的数据D 元素之间无联系的数据 3 的同种顺序的遍历仍需要栈的支持 A 先序线索树B 中序线索树 C 后序线索树D 4 已知二叉树的后序遍历序列是 dabec 中序遍历序列是 debac 则它的先序遍历序列是 A acbedB decab C deabcD cedba 5 对于表达式 a b c d e f 其前缀表达式为 错 A abcd efB a b c d e f C a bcd efD ab c d ef 第二题 多项选择题 每题 2 分 5 道题共 10 分 1 下列关于完全二叉树的叙述中 正确的有 A 完全二叉树一定是满二叉树 B 满二叉树一定是完全二叉树 C 完全二叉树中要么没有结点的度为 1 要么只可能有一个结点的度为 1 D 只有一个结点的度为 1 的二叉树一定是完全二叉树 2 下列关于树和二叉树的叙述中 正确的有 A 森林和二叉树之间可以相互转换 B 树和二叉树之间可以相互转换 C 二叉树的子树有左右之分 而树的子树没有左右之分 D 二叉树结点的最大度数为 2 而树的结点的最大度数没有限制 3 森林的遍历方式有 A 先序遍历 B 中序遍历 C 后序遍历 D 层序遍历 4 先序序列和中序序列相同的二叉树有 A 空二叉树 B 左单支树 C 右单支树 D 根树 5 将一个有 50 个结点的完全二叉树按层序编号 根编号为 1 则编号为 25 的结点 A 有左孩子 B 有右孩子 C 无左孩子 D 无右孩子 第三题 判断题 每题 1 分 5 道题共 5 分 1 n 个叶子的 Huffman 树共有 2n 1 个结点 正确错误 2 二叉树的先 中 后序遍历序列中 叶子结点的相对顺序不会发生改变 正确错误 3 将一棵树转换成相应的二叉树后 二叉树的根结点肯定没有左子树 正确错误 4 二叉树的先序遍历序列中 任意一个结点均处在其孩子结点的前面 正确错误 5 给定二叉树的先序和后序遍历序列 可以唯一的确定这棵二叉树 正确错误 数据结构 第 06 章在线测试剩余时间 47 27 答题须知 1 本卷满分 20 分 2 答完题后 请一定要单击下面的 交卷 按钮交卷 否则无法记录本试卷的成绩 3 在交卷之前 不要刷新本网页 否则你的答题结果将会被清空 第一题 单项选择题 每题 1 分 5 道题共 5 分 1 一个有 n 个顶点的无向图若是连通图 则至少有 条边 A n 1B n C n 1D n 1 2 2 4 个顶点的无向完全图有 条边 错 A 6B 12 C 16D 20 3 一个无向连通图的生成树是含有该连通图所有顶点的 A 极大连通子图B 极大子图 C 极小连通子图D 极小子图 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 图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点 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 章在线测试剩余时间 42 32 答题须知 1 本卷满分 20 分 2 答完题后 请一定要单击下面的 交卷 按钮交卷 否则无法记录本试卷的成绩 3 在交卷之前 不要刷新本网页 否则你的答题结果将会被清空 第一题 单项选择题 每题 1 分 5 道题共 5 分 1 对线性表进行折半查找时 要求线性表必须 A 以顺序方式存储B 以链式方式存储 C 以顺序方式存储且表中元素按关键字有序排列D 以链式方式存储且表中元素按关键字有序排列 2 用折半查找对长度为 12 的有序表进行查找 则等概率下查找成功时的平均查找长度为 A 35 12B 37 12 C 39 12D 43 12 3 用链地址法处理冲突构造的散列表中 每个地址单元所链接的同义词表的 相同 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 树中叶子结点的个数为 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 折半插入排序B 希尔排序 C 快速排序D 堆排序 2 一组记录的关键字序列为 46 79 56 38 40 84 则利用快速排序方法 以第一个记录为枢轴得到的一次划分结果是 A 38 40 46 56 79 84 B 40 38 46 79 56 84 C 40 38 46 56 79 84 D 40 38 46 84 56 79 3 在下列排序方法中 平均情况下占用内存量最大的是 方法 A 快速排序B 插入排序 C 冒泡排序D 堆排序 4 在下列排序方法中 在待排序的数据有序时 花费时间反而最多的是 A 堆排序B 起泡排序 C 快速排序D 插入排序 5 对 n 个记录的序列进行堆排序 最坏情况下的时间复杂度为 A O logn B O nlogn C O n D O n 2 第二题 多项选择题 每题 2 分 5 道题共 10 分 1 下列排序方法中 是稳定的排序方法 A 简单选择排序 B 起泡排序 C 快速排序 D 直接插入排序 E 折半插入排序 2 在下列排序方法中 每一趟排序结束后都能选出一个元素放在其最终位置上的是 A 简单选择排序 B 起泡排序 C 快速排序 D 直接插入排序 E 堆排序 3 下列排序方法中 空间复杂度为 O 1 的排序方法有 A 堆排序 B 快速排序 C 直接插入排序 D 冒泡排序 4 下列排序方法中 在最坏情况下算法的时间复杂度为 O n 2 的有 A 堆排序 B 快速排序