2018年温州大学数据结构考研真题831.doc0页

2018年温州大学数据结构考研真题831.doc 2018 年硕 士研究 生 招生 考 试试 题 （A 卷） 科 目 代 码 及 名 称 ：831 数 据 结 构 适 用 专 业 ：081201 计 算 机 系 统 结 构 081202 计 算机 软件 与理 论 第 1 页， 共 4 页 （ 请 考 生在答 题纸 上答题 ，在 此试题 纸上 答题无 效 ） 一、 单项选 择题（10 小题，每 小题 4 分，共 40 分） 1. 计算机 所处 理的 数据 一般 具有某 种内 在联 系， 这是 指 （ ） 。 A. 数据 和数 据之 间存 在某 种关系 B. 数 据元 素和 数据 元素 之 间存在 某种 关系 C. 数 据元 素内 部具 有某 种 结构 D. 数据 项和 数据 项之 间存 在某种 关系 2. 顺序存 储方 式只 能用 于线 性结构 ，不 能用 于非 线性 结构 。 这个 断言 是（ ）。 A. 正确 的 B. 错 误的 3. 设某算 法完 成对 n 个 元素 进行处 理 ， 所需 的时 间是 T(n)=100nlog 2 n+200n+500 ，则该 算法 的时 间 复 杂度 是 （ ） 。 A. O(1) B. O(n) C. O(nlogn) D. O(nlogn+n) 4. 采用顺 序存 储的 两个 栈它 的共享 空间 为 S[1 …m] ，top[i] 代表第 i 个栈 （i=1 ，2 ） 的 栈顶 ， 栈 1 的底 在 S[1] ，栈 2 的底 在 S[m] ，则栈 满的 条件 是 （ ）。 A. top[2]-top[1]=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 5. 已知二 叉树 有 50 个 叶子 结 点，则 该二 叉树 的总 结点 数至少 应有 （ ） 个。 A. 99 B. 100 C. 101 D. 102 6. 无向 图 G 有 16 条 边， 度 为 4 的 顶点 有 3 个， 度 为 3 的顶 点有 4 个 ，其 余顶 点的度 均小 于 3 ，则 图 G 至 少有 （ ） 个顶 点 。 A. 10 B. 11 C. 12 D. 13 7. 对于一 个具 有 n 个顶 点的 无向图 ，若 采用 邻接 矩阵 表示， 则该 矩阵 的大 小是 （ ） 。 A. n B. (n-1)/2 C. n-1 D. n 2 8. 适合于 折半 查找 的表 的存 储方式 及元 素排 列要 求为 （ ）。 A. 链接 存储 ，元 素无 序 B. 链 接存 储， 元素 有序 C. 顺 序存 储， 元素 无序 D. 顺序 存储 ，元 素有 序 9. 排序算 法的 稳定 性是 指 （ ） 。 A. 经过 排序 之后 ，能 使值 相同的 数据 保持 原顺 序中 的相对 位置 不变 B. 经 过排 序之 后， 能使 值 相同的 数据 保持 原顺 序中 的绝对 位置 不变 C. 排 序算 法的 性能 与待 排 序元素 的数 量关 系不 大 D. 排序 算法 的性 能与 待排 序元素 的数 量关 系密 切 10. 5 个不 同的 数据 元素 进行 直接插 入排 序， 最多 需要 进行（ ）次 比较 。 A. 8 B. 14 C. 15 D. 25 二、 简答题 （4 小题 ， 每小题 10 分， 共 40 分） 1． 找出满 足以 下条 件的 所有 二叉树 ： （1 ） 二 叉树 的前 序序列 与中 序序 列相 同； （2） 二叉 树的 中序 序列 与后序 序列 相同 ； （3 ）二 叉树的 前序 序列 与后 序序 列相同 。 2． 假设通 讯电 文中 只用 到 A ，B ，C ，D ，E ，F 六个字 母，它 们在 电文 中出 现的 相对频 率分 别为 ：8 ， 3，16 ，10 ，5，20 。 （1） 构造哈 夫曼 树。 （2 ） 计算 该哈夫 曼树 的带 权路 径长 度 WPL 。 3． 己知序 列{355 ，672 ，91，83，781 ，34，410 ，76，125 ，320} ， 建大 根堆 。 4． 已知序 列{12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18} ， 请 按照 下面的 快速 排序 算法 ， 给 出 该序 列 作 升序 排 列 时前三 趟 的 结果 。