2011
年全国硕士研究生人学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题
(1~40
小题,每小题
2
分,共
80
分。下列每小题给出的四个选项中,只有
一项符合题目要求)
1.
设
n
是描述问题规模的非负整数,下面程序片段的时间复杂度是
。
x=2;
while(x<n/2)
x=2,*;ip
A. O(log2n) B. O(n) C. O(nlog2n) D.
O(n
勺
2.
元素
a,
b, c,
d,
e
依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素
都出栈,则在所有可能的出栈序列中,以元素
d
开头的序列个数是
。
A. 3
B.
4 C. 5 D. 6
3.
已知循环队列存储在一维数组
A[O
...
n-1]
中,且队列非空时
front
和
rear
分别指向队头元
素和队尾元素。若初始时队列为空,且要求第
1
个进入队列的元素存储在
A[O]
处,则初始时
front
和
rear
的值分别是
。
A.
0,0
B.
O,n-1
C.
n-1,0
D.
n-I,n-1
4.
若一棵完全二叉树有
768
个结点,则该二叉树中叶结点的个数是
A. 257 B.
258·C.
384 D. 385
5.
若一棵二叉树的前序遍历序列和后序遍历序列分别为
1,
2, 3,
4
和
4,
3, 2,
I,
则该二叉树的
中序遍历序列不会是
。
A.
1,
2, 3, 4 B.
2,
3,
4,
1 C.
3,
2,
4, 1 D. 4,
3,
2, 1
6.
已知一棵有
2011
个结点的树,其叶结点个数为
116,
该树对应的二叉树中无右孩子的结
点个数是
。
A.
115
B.
116
C.
1895
D. 1896
7.
对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是
。
A. 95, 22, 91, 24, 94,
71
B.
92,20,91,34,88,35
C. 21, 89, 77,
29, 36,
38
.
D.
12,
25, 71, 68, 33, 34
8.
下列关于图的叙述中,正确的是
。
I.
回路是简单路径
II.
存储稀疏图,用邻接矩阵比邻接表更省空间
III.
若有向图中存在拓扑序列,则该图不存在回路
A.
仅
II
B.
仅
I
、
II
C.
仅
III
D.
仅
1
、
III
9.
为提高散列
(Hash)
表的查找效率,可以采取的正确措施是
。
I.
增大装填(载)因子
II.
设计冲突(碰撞)少的散列函数
2018年计算机408统考真题 第 1 页,共 8 页
评论0