2017年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题
一、单项选择题： 1～ 40小题，每小题 2分，共 80分。下列每题给出的四个选项中，只有一
个选项符合题目要求。
1．下列函数的时间复杂度是
int func ( int n)
{ int i=0, sum=0;
while(sum< n) sum += ++ i;
return i ;
{
A. O(log n) B. O(n
1/2
) C. O(n) D. O(nlog n)
2．下列关于栈的叙述中，错误
．．
的是
Ⅰ．采用非递归方式重写递归程序时必须使用栈
Ⅱ．函数调用时，系统要用栈保存必要的信息
Ⅲ．只要确定了入栈次序，即可确定出栈次序
Ⅳ．栈是一种受限的线性表，允许在其两端进行操作
A．仅Ⅰ B．仅Ⅰ、Ⅱ、Ⅲ
C．仅Ⅰ、Ⅲ、Ⅳ D．仅Ⅱ、Ⅲ、Ⅳ
3．适用于压缩存储稀疏矩阵的两种存储结构是
A．三元组表和十字链表 B．三元组表和邻接矩阵
C．十字链表和二叉链表 D．邻接矩阵和十字链表
4．要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是
A．只有左子树 B．只有右子树
C．结点的度均为 1 D．结点的度均为 2
5．已知一棵二叉树的树形如下图所示，其后序序列为 e，a，c， b，d，g，f，树中与结点 a
同层的结点是
A．c B．d C．f D．g
6．已知字符集 {a，b，c， d，e，f， g，h} ，若各字符的哈夫曼编码依次是
0100，10，0000，0101，001，011，11，0001，则编码序列
0100011001001011110101的译码结果是
A．a c g a b f h B．a d b a g b b
C． a f b e a g d D． a f e e f g d
剩余12页未读，继续阅读
评论0