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

老当益壮，宁移白首之心；穷且益坚，不坠青云之志。——唐·王勃

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

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

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

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

求。

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

x=0；

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

x=x+l；

1/22

A.O(logn)B.O(n)C.O(n)D.O(n)

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

A.先序遍历B.中序遍历C.后序遍历D.按层遍历

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

A.56B.57C.58D.60

4.在任意一棵非空平衡二又树(AVL树)T中，删除某结点v之后形成平衡二又树T，再将w插入T形成平衡

122

二又树T。下列关于T与T的叙述中，正确的是

313

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

113

Ⅱ.若v不是T的叶结点，则T与T一定不相同

113

Ⅲ.若v不是T的叶结点，则T与T一定相同

113

A.仅IB.仅IIC.仅I、ⅡD.仅I、Ⅲ

5.下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是

A.3和7B.12和12C.12和14D.15和15

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

A.5B.6C.8D.9

7.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是

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

A.仅ⅢB.仅I、ⅡC.仅Ⅱ、Ⅲ、IVD.I、Ⅱ、Ⅲ、Ⅳ

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

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

是

A.4B.C.6D.

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

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