考研计算机学科专业基础综合-17(总分：150.00，做题时间：90分钟)一、单项选择题(总题数：40，分数：80.00)1.栈S最多只能容纳4个元素，现在6个元素按A，B，C，D，E，F的顺序进栈，下列哪一个序列是可能的出栈序列( )?A．EDCBAF B．BCEFAD C．CBEDAF D．ADFEBC（分数：2.00）A.B.C. √D.解析：由于栈只能容纳4个元素，所以一次进栈最多4个，即ABCD同时在栈中，则EDCBAF不可能，E和F 还没有进栈就已经出栈，B中的D元素不可能出栈在A的后面。

D中最后两个元素出栈顺序也有误。

2.有A，B，C，D，E 5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出栈的序列中，下列正确的一组是( )。

A．CDBAE CDABE B．CDEBA CDBEAC．CDEAB CDABE D．CEBAE CDAEB（分数：2.00）A.B. √C.D.解析：要使得CD作为第一、二个元素出栈，应是A、B、C先入栈，C出栈，D入栈，D出栈；接着就剩下A、B在栈中，E未入栈，共3个元素，此三者序列为BAE，BEA，EBA。

3.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是( )。

A．39 B．52 C．111 D．119（分数：2.00）A.B.C. √D.解析：4.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u 和v可能具有的关系是( )。

Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系A．只有Ⅱ B．Ⅰ和Ⅱ C．Ⅰ和Ⅱ D．Ⅰ、Ⅱ和Ⅲ（分数：2.00）A.B. √C.D.解析：5.线索化的二叉树中，某结点*p没有孩子的充要条件是( )。

A．p-＞lchild=NULL B．p-＞ltag=1＆＆p-＞rtag=1C．p-＞ltag=0 D．p-＞lchild=NULL＆＆p-＞ltag＝1（分数：2.00）A.B. √C.D.解析：参考线索二叉树的定义。

6.设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是( )。

A．2，252．401，398，330，344，397，363 B．924，220，911，244，898，258，362，363 C．925，202，911，240，912，245，363D．2，399，387，219，266，382，381，278，363（分数：2.00）A.B.C. √D.解析：可以把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，C序列形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。

7.在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是( )。

A．顺序查找 B．二分法C．利用二叉搜索树 D．利用哈希(hash)表（分数：2.00）A.B.C.D. √解析：8.如下所示带权图G，其最小生成树各边权的总和为( )。

[*]A．14 B．19 C．21 D．26（分数：2.00）A.B.C. √D.解析：9.将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是( )，最多需要比较的次数是( )。

A．N，2N-1 B．N-1，2NC．N，2N D．N-1，2N-1（分数：2.00）A. √B.C.D.解析：10.用直接插入排序方法对下列4个表进行(由小到大)的排序，比较次数最少的是( )。

A．94，32，40，90，80，46，21，69 B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80 D．90，69，80，46，21，32，94，40（分数：2.00）A.B.C. √D.解析：11.CPU中决定指令执行顺序的是( )。

A．指令寄存器IR B．程序计数器PCC．程序状态字寄存器PSWR D．主存地址寄存器MAR（分数：2.00）A.B. √C.D.解析：CPU中用程序计数器PC来跟踪下一条将要执行的指令的地址，即通过程序计数器PC来决定指令执行顺序。

12.一个C语言程序在一台32位机器上运行。

程序中定义了三个变量x、y和z，其中x和z是int型，y 为short型。

当x=127，y=-9时，执行赋值语句z=x+y后，x、y和z的值分别是( )。

A．x=0000007FH，y=FFF9H，z=00000076HB．x=0000007FH，y=FFF9H，z=FFFF0076HC．x=0000007FH，y=FFF7H，z=FFFF0076HD．x=0000007FH，y=FFF7H，z=00000076H（分数：2.00）A.B.C.D. √解析：结合题干及选项可知，int为32位，short为16位；又C语言的整型数据在内存中为补码形式，故x、y的机器数写为十六进制为O000007FH、FFF7H；执行z=x+y时，由于x为int型，y为short型，故需将y的类型强制转换为int，在机器中通过符号位扩展实现，由于y的符号位为1，故在y的前面添加16个1，即可将y强制转换为int型，其十六进制形式为FFFFFFF7H；然后执行加法，即0000007FH+FFFFFFF7H=00000076H(最高位的进位1自然丢弃)。

故选D。

13.原码两位乘中，符号位单独处理，参加操作的数是( )。

A．原码 B．补码C．绝对值的原码 D．绝对值的补码（分数：2.00）A.B.C.D. √解析：原码两位乘中，符号位单独处理，但运算过程中可能需要进行“减被乘数绝对值”的操作，计算机中减法一般通过补码加法来实现，故原码两位乘运算过程中参加操作的数是绝对值的补码。

14.在Cache和主存构成的两级存储系统中，Cache的存取时间为100ns，主存的存取时间为1μs，Cache 访问失败后CPU才开始访存。

如果希望Cache—主存系统的平均存取时间不超过Cache存取时间的15%，则Cache的命中率至少应为( )。

