2009年计算机统考真题参考答案
摘要：2009年计算机统考真题参考答案，供考研学子备考使用。
一． 选择题
12345678910
BCDBCBADAB
111213 14 15 16 17 18 19 20
CDDCDCAADB
212223 24 25 26 27 28 29 30
DADDCACBAA
313233 34 35 36 37 38 39 40
BABBCADDCA
二． 综合应用题
41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，
从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。
42. （1）算法基本思想如下：从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。当遍历
到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。
（2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当
前遍历的节点，指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头
节点。用整型变量i表示当前遍历了多少节点，当i>k时，指针p随着每次遍历，也向前移动一个节
点。当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。
（3）算法描述：
Int LocateElement(linklist list,int k)
{ P1=list->link;
P=list;
i=1;
while(P1)
{ P1=P1->link;
i++;
if(i>k)p=p->next; //如果i>k,则p也往后移
}
if(p==list)return 0;//说明链表没有k个结点
else
{
printf(“%d\n“,p->data);
return 1;
}
}
43.（1）在中断方式下，每32位（4B）被中断一次，故每秒中断
0.5MB/4B=0.5×106/4=12.5×104次
要注意的是，这里是数据传输率，所以1MB=106B。因为中断服务程序包含18条指令，中断服务的
其他开销相当于2条指令的执行时间，且执行每条指令平均需5个时钟周期，所以，1秒内用于中断
的时钟周期数为 分页标题#e#
（18+2）×5×12.5×104=12.5×106
（2）在DMA方式下，每秒进行DMA操作
5MB/5000B=5×106/5000=1×103 次因为DMA预处理和后处理的总开销为500个时钟周期，所以1秒
钟之内用于DMA操作的时钟周期数为
500×1×103=5×105
故在DMA方式下，占整个CPU时间的百分比是
（（5×105）/（500×106））×100%=0.1%
44.指令执行阶段每个节拍的功能和有效控制信号如下所示
时钟 功能有效控制信号
C5MAR←(R1)PCout,MARin
C6MDR←M(MAR)MemR,MDRinE
C7A←(R0)R0out,Ain
C8AC←(MDR)+(A) MDRout,Addr,ACin
C9MDR←(AC)ACout,MDRin
C10M(MAR) ←MDR MDRoutE,MemW
45.定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者
之间的同步；mutex控制进程间互斥使用缓冲区。程序如下：
Var s1=0,s2=0,empty=N,mutex=1;
Parbegin
P1:begin
X=produce();
P(empty);
P(mutex);
Put();
If x%2==0
V(s2);
else
V(s1);
V(mutex);
end.
P2:begin
P(s1);
P(mutex);
Getodd();
Countodd():=countodd()+1;
V(mutex);
V(empty);
end.
P3:begin
P(s2)
P(mutex);
Geteven();
Counteven():=counteven()+1;
V(mutex);
V(empty);
end.
Parend.
46.
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。 分页标题#e#
1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。
25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。
（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。
47.
（1）无类IP地址的核心是采用不定长的网络号和主机号，并通过相应的子网掩码来表示（即网络号部分为1，主机号部分为0）。本题中网络地址位数是24，由于IP地址是32位，因此其主机号部分就是8位。因此，子网掩码就是11111111 11111111 11111111 00000000，即255.255.255.0。
根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是2的8次方—2，即254台。
该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件：
X
2的X次方>120,因为根据题意需要容纳120台主机。
X是整数。
解上述方程，得到X=7.子网掩码就是11111111 11111111 11111111 10000000，即255.255.255.128。
所以划分的两个网段是：202.118.1.0/25与202.118.1.128/25。
（2）填写R1的路由表
填写到局域网1的路由。局域网1的网络地址和掩码在问题（1）已经求出来了，为202.118.1.0/25。则R1路由表应填入的网络地址为202.118.1.0，掩码为255.255.255.128。由于局域网1是直接连接到路由器R1的E1口上的，因此，下一跳地址填写直接路由（Direct）。接口填写E1. 填写到局域网2的路由表1。
局域网2的网络地址和掩码在问题（1）中已经求出来了，为202.118.1.128/25。则R1路由表应该填入的网络地址为202.118.1.128，掩码为255.255.255.128.由于局域网2是直接连接到路由器R1的E2口上的，因此，下一跳地址填写直接路由。接口填写E2。 填写到域名服务器的路由。由于域名服务器的IP地址为202.118.3.2，而该地址为主机地址，因此掩码为255.255.255.255。同时，路由器R1要到DNS服务器，就需要通过路由器R2的接口L0才能 到达，因此下一跳地址填写L0的IP地址（202.118.2.2）。
填写互联网路由。本题实质是编写默认路由。默认路由是一种特殊的静态路由，指的是当路由表中与包的目的地址之间没有匹配的表项时路由器能够做出的选择。如果没有默认路由器，那么目的地址在路由表中没有匹配表项的包将被丢弃。默认路由在某些时候非常有效，当存在末梢网络时，默认路由会大大简化路由器的配置，减轻管理员的工作负担，提高网络性能。默认路由叫做“0/0”路由，因为路由的IP地址0.0.0.0，而子网掩码也是0.0.0.0。同时路由器R1连接的网络需要通过路由器R2的L0口才能到达互联网络，因此下一跳地址填写L0的IP为202.118.2.2。 分页标题#e#
综上，填写的路由表如下：
R1路由表
目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.0 255.255.255.0 128 Direct E1
202.118.1.128 255.255.255.128 Direct E2
202.118.3.2 255.255.255.255 202.118.2.2 L0
0.0.0.0 0.0.0.0 202.118.2.2 L0
（3）填写R2到局域网1和局域网2的路由表2。局域网1和局域网2的地址可以聚合为
202.118.1.0/24，而R2去往局域网1和局域网2都是同一条路径。因此，路由表里面只需要填写到
202.118.1.0/24网络的路由即可，如下表所示
R2路由表 目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.0 255.255.255.0 202.118.2.1 L0
页:
[1]