计算机学科专业基础考研综合模拟试题及详细解析

1、第 第 页对于实时操作系统而言，处理机效率一般不作为其设计目标 铁路信号系统、门禁系统和股票交易系统都需要实时操作系统支持 A、B、C只有D只有24以下服务中，能发挥多线程系统的特长的是（利用线程并发地执行矩阵乘法运算服务器利用线程请求 HTTP 服务 键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入 基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作 A、B、C、D、25现在有 3 个同时到达的作业 J1、J2 和 J3，它们的执行时间分别为 T1、T2 和T3，且 T1T2T3。如果该系统中有两个 CPU，各自按照单道方式运行且采用短作业优

2、先算法，则平 均周转时间是（ （1+T2+3）/3（21+T2+3）/3（T1+2T2+3）/3D（2T1+2+T3）3 或（T1+2T2+3）26对计数型信号量 S 执行 V 操作后，下列选项错误的是（当 S.value0时，唤醒一个阻塞队列进程只有当 S.value0 时，唤醒一个阻塞队列进程 当 S.value0 时，唤醒一个就绪队列进程 只有当 S.valuefront 和 rearfront 时，队列中元素个数为rear-front=(rear-front+m)%m因为0rear-frontm，所以rear-front+m 与m 取余后结果还是rear-front。（2）当 rear

3、front 时，队列中元素个数为m-（front-rear）=rear-front+m=（rear-front+m)%m因为0rear-front+mm，所以rear-front+m 与m 取余后结果还是rear-front+m。 选项正确。 知识点总结：循环队列的两大状态和两大操作以及三大重点提醒。（1）两大状态（数学式子表示） 1）队空状态：q.rear=q.front。 （2）两大操作1）元素x q.rear=(q.rear+1)%MAX； q.dataq.rear=x；2）元素x q.front=(qu.front+1)%MAX； x=q.dataq.front；重点提醒 1：有些教材

4、说循环队列队尾指针指向队尾元素，有些教材说循环队列队尾指针 指向队尾元素的下一个元素。不同的说法可能导致很多题目的答案总是相差 1。所以如果在考 研试卷中碰到，且题目没有说明（不过像考研试卷一般都会说明），一律认为是循环队列队尾 指针指向队尾元素的下一个元素。重点提醒 2：元素入队时，先移动指针，后存入元素；元素出队时，也是先移动指针，再 取出元素。有些书上可能有不同的顺序，其实本质是一样的，考生只需去适应一种写法，对于程序设计题目已经足够。对于选择题，则可根据题目描述确定是先存取元素，再移动指针，还 是其他处理顺序。重点提醒 3：循环队列的队尾指针、队头指针、队中元素个数，知道其中任何两者均

5、可算 出第三者。4B。 ：的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目的时候一定要先想到这种特殊情况，所以错误。 ：二叉树的左右子树是有顺序的，不能随意交换，所以正确。 ：一般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用顺序结构存储，所以错误。 ：该结论只对完全二叉树才成立，所以错误。 综上所述，只有正确。5C。每个非叶子结点的平衡因子均为 0，说明了该平衡二叉树为满二叉树，所以结点总数为 2k-1。总结（1）设Nh 表示深度为h 的平衡二叉树中含有的最少结点数，则N0=0，N1=1，N2=2， L ，Nh=Nh1+Nh2+1例如，深度为 5 的平衡二

6、叉树中含有最少的结点数为N5=12。（2）二叉排序树的查找效率取决于其深度。对于结点个数相同的二叉排序树，平衡二叉树的深度最小，因此效率最高。6D。赫夫曼树中只有度为0 或2 的结点，由D 选项可以画出对应的二叉树，如图1-7 所示。图 1-7 D选项对应的二叉树由赫夫曼树的性质可知，树中不应该含度为 1 的结点，因此D 选项不可能。7A。 最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一定相等，故错误；既然最小生成树不唯一，并且最小生成树的边都为 n-1 条，说明图 G 的边 数一定会大于 G 的权值最小的边的条数没有任何关系， 故错误。8A。 有两种方法可以判

