2019年计算机考研408真题（1-10）

考研408计算机统考分两部分，80分单项选择题和70分大题，满分150分。单项选择题总共80分，每小题2分，40小题。单项选择题，1-10题是数据结构部分；11-22题是计算机组成原理部分；23-32题是操作系统部分；33-40题是计算机网络部分。综合应用题70分，共7小题，41和42题是数据结构题，分值各为10分和15分；43和44题是计算机组成原理题，各占8分和13分；45和46题是操作系统题，各占7分和8分；47题是计算机网络题，分值为9分。为了方便大家更好的来备考，小编为大家整理了“2019年408计算机考研真题”，希望可以帮助大家更好的复习408计算机考研内容。

2019年考研408计算机统考考研真题

一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）

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

x=0;

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

x=x+1

A.O(logn)

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，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是（  ）。

I.若v是T1的叶结点，则T1与T3可能不相同

II.若v不是T1的叶结点，则T1与T3一定不相同

III.若v不是T1的叶结点，则T1与T3一定相同

A.仅I

B.仅II

C.仅I、II

D.仅I、III

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.数据的规模

II.数据的存储方式

III.算法的稳定性

IV.数据的初始状态

A.仅III

B.仅I、II

C.仅II、III、IV

D.I、II、III、IV

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="abaabc"，采用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