2023年硕士研究生入学考试计算机统考试题参考答案.doc

全国研究生研究生入学考试计算机统考试题参照答案
　　一、单选题：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<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(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分组的总长度字段，标志字段，片偏移字段都是需要发生变化的。