文档库

最新最全的文档下载
当前位置:文档库 > 2019年考研408计算机学科专业基础综合真题及答案

2019年考研408计算机学科专业基础综合真题及答案

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、Ⅲ

2019年考研408计算机学科专业基础综合真题及答案

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. 程序执行前,指令和数据需预先存放在存储器中