白中英《计算机组成原理》（第5版）配套题库【名校考研真题＋课后习题＋章节题库＋

下载地址:http://free.100xuexi.com/Ebook/83271.html
目录                                                                                        封面
内容简介
目录
第一部分　名校考研真题
　2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
　2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
第二部分　课后习题
　第1章　计算机系统概论
　第2章　运算方法和运算器
　第3章　多层次的存储器
　第4章　指令系统
　第5章　中央处理器
　第6章　总线系统
　第7章　外存与I/O设备
　第8章　输入输出系统
　第9章　并行组织与结构
第三部分　章节题库
　第1章　计算机系统概论
　第2章　运算方法和运算器
　第3章　多层次的存储器
　第4章　指令系统
　第5章　中央处理器
　第6章　总线系统
　第7章　外存与I/O设备
　第8章　输入输出系统
　第9章　并行组织与结构
第四部分　模拟试题
　白中英《计算机组成原理》（第5版）模拟试题及答案（一）
　白中英《计算机组成原理》（第5版）模拟试题及答案（二）
                                                                                                                                                                                                    内容简介                                                                                            
　　“十二五”普通高等教育本科国家级规划教材《计算机组成原理》（第5版，白中英主编，科学出版社）是我国高校广泛采用的计算机专业权威教材之一，也被众多高校（包括科研机构）指定为计算机专业考研考博专业课参考书目。
　　为了帮助参加研究生入学考试指定考研参考书目为白中英主编的《计算机组成原理》（第5版）的考生复习专业课，我们根据教材和名校考研真题的命题规律精心编写了白中英《计算机组成原理》（第5版）辅导用书（均提供免费下载，免费升级）：
　　1．[3D电子书]白中英《计算机组成原理》（第5版）笔记和课后习题详解[免费下载，送手机版]
　　2．[3D电子书]白中英《计算机组成原理》（第5版）配套题库【名校考研真题+课后习题+章节题库+模拟试题】[免费下载，送手机版]
　　3．[3D电子书]白中英《计算机组成原理》（第5版）【教材精讲+考研真题解析】讲义与视频课程【30小时高清视频】[免费下载，送手机版]
　　不同一般意义的传统题库，本题库是详解研究生入学考试指定考研参考书目为白中英《计算机组成原理》（第5版）的专业课复习题库，包括名校考研真题、课后习题、章节题库和模拟试题四大部分。具体来说包括以下四部分：
　　第一部分为名校考研真题。精选七套考研真题，每道试题均提供详尽答案解析。学员可以熟悉考试真题的特点，并测试自己的水平。
　　第二部分为课后习题。本部分内容选用白中英《计算机组成原理》（第5版）的全部课后习题，并提供详细答案和解析，由于白中英《计算机组成原理》知识点涵盖广，因此考生可在第一轮复习中通过此部分内容的练习，打好专业课基础。
　　第三部分为章节题库。遵循白中英《计算机组成原理》（第5版）的章目编排，共分为9章，精选详析了部分名校近年的考研真题，同时针对该教材的重难点相应整理了典型题，并对题库中的试题进行详细解析。
　　第四部分为模拟试题。根据历年考研真题的命题规律及热门考点进行押题，其试题数量、试题难度、试题风格与研究生入学考试真题完全一样。通过模拟试题的练习，学员既可以用来检测学习该考试科目的效果，又可以用来评估对自己的应试能力。
　　圣才学习网│计算机类（www.100xuexi.com）提供全国各高校计算机类专业考研考博辅导班【一对一辅导（面授/网授）、网授精讲班等】、多媒体e书、多媒体题库（免费下载，免费升级）、全套资料（历年真题及答案、笔记讲义等）、计算机类国内外经典教材名师讲堂、考研教辅图书等。本题库特别适用于参加研究生入学考试指定考研参考书目为白中英《计算机组成原理》的考生，也可供各大院校学习计算机组成原理的师生参考。
　　与传统图书相比，本书具有以下七大特色：
1．互动学习：摇一摇，找学友，交友学习两不误　　摇一摇，找到学习本书的所有学友，可精确查找学友的具体位置；与学友互动，交流学习（视频、语音等形式），交友学习两不误；学习圈内有学霸解答本书学习中的问题，并配有专职教师指导答疑解惑。

