1、计算机专业（基础综合）模拟试卷 63 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 31 所示。若有 8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列( )。（A）2、8、1、4（B） 1、4、8、2（C） 4、2、1、8（D）2、1、4、82 若要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向( )。（A）各自的头结点（B）各自的尾结点（C）各自的第一个元素结点（D）一
2、个表的头结点，另一个表的尾结点3 下列说法正确的是( ) 。用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改将递归算法转换成等价的非递归算法应使用栈图的广度优先搜索使用了栈来实现（A）（B） 、（C） （D）、4 下列关于二叉排序树的说法正确的是( )。向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度二叉排序树一定是平衡二叉树删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树 平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树（A）、IV（B） 、（C） 、（D）全错5 设结点 x 和 y 是二叉树中任意的两个结点，在该二叉树的先
3、序遍历序列中 x 在 y之前，而在其后序遍历序列中 x 在 y 之后，则 x 和 y 的关系是( )。（A）x 是 y 的左兄弟（B） x 是 y 的右兄弟（C） x 是 y 的祖先（D）x 是 y 的子孙6 在常用的描述二叉排序树的存储结构中，关键字值最大的结点( )。（A）左指针一定为空（B）右指针一定为空（C）左右指针均为空（D）左右指针均不为空7 设有无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下面不正确的说法是( )。G为 G 的连通分量 G是 G 的无环子图 G为 G 的极小连通子图，且 V=V（A）、 （B） 、（C）只有 （D）只有8 下列说法正确的是
4、( ) 。当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题广度优先遍历算法可用来求无向图的所有连通分量广度优先遍历算法类似于树中的后序遍历算法（A）仅、（B）仅 、（C）仅 （D）仅、9 关于 Hash 查找说法不正确的有( )个。 采用链地址法解决冲突时，查找一个元素的时间是相同的 采用链地址法解决冲突时，若插入操作规定总是在链首，则插入任一个元素的时间是相同的 用链地址法解决冲突易引起聚集(堆积)现象 再散列法不易产生聚集(堆积)（A）1（B） 2（C） 3（D）410 一组记录的关键字为25，50，15，35，80，85，20，40，36，70 ，其中含有5 个长度为 2
5、的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（A）15，25，35，50，20，40，80，85，36，70（B） 15，25，35，50，80，20，85，40，70，36（C） 15，25，50，35，80，85，20，36，40，70（D）15，25，35，50，80，20，36，40，70，8511 已知有 31 个长度不等的初始归并段，其中 8 段长度为 2；8 段长度为 3；7 段长度为 5；5 段长度为 12：3 段长度为 20(单位均为物理块)。在最佳 5-路归并方案下，则总的读写外存的次数为( )。（A）400（B） 500（C） 600（D）80012 x
6、=-08752 1，y=0 6252 2，设尾数为 3 位，符号位为 1 位，阶码为 2 位，阶符为 1 位，通过补码求出 Z=Xy 的二进制浮点规格化的结果是( )。（A）1011011（B） 0111011（C） 1001011（D）011011113 已知X2 补 =C6H，计算机的机器字长为 8 位二进制数编码，则X4 补 为( )。（A）8CH（B） 18H（C） E3H（D）F1H14 下列( ) 是动态半导体存储器的特点。在工作中存储器内容会产生变化每隔一定时间，需要根据原存内容重新写入一遍一次完整的刷新过程需要占用两个存储周期一次完整的刷新过程只需要占用一个存储周期（A）、（B
7、） 、（C） 、（D）只有15 Cache 常使用的写回策略有写直达法和写回法，则下面关于写直达法和写回法说法正确的是( ) 。写回法是一个 Cache 数据块在任何一次写操作数时都需要写回主存写直达法是一个 Cache 数据块仅在第一次写操作数时才需要写回主存写回法的每个 Cache 块需要设置一位状态位（A）仅、（B）仅 （C）仅 （D）、和16 在 Cache 和主存构成的两级存储器中，Cache 的存储时间是 100ns，主存的存储时间是 1000ns，如果希望有效存储时间不超过 115ns，则 Cache 的命中率至少为( )。（A）90（B） 98（C） 95（D）9917 假设寄
8、存器 R 中的数值为 200，主存地址为 200 和 300 的地址单元中存放的内容分别是 300 和 400，则( )访问到的操作数为 200。直接寻址 200寄存器间接寻址(R)存储器间接寻址(200)寄存器寻址 R（A）仅（B）仅 、（C）仅 、（D）仅18 指令流水线中出现数据相关时流水线将受阻，( )可解决数据相关问题。（A）增加硬件资源（B）采用旁路电路技术（C）采用分支预测技术（D）AC 都可以19 为了便于实现多级中断，保存现场信息最有效的办法是采用( )。（A）通用寄存器（B）堆栈（C）存储器（D）外存20 为确定下一条微指令的地址，通常采用断定方式，其基本思想是( )。（A
9、）用程序计数器(PC)来产生后继微指令地址（B）用微程序计数器(PC)来产生后继微指令地址（C）由微指令的下地址字段直接指出后续微指令地址（D）由专门的硬件电路或者外部直接向 CMAR 输入微指令地址21 在某计算机系统中，各个主设备得到总线使用权的机会基本相等，则该系统采用的总线判优控制方式可能是( )。链式查询方式 计数器定时查询方式 独立请求方式（A）仅（B）仅 、（C）仅 （D）、和22 下列( ) 操作可能会发生中断请求。一条指令执行结束 一次 IO 操作结束 机器内部发生故障 一次 DMA 操作结束（A）、（B） 、（C） 、（D）、23 一台装有 Linux 系统的主机，只有两个
10、账号 root 和 guest，下面关于“Linux 是一个多用户、多任务的操作系统”的理解中，正确的有( )。该主机允许 root 和 guest 同时登录，因为 LinUX 系统支持多用户该主机不允许 root 和 guest 同时登录，因为 Linux 系统最多只能有一个活跃用户该主机允许多个客户端通过 root 账号登录，因为 Linux 系统支持多任务该主机不允许多个客户端通过同一账号登录，因为 Linux 用户只能有一个活跃客户端（A）和（B） 和（C） 和（D）和24 下列关于进程通信的叙述正确的有( )。基于消息队列的通信方式中，复制发送比引用发送效率高从进程通信的角度设计 P
11、CB 应包含的项目，需要有消息队列指针、描述消息队列中消息个数的资源信号量、进程调度信息 进程可以通过共享各自的内存空间来直接共享信息并发进程之间进行通信时，一定共享某些资源（A）、（B） 、（C） 、（D）25 有两个作业 A 和 B，分别在 7：00 和 8：30 到达系统，它们估计的计算时间分别为 08h 和 01h，系统在 9：00 开始以响应比高者优先算法进行调度，请问在单道执行时 A、B 两道作业被选中时的响应比( )。（A）3 和 6（B） 35 和 6（C） 35 和 65（D）3625 和 626 在使用信号量机制实现互斥时，互斥信号量的初值一般为( )：而使用信号量机制实现
12、同步时，同步信号量的初值一般为( )。（A）0；1（B） 1；0（C）不确定；1（D）1；不确定27 利用死锁定理简化下列进程资源图(见图 3-2)，则处于死锁状态的是( )。（A）图 32a（B）图 3-2b（C）图 32a 和图 32b（D）都不处于死锁状态28 用户在段页式存储管理方式下运行一个进程，段表寄存器和段表如图 33 所示(页面大小为 1KB)。 该用户在调试过程中，设计了 3 个地址，试图获取数据，地址如表 3-1 所示：这 3 次获取数据的操作，分别访问内存次数为( )。（A）3、3、3（B） 1、0、3（C） 2、1、3（D）1、2、229 假设系统为某进程分配了 3 个
13、物理块，考虑页面走向为：7，0，1，2，0，3，0，4。试问采用 CLOCK 页面淘汰算法时缺页中断的次数为 ( )。（A）8（B） 7（C） 6（D）530 下列关于文件控制块的错误说法的个数为( )。 文件控制块就是文件目录项 文件控制块是在执行 open(打开) 系统调用时建立的 一个文件可以对应有多个文件控制块 文件控制块通常含有 3 类信息：基本信息、存取控制信息及使用信息（A）1（B） 2（C） 3（D）431 如果当前读写磁头正在 50 号柱面上执行输入输出操作，依次有 4 个等待者分别要访问的柱面号为 37、98、124、65，当采用( )调度算法时下一次读写磁头可能到达 37
14、 号柱面。先来先服务(FCFS)最短寻道时间优先(SSTF)磁头移动方向朝着小磁道方向的电梯调度(SCAN)磁头移动方向朝着大磁道方向的循环扫描算法(CSCAN)（A）（B） 、（C） 、（D）全部都是32 下列技术中属于以空间换时间的是( )。SPOOLing 技术 虚拟存储技术 缓冲技术 通道技术（A）和（B） 和（C） 和（D）全部都是33 下列关于 TCPIP 参考模型的说法正确的是 ( )。（A）明显地区分接口和协议的概念（B）网络层可以提供面向连接的服务（C）不区分物理层和数据链路层（D）TCP IP 参考模型共有 5 层34 TCPIP 中的 IP 层属于 ( )。（A）电路交换
15、（B）分组交换（C）报文交换（D）虚电路交换35 以太网中采用二进制指数后退算法处理冲突问题，下列数据帧中重传时再次发生冲突概率最低的是( ) 。（A）首次重传的帧（B）发生两次冲突的帧（C）发生 3 次冲突的帧（D）发生 4 次冲突的帧36 数据链路层采用后退 N 帧方式进行流量和差错控制，发送方已经发送了编号07 的帧。当计时器超时，只收到了对 1、3 和 5 号帧的确认，发送方需要重传的帧的数目是( ) 。（A）2（B） 4（C） 6（D）837 关于 ICMP 的说法正确的是( )。ICMP 消息的传输是可靠的 ICMP 被封装在 IP 数据报的数据部分 ICMP 可用来进行拥塞控制（
16、A）仅（B）仅 、（C）仅 、（D）仅、38 经 CIDR 路由汇聚后的路由表如表 32 所示。如果该路由器接收到目的地址为172165937 的分组，则路由器( )。（A）将接收到的分组直接传送给目的主机（B）将接收到的分组丢弃（C）将接收到的分组从 SO 接口转发（D）将接收到的分组从 S1 接口转发39 如果主机 A 要向处于同一子网段的主机 B(IP 地址为 172162048916)发送一个分组，那么主机 A 使用的“这个网络上的特定主机”的地址为( )。（A）17216255255（B） 17216204255（C） 00255255（D）002048940 使用 WWW 浏览器浏
17、览网页，用户可用鼠标单击某个超链接，从协议的分析角度看，此浏览器首先要进行( )。（A）IP 地址到 MAC 地址的解析（B）建立 TCP 连接（C）域名到 IP 地址的解析（D）建立会话连接，发出获取某个文件的命令二、综合应用题41-47 小题，共 70 分。41 现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2 ，em) ；i=1；while(所剩边数顶点数)从图中删去 ei；若图不再连通，则恢复 ei；i+；请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举反例说明。41 输入一整数数组5，7 ，6，9，11，10，8 ，该整数序
18、列为图 2-2 所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。要求：42 给出算法的基本设计思想。43 根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出注释。44 说明你所设计算法的时间复杂度。44 一台模型机共有 7 条指令，主频 25MHz，各指令的使用频率与 CPI 如表 2-4 所示。该模型机有 8 位和 16 位两种指令字长，采用 2-4 扩展操作码。8 位字长指令为寄存器-寄存器(R-R) 二地址类型，
19、16 位字长指令为寄存器-存储器(RM)二地址变址寻址类型(-128地址码范围127)，并且使用专门的变址寄存器。试问：45 计算该机的 MIPS。46 计算操作码的平均码长。47 设计该机的两种指令格式，标出各字段位数并给出操作码编码。48 基于(3)，该机允许使用多少个可编址的通用寄存器以及多少个变址寄存器?48 假定一个计算机系统中有一个 TLB 和一个 L1 Data Cache。该系统按字节编址，虚拟地址 16 位，物理地址 12 位，页大小为 128B，TLB 为 4 路组相连，共有 16个页表项，L1 Data Cache 采用直接映射方式，块大小为 4B，共 16 行。在系统运
20、行到某一时刻时，TLB、页表和 L1 Data Cache 中的部分内容如图 2-3 所示。试回答下列问题：49 虚拟地址中哪几位表示虚拟页号?哪几位表示页内偏移量? 虚拟页号中哪几位表示 TLB 标记? 哪几位表示 TLB 索引?50 物理地址中哪几位表示物理页号?哪几位表示页内偏移量?51 主存(物理) 地址如何划分成标记字段、行索引字段和块内地址字段?52 CPU 从地址 067AH 中取出的值为多少?说明 CPU 读取地址 067AH 中内容的过程。53 学生选课最多可以选 3 门，如果王同学选了 3 门 C1、C2、C3 后，想把 C3 换成 C4，王同学就得先退选 C3 再申请选修
21、 C4。但是这个时候可能 C4 已经选满了，而王同学再选回 C3 的时候可能已经被人选满，不能再选了。为了解决这个问题，使用一个函数 TradeCourse(user，course1，course2)将课程 course1 换成 course2。下面给出一种实现。如果不正确，给出所有错误的执行情况，并给出你认为正确的实现，要有适当的注释。TradeCourse(user，course1，course2)course1-p()； 申请课程 coursel 数据结构的互斥信号量course1-drop(user)； 退选课程 course1course2-p()； 申请课程 course2 数据结
22、构的互斥信号量if(course2-isFull()=false) 课程 course2 没有选满course2-add(user)； 申请选修课程 course2course2-v()； 释放课程 course2 数据结构的互斥信号量course1-v()； 释放课程 course1 数据结构的互斥信号量53 下列程序实现了矩阵乘法。int A1 0 01 5 0；int B1502 0 0；int C1 0 02 0 0；for(i=0，inext； 保存 A 表的头结点 A-next=B-neXt-next； B 的开始结点链接到 A 表尾 free(B-next)； 释放 B 表的头结
23、点 B-next=p；/将 B 表的尾结点链接到 A 表的头结点【小技巧】一般出现循环链表的题目时，尾指针的作用总是大于头指针的，因为头指针可通过尾指针直接得到。因此，这样的题目一般都会选择带尾指针的选项。 3 【正确答案】 C【试题解析】 ：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以错误。 ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以正确。 ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以错
24、误。4 【正确答案】 D【试题解析】 ：根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以 I 错误。 lI：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以错误。 ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图 3-7 所示。此时删除结点 3，二叉排序树变为图 37b，再插入结点 3，变为图 3-7c。显然图 3-7a 和图 37c 不是同一个二叉排序树，所以 错误。：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉排序
25、树(出此选项的目的是让大家记住平衡二叉树默认是二叉排序树)，所以错误。 可能疑问点：为什么有些教材定义平衡二叉树还是二叉树，而不是二叉排序树? 提示：首先不管教材是怎么定义的，因为考研大纲没有指定教材，所以考生只能依靠大纲解析为准，如果以前认为平衡二叉树不一定是二叉排序树就把这种思想改变过来吧。 补充知识点：关于二叉排序树、完全二叉树、平衡二叉树、堆之间的关系。 (1)首先堆的建立永远都是从最后开始插，所以堆一定是完全二叉树。 (2)完全二叉树不一定是平衡二叉树，平衡二叉树也不一定是完全二叉树。因为平衡二叉树是有序的，而完全二叉树不一定有序，所以完全二叉树不一定是平衡二叉树。平衡二叉树不一定是
26、完全二叉树比较好理解。5 【正确答案】 C【试题解析】 由于先序遍历是根左右，而后序遍历是左右根，题目中二叉树的先序遍历序列中 x 在 v 之前，而在其后序遍历序列中 x 在 y 之后，则 x 一定是 y 的祖先。 3 种遍历方式的总结，如表 36。6 【正确答案】 B【试题解析】 二叉排序树对于其中任意一个结点都有，其值大于左子树根，小于其右子树根。因此关键字值最大的结点一定是右指针为空。本题选 B。7 【正确答案】 D【试题解析】 一个连通图的生成树是一个极小连通子图(既然是树就肯定无环)，它含有图中全部顶点，所以选项、均为生成树的特点，而选项为概念错误：极大连通子图称为连通分量，G为连通
27、图而非连通分量。8 【正确答案】 A【试题解析】 ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图 38 所示。图中各顶点分布在 3 个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从 13 的层次顺序来遍历各个顶点的，并在遍历的过程中形成了一棵树，称为广度优先搜索生成树。树的分支总是连接不同层上的顶点，如图38 中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以
28、类比为无权图(无权图可理解为各边权值为 1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以正确。 ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以正确。 ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以错误。 综上所述，、正确。 补充：分别使用邻接表、邻接矩阵进行广度、深度优先遍历的时间、空间复杂度的总结。 (1)对于有 n 个顶点 e 条边的图采用邻接表表示时，进行深度优先遍历的时间复杂度是 O(n+e)，空间复杂度是 O(n)。 (2)对于有
29、n 个顶点 e 条边的图采用邻接矩阵表示时，进行深度优先遍历的时间复杂度是O(n2)。 (3)对于有 n 个顶点 e 条边的图采用邻接表表示时，进行广度优先遍历的时间复杂度是 O(n+e)，空间复杂度是 O(n)。 (4)对于有 n 个顶点 e 条边的图采用邻接矩阵表示时，进行广度优先遍历的时间复杂度是 O(n2)。9 【正确答案】 B【试题解析】 如果两个元素在同一链表中，查找时间肯定不相同，故不正确；插入规定在链首的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此正确；所谓聚集(堆积)，即在 Hash 表的建立过程中，某些 Hash 地址是由冲突处理产生的
30、，而不是直接由 Hash 函数直接产生的，这就可能造成原本 Key1 与 Key2 虽然不是同义词，但是最后却得出了相同的 Hash地址。显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此不正确；再散列法即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间，因此正确。 综上，不正确的说法有两个，选 B。10 【正确答案】 A【试题解析】 根据归并算法的思想，对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一。个长度为 2 的有序表，只有 A 满足。 注意：考题经常会给出一个初始序列，然后再给出几
31、个排序的过程序列，问可能是以下哪种排序。这种题型一定要抓住每种排序的本质特征。例如，快速排序第一趟结束后，整个序列会出现以下特点，即在序列中一定存在这样一个元素 a，比 a 大的元素与比 a 小的元素分别出现在 a 的两边，其他的排序就要靠考生自己去总结了。11 【正确答案】 D【试题解析】 固定解题思路： 判断是否需要补充空归并段。如何判断?设度为 O的结点有 n0 个，度为 m 的结点有 nm 个，则对严格 m 叉树有 n0=(m 一 1)nm+1，由此可以得出 nm=(n01) m 一 1。 (1)如果(n 0 一 1)mod(m 一 1)=0，则说明这 n0 个叶子结点(初始归并段)
32、正好可以构造 m 叉归并树。此时，内结点有 nm 个。 (2)如果(n0 一 1)mod(m1)=u0，则说明这 n0 个叶子结点，其中有 u 个结点多余，不能被包含在 m 叉归并树内。为了构造包含所有 n0 个初始归并段的 m 叉归并树，应在原有的 nm 个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的 u 个叶子结点，再加上 mu 一 1 个空归并段，就可以建立归并树。 按照以上步骤：因为(31-1)mod(51)0，所以需要增设空归并段。需要增设 521=2 个空归并段。接下来就比较简单了，仿造赫夫曼树的构造方法，来构造 5-路最佳归并树，
33、如图 39 所示。从图 39 中可以算出(带有方框的结点表示原数据结点)： WPL=(28+38+52)3+(55+125+201)2+202=400 则总的读写外存的次数为： 4002=800。12 【正确答案】 B【试题解析】 浮点数 x 尾数的补码为 1001；浮点数一 y 尾数的补码为1011。因为 x 的阶数为 1，y 的阶数为 2，所以要进行对阶，保留 y 的阶数 2，把x 的尾数右移一位，阶数变为 2(这里要注意，x 是负数，右移的时候是补 1，而不是补 0)。于是，右移后的 x 的尾数为 1100。相加得到1100+1 011=10111，结果出现溢出，需要右规；将其结果右移一
34、位，得到1011，同时阶码加 1 得到 11(对应真值为 3)，最终得到二进制浮点规格化的结果是 0111011。13 【正确答案】 C【试题解析】 对某个数据进行乘 2 运算相当于对该数据二进制数进行不带符号位左移一位的运算，对某个数据进行除 2 运算相当于对该数据二进制数进行不带符号位右移一位的运算。本题中，由于X2=C6H=(11000110) 2，所以求解X 4 补 则需将(11000110) 2 进行不带符号位右移一位的运算，其结果是(11100011) 2=E3H。如果此题是求X 补 ，则需将 (11000110)2 进行不带符号位左移一位的运算，其结果是(10001100)2=8
35、CH。14 【正确答案】 C【试题解析】 动态半导体存储器是利用电容存储电荷的特性记录信息的，由于电容会放电，所以必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍，所以错误，其他的选项请参考下面的补充知识点。 知识点扩展：刷新的总结。刷新其实分为两步：第一步是读取并放大信息，第二步是存入信息，因此将刷新看做信息的再生过程。刷新是按存储器的行来进行的，刷新一行的时间为一个存取周期。这里需要额外解释的是，有人也许认为刷新一次分为两步：读和存，应该占用两个存取周期，但事实上，这里的读并不是把信息读入 CPU，存也不是从 CPU向主存存入信息，它只是把信息读出，通过一个
36、刷新放大器后又重新存回到存储单元里去，而刷新放大器是集成在 RAM 上的。因此，这里只进行了一次访存，也就是占用一个存取周期(这点考生一定要注意，这也是出此题的用意所在)。刷新有以下 3 种方法。(1)集中刷新：在一段时间里，只对所有的行进行刷新，不进行任何访存行为。存在较长的“死时间”。(2)分散刷新：存取周期分为两段，前段用来正常访存，后段用来刷新。因此，存取周期变长，系统速度降低。(3)异步刷新：前两者结合，同一行的两次刷新时间间隔只要不超过电荷流失光的时间即可。在刷新时，类似于 DMA 的周期挪用， “借”一个周期来刷新该行。15 【正确答案】 C【试题解析】 写直达法：是指每次写操作
37、数时既写入 Cache 又写入主存，所以并不是仅在第一次才写回主存，所以错误。 写回法：是写 Cache 时不写入主存，而当 Cache 数据被替换出去时才写回主存，所以会造成写回法的 Cache 中的数据与主存的不一致。为了识别 Cache 中的数据是否与主存中的一致，Cache 中的每一块要增加一个记录信息位，写 Cache 时设置这个位，Cache 数据写回主存时清除这个位。根据这个位的值，Cache 中每一块都有两个状态：清(Clean)和浊(Dirty)，在写 Cache 时状态为“浊”，在数据写回主存时状态为“清”，所以错误，正确。16 【正确答案】 D【试题解析】 假设 Cach
38、e 的命中率为 x，则可以得到一个不等式： 1000(1-x)+100x115 x0983 所以，Cache 命中率 x 至少为 99。17 【正确答案】 D【试题解析】 ：直接寻址(200)中的 200 应该是有效地址，所以访问的内容应该是主存地址为 200 对应的内容，即 300。：寄存器间接寻址(R)和的情况一样，访问的操作数也是 300。：存储器间接寻址(200)表示主存地址 200 所存的单元为有效地址，所以有效地址为 300，访问的操作数是 400。：寄存器寻址 R 表示寄存器 R 的内容即为操作数，所以访问的操作数为200。18 【正确答案】 B【试题解析】 在流水线处理器中处理
39、数据相关问题有两种方法：一种是暂停相关指令的执行，即暂停流水线，直到能够正确读出寄存器操作数为止；另一种是采用旁路电路技术，即采用专门的数据通路，直接把结果送到 ALU 的输入端，也就是把内部数据前推，即不必等待某条指令的执行结果写回到寄存器后，再从寄存器取出结果，而是直接将执行结果通过专用通路送至需要该结果的地方。19 【正确答案】 B【试题解析】 CPU 响应中断时，需要保存当前的一些寄存器中的现场信息，以便在中断结束后进行恢复从而继续执行完毕。在多级中断时，每一层的中断都需要保护中断时的现场信息。例如，一个三级中断，依次需要保护第一、第二、第三级的现场信息，当产生第三级的中断处理程序结束
40、后，首先恢复第三级的现场进行处理，结束后返回第二级以此类推，这样正好符合堆栈的特性，即后进入堆栈的先出来。因此，采用堆栈存储较为有效。 补充：子程序调用指令执行时，也是要把当前程序计数器(PC)的内容送到堆栈保存。20 【正确答案】 C【试题解析】 A：这种方法无法用来控制微程序的执行，因为 PC 的最小控制单位是一条指令，或者说是一个微程序(因为一个微程序解释一条指令)，而微指令是更小的单位。B：该方法为增量计数法。C：该方法直接由下地址字段来指出，也称为断定方式。D：此方式为硬件方式。21 【正确答案】 B【试题解析】 (1)链式查询方式是越靠近总线仲裁机构的主设备优先级越高，且其优先级顺
41、序永远固定不变，所以不可能出现各主设备得到总线使用权机会基本相等的情况，排除 A 和 D 选项。(2)计数器定时查询方式有两种情况，如果计数器永远都是从 0 开始，那么设备的优先级就按 0，1，2，n 的顺序降序排列，而且固定不变；如果计数器是从上一次计数的终止点开始，那么就是一种循环的方法，此时设备使用总线的机会就基本相等了，所以计数器定时查询方式是有可能的。(3)独立请求方式的优先次序是可以通过程序改变的，控制非常灵活，所以肯定存在一种程序使得各个设备使用总线的机会相等。22 【正确答案】 B【试题解析】 ：一条指令执行结束可能会响应中断请求，但是一定不会发生中断请求。：一次 IO 操作结
42、束后，需要通知 CPU 进行下一步的操作，因此需要发送中断请求。：机器内部发生故障，如插件接触不良、通风不良、磁表面损坏、电源掉电等，都会发生不可屏蔽的中断。 ：一次 DMA 操作结束后，需要向 CPU 申请程序中断，标志数据块传送结束。补充：CPU 响应中断必须满足以下 3 个条件。(1)CPU 接收到中断请求信号。(2)CPU 允许中断，即开中断。(3)一条指令执行完毕。23 【正确答案】 A【试题解析】 这里的“账号”等价于“用户”。正确很容易理解，支持多用户，肯定就是支持同时登录。正确，多个客户端通过同一账号登录，这些个客户端其实运行的只是一个进程。Linux 支持多任务的系统，所以肯
43、定是可以的。 知识点扩展： Linux 是一个多用户、多任务的操作系统，考生应该了解单用户多任务和多用户多任务的概念。(1)Linux 的单用户、多任务。 例如，以 beinan 登录系统，进入系统后，要打开 gedit 来写文档，但在写文档的过程中，感觉少点音乐，所以又打开 xmms 来点音乐；当然听点音乐还不行，MSN 还得打开，想知道几个朋友现在正在做什么。这样，在用 beinan 用户登录时，执行了 gedit、xmms 以及 msn 等，还有输入法fcitx。这样说来就有点简单了，一个 beinan 用户，为了完成工作，执行了几个任务；当然 beinan 这个用户，其他的人还能以远程
44、登录过来，也能做其他的工作。 (2)Linux 的多用户、多任务。有时可能是很多用户同时用同一个系统，但并非所有的用户都一定要做同一件事，所以这就有多用户、多任务。 例如，LinuxSir org 服务器，上面有 FTP 用户、系统管理员、Web 用户、常规普通用户等，在同一时刻，可能有人正在访问论坛；有人可能在上传软件包管理子站，如 luma 或 Yuking 在管理他们的主页系统和FTP；与此同时，可能还会有系统管理员在维护系统；浏览主页用的是 nobodv 用户，大家都用同一个，而上传软件包用的是 FTP 用户；管理员对系统的维护或查看，可能用的是普通账号或超级权限 root 账号；不同
45、用户所具有的权限也不同，要完成不同的任务就需要不同的用户，也可以说不同的用户，可能完成的工作也不一样。值得注意的是，多用户、多任务并不是大家同时挤到一起在一台机器的键盘和显示器前来操作机器，多用户可能通过远程登录来进行，比如对服务器的远程控制，只要有用户权限任何人都是可以上去操作或访问的。24 【正确答案】 D【试题解析】 错误，当发送方发送一个较小的数据包时，发送方将数据复制至消息队列，然后接收方从消息队列中复制走，这称为复制发送；如果数据包较大，发送方只是把指向数据包的指针和数据包大小发送给接收者，接收者通过指针访问数据包，这称为引用发送。显然引用发送比复制发送更复杂，但不需要复制数据，所
46、以引用发送效率高。错误，进程调度信息属于进程管理的内容，并非进程通信内容，这里还缺少一个实现消息队列互斥访问的互斥信号量。错误，各个进程有自己的内存空间、数据栈等，所以只能使用进程间通信(Inter Process Communications，IPC)，而不能直接共享信息。需要注意的是，这里的内存空间和进程通信中的共享缓冲区是不一样的。正确，并发进程之间进行通信时，必定存在资源共享问题。进程通信归结为三大类：(1)共享存储器系统，很明显共享了存储器资源。(2)消息传递系统，共享了消息文件。(3)管道通信，共享了管道文件。25 【正确答案】 D【试题解析】 按照响应比的定义：响应比=响应时间要
47、求服务时间=(等待时间+要求服务时间)要求服务时间=1+(等待时间要求服务时间) 在 9：00 时： A 作业的响应比=1+(120 分48分)=35 B 作业的响应比=1+(30 分6 分)=6 因而应选中作业 B 执行，作业 B被选中的响应比为 6，待作业 B 执行结束后再选作业 A 执行，此时 A 的响应比=1+(120+6)48=3625。 本题要注意题目的问法，并不是问在 9：00 时，A、B 作业的响应比，而是 A、B 作业被选中时的响应比。26 【正确答案】 D【试题解析】 同步(直接相互制约关系)：一个进程到达了某些点后，除非另一个进程已经完成了某些操作，否则就不得不停下来等待
48、这些操作的结束，这就是进程的同步，有了同步后进程问就可以相互合作了。用 P、V 操作实现进程同步，信号量的初值应根据具体情况来确定。若期望的消息尚未产生，则对应的初值应设为0；若期望的消息已经存在，则信号量应设为一个非 0 的正整数。互斥(间接相互制约关系)：多个进程都想使用一个临界资源，但是不能同时使用，于是只好一个进程用完了才能给其他进程用，这就是进程互斥。从某种意义上说，互斥是同步的一种特殊情况。一般互斥信号量的初始值都设置为 1，P 操作成功则将其改成 0，V 操作成功将其改成 1，所以互斥信号量的初值为 1。 综上所述，本题选 D。27 【正确答案】 B【试题解析】 在图 3-2a 中，系统中共有 R1 类资源 2 个，R 2 类资源 3 个，在当前状态下仅有一个 R2 类资源空闲。进程 P2 占有一个 R1 类
