2019年全国硕士研究生招生考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要

求。

1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是

x=0；

while(n>=(x+l)*(x+l))

x=x+l；

A. O(log n)

B. O(n1/2)

C. O(n)

D. O(n2)

2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的

是

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层遍历

3.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是

A. 56

B. 57

C. 58

D. 60

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

的最早开始时间和最迟开始时间分别是

A. 3和7

B. 12和12

C. 12和14

D. 15和15

6.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个

数至少是

A. 5

B. 6

C. 8

D. 9

7.选择一个排序算法时，除算法的时空效率外，下列因素中，

还需要考虑的是

I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态

A. 仅Ⅲ

B. 仅I、Ⅱ

C. 仅Ⅱ、Ⅲ、IV

D. I、Ⅱ、Ⅲ、Ⅳ

8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)

法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是

A. 4

B. 5.25

C. 6

D. 6.29

9.设主串T=“abaabaabcabaabc”，模式串S=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在

匹配过程中进行的单个字符间的比较次数是

A. 9

B. 10

C. 12

D. 15

10. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序

第二趟结果的是

A. 5，2，16，12，28，60，32，72

B. 2，16，5，28，12，60，32，72

C. 2，12，16，5，28，32，72，60

D. 5，2，12，28，16，32，72，60

11. 设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是

A. 1

B. 2

C. 3

D. 4

12. 下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是

A. 程序的功能都通过中央处理器执行指令实现

B. 指令和数据都用二进制表示，形式上无差别

C. 指令按地址访问，数据都在指令中直接给出

D. 程序执行前，指令和数据需预先存放在存储器中