2．720度立体旋转：好用好玩的全新学习体验　　圣才电子书带给你超逼真的3D学习体验，720度立体场景，任意角度旋转，模拟纸质书真实翻页效果，让你学起来爱不释手！

3．手机扫码即可阅读，精彩内容，轻松分享　　圣才电子书扫码即可在手机阅读，随处随学。可以不用客户端不用账号，简单方便！
4．质量保证：每本电子书都经过图书编辑队伍多次反复修改，年年升级　　我们拥有一支强大图书编辑团队，他们专门从事图书的编辑工作，对各类职称考试、考研考博等教材教辅深入研究，以及各类职称考试、考研考博的历年真题进行详尽仔细研究与分析，掌握考试命题的规律和方向，并结合行业最新前沿动态，不断分析整理各个科目的考试要点，把重要考点全部固化为试题形式，形成精准领先及时的备考电子书。同时，依托北京高校资源，我们聘请知名高校众多专家组成顾问团队严格审核圣才电子书，确保质量。
5．免费升级：更新并完善内容，终身免费升级　　如购买本书，可终生使用。免费自动升级指我们一旦对该产品的内容有所修订、完善，系统立即自动提示您免费在线升级您的产品，您将自动获得最新版本的产品内容。真正做到了一次购买，终身使用。当您的电子书出现升级提示时，请选择立即升级。
6．功能强大：记录笔记、答案遮挡等十大功能　　本书具有“知识点串联列举”“划线添加笔记”、“答案自动遮挡”、“全文检索”等功能。
　　（1）知识点串联列举——相同知识点内容列表呈现，便于读者记忆和复习，举一反三，触类旁通。【为考试教辅量身定做】

　　（2）划线添加笔记——使用颜色笔工具，划一条线，写笔记，提交纠错。【圣才电子书独家推出】

　　（3）答案遮挡——先看题后看答案，学习效果好。【圣才电子书独家推出】

　　（4）全文检索——输入关键词，本书相关内容一览无余。【圣才电子书独家推出】

7．多端并用：电脑手机平板等多平台同步使用　　本书一次购买，多端并用，可以在PC端（在线和下载）、手机（安卓和苹果）、平板（安卓和苹果）等多平台同步使用。同一本书，使用不同终端登录，可实现云同步，即更换不同设备所看的电子书页码是一样的。

　　特别说明：本书的部分内容参考了部分网络资料及相关资料。但由于特殊的原因，比如作者姓名或出处在转载之前已经丢失，或者未能及时与作者取得联系等，因而可能没有注明作者的姓名或出处。如果原作者或出版人对本书有任何异议，请与我们联系，我们会在第一时间为您处理！
　　圣才学习网（www.100xuexi.com）是一家为全国各类考试和专业课学习提供辅导方案【保过班、网授班、3D电子书、3D题库】的综合性学习型视频学习网站，拥有近100种考试（含418个考试科目）、194种经典教材（含英语、经济、管理、证券、金融等共16大类），合计近万小时的面授班、网授班课程。
　　如您在购买、使用中有任何疑问，请及时联系我们，我们将竭诚为您服务！
　　全国热线：400-900-8858（8:30-00:30）
　　咨询QQ：4009008858(8:30-00:30)