A．95% B．98% C．98.5% D．99.5%（分数：2.00）A.B.C. √D.解析：设Cache—主存系统的平均存取时间为Cache存取时间的1.15倍时Cache命中率为p，则有100+1000×(1-p)=115，解之得，p=0.985=98.5%。

15.双端口存储器之所以能高速读写是因为( )。

A．采用了两套独立的存储体 B．采用了两套相互独立的读写电路C．采用了新型的器件 D．两套读写电路分时使用存储体（分数：2.00）A.B. √C.D.解析：双端口存储器采用了两套相互独立的读写电路，两套读写电路可以同时访问共同的存储体，故可以高速读写。

16.某机主存容量64KB，按字节编址。

主存地址0100H处有一条相对转移指令，指令字长16位，其中，第一个字节为操作码，第二个字节为相对位移量(用补码表示)，则该指令执行结束后，后继指令的地址范围可能是( )。

A．0000H～FFFFH B．0080H～017FHC．0082H～0181H D．0080H～01FFH（分数：2.00）A.B.C. √D.解析：该指令取指结束后，PC值自动加2，即(PC)=0102H；相对位移量用8位补码表示，故其范围为80H～7FH，扩展到16位为FF80H～007FH，与PC值相加就可得后继指令的地址范围为0082H～0181H。

17.下列哪个选项不是RISC的特点( )。

A．只有取数和存数指令访问存储器，其余指令都在寄存器之间进行B．由使用频率高的简单指令和很有用且不复杂的指令组成C．使用RISC技术后，指令系统又回到了计算机发展早期的比较简单的情况D．使用优化的编译程序（分数：2.00）A.B.C. √D.解析：早期的指令系统简单是由设计水平和器件水平决定的，而且RISC技术不是简单地精简了指令系统，而是在合理选择简单指令的基础上采取了很多优化措施，如缩短机器周期，采用流水线技术，使用优化的编译程序等等，两者不可等同。

18.下列微指令的编码方式中，执行速度最快的是( )。

A．直接编码 B．字段直接编码C．字段间接编码 D．无法判断（分数：2.00）A. √B.C.D.解析：直接编码方式下，微指令操作控制字段中的每一位代表一个微操作命令，微操作命令的发出不需要通过译码，故执行速度最快。

19.相对于微程序控制器，硬布线控制器的特点是( )。

A．指令执行速度慢，指令功能的修改和扩展容易B．指令执行速度慢，指令功能的修改和扩展难C．指令执行速度快，指令功能的修改和扩展容易D．指令执行速度快，指令功能的修改和扩展难（分数：2.00）A.B.C.D. √解析：硬布线控制器采用硬连线逻辑，故一旦构成，除非在物理上进行重新布线，否则指令功能无法修改和扩展；微程序控制器采用存储逻辑，当需要对指令功能进行修改和扩展时，只要重新设计微代码的码点，并将其注入控制存储器中即可；但是由于采用存储逻辑，相比硬布线控制器多了从控制存储器中读出码点的过程，故其执行速度较慢。

综合上述分析，可知D正确。

20.某机采用计数器定时查询方式来进行总线判优控制，共有4个主设备竞争总线使用权，当计数器初值恒为102时，4个主设备的优先级顺序为( )。

A．设备0＞设备1＞设备2＞设备3 B．设备2＞设备1＞设备0＞设备3C．设备2＞设备3＞设备0＞设备1 D．设备2=设备3=设备0=设备1（分数：2.00）A.B.C. √D.解析：计数器初值为10[2]，故设备2的优先级最高，计数器值会递增然后返回到0，故优先级顺序为设备2＞设备3＞设备0＞设备1。

21.下列通道中，以字节为单位进行数据传送的是( )。

A．字节多路通道 B．选择通道 C．数组多路通道 D．以上都是（分数：2.00）A. √B.C.D.解析：选择通道和数组多路通道都是以数据块为单位进行数据传送。

22.下列选项中，能引起外部中断的事件是( )。

A．键盘输入 B．除数为0 C．浮点运算下溢 D．访存缺页（分数：2.00）A. √B.C.D.解析：浮点数下溢一般做“机器零”处理．不引起中断；除数为0、访存缺页会引出内部中断；只有键盘输入能引起外部中断，故选A。

23.单处理机系统中，可并行的是( )。

Ⅰ进程与进程Ⅱ处理机与设备Ⅲ处理机与通道Ⅳ设备与设备A．Ⅰ、Ⅱ和Ⅲ B．Ⅰ、Ⅱ和Ⅳ C．Ⅰ、Ⅲ和Ⅳ D．Ⅱ、Ⅲ和Ⅳ（分数：2.00）A.B.C.D. √解析：进程和进程是不能并行的，因为只有一个CPU。

24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是( )。

A．时间片轮转调度算法 B．短进程优先调度算法C．先来先服务调度算法 D．高响应比优先调度算法（分数：2.00）A.B.C.D. √解析：响应比=(等待时间+执行时间)/要求服务的时间。