2020年暨南大学计算机基础综合考研真题848.doc0页

2020年暨南大学计算机基础综合考研真题848.doc 2020 年 招收 攻读 硕士学 位研 究生入 学考 试试题 （B ） ******************************************************************************************** 招生专业与代码： 计算机系统结构 081201 、 计算机软件与理论 081202 、计算机应用技术 081203 、电 子信 息( 专 业学 位) 085400 考试科 目名 称及 代码 ： 计 算机基 础综 合 848 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 第一部分 数据结构（75 分） 一、 单项选 择题( 每题 2 分 ，共 20 分) 1. 含有m 个结 点的 二叉 树 链式存 储结 构中 空指 针的 个数 为 ( ) 。 A．2m B．m-1 C ．m+1 D ．m 2. 下 列排 序算 法中 元素 的 移动次 数和 关键 字的 初始 排列次 序无 关的 是 （ ） 。 A. 快 速排 序 B. 插入 排序 C. 选择 排序 D. 希 尔排序 3. 一 个栈 的进 栈序 列是a b c d e ， 则栈 的输 出序 列不可 能的 是 （ ）。 A ．a b c d e B．e d c b a C．d e c b a D ．d c e a b 4. 需 要的 辅助 空间 最多 的 排序算 法为 （ ）。 A. 归 并排 序 B. 快速 排 序 C. 基 数排 序 D. 堆排 序 5. 哈 希表 的平 均查 找长 度 说法错 误的 是 ( ) 。 A. 与 处理 冲突 方法 有 关而与 表的 长度 无关 B. 与 选用 的哈 希函 数 有关 C. 与 哈希 表的 饱和 程 度有关 D. 与 表中 填入 的记 录 数有关 6. 有n 个 顶点 、e 条 边且 使用了 邻接 表存 储的 有向 图进行 深度 优先 遍历 ， 其 算法的 时间 复杂 度是 （ ）。 A. O （n+e ） B. O （n 2 ） C. O （n+2e ） D. O （n*e ） 7. 已 知一 个长 度为 11 的 顺序表 ，其 元素 按关 键字 有序排 列， 若采 用折 半查 找查找 一个 其中 不存 存在的 元素 ，则 关键 字的 比较次 数最 多是 （ ）。 A ．3 B ．4 C ．5 D ．6 8. 一 棵完 全二 叉树 上有3001 个 结点 ，其 中叶 子结 点的个 数是 （ ）。 A. 1500 B.1501 C. 1000 D.1001 9. 若 一棵 二叉 树度 为2 的 结点 有 18 个， 度 为1 的结 点有10 个， 则 度 为0 的结 点个数 是 （ ）。 A. 46 B. 28 C. 19 D. 17 10. m 阶B- 树是 一棵 （ ）。 A .m 叉排 序树 B. m-1 叉 平衡 排序 树 C. m 叉平衡 排序 树 D. m+1 叉平 衡排 序树 二、 填空题( 每空 2 分 ，共 14 分) 1. 已 知一 棵二 叉树 的中 序 遍历序 列为GDHBAECIF ，后 序遍历 序列 为GHDBEIFCA ， 那么先 序 遍 历序 序 列 为 。 2. 若 某记 录的 关键 字序 列 是（491 ，77，572 ，16 ，996 ，101 ，863 ，258 ，689 ，325 ）， 以第 一 个关键 字为 枢轴 ，写 出采 用快速 排序 算法 第一 趟排 序 的结 果 。 考试科目： 计算机 基础 综合 共 4 页，第 1 页