您现在的位置： 考博信息网 >> 文章中心 >> 考研复习 >> 考研政治 >> 正文 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个，由此可以画出

压缩存储数组中的元素所属行的情况，如下图所示：

将个元素填入各行即得邻接矩阵：（2分）

A=

(2)根据第一步所得矩阵A容易做出有向带权图G，如下：（2分）

(3)下图中粗线箭头所标识的4个活动组成G的关键路径（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<b），中位数只能出现在（a，b）范围内。

     原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…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[mid1]==B[mid2])

             return A[mid1];

             if(A[mid1]<B[mid2])

               {

                      //分别考虑奇数和偶数，保持两个子数组元素个数相等

                      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[s1]<B[s2] ? A[s1]:B[s2]）;

}

(3)上述所给算法的时间、空间复杂度分别是O(log₂n)和O(1)。（2分）

   因为每次总的元素个数变为原来的一半，所以有：

   第一次：元素个数为n/2=n/(2¹)

第二次：元素个数为n/4=n/(2²)

……

……

第k次：元素个数为n/(2^k)

最后元素个数为2

则有n/(2^k)=2

解得k= log₂n – 1

因此：时间复杂度为O(log₂n)，而空间复杂度从上述程序中可看出为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位（2²⁴=16M）。由于页面大小为4KB（2¹²=4K），所以虚页号为前12位。由于主存（物理）地址空间大小为1MB，所以物理地址共有20位（2²⁰=1M）。由于页内地址12位，所以20-12=8，即前8位为页框号。

      （2）由于Cache采用直接映射方式，所以物理地址应划分成3个字段，如下：

               12位               3位                     5位

分析：由于块大小为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分组的总长度字段，标志字段，片偏移字段都是需要发生改变的。