7、断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个顶点v dfs(v)结束之前出现一条从顶点j 到v j 在生成树上是v 的子 孙，则图中必定存在包含 v 和 j 次要删去一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环， 因此正确。而最短路径和关键路径（建立在无环的 AOE 网的基础之上）都是不可以判断的。补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图一定有什么？想必 90%以上的考生都会选择有环，但是没有环这个选项，只有顶 点数目大于 1 的强连通分量这个选项，此时考生必须知道顶点数目大于 1 的强连通分量就表

8、明 有环。9D。 可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线如图 1-8所示。图 1-8 查找路线图A 选项中 28 的右子树中出现了小于它的18，不满足二叉排序树规定，排除。 B 选项中 36 的左子树中出现了大于它的 46，不满足二叉排序树规定，排除。 C 选项中 28 的左子树中出现了大于它的36，不满足二叉排序树规定，排除。补充：在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于折 半查找的时间复杂度，即 O(log2n)。平衡二叉树的查找效率最高，因为二叉树的查找效率取决于二叉树的高度，对于结点个数相同的

9、二叉树，平衡二叉树的高度最小。10B。直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为 n-1（n 简单选择排序：每趟排序都是选出一个最小（或最大）的元素，所以排序趟数固定为 n-1（n为元素数。交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。 为组成元素的关键字位数。综上所述，、都是无关的，所以选B。 11C。A：影响外排序时间的主要因素就是内存与外设交换信息的总次数，所以 A 错误。B：外部排序也是在内存上进行排序，只不过需要分为多步而已，所以 B 错误。 C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以 C 正确。 补充知识点：败者树和堆有什么区别？

10、解析：外排序中败者树和堆排序的区别在于：（1）败者树是在双亲结点中记下刚进行完的这场比赛的败者，而让胜者去参加更加高一层 的比赛，便可得到一棵败者树。而堆排序可看做一种胜者树，即双亲结点表示其左右孩子中的 胜者。n 个关键字全部为叶子结点，双亲即为其左、右子女的败者， 败者树中结点总数为 2n-1，加上冠军结点恰好为 2n。而堆是由n 个关键字组成的完全二叉树， 每个关键字作为树中一个结点，根是 n 个关键字中的胜者，树中结点总数为n。D：使用置换-选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的 过程也可以得到答案，所以 D错误。外排序的基本过程： 基于磁盘进行的排序多使用

11、归并排序方法。其排序过程主要分为两个阶段：（1）建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内 排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中。（2）按归并树模式，把（1）生成的初始归并段加以归并，一趟趟扩大归并段和减少归并 段数，直到最后归并成一个大归并段为止。例如：设有一个包含 4500 个记录的输入文件，现用一台其内存至多可容纳 750个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳 250 个记录，这样全部 记录可存储在 4500/250=18 个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中

12、可用于排序的存储区域能容纳 750 个记录，所以内存中恰好能存3 个块的记录。在外排序一开始，把 18 块记录每 3块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到 6 个初始归并段。然后一趟一趟进行归并排序，如图 1-9所示。图 1-9 归并排序12B。图中实线框为CPU，而CPU 包含五大部件中的运算器和控制器，排除C 选项。控制器为 计算机提供工作统一的时钟及其发出各种控制命令来协调计算机的各部件自动地工作，所以控 制器应该与其他四大部件相连，可得为运算器，为控制器。最后，根据数据的流向可以判 断，为输入设备，为输出设备。剩下为存储器。13D。由于“a

13、”的 ASCII 码值为 61H，而“g”是第 7 个字母，所以可以得到“g”的ASCII 码 值应为61H +6=67H=1100111B。现在“g”的ASCII 码值中有5 应该在最高位上添加一个 1，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进 制数为 14A。 本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统管理中，逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为 8644 除以4096，取整为2，取余为452。页号为2，查页表得物理块号为8。因此，a 的有效地址为 84096+452=33220。15D。 对于选项：首先，ROM和R

