文档内容
2009 年计算机学科专业基础综合试题参考答案
一、单项选择题
CBAABD CDCCB DBBAC DDADB CAADA DDBC
1. B 2. 3. 4. 5. 6. 7. 8.
9. A 10. 11. 12. 13. 14. 15. 16.
17. A 18. 19. 20. 21. 22. 23. 24.
25. C 26. 27. 28. 29. 30. 31. 32.
33. B 34. 35. 36. 37. 38. 39. 40.
1. 解析：
缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主
机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数
据则要排队到最后才能打印，显然不符题意，故选B。
2. 解析：
由千队列的特点是先进先出，即栈 S 的出栈顺序就是队 Q 的出队顺序。故本题只需注意栈
的特点是先进后出。出入栈的详细过程见下表。
序号 说明 栈内 栈外 序号 说明 栈内 栈外
1 a入栈 A 8 e入栈 ae bdc
2 b入栈 Ab 9 f入栈 aef bdc
DCDAA
3 b出栈 A b 10 f出栈 ae bdcf
4 c入栈 Ac b 11 e出栈 a bdcfe
5 d入栈 Acd b 12 a出栈 bdcfea
6 d出栈 Ac bd 13 g入栈 g bdcfea
7 c出栈 A bdc 14 g出栈 bdcfeag
栈内的最大深度为 3, 故栈 S 的容量至少是 3。
【另解】元素的出栈顺序是b, d, c, f, e, a, g, 可推出进栈出栈顺序为 Push(S, a), Push(S, b),
Pop(S, b), Push(S, c), Push(S, d), Pop(S, d), Pop(S, c), Push(S, e), Push(S, f), Pop(S, f), Pop(S, e),
Pop(S, a), Push(S, g), Pop(S, g)。假设初始所需容量为 o, 每做一次 Push进行一次 "+1" 操作，
每做一次Pop进行一次 "-1" 操作，记录容量的最大值为 3, 所以选 C。
3. 解析：
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即
遍历的方式是RNL。本题考查的遍历方法并不是二叉树的 3 种基本遍历方法，对于考生而言，
重要的是要掌握遍历的思想。
4. 解析：
根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余 3 个
选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结
点的平衡因子都写出来再进行判断。5. 解析：
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个
满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为 6或7,
显然树高为 7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了
8x2 = 16个叶结点，故完全 二叉树的结点个数最多为(27-1)-16 = 111个结点。
6. 解析：
森林与二叉树的转换规则为 “ 左孩子右兄弟 ” 。在最后生成的二叉树中，父子关系在对应
森林关系中可能是兄弟关系或原本就是父子关系。
情形I: 若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩
子的右孩子，符合要求。
情形II: 结点 u和v 是兄弟结点的关系，但二者之中还有一个兄弟结点k, 则转换后，结
点v就变为结点K的右孩子，而结点k则是结点u的右孩子，符合要求。
喜｀｀。
嘉｀｀
II
情形III: 若结点u的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者
最左父结点的两棵子树中，不可能出现在同一条路径中。
分
图III
【逆向法】由题意可知u是v的父结点的父结点，如下图所示有 4种情况：
根据树与二叉树的转换规则，将这4种情况转换成树种结点的关系。(1)在原来的树中 u是
v的父结点的父结点�； (2)在树中u是v�的父结点；�(3)在树中u�是v的父结点 的兄弟； (4)在树中
u与v是兄弟关系。由此可知 I和II正确。
7. 解析：
每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），
故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-l条边可以构成无向连通图，比如树，
II错误。顶点数为N (N�l)的无向完全图中不存在度为 1的顶点，III错误。
8. 解析：
选项A、B和C都是 B-树的特点，而选项D则是 B+树的特点。注意区别 B-树和B+树各自的特点。
9. 解析：
根据关键字序列得到的小顶堆的二叉树形式如下图所示。
19 15 15 15
22 22 22
(I)
插入关键字3时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，
得到的结果如图(3)所示。所以，调整后的小顶堆序列为3,5, 12, 8, 28, 20, 15, 22, 19。
10. 解析：
解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确
定一个元素的最终位置，而题目中，前2个元素和后2个元素均不是最小或最大的2个元素并
按序排列。选项D中的2路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时
的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，
而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。
11. 解析：
虽然指令和数据都是以二进制形式存放在存储器中，但CPU可以根据指令周期的不同阶段
来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易
误选A, 需要清楚的是，CPU只有在确定取出的是指令之后，才会将其操作码送去译码，因此，
不可能依据译码的结果来区分指令和数据。
12. 解析：
C语言中的整型数据为补码形式，int为32位，short为16位，故x、y转换成十六进制为
0000007FH、FFF7H。执行z=x+y时，由于x是int型，y为short型，需将短字长数据转换成
长字长数据，称之为 “ 符号扩展 ” 。 由于y的符号位为 1, 故在y的前面添加16个 1, 即可将
y上升为int型，其十六进制形式为FFFFFFF7H。最后执行加法，即0000007FH+ FFFFFFF7H =
00000076H, 其中最高位的进位1 自然丢弃。故选D。
【排除法】对于x的值，4个选项都一样，无须计算； z = x + y = 127-9 = 118 > O, 前4个
o,
字节必然全 排除BC; 只需算出y=-9的值即可，其十六进制形式为FFF7H, 排除A。
【提示】解题时，应先排除明显错误的选项，然后再推敲剩下的选项。
13. 解析：
X的浮点数格式为00,111;00,11101 (分号前为阶码，分号后为尾数），Y的浮点数格式为
00,101;00,10100。然后根据浮点数的加法步骤进行运算。
第一步：对阶。X、Y阶码相减，即00, 111-00, 101 = 00, 111+11, 0111 = 00, 010, 可知X
的阶码比Y的价码大2 (这一步可直接目测）。根据小阶向大阶看齐的原则，将Y的阶码加2,
尾数右移2位，将Y变为00,111; 00, 00101。
第二步：尾数相加。即00, 11101 + 00, 00101 = 01, 00010, 尾数相加结果符号位为01, 故
需右规。
第三步：规格化。将尾数右移l位，阶码加1, 得X+Y为01,000; 00, 10001。
第四步：判溢出。阶码符号位为01, 说明发生溢出。c,
本题容易误选选项B、 这是因为选项B、C本身并没有计算错误，只是它们不是最终结
果， 选项 B少了第3步和 第4步，选项C少了第4步。
【偷懒法】本题也可以直接用数学知识对原数进行计算，然后将计算的结果 转换成浮点数
的格式。X+Y = 29/32x27 + 5/8x25 = 29/32x 27 + 5/32x27 = (29/32+5/32)x27 = 34/32x27 =1 7/32x少，
阶码用补码表示，数值位 3位，最大只能表示7, 即X+Y的结果的阶码8超出了该浮点数的
表示范围，故溢出。“
你在做题时想到过这种方法吗？
”
14. 解析：
由于Cache共有16块，采用 2路组相联，因此 共分为8组，组号为0,1, 2, …，7。主存的
某一字块按模8映射到Cache某组的任一字块中，即主存的 第0, 8,1 6, …字块可以映射到Cache
第0组的任一字块中。每个 主存块大小为32字节，故129号单元位于第4块 主存块（注意是从
0开始），因此 将映射到Cache第4组的任一字块中。
15. 解析：
—4Kx8
=
首先确定 ROM的个数，ROM区为4KB, 选用 2Kx8位的ROM芯片，需要 2片，
2Kx8
60Kx8
采用字扩展方式；RAM区为60KB, 选用 4Kx4位的 RAM芯片，需要 =30片，采用字
4Kx4
和位同时扩展方式。
16. 解析：
相对寻址EA=(PC)+A, 首先要求的是取指令后PC的值。转移指令由两个字节组成，每取
一个字节 PC值自动加1,因此取指令后PC值为2000H + 2H = 2002H, 故EA=(PC)+A=2002H +
06H =2008H。
【易错点】本题易误选A或B。选项A没有考虑PC值的自动更新，选项B虽然考虑了PC
值要自动更新，但没有注意到该转移指令是一条两字节指令，PC值仅仅"+I"而不是"+2"。
17. 解析：
相对千CISC, RISC的特点是指令条数少；指令长度固定，指令格式和 寻址种类少；只有
取数I存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU中通用寄存器多；大部
分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。
选项B、C、D都是RISC的特点，选项A是错误的，因为RISC的速度快， 所以普遍采用硬布
线控制器，而非微程序控制器。
18. 解析：
流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确
完成。
19. 解析：
微程序控制器采用了 “ 存储程序 ” 的原理， 每条机器指令对应一个微程序，因此修改
和扩充容易，灵活性好，但每条指令的执行都要访问控制存储器，所以速度慢。硬布线控制
器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩
展困难，灵活性差。
20. 解析：
总线带宽是指单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡
量， 单位Bis。由题意可知，在1个总线周期(=2个时钟周期）内传输了4字节信息，时钟周
期=1110MHz = O.lµs, 故总线带宽为4B/(2xO.Iµs)= 4B/(0.2x10-6s)= 20MB/s。21. 解析：
命中率=Cache命中次数I总访问次数。 需要注意的是看清题，题中说明的是缺失50次，
而不是命中 50次，仔细审题是做对题的第一步。
22. 解析：
外部中断指的是CPU执行指令以外的事件产生的中断，通常是指来自CPU与内存以外的
中断。A中键盘输入属于外部事件，每次键盘输入CPU都需要执行中断以读入输入数据，所以
能引起外部中断。 B中除数为0属于异常，也就是内中断，发生在CPU内部。C中浮点运算下
溢将按机器零处理，不会产生中断。 而D访存缺页属于CPU执行指令时产生的中断，也不属
于外部中断。 所以能产生外部中断的只能是输入设备键盘。
23. 解析：
在单处理机系统（不包含多核的情况）中，同一时刻只能有一个进程占用处理机，因此进
程之间不能并行执行。 通道是独立于CPU的控制输入／输出的设备，两者可以并行，显然，设
备与设备之间也是可以并行的。
24. 解析：
在高响应比优先调度算法中，选出响应比最高的进程投入执行，响应比R定义如下：响应
比R=(等待时间＋执行时间）／执行时间。它综合考虑 了每个进程的等待时间和执行时间，对于
同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量；而长进程的响应比可以
随等待时间的增加而提高，不会产生进程无法调度的情况。
25. 解析：
这种题用到组合数学中鸽巢原理的思想。考虑最极端情况，因为每个进程最多需要 3台打
印机，如果每个进程已经占有了2台打印机，那么只要还有多的打印机，总能满足一个进程达
到3台的条件，然后顺利执行，所以将 8台打印机分给K个进程，每个进程有2台打印机，这
个情况就是极端情况，K为4。
26. 解析：
每个进程都拥有自己独立的进程空间，若一个进程在运行时 所产生的地址在其地址空间之
外，则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检
查是否允许，如果允许则执行，否则产生地址越界中断。
27. 解析：
分段存储管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。 地
址长度为32位，段号占8位，则位移量占32-8= 24位，故最大段长为224B。
28. 解析：
文件的物理结构包括连续、 链式、 索引三种，其中链式结构不能 实现随机访问，连续结构
的文件不易于扩展。 因此随机访问且易于扩展是索引结构的特性。
29. 解析：
SCAN算法类似电梯的工作原理。 首先，当磁头从105道向序号增加的方向移动时，便会
按照从小到大的顺序服务 所有大于105的磁道号(110,170,180,195); 往回移动时又会按照从
大到小的顺序进行服务(68, 45,3 5, 12)。
30. 解析：
“ ”
为了实现 按名存取 ，在文件系统中为每个文件设置用于描述和控制文件的数据结构，
称之为文件控制块(FCB)。在文件控制块中，通常包含以下三类信息，即基本信息、存取控制
信息及使用信息。31. 解析：
建立符号链 接时， 引用计数值直接复制；建立硬链接时， 引用计数值加1。删除文件时，删除
操作 对于符号链接是不可见的， 这并不影响文件系统， 当以后再通过符号链接访问时， 发现文
件 不存在， 直接删除符号链接；但对于硬链接则不可以直接删除， 引用计数值减1, 若值
不为O, 则不能删除此文件， 因为还有其他硬链接指向此文件。
当建立F2时，Fl和F2的引用计数值都为1。当再建立F3时，Fl和F3的引用计数值就
都变成了 2。当后来删除Fl时，F3的引用计数值为2-1 = 1, F2的引用计数值一直不变。
32. 解析：
设备管理具有设备独立性的特点，操作系统以系统调用方式来请求某类设备时， 使用的是
逻辑设备名。而在程序实际执行时， 将逻辑设备名 转换为对应的物理 设备名。
33. 解析：
传输层提供应用进程间的逻辑通信（通过端口号）， 即端到端的通信。 而数据链路层负责
相邻结点之间的通信， 这个结点包括了交换机和路由器等数据通信 设备， 这些设备 不能称为端
系统。网络层负责主机到主机的逻辑通信。因此选B。
34. 解析：
采用 4个相位，每个相位有4种幅度的QAM调制方法，每个信号可以有16种变化，传输
4bit的数据。根据奈奎斯特定理， 信息的最大传输速率为2x3kx4= 24kbps。
35. 解析：
在后退N帧协议中，当 接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续
帧， 发送方超时后需重传该数据帧及其后续的所有帧。这里应注意， 连续ARQ协议中， 接收
方一般采用累积确认的方式， 即接收方 对按序到达的最后一个分组发送确认， 因此本题中收到
3的确认帧就表示编号为0, 1, 2, 3的帧已接收， 而此时发送方未收到1号帧的确认只能代表确
认帧在返回的过程中丢失了，而不代表 1号帧未到达 接收方。因此需要重传的帧为编号是4, 5, 6,
7的帧。
36. 解析：
交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层 使用物理地址进行转发，
而转发到目的地通常是使用 目的地址。因此POU地址是目的物理地址。
37. 解析：
若最短帧长减少， 而数据传输速率不变，则需要 使冲突域的最大距离变 短来实现碰撞窗口
的减少。碰撞窗口是指网络中收发结点间的往返时延， 因此假设需要减少的最小距离为S, 则
可以得到如下公式（注意单位的 转换）：
减少的往返时延＝减少的发送时延， 即 2x[s/(2xl08)] = 800/(lxl09)。即， 由千帧长减少而
缩短的发送时延，应等于由于距离减少而缩短的 传播时延的 2倍。
可得s= 80, 即最远的两个站点之间的距离最少需要减少 80m。
【注意】CSM幻CD的碰撞窗口 = 2倍传播时延，报文发送时间＞＞碰撞窗口。
38. 解析：
返回的确认序列号是接收 端期待收到对方下一个报文段数据部分的第一个字节的序号， 因
此乙在正确接收到两个段后，返回给甲的确认序列号是200+ 300 + 500 = 1000。
39. 解析：
在发生超时后，慢开始门限ssthresh变为16KB/2= 8KB, 拥塞窗口变为1KB。在接下来的
3个RTT内，执行慢开始算法，拥塞窗口大小依次为2KB、4KB、8KB, 由千慢开始门限ssthresh为8KB, 因此之后转而执行拥塞避免算法，即拥塞窗口开始 “ 加法增大” 。因此第4个RTT结
束后，拥塞窗口的大小为9KB。
40. 解析：
对于FTP文件传输，为了保证可靠性，选择TCP协议，排除C、D。FTP的控制信息是带
外传送的，也即FTP使用了一个分离的控制连接来传送命令，故选A。
二、综合应用题
41. 解答：
该方法不一定能（或不能）求得最短路径。(4 分）
举例说明： (6分）
图(1)中，设初始顶点为1, 目标顶点为4, 欲求从顶点1到顶点4之间的最短路径，
显然这两点之间的最短路径长度为2。利用给定方法求得的路径长度为3, 但这条路径并不是
这两点之间的最短路径。
图(2)中，设初始顶点为1, 目标顶点为3, 欲求从顶点1到顶点3之间的最短路径。利
用给定的方法／，无法求二出顶点1到顶点3的路径。
二
(I) (2)
“ ”
【评分说明】CD若考生回答 能求得最短路径 ，无论给出何种证明，均不给分。
＠考生只要举出类似上述的一个反例说明 “ 不能求得最短路径 ” 或答案中体现了 “ 局部
最优不等于全局最优 ” 的思想，均可给6分；若举例说明不完全正确，可酌情给分。
42. 解答：
1)算法的基本设计思想：
问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的
位置。算法的基本设计思想：定义两个指针变量p和q, 初始时均指向头结点的下一个结点（链
表的第一个结点）。p指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同
步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对
链表仅进行一遍扫描。
2)算法的详细实现步骤：
CDc ount= O, p和q指向链表表头结点的下一个结点；
＠若p为空，转@;
＠若count等于k , 则q指向下一个结点；否则，count= count + 1;
®p指向下一个结点，转＠；
© 若count等于k, 则查找成功，输出该结点的data域的值，返回1; 否则，说明K值超
过了线性表的长度，查找失败，返回 0;
＠算法结束。
3)算法实现：
typedef int Elem.Type; ／／链表数据的类型定义
typedef struct LNode{ II链表结点的结构定义
ElemType . data; ／／结点数据
struct Lnode *link; ／／结点链接指针) *LinkList;
in七 Search k(LinkList list,int k) [
／／查找链表list倒数第k个结点，并输出该结点data域的值
LinkList p=list->link,q=lis七一>link; //指针p、q指示第一个结点
int count�O; .
while (p ! =NULL} { II遍历链表直到最后一个结点
if(countlink;p=p->link; ／／之后让p、q同步移动
} .//while
if(countdata};
return l;
} //Search_k
提示：算法程序题，如果能够写出数据结构类型定义， 正确的算法思想都会至少给 一半以
上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。
【评分说明】＠若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若
采用两遍或多遍扫描才能得到正确结果的，最高给10分；若采用递归算法得到正确结果的，最
高给10分；若实现算法的空间复杂度过高（使用了大小与K有关的辅助数组），但结果正确，
最高给10分；若实现的算法的空间复杂度过高（使用了大小与K有关的辅助数组），但结果正
确，最高给10分。
＠若在算法基本思想描述和算法步骤描述中因文字表达没有非常清晰地反映出算法的思
路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照O的标准给分。
＠若考生的答案中算法基本思想描述、 算法步骤描述或算法实现中部分正确，可酌情
给分。
43. 解答：
1)按题意，外设每秒传送0.5MB, 中断时每次传送4B。中断方式下，CPU每次用于数据
传送的时钟周期为5x18+ 5x2= 1 00。(2分）
为达到外设0.5MB/s的数据传输率，外设每秒申请的中断次数为0.5MB/4B =1 25000。
(1分）
ls内用于中断的开销为lOOx125000 =1 2500000 =1 2.5M个时钟周期。(1分）
CPU用于外设1/0的时间占整个CPU时间的百分比为12.5M/500M = 2.5%。(1分）
2)当外设数据传输率提高到5MB/s时，改用DMA方式传送，每次DMA传送5000B,ls
内需产生的DMA次数为5MB/5000B =1 000。(1分）
CPU用于DMA处理的总开销为lOOOx 500 = 500000 = 0.5M个时钟周期。(1分）
CPU用于外设1/0的时间占整个CPU时间的百分比为0.5M/500M = 01. %。(1分）
【评分说明】如果考生只给出正确的计算结果，未给出计算过程， 每个给2分。
44. 解答：
题干己给出取值和译码阶段每个节拍的功能和有效控制信号，我们应以弄清楚取指阶段中
数据通路的信息流动作为突破口，读懂每个节拍的功能和有效控制信号。然后应用到解题思路
中， 包括划分执行步骤、 确定完成的功能、 需要的控制信号。
先分析题干中提供的示例（本部分解题时不做要求）：取指令的功能是根据PC的内容所指主存 地址，取出指令代码，经过MDR, 最终送至IR。
这部分和后面的指令执行阶段的取操作数、存运算结果的方法是相通的。
Cl: (PC)--MAR
在读 写存储器前， 必须先将地址（这里为(PC))送至M凡{。
C2: M(MAR尸MDR, (PC) + 1--PC
读 写的数据必须经过MDR, 指令取出后PC自增1。
C3: (MDR)--IR
然后将读到MDR中指令代码送至IR进行后续操作。
指令"ADD(Rl), RO"的操作数一个在主存中，一个在寄存器中， 运算结果在主存中。根
据指令功能，要读出 Rl的内容所指的主存单元，必须先将Rl的内容送至MAR,即(Rl)--M凡L
而读出的数据必须经过MDR, 即M(M凡l)--MDR。
因此， 将Rl的内容所指主存单元的数据读出到MDR的节拍安排如下：
C5: (Rl)--MAR
C6: M(MAR尸MDR
ALU一端是寄存器A, MDR或RO中必须有一个先写入A中， 如MDR。
C7: (MDR)--A
然后执行加法操作， 并将结果送入寄存器AC。
CS: (A)+ (RO)--AC
之后将加法结果写回到Rl的内容所指主存单元，注意MAR中的内容没有改变。
C9: (AC)--MDR
ClO: (MDR)--M(MAR)
有效控制信号的安排并不难，只需看数据是流入还是流出， 如流入寄存器X就是Xin, 流
出 寄存器X就是Xout。还需注意其他特殊控制信号， 如PC+1、Add等。
千是得到参考答案如下：
时钟 功能 有效控制信号
cs
MAR-(Rl) RI out,M ARin
C6 MDR-M(MAR) MemR, MDRinE
C7 A-(MDR) MDRout,Ain
cs
AC-(A)+(RO) ROout, Add,A Cin
C9 MDR一(AC) ACout,M DRin
CIO M(MAR)-(MDR) MDRoutE,M emW
本题答案不唯一， 如果在C6 执行M(MAR)-MDR的同时，完成(RO)-A (即选择将(RO)
写入A), 并不会发生总线冲突， 这种方案可节省l个节拍，见下表。
时钟 功能 有效控制信号
cs
MAR-(Rl) Rlout, MARin
C6 MDR一M(MAR), A-(RO) MemR,M DRinE, ROout, Ain
C7 AC-(MDR)+(A) MDRout, Add, ACin
C8 MDR-(AC) ACout,MDRin
C9 M(MAR) (MDR) MDRoutE,M emW
气45. 解答：
互斥资源：缓冲区只能互斥访问，因此设置互斥信号噩mutex。
同步问题：P 1、P2因为奇数的放置与取用而同步，设同步信号量odd; P
1
、P
3
因为偶数的
放置与取用而同步，设置同步信号量even; P1、P、P 因为共享缓冲区，设同步信号量empty,
2 3
初值为N。程序如下：
semaphore mutex=l;
semaphore odd=O,even=O;
semaphore empty=N;
main()
cobegin{
Process Pl()
while(True)
｛
x=produce(); II生成一个数
P (empty); II判断缓冲区是否有空单元
P (mutex); ／／缓冲区是否被占用
Put() ;
V (mutex); II释放缓冲区
if (x%2==0)
V (even); ／／如果是偶数，向P3发出信号
else
V( odd); II如果是奇数，向P2发出信号
Process P2 ()
while(True)
｛
P (odd); II收到Pl发来的信号，已产生一个奇数
P(mu七ex); ／／缓冲区是否被占用
getodd();
V (mutex); II释放缓冲区
V (empty); II向Pl发信号，多出一个空单元
countodd();
Process P3 ()
while( True)
｛
P(even); II收到Pl发来的信号，已产生一个偶数
P(mutext); II缓冲区是否被占用
geteven();
V(mutex); II释放缓 冲 区
V (empty); ／／向Pl发信号，多出一个空单元
counteven( );
}coend
46. 解答：
1)根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面
大小为4KB, 即i2, 则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的
页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，
最高位为页号）：2362H: P = 2, 访问快表lOns, 因初始为空， 访问页表lOOns得到页框号，合成物理地址
后访问主存lOOns, 共计lOns + lOOns + lOOns = 2l Ons。
1565H: P = 1, 访问快表lOsn , 落空，访问页表lOOns落空， 进行缺页中断处理108 ns, 访
问快表lOns, 合成物理地址后访问主存lOOns, 共计lOns + lOOns + 108 ns + 1 Ons + lOOns =
100000220 sn 。
25A5H: P=2, 访问快表， 因第一次访问已将该页号放入快表， 因此花费lOns便可合成物
理地址， 访问主存lOOns, 共计lOns + lOOns =l lOns。
2)当访问虚地址1565H时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，
根
的
据
物
题
理
目
地
的
址
置
为
换
1 0
算
1 5
法
6 5
，
H
应
。
淘 汰 0 号 页 面 ， 因 此 1 5 6 5 H 的 对 应 页 框 号 为 1 0 1 H 。 由 此 可 得 1 5 6 5 H
47. 解答：
1) CIDR 中的子网号可以全0或全1, 但主机号不能全0或全l。
因此若将IP地址空间202.118.1.0/24划分为2个子网，且每个局域网需分配的IP地址个数
不少于120个， 子网号至少要占用一位。
由26-2 < 120 < 27-2 可知， 主机号至少要占用7 位。
由于源IP地址空间的网络前缀为24 位， 因此主机号位数＋子网号位数 =8。
综上可得主机号位数为7, 子网号位数为1。
因此子网的划分结果为子网1: 202.118.1 .0/25, 子网2: 202.118.1.128/25。
地址分配方案：子网1分配给局域网1, 子网2分配给局域网2;或子网1分配给局域网2,
子网2分配给局域网l。
2)由于局域网1和局域网2分别与路由器Rl的El、E2 接口直接相连， 因此在Rl的
路由表中， 目的网络为局域网l的转发路径是直接通过接口El转发的， 目的网络为局域网
2 的转发路径是直接通过接口El转发的。 由于局域网l、2 的网络前缀均为25 位， 因此它
们的子网掩码均为255.255.255.128。
Rl专门为域名服务器设定了一个特定的路由表项， 因此该路由表项中的子网掩码应为
255.255.255.255 (只有和全l的子网掩码相与才能完全保证和目的IP地址一样， 从而选择该特
定 路 由 。） 对 应 的 下 一 跳 转 发 地 址 是 2 0 2 1. 1 8 2. 2. , 转 发 接 口 是 L O。
Rl到互联网的路由实质上相当于一个默认路由， 默认路由一般写为0/0, 即目的地址为
0.0.0.0, 子网掩码为0.0.0.0。 对应的下一跳转发地址是202.118.2.2, 转发接口是L。O
综上可得到路由器Rl的路由表如下。
若子网1分配给局域网1, 子网2分配给局域网2, 见下表。
目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.0 255.255.255.128 El
202.1 I 8.1.128 255.255.255.128 E2
202.118.3.2 255.255.255.255 202.118.2.2 LO
0.0.0.0 0.0.0.0 202.118.2.2 LO
若子网1分配给局域网2, 子网2分配给局域网1, 见下表。
目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.128 255.255.255.128 El
202.118.1.0 255.255.255.128 E2
202.118.3.2 255.255.255.255 202.118.2.2 LO
0.0.0.0 0.0.0.0 202.118.2.2 LO3)局域网1和局域网2的地址可以聚合为202.118.1.0/24, 而对于路由器R2来说，通往局
域网l和局域网2的转发路径都是从LO接口转发， 因此采用路由聚合技术后，路由器R2到局
域网1和局域网2的路由， 见下表。
目的网络IP地址 子网s掩码 下一跳IP地址 接口
202.118.1.0 255.255.255.0 202.118.2.1 LO
