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的叙述中，
