2019 年真题
设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。
x = 0;
while (n >= (x + 1) * (x + 1))
x = x + 1;
A. (O(n)) B. (O(\sqrt{n})) C. (O(n\log_2 n)) D. (O(\log_2 n))
[tag_link]
正确答案：B
假设第 k 次循环终止，则第 k 次执行时，(x+1)2>n，x 的初始值为 0，第 k 次判断时，x=k-1，即k2>n，k>n1/2,，因此该程序段的时间复杂度为O(n1/2)。
若将一棵树 T 转化为对应的二又树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是（ ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
[tag_link]
正确答案：B
本第一步，需要知道如何将一棵 树转化为二叉树：对于每一个结点，第一个孩子结点放左子树，其余孩子结点（即第一个孩子结点的兄弟结点）放在第一个孩子结点的右子树，其余的孩子结点再依次放在右子树的右子树，依次类推。第二步，需要知道选项中的四种遍历方式先序遍历：该结点，左子树，右子树中序遍历：左子树，该结点，右子树后序遍历：左子树，右子树，该节点层次遍历：队列实现前 3 种遍历方式，左子树都是先于右子树，“先”、“中”、“后”指的是访问该结点的次序，对于上图，我们发现，对树的后序遍历与对二叉树的中序遍历相同，选 B。
对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是（ ）。
A. 56 B. 57 C. 58 D. 60
[tag_link]
正确答案：C
哈夫曼树 是一颗带权路径长度最短二叉树，有性质：n 个叶子结点的哈夫曼树，共 2n-1 个结点 2n-1 = 115 解得 n = 58，选 C。
在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树 T2 ，再将 v 插入 T2 形成平衡二叉树 T3 。下列关于 T1 与 T3 的叙述中，正确的是（ ）。
I.若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同
II.若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同
III.若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同
A. 仅 I B. 仅 II C. 仅 I、II D. 仅 I、III
[tag_link]
正确答案：A
非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。若删除的是 T1 的叶结点，则删除后平衡二叉树不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树 T1 与 T3 相同;若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树 T3 与 T1 可能不同。I 正确。例如，如下图所示，删除结点 0，平衡二叉树失衡调整，再插入结点 0 后，平衡二叉树和以前不同。对于比较绝对的说法 II 和 III，通常只需举出反例即可。
若删除的是 T1 的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整 (这时可以首先想到删除的结点只有一个孩子的情况)，则该结点从非叶结点变成了叶结点，T1 与 T3 显然不同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树和以前不同。
若删除的是 T1 的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，T1 与 T3 相同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。
下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是（ ）。
A. 3 和 7 B. 12 和 12 C. 12 和 14 D. 15 和 15
[tag_link]
正确答案：C
AOE 网
是以边表示活动的有向无环网。活动 d 的弧尾事件必须等待所有前驱活动完成，其最早时间为 max{a, b+c}=max{3,4+8}=12。工程工期（源点到汇点的最长路径）为 27；由汇点逆推，d 的弧头事件最迟发生时间为 27-g=27-6=21，所以活动 d 最迟开始时间为 21-d=21-7=14。因此最早/最迟开始时间为 12 和 14，选 C。
用有向无环图描述表达式 (x+y)*((x+y)/x)，需要的顶点个数至少是（ ）。
A. 5 B. 6 C. 8 D. 9
[tag_link]
正确答案：A
把相同的变量和公共子表达式只存一次：叶结点 x、y 各 1 个，x+y 共用 1 个加法结点，再加除法结点和最外层乘法结点，共 2+1+1+1=5 个顶点。不能把两处 x+y 分别建树，也不能把两处 x 分开存储，因此最少为 5，选 A。对应 DAG 如下：
选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是（ ）。
Ⅰ.数据的规模 Ⅱ.数据的存储方式 Ⅲ.算法的稳定性 Ⅳ.数据的初始状态
A. 仅Ⅲ B. 仅Ⅰ、Ⅱ C. 仅Ⅱ、Ⅲ、Ⅳ D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
[tag_link]
正确答案：D
当数据规模较小时可选择是复杂度为O(n2)的简单排序算法，当数据规模较大时应选择复杂度为O(nlog2 n)的排序方法，当数据规模大到内存无法放下时需选择外部排序方法，Ⅰ 正确。数据的存储方式主要分为顺序存储和链式存储，有些排序方法（如堆排序）只能用于顺序存储方式，Ⅱ 正确。若对数据稳定性有要求，则不能选择不稳定的排序方法，Ⅲ 显然正确。当数据初始基本有序时，直接插入排序的效率最高，冒泡排序和直接插入排序的时间复杂度都是O(n)，而归并排序的时间复杂度依旧是O(nlog2 n)，Ⅳ 正确。所以选 D。
现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是（ ）。
A. 4 B. 5.25 C. 6 D. 6.29
[tag_link]
正确答案：C
构造
散列表
只有当遇到关键字为空的地址时才会查找失败，key%7 之后，初始地址只可能在 06，所以即 06 到空地址的距离求平均，即为查找失败的平均查找长度初始地址是 0 的失败查找长度为 9，同理得初始地址为 1，2，3，4，5，6 的失败查找长度为 8，7，6，5，4，3，(9+8+7+6+5+4+3)/7 = 6 答案是 C。
设主串 T=“abaabaabcabaabc”，模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。
A. 9 B. 10 C. 12 D. 15
[tag_link]
正确答案：B
假设位序都是从 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。
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（ ）。
A. 5，2，16，12，28，60，32，72 B. 2，16，5，28，12，60，32，72 C. 2，12，16，5，28，32，72，60 D. 5，2，12，28，16，32，72，60
[tag_link]
正确答案：D
快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列，基准左边都比基准小，右边都比基准大。排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”，故快速排序第一趟被枢轴分成的 两个子序列 在第二趟中应该 各放一个枢轴 在最终位置（也即如果第一趟的枢轴在中间，第二趟应该至少有 3 个元素在最终位置），如果枢轴的位置正好在首端或尾端，那第一趟就只被分成了 一个序列，那第二趟只能放 一个枢轴 在最终位置（也即如果枢轴在首尾，第二趟应该至少有 2 个元素在最终位置）
- A 中，第一次快排选的基准值是 72，第二次的基准值是 28。
- B 中，第一次的基准值是 72，第二次的是 2。
- C 中，第一次的基准值是 28，第二次的基准值是 2 和 32。所以答案选择 D。
设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是（ ）。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：B
在 12 路归并树中只存在度为 0 和度为 12 的结点，设度为 0 的结点数、度为 12 的结点数和要补充的结点数分别为n0，n12，n补，则有n0 =120+n补，n0 =(12−1)n12 +1，可得n12 =(120−1+n补 )/(12−1)。由于结点数n12为整数，所以 n 补是使上式整除的最小整数，求得n补 =2，所以答案选 B。
下列关于冯 ·诺依曼结构计算机基本思想的叙述中，错误的是()。
A. 程序的功能都通过中央处理器执行指令实现 B. 指令和数据都用二进制表示，形式上无差别 C. 指令按地址访问，数据都在指令中直接给出 D. 程序执行前，指令和数据需预先存放在存储器中
[tag_link]
正确答案：C
冯·诺依曼计算机 的功能部件包括输入设备、输出设备、存储器、运算器和控制器，程序的功能都通过中央处理器（运算器和控制器）执行指令，A 正确。指令和数据以同等地位存于存储器内，形式上无差别，只在程序执行时具有不同的含义，B 正确。指令在地址访问，数据由指令的地址码指出，除立即寻址，数据均存放在存储器内，C 错误。在程序执行前，指令和数据需预先存放在存储器中，中央处理器可以从存储器存取代码，D 正确。
考虑以下C 语言代码：
unsigned short usi = 65535; short si =usi;
执行上述程序段后，si 的 值 是 ( ) 。
A. -1 B. -32767 C. -32768 D. -65535
[tag_link]
正确答案：A
unsigned short 类型为 无符号 短整型，长度为 2 字节，因此 unsigned short usi 转换为二进制代码即 1111 1111 1111 1111。short 类型为短整型，长度为 2 字节，在采用 补码 的机器上 short si 的二进制代码为 1111 1111 1111 1111，因此 si 的值为 -1，所以选 A。
下列关于缺页处理的叙述中，错误的是()。
A. 缺页是在地址转换时CPU 检测到的一种异常 B. 缺页处理由操作系统提供的缺页处理程序来完成 C. 缺页处理程序根据页故障地址从外存读入所缺失的页 D. 缺页处理完成后回到发生缺页的指令的下一条指令执行
[tag_link]
正确答案：D
在请求分页系统中，每当要访问的页面不在内存中时，CPU 检测到异常，便会产生 缺页中断 ，请求操作系统将所缺的页调入内存。缺页处理由缺页中断处理程序完成，根据发生缺页故障的地址从外存读入所缺失的页，鋏页处理完成后回到发生缺页的指令继续执行。选项 D 中描述回到发生缺页的指令的下一条指令执行，明显错误，所以选 D。
某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234FF00H, 该操作数采用基址寻 址方式，形式地址(用补码表示)为FF12H, 基址寄存器内容为F0000000H, 则该操作数的LSB ( 最低 有效字节)所在的地址是()。
A. F000FF12H B. F000FF15H C. EFFFFF12H D. EFFFFF15H
[tag_link]
正确答案：C
注意，内存地址是无符���数。操作数采用基址寻址方式，EA=(BR)+A，基址寄存器 BR 的内容为 F000 0000H，形式地址用补码表示为 FF12H，即 1111 1111 0001 0010B，因此有效地址为 F000 0000H +(-00EEH) = EFFF FF12H。计算机采用 大端方式 编址，故低位字节存放在字的高地址处，机器数一共占 4 字节，该操作数的 LSB 所在的地址是 EFFF FF12H + 3 = EFFF FF15H，所以选 D。
下列有关处理器时钟脉冲信号的叙述中，错误的是()。
A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成 B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频 C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定 D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
[tag_link]
正确答案：D
时钟脉冲信号 的宽度称为 时钟周期 ，时钟周期是 CPU 工作的最小时间单位，时钟周期的倒数为机器主频。时钟脉冲信号是由机器脉冲源发出的脉冲信号经整形和分频后形成的，时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定。CPU 从内存中取出并执行一条指令所需的全部时间称为指令周期，指令周期又由若干机器周期来表示，一个机器周期又包含若干时钟周期，选项 D 显然错误。
某指令功能为R[r2]-R[r1]+M[R[r0]], 其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于 下列给定部件，该指令在取数及执行过程中需要用到的是()。
I. 通用寄存器组(GPRs) II. 算术逻辑单元(ALU)
II. 存储器(Memory) IV. 指令译码器(ID)
A. 仅 I、Ⅱ B. 仅 I、Ⅱ、Ⅲ C. 仅 Ⅱ、Ⅲ、IV D. 仅 I、Ⅲ、IV
[tag_link]
正确答案：B
该指令的两个源操作数分别采用 寄存器寻址 和 寄存器间接寻址 ，因此在取数阶段需要用到通用寄存器组和存储器；在执行阶段，两个源操作数相加需要用到算术逻辑单元；而指令译码器用于操作码字段进行译码，向控制器提供特定的操作信号，在取数及执行阶段用不到，所以答案选 B。
在采用“取指、译码/取数、执行、访存、写回”5段流水线的处理器中，执行如下指令序列，其中s0、 s1、s2 、s3和t2 表示寄存器编号。
//R[s2]←R[s1]+R[s0] //R[s3]+M[R[t2]+0]
//R[s2]←R[s2]+R[s3] //M[R[t2]+0]<R[s2]
I1: add s2,s 1, so
I2: load s3,0 (t2)
I3: add s2,s2,s3
I4:store s2,0(t2)
下列指令对中，不存在数据冒险的是()。
A. I1 和 I3 B. I2 和 I3 C. I2 和 I4 D. I3 和 I4
[tag_link]
正确答案：C
出这四条指令在流水线中执行的过程如下图所示：
数据冒险 指在程序中存在必须等前条指令执行完才能执行后一条指令的情况，此时这两条指令即为数据相关。其中 I1 和 I3、I2 和 I3、I3 和 I4 均发生了写后读相关，因此必须等相关的前条指令执行完才能执行后一条指令。只有 I2 和 I4 不存在数据冒险。所以答案选 C。
假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333, 即内存条所接插的存储器 总线的工作频率为1333MHz, 总线宽度为64位，则存储器总线的总带宽大约是()。
A. 10.66GB/s B. 32GB/s C. 64GB/s D. 96GB/s
[tag_link]
正确答案：B
由题目可知，计算机采用 3 通道存储器总线，存储器总线的工作频率为 1333MHz，即 1 秒内传送 1333M 次数据，总线宽度为 64 位即单条总线工作一次可传输 8 字节（Byte），因此存储器总线的总带宽 3×8×1333MB/s，约为 32GB/s，故答案选 B。
下列关于磁盘存储器的叙述中，错误的是()。
A. 磁盘的格式化容量比非格式化容量小 B. 扇区中包含数据、地址和校验等信息 C. 磁盘存储器的最小读写单位为一字节 D. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成
[tag_link]
正确答案：C
磁盘存储器 的最小读写单位为一个扇区，即磁盘按块存取，选项 C 错误。磁盘存储数据之前需进行格式化，将磁盘分成扇区，并写入信息，因此磁盘的格式化容量比非格式化容量小，选项 A 正确。磁盘扇区中包含数据、地址和校验等信息，选项 B 正确。磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成，选项 D 正确。
某设备以中断方式与CPU 进行数据交换，CPU主频为1GHz, 设备接口中的数据缓冲寄存器为32位， 设备的数据传输率为50KBps。若每次中断开销(包括中断响应和中断处理)为1000个时钟周期，则 CPU 用于该设备输入/输出的时间占整个 CPU时间的百分比最多是()。
A. 1.25% B. 2.5% C. 5% D. 12.5%
[tag_link]
正确答案：A
设备接口中的数据缓冲寄存器为 32 位，即一次 中断 可以传输 4B 数据，设备数据传输率为 50kB/s，共需要 12.5k 次中断，每次中断开销为 1000 个时钟周期，CPU 频为 1GHz，则 CPU 用于该设备输入/输出的时间占整个 CPU 时间的百分比最多是 (12.5k×1000)/1G=1.25%。
下列关于 DMA 方式的叙述中，正确的是（ ）。
I. DMA 传送前由设备驱动程序设置传送参数Ⅱ. 数据传送前由 DMA 控制器请求总线使用权Ⅲ. 数据传送由 DMA 控制器直接控制总线完成IV. DMA 传送结束后的处理由中断服务程序完成
A. 仅 I、Ⅱ B. 仅 I、Ⅲ、IV C. 仅 Ⅱ、Ⅲ、IV D. I、Ⅱ、Ⅲ、IV
[tag_link]
正确答案：D
每类设备都配置一个设备驱动程序，设备驱动程序向上层用户程序提供一组标准接口，负责实现对设备发出各种具体操作指令，用户程序不能直接和 DMA 打交道。DMA 的数据传送过程分为预处理、数据传送和后处理 3 个阶段。预处理阶段由 CPU 完成必要的准备工作，数据传送前由 DMA 控制器请求总线使用权；数据传送由 DMA 控制器直接控制总线完成；传送结束后，DMA 控制器向 CPU 发送中断请求，CPU 执行中断服务程序做 DMA 结束处理。
下列关于线程的描述中，错误的是（ ）。
A. 内核级线程的调度由操作系统完成 B. 操作系统为每个用户级线程建立一个线程控制块 C. 用户级线程间的切换比内核级线程间的切换效率高 D. 用户级线程可以在不支持内核级线程的操作系统上实现
[tag_link]
正确答案：B
应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口，内核为进程及其内部的每个线程维护上下文信息，调度也是在内核中由操作系统完成的，选项 A 正确。在多线程模型中， 用户级线程和内核级线程 的连接方式分为多对一、一对一、多对多，“操作系统为每个用户线程建立一个线程控制块”属于一对一模型，选项 B 错误。用户级线程的切换可以在用户空间完成，内核级线程的切换需要操作系统帮助进行调度，故用户级线程的切换效率更高，选项 C 正确。用户级线程的管理工作可以只在用户空间中进行，故可以在不支持内核级线程的操作系统上实现，选项 D 正确。
下列选项中，可能将进程唤醒的事件是（ ）。
Ⅰ.I/O 结束
Ⅱ.某进程退出临界区
Ⅲ.当前进程的时间片用完
A. 仅Ⅰ B. 仅Ⅲ C. 仅Ⅰ、Ⅱ D. Ⅰ、Ⅱ、Ⅲ
[tag_link]
正确答案：C
参考 进程状态转化 ，当被阻塞进程等待的某资源为可用时，进程将会被唤醒。I/O 结束后，等待该 I/O 结束而被阻塞的有关进程就会被唤醒，Ⅰ正确；某进程退出临界区后，之前因需要进入该临界区而被阻塞的有关进程就会被唤醒，Ⅱ正确，当前进程的时间片用完后进入就绪队列等待重新调度，优先级最高的进程将获得处理机资源从就绪态变成执行态，Ⅲ错误。
下列关于系统调用的叙述中，正确的是（ ）。
Ⅰ.在执行系统调用服务程序的过程中，CPU 处于内核态
Ⅱ.操作系统通过提供系统调用避免用户程序直接访问外设
Ⅲ.不同的操作系统为应用程序提供了统一的系统调用接口
Ⅳ.系统调用是操作系统内核为应用程序提供服务的接口
A. 仅Ⅰ、Ⅳ B. 仅Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ、Ⅳ D. Ⅰ、Ⅲ、Ⅳ
[tag_link]
正确答案：C
用户可以在用户态调用操作系统的服务，但执行具体的系统调用服务程序是处于内核态的，Ⅰ正确：设备管理属于操作系统的职能之一，包括对输入/输出设备的分配、初始化、维护等，用户程序需要通过系统调用使用操作系统的设备管理服务，Ⅱ正确：操作系统不同，底层逻辑、实现方式均不相同，为应用程序提供的系统调用接口也不同，Ⅲ错误：系统调用是用户在程序中调用操作系统提供的子功能，Ⅳ正确。
下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。
Ⅰ. 位图
Ⅱ. 索引结点
Ⅲ. 空闲磁盘块链
Ⅳ. 文件分配表 (FAT)
A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ、Ⅳ C. 仅Ⅰ、Ⅲ D. 仅Ⅱ、Ⅲ、Ⅳ
[tag_link]
正确答案：B
传统的文件系统 管理空间磁盘的方法 包括空闲表法、空闲链表法、位示图和成组链接法，Ⅰ、Ⅲ 正确。文件分配表（FAT）的表项与物理磁盘块一一对应，并且可以用一个特殊的数字 -1 表示文件的最后一块，用 -2 表示这个磁盘块是空闲的（当然，规定用 -3、-4 来表示也是可行的）。因此文件分配表（FAT）不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过 FAT 对文件存储空间进行管理，Ⅳ正确。索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构，存储了文件描述信息，索引结点属于文件目录管理部分的内容，Ⅱ错误。
系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法，时间片为 10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度 Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2 中的进程；新创建的进程首先进入 Q1;Q1 中的进程执行一个时间片后，若未结束，则转入 Q2。若当前 Q1，Q2 为空，系统依次创建进程 P1，P2 后即开始进程调度，P1,P2 需要的 CPU 时间分别为 30ms 和 20ms，则进程 P1，P2 在系统中的平均等待时间为（ ）。
A. 25ms B. 20ms C. 15ms D. 10ms
[tag_link]
正确答案：C
参考 多级反馈队列 。进程 P1、P2 依次创建后进入队列 Q1，根据时间片调度算法的规则，进程 P1、P2 将依次被分配 10ms 的 CPU 时间，两个进程分别执行完一个时间片后都会被转入队列 Q2，就绪队列 Q2 采用短进程优先调度算法，此时 P1 还需要 20ms 的 CPU 时间，P2 还需要 10ms 的 CPU 时间，所以 P2 会被优先调度执行，10ms 后进程 P2 执行完成，之后 P1 再调度执行，再过 20ms 后 P1 也执行完成。平均等待时间 = (P1 等待时间 + P2 等待时间) / 2 = (20 + 10) / 2 = 15。
在分段存储管理系统中，用共享段表描述所有共享的段。若进程 P1 和 P2 共享段 S，下列叙述中，错误的是（ ）。
A. 在物理内存中仅保存一份段 S 的内容 B. 段 S 在 P1 和 P2 中应该具有相同的段号 C. P1 和 P2 共享段 S 在共享段表中的段表项 D. P1 和 P2 都不再使用段 S 时才回收段 S 所占的内存空间
[tag_link]
正确答案：B
本题考察 段式管理 。段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的，因此在内存中仅保存一份段 s 的内容。选项 A 正确。段 S 对于进程 P1，P2 来说，使用位置可能不同，所以在不同进程中的逻辑段号可能不同，选项 B 错误。段表项存放的是段的物理地址，对于共享段 S 来说物理地址唯一，选项 C 正确。为了保证进程可以顺利使用段 S，段 S 必须确保在没有任何进程使用它后才能被删除，选项 D 正确。
某系统采用 LRU 页置换算法和局部置换策略，若系统为进程 P 预分配了 4 个页框，进程 P 访问页号的序列为 0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6，则进程访问上述页的过程中，产生页置换的总次数是（ ）。
A. 3 B. 4 C. 5 D. 6
[tag_link]
正确答案：C
LRU 每次执行页面置换时会换出最近最久没有使用过的页面。第一次访问 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 |
| 物理块 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | |
| 物理块 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 7 | 7 | ||
| 物理块 | 7 | 7 | 7 | 7 | 7 | 7 | 2 | 2 | 2 | |||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
需要注意的是：题中问的是页置换算法，而不是缺页次数，所以前 4 次缺页未还也的操作不考虑在内，答案为 5 次，故选 C。
下列关于死锁的叙述中，正确的是（ ）。
Ⅰ、可以通过剥夺进程资源解除死锁
Ⅱ、死锁的预防方法能确保系统不发生死锁
Ⅲ、银行家算法可以判断系统是否处于死锁状态
Ⅳ、当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
A. 仅Ⅱ、Ⅲ B. 仅Ⅰ、Ⅱ、Ⅳ C. 仅Ⅰ、Ⅱ、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ
[tag_link]
正确答案：B
本题考察 死锁 相关知识。剥夺进程资源，将其分配给其他死锁进程，可以解除死锁，Ⅰ正确。死锁预防是死锁处理策略（死锁预防、死锁避免、死锁检测）中最为严苛的一种策略，破坏死锁产生的 4 个必要条件之一。可以确保系统不发生死锁，Ⅱ正确。银行家算法是一种死锁避免算法，用于计算动态资源分配的完全性以避免系统进入死锁状态，不能用于判断系统是否处于死锁，Ⅲ错误。通过简化资源分配图可以检测系统是否为死锁状态，当系统出现死锁时，资源分配图不可完全简化。只有两个成两个以上的进程才会出现“环”而不能被简化，Ⅳ正确。
某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：
虚拟地址 20501225H 对应的页目录号、页号分别是（ ）。
A. 081H、101H B. 081H、401H C. 201H、101H D. 201H、401H
[tag_link]
正确答案：A
题中给出的是十六进制地址，首先将它转化为二进制地址，然后用二进制地址去匹配题中对应的地址结构。转换为进制地址和地址结构的对应关系如下所示。2050 1225H = 0010 0000 01010000 00010010 00100101前 10 位、1120 位、2132 位分别对应页目录号、页号和页内偏移。把页目录号、页号单独拿出，转换为十六进制时缺少的位数在高位补零，0000 1000 0001、0001 0000 0001 分别对应 081H、101H，选项 A 正确。
在下列动态分区分配算法中，最容易产生内存碎片的是（ ）。
A. 首次适应算法 B. 最坏适应算法 C. 最佳适应算法 D. 循环首次适应算法
[tag_link]
正确答案：C
最佳适应 算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用的内存块，所以最佳适应算法最容易产生最多的内存碎片，选项 C 正确。
OSI 参考模型的第 5 层（自下而上）完成的主要功能是（ ）
A. 差错控制 B. 路由选择 C. 会话管理 D. 数据表示转换
[tag_link]
正确答案：C
OSI 参考模型 自下而上分别为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。第 5 层为会话层，它的主要功能是管理和协调不同主机上各种进程之间的通信（对话），即负责建立、管理和终止应用程序之间的会话，这也是会话层得名的原因。
100BaseT 快速以太网使用的导向传输介质是（ ）。
A. 双绞线 B. 单模光纤 C. 多模光纤 D. 同轴电缆
[tag_link]
正确答案：A
参考 以太网传输介质 ：100base-T 是一种以速度 100Mb/s 工作的局域网标准，它通常被称为快速以太网标准，并使用两对铜质电缆。100base-T：100 标识传输速度为 100Mb/s，base 标识采用基带传输，T 表示传输介质为双绞线，当为 F 时表示光纤。
对于滑动窗口协议，如果分组序号采用 3 比特编号，发送窗口大小为 5，则接收窗口最大是（ ）。
A. 2 B. 3 C. 4 D. 5
[tag_link]
正确答案：B
对于一般的如果要满足在窗口中发送缓存的帧序号不存在二义性，那么需要满足 窗口大小限制 ：发送窗口大小 + 接收窗口大小 ≤2n。例如当 n=3 时，若发送窗口大小 + 接收窗口大小大于帧序号数，那么说明其容纳下的帧数已经超过了帧的序号，则对于接收方，一定会出现重复的帧号，此时若出现故障，就不能辨别是同帧号中哪一个帧出现了丢失
假设一个采用 CSMA/CD 协议的 100Mbps 局域网，最小帧长是 128 B，则在一个冲突域内两个站点之间的单向传播延时最多是（ ）。
A. 2.56 us B. 5.12 us C. 10.24 us D. 20.48 us
[tag_link]
正确答案：B
本题考察 CSMA/CD 协议中的 限制条件 ：每次发送一个数据帧，最少需要 2τ时间才能收到其回复。因此发送一个最小数据帧的时间必须大于 2τ，再本题中 128×8/100M>=2τ，所以 τ 最大为 5.12us，答案为 B。
若将 101.200.16.0/20 划分为 5 个子网，则可能的最小子网的可分配 IP 地址数是（ ）。
A. 126 B. 254 C. 510 D. 1022
[tag_link]
正确答案：B
本题考察 变长子网划分 。网络前缀为 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 个。
某客户通过一个 TCP 连接向服务器发送数据的部分过程如题 38 图所示。客户在t0时刻第一次收到确认序列号 ack_seq=100 的段，并发送序列号 seq=100 的段，但发生丢失。若 TCP 支持快速重传，则客户重新发送 seq=100 段的时刻是（ ）。
A. (t_0) 时刻 B. 收到一个重复确认时 C. 收到三个重复确认时 D. 超时重传时
[tag_link]
正确答案：C
TCP 规定当发送方收到对同一个报文段的 3 个重复的确认时，就可以认为跟在这个被确认报文段之后的报文已经丢失，立即执行 快速重传 算法。t3 时刻连续收到了来自服务器的三个确认序列号 ack_seq = 100 的段。发送方认为 seq = 100 的段已经丢失，执行快速重传算法，重新发送 seq = 100 段。
若主机甲主动发起一个与主机乙的 TCP 连接，甲、乙选择的初始序列号分别为 2018 和 2046，则第三次握手 TCP 段的确认序列号是（ ）。
A. 2018 B. 2019 C. 2046 D. 2047
[tag_link]
正确答案：D
根据 TCP 连接建立的 三次握手 原理，第三次握手时甲发出的确认序列号应为第二次握手时乙发出的序列号 +1，即 2047。
下列关于网络应用模型的叙述中，错误的是（ ）。
A. 在 P2P 模型中，结点之间具有对等关系 B. 在客户/服务器 (C/S) 模型中，客户与客户之间可以直接通信 C. 在 C/S 模型中，主动发起通信的是客户，被动通信的是服务器 D. 在向多用户分发一个文件时，P2P 模型通常比 CIS 模型所需时间短
[tag_link]
正确答案：B
在 P2P 模型 中，每个结点的权利和义务是对等的，在 C/S 模型中，客户是服务发起请求，使服务器被动接受各地客户的请求，但是客户之间不能直接通信，例如 Web 应用中两个浏览器不能直接通信，P2P 模型减轻了对某个服务器的计算压力，可以将任务分配到各个节点，提高了系统效率和资源利用率。
设线性表L=(a1 ,a2 ,a3 ,⋯,an−1 ,an−1 ,an )采用带头结点的单链表保存，链表中的结点定义如下：
typedef struct node {
int data;
struct node *next;
} NODE;
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L′=(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度。
[tag_link]
1）算法的基本设计思想：先观察 L(a1 ,a2 ,a3 ,⋯,an−2 ,an−1 ,an) 和 L’(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)，发现 L’ 是由 L 摘取第一个元素，再摘取倒数第一个元素⋯依次合并而成的。为了方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。
2）算法实现如下：
// 找到链表的中间结点
NODE *findMiddleNode(NODE *head) {
NODE *slow = head;
NODE *fast = head;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
fast = fast->next;
}
slow = slow->next;
}
return slow;
}
// 反转链表
NODE *reverse(NODE *start) {
NODE *p = start;
NODE *q = start->next;
while (q != NULL) {
NODE *tmp = q->next;
q->next = p;
p = q;
q = tmp;
}
return p;
}
// 1. 找到中位结点
// 2. 翻转后一半链表
// 3. 遍历两个链表，依次穿插所有结点
void solve(HEAD *head) {
if (head->next == NULL) {
return;
}
NODE *middle = findMiddleNode(head);
NODE *list2 = reverse(middle);
NODE *list1 = head->next;
// 穿插操作
NODE *p = list1;
NODE *q = list2;
// 退出循环的条件
// 链表长度为奇数：p == q
// 链表长度为偶数：p->next == q
// while (!(p == q || p->next == q))
while (p != q && p->next != q) {
NODE *tmp1 = p->next;
NODE *tmp2 = q->next;
p->next = q;
q->next = tmp1;
p = tmp1;
q = tmp2;
}
}
3）第 1 步找中间结点的时间复杂度为 O(n)，第 2 步逆置的时间复杂度为 O(n)，第 3 步合并链表的时间复杂度为 O(n)，所以该算法的时间复杂度为 O(n)。
请设计一个队列，要求满足：
① 初始时队列为空；
② 入队时，允许增加队列占用空间；
③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。
请回答下列问题：
(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件。
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。
[tag_link]
1）顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求①容易满足；链式存储方便开辟新空间，要求②容易满足；对于要求③，出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为 O(1)，要求④可以满足。因此，采用链式存储结构（两段式单向循环链表），队头指针为 front，队尾指针为 rear。
2）该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。初始时，创建只有一个空闲结点的循环单链表，头指针 front 和尾指针 rear 均指向空闲结点，如下图所示。
队空的判定条件：front == rear。队满的判定条件：front == rear->next。
3）插入第一个元素后的状态如下图所示。4)操作的基本过程：入队操作
if (front == rear->next)
则在 rear 后面插入一个新的空闲结点；
入队元素保存到 rear 所指结点中；rear=rear->next；返回。
出队操作
if（front==rear） // 队空
则出队失败，返回；
取 front 所指结点中的元素 e；front=front->next；返回 e。
有 n（n ≥ 3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m ≥ 1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作（wait()、signal() 操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
[tag_link]
回顾传统的哲学家就餐问题，假设餐桌上有 n 个哲学家、根筷子，那么可以用这种方法避免死锁：限制至多允许 n-1 个哲学家同时“抢”筷子，那么至少会有 1 个哲学家可以获得两根筷子并顺利进餐，于是不可能发生死锁的情况。本题可以用碗这个限制资源来避免死锁：当碗的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m，确保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量大于等于哲学家的数量时，为了让碗起到同样的限制效果，我们让碗的资源量等于 -1，这样就能保证最多只有 n-1 个哲学家同时进餐，所以得到碗的资源量为 min{n-1, m}。在进 PV 操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。具体过程如下：
// 限制哲学家能同时拿到盘子的数量
semaphore fork[n] = {1};
// 并发盘子数量 < n
semaphore plate = min(m, n-1);
philosopher(int i) {
while (1) {
think();
P(plate);
P(fork[i]);
P(fork[(i + 1) % n]);
eat();
V(fork[i]);
V(fork[(i + 1) % n]);
V(plate);
}
}
某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：
(1) 磁盘的容量是多少？
(2) 假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100260、60005、101660 和 110560。若采用最短寻道时间优先 (SSTF) 调度算法，则系统访问簇的先后次序是什么？
(3) 第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？
[tag_link]
1）磁盘容量 = 磁盘的柱面数每个柱面的磁道数每个磁道的扇区数每个扇区的大小 =(300×10×200×512/1024)KB=3×105KB。
2）磁头在 85 号柱面上，对 SSTF 算法而言，总是访问当前柱面距离最近的地址。注意每个簇包含 2 个扇区，通过计算得到，85 号柱面对应的簇号为 85000～85999。通过比较得出，系统最先访问离 85000～85999 最近的 100260，随后访问离 100260 最近的 101660，然后访问 110560，最后访问 60005。顺序为 100260、101660、110560、60005。
3）参考 CHS 地址，第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁道号、扇区号构成。柱面号= ⌊簇号/每个柱面的簇数⌋ = ⌊100530/(10×200/2)⌋ = 100。磁道号 = ⌊(簇号%每个柱面的簇数)/每个磁道的簇数⌋ = ⌊530/(200/2)⌋ = 5。扇区号 = 扇区地址%每个磁道的扇区数 = (530×2) % 200 = 60。将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。
已知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)
11 00401018 83 7D 08 01 cmp dword ptr [ebp+8],1
12 0040101C 7E 17 jle f1+35h (00401035)
return n*f1(n-1);
13 0040101E 8B 45 08 mov eax, dword ptr [ebp+8]
14 00401021 83 E8 01 sub eax, 1
15 00401024 50 push eax
16 00401025 E8 D6 FF FF FF call f1 ( 00401000)
... ... ...
19 00401030 0F AF C1 imul eax, ecx
20 00401033 EB 05 jmp f1+3Ah (0040103a)
else return 1;
}
21 00401035 B8 01 00 00 00 mov eax,1
... ... ...
26 00401040 3B EC cmp ebp, esp
... ... ...
30 0040104A 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 指令后应加一条什么指令？
[tag_link]
1）计算 f(10) 需要调用函数 f1 共 10 次，执行第 16 行的 call 指令会递归调用 f1。
2）第 12 行的 jle 指令是条件转移指令，其含义为小于等于时转移，本行代码的意义为：当 n≤1 时，跳转至地址 0040 1035H。第 16 行的 call 指令为函数调用指令，第 20 行的 jmp 指令为无条件转移指令，第 30 行的 ret 指令为子程序的返回指令，这三条指令一定会使程序跳转执行。
3）其长度计算机 M 上按字节编址，第 16 行的 call 指令的虚拟地址为 0040 1025H，长度为 5 字节，故第 17 行的指令的虚拟地址为 0040 1025H + 5 = 0040 102AH。第 16 行的 call 指令采用相对寻址方式，即目标地址 = (PC) +偏移量，call 指令的目标地址为 0040 1000H，所以偏移量 = 目标地址 - (PC) = 0040 1000H - 0040 102AH = FFFF FFD6H。根据第 16 行的 call 指令的偏移量字段为 D6 FF FF FF，可以确定 M 采用小端方式。
4）因为 f(13) = 6227020800，其结果超出了 32 位 int 型数据可表示的最大范围，因此 f(13) 的返回值是一个发生了溢出的错误结果。为使 f1(13) 能返回正确结果，可将函数 f1 的返回值类型改为 double（或 long long，或 long double，或 float）类型。
5）若乘积的高 33 位为非全 0 或非全 1，则 OF=1。编译器应在 imul 指令后加一条“溢出自陷指令”，使得 CPU 自动查询溢出标志 OF，当 OF=1 时调出“溢出异常处理程序”。
对于上题，若计算机 M 的主存地址为 32 位，釆用分页存储管理方式，页大小为 4KB，则第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中（说明理由）？若指令 Cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块内地址？哪几位表示 Cache 组号？哪几位表示标记（tag）信息？读取第 16 行的 call 指令时，只可能在指令 Cache 的哪一组中命中（说明理由）？
[tag_link]
因为页大小为 4KB，所以虚拟地址的高 20 位为虚拟页号。第 1 行的 push 指令和第 30 行的 ret 指令的虚拟地址的高 20 位都是 00401H，因此两条指令在同一页中。指令 Cache 有 64 块，采用 4 路组相联映射方式，故指令 Cache 共有 64/4 = 16 组，Cache 组号共 4 位。主存块大小为 64B，故块内地址为低 6 位。综上所述，在 32 位主存地址中，低 6 位为块内地址，中间 4 位为组号，高 22 位为标记。因为页大小为 4KB，所以虚拟地址和物理地址的最低 12 位完全相同，因而 call 指令虚拟地址 0040 1025H 中的 025H = 0000 0010 0101B 为物理地址的低 12 位，对应的 7～10 位为组号，故对应的 Cache 组号为 0。
某网络拓扑如题 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 数据报，网络中哪几个主机会接收该数据报？
[tag_link]
1）以太网交换机（无 VLAN 功能）连接的若干 LAN 仍然是一个网络（同一个广播域），路由器可以连接不同的 LAN、不同的 WAN 或把 WAN 和 LAN 互联起来，隔离了广播域。IP 地址 192.168.1.2/26 与 192.168.1.3/26 的网络前缀均为 192.168.1.0，视为 LAN1。IP 地址 192.168.1.66/26 与 192.168.1.67/26 的网络前缀均为 192.168.1.64，视为 LAN2。所以设备 1 为路由器，设备 2、3 为以太网交换机。
2）设备 1 为路由器，其接口应配置 IP 地址。IF1 接口与路由器 R 相连，其相连接口的 IP 地址为 192.168.1.253/30，253 的二进制表示形式为 11111101，故 IF1 接口的网络前缀也应为 192.168.1.111111，已分配 192.168.1.253，去除全 0 全 1，IF1 接口的 IP 地址应为 192.168.1.254。LAN1 的默认网关为 192.168.1.1，LAN2 的默认网关为 192.168.1.65，网关的 IP 地址是具有路由功能的设备的 IP 地址，通常默认网关地址就是路由器中的 LAN 端口地址，设备 1 的 IF2、IF3 接口的 IP 地址分别设置为 192.168.1.1 和 192.168.1.65。
3）私有地址段：C 类 192.168.0.0~192.168.255.255，即 H1～H4 均为私有 IP 地址，若要能够访问 Internet，R 需要提供 NAT 服务，即网络地址转换服务。
4）主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，主机号全为 1，为本网络的广播地址，由于路由器可以隔离广播域，只有主机 H4 会接收到数据报。