2021全国硕士研究生招生考试计算机学科专业基础试题
一、单项选择题
第01~40小题,每小题2分,共80分。下列每题给出的四个选项中,只有一个选项最符合试题要求。
01.
D
02.已知初始为空的队列Q的一端仅能进行入队操作,另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5,则不能得到的出队序列是()。
D
03.已知二维数组A按行优先方式存储,每个元素占用1个存储单元。若元素A[0][0]的存储地址是100,A[3][3]的存储地址是220,则元素A[5][5]的存储地址是()。
B
二维数组A按行优先存储,每个元素占用1个存储单元,由A[O][0]和A[3][3]的存储地址可知A[3][3]是二维数组A中的第121个元素,假设二维数组A的每行有n个元素,则n×3+4=121,求得n=39,故元素A[5][5]的存储地址为100+39×5+6-1=300,故选B。
二维数组A按行优先存储,每个元素占用1个存储单元,由A[O][0]和A[3][3]的存储地址可知A[3][3]是二维数组A中的第121个元素,假设二维数组A的每行有n个元素,则n×3+4=121,求得n=39,故元素A[5][5]的存储地址为100+39×5+6-1=300,故选B。
04.某森林F对应的二叉树为T,若T的先序遍历序列是a,b,d,c,e,g,f,中序遍历序列是b,d, a,e,g,c,f,则F中树的棵数是()。
C
05.若某二叉树有5个叶结点,其权值分别为10,12,16,21,30,则其最小的带权路径长度(WPL)是()。
B
06.
D
07.
A
求拓扑序列的过程如下：从图中选择无入边的结点,输出该结点并删除该结点的所有出边,重复上述过程,直至全部结点都已输出,求得拓扑序列ABCDEF。每次输出一个结点并删除该结点的所有出边后,都发现仅有一个结点无入边,因此该拓扑序列唯一,故选A。
求拓扑序列的过程如下：从图中选择无入边的结点,输出该结点并删除该结点的所有出边,重复上述过程,直至全部结点都已输出,求得拓扑序列ABCDEF。每次输出一个结点并删除该结点的所有出边后,都发现仅有一个结点无入边,因此该拓扑序列唯一,故选A。
08.
C
在执行Dijkstra算法时,首先初始化dist[],若顶点1到顶点i(i=2,3,4,5)有边,就初始化为边的权值;若无边,就初始化为∞;初始化顶点集S只含顶点1。Dijkstra算法每次选择一个到顶点1距离最近的顶点加入顶点集S,并判断由顶点1绕行顶点j后到任一顶点k是否距离更短,若距离更短(即dist[j]+arcs[i][k] < dist[k]),则将dist[x]更新为dist[j]+ arcs[j][k];重复该过程,直至所有顶点都加入顶点集S。数组dist的变化过程如下图所示,可知将第二个顶点5加入顶点集S后,数组dist更新为21,3,14,6,故选C。
在执行Dijkstra算法时,首先初始化dist[],若顶点1到顶点i(i=2,3,4,5)有边,就初始化为边的权值;若无边,就初始化为∞;初始化顶点集S只含顶点1。Dijkstra算法每次选择一个到顶点1距离最近的顶点加入顶点集S,并判断由顶点1绕行顶点j后到任一顶点k是否距离更短,若距离更短(即dist[j]+arcs[i][k] < dist[k]),则将dist[x]更新为dist[j]+ arcs[j][k];重复该过程,直至所有顶点都加入顶点集S。数组dist的变化过程如下图所示,可知将第二个顶点5加入顶点集S后,数组dist更新为21,3,14,6,故选C。
09.在一棵高度为3的3阶B树中,根为第1层,若第2层中有4个关键字,则该树的结点个数最多是()。
A
10.设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892},采用最低位优先(LSD)基数排序将S排列成升序序列。第1趟分配、收集后,元素372之前、之后紧邻的元素分别是()。
C
基数排序是一种稳定的排序方法。由于采用最低位优先(LSD)的基数排序,即第1趟对个位进行分配和收集的操作,因此第一趟分配和收集后的结果是{151,301,372,892,93,43,485,946,146,236,327,9},元素372之前、之后紧邻的元素分别是301和892,故选C。
基数排序是一种稳定的排序方法。由于采用最低位优先(LSD)的基数排序,即第1趟对个位进行分配和收集的操作,因此第一趟分配和收集后的结果是{151,301,372,892,93,43,485,946,146,236,327,9},元素372之前、之后紧邻的元素分别是301和892,故选C。
11.将关键字6,9,1,5,8,4,7依次插入到初始为空的大根堆H中,得到的H是()。
B
12.2017年公布的全球超级计算机TOP500排名中,我国“神威·太湖之光”超级计算机蝉联第一,其浮点运算速度为93.0146 PFLOPS,说明该计算机每秒钟内完成的浮点操作次数约为()。
D
13.己知带符号整数用补码表示,变量x,y,z的机器数分别为FFFDH,FFDFH,7FFCH,下列结论中,正确的是()。
D
若x,y和z均为无符号整数,则x>y>z,A和B错误。若x,y和z均为带符号整数,补码的最高位是符号位,0表示正数,1表示负数,因此z为正数,而x和y为负数。对于x和y的比较,数值位取反加1,可知x=-3H,y=-21H,故x>y。D选项正确。
若x,y和z均为无符号整数,则x>y>z,A和B错误。若x,y和z均为带符号整数,补码的最高位是符号位,0表示正数,1表示负数,因此z为正数,而x和y为负数。对于x和y的比较,数值位取反加1,可知x=-3H,y=-21H,故x>y。D选项正确。
14.下列数值中,不能用IEEE754浮点格式精确表示的是()。
B
15.某计算机的存储器总线中有24位地址线和32位数据线，按字编址，字长为32位。如果00 0000H~3F FFFFH为RAM区，那么需要512K×8位的RAM芯片数为()。
C
16.若计算机主存地址为32位,按字节编址,Cache数据区大小为32KB,主存块大小为32B,采用直接映射方式和回写(Write Back)策略,则Cache行的位数至少是()。
A
Cache数据区大小为32KB,主存块的大小为32B,那么Cache中共有1K个Cache行,物理地址中偏移量部分的长度为5bit。因为采用直接映射方式,所以1K个Cache行映射到1K个分组,物理地址中组号部分的长度为10bit。32bit的主存地址除去5bit的偏移量和10bit的组号后,还剩17bit的tag部分。又因为Cache采用回写法,所以Cahce行的总位数应为32B(数据位)+17bit(tag位)+1bit(脏位)+1bit(有效位)=275bit。
Cache数据区大小为32KB,主存块的大小为32B,那么Cache中共有1K个Cache行,物理地址中偏移量部分的长度为5bit。因为采用直接映射方式,所以1K个Cache行映射到1K个分组,物理地址中组号部分的长度为10bit。32bit的主存地址除去5bit的偏移量和10bit的组号后,还剩17bit的tag部分。又因为Cache采用回写法,所以Cahce行的总位数应为32B(数据位)+17bit(tag位)+1bit(脏位)+1bit(有效位)=275bit。
17.下列寄存器中,汇编语言程序员可见的是()。
I.指令寄存器
Ⅱ.微指令寄存器
Ⅲ.基址寄存器
Ⅳ.标志/状态寄存器
D
汇编程序员可见的寄存器有基址寄存器(用于实现多道程序设计,或者编制浮动程序)和状态/标志寄存器、程序计数器PC及通用寄存器组;而MAR、MDR、IR是CPU的内部工作寄存器,对汇编程序员不可见。微指令寄存器属于微程序控制器的组成部分,它是硬件设计者的任务,对汇编程序员是透明的（即不可见的）。
汇编程序员可见的寄存器有基址寄存器(用于实现多道程序设计,或者编制浮动程序)和状态/标志寄存器、程序计数器PC及通用寄存器组;而MAR、MDR、IR是CPU的内部工作寄存器,对汇编程序员不可见。微指令寄存器属于微程序控制器的组成部分,它是硬件设计者的任务,对汇编程序员是透明的（即不可见的）。
18.下列关于数据通路的叙述中,错误的是()。
C
指令执行过程中数据所经过的路径,包括路径上的部件,称为数据通路。ALU、通用寄存器、状态寄存器、Cache、MMU、浮点运算逻辑、异常和中断处理逻辑等,都是指令执行过程中数据流经的部件,都属于数据通路的一部分。数据通路中的数据流动路径由控制部件控制,控制部件根据每条指令功能的不同,生成对数据通路的控制信号。C错误。
指令执行过程中数据所经过的路径,包括路径上的部件,称为数据通路。ALU、通用寄存器、状态寄存器、Cache、MMU、浮点运算逻辑、异常和中断处理逻辑等,都是指令执行过程中数据流经的部件,都属于数据通路的一部分。数据通路中的数据流动路径由控制部件控制,控制部件根据每条指令功能的不同,生成对数据通路的控制信号。C错误。
19.下列关于总线的叙述中,错误的是()。
C
总线是在两个或多个设备之间进行通信的传输介质,A正确。同步总线是指总线通信的双方采用同一个时钟信号,但是一次总线事务不一定在一个时钟周期内完成,即时钟频率不一定等于工作频率,B正确。异步总线采用握手的方式进行通信,每次握手的过程完成一次通信,但一次通信往往会交换多位而非一位数据,C错误。突发传送总线事务是指发送方在传输完地址后,连续进行若干次数据的发送,D正确。
总线是在两个或多个设备之间进行通信的传输介质,A正确。同步总线是指总线通信的双方采用同一个时钟信号,但是一次总线事务不一定在一个时钟周期内完成,即时钟频率不一定等于工作频率,B正确。异步总线采用握手的方式进行通信,每次握手的过程完成一次通信,但一次通信往往会交换多位而非一位数据,C错误。突发传送总线事务是指发送方在传输完地址后,连续进行若干次数据的发送,D正确。
20.下列选项中,不属于I/O接口的是()。
A
I/O接口即I/O控制器,其功能是接收主机发送的I/O控制信号,并实现主机和外部设备之间的信息交换。磁盘驱动器是由磁头、磁盘和读写电路等组成的,也就是我们平常所说的磁盘本身,A错误。B、C和D均为I/O控制器。
I/O接口即I/O控制器,其功能是接收主机发送的I/O控制信号,并实现主机和外部设备之间的信息交换。磁盘驱动器是由磁头、磁盘和读写电路等组成的,也就是我们平常所说的磁盘本身,A错误。B、C和D均为I/O控制器。
21.异常事件在当前指令执行过程中进行检测,中断请求则在当前指令执行后进行检测。下列事件中,相应处理程序执行后,必须回到当前指令重新执行的是()。
B
大部分中断都是在一条指令执行完成后（中断周期）才被检测并处理,除了缺页中断和DMA请求。DMA请求只请求总线的使用权,不影响当前指令的执行,不会导致被中断指令的重新执行;而缺页中断发生在取指或间址等指令执行过程之中,并且会阻塞整个指令。当缺页中断发生后,必须回到这条指令重新执行,以便重新访存。选B。
大部分中断都是在一条指令执行完成后（中断周期）才被检测并处理,除了缺页中断和DMA请求。DMA请求只请求总线的使用权,不影响当前指令的执行,不会导致被中断指令的重新执行;而缺页中断发生在取指或间址等指令执行过程之中,并且会阻塞整个指令。当缺页中断发生后,必须回到这条指令重新执行,以便重新访存。选B。
22.下列是关于多重中断系统中CPU响应中断的叙述,其中错误的是()。
A
中断服务程序在内核态下执行,若只能在用户态下检测和响应中断,显然无法实现多重中断（中断嵌套）,A错误。在多重中断中,CPU只有在检测到中断请求信号后(中断处理优先级更低的中断请求信号是检测不到的),才会进入中断响应周期。进入中断响应周期时,说明此时CPU一定处于中断允许状态,否则无法响应该中断。如果所有中断源都被屏蔽(说明该中断处理优先级最高),则CPU不会检测到任何中断请求信号。
中断服务程序在内核态下执行,若只能在用户态下检测和响应中断,显然无法实现多重中断（中断嵌套）,A错误。在多重中断中,CPU只有在检测到中断请求信号后(中断处理优先级更低的中断请求信号是检测不到的),才会进入中断响应周期。进入中断响应周期时,说明此时CPU一定处于中断允许状态,否则无法响应该中断。如果所有中断源都被屏蔽(说明该中断处理优先级最高),则CPU不会检测到任何中断请求信号。
23.下列指令中,只能在内核态执行的是()。
B
在内核态下,CPU可执行任何指令,在用户态下CPU只能执行非特权指令,而特权指令只能在内核态下执行。常见的特权指令有：①有关对I/O设备操作的指令;②有关访问程序状态的指令;③存取特殊寄存器指令;④其他指令。A、C和D都是提供给用户使用的指令,可以在用户态执行,只是可能会使CPU从用户态切换到内核态。故选B。
在内核态下,CPU可执行任何指令,在用户态下CPU只能执行非特权指令,而特权指令只能在内核态下执行。常见的特权指令有：①有关对I/O设备操作的指令;②有关访问程序状态的指令;③存取特殊寄存器指令;④其他指令。A、C和D都是提供给用户使用的指令,可以在用户态执行,只是可能会使CPU从用户态切换到内核态。故选B。
24.下列操作中,操作系统在创建新进程时,必须完成的是()。
I.申请空白的进程控制块
Ⅱ.初始化进程控制块
Ⅲ.设置进程状态为执行态
B
操作系统感知进程的唯一方式是通过进程控制块PCB,所以创建一个新进程时就是为其申请一个空白的进程控制块,并初始化一些必要的进程信息,如初始化进程标志信息、初始化处理机状态信息、设置进程优先级等。I、Ⅱ正确。创建一个进程时,一般会为其分配除 CPU外的大多数资源,所以一般是将其设置为就绪态,让其等待调度程序的调度。
操作系统感知进程的唯一方式是通过进程控制块PCB,所以创建一个新进程时就是为其申请一个空白的进程控制块,并初始化一些必要的进程信息,如初始化进程标志信息、初始化处理机状态信息、设置进程优先级等。I、Ⅱ正确。创建一个进程时,一般会为其分配除 CPU外的大多数资源,所以一般是将其设置为就绪态,让其等待调度程序的调度。
25.下列内核的数据结构或程序中,分时系统实现时间片轮转调度需要使用的是()。
I.进程控制块
Ⅱ.时钟中断处理程序
Ⅲ.进程就绪队列
Ⅳ.进程阻塞队列
C
在分时系统的时间片轮转调度中,当系统检测到时钟中断时,会引出时钟中断处理程序,调度程序从就绪队列中选择一个进程为其分配时间片,并修改该进程的进程控制块中的进程状态等信息,同时将时间片用完的进程放入就绪队列或让其结束运行。I、Ⅱ、Ⅱ正确。阻塞队列中的进程只有被唤醒进入就绪队列后,才能参与调度,所以该调度过程不使用阻塞队列。
在分时系统的时间片轮转调度中,当系统检测到时钟中断时,会引出时钟中断处理程序,调度程序从就绪队列中选择一个进程为其分配时间片,并修改该进程的进程控制块中的进程状态等信息,同时将时间片用完的进程放入就绪队列或让其结束运行。I、Ⅱ、Ⅱ正确。阻塞队列中的进程只有被唤醒进入就绪队列后,才能参与调度,所以该调度过程不使用阻塞队列。
26.某系统中磁盘的磁道数为200(0~199),磁头当前在184号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次为184,187,176,182,199。若采用最短寻道时间优先调度算法(SSTF)完成磁盘访问,则磁头移动的距离(磁道数)是()。
C
最短寻道时间优先算法总是选择调度与当前磁头所在磁道距离最近的磁道。可以得出访问序列184,182,187,176,199,从而求出移动距离之和是0+2+5+11+23=41。
最短寻道时间优先算法总是选择调度与当前磁头所在磁道距离最近的磁道。可以得出访问序列184,182,187,176,199,从而求出移动距离之和是0+2+5+11+23=41。
27.下列事件中,可能引起进程调度程序执行的是()。
I.中断处理结束
Ⅱ.进程阻塞
Ⅲ.进程执行结束
Ⅳ.进程的时间片用完
D
在时间片调度算法中,中断处理结束后,系统检测当前进程的时间片是否用完,如果用完,则将其设为就绪态或让其结束运行,若就绪队列不空,则调度就绪队列的队首进程执行,Ⅰ可能。当前进程阻塞时,将其放入阻塞队列,若就绪队列不空,则调度新进程执行,Ⅱ可能。进程执行结束会导致当前进程释放CPU,并从就绪队列中选择一个进程获得CPU,Ⅲ可能。进程时间片用完,会导致当前进程让出CPU,同时选择就绪队列的队首进程获得CPU,Ⅳ可能。
在时间片调度算法中,中断处理结束后,系统检测当前进程的时间片是否用完,如果用完,则将其设为就绪态或让其结束运行,若就绪队列不空,则调度就绪队列的队首进程执行,Ⅰ可能。当前进程阻塞时,将其放入阻塞队列,若就绪队列不空,则调度新进程执行,Ⅱ可能。进程执行结束会导致当前进程释放CPU,并从就绪队列中选择一个进程获得CPU,Ⅲ可能。进程时间片用完,会导致当前进程让出CPU,同时选择就绪队列的队首进程获得CPU,Ⅳ可能。
28.
C
页面大小为4KB,低12位是页内偏移。虚拟地址为02A01H,页号为02H,02H页对应的页表项中存在位为0,进程P分配的页框固定为2,且内存中已有两个页面存在。根据 CLOCK算法,选择将3号页换出,将2号页放入60H页框,经过地址变换后得到的物理地址是60A01H。
页面大小为4KB,低12位是页内偏移。虚拟地址为02A01H,页号为02H,02H页对应的页表项中存在位为0,进程P分配的页框固定为2,且内存中已有两个页面存在。根据 CLOCK算法,选择将3号页换出,将2号页放入60H页框,经过地址变换后得到的物理地址是60A01H。
29.在采用二级页表的分页系统中,CPU页表基址寄存器中的内容是()。
B
在多级页表中,页表基址寄存器存放的是顶级页表的起始物理地址,故存放的是一级页表的起始物理地址。
在多级页表中,页表基址寄存器存放的是顶级页表的起始物理地址,故存放的是一级页表的起始物理地址。
30.若目录dir下有文件file1,则为删除该文件内核不必完成的工作是()。
A
删除一个文件时,会根据文件控制块回收相应的磁盘空间,将文件控制块回收,并删除目录中对应的目录项。B、C、D正确。快捷方式属于文件共享中的软连接,本质上是创建了一个链接文件,其中存放的是访问该文件的路径,删除文件并不会导致文件的快捷方式被删除,正如在Windows上删除一个程序后,其快捷方式可能仍存在于桌面,但已无法打开。
删除一个文件时,会根据文件控制块回收相应的磁盘空间,将文件控制块回收,并删除目录中对应的目录项。B、C、D正确。快捷方式属于文件共享中的软连接,本质上是创建了一个链接文件,其中存放的是访问该文件的路径,删除文件并不会导致文件的快捷方式被删除,正如在Windows上删除一个程序后,其快捷方式可能仍存在于桌面,但已无法打开。
31.若系统中有n(n≥2)个进程,每个进程均需要使用某类临界资源2个,则系统不会发生死锁所需的该类资源总数至少是()。
C
考虑极端情况,当临界资源数为时,每个进程都拥有1个临界资源并等待另一个资源,会发生死锁。当临界资源数为n+1时,则n个进程中至少有一个进程可以获得2个临界资源,顺利运行完后释放自己的临界资源,使得其他进程也能顺利运行,不会产生死锁。
考虑极端情况,当临界资源数为时,每个进程都拥有1个临界资源并等待另一个资源,会发生死锁。当临界资源数为n+1时,则n个进程中至少有一个进程可以获得2个临界资源,顺利运行完后释放自己的临界资源,使得其他进程也能顺利运行,不会产生死锁。
32.下列选项中,通过系统调用完成的操作是()。
C
系统调用是由用户进程发起的,请求操作系统的服务。对于A,当内存中的空闲页框不够时,操作系统会将某些页面调出,并将要访问的页面调入,这个过程完全由操作系统完成,不涉及系统调用。对于B,进程调度完全由操作系统完成,无法通过系统调用完成。对于 C,创建新进程可以通过系统调用来完成,如Linux中通过fok系统调用来创建子进程。对于D,生成随机数只需要普通的函数调用,不涉及请求操作系统的服务,如C语言中 random()函数。
系统调用是由用户进程发起的,请求操作系统的服务。对于A,当内存中的空闲页框不够时,操作系统会将某些页面调出,并将要访问的页面调入,这个过程完全由操作系统完成,不涉及系统调用。对于B,进程调度完全由操作系统完成,无法通过系统调用完成。对于 C,创建新进程可以通过系统调用来完成,如Linux中通过fok系统调用来创建子进程。对于D,生成随机数只需要普通的函数调用,不涉及请求操作系统的服务,如C语言中 random()函数。
33.在TCPP参考模型中,由传输层相邻的下一层实现的主要功能是()。
B
TCP/IP参考模型中传输层相邻的下一层是网际层。TCP/IP的网际层使用一种尽力而为的服务,它将分组发往任何网络,并为之独立选择合适的路由,但不保证各个分组有序到达, B正确。TCP/IP认为可靠性是端到端的问题（传输层的功能）,因此它在网际层仅有无连接、不可靠的通信模式,无法完成结点到结点的流量控制(OS参考模型的网络层具有该功能)。对话管理和端到端的报文段传输均为传输层的功能。A、C和D错误。
TCP/IP参考模型中传输层相邻的下一层是网际层。TCP/IP的网际层使用一种尽力而为的服务,它将分组发往任何网络,并为之独立选择合适的路由,但不保证各个分组有序到达, B正确。TCP/IP认为可靠性是端到端的问题（传输层的功能）,因此它在网际层仅有无连接、不可靠的通信模式,无法完成结点到结点的流量控制(OS参考模型的网络层具有该功能)。对话管理和端到端的报文段传输均为传输层的功能。A、C和D错误。
34.
A
差分曼彻斯特编码常用于局域网传输,其规则是：若码元为1,则前半个码元的电平与上一码元的后半个码元的电平相同;若码元为0,则情形相反。差分曼彻斯特编码的特点在于,在每个时钟周期的起始处,跳变则说明该比特是0,不跳变则说明该比特是1。根据题34图,第1个码元的信号波形因缺乏上一码元的信号波形,无法判断是0还是1,但根据后面的信号波形,可以求出第2~8个码元为011 1001,因此选A。
差分曼彻斯特编码常用于局域网传输,其规则是：若码元为1,则前半个码元的电平与上一码元的后半个码元的电平相同;若码元为0,则情形相反。差分曼彻斯特编码的特点在于,在每个时钟周期的起始处,跳变则说明该比特是0,不跳变则说明该比特是1。根据题34图,第1个码元的信号波形因缺乏上一码元的信号波形,无法判断是0还是1,但根据后面的信号波形,可以求出第2~8个码元为011 1001,因此选A。
35.现将一个P网络划分为3个子网,若其中一个子网是192.168.9.128/26,则下列网络中,不可能是另外两个子网之一的是()。
B
根据题意,将P网络划分为3个子网。其中一个是192.168.9.128/26。可以简写成x.x.x.10/26
(其中10是128的二进制10000000的前两位,因为26-24=2)。
A选项可以简写成x.x.x.0/25;
B选项可以简写成x.x.x.00/26;
C选项可以简写成x.x.X.11/26;
D选项可以简写成x.x.x.110/27。
对于A和C,可以组成x.x.x.0/25、x.x.x.10/26、x.x.x.11/26这样3个互不重叠的子网。
对于D,可以组成x.x.x.10/26、x.x.x.110/27、x.x.x.111/27这样3个互不重叠的子网。
但对于B,要想将一个P网络划分为几个互不重叠的子网,3个是不够的,至少需要划分
为4个子网：x.x.x.00/26、x.x.x.01/26、x.x.x.10/26、x.x.x.11/26。
根据题意,将P网络划分为3个子网。其中一个是192.168.9.128/26。可以简写成x.x.x.10/26
(其中10是128的二进制10000000的前两位,因为26-24=2)。
A选项可以简写成x.x.x.0/25;
B选项可以简写成x.x.x.00/26;
C选项可以简写成x.x.X.11/26;
D选项可以简写成x.x.x.110/27。
对于A和C,可以组成x.x.x.0/25、x.x.x.10/26、x.x.x.11/26这样3个互不重叠的子网。
对于D,可以组成x.x.x.10/26、x.x.x.110/27、x.x.x.111/27这样3个互不重叠的子网。
但对于B,要想将一个P网络划分为几个互不重叠的子网,3个是不够的,至少需要划分
为4个子网：x.x.x.00/26、x.x.x.01/26、x.x.x.10/26、x.x.x.11/26。
36.若路由器向MTU=800B的链路转发一个总长度为1580B的IP数据报(首部长度为20B)时,进行了分片,且每个分片尽可能大,则第2个分片的总长度字段和MF标志位的值分别是()。
B
链路层MTU=800B。P分组首部长20B。片偏移以8个字节为偏移单位,因此除最后一个分片,其他每个分片的数据部分长度都是8B的整数倍。所以,最大P分片的数据部分长度为776B。总长度1580B的IP数据报中,数据部分占1560B,1560B/776B=2.01...,需要分成3片。故第2个分片的总长度字段为796,MF为1（表示还有后续的分片）。
链路层MTU=800B。P分组首部长20B。片偏移以8个字节为偏移单位,因此除最后一个分片,其他每个分片的数据部分长度都是8B的整数倍。所以,最大P分片的数据部分长度为776B。总长度1580B的IP数据报中,数据部分占1560B,1560B/776B=2.01...,需要分成3片。故第2个分片的总长度字段为796,MF为1（表示还有后续的分片）。
37.某网络中的所有路由器均采用距离向量路由算法计算路由。若路由器E与邻居路由器A,B, C和D之间的直接链路距离分别是8,10,12和6,且E收到邻居路由器的距离向量如下表所示,则路由器E更新后的到达目的网络Netl~Net4的距离分别是()。
D
38.若客户首先向服务器发送FN段请求断开TCP连接,则当客户收到服务器发送的FIN段并向服务器发送了ACK段后,客户的TCP状态转换为()。
B
39.若大小为12B的应用层数据分别通过1个UDP数据报和1个TCP段传输,则该UDP数据报和TCP段实现的有效载荷（应用层数据）最大传输效率分别是()。
D
应用层数据交给传输层时,放在报文段的数据部分。UDP首部有8B,TCP首部最短有20B。为了达到最大传输效率,通过UDP传输时,总长度为20B,最大传输效率是12B/20B=60%。通过TCP传输时,总长度为32B,最大传输效率是12B/32B=37.5%。
应用层数据交给传输层时,放在报文段的数据部分。UDP首部有8B,TCP首部最短有20B。为了达到最大传输效率,通过UDP传输时,总长度为20B,最大传输效率是12B/20B=60%。通过TCP传输时,总长度为32B,最大传输效率是12B/32B=37.5%。
40.
C
依题意,甲发送完200B报文后,继续发送的报文段中序号字段seq=701。由于乙告知接收窗口为500,且甲未收到乙对seq=501报文段的确认,那么甲还能发送的报文段字节数为 500-200=300B,因此甲在未收到新的确认段之前,还能发送的数据序号范围是701~1000。
依题意,甲发送完200B报文后,继续发送的报文段中序号字段seq=701。由于乙告知接收窗口为500,且甲未收到乙对seq=501报文段的确认,那么甲还能发送的报文段字节数为 500-200=300B,因此甲在未收到新的确认段之前,还能发送的数据序号范围是701~1000。
二、综合应用题
第41~47小题,共70分。
41.(15分)已知无向连通图G由顶点集V和边集E组成,|E|>0,当G中度为奇数的顶点个数为不大于2的偶数时,G存在包含所有边且长度为|E|的路径（称为EL路径）。设图G采用邻接矩阵存储,类型定义如下：
请设计算法int IsExistEL(MGraph G),判断G是否存在EL路径,若存在,则返回1,否则返回0。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。
42.(8分)已知某排序算法如下:
请回答下列问题。
1)若有inta[]={25,-10,25,10,11,19},b[6];则调用cmpCountSort(a,b,6)后数组b中的内容是什么？
2)若a中含有n个元素，则算法执行过程中，元素之间的比较次数是多少？
3)该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
43.
1)ALU的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存器(MAR)和主存数据寄存器(MDR)分别应有多少位？
2)R型格式最多可定义多少种操作？I型和J型格式总共最多可定义多少种操作？通用寄存器最多有多少个？
3)假定op1为0010和0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令01B2H的功能是什么(参考上述指令功能说明的格式进行描述)？若1,2,3号通用寄存器当前内容分别为B052H,0008H,0020H,则分别执行指令01B2H和01B3H后，3号通用寄存器内容各是什么？各自结果是否溢出？
4)若采用I型格式的访存指令中imm(偏移量)为带符号整数，则地址计算时应对imm进行零扩展还是符号扩展？
5)无条件转移指令可以采用上述哪种指令格式？
44.(8分)假设计算机M的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟地址为30位，页大小为4KB;TLB采用2路组相联方式和LRU替换策略，共8组。请回答下列问题。
1)虚拟地址中哪几位表示虚页号？哪几位表示页内地址？
2)已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？
3)假设TLB初始时为空，访问的虚页号依次为10,12,16,7,26,4,12和20，在此过程中,哪一个虚页号对应的TLB表项被替换？说明理由。
4)若将M中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？
45.
1)信号量S是能被多个进程共享的变量，多个进程都可通过wait()和signal()对S进行读、写操作。所以，wait()和signal()操作中对S的访问必须是互斥的。
2)方法1错误。在wait()中，当S<=0时，关中断后，其他进程无法修改s的值，while语句陷入死循环。方法2正确。方法2在循环体中有一个开中断操作，这样就可以使其他进程修改s的值，从而避免while语句陷入死循环。
3)用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指令，不能在用户态下执行，只能在内核态下执行。
2)方法1错误。在wait()中，当S<=0时，关中断后，其他进程无法修改s的值，while语句陷入死循环。方法2正确。方法2在循环体中有一个开中断操作，这样就可以使其他进程修改s的值，从而避免while语句陷入死循环。
3)用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指令，不能在用户态下执行，只能在内核态下执行。
46.(8分)某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序。请回答下列问题。
1)系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么？
2)把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这4个操作的正确顺序是什么？
3)磁盘扇区的划分和文件系统根目录的建立分别是在第2)问的哪个操作中完成的？
1)执行顺序依次是ROM中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始化程序。启动系统时，首先运行ROM中的引导代码(bootstrap)。为执行某个分区的操作系统的初始化程序，需要先执行磁盘引导程序以指示引导到哪个分区，然后执行该分区的引导程序，用于引导该分区的操作系统。
2)4个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系统的安装。磁盘只有通过分区和逻辑格式化后才能安装系统和存储信息。物理格式化(又称低级格式化，通常出厂时就已完成)的作用是为每个磁道划分扇区，安排扇区在磁道中的排列顺序，并对已损坏的磁道和扇区做“坏”标记等。随后将磁盘的整体存储空间划分为相互独立的多个分区（如Windows中划分C盘、D盘等），这些分区可以用作多种用途，如安装不同的操作系统和应用程序、存储文件等。然后进行逻辑格式化（又称高级格式化），其作用是对扇区进行逻辑编号、建立逻辑盘的引导记录、文件分配表、文件目录表和数据区等。最后才是操作系统的安装。
3)由上述解析知，磁盘扇区的划分是在磁盘的物理格式化操作中完成的，文件系统根目录的建立是在逻辑格式化操作中完成的。
2)4个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系统的安装。磁盘只有通过分区和逻辑格式化后才能安装系统和存储信息。物理格式化(又称低级格式化，通常出厂时就已完成)的作用是为每个磁道划分扇区，安排扇区在磁道中的排列顺序，并对已损坏的磁道和扇区做“坏”标记等。随后将磁盘的整体存储空间划分为相互独立的多个分区（如Windows中划分C盘、D盘等），这些分区可以用作多种用途，如安装不同的操作系统和应用程序、存储文件等。然后进行逻辑格式化（又称高级格式化），其作用是对扇区进行逻辑编号、建立逻辑盘的引导记录、文件分配表、文件目录表和数据区等。最后才是操作系统的安装。
3)由上述解析知，磁盘扇区的划分是在磁盘的物理格式化操作中完成的，文件系统根目录的建立是在逻辑格式化操作中完成的。
47.
1)从t到t1期间，除了HTTP,H1还运行了DNS应用层协议，以将域名转换为P地址。DNS运行在UDP之上，UDP将应用层交下来的DNS报文添加首部后，向下交付给IP层，IP层使用IP数据报进行封装，封装好后，向下交付给数据链路层，数据链路层使用CSMA/CD帧进行封装。因此，逐层封装关系如下：DNS报文→UDP数据报→IP数据报→CSMA/CD帧。
2)时刻，H1的ARP表和S的交换表为空。H1利用浏览器通过域名请求访问Web服务器。由于要先解析域名，所以会发送DNS报文到本地域名服务器，查询该域名对应的P地址，所以要先向本地域名服务器发送请求。ARP表为空，所以需要先发送ARP请求分组，查询本地域名服务器对应的MAC地址。这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。 S接收到这个，在交换表中记录下MAC地址为00-11-22-33-44-cc,位于端口4，然后广播该帧。当本地域名服务器接收到ARP请求后，向H1发送响应ARP分组。S接收到这个帧，在交换表中记录下MAC地址为00-11-22-33-44-bb,位于端口1，然后把该帧从端口4发送出去。
得到了域名对应的P地址，发现不在本局域网中，需要通过路由表转发。
H1的ARP表中并没有路由器对应的MAC地址，因此需要先发送ARP请求分组，查询路由器对应的MAC地址。这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。S接收到这个帧，广播该帧。当路由器收到ARP请求后，向H1发送响应ARP分组。S接收到这个帧，在交换表中记录下MAC地址为00-11-22-33-44-aa,位于端口2，然后把该帧从端口4发送出去。现在，H1能把数据发送给路由器了。在整个过程中，并没有涉及H2,H2没有主动发送数据。所以S并不会记录下H2的MAC地址和端口，所以S在t1时刻的交换表如下表所示。
3)由2)的分析可知，H2至少会接收到2个和此次Web访问相关的帧。接收到的均是封装ARP查询报文的以太网帧；这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。
2)时刻，H1的ARP表和S的交换表为空。H1利用浏览器通过域名请求访问Web服务器。由于要先解析域名，所以会发送DNS报文到本地域名服务器，查询该域名对应的P地址，所以要先向本地域名服务器发送请求。ARP表为空，所以需要先发送ARP请求分组，查询本地域名服务器对应的MAC地址。这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。 S接收到这个，在交换表中记录下MAC地址为00-11-22-33-44-cc,位于端口4，然后广播该帧。当本地域名服务器接收到ARP请求后，向H1发送响应ARP分组。S接收到这个帧，在交换表中记录下MAC地址为00-11-22-33-44-bb,位于端口1，然后把该帧从端口4发送出去。
得到了域名对应的P地址，发现不在本局域网中，需要通过路由表转发。
H1的ARP表中并没有路由器对应的MAC地址，因此需要先发送ARP请求分组，查询路由器对应的MAC地址。这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。S接收到这个帧，广播该帧。当路由器收到ARP请求后，向H1发送响应ARP分组。S接收到这个帧，在交换表中记录下MAC地址为00-11-22-33-44-aa,位于端口2，然后把该帧从端口4发送出去。现在，H1能把数据发送给路由器了。在整个过程中，并没有涉及H2,H2没有主动发送数据。所以S并不会记录下H2的MAC地址和端口，所以S在t1时刻的交换表如下表所示。
3)由2)的分析可知，H2至少会接收到2个和此次Web访问相关的帧。接收到的均是封装ARP查询报文的以太网帧；这些帧的目的MAC地址均是FF-FF-FF-FF-FF-FF。