14、AM都是采用随机存取方式。由于EPROM属于ROM，故采用随机存取方式。而CD-ROM属于光盘，为非随机存储，故错误。 对于选项：SRAM采用双稳态触发器来记忆信息，因此不需要刷新；而DRAM采用电容存储电荷的原理来存储信息，只能维持很短的时间，因此需要刷新，故错误。 对于选项：Cache需要有信息的输入和输出，而ROM只可读，不可输入，因此不能作为Cache，故错误。16D。Flash 存储器是一种具有较高存储容量、较低价格、非易失性、可在线擦除与编程的新一 代读写存储器。从基本工作原理上看，Flash 存储器属于 ROM 型存储器，但由于它又可以随时 ash 存储器与其他存储器的区别总结（

15、见表1-6。表 1-6 Flash 存储器与其他存储器区别内存类型非易失性高密度可写Flash 存储器是是是SRAM不是不是是DRAM不是是是ROM是是不是EPROM是是不是EEPROM是不是是17A。首先可以计算出操作码字段的长度为 16-5-5=6。所以一共可以定义26=64 地址指令占了60 条，且是定长操作码，故单地址指令最多可以有64-60=4 条，所以选A。如果此题将条件改为采用不定长操作码，答案又是什么？分析如下： 如果采用不定长（扩展）操作码，每条二地址指令可扩展为 32 条单地址指令，那么单地址指令最多有 324=128条。18A。 指令情况，认为不一定总是根据 PC 读出。

16、实际上，正确的执行顺序是这样的，当前指令正在执行时，其实 PC 已经是下一条指令的地址了，如果遇到了无条件转移指令，则只需要简单地 把跳转的地址覆盖PC 19C。 ：外部事件是可以提出中断请求的，如可以通过敲击键盘来终止现在正在运行的程序，这个就可以看做一个中断，所以可以。：Cache 是属于存储设备，不能提出中断请求，所以不可以。 、：浮点运算下溢，可以当做机器零处理，不需要中断来处理；而浮点运算上溢，必须中断来做相应的处理，所以不可以，可以。20D。24 位图像是典型的JPG 各占8 3B。未经压缩的图片大小=160012003B5.5MB，128MB/5.5MB=23.3，所以内置的存储

17、空间最多可存储 23 张照片。21D。PCI 总线与 CPU 及时钟频率都无关，故错误；PCI总线支持即插即用并且可对数据和 地址进行奇偶校验，并且 PCI 总线采用猝发传送方式，故正确；主设备指获得总线控制权 的设备，所以 PCI 设备不一定都是主设备，故错误；系统中肯定允许有多条PCI 总线，以 此来提升计算机的效率，故正确。22D。A：在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的地址码来区分的；在 独立编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的，所以A 错误。B：除主机外的硬件装置统称为外围设备或外部设备，包括输入、输出设备和外存储器， 所以B

18、 错误。C：中断隐指令并不是一条真正的指令，因此不可能把它预先编入程序中，只能在响应中 断时由硬件直接控制执行，它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断 隐指令不在指令系统中，不属于程序控制指令，所以 C错误。补充：在中断周期中，由中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及硬件关中断的操作。D：为了防止在恢复现场过程中又出现新的中断，在恢复现场前需要增加关中断操作，所 以D 正确。提醒：请注意区分，保护现场前的关中断由中断隐指令完成，但是恢复现场前的关中断是 由中断服务程序完成。23C。 正确。在分时操作系统中，响应时间跟时间片和用户数成正比。响应时间：从提交第

19、一个请求到产生第一个响应所用时间。在 RR 算法中，用户作业时间 片结束后，就认为产生了第一个响应。错误。操作系统具有主存的共享性，因此每个用户拥有的主存空间大小是由用户程序的 大小决定的。 牺牲效率也是必然的。正确。铁路信号系统需要实时调度车辆，延时会出事故；门禁系统需要及时响应用户的 进入请求；股票交易系统需要当前的实时行情，上述应用均要求使用实时操作系统。综上所述，本题选C。24D。在多线程操作系统中，通常一个进程中包括多个线程，每个线程都是作为利用 CPU 的基 本单位，是花费最小开销的实体。线程具有下述属性：（1）轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的，即能

