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．用有向无环图描述表达式(xy)((xy)/x)，需要的顶点个数至少是。A．5B．6C．8D．97.选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅IIIB．仅I、IIC．仅II、III、IVD．I、II、III、IV2019年计算机408统考真题第1页，共7页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.指令和数据都用二进制数表示，形式上无差别C．指令按地址访问，数据都在指令中直接给出D．程序执行前，指令和数据需预先存放在存储器中13.考虑以下C语言代码：unsignedshortusi=65535;shortsi=usi;执行上述程序段后，si的值是。A．-1B．-32767C．-32768D．-6553514.下列关于缺页处理的叙述中，错误的是。A．缺页是在地址转换时CPU检测到的一种异常B．缺页处理由操作系统提供的缺页处理程序来完成C.缺页处理程序根据页故障地址从外存读入所缺失的页D．缺页处理完成后回到发生缺页的指令的下一条指令执行15.某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为FF12H，基址寄存器的内容为F0000000H，则该操作数的LSB（最低有效字节）所在的地址是。A．F000FF12HB．F000FF15HC．EFFFFF12HD．EFFFFF15H16.下列有关处理器时钟脉冲信号的叙述中，错误的是。A．时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B．时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C．时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D．处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令17.某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是。I．通用寄存器组（GPRs）II．算术逻辑单元（ALU）2019年计算机408统考真题第2页，共7页I1：adds2,s1,s0I2：loads3,0(t2)I3：adds2,s2,s3I4：stores2,0(t2)//R[s2]R[s1]+R[s0]//R[s3]M...