　　详情访问：http://it.100xuexi.com/（圣才学习网|计算机类）
圣才学习网编辑部
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
第一部分　名校考研真题
2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。
1．已知程序如下：
intS（intn）
{
return（nS（1）->S（0）
B．S（0）->S（1）->main（　　）
C．main（　　）->S（0）->S（1）
D．S（1）->S（0）->main（　　）
【答案】A查看答案
【解析】函数S（intn）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n-1），并将S（n-1）的结果加上n作为返回值。程序从main（　　）函数开始，首先调用main（　　）函数；在main（　　）函数中调用S（1）函数时，将main（　　）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S（0）中，实际参数小于等于零，递归终止。
2．先序序列为a，b，c，d的不同二叉树的个数是（　　）。
A．13
B．14
C．15
D．16
【答案】B查看答案
【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。
3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（　　）。
A．24，10，5和24，10，7
B．24，10，5和24，12，7
C．24，10，10和24，14，11
D．24，10，5和24，14，6
【答案】D查看答案
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B项错误。同理，通过第三个被访问的节点排除A项。C项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C项错误。D项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
4．现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（　　）。
A．根节点的度一定为2
B．树中最小元素一定是叶节点
C．最后插入的元素一定是叶节点
D．树中最大元素一定是无左子树
【答案】D查看答案
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
5．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{，，，}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（　　）。
A．2
B．3
C．4
D．5
【答案】D查看答案
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。


6．暂缺
7．下列选项中，不能构成折半查找中关键字比较序列的是（　　）。
A．500，200，450，180
B．500，450，200，180
C．180，500，200，450
D．180，200，500，450
【答案】A查看答案
【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A项错误，第三次比较的关键字为450，说明待查关键字位于200～450间，所以第四次比较时不会遇到关键字180。
8．已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别是（　　）。
A．i＝1，j＝0
B．i＝5，j＝0
C．i＝5，j＝2
D．i＝6，j＝2
【答案】C查看答案
【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t）本身决定的，即t的子串t[0…j-1]中前缀串和后缀串相等的最长长度。本题中第一次失配i＝5，字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j＝2。
9．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（　　）。
A．直接插入排序
B．起泡排序
C．基数排序
D．快速排序
【答案】C查看答案
【解析】C项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n（n-1）/2次（n为元素个数）。
10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（　　）。
A．1
B．2
C．3
D．4
【答案】C查看答案
【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15，所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。
11．希尔排序的组内排序采用的是（　　）。
A．直接插入排序
B．折半插入排序
C．快速排序
D．归并排序
【答案】A查看答案
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
12．计算机硬件能够直接执行的是（　　）。
Ⅰ．机器语言程序Ⅱ.汇编语言程序Ⅲ.硬件描述语言程序
A．仅Ⅰ
B．仅ⅠⅡ
C．仅ⅠⅢ
D．ⅠⅡⅢ
【答案】A查看答案
【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言，但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。
13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（　　）。
A．-126
B．-125
C．-32
D．-3
【答案】B查看答案
【解析】能表示的最小整数一定是负数，符号位占用1个“1”；负数的补码和原码的转化是：原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码为“11111101”，即-12510。
14．下列有关浮点数加减运算的叙述中，正确的是（　　）。
Ⅰ．对阶操作不会引起阶码上溢或下溢
Ⅱ．右规和尾数舍入都可能引起阶码上溢
Ⅲ．左规时可能引起阶码下溢
Ⅳ．尾数溢出时结果不一定溢出
A．仅ⅡⅢ
B．仅ⅠⅡⅣ
C．仅ⅠⅢⅣ
D．ⅠⅡⅢⅣ
【答案】D查看答案
【解析】浮点数的加减运算步骤包括：①对阶，使两个操作数的小数点位置对齐，阶码小的尾数右移，可能产生溢出，但是阶码不会溢出；②尾数求和，将对阶后的尾数按定点数加（减）运算规则运算；③规格化，包括左规和右规，左规时阶码减少，可能出现阶码下溢，而右规时，阶码增加可能出现阶码上溢；④舍入，该过程可能需要右规调整，因此可能出现阶码上溢；⑤溢出判断，浮点数的溢出与否是由阶码的符号决定的，而不是由尾数溢出判断的，因此尾数溢出时结果不一定溢出。因此ⅠⅡⅢⅣ均正确。
15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack）方式，则能存放4K字数据的Cache的总容量的位数至少是（　　）。
A．146k
B．147K
C．148K
D．158K
【答案】B查看答案
【解析】Cache和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache的一个特定的块中。本题中，Cache总共存放4K字数据，块大小为4个字，因此cache被分为4K/4＝1K个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14＝18位。所以，Cache的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容量为：（4*32 + 18 + 1）*1K＝147K。
16．假定编译器将赋值语句“x＝x+3；”转换为指令”addxaddt，3”，其中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（WriteThrough）方式，则完成该指令功能需要访问主存的次数至少是（　　）。
A．0
B．1
C．2
D．3
【答案】C查看答案
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB的页式虚拟管理方式中，如果给出的地址在TLB中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。
17．下列存储器中，在工作期间需要周期性刷新的是（　　）。
A．SRAM
B．SDRAM
C．ROM
D．FLASH
【答案】B查看答案
【解析】动态随机存储器（DRAM）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持1～2ms，因此即使电源不掉电，信息也会自动消失。为此，每隔一定时间必须刷新。
18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（　　）。
A．8004、8008
B．8002、8007
C．8001、8008
D．8000、8004
【答案】D查看答案
【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。
19．下列有关总线定时的叙述中，错误的是（　　）。
A．异步通信方式中，全互锁协议最慢
B．异步通信方式中，非互锁协议的可靠性最差
C．同步通信方式中，同步时钟信号可由多设备提供
D．半同步通信方式中，握手信号的采样由同步时钟控制
【答案】C查看答案
【解析】A项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
20．若磁盘转速为7200转/分，平均寻道时间为8ms，每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（　　）。
A．8.1ms
B．12.2ms
C．16.3ms
D．20.5ms
【答案】B查看答案
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms，平均等待时间与磁盘转速有关，为[60s/7200]*0.5≈4.165ms。磁盘的存取一个扇区的时间为60s/（7200* 1000）≈ 0.0083ms。因此总的时间为：8 + 4.165 + 0.0083 ＝ 12.1733ms。
21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是（　　）。
A．打印字符
B．主存地址
C．设备状态
D．控制命令
【答案】B查看答案
【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A项为数据，C项为设备状态，D项为命令。B项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU和打印控制接口中的I/O端口之间交换的信息。
22．内部异常（内中断）可分为故障（fault）、陷阱（trap）和终止（abort）三类。下列有关内部异常的叙述中，错误的（　　）。
A．内部异常的产生与当前执行指令相关
B．内部异常的检测由CPU内部逻辑实现
C．内部异常的响应发生在指令执行过程中
D．内部异常处理后返回到发生异常的指令继续执行
【答案】D查看答案
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU自身启动的中断。D项错误，如突然掉电引发的内中断经处理后不会继续执行。
23．处理外部中断时，应该由操作系统保存的是（　　）。
A．程序计数器（PC）的内容
B．通用寄存器的内容
C．快表（TLB）的内容
D．Cache中的内容
【答案】B查看答案
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）；②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
24．假定下列指令已装入指令寄存器。则执行时不可能导致CPU从用户态变为内核态（系统态）的是（　　）。
A．DIVR0，R1；（R0）/（R1）→R0
B．INTn；产生软中断
C．NOTR0；寄存器R0的内容取非
D．MOVR0，addr；把地址处的内存数据放入寄存器R0中
【答案】C查看答案
【解析】A项，除法操作出现除数为零的情况时，会产生内中断，CPU切换为内核态进行中断处理；B项，直接产生中断，会切换到内核态；D项，addr出现非法地址，会出现中断，进而切换到内核态。
25．下列选项中会导致进程从执行态变为就绪态的事件是（　　）。
A．执行P（wait）操作
B．申请内存失败
C．启动I/0设备
D．被高优先级进程抢占
【答案】D查看答案
【解析】D项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC三项，程序由于缺少资源而由执行态转为阻塞态。
26．若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是（　　）。
Ⅰ.S1会限制用户申请资源的顺序
Ⅱ.S1需要进行所需资源总量信息，而S2不需要
Ⅲ.S1不会给可能导致死锁的进程分配资源，S2会
A．仅ⅠⅡ
B．仅ⅡⅢ
C．仅ⅠⅢ
D．ⅠⅡⅢ
【答案】C查看答案
【解析】死锁避免的策略是：必须知道将来的资源需求，以寻找可能的安全允许顺序，如果不存在安全序列就阻塞；死锁检测的策略是：只要允许就分配资源，它指定期检查死锁是否已经发生，如果发生就通过剥夺解除死锁。两种方式都需要所需资源的总量信息，但S1是用于在分配资源时判断是否会导致死锁，而S2是用于检测是否出现死锁。
27．系统为某进程分配了4个页框，该进程已访问的页号序列为2，0，2，9，3，4，2，8，2，3，8，4，5，若进程要访问的下一页的页号为7，依据LRU算法，应淘汰页的页号是（　　）。
A．2
B．3
C．4
D．8
【答案】B查看答案
【解析】LRU置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：　 2 0 2 9 3 4 2 8 2 3 8 4 5
页框：　 2 2 0 0 0 2 9 3 3 4 4 2 3
0 2 2 2 9 3 4 4 8 2 3 8
9 9 3 4 2 8 2 3 8 4
3 4 2 8 2 3 8 4 5
淘汰：　 0　 9 2
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU定义应淘汰的是3。
28．在系统内存中设置磁盘缓冲区的主要目的是（　　）。
A．减少磁盘I/O次数
B．减少平均寻道时间
C．提高磁盘数据可靠性
D．实现设备无关性
【答案】A查看答案
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
29．在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（　　）。
A．1，2
B．1，3
C．2，3
D．2，4
【答案】B查看答案
【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是0～2559，一级索引的偏移量范围是2560～65791，二级索引访问的偏移量范围是65792～45183907。偏移量1234可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在磁盘的位置，需要分别访问存放二级索引的两个索引块以及对应的数据块。
30．在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（　　）。
A．可变分配，全局置换
B．可变分配，局部置换
C．固定分配，全局置换
D．固定分配，局部置换
【答案】C查看答案
【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等），或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。
31～40．暂缺
二、综合应用题：41～47小题，共70分。
41．（9分）用单链表保存m个整数，节点的结构为（data，link），且|data|＜n（n为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
例如若给定的单链表head如下

删除节点后的head为

要求
（1）给出算法的基本思想
（2）使用c或c++语言，给出单链表节点的数据类型定义。
（3）根据设计思想，采用c或c++语言描述算法，关键之处给出注释。
（4）说明所涉及算法的时间复杂度和空间复杂度。
答：（1）算法思想：
定义一个大小为n的布尔数组flag，初始时所有的元素都赋值为false，用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该结点；若为假（false），则将flag位置为真（true）。
（2）节点的数据结构定义如下：

（3）boolflag[n]；　 //全局数组标志节点的绝对值是否出现过
Node* deleteABSEnqualNode（Node * head）
{
memset（flag, false, sizeof（flag））;
Node *pre＝head;
Node *p＝head->next;
while（p !＝NULL）{
if（flag[abs（p->data）]）{//如果此绝对值已经在节点值的绝对值中出现过则删除该节点
　 pre->next＝p->next;
　 deletep;
　 p＝pre->next;
} else {//否则，将flag中对应的位置置为true，并将指针指向下一个元素
flag[abs（p->data）]＝true;
p＝p->next;
}
}
returnhead;
}
（4）只遍历一次链表，所以时间复杂度为O（m）（m为单链表中元素的个数），申请大小为n的数组，所以空间复杂度为O（n）（n为节点绝对值的最大值）。
42．（11分）已知有5个顶点的图G如下图所示

请回答下列问题
（1）写出图G的邻接矩阵A（行、列下标从0开始）。
（2）求A2，矩阵A2中位于0行3列元素值的含义是什么？
（3）若已知具有n（n>＝2）个顶点的邻接矩阵为B，则Bm（22为：

0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。
（3）Bm中非零元素的含义是：假设此顶点位于i行j列，表示从i结点到j结点路径长度为m的路径的条数。。
43．（12分）某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU采用单总线结构，主要部分如下图所示。图中R0～R3为通用寄存器；T为暂存器；SR为移位寄存器，可实现直送（mov）、左移一位（left）、右移一位（right）3种操作，控制信号为Srop，SR的输出信号Srout控制；ALU可实现直送A（mova）、A加B（add）、A减B（sub）、A与B（and）、A或B（or）、非A（not）、A加1（inc）7种操作，控制信号为ALUop。

请回答下列问题。
（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T？
（2）控制信号ALUop和SRop的位数至少各是多少？
（3）控制信号Srout所控制部件的名称或作用是什么？
（4）端点①～⑨中，哪些端点须连接到控制部件的输出端？
（5）为完善单总线数据通路，需要在端点①～⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。
（6）为什么二路选择器MUX的一个输入端是2？
答：（1）图中程序员可见的寄存器有通用寄存器R0～R3和程序计数器PC；当执行算术或逻辑操作时，由于ALU本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU的两个输入端同时有效，因此设置暂存器T用于暂存数据总线发送的数据。
【解析】程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR、MAR和MDR等是CPU的内部工作寄存器，对程序员不可见。
（2）ALUop和SRop的位数分别为3，2。
【解析】ALU中共有7种命令，用三位即可区别表示，SR共有三种命令二位二进制即可表示。
（3）Srout所控制的部件是状态字寄存器，用来存放ALU及CPU的指令状态。
（4）须连接到控制部件的输出端端点有①②③⑤⑧。
【解析】操作符命令，传输等都需要控制信号进行控制。
（5）⑥→⑨，⑦→④。
（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU的第二个操作数。
44．（10分）题43中描述的计算机，其部分指令执行过程的控制信号如如题44图a所示。

题44图a部分指令控制信号
该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0～R3的编号分别为0、1、2和3。

题44图b指令格式
请回答下列问题。
（1）该机的指令系统最多可定义多少条指令？
（2）假定inc、shl和sub指令的操作码分别为01H、02H和03H，则以下指令对应的机器代码各是什么？
①incR1；R1+1→R1
②shlR2，R1；（R1）7条指令。
（2）①0240H，②0464H，③06EEH
【解析】“incR1；”中R1是直接寻址的单地址指令，代码是“0000001001000000”，前面七位是操作码（01H），001是第一个操作数地址（R1）；
“shlR2，R1；（R1）<<1→R2”中R1是间接寻址，R2是直接寻址，代码是“0000010010101000”，前面七位是操作码（02H），010是第一个操作数地址（R2），101是第二个操作数地址；
“subR3，（R1），R2；（（R1））–（R2）→R3”中R1和R2是间接寻址，R3是直接寻址，代码是“000011011101110”，前面七位是操作码（03H），011是第一个操作数地址（R3），101是第二个操作数地址，110是第三个操作数地址。
（3）①0，②mov，③mova，④left，⑤read，⑥sub，⑦mov，⑧Srout。
（4）至少各需要8和1个时钟周期。
【解析】在一个时钟周期内CPU仅完成一个动作。
subR1，R3，（R2）；（R3）–（（R2））→R1执行周期的微操作序列是：
T0：R3→MAR
T1：M（MAR）→MDR
T2：MDR→R3
T3：R2→MAR
T4：M（MAR）→MDR
T5：MDR→MAR
T6：M（MAR）→MDR
T7：R3+MDR→R1
所以至少需要8个时钟周期。
incR1；R1+1→R1执行周期的微操作序列是：
T0：R1+1→R1
所以至少需要1个时钟周期。
45．（15分）有A、B两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中，设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0<x<M），B中有y个（0<y<N）。辩论者每取出一个邮件，邮件数减1.。
A、B两人操作过程：
CodeBegin
A{
While（TRUE）{
从A的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B的信箱；
}
}
B{
While（TRUE）{
从B的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入A的信箱；
}
}
CodeEnd
当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。
当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。
请添加必要的信号量和P、V（或waitsigned）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。
答：首先定义两个互斥信号量：mutexA和mutexB，初始时为1，分别用来实现对A的邮箱和B的邮箱的互斥使用；然后针对A的邮箱再定义两个信号量emptyA和fullA，初值分别为M–x和x，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB和fullB，初值为N–y和y。
初始代码：
SemaphoremutexA＝1，mutexB＝1；
SemaphoreemptyA＝M–x，fullA＝x；
SemaphoreemptyB＝N–y,，fullB＝y；
通信代码：
CodeBegin
A｛
while（TRUE）{
P（fullA）;
P（mutexA）;
从A的信箱中取出一个邮件；
V（mutexA）;
V（emptyA）;
回答问题并提出一个新问题；
P（emptyB）;
P（mutexB）;
将新邮件放入B的信箱；
V（mutexB）;
V（fullB）;
}
}
B{
While（TRUE）{
P（fullB）;
P（mutexB）;
从B的信箱中取出一个邮件；
V（mutexB）;
V（emptyB）;
回答问题并提出一个新问题；
P（emptyA）;
P（mutexA）;
将新邮件放入A的信箱；
V（mutexA）;
V（fullA）;
}
}
CodeEnd
46～47．暂缺

下载地址:http://free.100xuexi.com/Ebook/83271.html