20、保证 独立运行的资源。它包含了一个线程 ID、一个程序计数器、一个寄存器组和一个堆栈。（2）独立调度和分派的基本单位。（3）可并发执行。（4）共享进程资源。在同一进程中的各个线程，都可以共享该进程所拥有的资源，包括共 享代码段、数据段以及其他的操作系统资源（如打开的文件）等。多线程最大的优点就是并发执行。在 4 个服务中，只有键盘操作是无法并发执行的，因为 整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处 理整个系统的键盘操作，所以选择D。25B。J1、J2 和J3 同时在0 时刻到达，按短作业优先算法，选择J1 和J2 执行，则J1 和J2 等待 时间为0。

21、又因为T1T2，所以J1 先于J2 完成，即在 时刻，释放CPU，J3 开始，则J3 的 等待时间为T1。然后J2 完成，最后J3 完成。J1 周转时间为T1。 J2 周转时间为T2。J3 周转时间为 T1+T3。 所以平均周转时间为（2T1+T2+T3）/3。知识点回顾：周转时间=等待时间+运行时间=结束时间-到达时间26B。 提醒：计数型信号量就是记录型信号量，不要被这个搞混了。 V V 操作之前 S.value 的绝对值就是阻塞队列中进程的个数，所以阻塞队列必有进程在等到，所以需要唤醒一个阻塞队列的进程。错误。由的分析可知，S.value0 就会唤醒。因为可能在执行 V 操作前，只有一个

22、进 程在阻塞队列，也就是说 S.value=-1，执行 V 操作后，唤醒该阻塞进程，S.value=0。和错误。S.value 的值和就绪队列中的进程没有此层关系，所以全错。 综上所述，本题选B。27C。对于逻辑地址结构，因为 8 页=23 页，所以表示页号的地址有 3 位，又因为每页有1024B= 210B，所以页内偏移地址有 10 位。因此总共逻辑地址有13 位。对于物理地址结构，因为页面的大小和物理块的大小是一样的，所以每个物理块也是 1024B，而内存至少有 32 块物理块，所以内存大小至少是 321024B=215B。因此物理地址至少 要 15位，不然无法访问内存的所有区域。28D。

23、每页1KB，默认字长为1B，那么页内地址需要10 位，则剩下的6 位为虚页号。计算过程 如表 1-7所示。表 1-7 十六进制虚地址及物理地址十六进制虚地址0A5C1A5C二进制虚地址0000 1010 0101 11000001 1010 0101 1100二进制虚页号0000 100001 10二进制物理页号0001 00缺页中断二进制页内地址10 0101 1100二进制物理地址0001 0010 0101 1100十六进制物理地址125C29B。 正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入和换出过程，可提高 CPU 利用率。 错误。因为系统实际已处于频繁的换入

24、和换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量无用。正确。因为从给定的条件中磁盘交换区的利用率为 99.7%，说明系统现在已经处于频繁 的换入和换出过程中，可减少主存中的程序。错误。系统处于频繁的换入和换出过程中，再增加主存中的用户进程数，只能导致系统 的换入和换出更频繁，使性能更差。错误。因为系统现在处于频繁的换入和换出过程中，即使采用更快的磁盘交换区，其换 入和换出频率也不会改变，因此没用。错误。系统处于频繁的换入和换出过程中，CPU 处于空闲状态，利用率不高，提高CPU的速度无济于事。 综上所述，本题选B。 30D。图 1-10 所示为文件系统模型。可将该模型分为3

