2019年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题
一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求。
1设
是描述问题规模的非负整数，下列程序段的时间复杂度是x0；while
xlxl
xxl；
AOlog

BO
12
CO

DO
2
2若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的
是
A先序遍历
B中序遍历
C后序遍历
D按层遍历
3对
个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则
的值是
A56
B57
C58
D60
4在任意一棵非空平衡二又树AVL树T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成
平衡二又树T3。下列关于T1与T3的叙述中，正确的是
I若v是T1的叶结点，则T1与T3可能不相同
Ⅱ若v不是T1的叶结点，则T1与T3一定不相同
Ⅲ若v不是T1的叶结点，则T1与T3一定相同
A仅I
B仅II
C仅I、Ⅱ
D仅I、Ⅲ
5下图所示的AOE网表示一项包含8个活动的工程。活动d
的最早开始时间和最迟开始时间分别是
A3和7B12和12C12和14D15和156用有向无环图描述表达式xyxyx，需要的顶点个
数至少是
A5
B6
C8
D9
7选择一个排序算法时，除算法的时空效率外，下列因素中，
还需要考虑的是
I数据的规模Ⅱ数据的存储方式
Ⅲ算法的稳定性V数据的初始状态
A仅Ⅲ
B仅I、Ⅱ
C仅Ⅱ、Ⅲ、IVDI、Ⅱ、Ⅲ、Ⅳ
8现有长度为11且初始为空的散列表HT，散列函数是Hkeykey7，采用线性探查线性探测再散列
法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找
长度是
A4
B525
C6
D629
9设主串T“abaabaabcabaabc”，模式串S“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在
匹配过程中进行的单个字符间的比较次数是
A9
B10
C12
D15
10排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序
第二趟结果的是
A5，2，16，12，28，60，32，72C2，12，16，5，28，32，72，60
B2，16，5，28，12，60，32，72D5，2，12，28，16，32，72，60
11设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是
A1B2C3D412下列关于冯诺依曼结构计算机基本思想的叙述中，错误的是
A程序的功能都通过中央处理器执行指令实现
B指令和数据都用二进制表示r