资源描述
科目名称：程序设计 第 1 页 共 4 页 中国科 学院研 究生院 2012 年 招收 攻 读硕士 学位研 究生入 学统一 考试试 题 科目名 称：程 序设计 考 生须 知： 1本试卷满分为150 分，全部考试时间总计180 分钟。 2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 一 、判 断题（ 共 10 分， 每小 题 2 分） (1) Floyd 算法求两个 顶点 的最 短路径 时，path k-1 一 定是 path k 的子 集。 【 】 (2) 在 快 速排 序、 堆 排序、 归并排 序 和插 入排 序中， 堆排 序所 需 要的 附加 存储 开销 最大 。 【 】 (3) 用 Prim 算法和 Kruskal 算 法分别 构造 的图 的最 小生 成树不 一定 相同 。 【 】 (4) 在结点 数多 于1 的 哈夫 曼树 中 不存 在度为 1 的结 点。 【 】 (5) 在 长 度都为 n 的有 序单 链 表和顺 序表 上分 别做 顺序 查找， 若查 找每 个元 素的 概率相 等， 则顺序 查找 表中 任一 元素 的查找 成功 的平 均查 找长 度相同 。 【 】 二 、选 择题（ 共 20 分， 每题 2 分） 1、在 存储 数据 时， 通常 不 仅要存 储各 数据 元素 的值 ，而且 还要 存储 【 】 。 A 数 据的 操作 方法 B 数 据的 存取方 法 C 数 据元 素之 间的 关系 D 数 据元 素的类 型 2、程序 段 for ( i=n-1; i1; i- ) for ( j=1; jAj+1) Aj 与 Aj+1 对换; 其中 n 为正 整数 ，则 最后 一行的 语句 频度 在最 坏情 况下是 【 】。 A O(n) B O(n 2 ) C O(n log 2 n) D 不直 接依 赖于 n 3、在顺 序表 的动 态存 储定义 中 需要 包含 的数 据成 员是 【 】 I 数组基址 base II 表中元素 个数 n III 数组指针*data IV 表的 大小 maxSize A II 、III B I 、II 、III C II 、III 、IV D 全部 需要 科目名称：程序设计 第 2 页 共 4 页 4、对于 一个线 性表 既要能 够进行 较快速 地插入 和删 除，又 要求存 储结构 能反 映数据 之间的 逻辑关 系， 则应 选用 【 】 A 链式 存储 方式 B 顺序 存储 方式 C 散列 存储 方式 D 以上 均可 以 5、3 个数 顺序 （依 次） 进 栈，出 栈序 列有 【 】 种。 A 4 B 5 C 6 D 7 6、度为 4 、高 度为 h 的树， 则 【 】 A至 少有 h+3 个 结点 B至 多有 4h-1 个 结点 C至 多有 4h 个 结点 D至 少有 h+4 个 结点 7、若 用数 组名 作为 函数 调 用的实 参， 则传 递给 形参 的是【 】。 A 数组 的首 地址 B 数 据第 一个 元素 的值 C 数 组中 全部 元素 的值 D 数组 元素 的个 数 8、假设 一棵 二叉 树的 结点个 数为 50 ，则 它的 最小 高 度是【 】 A 4 B 5 C 6 D 7 9、对 于下 列关 键字 序列 ， 不可能 构成 某二 叉排 序树 中一条 查找 路径 的序 列是 【 】。 A 92，20，91，34，88，35 B 95 ，22 ，91 ，24 ，94，71 C 21 ，89 ，77 ，29 ，36 ，38 D 12，25，71，68，33，34 10、二 叉树 在线 索化 后， 仍不能 有效 求解 的问 题是 【 】。 A 先 序线 索二 叉树 中求先 序 后继 B 中序 线索 二叉 树中 求中 序后继 C 中序 线索 二叉 树中 求中 序前驱 D 后 序线 索二 叉树 中求后 序 后继 三 填 空题（ 共 20 分， 每空 2 分） 1 、 数据结构是【 】 。一个算法的设计和实现分别取决于所选定的 【 】。 2、设栈 S 和队列 Q 的初始 状 态均 为空 ，元素 abcdefg 依 次进 入栈 S 。 若 每个元 素 出栈 后立 即 进 入队列 Q ，且 7 个 元素 出 队列 的顺 序是 bdcfeag ， 则栈 S 的 容量 至少 是【 】 。 3、已知 一棵 完全 二叉 树的第 6 层 （设 根为第 1 层 ）有 8 个 叶结 点， 则完 全二叉 树 的结 点个 数最少 是【 】。 4、在排 序二 叉树 中的 查找效 率 与 【 】有关 。 科目名称：程序设计 第 3 页 共 4 页 5、 已知 一个 长度 为 16 的 顺序表 ， 其元 素按关 键字 有序排 列 ， 若 采用折 半查 找一个 不存 在 的 元素， 则比 较的 次数 至少 是【 】 ， 至多 是【 】。 6、 一棵 赫夫 曼树 共有 215 个 结 点， 对 其进 行赫 夫曼编 码， 共能 得到 【 】 个不 同 的码 字。 7、一 个有 n 个顶 点和 n 条 边的无 向图 一定 是【 】。 8、在 含有 n 个顶 点和 e 条 边的无 向图 的邻 接矩 阵中 ，零元 素的 个数 为【 】。 四 、问 答题（ 共 50 分， 每题 10 分） 1、 一 个算 法所 需时 间由 下述递 归方 程表 示， 试求 出该算 法的 时间 复杂 度级 别。 T(n) = 1, 若 n = 1 2T n 2 + n, 若 n 1式中，n 是问 题规 模， 设 n 是 2 的 整数 幂。 2、 依次 把结 点 （34 ，23 ，15，98，115 ，28 ，107 ） 插入到 初始 状态 为空 的平 衡二叉 排序 树 中， 使 得每 次插 入后 保持 该树仍 然是 平衡 二叉 树。 请依次 画出 每次 插入 后所 形成的 平衡 二叉 排序树 。 3、 试 为下 列每 种情 况选 择合适 的排 序方 法： （1）n=30 ，要 求最 坏情 况下 速 度最 快； （2）n=30 ， 要求 既快 又要 排序稳 定； （3）n=1000，要 求平 均情 况下速 度最 快； （4）n=1000，要 求最 坏情 况下速 度最 快且 稳定 ； （5）n=1000，要 求既 快又 最省内 存。 4、 将下 列递 推过 程改 写为 递 归过 程。 void ditui(int n) int i; i=n; while (i1) printf(i-); 5、 设有 序顺序 表的元 素 依次为 017、094、154 、170 、275 、503 、509 、512 、553、612、 677、765 、897 、908 。 （1）画 出对 其进 行折 半查找 的 判定 树。 科目名称：程序设计 第 4 页 共 4 页 （2）若 查找 275 或 684 的 元素， 将依 次与 表中 哪些 元素比 较？ （3） 计算 查找 成功 的平 均 查找长 度和 查找 不成 功的 平均查 找长 度。 五 、写 算法（ 共 50 分， 每题 25 分） 1、 给 定两 个单 链表 ，编 写算法 找出 两个 链表 的公 共结点 。 要求： （1） 写出 算法 的基 本思想 ，给 出算 法时 间复 杂度； （2） 用熟 悉的 程序 设计语 言实 现上 述算 法。 2、 试 编写 一个 算法， 判断 一 个无 向图 G 是否为 一 棵树 。 若是 一棵 树， 则 算法 返回 true，否 则 返回 false 。 要求： （1）写 出算 法的 基本 思 想； （2） 用熟 悉的 程序 设计语 言实 现上 述算 法。
展开阅读全文