25、个层次，其最底 层是对象及其属性；中间层是对对象进行操纵和管理的软件集合；最 高层是文件系统提供给用户的接口。其中对对象操纵和管理的软件集合这个层次，是文件系统的核心 部分。文件系统的功能大多是在这一层实现的，其中包括：对文件存 储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物 所以 A选项是错误的。图 1-10 文件系统模型在多级目录结构中，从根目录到任何数据文件，都只有一条唯一的路径。在该路径上从树 的根（即主目录）开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构成该数 据文件的路径名。系统中的每个文件都有唯一的路径名。所以 B 选项的说法是不准确的。对文件的访问

26、只需要通过路径名即可。对于C 所以 C选项错误。D 选项正确。基于文件系统的概念，可以把数据组成分为数据项、记录和文件 3 级。记录 是一组相关数据项的集合，用于描述一个对象在某方面的属性。记录是文件存取的基本单位， 数据项是文件可使用的最小单位。31A。在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2。当数据从控制器 传送至内存后，磁头开始读数据时，刚好转到目标扇区。所以总时间为总时间=初始寻找 0 扇区时间+读扇区总时间+将扇区数据送入内存总时间 由题中条件可知，旋转速度为：3000 转/分=50 转/秒，即 20ms/转。 读一个扇区需要时间：20/8ms=2.5ms读一

27、个扇区并将扇区数据送入内存需要时间：2.53ms=7.5ms读出一个磁道上的所有扇区需要时间：20/2ms+87.5ms=70ms=0.07s每磁道数据量为 数据传输速度为8512B=4KB4KB/0.07s=57.1KB/s所以依次读出一个磁道上的所有扇区需要 0.07s，其数据传输速度为 57.1KB/s。 32A。单缓冲工作示意图和时序图如图 1-11 I/O 控制器到缓冲区 和数据由缓冲区到工作区必须串行操作；同样，数据从缓冲区到工作区和 CPU 从工作区中取 出数据进行处理也需串行进行；但由于在顺序访问时可采用预先读的方式，即 CPU 在处理一 块数据（从工作区取数据）的同时可从磁盘

28、输入下一块数据，所以系统对一块数据的处理时间 为max(T,C)+M。图 单缓冲工作示意图与时序图双缓冲的工作示意图和时序图如图 1-12 I/O 控制器到双缓冲和数 据由双缓冲区到工作区可以并行工作，因此，系统对一块数据的处理时间为 max(T,M+C)。33A。 从计算机网络组成的角度来看，典型的计算机网络从逻辑功能上可以分为两部分：资源子网和通信子网。 资源子网：由主计算机系统、终端、终端控制器、联网外部设备、各种软件资源与信息资通信子网（包括物理层、数据链路层、网络层）：由通信控制处理机、通信线路与其他通信设备组成，完成网络数据传输、转发等通信处理任务。图 1-12 双缓冲工作示意图与

29、时序图综上所述，网桥、交换机、路由器都属于通信子网，而只有计算机软件属于资源子网。34A。CM 代表Puse Code Moduaion（脉冲编码调制。补充：PCM 通常用在电话系统中对模拟数据进行采样。一般都把 PCM 采样时间设置成125s，125s 的采样时间对应于每秒 8000 次采样。一个典型的电话通道是 4kHz，根据奈奎斯特定理，为获取在一个4kHz 通道中的全部信息 需要每秒 8000 次的采样频率。128=27，每个采样表示 7 个二进制位。80007bit/s=56000bit/s= 56kbit/s。35B。 发送窗口的后沿的变化情况只能有两种：（1）原地不动（没有收到新

30、的确认。 发送窗口不可能向后移动，因为不可能撤销已收到的确认帧。 36B。流就是 Internet 上从特定主机的源站到特定的目的站的单播或组播数据分组，所经过的路 径上的路由器都能保证指定的服务质量。头部中的源地址、目的地址和流标号字段唯一地标识 了一个流。37D。 需要分两种情况，分析如下：第一种：假设计算机 A 和计算机 B 在同一个局域网内，那么应该由计算机 B 使用ARP 响 应分组将计算机 B 的硬件地址告诉计算机A。第二种：假设计算机 A 和计算机 B 不在同一个局域网内，则应该由连接本网络的路由器 使用 ARP 响应分组将自己的硬件地址告诉计算机A。综上所述，由谁通过 ARP

