2020全国硕士研究生招生考试计算机学科专业基础试题
一、单项选择题
第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。
01.将一个10×10对称矩阵M的上三角部分的元素mi,j(1≤i≤j≤10)按列优先存入C语言的一维数组N中，元素m7,2在N中的下标是()。
C
02.对空栈S进行Push和Pop操作，入栈序列为a,b,c,d,e,经过Push,Push,Pop,Push,Pop,Push, Push,Pop操作后得到的出栈序列是()。
D
03.对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是()。
A
二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1~5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，总共需要存储单元的数量为1+2+4+8+16=31。
二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1~5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，总共需要存储单元的数量为1+2+4+8+16=31。
04.己知森林F及与之对应的二叉树T,若F的先根遍历序列是a,b,c,d,e,,中根遍历序列是 b,a,d,fe,c,则T的后根遍历序列是()。
C
05.
B
06.修改递归方式实现的图的深度优先搜索(DFS)算法，将输出(访问)顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点，则输出的顶点序列是G的()。
B
07.已知无向图G如下所示，使用克鲁斯卡尔(Kruskal)算法求图G的最小生成树，加到最小生成树中的边依次是()。
A
Kruskal算法：按权值递增顺序依次选取n-1条边，并保证这n-1条边不构成回路。初始构造一个仅含n个顶点的森林；第一步，选取权值最小的边(b,f)加入最小生成树；第二步，剩余边中权值最小的边为(b,d),加入最小生成树，第二步操作后权值最小的边(d,f)不能选，因为会与之前已选取的边形成回路；接下来依次选取权值9,10,11对应的边加入最小生成树，此时6个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树的边依次为(b,f),(b,d),(a,e),(c,e),(b,e)。其生成过程如下所示。
Kruskal算法：按权值递增顺序依次选取n-1条边，并保证这n-1条边不构成回路。初始构造一个仅含n个顶点的森林；第一步，选取权值最小的边(b,f)加入最小生成树；第二步，剩余边中权值最小的边为(b,d),加入最小生成树，第二步操作后权值最小的边(d,f)不能选，因为会与之前已选取的边形成回路；接下来依次选取权值9,10,11对应的边加入最小生成树，此时6个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树的边依次为(b,f),(b,d),(a,e),(c,e),(b,e)。其生成过程如下所示。
08.若使用AOE网估算工程进度，则下列叙述中正确的是()。
B
关键路径是指权值之和最大而非边数最多的路径，故选项A错误。选项B正确，是关键路径的概念。无论是存在一条还是存在多条关键路径，增加任一关键活动的时间都会延长工程的工期，因为关键路径始终是权值之和最大的那条路径，选项C错误。仅有一条关键路径时，减少关键活动的时间会缩短工程的工期；存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，选项D错误。
关键路径是指权值之和最大而非边数最多的路径，故选项A错误。选项B正确，是关键路径的概念。无论是存在一条还是存在多条关键路径，增加任一关键活动的时间都会延长工程的工期，因为关键路径始终是权值之和最大的那条路径，选项C错误。仅有一条关键路径时，减少关键活动的时间会缩短工程的工期；存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，选项D错误。
09.下列关于大根堆（至少含2个元素）的叙述中，正确的是()。
Ⅰ.可以将堆视为一棵完全二叉树
Ⅱ.可以采用顺序存储方式保存堆
Ⅲ.可以将堆视为一棵二叉排序树
Ⅳ.堆中的次大值一定在根的下一层
C
这是一道简单的概念题。堆是一棵完全树，采用一维数组存储，故I正确，Ⅱ正确。大根堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，Ⅲ错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，Ⅳ正确。
这是一道简单的概念题。堆是一棵完全树，采用一维数组存储，故I正确，Ⅱ正确。大根堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，Ⅲ错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，Ⅳ正确。
10.依次将关键字5,6,9,13,8,2,12,15插入初始为空的4阶B树后，根结点中包含的关键字是()。
B
11.对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是()。
I.直接插入排序过程中元素之间的比较次数更少
Ⅱ.直接插入排序过程中所需要的辅助空间更少
Ⅲ.直接插入排序过程中元素的移动次数更少
A
考虑较极端的情况，对于有序数组，直接插入排序的比较次数为n-1，简单选择排序的比较次数始终为1+2+…+n-1=n(n-1)/2,I正确。两种排序方法的辅助空间都是O(1),无差别，Ⅱ错误。初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，Ⅲ错误。
考虑较极端的情况，对于有序数组，直接插入排序的比较次数为n-1，简单选择排序的比较次数始终为1+2+…+n-1=n(n-1)/2,I正确。两种排序方法的辅助空间都是O(1),无差别，Ⅱ错误。初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，Ⅲ错误。
12.下列给出的部件中，其位数（宽度）一定与机器字长相同的是()。
I.ALU
Ⅱ.指令寄存器
Ⅲ.通用寄存器
Ⅳ.浮点寄存器
B
机器字长是指CPU内部用于整数运算的数据通路的宽度。CPU内部数据通路是指CPU内部的数据流经的路径及路径上的部件，主要是CPU内部进行数据运算、存储和传送的部件，这些部件的宽度基本上要一致才能相互匹配。因此，机器字长等于CPU内部用于整数运算的运算器位数和通用寄存器宽度。
机器字长是指CPU内部用于整数运算的数据通路的宽度。CPU内部数据通路是指CPU内部的数据流经的路径及路径上的部件，主要是CPU内部进行数据运算、存储和传送的部件，这些部件的宽度基本上要一致才能相互匹配。因此，机器字长等于CPU内部用于整数运算的运算器位数和通用寄存器宽度。
13.已知带符号整数用补码表示，float型数据用IEEE754标准表示，假定变量x的类型只可能是int或float,当x的机器数为C800 0000H时，x的值可能是()。
A
14.
D
15.下列关于TLB和Cache的叙述中，错误的是()。
D
Cache由SRAM组成；TLB通常由相联存储器组成，也可由SRAM组成。DRAM需要不断刷新，性能偏低，不适合组成TLB和Cache。选项A、B和C都是TLB和Cache的特点。
Cache由SRAM组成；TLB通常由相联存储器组成，也可由SRAM组成。DRAM需要不断刷新，性能偏低，不适合组成TLB和Cache。选项A、B和C都是TLB和Cache的特点。
16.某计算机采用16位定长指令字格式，操作码位数和寻址方式位数固定，指令系统有48条指令，支持直接、间接、立即、相对4种寻址方式。单地址指令中，直接寻址方式的可寻址范围是()。
A
48条指令需要6位操作码字段(25 < 48 < 26)，4种寻址方式需要2位寻址特征位(4=22)，还剩16-6-2=8位作为地址码，故直接寻址范围为0~255。注意，主存地址不能为负。
48条指令需要6位操作码字段(25 < 48 < 26)，4种寻址方式需要2位寻址特征位(4=22)，还剩16-6-2=8位作为地址码，故直接寻址范围为0~255。注意，主存地址不能为负。
17.下列给出的处理器类型中，理想情况下，CPI为1的是()。
I.单周期CPU
Ⅱ.多周期CPU
Ⅲ.基本流水线CPU
Ⅳ.超标量流水线CPU
B
CPI表示执行指令所需的时钟周期数。对于一个程序或一台机器来说，其CPI指执行该程序或机器指令集中的所有指令所需的平均时钟周期数。对于单周期CPU,令指令周期=时钟周期，CPI=1,I正确。对于多周期CPU,CPU的执行过程分成几个阶段，每个阶段用一个时钟去完成，每种指令所用的时钟数可以不同，CPI>1,Ⅱ错误。对于基本流水线CPU,让每个时钟周期流出一条指令，CPI=1,Ⅲ正确。超标量流水线CPU在每个时钟周期内并发执行多条独立的指令，每个时钟周期流出多条指令，CPI< 1,Ⅳ错误。
CPI表示执行指令所需的时钟周期数。对于一个程序或一台机器来说，其CPI指执行该程序或机器指令集中的所有指令所需的平均时钟周期数。对于单周期CPU,令指令周期=时钟周期，CPI=1,I正确。对于多周期CPU,CPU的执行过程分成几个阶段，每个阶段用一个时钟去完成，每种指令所用的时钟数可以不同，CPI>1,Ⅱ错误。对于基本流水线CPU,让每个时钟周期流出一条指令，CPI=1,Ⅲ正确。超标量流水线CPU在每个时钟周期内并发执行多条独立的指令，每个时钟周期流出多条指令，CPI< 1,Ⅳ错误。
18.下列关于“自陷”(Trap,也称陷阱)的叙述中，错误的是()。
A
自陷是一种内部异常，A错误。在80x86中，用于程序调试的“断点设置”功能是通过“自陷”方式实现的，选项B正确。执行到自陷指令时，无条件或有条件地自动调出操作系统内核程序进行执行，选项C正确。CPU执行“陷阱指令”后，会自动地根据不同“陷阱”类型进行相应的处理，然后返回到“陷阱指令”的下一条指令执行，选项D正确。
自陷是一种内部异常，A错误。在80x86中，用于程序调试的“断点设置”功能是通过“自陷”方式实现的，选项B正确。执行到自陷指令时，无条件或有条件地自动调出操作系统内核程序进行执行，选项C正确。CPU执行“陷阱指令”后，会自动地根据不同“陷阱”类型进行相应的处理，然后返回到“陷阱指令”的下一条指令执行，选项D正确。
19.QPI总线是一种点对点全工同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输20位信息(16位数据+4位校验位)，每个QPI数据包有80位信息，分2个时钟周期传送，每个时钟周期传递2次。因此，QPI总线带宽为：每秒传送次数×2B×2。若QPI时钟频率为2.4GHz,则总线带宽为()。
C
每个时钟周期传送2次，故每秒传送的次数=时钟频率×2=2.4G×2/s。
总线带宽=每秒传送次数×2B×2=2.4G×2×2B×2/s=19.2GB/s。
题中已给出总线带宽公式，降低了难度。公式中的“×2B”是因为每次传输16位数据，“×2”
是因为采用点对点全双工总线，两个方向可同时传输信息。
每个时钟周期传送2次，故每秒传送的次数=时钟频率×2=2.4G×2/s。
总线带宽=每秒传送次数×2B×2=2.4G×2×2B×2/s=19.2GB/s。
题中已给出总线带宽公式，降低了难度。公式中的“×2B”是因为每次传输16位数据，“×2”
是因为采用点对点全双工总线，两个方向可同时传输信息。
20.下列事件中，属于外部中断事件的是()。
I.访存时缺页
Ⅱ.定时器到时
Ⅲ.网络数据包到达
C
访存时缺页属于内部异常，I错误；定时器到时描述的是时钟中断，属于外部中断，Ⅱ正确：网络数据包到达描述的是CPU执行指令以外的事件，属于外部中断，Ⅲ正确。
访存时缺页属于内部异常，I错误；定时器到时描述的是时钟中断，属于外部中断，Ⅱ正确：网络数据包到达描述的是CPU执行指令以外的事件，属于外部中断，Ⅲ正确。
21.外部中断包括不可屏蔽中断(NMI)和可屏蔽中断，下列关于外部中断的叙述中，错误的是()。
B
由CPU内部产生的异常称为内中断，内中断都是不可屏蔽中断。通过中断请求线INTR和 NMI,从CPU外部发出的中断请求为外中断，通过INTR信号线发出的外中断是可屏蔽中断，而通过NMI信号线发出的是不可屏蔽中断。不可屏蔽中断不受中断标志位的影响，即使在关中断的情况下也会被响应，选项A正确。不可屏蔽中断的处理优先级最高，任何时候只要发生不可屏蔽中断，都要中止现行程序的执行，转到不可屏蔽中断处理程序执行，选项C正确。CPU响应中断需要满足3个条件：①中断源有中断请求；②CPU允许中断及开中断；③一条指令执行完毕，且没有更紧迫的任务。故选项B错误。
由CPU内部产生的异常称为内中断，内中断都是不可屏蔽中断。通过中断请求线INTR和 NMI,从CPU外部发出的中断请求为外中断，通过INTR信号线发出的外中断是可屏蔽中断，而通过NMI信号线发出的是不可屏蔽中断。不可屏蔽中断不受中断标志位的影响，即使在关中断的情况下也会被响应，选项A正确。不可屏蔽中断的处理优先级最高，任何时候只要发生不可屏蔽中断，都要中止现行程序的执行，转到不可屏蔽中断处理程序执行，选项C正确。CPU响应中断需要满足3个条件：①中断源有中断请求；②CPU允许中断及开中断；③一条指令执行完毕，且没有更紧迫的任务。故选项B错误。
22.若设备采用周期挪用DMA方式进行输入和输出，每次DMA传送的数据块大小为512字节，相应的I/O接口中有一个32位数数据缓冲寄存器。对于数据输入过程，下列叙述中，错误的是()。
C
周期挪用法由DMA控制器挪用一个或几个主存周期来访问主存，传送完一个数据字后立即释放总线，是一种单字传送方式，每个字传送完后CPU可以访问主存，选项C错误。停止CPU访存法则是指在整个数据块的传送过程中，使CPU脱离总线，停止访问主存。
周期挪用法由DMA控制器挪用一个或几个主存周期来访问主存，传送完一个数据字后立即释放总线，是一种单字传送方式，每个字传送完后CPU可以访问主存，选项C错误。停止CPU访存法则是指在整个数据块的传送过程中，使CPU脱离总线，停止访问主存。
23.若多个进程共享同一个文件F,则下列叙述中，正确的是()。
B
多个进程可同时以“读”或“写”方式打开文件，操作系统并不保证写操作的互斥性，进程可通过系统调用对文件加锁，保证互斥写（读者-写者问题），选项A错误。整个系统只有一个系统打开文件表，同一个文件打开多次只需改变引用计数，选项B正确。用户进程的打开文件表关于同一个文件不一定相同，例如读写指针位置不一定相同，选项C错误。进程关闭文件时，文件的引用计数减1，引用计数变为0时才删除系统打开文件表中的表项，选项D错误。
多个进程可同时以“读”或“写”方式打开文件，操作系统并不保证写操作的互斥性，进程可通过系统调用对文件加锁，保证互斥写（读者-写者问题），选项A错误。整个系统只有一个系统打开文件表，同一个文件打开多次只需改变引用计数，选项B正确。用户进程的打开文件表关于同一个文件不一定相同，例如读写指针位置不一定相同，选项C错误。进程关闭文件时，文件的引用计数减1，引用计数变为0时才删除系统打开文件表中的表项，选项D错误。
24.下列选项中，支持文件长度可变、随机访问的磁盘存储空间分配方式是()。
A
索引分配支持变长的文件，同时可以随机访问文件的指定数据块，选项A正确。链接分配不支持随机访问，需要依靠指针依次访问，选项B错误。连续分配的文件长度固定，不支持可变文件长度（连续分配的文件长度虽然也可变，但是需大量移动数据，代价较大，相比之下不太合适)，选项C错误。动态分区分配是内存管理方式，不是磁盘空间的管理方式，选项D错误。
索引分配支持变长的文件，同时可以随机访问文件的指定数据块，选项A正确。链接分配不支持随机访问，需要依靠指针依次访问，选项B错误。连续分配的文件长度固定，不支持可变文件长度（连续分配的文件长度虽然也可变，但是需大量移动数据，代价较大，相比之下不太合适)，选项C错误。动态分区分配是内存管理方式，不是磁盘空间的管理方式，选项D错误。
25.下列与中断相关的操作中，由操作系统完成的是()。
I.保存被中断程序的中断点
Ⅱ.提供中断服务
Ⅲ.初始化中断向量表
Ⅳ.保存中断屏蔽字
D
当CPU检测到中断信号后，由硬件自动保存被中断程序的断点（即程序计数器PC）,I错误。之后，硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址(各中断向量统一存放在中断向量表中，该表由操作系统初始化，Ⅲ正确)。接下来开始执行中断服务程序，保存PSW、保存中断屏蔽字、保存各通用寄存器的值，并提供与中断信号对应的中断服务，中断服务程序属于操作系统内核，Ⅱ和Ⅳ正确。
当CPU检测到中断信号后，由硬件自动保存被中断程序的断点（即程序计数器PC）,I错误。之后，硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址(各中断向量统一存放在中断向量表中，该表由操作系统初始化，Ⅲ正确)。接下来开始执行中断服务程序，保存PSW、保存中断屏蔽字、保存各通用寄存器的值，并提供与中断信号对应的中断服务，中断服务程序属于操作系统内核，Ⅱ和Ⅳ正确。
26.下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是()。
I.就绪队列的数量
Ⅱ.就绪队列的优先级
Ⅲ.各就绪队列的调度算法
Ⅳ.进程在就绪队列间的迁移条件
D
多级反馈队列调度算法需要综合考虑优先级数量、优先级之间的转换规则等，就绪队列的数量会影响长进程的最终完成时间，I正确；就绪队列的优先级会影响进程执行的顺序，Ⅱ正确；各就绪队列的调度算法会影响各队列中进程的调度顺序，Ⅲ正确；进程在就绪队列中的迁移条件会影响各进程在各队列中的执行时间，Ⅳ正确。
多级反馈队列调度算法需要综合考虑优先级数量、优先级之间的转换规则等，就绪队列的数量会影响长进程的最终完成时间，I正确；就绪队列的优先级会影响进程执行的顺序，Ⅱ正确；各就绪队列的调度算法会影响各队列中进程的调度顺序，Ⅲ正确；进程在就绪队列中的迁移条件会影响各进程在各队列中的执行时间，Ⅳ正确。
27.
B
28.下列因素中，影响请求分页系统有效（平均）访存时间的是()。
I.缺页率
Ⅱ.磁盘读写时间
Ⅲ.内存访问时间
Ⅳ.执行缺页处理程序的CPU时间
D
I影响缺页中断的频率，缺页率越高，平均访存时间越长；Ⅱ和Ⅳ影响缺页中断的处理时间，中断处理时间越长，平均访存时间越长；Ⅲ影响访问页表和访问目标物理地址的时间，故I、Ⅱ、Ⅲ和Ⅳ均正确。
I影响缺页中断的频率，缺页率越高，平均访存时间越长；Ⅱ和Ⅳ影响缺页中断的处理时间，中断处理时间越长，平均访存时间越长；Ⅲ影响访问页表和访问目标物理地址的时间，故I、Ⅱ、Ⅲ和Ⅳ均正确。
29.下列关于父进程与子进程的叙述中，错误的是()。
B
父进程与子进程当然可以并发执行，选项A正确。父进程可与子进程共享一部分资源，但不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等，选项B错误。临界资源一次只能为一个进程所用，选项D正确。进程控制块PCB是进程存在的唯一标志，每个进程都有自己的PCB,选项C正确。
父进程与子进程当然可以并发执行，选项A正确。父进程可与子进程共享一部分资源，但不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等，选项B错误。临界资源一次只能为一个进程所用，选项D正确。进程控制块PCB是进程存在的唯一标志，每个进程都有自己的PCB,选项C正确。
30.对于具备设备独立性的系统，下列叙述中，错误的是()。
D
设备可视为特殊文件，选项A正确。用户使用逻辑设备名来访问物理文件，有利于设备独立性，选项B正确。通过逻辑设备名访问物理设备时，需要建立逻辑设备和物理设备之间的映射关系，选项C正确。应用程序按逻辑设备名访问设备，再经驱动程序的处理来控制物理设备，若更换物理设备，则只需更换驱动程序，而无须修改应用程序，选项D错误。
设备可视为特殊文件，选项A正确。用户使用逻辑设备名来访问物理文件，有利于设备独立性，选项B正确。通过逻辑设备名访问物理设备时，需要建立逻辑设备和物理设备之间的映射关系，选项C正确。应用程序按逻辑设备名访问设备，再经驱动程序的处理来控制物理设备，若更换物理设备，则只需更换驱动程序，而无须修改应用程序，选项D错误。
31.某文件系统的目录项由文件名和索引结点号构成。若每个目录项长度为64字节，其中4字节存放索引结点号，60字节存放文件名。文件名由小写英文字母构成，则该文件系统能创建的文件数量的上限为()。
B
在总长为64字节的目录项中，索引结点占4字节，即32位。不同目录下的文件的文件名可以相同，所以在考虑系统创建最多文件数量时，只需考虑索引结点的个数，即创建文件数量上限=索引结点数量上限。整个系统中最多存储232个索引结点，因此整个系统最多可以表示232个文件，选项B正确。
在总长为64字节的目录项中，索引结点占4字节，即32位。不同目录下的文件的文件名可以相同，所以在考虑系统创建最多文件数量时，只需考虑索引结点的个数，即创建文件数量上限=索引结点数量上限。整个系统中最多存储232个索引结点，因此整个系统最多可以表示232个文件，选项B正确。
32.下列准则中，实现临界区互斥机制必须遵循的是()。
I.两个进程不能同时进入临界区
Ⅱ.允许进程访问空闲的临界资源
Ⅲ.进程等待进入临界区的时间是有限的
Ⅳ.不能进入临界区的执行态进程立即放弃CPU
C
实现临界区互斥需满足多个准则。“忙则等待”准则，即两个进程不能同时访问临界区，I正确。“空闲让进”准则，若临界区空闲，则允许其他进程访问，Ⅱ正确。“有限等待”准则，即进程应该在有限时间内访问临界区，Ⅲ正确。I、Ⅱ和Ⅲ是互斥机制必须遵循的原则。Ⅳ是“让权等待”准则，不一定非得实现，如皮特森算法。
实现临界区互斥需满足多个准则。“忙则等待”准则，即两个进程不能同时访问临界区，I正确。“空闲让进”准则，若临界区空闲，则允许其他进程访问，Ⅱ正确。“有限等待”准则，即进程应该在有限时间内访问临界区，Ⅲ正确。I、Ⅱ和Ⅲ是互斥机制必须遵循的原则。Ⅳ是“让权等待”准则，不一定非得实现，如皮特森算法。
33.
C
协议由语法、语义和时序（又称同步）三部分组成。语法规定了通信双方彼此“如何讲”，即规定了传输数据的格式。语义规定了通信双方彼此“讲什么”，规定了所要完成的功能，如通信双方要发出什么控制信息、执行的动作和返回的应答。时序规定了信息交流的次序。由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。
协议由语法、语义和时序（又称同步）三部分组成。语法规定了通信双方彼此“如何讲”，即规定了传输数据的格式。语义规定了通信双方彼此“讲什么”，规定了所要完成的功能，如通信双方要发出什么控制信息、执行的动作和返回的应答。时序规定了信息交流的次序。由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。
34.下列关于虚电路网络的叙述中，错误的是()。
B
虚电路服务需要有建立连接过程，每个分组使用短的虚电路号，属于同一条虚电路的分组按照同一路由进行转发，分组到达终点的顺序与发送顺序相同，可以保证有序传输，不需要为每条虚电路预分配带宽。
虚电路服务需要有建立连接过程，每个分组使用短的虚电路号，属于同一条虚电路的分组按照同一路由进行转发，分组到达终点的顺序与发送顺序相同，可以保证有序传输，不需要为每条虚电路预分配带宽。
35.在下图所示的网络中，冲突域和广播域的个数分别是()。
C
36.假设主机甲采用停-等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B,数据传输速率是10kbps,单项传播延时是200ms。则甲的最大信道利用率为()。
D
发送数据帧和确认帧的时间均为t=1000×8b/10kbps=800ms。
发送周期T=800ms+200ms+800ms+200ms=2000ms。
信道利用率=t/T×100%=800/2000×100%=40%。
发送数据帧和确认帧的时间均为t=1000×8b/10kbps=800ms。
发送周期T=800ms+200ms+800ms+200ms=2000ms。
信道利用率=t/T×100%=800/2000×100%=40%。
37.
A
为了尽量避免碰撞，802.11规定，所有站在完成发送后，必须等待一段很短的时间(继续监听)才能发送下一帧。这段时间称为帧间间隔(InterFrame Space,IFS)。帧间间隔的长短取决于该站要发送的帧的类型。IEEE 802.11使用3种帧间间隔:
DIFS(分布式协调IFS):最长的IFS,优先级最低，用于异步帧竞争访问的时延。
PIFS(点协调IFS):中等长度的IFS,优先级居中，在PCF操作中使用。
SIFS(短IFS):最短的IFS,优先级最高，用于需要立即响应的操作。网络中的控制帧及所接收数据的确认帧都采用SIFS作为发送之前的等待时延。当结点要发送数据帧时，载波监听到信道空闲时，需等待DIFS后发送RTS预约信道，图中IFS1对应的是帧间间隔DIFS,时间最长，图中IFS2、FS3、IFS4对应SIFS。
为了尽量避免碰撞，802.11规定，所有站在完成发送后，必须等待一段很短的时间(继续监听)才能发送下一帧。这段时间称为帧间间隔(InterFrame Space,IFS)。帧间间隔的长短取决于该站要发送的帧的类型。IEEE 802.11使用3种帧间间隔:
DIFS(分布式协调IFS):最长的IFS,优先级最低，用于异步帧竞争访问的时延。
PIFS(点协调IFS):中等长度的IFS,优先级居中，在PCF操作中使用。
SIFS(短IFS):最短的IFS,优先级最高，用于需要立即响应的操作。网络中的控制帧及所接收数据的确认帧都采用SIFS作为发送之前的等待时延。当结点要发送数据帧时，载波监听到信道空闲时，需等待DIFS后发送RTS预约信道，图中IFS1对应的是帧间间隔DIFS,时间最长，图中IFS2、FS3、IFS4对应SIFS。
38.若主机甲与主机乙已建立一条TCP连接，最大段长(MSS)为1KB,往返时间(RTT)为 2s,则在不出现拥塞的前提下，拥塞窗口从8KB增长到32KB所需的最长时间是()。
D
由于慢开始门限ssthresh可以根据需求设置，为了求拥塞窗口从8KB增长到32KB所需的最长时间，可以假定慢开始门限小于等于8KB,只要不出现拥塞，拥塞窗口就都是加法增大，每经历一个传输轮次(RTT),拥塞窗口逐次加1，所需最长时间为(32-8)×2s=48ms。
由于慢开始门限ssthresh可以根据需求设置，为了求拥塞窗口从8KB增长到32KB所需的最长时间，可以假定慢开始门限小于等于8KB,只要不出现拥塞，拥塞窗口就都是加法增大，每经历一个传输轮次(RTT),拥塞窗口逐次加1，所需最长时间为(32-8)×2s=48ms。
39.若主机甲与主机乙建立TCP连接时，发送的SYN段中的序号为1000，在断开连接时，甲发送给乙的FN段中的序号为5001，则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为()。
C
甲与乙建立TCP连接时发送的SYN段中的序号为1000，则在数据传输阶段所用的起始序号为1001；断开连接时，甲发送给乙的FN段中的序号为5001，在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为5001-1001=4000。
甲与乙建立TCP连接时发送的SYN段中的序号为1000，则在数据传输阶段所用的起始序号为1001；断开连接时，甲发送给乙的FN段中的序号为5001，在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为5001-1001=4000。
40.
D
题中RTT均为局域网内主机（主机H、本地域名服务器）访问Internet上各服务器的往返时间，且忽略其他时延，因此主机H向本地域名服务器的查询时延忽略不计。最短时间：本地主机中有该域名到IP地址对应的记录，因此不需要DNS查询时延，直接和 www.abc.com服务器建立TCP连接再进行资源访问，TCP连接建立需要1个RTT,接着发送访问请求并收到服务器资源响应需要1个RTT,共计2个RTT,即20ms;最长时间：本地主机递归查询本地域名服务器（延时忽略），本地服务器依次迭代查询根域名服务器、com顶级域名服务器、abc.com域名服务器，共3个RTT,查询到IP地址后，将该映射返回给主机H,主机H和www.abc.com服务器建立TCP连接再进行资源访问，共2个RTT,因此最长时间需要3+2=5个RTT,即50ms。
题中RTT均为局域网内主机（主机H、本地域名服务器）访问Internet上各服务器的往返时间，且忽略其他时延，因此主机H向本地域名服务器的查询时延忽略不计。最短时间：本地主机中有该域名到IP地址对应的记录，因此不需要DNS查询时延，直接和 www.abc.com服务器建立TCP连接再进行资源访问，TCP连接建立需要1个RTT,接着发送访问请求并收到服务器资源响应需要1个RTT,共计2个RTT,即20ms;最长时间：本地主机递归查询本地域名服务器（延时忽略），本地服务器依次迭代查询根域名服务器、com顶级域名服务器、abc.com域名服务器，共3个RTT,查询到IP地址后，将该映射返回给主机H,主机H和www.abc.com服务器建立TCP连接再进行资源访问，共2个RTT,因此最长时间需要3+2=5个RTT,即50ms。
二、综合应用题
第41~47小题，共70分。
41.
分析。由D=|a-b|+|b-c|+|c-a|≥0得：
①当a=b=c时，距离最小。
②其余情况。不失一般性，假设α≤b≤c,观察下面的数轴：
①当a=b=c时，距离最小。
②其余情况。不失一般性，假设α≤b≤c,观察下面的数轴：
42.
1)使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径，路径长度等于编码位数，路径到达的叶结点中保存该编码对应的字符。
2)从左至右依次扫描0/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到0/1串结束，译码完成。
3)二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。
依次读入每个编码C,建立/寻找从根开始对应于该编码的一条路径，过程如下：
对每个编码，从左至右扫描C的各位，根据C的当前位(0或1)沿结点的指针(左子指针或右子指针)向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况：
①若遇到了叶结点（非根），则表明不具有前缀特性，返回。
②若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回。
③若在处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。若所有编码均通过验证，则编码具有前缀特性。
2)从左至右依次扫描0/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到0/1串结束，译码完成。
3)二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。
依次读入每个编码C,建立/寻找从根开始对应于该编码的一条路径，过程如下：
对每个编码，从左至右扫描C的各位，根据C的当前位(0或1)沿结点的指针(左子指针或右子指针)向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况：
①若遇到了叶结点（非根），则表明不具有前缀特性，返回。
②若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回。
③若在处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。若所有编码均通过验证，则编码具有前缀特性。
43.
44.
45.
46.
3)已知数组a按行优先方式存放，若对数组a分别按行遍历和按列遍历，则哪种遍历方式的局部性更好？
2)根据数组的随机存取特点，数组a在虚拟地址空间中所占的区域必须连续，由于数组a不止占用一页，相邻逻辑页在物理上不一定相邻，因此数组a在物理地址空间中所占的区域可以不连续。3)由1)可知每个页面正好可以存放一整行的数组元素，“按行优先方式存放”意味着数组的同一行的所有元素都存放在同一个页面中，同一列的各个元素都存放在不同的页面中，因此数组a按行遍历的局部性较好。
47.
