2011年全国硕士研究生入学考试计算机科学与技术入学考试答案及详解
2011年全国硕士研究生入学考试计算机科学与技术入学考试答案及详解一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。请在答题卡上将所选项的字母涂黑。
1．
【答案】A
2．
【答案】B
3．
【答案】B
4．
【答案】C
5．
【答案】C
6．
【答案】D
7．
【答案】A
8．
【答案】C
9．
【答案】B
10．
【答案】A
11．
【答案】B
12．
【答案】D
13．
【答案】A
14．
【答案】B
15．
【答案】D
16．
【答案】A
17．
【答案】C
18．
【答案】D
19．
【答案】C
20．
【答案】C
21．
【答案】D
22．
【答案】C
23．
【答案】B
24．
【答案】A
25．
【答案】D
26．
【答案】B
27．
【答案】D
28．
【答案】D
29．
【答案】A
30．
【答案】B
31．
【答案】B
32．
【答案】C
33．
【答案】A
34．
【答案】B
35．
【答案】B
36．
【答案】D
37．
【答案】D
38．
【答案】C
39．
【答案】C
40．
【答案】B
二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。
41．
【答案解析】此题考察的知识点是图的存储以及关键路径求解的综合知识。
（1）由题可以画出待定上三角矩阵的结构图如下（图中“？”待定元素）
可以看出，第一行至第五行主对角线上方的元素分别5、4、3、2、1个，由此可以画出
压缩存储数组中的元素所属行的情况，如下图所示：
4
6
∞
∞
∞
5
∞
∞
∞
4
3
∞
∞
3
3
第五行
第一行
第二行
第三行
第四行
将个元素填入各行即得邻接矩阵：（2分）
A=
(2)根据第一步所得矩阵A容易做出有向带权图G，如下：（2分）
0
1
2
3
4
5
4
6
5
4
3
3
3
(3)下图中粗线箭头所标识的4个活动组成G的关键路径（3分）
0
1
2
3
4
5
4
6
5
4
3
3
3
由上图容易求得图的关键路径长度为：4+5+4+3=16。
42．
【答案解析】此题考察的知识点是基本算法的灵活运用。
（1）算法的基本设计思想：（5分）
1) 比较笨的方法：
将两升序序列归并排序，然后求其中位数，时间复杂度是O(n)，空间复杂度O(n)。
2) 高效的方法：分别求两个升序序列A和B的中位数，设为a和b。
如果a=b，则a或者b即为所求的中位数。
原因：如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素；排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。
如果a≠b（假设a
原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在（a，b）范围内。因此可以做如下处理：舍弃a所在序列A之中比较小的一半，同时舍弃b所在序列B之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。
（2）算法实现（高效方法）：（8分）
int Search(int A[], int B[], int n)
{
int s1,e1,mid1,s2,e2,mid2;
s1=0;
e1=n-1;
s2=1;
e2=n-1;
while(s1!=e1||s2!=e2)
{
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
if(A==B)
return A;
if(A
{
//分别考虑奇数和偶数，保持两个子数组元素个数相等
if（（s1+e1）%2==0）//若元素个数为奇数
{
s1=mid1;//舍弃A中间点以前部分且保留中间点
e2=mid2; //舍弃B中间点以后部分且保留中间点
}
else//若元素个数为偶数
{
s1=mid1+1;//舍弃A中间点以前部分且保留中间点
e2=mid2; //舍弃B中间点以后部分且保留中间点
}
}
else
{
if((s1+e1)%2==0)//若元素个数为奇数个
{
e1=mid1;//舍弃A中间点以后部分且保留中间点
s2=mid2;//舍弃B中间点以前部分且保留中间点
}
else //若元素个数为偶数个
{
e1=mid1+1；//舍弃A中间点以后部分且保留中间点
s2=mid2；//舍弃B中间点以前部分且保留中间点
}
}
}
return （A
}
(3)上述所给算法的时间、空间复杂度分别是O(log2n)和O(1)。（2分）
因为每次总的元素个数变为原来的一半，所以有：
第一次：元素个数为n/2=n/(21)
第二次：元素个数为n/4=n/(22)
……
……
第k次：元素个数为n/(2k)
最后元素个数为2
则有n/(2k)=2
解得k= log2n – 1
因此：时间复杂度为O(log2n)，而空间复杂度从上述程序中可看出为O(1)。
43．
【答案解析】此题考察的知识点是程序编译运行时各寄存器的运用与变化。
（1）寄存器R1存储的是134，转换成二进制为1000 0110B，即86H。寄存器R5存储的是x－y的内容，x－y=-112，转换成二进制为1001 0000B，即90H。寄存器R6存储的是x+y的内容，x+y=380，转换成二进制为1 0111 1100B（前面的进位舍弃），即7CH。由于计算机字长为8位，所以无符号整数能表示的范围为0~255。而x+y=380，故溢出。
（2）m二进制表示为1000 0110B，由于m是int型，所以最高位为符号位，所以可以得出m的原码为：1111 1010（对1000 0110除符号位取反加1），即-122。同理n的二进制表示为1111 0110B，故n的原码为：1000 1010，转成十进制为-10。所以k1=-122-（-10）=-112.
（3）可以利用同一个加法器及辅助电路实现。因为无符号整数都是以补码形式存储，所以运算规则都是一样的。但是有一点需要考虑，由于无符号整数和有符号整数的表示范围是不一样的，所以需要设置不一样的溢出电路。
（4）带符号整数只有k2会发生溢出。分析：8位带符号整数的补码取值范围为：-128~+127，而k2=m+n=-122-10=-132，超出范围，而k=-112，在范围-128~+127之内。三种方法可以判断溢出：双符号位、最高位进位、符号相同操作数的运算后与原码操作数的符号不同则溢出。
44．
【答案解析】此题考察的知识点是计算机的地址管理。
（1）由于虚拟地址空间大小为16MB，且按字节编址，所以虚拟地址共有24位（224=16M）。由于页面大小为4KB（212=4K），所以虚页号为前12位。由于主存（物理）地址空间大小为1MB，所以物理地址共有20位（220=1M）。由于页内地址12位，所以20-12=8，即前8位为页框号。
（2）由于Cache采用直接映射方式，所以物理地址应划分成3个字段，如下：
12位 3位 5位
主存字块标记
Cache字块标记
字块内地址
分析：由于块大小为32B，所以字块内地址占5位。Cache共8行，故字块标记占3位，所以主存字块标记占20-5-3=12位。
（3）虚拟地址001C60H的虚页号为前12位，即001H=1。查表可知，其有效位为1，故在内存中。虚页号为1对应页框号为04H，故物理地址为04C60H。由于采用的是直接映射方式，所以对应Cache行号为4。尽管有效位为1，但是由于标记位04CH≠064H，故不命中。
（4）由于采用了4路组相联的，所以Cache被分为2组，每组4行。所以物理地址应划分成3个字段，如下：
11位 1位 12位
标记位
组号
页内地址
将024BACH转成二进制为：0000 0010 010 0 1011 1010 1100，可以看出组号为0，标记为0000 0010 010，换成十六进制为0000 0001 0010（高位补一个0），即012H，从图44-c中的0组可以看出，标记为012H页面的页框号为1F，故虚拟地址024BACH所在的页面在主存中。
45.
【答案解析】此题考察的知识点是共享资源的使用与 P、V操作以防止死锁。
Semaphore seets =10;//表示空余座位数量的资源信号量，初值为10
Semaphore mutex = 1; //管理取号机的互斥信号量，初值为1，表示取号机空闲
Semaphore custom = 0; //表示顾客数量的资源信号量，初值为0
Process 顾客
{
P(seets); //找个空座位
P(mutex); //在看看取号机是否空闲
从取号机取号；
V(mutex) //放开那个取号机
V(custom); //取到号，告诉营业员有顾客
等待叫号；
V(seets) //被叫号，离开座位
接受服务；
}
Process 营业员
{
While(true)
{
P(custom); //看看有没有等待的顾客
叫号；
为顾客服务；
}
}
46.
【答案解析】此题考察的知识点是文件系统中数据的组织方式，及文件的查找。
（1）连续更合适。因为一次写入不存在插入问题，而且写入文件之后不需要修改，连续的数据块组织方式很适合一次性写入磁盘不再修改的情况，同时连续存储相对链式和索引省去了指针的空间开销，支持随机查找，查找速度最快。
（2）FCB集中存储较好。FCB存储有文件的很多重要信息，同时是文件目录的重要组成部分，在检索时，通常会访问对应文件的FCB。如果将FCB集中存储，则可以减少在检索过程中产生的访盘次数，提高检索速度。
47．
【答案解析】此题考察的知识点是网络层的ARP协议与路由算法。
解题之前，首先说明图47-b中每行前面的0000、0010、0020等等都不属于以太网帧的内容。
（1） 首先，IP分组是完整的作为MAC帧的数据部分。所以目的IP地址应该在MAC帧的数据里面，如下图所示：
其次，以太网帧首部有14字节，IP数据包首部目的IP地址前有16字节。所以目的IP地址在一台网帧中的位置应该是第31、32、33、34字节。查阅图47-b，找到这四个字节的内容，即40aa6220（十六进制），转换成十进制为：64.170.98.96.32。
从图47-c中可以知道，目的MAC地址就是前6个字节。查阅图47-b，找到这六个字节的内容，即00-21-27-21-51-ee。由于下一跳极为默认网关10.2.128.1，所以所求的目的MAC地址就是默认网关10.2.128.1端口的物理地址。
（2） 本小问考察ARP协议。ARP协议主要用来解决IP地址到MAC地址的映射问题，当源主机知道目的主机的IP地址，而不知道目的主机的MAC地址时，主机的ARP进程就在本以太网上进行广播，此事以太网的目的MAC地址为全1，即ff-ff-ff-ff-ff-ff。
（3） 由于采用的是非流水线方式进行工作，所以客户机在收到前一个请求的响应后才能发送下一个请求。第一个请求用于请求web页面，后续5个JPEG小图像分别需要5次请求，故一共需要6次请求。
（4） 首先，题目中已经说明IP地址10.2.128.100是私有地址。所以经过路由器转发源IP地址是要发生改变的，即变成NAT路由器的一个全球IP地址（一个NAT路由可能不止一个全球IP地址，随机选一个即可，而本题只有一个）。也就是将IP地址10.2.128.100改成101.12.123.15。计算得出，源IP地址字段0a 02 80 64（在第一问的目的IP地址字段往前数4个字节即可）需要改为65 0c 7b 0f。另外，IP分组没经过一个路由器，生存时间都需要减1，结合47-d和47-b可以得到初始生存时间字段为80，经过路由器R之后变为7f，当然还得重新计算首部校验和。最后，如果IP分组的长度超过该链路所要求的最大长度，IP分组报就需要分片，此时IP分组的总长度字段，标志字段，片偏移字段都是需要发生改变的。
页:
[1]