数据结构模拟试题四及答案

数据结构模拟试题四 一 共 30 分 每题 2 分 单项选择题 1 循环队列用数组 A 0 m 1 存放其元素值 已知其头尾指针分别为 front 和 rear 则当 前元素个数为 A rear front m mod m B rear front 1 C rear front 1 D rear front E 以上答案都不对 2 数据结构中 与所使用的计算机无关的是数据的 A 存储结构 B 物理结构 C 逻辑结构 D 物理结构和存储结构E 以上答案都不对 3 在具有 n 个结点的单链表中 实现 的操作 其算法的时间复杂度都是 O n A 遍历链表和求链表的第 i 个结点 B 在地址为 p 的结点之后插入一个结点 C 删除开始结点 D 删除地址为 p 的结点的后继结点E 以上答案都不对 4 某二叉树的前序遍历序列为 IJKLMNO 中序遍历序列为 JLKINMO 则后序遍历序列为 A JLKMNOI B LKNJOMI C LKJNOMI D LKNOJMI E 以上答案都不对 5 设 n 阶方阵是一个上三角矩阵 则需存储的元素个数为 A n B n n C n n 2 D n n 1 2 E 以上答案都不对 6 串的 模式匹配 是指 A 判两个串是否相等 B 对两个串进行大小比较 C 找某字符在串中第一次出现 位置 D 找某子串在主串中第一次出现的位置 E 以上答案都不对 7 有 n 个结点的无向图的边数最多为 A n 1 B n n 1 2 C n n 1 D 2n n 1 E 以上答案都不对 8 多关键字文件是指 A 有多个主关键字 B 有多个次关键字 C 有一个主关键字多个次关键字 D 有多个主关键字和多个次关键字 E 以上答案都不对 9 某顺序存储的表格中有 90000 个元素 已按关键字值额定升序排列 假定对每个元素进 行查找的概率是相同的 且每个元素的关键字的值皆不相同 用顺序查找法查找时 平均 比较次数约为 A 25000 B 30000 C 45000 D 90000 E 以上答案都不对 10 对于序列 49 38 65 97 76 13 27 50 按由小到大进行排序 是初始步长 d 4 的希 尔排序法第一趟的结果 A 49 76 65 13 27 50 97 38 B 13 27 38 49 50 65 76 97 C 97 76 65 50 49 38 27 13D 49 13 27 50 76 38 65 97 E 以上答案都不对 11 下列排序算法中 第一趟排序完毕后 其最大或最小元素一定在其最终位置的算法是 A 归并排序 B 直接插入排序 C 快速排序 D 冒泡排序 E 以上答案都不对 12 关于树和二叉树的有序性 正确的结论是 A 树和二叉树都是有序的 B 树和二叉树都可能是有序的 C 树和二叉树都是无序的 D 二叉树是有序的 树可能是有序的 也可能是无序的 E 以上答案都不对 13 在一个图中 所有顶点的度数之和与图的边数的比是 A 1 2 B 1 1 C 2 1 D 4 1 E 以上答案都不对 14 若一组纪录的关键码为 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 E 以上答案都不对 15 从理论上讲 将数据以 结构存放 则查找一个数据所用时间不依赖于数据个数 n A 二叉查找树 B 链表 C 二叉树 D 哈希表 E 以上答案都不对 二 共 40 分 每空 2 分 填空题 1 二分查找算法的时间复杂度为 2 在单链表中 申请到新结点 p 将 p 指向的结点后插到 s 所指结点的操作 其一是 p next s next 其二是 3 对一般树和森林的后序遍历序列的次序与对应的二叉树的 遍历次序相同 4 设二维数组 A 10 20 5 10 按行优先存储 每个元素占 4 个单元 A 10 5 的地址为 160 则 A 15 10 的地址为 5 线性结构反映结点间的逻辑关系是 的 非线性结构反映结点间的逻辑关系是 的 6 赫夫曼树是带权路径长度 的二叉树 7 前序为 abc 且后序为 cba 的二叉树共有 棵 8 已知完全二叉树的高度为 8 第 7 层有 10 个叶子结点 则二叉树的总结点数至少是 9 已知二叉树有 50 个叶子结点 且仅有一个孩子的结点数为 30 则总结点数为 10 具有 m 个叶子结点的赫夫曼树共有 个结点 11 从一棵二叉树的前序序列和 可唯一确定这棵二叉树 设某二叉树的后序遍历为 ABKCBPM 则可知该二叉树的根为 12 设广义表 C x a b x a b y 则 C 的长度为 深度为 13 设有一稠密图 G 则 G 采用 存储较省空间 14 在插入和选择排序中 若初始数据基本正序 则选用 若初始数据基本反序 则选用 15 有 n 结点的二叉链表中 空指针域有 个 利用这些空指针域 存放指向结 点在中序次序下的前趋或后继的指针 这种附加的指针称为 三 10 分 已知一棵度为 m 的树中有 N1 个度为 1 的结点 N2 个度为 2 的结点 Nm 个度为 m 的结点 问该树中有多少个叶子结点 请写出推导过程 四 15 分 给定字母 a b c d e 的使用频率为 0 09 0 17 0 2 0 23 0 31 设计以该权 值为基础的赫夫曼树 并给出赫夫曼编码 五 15 分 设散列表的长度为 13 散列函数为 H K K 13 给定的关键字序列为 19 14 23 01 68 20 84 27 55 11 10 79 试画出用线性探测再散列解决冲突 时所构成的散列表 并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度 六 15 分 已知奇偶交换排序如下所述 第一趟对序列中所有奇数项 i 扫描 将 a i 和 a i 1 进行比较 第二趟对序列中所有偶数项 i 扫描 将 a i 和 a i 1 进行比较 每 次比较时若 a i a i 1 则将两者交换 第三趟对所有奇数项 第四趟对所有偶数 项 如此重复 直至整个序列有序 1 写出奇偶交换排序算法 设待排序的 n 个元素存放在数组 a 1 n 中 2 说明你的排序方法的结束条件 3 若待排序的初始序列已按关键字从小到大有序 则关键字的比较次数是多少 七 10 分 已知长度为 n 的线性表 A 采用顺序存储结构 并且元素按值大小非递减排列 下面的算法删除线性表中多余的值相同的元素 请在算法中空白处填入适当内容 使之能 够正常工作 void DEL int A n 设 A 1 A n 存放着 n 个元素 int i 1 while 1 do if A i A i 1 i else 查找满足条件的元素 for 2 A j 1 A j 删除第 i 1 个元素 满足条件的元素 3 修改线性表的长度 八 15 分 设计算法 已知一棵以二叉链表存储的二叉树 root 指向根结点 p 指向 二叉树中任一结点 编写算法求从根结点到 p 所指结点之间的路径 要求输出该路径上每 个结点的数据 数据结构模拟试题四参考答案 一 共 30 分 每题 2 分 单项选择题 1A 2C 3A 4C 5D 6D 7B 8C 9C 10D 11D 12D 13C 14C 15 D 二 共 40 分 每空 2 分 填空题 1 log2n 2 s next p 3 中序 4 300 5 一对一的 一对多或多对多的 6 最小 7 4 8 235 9 129 10 2m 1 11 中序 M 12 2 4 13 邻接矩阵 14 插入排序 选择排序 15 n 1 线索 三 10 分 解 设 N 为总结点数 N0 为叶子结点数则 N N0 N1 N2 Nm 又有 N 1 度的总数 则 N 1 N1 1 N2 2 Nm m 则有 N0 1 N2 2N3 m 1 Nm 四 15 分 cde ab c 00 d 01 a 100 b 101 e 11 五 15 分 线性探测再散列的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 14168275519208479231110 121431139113 查找成功的平均长度为 ASL 1 12 1 6 2 1 3 3 4 1 9 2 5 查找不成功的平均长度为 ASL 1 13 1 2 3 4 13 7 六 15 分 1 void oesort int a n int i flag do flag 0 for i 1 ia i 1 flag 1 t a i 1 a i 1 a i a i t for i 2 ia