31、响应分组回应是不确定的。38C。在该网络上共有 50 个路由器，因此每个路由器的路由表大小为 6850bit=2400bit。在基 于距离-向量的路由选择算法中，每个路由器都定期地与所有相邻的路由器交换整个路由表， 并以此更新自己的路由表项。由于每个路由器每秒与自己的每个邻接路由器交换 1 次路由表， 一条链路连接两个路由器，所以每秒在一条链路上交换的数据为 22400bit=4800bit，即由于更 新路由信息而耗费的带宽为 4800bit/s。39B。在慢启动和拥塞避免算法中，拥塞窗口初始值为 1，窗口大小开始按指数增长。当拥塞窗 口大于慢启动门限后，停止使用慢启动算法，改用拥塞避免算法。

32、此时，慢启动的门限值初始 为8，当拥塞窗口增大到8 时改用拥塞避免算法，窗口大小按线性增长，每次增长1 个报文段。 当增加到 12 时，出现超时，重新设置门限值为 6（12 1，执行 慢启动算法，到门限值为 6 时执行拥塞避免算法。按照上面的算法，拥塞窗口的变化为1、2、4、8、9、10、11、12、1、2、4、6、7、8、9L ，从该序列可以看出，第 12 次传输时拥塞窗 口大小为6。注意：在以上的序列中，6 被加粗，原因是很多考生直接从4 增加到8，导致误选D 选项。原因是拥塞窗口的大小是与门限值有关的，在慢开始算法中不能直接变化为大于门限值，所以4 只能最多增加到6，之后再执行拥塞避免算

33、法。40A。FTP 使用两条 TCP 连接完成文件传输，一条是控制连接，另一条是数据连接，所以 C 选 FTP 中，控制连接在整个用户会话期间一直打开着，而数据连接有可能为每次文件 传送请求重新打开一次，即数据连接是非持久的，而控制连接是持久的，所以 A 选项错误，B 选项正确；D 选项显然正确。二、综合应用题41【答案要点】首先解答此题需要很清楚地知道 B-树的基本定义，这个就不再一一列举了，参考教材即 可。另外，B-树插入和删除的详细过程也请参考教材，以下的讲解只是大概地描述几个较为关 键的步骤。（1）插入 33：第一步需要定位，33 应该被插入 35 和 41 的那个叶子结点。由于该叶子

34、结 点没有了空位置（怎么检测是否有空位置？m 阶 B-树最多只能有 m-1 进行分裂操作。插入后的情况应该是 35、41、33，那么怎么分裂？首先需要取一个新结点，把 原结点上的关键字按照升序排列，即 33、35、41。从中间位置（即 m/2 之处）把关键字（不 包括中间位置的关键字）分成两部分，左部分所含的关键字放在旧结点中，右边所含的关键字 放在新结点中，中间位置的关键字连同新结点的存储位置插入到双亲结点中，如图 1-13 所示。如果双亲结点的关键字个数也超过分支数减 1，则要再分裂，再往上插，直至这个过程传 到根结点为止。从以上步骤可以得出插入 33 之后的 B-树，如图1-14 所示。

35、图 1-13图 1-14 插入 33 后的 B-树可能疑问点：结点下面的小方块都是什么？ 解析：小方块就是叶子结点，因为叶子结点本身不带有信息，所以有些教材都不画出来，但是叶子结点这一层是一定要计入树的高度。另外，叶子结点一般也被认为外部结点（类似于 折半查找判定树的外部结点）或是查找失败的结点。插入 97：过程与上面的一样，最终结果如图1-15 所示。图1-15 插入33 和97 后的B-树（2）B-树的删除过程与插入过程类似，只是稍微复杂一些。因为要使删除后的结点中的关 键字个数m/2-1，这就将涉及结点的“合并”问题。删除 66：首先需要根据 B-树的查找算法找到关键字所在的结点，然后在

