2013 年招收攻读硕士学位研究生入学统一考试试题 科目名称.pdf

中国科学院大学 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; i=n-1; i++) (1) for (j=n; ji; j--) (2) state; (3) A ．n(n +2) / 2 B ．(n −1)(n +2) / 2 C ．n(n +1) / 2 D ．(n −1)(n +2) 3、如果具有n 个顶点的图是一个环，则它有 【 】棵生成树。 A ． n B ．2n C ．n-1 D ．n+ 1 4 、下面关于B 树和B+树的叙述中，不正确的是 【 】 A. B 树和B+树都是平衡的多分树 B. B 树和B+树都是可用于文件的索引结构 C. B 树和B+树都能有效地支持顺序检索 科目名称：程序设计 第1 页 共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 ．缩短