2019 年 408 真题
本节正在编写中，敬请期待。
选择题
数据结构
1
设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是 （ ）。
x = 0;
while (n >= (x + 1) * (x + 1))
x = x + 1;
假设第 k 次循环终止，则第 k 次执行时， $(x+1)^{2} > n$，x 的初始值为 0，第 k 次判 断时，x=k-1，即 $k^2 > n$，$k > n^{1/2}$,，因此该程序段的时间复杂度为 $O(n^{1/2})$。
2
若将一棵树 T 转化为对应的二又树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是
第一步，需要知道如何将一棵树转化为二叉树：对于每一个结点，第一个孩子结点 放左子树，其余孩子结点（即第一个孩子结点的兄弟结点）放在第一个孩子结点的右子树， 其余的孩子结点再依次放在右子树的右子树，依次类推。
第二步，需要知道选项中的四种遍历方式先序遍历：该结点，左子树，右子树中序遍历：左子 树，该结点，右子树后序遍历：左子树，右子树，该节点层次遍历：队列实现前 3 种遍历方 式，左子树都是先于右子树，“先”、“中”、“后”指的是访问该结点的次序，对于上图，我们 发现，对树的后序遍历与对二叉树的中序遍历相同，选 B。
3
对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是（ ）。
哈夫曼树是一颗带权路径长度最短二叉树，有性质：n 个叶子结点的哈夫曼树，共 2n-1 个结点 2n-1 = 115 解得 n = 58，选 C。
4
在任意一棵非空平衡二叉树（AVL 树） T1 中，删除某结点 v 之后形成平衡二叉树 T2 ， 再将 v 插入 T2 形成平衡二叉树 T3 。下列关于 T1 与 T3 的叙述中，正确的是（ ）。
I.若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同
II.若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同
III.若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同
平衡二叉树的插入、删除操作可能会引起树的旋转（为了保持树的平衡性），所以 T1 与 T3 可能不相同，选 A。
5
下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是
AOE 网是以边表示活动的有向无环网。活动 d 开始必须满足活动 a 和活动 b 结束， 所以最早开始时间是 12。最晚开始时间是指不会延长整个网的结束时间的前提下，d 的开始 时间。结点 1 到结点 6 的最长路径（关键路径）是 27，结点 4 的最晚开始时间是 27-6=21， 结点 d 的最晚开始时间是 21-7=14。答案选 C。
6
用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是
先将该表达式转换成有向二叉树，注意到该二叉树中有些顶点时重复的，为了节省 存储空间，可以去除重复的顶点（使顶点个数达到最少），将有向二叉树去重转换成有向无环 图，结果如图所示：
7
选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是
I.数据的规模 Ⅱ.数据的存储方式 Ⅲ.算法的稳定性 Ⅳ.数据的初始状态
当数据规模较小时可选择是复杂度为 O(n2)的简单排序算法，当数据规模较大时应选 择复杂度为 O(nlog2n)的排序方法，当数据规模大到内存无法放下时需选择外部排序方法，Ⅰ 正确。数据的存储方式主要分为顺序存储和链式存储，有些排序方法（如堆排序）只能用于 顺序存储方式，Ⅱ正确。若对数据稳定性有要求，则不能选择不稳定的排序方法，Ⅲ显然正 确。当数据初始基本有序时，直接插入排序的效率最高，冒泡排序和直接插入排序的时间复 杂度都是 O(n)，而归并排序的时间复杂度依旧是 O(nlog2n)，Ⅳ正确。所以选 D。
8
现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是
构造散列表只有当遇到关键字为空的地址时才会查找失败，key%7 之后，初始地址 只可能在 0~6，所以即 0~6 到空地址的距离求平均，即为查找失败的平均查找长度初始地址 是 0 的失败查找长度为 9，同理得初始地址为 1，2，3，4，5，6 的失败查找长度为 8，7， 6，5，4，3，(9+8+7+6+5+4+3)/7 = 6 答案是 C。
9
设主串 T=“abaabaabcabaabc”，模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是
假设位序都是从 0 开始的，按照 next 数组生成算法，对于 S 有
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | a | a | b | c |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
根据 KMP 算法，第一趟连续对比 6 次，在模式串的 5 号位和主串的 5 号位匹配失败，模式 串的下一个比较位置为 next[5]，即下一次比较从模式串的 2 号位和主串 5 号位开始，然后直 到模式串 5 号位和主串 8 号位匹配，第二趟比较 4 次，模式串匹配成功。单个字符的比较次 数为 10 次，所以选 B。
10
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（）
要理解清楚排序过程中一“趟”的含义，题干也进行了解释。一个初始无序序列，所 有元素都没有确定最终位置，对所有元素做一次（称为趟）快速排序后一个元素确定最终位置， 且将原序列划分成了前后两块，此时前后两块子表是无序的。按“趟”的解释一一对尚未确 定最 终位置的所有元素都处理一遍才是一 趟， 所以此时要对前后两块子表各做次快速排序 才是一趟快速排序，如果只对一块子表进行了排序，而未处理另一块字表，就不能算是完整 的一趟，选项 D 无论先匹配 12 还是 32，都会将序列分成两块，那么第二趟必须有两个元素 匹配，所以 D 不可能，故选 D。
11
设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是
在 12 路归并树中只存在度为 0 和度为 12 的结点，设度为 0 的结点数、度为 12 的 结点数和要补充的结点数分别为 $n_0$，$n_{12}$，$n_{补}$，则有 $n_{0} = 120 + n_补$，$n_0=(12-1)n_{12}+1$，可得 $n_{12}=(120-1+n{补})/(12-1)$。由于结点数 $n_{12}$ 为整数，所以 n 补是使上式整除的最小整数，求得 $n_补 = 2$，所以答案选 B。
组成原理
12
下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是
冯·诺依曼结构计算机的功能部件包括输入设备、输出设备、存储器、运算器和控制 器，程序的功能都通过中央处理器（运算器和控制器）执行指令，A 正确。指令和数据以同等地 位存于存储器内，形式上无差别，只在程序执行时具有不同的含义，B 正确。指令在地址访 问，数据由指令的地址码指出，除立即寻址，数据均存放在存储器内，C 错误。在程序执行 前，指令和数据需预先存放在存储器中，中央处理器可以从存储器存取代码，D 正确。
13
考虑以下 C 语言代码：
unsigned short usi = 65535;
short si = usi;
执行上述程序段后，si 的值是
unsigned short 类型为无符号短整型，长度为 2 字节，因此 unsigned short usi 转换 为二进制代码即 1111 1111 1111 1111。short 类型为短整型，长度为 2 字节，在采用补码的机 器上 short si 的二进制代码为 1111 1111 1111 1111，因此 si 的值为-1，所以选 A。
14
下列关于缺页处理的叙述中，错误的是( )
在请求分页系统中，每当要访问的页面不在内存中时，CPU 检测到异常，便会产生 缺页中断，请求操作系统将所缺的页调入内存。缺页处理由缺页中断处理程序完成，根据发 生缺页故障的地址从外存读入所缺失的页，鋏页处理完成后回到发生缺页的指令继续执行。 选项 D 中描述回到发生缺页的指令的下一条指令执行，明显错误，所以选 D。
15
某计算机采用大端方式，按字节编址。某指令中操作数的机器数为 1234FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为 FF12H，基址寄存器内容为 F0000000H，则该操作数的 LSB（最低有效字节）所在的地址是( )
注意，内存地址是无符号数。操作数采用基址寻址方式，EA=(BR)+A，基址寄存器 BR 的内容为 F000 0000H，形式地址用补码表示为 FF12H，即 1111 1111 0001 0010B，因 此有效地址为 F000 0000H +(-00EEH) = EFFF FF12H。计算机采用大端方式编址，故低位字 节存放在字的高地址处，机器数一共占 4 字节，该操作数的 LSB 所在的地址是 EFFF FF12H+3= EFFF FF15H，所以选 D。
16
下列有关处理器时钟脉冲信号的叙述中，错误的是( )
时脉冲信号的宽度称为时钟周期，时钟周期是 CPU 工作的最小时间单位，时钟周期 的倒数为机器主频。时钟脉冲信号是由机器脉冲源发出的脉冲信号经整形和分频后形成的， 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定。CPU 从内存中取出并执行 一条指令所需的全部时间称为指令周期，指令周期又由若干机器周期来表示，一个机器周期 又包含若干时钟周期，选项 D 显然错误。
17
某指令功能为 R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是
I.通用寄存器组(GPRs) II. 算术逻辑单元(ALU)
II.存储器(Memory) IV. 指令译码器(ID)
该指令的两个源操作数分别采用寄存器，寄存器间接寻址方式，因此在取数阶段需 要用到通用寄存器组和存储器；在执行阶段，两个源操作数相加需要用到算术逻辑单元；而 指令译码器用于操作码字段进行译码，向控制器提供特定的操作信号，在取数及执行阶段用 不到，所以答案选 B。
18
在采用“取指、译码/取数、执行、访存、写回”5 段流水线的处理器中，执行如下指令序列，其中 s0、s1、s2、s3 和 t2 表示寄存器编号。
I1: add s2,s1,s0 // R[s2]←R[s1]+R[s0]
I2: load s3,0(t2) // R[s3]←M[R[t2]+0]
I3: add s2,s2,s3 // R[s2]←R[s2]+R[s3]
I4: store s2,0(t2) // M[R[t2]+0]←R[s2]
下列指令对中，不存在数据冒险的是（ ）。
出这四条指令在流水线中执行的过程如下图所示：
数据冒险即数据相关，指在程序中存在必须等前条指令执行完才能执行后一条指令 的情况，此时这两条指令即为数据相关。其中 I1 和 I3、I2 和 I3、I3 和 I4 均发生了写后读相 关，因此必须等相关的前条指令执行完才能执行后一条指令。只有 I2 和 I4 不存在数据冒险。 所以答案选 C。
19
假定一台计算机采用 3 通道存储器总线，配套的内存条型号为 DDR3-1333，即内存条所接插的存储器总线的工作频率为 1333MHz，总线宽度为 64 位，则存储器总线的总带宽大约是（ ）。
由题目可知，计算机采用 3 通道存储器总线，存储器总线的工作频率为 1333MHz， 即 1 秒内传送 1333M 次数据，总线宽度为 64 位即单条总线工作一次可传输 8 字节(Byte)， 因此存储器总线的总带宽 3×8×1333MB/s，约为 32GB/s，故答案选 B。
20
下列关于磁盘存储器的叙述中，错误的是（ ）。
磁盘存储器的最小读写单位为一个扇区，即磁盘按块存取，选项 C 错误。磁盘存储 数据之前需进行格式化，将磁盘分成扇区，并写入信息，因此磁盘的格式化容量比非格式化 容量小，选项 A 正确。磁盘扇区中包含数据、地址和校验等信息，选项 B 正确。磁盘存储器 由磁盘控制器、磁盘驱动器和盘片组成，选项 D 正确。
21
某设备以中断方式与 CPU 进行数据交换，CPU 主频为 1GHz，设备接口中的数据缓冲寄存器为 32 位，设备的数据传输率为 50KBps。若每次中断开销（包括中断响应和中断处理）为 1000 个时钟周期，则 CPU 用于该设备输入/输出的时间占整个 CPU 时间的百分比最多是（ ）。
设备接口中的数据缓冲寄存器为 32 位，即一次中断可以传输 4B 数据，设备数据传 输率为 50kB/s,共需要 12.5k 次中断，每次中断开销为 1000 个时钟周期，CPU 频为 1GHz， 则 CPU 用于该设备输入/输出的时间占整个 CPU 时间的百分比最多是(12.5k×1000)/1G = 1.25%。
22
下列关于 DMA 方式的叙述中，正确的是（ ）。
Ⅰ. DMA 传送前由设备驱动程序设置传送参数
Ⅱ. 数据传送前由 DMA 控制器请求总线使用权
Ⅲ. 数据传送由 DMA 控制器直接控制总线完成
Ⅳ. DMA 传送结束后的处理由中断服务程序完成
类设备都配置一个设备驱动程序，设备驱动程序向上层用户程序提供一组标准接 口，负责实现对设备发出各种具体操作指令，用户程序不能直接和 DMA 打交道。DMA 的数 据传送过程分为预处理、数据传送和后处理 3 个阶段。预处理阶段由 CPU 完成必要的准备工 作，数据传送前由 DMA 控制器请求总线使用权；数据传送由 DMA 控制器直接控制总线完成； 传送结束后，DMA 控制器向 CPU 发送中断请求，CPU 执行中断服务程序做 DMA 结束处理。
操作系统
23
下列关于线程的描述中，错误的是（ ）。
应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口，内核为进 程及其内部的每个线程维护上下文信息，调度也是在内核中由操作系统完成的，选项 A 正确。 在多线程模型中，用户级线程和内核级线程的连接方式分为多对一、一对一、多对多，“操作 系统为每个用户线程建立一个线程控制块”属于一对一模型，选项 B 错误。用户级线程的切 换可以在用户空间完成，内核级线程的切换需要操作系统帮助进行调度，故用户级线程的切 换效率更高，选项 C 正确。用户级线程的管理工作可以只在用户空间中进行，故可以在不支 持内核级线程的操作系统上实现，选项 D 正确。
24
下列选项中，可能将进程唤醒的事件是（ ）。
Ⅰ.I/O 结束
Ⅱ.某进程退出临界区
Ⅲ.当前进程的时间片用完
当被阻塞进程等待的某资源为可用时，进程将会被唤醒。I/O 结束后，等待该 I/O 结 束而被阻塞的有关进程就会被唤醒，Ⅰ正确；某进程退出临界区后，之前因需要进入该临界 区而被阻塞的有关进程就会被唤醒，Ⅱ正确，当前进程的时间片用完后进入就绪队列等待重 新调度，优先级最高的进程将获得处理机资源从就绪态变成执行态，Ⅲ错误。
25
下列关于系统调用的叙述中，正确的是（ ）。
Ⅰ.在执行系统调用服务程序的过程中，CPU 处于内核态
Ⅱ.操作系统通过提供系统调用避免用户程序直接访问外设
Ⅲ.不同的操作系统为应用程序提供了统一的系统调用接口
Ⅳ.系统调用是操作系统内核为应用程序提供服务的接口
用户可以在用户态调用操作系统的服务，但执行具体的系统调用服务程序是处于内 核态的，Ⅰ正确：设备管理属于操作系统的职能之一，包括对输入/输出设备的分配、初始化、 维护等，用户程序需要通过系统调用使用操作系统的设备管理服务，Ⅱ正确：操作系统不同， 底层逻辑、实现方式均不相同，为应用程序提供的系统调用接口也不同，Ⅲ错误：系统调用是 用户在程序中调用操作系统提供的子功能，Ⅳ正确。
26
下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。
Ⅰ. 位图
Ⅱ. 索引结点
Ⅲ. 空闲磁盘块链
Ⅳ. 文件分配表 (FAT)
传统的文件系统管理空间磁盘的方法包括空闲表法、空闲链表法、位示图和成组链 接法，Ⅰ、Ⅲ正确。文件分配表(FAT)的表项与物理磁盘块一一对应，并且可以用一个特殊的 数字-1 表示文件的最后一块，用-2 表示这个磁盘块是空闲的（当然，规定用-3、-4 来表示也是 可行的）。因此文件分配表(FAT)不仅记录了文件中各个块的先后链接关系，同时还标记了空闲 的磁盘块，操作系统可以通过 FAT 对文件存储空间进行管理，Ⅳ正确。索引结点是操作系统 为了实现文件名与文件信息分开而设计的数据结构，存储了文件描述信息，索引结点属于文 件目录管理部分的内容，Ⅱ错误。
27
系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法，时间片为 10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度 Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2 中的进程；新创建的进程首先进入 Q1;Q1 中的进程执行一个时间片后，若未结束，则转入 Q2。若当前 Q1，Q2 为空，系统依次创建进程 P1，P2 后即开始进程调度，P1,P2 需要的 CPU 时间分别为 30ms 和 20ms，则进程 P1，P2 在系统中的平均等待时间为（）。
进程 P1、P2 依次创建后进入队列 Q1，根据时间片调度算法的规则，进程 P1、P2 将依次被分配 10m 的 CPU 时间，两个进程分别执行完一个时间片后都会被转入队列 Q2，就 绪队列 Q2 采用短进程优先调度算法，此时 P1 还需要 20ms 的 CPU 时间，P2 还需要 10ms 的 CPU 时间，所以 P2 会被优先调度执行，10ms 后进程 P2 执行完成，之后 P1 再调度执 行，再过 20ms 后 P1 也执行完成。平均等待时间= （P1 等待时间+P2 等待时间）/2 = (20+10)/2 =15。
28
在分段存储管理系统中，用共享段表描述所有被共享的段。若进程 P1 和 P2 共享段 S，下列叙述中，错误的是（ ）。
段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实 现的，因此在内存中仅保存一份段 s 的内容。选项 A 正确。段 s 对于进程 P1，P2 来说，使用 位置可能不同，所以在不同进程中的逻辑段号可能不同，选项 B 错误。段表项存放的是段的 物理地址，对于共享段 s 来说物理地址唯一，选项 C 正确。为了保证进程可以顺利使用段 s， 段 s 必须确保在没有任何进程使用它后才能被删除，选项 D 正确。
29
某系统采用 LRU 页置换算法和局部置换策略，若系统为进程 P 预分配了 4 个页框，进程 P 访问页号的序列为 0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6，则进程访问上述页的过程中，产生页置换的总次数是（ ）。
最近最久未使用算法每次执行页面置换时会换出最近最久没有使用过的页面。第一 次访问 5 页面时，会把最久未被使用的 1 页面换出，第一次访问 3 页面时，会把最久未访问 的 2 页面换出。具体的页面置换情况如下图所示：
| 访问页面 | 0 | 1 | 2 | 7 | 0 | 5 | 3 | 5 | 0 | 2 | 7 | 6 | | 物理块 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 物理块 | 2 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | | 物理块 | 3 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 7 | 7 | | 物理块 | 4 | 7 | 7 | 7 | 7 | 7 | 7 | 2 | 2 | 2 | | 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
需要注意的是：题中问的是页置换算法，而不是缺页次数，所以前 4 次缺页未还也的操作不 考虑在内，答案为 5 次，故选 C。
30
下列关于死锁的叙述中，正确的是（）。
Ⅰ、可以通过剥夺进程资源解除死锁
Ⅱ、死锁的预防方法能确保系统不发生死锁
Ⅲ、银行家算法可以判断系统是否处于死锁状态
Ⅳ、当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
剥夺进程资源，将其分配给其他死锁进程，可以解除死锁，Ⅰ正确。死锁预防是死锁 处理策略（死锁预防、死锁避免、死锁检测）中最为严苛的一种策略，破坏死锁产生的 4 个必要 条件之一。可以确保系统不发生死锁，Ⅱ正确。银行家算法是一种死锁避免算法，用于计算 动态资源分配的完全性以避免系统进入死锁状态，不能用于判断系统是否处于死锁，Ⅲ错误。 通过简化资源分配图可以检测系统是否为死锁状态，当系统出现死锁时，资源分配图不可完 全简化。只有两个成两个以上的进程才会出现“环”而不能被简化，Ⅳ正确。
31
某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：
虚拟地址 20501225H 对应的页目录号、页号分别是（ ）。
【解析】题中给出的是十六进制地址，首先将它转化为二进制地址，然后用二进制地址去匹 配题中对应的地址结构。转换为进制地址和地址结构的对应关系如下所示。
2050 1225H = 0010 0000 01010000 00010010 00100101
前 10 位、11~20 位、21~32 位分别对应页目录号、页号和页内偏移。把页目录号、页号单独 拿出，转换为十六进制时缺少的位数在高位补零，0000 1000 0001、0001 0000 0001 分别对 应 081H、101H, 选项 A 正确。
32
在下列动态分区分配算法中，最容易产生内存碎片的是（ ）。
最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲 分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用 的内存块，所以最佳适应算法最容易产生最多的内存碎片，选项 C 正确。
计算机网络
33
OSI 参考模型的第 5 层（自下而上）完成的主要功能是( )
OSI 参考模型自下而上分别为物理层、数据链路层、网络层、传输层、会话层、表示 层和应用层。第 5 层为会话层，它的主要功能是管理和协调不同主机上各种进程之间的通信 （对话），即负责建立、管理和终止应用程序之间的会话，这也是会话层得名的原因。
34
100BaseT 快速以太网使用的导向传输介质是( )
100base-T 是一种以速度 100Mb/s 工作的局域网标准，它通常被称为快速以太网标 准，并使用两对 UTP 铜质电缆。100base-T：100 标识传输速度为 100Mb/s，base 标识采用 基带传输，T 表示传输介质为双绞线，当为 F 时表示光纤。
35
对于滑动窗口协议，如果分组序号采用 3 比特编号，发送窗口大小为 5，则接收窗口最大是( )
对于一般的如果要满足在窗口中发送缓存的帧序号不存在二义性，那么需要发送窗 口大小 + 接收窗口大小≤2n。例如当 n=3 时，若发送窗口大小+接收窗口大小大于帧序号数， 那么说明其容纳下的帧数已经超过了帧的序号，则对于接收方，一定会出现重复的帧号，此 时若出现故障，就不能辨别是同帧号中哪一个帧出现了丢失
36
假设一个采用 CSMA/CD 协议的 100Mbps 局域网，最小帧长是 128 B，则在一个冲突域内两个站点之间的单向传播延时最多是( )
考察 CSMA/CD 协议中最小数据帧长与单项传播时延的关系。每次发送一个数据帧， 最少需要 2τ时间才能收到其回复。因此发送一个最小数据帧的时间必须大于 2τ，再本题中 128×8/100M>=2τ，所以τ最大为 5.12us，答案为 B。
37
若将 101.200.16.0/20 划分为 5 个子网，则可能的最小子网的可分配 IP 地址数是( )
网络前缀为 20 位，将 101.200.16.0/20 划分为 5 个子网，为了保证有子网的可分配 IP 地址数尽可能小，即要让其他子网的可分配 IP 地址数尽可能大，不能采用平均划分的方 法，而要采用变长的子网划分方法，也就是最大子网用 1 位子网号，第二大子网用 2 位子网 号，以此类推。 当地址范围为 101.200.31.1/24~101.200.31.254/24 时，可分配的 IP 地址数为 254 个，即可 能的最小子网的可分配 IP 地址数是 254 个。
38
某客户通过一个 TCP 连接向服务器发送数据的部分过程如题 38 图所示。客户在 t0 时刻第一次收到确认序列号 ack_seq=100 的段，并发送序列号 seq=100 的段，但发生丢失。若 TCP 支持快速重传，则客户重新发送 seq=100 段的时刻是( )
TCP 规定当发送方收到对同一个报文段的 3 个重复的确认时，就可以认为跟在这个 被确认报文段之后的报文已经丢失，立即执行快速重传算法。t3 时刻连续收到了来自服务器的 三个确认序列号 ack_seq = 100 的段。发送方认为 seq = 100 的段已经丢失，执行快速重传 算法，重新发送 seq = 100 段。
39
若主机甲主动发起一个与主机乙的 TCP 连接，甲、乙选择的初始序列号分别为 2018 和 2046，则第三次握手 TCP 段的确认序列号是( )
根据 TCP 连接建立的“三次握手”原理，第三次握手时甲发出的确认序列号应为第二次握手时乙发出的序列号+1，即 2047。
40
下列关于网络应用模型的叙述中，错误的是( )
在 P2P 模型中，每个结点的权利和义务是对等的，在 C/S 模型中，客户是服务发起 请求，使服务器被动接受各地客户的请求，但是客户之间不能直接通信，例如 Web 应用中两 个浏览器不能直接通信，P2P 模型减轻了对某个服务器的计算压力，可以将任务分配到各个 节点，提高了系统效率和资源利用率。
解答题
数据结构
41
设线性表 采用带头结点的单链表保存，链表中的结点定义如下：
typedef struct node {
int data;
struct node *next;
} NODE;
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度。
42
请设计一个队列，要求满足：
① 初始时队列为空；
② 入队时，允许增加队列占用空间；
③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。
请回答下列问题：
(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件。
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。
组成原理
43
有 $n$（$n \ge 3$）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 $m$（$m \ge 1$）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作（wait()、signal()操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
44
某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：
(1) 磁盘的容量是多少？
(2) 假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100260、60005、101660 和 110560。若采用最短寻道时间优先 (SSTF) 调度算法，则系统访问簇的先后次序是什么？
(3) 第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？
操作系统
45
已知 f(n)=n!=n×(n-1)×(n-2)×…×2×1，计算 f(n)的 C 语言函数 f1 的源程序（阴影部分）及其在 32 位计算机 M 上的部分机器级代码如下：
int f1(int n){
1 00401000 55 push ebp
… … …
if(n>1)
1100401018 83 7D 08 01 cmp dword ptr [ebp+8],1
120040101C 7E 17 jle f1+35h (00401035)
return n*f1(n-1);
130040101E 8B 45 08 mov eax, dword ptr [ebp+8]
1400401021 83 E8 01 sub eax, 1
1500401024 50 push eax
1600401025 E8 D6 FF FF FF call f1 ( 00401000)
… … …
1900401030 0F AF C1 imul eax, ecx
2000401033 EB 05 jmp f1+3Ah (0040103a)
else return 1;
2100401035 B8 01 00 00 00 mov eax,1
}
… … …
2600401040 3B EC cmp ebp, esp
… … …
300040104A C3 ret
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M 按字节编址，int 型数据占 32 位。请回答下列问题：
(1) 计算 f(10)需要调用函数 f1 多少次？执行哪条指令会递归调用 f1？
(2) 上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？
(3) 根据第 16 行的 call 指令，第 17 行指令的虚拟地址应是多少？已知第 16 行的 call 指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？已知第 16 行的 call 指令的后 4 字节为偏移量，M 是采用大端方式还是采用小端方式？
(4) f(13)=6227020800，但 f1(13)的返回值为 1932053504，为什么两者不相等？要使 f1(13)能返回正确的结果，应如何修改 f1 的源程序？
(5) 第 19 行的 imul 指令（带符号整数乘）的功能是 R[eax]←R[eax]×R[ecx]，当乘法器输出的高、低 32 位乘积之间满足什么条件时，溢出标志 OF=1？要使 CPU 在发生溢出时转异常处理，编译器应在 imul 指令后应加一条什么指令？
46
对于上题，若计算机 M 的主存地址为 32 位，釆用分页存储管理方式，页大小为 4KB，则第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中（说明理由）？若指令 Cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块内地址？哪几位表示 Cache 组号？哪几位表示标记（tag）信息？读取第 16 行的 call 指令时，只可能在指令 Cache 的哪一组中命中（说明理由）？
计算机网络
47
某网络拓扑如题 47 图所示，其中 R 为路由器，主机 HI~H4 的 IP 地址配置以及 R 的各接口 IP 地址配置如图中所示。现有若干台以太网交换机（无 VLAN 功能）和路由器两类网络互连设备可供选择。
请回答下列问题：
(1) 设备 1、设备 2 和设备 3 分别应选择什么类型网络设备？
(2) 设备 1、设备 2 和设备 3 中，哪几个设备的接口需要配置 IP 地址？并为对应的接口配置正确的 IP 地
址。
(3) 为确保主机 H1~H4 能够访问 Internet，R 需要提供什么服务？
(4) 若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？