36、该结点上删除关 键字，具体详细过程参考教材。找到 66 所在的结点之后，发现删除之后关键字个数不满足m/2 -1，所以需要像兄弟结点借，但是兄弟结点只有一个关键字 97，借不了。那么唯一的办 法就是把当初和它们分裂出去的关键字找回来，即 88。但是，88 找回来之后（也就是双亲结 -1，只有继续找更早以前被分裂出去的 60，最后的结果如图 1-16 所示。图 1-16 删除 66 后的 B-树42【答案要点】（1）基本设计思想：算法的策略是从数组的第一个元素位置和最后一个元素位置向数组的 中部进行遍历。因此我们可以定义两个变量，将它们当作下标来遍历数组，第一个下标一开始指向数组第一个元素，它只

37、向后移动，第二个下标一开始指向数组最后一个元素，它只向前移 动。在两个下标相遇之前，第一个下标总是位于第二个下标的前面。如果第一个下标指向的元 素是偶数而第二个下标指向的元素是奇数，我们就交换这两个元素。void ReorderOddEven(int a,n)void ReorderOddEven(int a,n)int left=0;int right=n-1; int temp; while(leftright)if(aleft%2!=0)left+; continue;if(aright%2=0)right-;/定义指向数组第一个元素的下标变量/定义指向数组最后一个元素的下标变量/元素交

38、换的中间变量/当两个下标相遇后才结束循环/如果left指向的元素是奇数，则left下标向后移动一位/如果right指向的元素是偶数，则right下标向左移动一位第23页（共32 continue;continue;/交换元素 temp=aleft; aleft=aright; aright=temp;/交换完成后，两边的下标各移动一位 left+;right-;（3）时间复杂度分析：整个算法过程相当于把数组遍历了一遍，所以时间复杂度为 O(n)。空间复杂度分析：算法中只需要使用 temp 这一个临时变量，所以空间复杂度为一常数，表示 为O(1)。43【答案要点】（1）对于时间局部性来说：在程序

39、段 A、B 和C 中，每个数组元素都只被访问一次，所以都没有时间局部性。 对于空间局部性来说：程序段 A 访问顺序和存放顺序一致，所以空间局部性好。 程序段 B访问顺序和存放顺序不一致，所以空间局部性不好。程序段 C 虽然访问顺序和存放顺序一致，但同一个主存块有两次访问，所以空间局部性不 （2）Cache 的行数为 512B/32B=16；数组首地址为 0000 0C80H，因为 0000 0C80H 正好是 主存第 1100100B（100）块的起始地址，所以数组从主存第 100 块开始存放，一个数组元素占 44B=16B，每两个数组元素占用一个主存块。88 的数组共占用 32 个主存块，正

40、好是 Cache 数据区大小的两倍。因为 100 mod 16=4，所以主存第 100 块映射到的 Cache 行号为4。主存中 的数组元素与 Cache 行的映射关系如图1-19 所示。（3）对于程序段 A：每两个数组元素（共涉及 8 次写操作）装入到一个 Cache行中，总是第一次访问时未命中，后面7 次都命中，所以总的写Cache操作次数为644=256次，写Cache不命中次数为2561/8=32 次，因而写Cache 缺失率为12.5%。对于程序段 B：每两个数组元素（共涉及 8 次写操作）装入到一个 Cache行中，但总是只有一个数组元素（涉及 4 次写操作）在被淘汰之前被访问，并

41、且总是第一次不命中，后面 3 次 命中，所以写Cache 不命中次数为2561/4=64 次，因而写Cache 缺失率为25%。第24页（共32 对于程序段 C：第一个循环共 64 次访问，每次装入两个数组元素，第一次不命中，第二 次命中；第二个循环共访问 643 次，每两个数组元素（共涉及 6 Cache 行中，并且总是第一次不命中，后面 5 次命中，所以总的写 Cache 不命中次数为 32+(364)1/6=64 次，因而写 Cache 缺失率为25%。图 1-19 主存中的数组元素与 Cache行的映射关系44【答案要点】（1由于该微型计算机的寻址范围为64K所以地址线有16 根PU

