2016考研计算机学科专业基础综合真题及答案.docx
2016考研计算机学科专业基础综合真题及答案一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。请在答题卡上将所选项的字母涂黑。)1. 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2;while(xx=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。2. 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.6解答：B。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。3. 已知循环队列存储在一维数组A0.n-1中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A0处，则初始时front和rear的值分别是A.0,0B.0，n-1C.n-1,0D.n-1，n-1解答：B。插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257B.258C.384D.385解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1(总结点数为偶数)，故而即2n=768。5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1解答：C。由前序和后序遍历序列可知3为根结点，故(1,2)为左子树，(4)为右子树，C不可能。或画图即可得出结果。6. 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A.115B.116C.1895D.1896解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。共116个叶结点7. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是A.95,22,91,24,94,71C.21,89,77,29,36,38B.92,20,91,34,88,35D.12,25,71,68,33,34解答：A。选项A中，当查到91后再向24查找，说明这一条路径之后查找的数都要比91小，后面的94就错了。8. 下列关于图的叙述中，正确的是. 回路是简单路径.存储稀疏图，用邻接矩阵比邻接表更省空间.若有向图中存在拓扑序列，则该图不存在回路A.仅B.仅、C.仅D.仅、解答：C。.回路对应于路径，简单回路对应于简单路径;.刚好相反;.拓扑有序的必要条件。故选C。9. 为提高散列(Hash)表的查找效率，可以采取的正确措施是. 增大装填(载)因子.设计冲突(碰撞)少的散列函数.处理冲突(碰撞)时避免产生聚集(堆积)现象A.仅B.仅C.仅、D.仅、解答：B。III错在“避免”二字。10.为实现快速排序算法，待排序序列宜采用的存储方式是A.顺序存储 B.散列存储 C.链式存储解答：A。内部排序采用顺序存储结构。D.索引存储11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A.1B.2C.4D.5解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。12.下列选项中，描述浮点数操作速度指标的是A.MIPSB.CPIC.IPCD.MFLOPS解答：D。送分题。13.float型数据通常用IEEE 754单精度浮点数格式表示。若编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是A.C104 0000H B.C242 0000H C.C184 0000H D.C1C2 0000H解答：A。x的二进制表示为-1000.01-1.000 01×211根据IEEE754标准隐藏最高位的“1”，又E-127=3，所以E=130=1000 0010(2)数据存储为1位数符+8位阶码(含阶符)+23位尾数。故FR1内容为1 10000 0010 0000 10000 0000 0000 0000 000即1100 0001 0000 0100 0000 0000 0000 0000，即C104000H14.下列各类存储器中，不采用随机存取方式的是A.EPROMB.CDROMC.DRAMD.SRAM解答：B。光盘采用顺序存取方式。15.某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是A.22位B.23位C.25位D.26位解答：D。64MB的主存地址空间，故而MAR的寻址范围是64M，故而是26位。而实际的主存的空间不能代表MAR的位数。16.偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是A.间接寻址B.基址寻址C.相对寻址D.变址寻址解答：A。间接寻址不需要寄存器，EA=(A)。基址寻址：EA=A+基址寄存器内同;相对寻址：EAA+PC内容;变址寻址：EAA+变址寄存器内容。17.某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt(无符号整数比较大于时转移)的转移条件是A. CF +OF =1B. SF +ZF =1C. CF +ZF =1D. CF +SF =1解答：C。无符号整数比较，如A>B，则A-B无进位/借位，也不为0。故而CF和ZF均为0。18.下列给出的指令系统特点中，有利于实现指令流水线的是. 指令格式规整且长度一致 .指令和数据按边界对齐存放.只有Load/Store指令才能对操作数进行存储访问A.仅、B.仅、C.仅、D.、解答：D。指令定长、对齐、仅Load/Store指令访存，以上三个都是RISC的特征。均能够有效的简化流水线的复杂度。19.假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误.的是A.每个指令周期中CPU都至少访问内存一次B.每个指令周期一定大于或等于一个CPU时钟周期C.空操作指令的指令周期中任何寄存器的内容都不会被改变D.当前程序在每条指令执行结束时都可能被外部中断打断解答：C。会自动加1，A取指令要访存、B时钟周期对指令不可分割。20.在系统总线的数据线上，不.可能传输的是A.指令C.握手(应答)信号B.操作数D.中断类型号解答：C。握手(应答)信号在通信总线上传输。
