中国科学院大学-864程序设计【2013】考研真题
2023-06-21
999+
86.9KB
4 页
侵权投诉
科目名称：程序设计 第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; i<=n-1; i++) (1)
for (j=n; j>i; j--) (2)
state; (3)
A．
( 2) / 2nn+
B．
( 1)( 2) / 2nn−+
C．
( 1) / 2nn+
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 ji
= =
+
∑∑
三．填空题（共 20 分，每空 2分）
1、设 m、n、a、b、c均为 int 型变量且 m=2，n=1，a=1，b=2，c=3，则执行表达式
d=(m=a!=b)&&(n=b>c)后，n的值为【 】； m的值为【 】。
2、前序遍历序列和中序遍历序列相同的二叉树为【 】。
3、有关键码值为 10、20、30 的三个结点。按所有可能的插入顺序去构造二叉排序树，能构
造出【 】棵不同的二叉排序树。
标签： #中国科学院大学
摘要：
展开>>
收起<<
科目名称：程序设计第1页共4页中国科学院大学2013年招收攻读硕士学位研究生入学统一考试试题科目名称：程序设计考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、判断题（共10分，每小题2分）(1)在快速排序、堆排序、归并排序和插入排序中，堆排序所需要的附加存储开销最大。【】(2)图的深度遍历不适用于有向图。【】(3)用Prim算法和Kruskal算法分别构造的图的最小生成树不一定相同。【】(4)对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为O(n)。【】(5)在长度都为n的有序单链表和顺序表上分别做顺序...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
