天勤论坛2016年全国硕士研究生入学统一考试(计算机科学与技术学科联考计算机学科专业基础综合试题).doc

2013 年全国硕士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题:1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个
选项符合试题要求。
1. 已知两个长度分别为 m 和 n 的升序链表,若将它们合并为一个长度为 m+n 的降序链表,则
最坏情况下的时间复杂度是
A. O(n)
B. O(m ´ n)
C. O(min(m, n))
D. O(max(m, n))
2. 一个栈的入栈序列为 1, 2, 3,
的个数是

,n ,其出栈序列是 p1, p2 , p3 ,

, pn 。若 p2 = 3 ,则 p3 可能取值
A. n - 3
B. n - 2
C. n -1
D. 无法确定
3. 若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中,则 T 中平衡因
子为 0 的分支结点的个数是
A. 0
B. 1
C. 2
D. 3
4. 已知三叉树 T 中 6 个叶结点的权分别是 2,3,4,5,6,7,T 的带权(外部)路径长度最
小是
A. 27
B. 46
C. 54
D. 56
5. 若 X 是后序线索二叉树中的叶结点,且 X 存在左兄弟结点 Y,则 X 的右线索指向的是
A. X 的父结点
C. X 的左兄弟结点 Y
B. 以 Y 为根的子树的最左下结点
D. 以 Y 为根的子树的最右下结点
6. 在任意一棵非空二叉排序树 T1 中,删除某结点 v 之后形成二叉排序树 T2,再将 v 插入 T2 形
成二叉排序树 T3。下列关于 T1 与 T3 的叙述中,正确的是
I.
若 v 是 T1 的叶结点,则 T1 与 T3 不同
II. 若 v 是 T1 的叶结点,则 T1 与 T3 相同
III. 若 v 不是 T1 的叶结点,则 T1 与 T3 不同
IV. 若 v 不是 T1 的叶结点,则 T1 与 T3 相同
A. 仅 I、III
B. 仅 I、IV
C. 仅 II、III
D. 仅 II、IV
7. 设图的邻接矩阵 A 如下所示。各顶点的度依次是
é0 1 0 1ù
A = ê ú
ê0 1 0 0ú
ê ú
ë1 0 0 0û
A. 1,2,1,2
B. 2,2,1,1
C. 3,4,2,3
D. 4,4,2,2
.
A. h,c,a,b,d,e,g,f
C. d,b,c,a,h,e,f,g
B. e,a,f,g,b,h,c,d
D. a,b,c,d,h,e,f,g
ê0 0 1 1ú
8. 若对如下无向图进行遍历,则下列选项中,不是广度优先遍历序列的是
此文档由天勤论坛整理(),转载请注明出处!
a
b

e
c

d

f

g
h
9. 下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工
程的工期。下列选项中,加快其进度就可以缩短工程工期的是
a=3

2

c=9
e=6

4

g=6
2

b=8
d=4

2

f=10

4

h=9
4
和 e

B. d 和 e

C. f 和 d

D. f 和 h
10. 在一株高度为 2 的 5 阶 B 树中,所含关键字的个数最少是

B. 7
C. 8
D. 14
11. 对给定的关键字序列 110,119,007,911,114,120,122 进行基数排序,则第 2 趟分配
收集后得到的关键字序列是
A. 007,110,119,114,911,120,122 B. 007,110,119,114,911,122,120
C. 007,110,911,114,119,120,122
D. 110,120,911,122,114,007,119
12. 某计算机主频为 GHz,其指令分为 4 类,它们在基准程序中所占比例及 CPI 如下表所
示。
该机的 MIPS 数是
A. 100
B. 200
C. 400
D. 600
13. 某数采用 IEEE 754 单精度浮点数格式表示为 C640 0000H,则该数的值是
指令类型
所占比例
CPI
A
50%
2
B
20%
3
C
10%
4
D
20%
5
此文档由天勤论坛整理(),转载请注明出处!
A. -×213

B. -×212