2016年计算机专业基础真题及答案

【新祥旭考研】 / 2016-04-04

　一、单项选择题：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.3

　　B.4

　　C.5

　　D.6

　　解答：B。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。

　　3. 已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是

　　A.0,0

　　B.0，n-1

　　C.n-1,0

　　D.n-1，n-1

　　解答：B。插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

　　4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是

　　A.257

　　B.258

　　C.384

　　D.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,4

　　B.2,3,4,1

　　C.3,2,4,1

　　D.4,3,2,1

　　解答：C。由前序和后序遍历序列可知3为根结点，故(1,2)为左子树，(4)为右子树，C不可能。或画图即可得出结果。

　　6. 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是

　　A.115

　　B.116

　　C.1895

　　D.1896

　　解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。

　　„„

　　共116个叶结点

　　7. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是

　　A.95,22,91,24,94,71

　　C.21,89,77,29,36,38

　　B.92,20,91,34,88,35

　　D.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.1

　　B.2

　　C.4

　　D.5

　　解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。

　　12.下列选项中，描述浮点数操作速度指标的是

　　A.MIPS

　　B.CPI

　　C.IPC

　　D.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，即C104000H

　　14.下列各类存储器中，不采用随机存取方式的是

　　A.EPROM

　　B.CDROM

　　C.DRAM

　　D.SRAM

　　解答：B。光盘采用顺序存取方式。

　　15.某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是

　　A.22位

　　B.23位

　　C.25位

　　D.26位

　　解答：D。64MB的主存地址空间，故而MAR的寻址范围是64M，故而是26位。而实际的主存的空间不能代表MAR的位数。