资源描述
科目名称：程序设计 第 1 页 共 4 页 中国科 学院 大学 2013 年 招收 攻 读硕士 学位研 究生入 学统一 考试试 题 科目名 称：程 序设计 考 生须 知： 1本试卷满分为150 分，全部考试时间总计180 分钟。 2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 一 、判 断题（ 共 10 分， 每小 题 2 分） (1) 在 快 速排 序、 堆 排序、 归并排 序 和插 入排 序中， 堆排 序所 需 要的 附加 存储 开销 最大 。 【 】 (2) 图的深 度遍 历不 适用 于有 向图。 【 】 (3) 用 Prim 算法和 Kruskal 算 法分别 构造 的图 的最 小生 成树不 一定 相同 。 【 】 (4) 对 一 个具有 n 个元 素的 线性 表 ，建 立其 有序 单链 表的 时 间复 杂度为 O(n) 。 【 】 (5) 在 长 度都为 n 的 有序 单链 表和顺 序表 上分 别做 顺序 查找， 若查 找每 个元 素的 概率相 等 ， 则顺序 查找 表中 任一 元素 的查找 成功 的平 均查 找长 度相同 。 【 】 二 、选 择题（ 共 20 分， 每题 2 分） 1、 若想 把数 组中 的 100 个元 素 调整 为小 根堆 （或 大根 堆 ） ， 需做 【 】 次 关键字 值比 较。 A 164 B 195 C 220 D 257 2、执行 下面 的程 序段 ，语句 3 的执 行次 数为 【 】。 for (i=0; ii; j-) (2) state; (3) A ( 2) / 2 nn + B ( 1)( 2) / 2 nn + C ( 1) / 2 nn + D ( 1)( 2) nn + 3、如果 具有 n 个 顶点 的图是 一 个环 ，则 它有 【 】棵 生成 树。 A n B 2n C n-1 D n+1 4、下面 关于 B 树和 B + 树的 叙 述中 ，不 正确 的是 【 】 A. B 树和 B + 树都 是平 衡的多 分 树 B. B 树和 B + 树都 是可 用于 文件的 索引 结构 C. B 树和 B + 树都 能有 效地 支持顺 序检 索 科目名称：程序设计 第 2 页 共 4 页 D. B 树和 B + 树 都 能有 效地支 持 随机 检索 5、若一 棵二 叉树 具有 10 个 度为 2 的结 点， 则该 二叉 树 的度为 0 的结 点个 数是 【 】 A. 9 B. 11 C. 12 D. 不确定 6、含有 12 个结 点的 平衡 二叉树 的最 大深 度为 【 】。 A 3 B 4 C 5 D 6 7、若 用数 组名 作为 函数 调 用的实 参， 则传 递给 形参 的是【 】。 A 数组 的首 地址 B 数 据第 一个 元素 的值 C 数 组中 全部 元素 的值 D 数组 元素 的个 数 8、 设待 排序 关键 码序 列为25 ，18 ，9，33 ，67 ，82 ，53 ，95 ，12 ，70 。 要按关 键 码值 递增 的顺序 进行 排序 ， 采 取以 第一个 关键 码为 分界 元素 的快速 排序 法， 第一 趟排 序完成 后关 键码 95 被放 置在 第几 个位 置？【 】。 A 7 B 8 C 9 D 10 9、能有 效缩 短关 键路 径长度 的 方法 是【 】。 A 缩 短任 意一 个活 动的持 续 时间 B 缩短 关键 路径 上任 意一 个关键 活动 的持 续时 间 C 缩短 多条 关键 路径 上共 有的任 意一 个关 键活 动的 持续时 间 D 缩短 所有 关键 路径 上 共有的 任意 一个 关键 活动 的持续 时间 10、当一 个有 N 个顶点 的 图用邻 接矩 阵 A 表示时 ， 顶点 i V 的度为 【 】。 A 1 , n i Ai j = B 1 , n j Ai j = C 1 , n i Aji = 11 , , nn ij Ai j A j i = = + 三 填 空题（ 共 20 分， 每空 2 分） 1 、 设 m 、n 、a 、b 、c 均为 int 型变量且 m=2 ，n=1 ，a=1 ，b=2 ，c=3 ，则执行表达式 d=(m=a!=b) for (i=1; i=n; i+) for(j=1; j=i ; j+) for(k=1; k=j ; k+) x=x+y; 5、 有 一棵 二叉 排序 树按 先序遍 历得 到的 序列 为（50 ，38 ，30 ，45 ，40 ，48 ，70，60 ，75 ， 80） ， 试画 出该 平衡 二叉 树 ，并求 出等 概率 下的 查找 成功和 查找 失败 的平 均查 找长度 。 五 、写 算法（ 共 50 分， 每题 25 分） 1、 已 知顺 序表 中有 n 个 记录 ， 表 中记 录不依 关键 字有序 排列 ， 编写一 算法 为该顺 序表建立 一个有 序的索 引表（ 依关 键字递 增排列） ，索 引表中 的每一 项应含 有记录 的关 键字和 该记录 在顺序 表中 的序 号。 要求 算法的 时间 复杂 度在 最好 的情况 下能 达 到 O(n) 。 要求： （1）写 出算 法的 基本 思 想； （2） 用熟 悉的 程序 设计语 言实 现上 述算 法。 2、 改 进有 向图 的邻 接表 存储方 法， 不用 遍历 整个 有向图 就可 获得 某个 顶点 的出 度和入度。 编写算 法实 现改 进的 有向 图邻接 表存 储。 要求： （1）写 出算 法的 基本 思 想； （2） 画出 下图 的改 进的有 向图 邻接 表示 意图 ； （3） 用熟 悉的 程序 设计语 言实 现上 述算 法。 V 0V 2V 3V 1
展开阅读全文