海文专业课模拟试卷
（3）按照改变后的中断屏蔽码，当D1、D2、D3、D4和D5这5个中断源同时请求中断时，处理机响应中断源的中断请求和实际运行中断服务程序过程如下图所示。图中时间轴向下，箭头表示处理过程，没有箭头的垂直线表示响应的过程。
原程序 1级 2级
11. #define CHAIR 6
semaphore customers = 0; semaphore barbers = 0; semaphore S = 1; int waiting = 0; void barber() {while(T) {
P(customers); P(S);
waiting = waiting – 1; V(barbers); V(S); 理发…… } }
void customer() {
P(S);
if(wait < CHAIR) {
waiting = waiting + 1; V(customers); V(S);
P(barbers);
信息咨询： 010-82487377 13701202290
21
3级 4级 5级
选择海文选择成功
坐下等待；
} else {
V(S); }
}
12. 相似处：
13. 信号和中断都采用了相同的异步通信方式；
14. 当检测出有信号或中断请求时，都是暂停正在执行的程序而转去执行相应的处理程序； 两者都是在处理完毕后返回到原来的断点； 对信号或中断都可进行屏蔽； 差异处：
中断有优先级，而信号没有优先级，即所有信号都是平等的；
信号处理程序是在用户态下运行的，而中断处理程序则是在核心态下运行的； 中断响应是及时的，而信号响应通常都有较大的时间延迟.
15. 已知路由器C测得到自己的另连接路由器B、D和E的时延分别等于6、3和5.在收到 来自D的矢量(16,12,6,0,9,10)后，路由器C的路由表如图(一)所示。
路由器C的路由表(一) 站点 A B C 下一跳 D B — 度量 19 6 — 站点 D E F 路由器C的路由表(二) 站点 A B C 下一跳 E B — 度量 12 6 — 站点 D E F 路由器C的路由表(三) 站点 A B C 下一跳 B B — 度量 11 6 — 站点 D E F 下一跳 D E B 度量 3 5 8 下一跳 D E E 度量 3 5 9 下一跳 D E D 度量 3 5 13 自E的矢量(7,6,3,9,0,4)后，路由器C的路由表如下图(二)
在收到来自B的矢量(5,0,8,12,6,2)后，路由器C的路由表如图(三)所示。
http://www.vipkaoyan.com
22
海文专业课模拟试卷
2010年计算机研究生全国统一考试冲刺模拟题（三）答案
16. Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 ① 2 3 ① 3 ① 3 ④ 1 ② 2 ④ 2 ④ 2 ④ 4 ④ 4 ⑤ 1 ⑤ 2 ⑤ 2 ⑥ 4 ⑦ 3 {1,2,4,3,5,6,7,8} {} {1,2,4,3,5,6,7} {8} {1,2,4,3,5,6} {7,8} {1,2,4,3,5} {6,7,8} {1,2,4,3} {5,6,7,8} {1,2,4} {3,5,6,7,8} {1,2} {3,4,5,6,7,8} 4 5 6 7 8 U {1} V-U {2,3,4,5,6,7,8} 17. typedef struct
{ int key; datatype info}RecType
void CountSort(RecType a[],b[],int n) //计数排序算法，将a中记录排序放入b中 { for(i=0;i if(a[j].key b[cnt]=a[i]; } }//Count_Sort (3) 对于有n个记录的表，关键码比较n次。 (4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间；而这种方法比较次数是n2，且需要另一数组空间。 信息咨询： 010-82487377 13701202290 23 2 选择海文选择成功 [算法讨论]因题目要求―针对表中的每个记录，扫描待排序的表一趟‖，所以比较次数是n2次。若限制―对任意两个记录之间应该只进行一次比较‖，则可把以上算法中的比较语句改为： for(i=0;i if(a[i].key 18. 答：（1）5位操作码可表示25=32种不同的指令。 （2）立即数寻址方式只能访问唯一的一个数据； 直接寻址方式用地址码表示存储器地址，8位地址码可以有28=256个数据字； 间接寻址方式用地址码表示地址的存储位置，存储器中16位的地址可以有2=64K种数据地址； 变址寻址方式用地址码表示地址的偏移量，地址在寄存器中，16位变址寄存器和8位偏移量的寻址范围是216+18； 相对寻址方式的寻址范围是PC值附近的字，8位地址偏移量可对PC附近的256个数据字进行寻址。 （3）设地址码位A，各寻址方式的有效地址表达式如下： 立即数寻址：EA=PC 直接寻址：EA=A 间接寻址：EA=（A） 变址地址：EA=Rx+A 相对地址：EA=PC+A 19. 因为虚拟存储系统有40位虚拟地址，32位实际地址，虚页为1M（220），所以主存地址格式为： 31 20 19 0 16 物理页号（12位） 虚拟地址格式为： 39 页内地址（20位） 20 19 0 虚页面号（20位） 页内地址（20位） http://www.vipkaoyan.com 24 海文专业课模拟试卷 （1）页表的字长=物理页号位数12+有效位、保护位、修改位和使用位共4位=16位。页表的单元数=1M（220）。 所以页表大小=1M×16。 （2）页面大小=1M（2）。 （3）虚实地址转换示意图如下图所示。 20. 抖动(Thrashing)就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调 出一页程序或数据送磁盘的对换区中，如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的时间，我们称这种现象为\抖动\ 产生抖动的原因是由于CPU的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导致CPU的利用率下降，而系统的调度程序又会为了提高CPU利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于\抖动\状态. 21. （1）10＋256＋256×256＋256×256×256 （2）7次 （3）6次 20 （4）将w链接到根目录最左端 5次 22. 无线局域网设计了独特的MAC层。MAC层在物理层的上面，包括有两个子 信息咨询： 010-82487377 13701202290 25 选择海文选择成功 层，分别是分布协调功能DCF子层和点协调功能PCF子层。通过协调功能来确定在基本服务集BSS中的移动站发送数据或者接收数据的时间。为了避免碰撞，规定所有的站在完成发送后，必须再等待一段时间才能发送下一帧。 CSMA/CD协议不能用于无线局域网，，主要有下列原因：第一，CSMA/CD协议要求一个站点在发送本站数据的同时还必须不间断地检测信道，以便发现是否有其他的站也在发送数据，这样才能实现―碰撞检测‖的功能，但是在无线局域网的设备中要实现这种功能花费太大；第二，即使能够实现碰撞检测的功能，且当发送数据的时候检测到信道是空闲的，在接收端仍然有可能发生碰撞，表明碰撞检测对于无线局域网没有发挥作用；第三，无线信道还由于传输条件特殊，造成信号强度的动态范围非常大，是发送站无法使用碰撞检测的方法确定是否发生了碰撞。所以，无线局域网不能使用CSMA/CD，而只能使用改进的CSMA/AD协议。 隐蔽站问题：当A和C都检测不到 无线信号时，以为B是空的，向B发送 数据，结果B同时收到A和C发送的数 据，发生碰撞，这就是隐蔽站问题。使用 与帧后，B处在A的传输范围，可以收 到A发送的RTS，当请求允许后，B将会 向其他站点发送CTS。当C收到B的 CTS后，在A和B通信的时间内就不能 发送数据，保证了A和B的正常通信。 暴露站问题：当站B向A发送数据， 而C又想和D通信时，由于C检测到了 媒体上有信号，于是不能向D发送数据。 这就是暴力站问题。使用RTS和CTS 帧后，在A和B通信的时间内C能收到B的RTS，但是收不到A的CTS，所以C可以发送自己的数据给D也不会干扰B。 可以看到通过使用RTS和CTS较好的解决了隐藏站和暴露站的问题。 B C D ·· · A B C · · · A · http://www.vipkaoyan.com 26