2019年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题（第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．56B．57C．58D．604．在任意一棵非空平衡二叉树（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．仅IB．仅IIC．仅I、IID．仅I、III5．下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是。A．3和7B．12和12C．12和14D．15和156．用有向无环图描述表达式()(()/)xyxyx，需要的顶点个数至少是。A．5B．6C．8D．97．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅IIIB．仅I、IIC．仅II、III、IVD．I、II、III、IV·2·8．现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失败的平均查找长度是。A．4B．5.25C．6D．6.299．设主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。A．9B．10C．12D．1510．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不．可能是快速排序第二趟结果的是。A．5,2,16,12,28,60,32,72B．2,16,5,28,12,60,32,72C．2,12,16,5,28,32,72,60D．5,2,12,28,16,32,72,6011．设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是。A．1B．2C．3D．412．下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是。A．程序的功能都通过中央处理器执行指令实现B...