42、外接了8KB的RM13 3 根地址线恰好可以被用来对8 片RAM 芯片进行片选。片选电路逻辑图如图 1-20所示。（2）第0 片地址范围（片选信号为000：000 0000000000000000 （0000H1FFFH）第1 片地址范围（片选信号为001（2000H3FFFH）第2 片地址范围（片选信号为010（4000H5FFFH）第3 片地址范围（片选信号为01 （6000H7FFFH）第4 片地址范围（片选信号为100图 1-20 片选电路逻辑图第25页（共32 （8000H9FFFH）第5 片地址范围（片选信号为101（A000HBFFFH）第6 片地址范围（片选信号为10 （C00

43、0HDFFFH）第7 片地址范围（片选信号为1（E000HFFFFH）3 片的片选信号始终为低电平， 即无论选哪片 RAM，与此同时第3 片都会同时被选中。（4）因为片选信号是低电平有效，说明 000 端输出始终为高电平，所以导致以0000H 为起 始地址的存储芯片不能读写。（5）第 片RAM 的片选信号分别为：001、011、101、111，唯一的共性就是地 址线A13 都为1，说明地址线A13 始终为0 导致故障。45【答案要点】本题还是一个生产者-消费者的变型，与 2009 年真题不同之处在于，2009 年真题是一个生 产者，对应两个消费者；本题是生产者-消费生产者-消费者类型，其实质是

44、两个生产者-消费者 是生产者，M 是对应消费者，同时 M 也充当生产者，P 是对应的消费者。把这些进程 间的关系理清楚，是解题的基础。本题的缓冲区 B可描述为char bufferBn;（1）缓冲区是一互斥资源，因此设互斥信号量mutex。（2）上述进程的同步问题，需设置 3 个信号量，其中 empty 对应空闲的缓冲单元，初值为 n；full_1 对应缓冲区中待 M 处理的字符，初值为 0；full_2 对应缓冲区中已经处理过而待打印 输出的字符，初值为 0。另外，还需定义 3 个整型变量 in、out_1、out_2，分别用来指示下一 个可存放字符的缓冲单元、下一个待 M 处理的缓冲单元及

45、下一个待打印输出的缓冲单元，它 们的初值均为0。过程如下：charchar bufferBnsemaphore empty=n; semaphore full_1=0; semaphore full_2=0; semaphore mutex=1; int in=0;int out_1=0;/缓冲区字符数组/空闲缓冲单元数/待 M处理的字符数/待 P取出打印字符数/缓冲区的互斥访问信号量/指示可存放字符的缓冲单元/指示下一个待 M处理的缓冲单元第26页（共32 int out_2=0;/指示下一个待 P取出打印的缓冲单元R()char ch; while(1)从输入设备读取一个字符到 ch中;P

46、(empty);/检查缓冲区是否有可以存放新读入字符的缓冲单元 P(mutex);/申请访问缓冲区bufferBin=ch;/存放新读入字符的缓冲单元 V(mutex);/释放缓冲区V(full_1);/待 M处理的字符数增1 in=(in+1)%n;/in指针后移，遇末循环到0单元M()/读者可参照R()自行写出注释while(1)P(full_1); P(mutex);if(bufferBout_1= ) bufferout_1=;V(mutex); V(full_2); out_1=(out_1+1)%n;P()/读者可参照R()自行写出注释char ch while(1)P(full_

47、2); P(mutex); ch=bufferBout_2;第27页（共32 V(mutex);V(mutex);V(empty); out_2=(out_2+1)%n;将字符 ch打印输出;说明：同步和互斥的解题思路为（1）分清哪些是互斥题（互斥访问临界资源，哪些是同步题（具有前后执行序 要求的。（2）对互斥问题要设置互斥信号量，不管具有互斥关系的进程有几个或几类，通常都只设 置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。（3）对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关， 即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进 程是否已经结束。（4）在每个进程中用于实现互斥的 PV 操作必须成对出现；用于实现同步的 PV 操作也必 须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的 P