2015年计算机真题及解析

2015年全国硕士研究生通过统考计算机学科专业基础综合问题一、个别选择题： 140小题，每小题2分，共80分。 以下四个选项中，只有一个满足主题要求。 请用黑色填充回答卡上选择的文字。1 .已知程序如下：int s(int n ) return (n=0)？ 0 : s(n-1) n； 以下称为void main () cout s(1)； 以下称为程序运行时使用堆栈保存调用进程的信息，从堆栈底部到堆栈顶部保存的信息一次对应的是a.main ()-s (1)-s (0) b.s (0)-s (1)-main ()c.main ()-s (0)-s (1) d.s (1)-s (0)-main ()d .先序序列为a、b、c、d的不同二叉树的数量A.13B.14C.15D.163 .以下选项指示了从根到两个叶节点的路径上的权重序列，并且可以属于同一本书的霍夫曼曼树呢a.24，10，5和24，10，7 b.24，10，5和24，12，7c.24，10，10和24，14，11 d.24，10，5和24，14，64 .当前有一个具有不重复关键字的平衡二叉树(AVL树)，对其进行中间扫描可得到降序序列。 在以下关于平衡二叉树的描述中，正确的是a .根节点的度必须是2B .树中的最小要素是叶节点c .最后插入的要素是叶节点d .树中的最大要素必须没有左子树当根据有向图G=(V，e )、顶点集合V=V0，V1，V2，V3、边缘集合e=，、顶点V0来遍历图时，可以获得不同遍历序列的数目A.2B.3C.4D.56 .当确定下一个带权图的最小(代价)生成树时，可能是第二次选择克鲁斯卡(kruskal )算法，但是不是Prim算法，而是第二次选择的边缘是从V4开始的A.(V1，V3)B.(V1，V4)C.(V2，V3)D.(V3，V4 )7 .在以下选项中，无法配置正在搜索的关键字比较序列a.500，200，450，180 b.500，450，200，180c.180，500，200，450 d.180，200，500，4508 .已知字符串s为“abaabaabacacaabaabcc”，模式字符串t为“abaabc”，使用KMP算法进行匹配，首次“不匹配”(si！=ti )的情况下，如果i=j=5，则在下一次开始匹配时，I和j的值分别为A.i=1，j=0B.i=5，j=0C.i=5，j=2D.i=6，j=29 .下列排序算法与元素的移动次数和关键字的初始排序顺序无关a .直接插入排序b .气泡排序c .基数排序d .快速排序10 .已知的小根峰是8、15、10、21、34、16、12，需要在删除关键字8之后重建峰。 在此过程中，关键字之间的比较数A.1 B.2C.3 D.411 .希尔排名的组内排名采用()a .直接插入排序b .半插入排序c .快速排序d .合并排序12 .计算机硬件能够直接运行()I .机械语言程序ii .汇编语言程序iii .硬件描述语言程序仅a.b.c.13.3位二进制补充代码由三个“1”和五个“0”组成，可以表示的最小整数为()A.-126 B.-125 C.-32 D.-314 .在以下有关浮点数加减法的描述中，正确的是()I .不对步进操作产生步进上溢或下溢ii .右标和尾数舍入均可导致步过.左侧规则可能会导致下降iv .尾数溢出的情况下，结果不一定溢出仅a.b .仅c .仅d.15 .主存储器地址为32位，以字节为单位编辑地址，在主存储器块和Cache之间采用直接映射方式，主存储器块的大小为4字，每字为32位，如果采用写回方式，则可以存储4K字的数据A.146k B.147K C.148K D.158K16 .编译器在句子“x=x 3； 中描述的场景，使用下列步骤创建明细表，以便在概念设计中分析体量的外表面积。 xaddt是与x相对应的存储单元的地址，如果执行命令的计算机采用基于页面的虚拟存储管理方案，存在相对应的TLB，并且Cache正在使用写通方案，则至少需要访问主存储器以完成命令功能A.0 B.1 C.2 D.317 .在以下内存中，在运行期间需要定期刷新()A.SRAM B.SDRAM C.ROM D.FLASH18 .一个计算机使用四介质交叉存储器，假设出现在存储器总线上的主存储地址(十进制)序列是8005、8006、8007、8008、8001、8002、8003、8004、8000，则可能发生高速缓存冲突的地址对是()A.8004、8008 B.8002、8007 C.8001、8008D.8000和800419 .在下一次巴士时机的记述中，错误的是()a .在异步通信方式中，完全联动协议最慢b .异步通信方案中，非联动协议的可靠性最差c .按照同步通信方案，同步时钟信号可以提供多个设备d .在半同步通信方式中，握手信号的采样由同步时钟控制20 .磁盘转速为7200转/分钟，平均寻道时间为8ms，每个磁道1000个扇区时，访问1个扇区的平均访问时间约为()a.8.1 msb.12.2 MSC.16.3 MSD.20.5 ms21 .通过中断I/O方式控制打印输出时，CPU和打印控制接口的I/O端口之间交换的信息不可能为()a .打印字符b .主存储地址c .设备状态d .控制命令22 .内部异常(内中断)分为故障(fault )、陷阱(trap )和中止(abort种。 在以下关于内部异常的记述中是错误的()a .内部异常的发生与目前正在执行的命令有关b .内部异常的检测由CPU内部逻辑实现c .内部异常的响应发生在指令执行中d .返回发生内部异常处理异常的指令，继续执行23 .处理外部中断时，操作系统应该保存()a .程序计数器(PC )的内容b .通用寄存器的内容c .块表(TLB )的内容D.Cache的内容24 .假设以下命令已加载到命令寄存器中。 CPU在运行时不可能从用户状态变为内核状态(系统状态()A.DIV R0，R1； (R0)/(R1)R0B.INT n； 发生软中断C.NOT R0； 寄存器R0的内容为非D.MOV R0、addr； 将地址的存储数据保存在寄存器R0中25 .在以下选项中，进程从运行状态变为就绪状态的事件为()执行P(wait )操作b .内存请求失败c .启动I/o设备d。 由高优先级进程断开连接26 .当系统S1采用死锁防止方法时，S2采用死锁检测方法，在以下的记述中正确的为().S1限制用户申请资源的顺序.S1需要所需资源的总量信息，S2不需要.可能导致s 1死锁的进程未分配资源，S2为仅a.b.c.27 .程序分配了四个页面框。 如果进程访问的页码为2，0，2，9，3，4，2，8，2，3，8，4，5，并且进程访问的下一页的页码为7，则此页框必须根据LRU算法丢弃页码()A.2 B.3 C.4 D.828 .在系统存储器中设置磁盘缓冲区的主要目的是()a .减少磁盘I/O次数b .减少平均寻道时间c .提高磁盘数据的可靠性d .实现设备的无关性29 .文件的索引节点上直接有10个索引指针，级别2的索引指针分别有1个，磁盘块的大小为1KB。 每个索引指针占据了4个字节。 如果文件的索引节点已经在存储器中，则将该文件的偏移(按字节地址)为1234和307400的磁盘块读入存储器中。 要访问的磁盘块的数量分别为()a.1，2 b.1，3 c.2，3 d.2，430 .请求分页系统不能将页面分配策略与页面替换策略结合使用()a .可变分配、全局替换b .可变分配、局部替换c .固定分配、全局替换d .固定分配、局部替换二、综合应用问题： 4147小问题，共70分。41 .如果将m个整数保存在单链表中，并且节点结构为(data，link )并且|data|=2)个顶点的相邻矩阵为b，那么Bm(2=m=n )非零元素的含义是什么43.(13分钟)一台16位计算机的主存储器以字节编码。 访问单位为16位。采用16位定长指令格式的CPU采用单总线结构，主要部分如下图所示。 图中的R0R3是通用寄存器，t是堆栈，SR是移位寄存器，可进行直接输送(mov )、左移位1位(left )、右移位1位(right)3等3种操作，控制信号为SRop，Sr的输出信号Srout控制ALU直接为A(mova )、a加可进行B(sub )、a和B(and )、a和B(or )、非A(not )、a +1(Inc )7) 7种操作，控制信号为ALUop。请回答下面的问题。(1)图中哪个寄存器看起来像程序员？ 为什么要设置堆栈t？(2)控制信号ALUop和SRop的比特数至少是多少？(3)控制信号Srout所控制的邮件的名称或者作用是什么？(4)端点中，哪个端点需要与控制部件的输出端连接？(5)为了完善单总线数据路径，需要在端点中在相应的端点之间追加必要的连接。 导出链接的起点和终点，以精确表示数据流的方向。(6)为什么双路选择器MUX的一个输入是2？44.(10分钟)问题43中所描述的计算机在其一些命令运行过程的控制信号如问题44-a所示。标题44图a部分指令控制信号该机器指令格式支持寄存器直接和寄存器间的两种地址方式，如标题44图b所示，地址方式位分别为0和1，通用寄存器R0R3的编号分别为0、1、2和3。标题44图b指令格式请回答下面的问题。(1)该机的指令系统最多可定义几个指令？(2)如果将Inc、shl、sub命令的操作码分别设为01H、02H、03H，则能够利用与以下命令对应的功能器具代码是什么 inc R1； R1 1R1 shl R2、R1； (R1) 1R2 sub R3、(R1 )、R2； (R1) - (R2) R3(3)将寄存器x的输入输出控制信号分别设为Xin和Xout，令其值为1时有效，令其值为0时无效(例如，令PCout=1时，是PC内容分发总线)。 存储器控制信号是MEMop，用于控制存储器的读取(read )和写入(write )的动作。 转录标题44图a中的符号的控制信号或控制信号的取得方法。(4)指令“sub R1，R3，(R2 )”和“inc R1”的执行阶段至