方法一：模拟

先模拟出进栈、退栈操作序列，然后检查是否出现连续三次进行退栈操作，题目明确要求“不允许连续三次进行退栈操作”。

A选项：a进栈，b进栈，c进栈，d进栈，d出栈，c出栈，e进栈，e出栈，b出栈，f进栈，f出栈，a出栈。没有出现连续三次进行出栈操作，正确。

B选项：a进栈，b进栈，c进栈，c出栈，b出栈，d进栈，d出栈，a出栈，e进栈，e出栈，f进栈，f出栈。没有出现连续三次进行出栈操作，正确。

C选项：a进栈，b进栈，b进栈，c进栈，c出栈，a出栈，d进栈，e进栈，e出栈，f进栈，f出栈，d出栈。没有出现连续三次进行出栈操作，正确。

D选项：a进栈，a出栈，b进栈，c进栈，d进栈，e进栈，f进栈，f出栈，e出栈，d出栈，c出栈，b出栈。出现连续五次出栈操作，错误。

本题选D。

方法二：观察选项

栈的性质为先进后出，序列a, b, c, d, e, f反转为序列f, e, d, c, b, a，如果出现连续三次进行出栈操作，则一定出现长度大于或等于 3 的f, e, d, c, b, a的子序列，D选项出现了f, e, d, c, b，长度大于 3。

本题选D。

为了方便下面表述，仅能进行入队操作的一端称为A端，既能进行入队操作又能进行出队操作的一端称为B端。

方法一：模拟

按照a, b, c, d, e依次入队的顺序进行模拟。

A选项：a从A端入队，b从B端入队，c从A端入队，d从A端入队，e从A端入队，b, a, c, d, e依次从B端出队。

B选项：a从A端入队，b从B端入队，c从A端入队，d从B端入队，e从A端入队，d, b, a, c, e依次从B端出队。

C选项：a从A端入队，无法继续执行，错误。

D选项：a从A端入队，b从B端入队，c从B端入队，d从A端入队，e从B端入队，e, c, b, a, d依次从B端出队。

本题选C。

方法二：栈+队列

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，这是一个输出受限的双端队列，当然命题组为了降低难度，没有给出专业术语，根据描述就知道如何操作，这样就是一个一个模拟。

当然，由于这个双端队列两端都能操作，模拟难度极大，这时候我们需要进行简化。

简化思路一：既能进行入队操作又能进行出队操作的一端视为一个完整的栈，仅能进行入队操作的一端用于插入元素。即简化为栈+插入。

栈是先进后出的数据结构，如果所有元素入栈后出栈，得到的是输入序列的逆序序列。

简化思路二：仅能进行入队操作的一端视为队列的尾部，既能进行入队操作又能进行出队操作的一端中具有出队功能的部分视为队列的头部，这样得到一个完整的队列，既能进行入队操作又能进行出队操作的一端中具有入队功能的部分用于插入元素。即简化为队列+插入。

队列是先进先出的数据结构，得到的是输出序列与输入序列一致。

由于这道题要求元素全部入队后进行操作，可以简化为栈+队列。如图(a)所示。

栈部分的子序列先出队，形成一个逆序子序列，队列部分的子序列后出队，形成一个顺序子序列。如图(b)所示。

A选项：a, c, d, e是a, b, c, d, e的顺序子序列，a, c, d, e从A端入队，b是a, b, c, d, e的逆序子序列，b从B端入队，得到序列为 b,a,c,d,e 。正确。

B选项：a, c, e是a, b, c, d, e的顺序子序列，a, c, e从A端入队，d, b是a, b, c, d, e的逆序子序列，b, d从B端入队，得到序列为 d,b,a,c,e 。正确。

C选项：a, e是a, b, c, d, e的子序列，a, e从A端入队，d, b, c不是a, b, c, d, e的逆序子序列，错误。

D选项：a, d是a, b, c, d, e的子序列，a, d从A端入队，e, c, b是a, b, c, d, e的逆序子序列，b, c, e从B端入队，得到序列为 e,c,b,a,d 。正确。

本题选C。

方法三：找规律

入队序列a, b, c, d, e转化为下标序列1, 2, 3, 4, 5，为一个单调递增序列。

A选项：b, a, c, d, e转化为2, 1, 3, 4, 5

B选项：d, b, a, c, e转化为4, 2, 1, 3, 5

C选项：d, b, c, a, e转化为4, 2, 3, 1, 5

D选项：e, c, b, a, d转化为5, 3, 2, 1, 4

很明显，只有C选项的折线图中间有一个凸起。这个绝对不是巧合哦！本题结果序列至多由一个下标单调递减序列和一个下标单调递增序列拼接而成。C选项明显不符合要求。

本题选C。

方法一：定义

若结点 x 为根结点，则无后继；

若结点 x 为其父结点的右孩子结点，则其后继为其父结点；

若结点 x 为其父结点的左孩子结点，且父结点无右孩子结点，则其后继为其父结点；

若结点 x 为其父结点的左孩子结点，且双亲有右孩子结点，则其后继为其父结点的右子树中按后序遍历的第一个结点。

本题选D。

方法二：后序遍历

后序遍历序列与后序线索树有对应关系。

图中二叉树后序遍历序列为d, b, c, a，后序线索树中c的前驱为b，后继为a，只有D选项符合要求。

需要注意的是，结点c在后序线索树中的指向结点a的后继指针不能用二叉树原有的指针，因为这里采用的是孩子表示法，原有指针是从a指向c的。

本题选D。

将平衡二叉树（AVL树）调整平衡的方法主要有旋转法和中序遍历法。

旋转法

观察插入不平衡结点的在所在子树上的路径：

• 先经过一个左指针，再经过一个左指针，对应LL平衡旋转。LL平衡旋转为右单旋转。
• 先经过一个右指针，再经过一个右指针，对应RR平衡旋转。RR平衡旋转为左单旋转。
• 先经过一个左指针，再经过一个右指针，对应LR平衡旋转。LR平衡旋转为先左后右双旋转。
• 先经过一个右指针，再经过一个左指针，对应RL平衡旋转。RL平衡旋转为先右后左双旋转。

本题出现RL平衡旋转。先R旋，再L旋。

中序遍历法

下面介绍中序遍历法，标记出插入不平衡结点从所在子树上的根结点到插入结点路径上的3个元素，写出子树的中序遍历序列，先标记3个元素为橙色，再标记3个橙色元素中间元素为红色，红色元素即为子树新的根结点，左边橙色元素为左子树根结点，右边橙色元素为右子树根结点。

在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24和53。

本题选C。

在一棵树中， 点数边数点数=边数+1 ，设树度为 m ，度为 i 的结点数为 ni ，有 

由题意：

解得： n0=82

本题选B。

哈夫曼树不一定是完全二叉树，A选项错误。

哈夫曼树中只有度为 0 或 2 的结点，一定没有度为 1 的结点，B选项正确。

构造哈夫曼树时，先选出两个权值最小的结点进行构造，所以树中两个权值最小的结点一定是兄弟结点，C选项正确。

用反证法，如果哈夫曼树中某一非叶结点的下一层存在某一结点的权值大于该非叶结点的权值，则可以将两种进行替换使得这棵树的带权路径长度变得更低，由于哈夫曼树是带权路径最小的二叉树，矛盾。D选项正确。

本题选A。

参考答案：C

答案解析：考查图的连通性。

要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G的任意六个结点构成完全连通子图 G1，需 15 条边，然后再添一条边将第 7 个结点与 G1 连接起来，共需 16 条边。

每次选择入度为 0 的结点剥离并输出。

可以得到 3 个不同的输出序列。

本题选B。

方法一：二叉搜索树

可以画出对应的二叉搜索树。

明显走到最深的下标为 32 或 33 的失败结点，路径长度为 5 ，需要和下标为 1,2,4,8,16 的结点进行比较。

本题选B。

方法二：公式法

若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 n ，

二叉搜索树高度为

代入 n=16 ，解得 h=5 。

本题选B。

参考答案：D

答案解析：考查快速排序。

递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。

参考答案：A

答案解析：考查各种排序算法的过程。

看第一趟可知仅有 88 被移到最后.

如果是希尔排序，则 12，88，10 应变为 10，12，88。因此排除希尔排序。

如果是归并排序，则应长度为 2 的子序列是有序的，由此可排除归并。

如果是基数排序，则 16，5，10 应变为 10，5，16，由此排除基数。

可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。

参考答案：D

Ⅰ.CPU 的时钟频率，也就是 CPU 主频率，一般说来，一个时钟周期内完成的指令数是固定的，所以主频越高，CPU 的速度也就快，程序的执行时间就越短。

Ⅱ.数据在功能部件之间传送的路径称为数据通路，数据通路的功能是实现 CPU 内部的运算器和寄存器以及寄存器之间的数据交换。优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行。

Ⅲ.计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到更优的指令序列，从而使得程序的执行时间也越短

参考答案：B

考查定点数的运算。

用补码表示时 8 位寄存器所能表示的整数范围为-128~+127。由于 r1 = -2，r2 = -14，r3 = -112，r4 = -8，则 r2×r3 = 1568，结果溢出。

参考答案：B

考查不同精度的数在计算机中的表示方法及其相互装换。由于（int）f=1，小数点后面 4 位丢失，故 II 错。IV 的计算过程是先将 f 转化为双精度浮点数据格式，然后进行加法运算，故（d+f）-d 得到的结果为双精度浮点数据格式，而 f 为单精度浮点数据格式，故 IV错。

参考答案：D

考查存储器的组成和设计。用 2K×4 位的芯片组成一个 8K×8 位存储器，每行中所需芯片数为 2，每列中所需芯片数为 4，各行芯片的地址分配为：

第一行（2个芯片并联） 0000H~07FFH

第二行（2个芯片并联） 0800H~0FFFH

第三行（2个芯片并联） 1000H~17FFH

第四行（2个芯片并联） 1800H~1FFFH

于是地址0B1FH 所在芯片的最小地址即为0800H。

参考答案：A

考查半导体随机存取存储器。一般 Cache 采用高速的 SRAM 制作，比 ROM 速度快很多，因此 III 是错误的，排除法即可选 A。RAM 需要刷新，而 ROM 不需要刷新。

参考答案：D

考查 TLB、Cache 及 Page 之间的关系。TLB 即为快表，快表只是慢表（Page）的小小副本，因此 TLB 命中，必然 Page 也命中，而当 Page命中，TLB 则未必命中，故 D 不可能发生；而 Cache 的命中与否与 TLB、Page 的命中与否并无必然联系。

参考答案：B

考查 CPU 内部寄存器的特性。汇编程序员可以通过指定待执行指令的地址来设置 PC 的值，而 IR，MAR，MDR 是 CPU 的内部工作寄存器，对程序员不可见。

参考答案：A

考查指令流水线的基本概念。有三种相关可能引起指令流水线阻塞：1. 结构相关，又称资源相关；2. 数据相关；3. 控制相关，主要由转移指令引起。数据旁路技术，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿

参考答案：D

考查典型的总线标准，目前典型的总线标准有：ISA、EISA、VESA、 PCI 、PCI-Express、AGP、USB、RS-232C 等。

PCI是Peripheral Component Interconnect的缩写，即外设部件互连标准，它是个人电脑中使用最为广泛的接口，几乎所有的主板产品上都带有这种插槽。

USB是Universal Serial Bus的缩写，是一种串口总线标准，被广泛地应用于个人电脑和移动设备等信息通讯产品，并扩展至摄影器材、数字电视（机顶盒）、游戏机等其它相关领域。

EISA是Enhanced Industry Standard Architecture的缩写，是一个为IBM个人电脑适用计算机定制的总线标准。

ISA是Industry Standard Architecture的缩写，是为PC/AT电脑而制定的总线标准，为16位体系结构，只能支持16位的I/O设备，数据传输率大约是16MB/S。

VESA是video electronics standard association的缩写，是一种局部总线(local bus)，是针对视频显示的高数据传输率要求而产生的，因此又叫做视频局部总线(VL bus)，简称VL总线。

PCI-Express是peripheral component interconnect express的缩写，是一种高速串行计算机扩展总线标准，它原来的名称为“3GIO”，是由英特尔在2001年提出的，旨在替代旧的PCI，PCI-X和AGP总线标准。

参考答案：A

考查中断处理过程。单级中断系统中，不允许中断嵌套。中断的处理过程为：1. 关中断；2. 保存断点；3. 识别中断源；4. 保存现场；5. 中断事件处理；（开中断、执行中断服务程序、关中断）6. 恢复现场；7. 开中断；8. 中断返回。其中，1~3 步由硬件完成，4~8 由中断服务程序完成。

参考答案：D

考查显示器相关概念。刷新所需带宽 = 分辨率×色深×帧频 = 1600×1200×24b×85HZ = 3916.8Mbps，显存总带宽的 50%用来刷屏，于是需要的显存总带宽为 3916.8/0.5 = 7833.6Mbps ≈ 7834Mbps。

【答案】A

【解析】操作系统提供两类接口： 一类是命令接口（包括图形接口，即图形化的命令接 口），比如用户通过键盘命令和鼠标命令来操作计算机；另一类是程序接口，它提供一组系统调用，用户可以通过运行一些应用程序来访问操作系统的资源。

库函数是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关），目的是隐藏“访管”指令的细节，使系操作系统考研复习指导统调用更为方便、抽象。但是，库函数属于用户程序而非系统调用，是系统调用的上层。

【答案】C

【解析】用户登录成功就需要为这个用户创建进程来解释用户的各种命令操作；设备分 配由内核自动完成，不需要创建新进程；启动程序执行的目的是创建一个新进程来执行程序。

解答：

本题考察记录型信号量的定义。

对于记录型信号量的值x：

若x>0，则该信号量还有x个资源，等待队列为空。

若x=0，则该信号量没有资源，等待队列为空。

若x<0，则该信号量没有资源，等待队列中有|x|个等待该资源的进程。

我们可以将信号量资源类比为停车场车位。

若x>0，则该停车场还有x个车位，停车场入口外没有等待的车辆。

若x=0，则该停车场没有车位，停车场入口外没有等待的车辆。

若x<0，则该停车场没有车位，停车场入口外有|x|个等待的车辆。

因为信号量的当前取值为1，所以可用资源个数为1。因为当前还有可用资源数，所以等待资源的进程数只能是0。

综上，M=1，N=0。

本题选B。

【答案】A

【解析】A 中进程时间片用完，可降低其优先级以让其他进程被调度进入执行状态。B 中进程刚完成I/O ,进入就绪队列等待被处理机调度，为了让其尽快处理I/O结果，因此应提高优先级。C 中进程长期处于就绪队列，为不至于产生饥饿现象，也应适当提高优先级。D 中进程的优先级不应该在此时降低，而应在时间片用完后再降低。

方法一：Peterson算法

本题考察进程间通信与Peterson算法。算法实现互斥的主要思想在于设置了一个turn变量用于进程间的互相谦让。如果进程P0试图访问临界资源，则flag[0]=true表示P0希望访问。此时如果进程P1还未试图访问临界资源，则flag[1]在进程上一次访问完临界资源退出临界区后已设置为false。所以进程P0在直线循环判断条件时，第一个条件不满足，进程P0可以正常进入临界区，且满足互斥条件。需要考虑的是两个进程同时试图访问临界资源的情况。注意turn变量的含义：当某进程试图访问时，首先设置自己的flag变量为true，表示希望访问；但又设置turn变量为对方的进程编号，表示谦让。因为在循环判断条件中turn变量不是自己的编号时就循环等待。虽然两个进程会互相谦让一番，但是这不会造成饥饿的局面，因为turn变量会有一个最终值，所以必定有进程可以结束循环进入临界区。实际情况是，先作出谦让的进程先进入临界区，后作出谦让的进程则需要循环等待。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“您走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相“谦让”，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。

Peterson算法遵循空闲让进、忙则等待、有限等待这三个原则，未遵循让权等待原则，暂时无法进入临界区的进程会占用CPU并执行拦截进入临界区的while循环导致忙等。

本题选D。

方法二：模拟

如果没有看出这是一个Peterson算法，那么可以用更通用的方法解决该问题，即直接观察代码进行模拟。

初始时P0和P1尚未执行，均未进入临界区，如图所示。

我们先考虑P0和P1都无法进入临界区的情况，即两个拦截进入临界区while循环的判断条件均成立，则 (flag[1] && (turn == 1)) 和 (flag[0] && (turn == 0)) 均为真成立，显然 turn == 1 和 turn == 0 不可能同时成立，因此这种情况不可能出现；同理，P0和P1同时进入临界区也不可能。进程P0和进程P1至少有一个能进入临界区。很明显，进程P0和进程P1的代码具有轮换对称性，不失一般性，假设此时P0能够进入临界区，此时flag[0] = TRUE; turn = 1;一定已经执行，有 flag[0] == TRUE 且 turn == 1，观察进程P1在进入临界区前代码为flag[1] = TRUE; turn = 0;不会修改 flag[0]。因为P0能够进入临界区，则有 flag[1] && (turn == 1) 为假，即 flag[1] == FLASE 或 turn != 1 为真，只要进程P1执行 turn=0; 即可满足条件，此时P0进入临界区，P1未进入临界区，如图所示。

P0访问临界区结束后，设置flag[0] = FALSE，此时拦截进程P1进入临界区的while循环判断条件 flag[0] && (turn == 0) 为真不成立，进程P1能够进入临界区（此前已经设置 flag[1] = TRUE）。如果进程P0想在P1在访问临界区时重新访问临界区，必须满足拦截P0进入临界区while循环判断条件 flag[1] && (turn == 1) 为真不成立，在进行拦截P0进入临界区的while循环判断前需要重新执行flag[0] = TRUE; turn = 1; 加上此前进程P1设置的flag[1] = TRUE，此时拦截进程P0进入临界区的while循环判断条件 flag[0] && (turn == 0) 为真成立，P0无法进入临界区，如图所示。

该算法实现了进程P0和进程P1互斥访问临界区。

本题选D。

解答：

最佳适配算法：该算法全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。

分配过程如下图所示。

初始时主存空闲容量为55MB。

第一步分配15MB后有一个40MB的空闲分区。

第二步分配30MB后有一个10MB的空闲分区。

第三步释放15MB后有一个15MB的空闲分区和一个10MB的空闲分区。

第四步分配8MB，因为采用最佳适配算法，所以选择10MB的空闲分区分配8MB，之后有一个15MB的空闲分区和一个2MB的空闲分区。

第四步分配8MB，此时只有15MB的空闲分区能够分配8MB，所以选择15MB的空闲分区分配8MB，之后有一个9MB的空闲分区和一个2MB的空闲分区。此时主存中最大空闲分区的大小是9MB。

本题选B。

常用的动态分区分配策略有最佳适配 (Best Fit) 算法，最坏适配 (Worst Fit) 算法，首次适配 (First Fit) 算法，循环首次适配 (Next Fit) 算法。

答案：B
页大小为2^{10}B，页表项大小为2B，因此一页可以存放2^{9}个页表项，逻辑地址空间大小为2^{16}页，即共需2^16个页表项，因此需要2^{16}/2^{9}=2^{7}=128个页面保存页表项，即页目录表中包含表项的个数至少是128。

答案：C
每个磁盘索引块和磁盘数据块大小均为256B，每个磁盘索引块有256/4=64个地址项。因此，4个直接地址索引指向的数据块大小为4*256B；2个一级间接索引包含的直接地址索引数为2*(256/4)，即其指向的数据块大小为2*(256/4)*256B。1个二级间接索引包含的直接地址索引数为(256/4)*(256/4)，即其所指向的数据块大小为(256/4)*(256/4)*256B。因此，7个地址项所指向的数据块总大小为4*256+2*(256/4)*256+(256/4)*(256/4)*256=1082368B=1057KB。

解答：

设置当前工作目录是指将操作系统的当前目录更改为特定的目录，以便在执行文件操作时，系统可以更快地找到和检索文件。当应用程序需要频繁地对多个文件进行读取或写入操作时，设置当前工作目录可以提高文件检索速度。在Linux系统中，用户可以使用Shell命令cd（change directory的缩写）快速地切换到目标目录。

本题选C。

解答：

当用户在键盘上输入信息时，键盘控制器会检测到输入并触发一个中断信号，通知操作系统有键盘输入事件发生。中断处理程序会接收到键盘中断信号，并负责处理该事件。

本题选B。

本题考察计算机网络体系结构的基本概念。

网络体系结构主要关注网络的层次、每一层使用的协议以及每一层必须完成的功能。

A 属于网络体系结构所描述的内容。计算机网络体系结构必须确定网络的层次，例如 OSI 七层模型，TCP/IP 四层模型。

B 属于网络体系结构所描述的内容。计算机网络体系结构必须确定每一层使用的协议。

C 不属于网络体系结构所描述的内容。计算机网络体系结构必须确定每一层使用的协议及该协议必须完成的功能，而具体实现细节可能是多样的。

D 属于网络体系结构所描述的内容。计算机网络体系结构必须确定每一层必须完成的功能。

本题选 C。

解答：

由于不考虑传播延迟，选择主机 H1 向主机 H2 经过路由器最少的路径进行转发。显然本题选择经过上面两个路由器的路径。

因为每个分组大小为 1000 B，其中分组头大小为 20 B，所以每个每个分组可携带的数据大小为 1000 B - 20 B = 980 B，发送一个大小为 980 000 B 的文件需要 980 000 B / 980 B = 1000 个分组。

一个分组的发送时延 = 分组大小/数据传输速率 = 

画出示意图如下：

总时延 = 一个分组的发送时延 × 分组数量 + 一个分组的发送时延 × 转发次数 = 0.08 ms × 1000 + 0.08 ms × 2 = 80.16 ms。

本题选 C。

RIP 协议一种基于距离向量的路由协议。它使用跳数 (hops) 作为路径选择的指标，并且周期性地广播路由更新信息。RIP 通常通过 UDP 的端口号 520 来进行通信。

RIP 协议允许一条路径的距离至多为 15，距离为 16 相当于不可达。

根据距离矢量中包含信息<net1, 16>，可知路由器 R1 通过路由器 R2 到达 net1 的距离为 16，示路由器 R1 不能通过路由器 R2 到达 net1。

本题选 D。

当路由器因为拥塞而丢弃 IP 分组时，还需要向源主机发送源点已知源点抑制报文来报告差错。

A 错误。路由重定向报文是一种 ICMP 报文，用于指示主机通过另一个路由器发送数据。通常情况下，它由路由器发送给主机，告知主机使用另一条路由来发送数据包。这种情况通常发生在主机发送数据包到一个路由器，而该路由器认为有更佳的路由选项可供选择时。主机接收到路由重定向报文后，会更新其路由表，以便将将来的数据包发送到更佳的路径上。路由重定向报文有助于优化数据包的传输路径，以提高网络的效率和性能。

B 错误。目的不可达报文是一种 ICMP 报文，用于通知发送方某个数据包无法到达其目的地的原因。这种消息可以指示多种问题，包括目标主机不可达、网络不可达、协议不可达、端口不可达或者需要进行分片但不允许分片等等。这种报文对于网络故障排除和诊断非常重要，因为它可以提供有关问题所在的关键信息，有助于维护人员解决网络通信中的问题。

C 正确。源点抑制报文是一种 ICMP 报文，用于指示数据流控制。当路由器或主机接收到太多数据包，超出其处理能力时，它可以发送源点抑制报文给数据包的源头，以通知其减缓发送速率。这有助于避免网络拥塞和过载，同时确保网络上的流量保持在可接受的水平。通常情况下，这种报文类型在现代网络中并不经常使用，因为大多数路由器和设备已经通过其他方式更好地处理了流量控制和拥塞管理。

D 错误。超时报文是一种 ICMP 报文，用于通知发送方某个数据包由于在路由过程中超时而被丢弃的情况。这种消息通常与 IP 的生存时间 TTL 字段有关，TTL 用于确保数据包在网络中不会永远存在而导致网络拥塞。当 TTL 减至 0 或者某一路由节点由于其他原因导致数据包在其内部超时时，将会向数据包的发送方发送超时消息。这种消息有助于发送方识别数据包传输中的问题，也有助于维护人员定位网络通信中的瓶颈和故障。

本题选 C。

IP 地址空间为 192.168.5.0/24 的主机号占 32-24 = 8位。

子网掩码 255.255.255.248，表示为二进制为  ，二进制位用红色表示，其表示的子网主机号占 3 位。

采用定长子网划分，192.168.5.0/24 可分配的子网掩码为 255.255.255.248 的最大子网个数为 28−3=32 。或者 192.168.5.0/24 的 IP 地址空间内 IP 数为 28 ，每个子网掩码为 255.255.255.248 的子网的 IP 地址空间内 IP 数为 23 ，最大子网个数为 28/23=32 。

每个子网的地址空间内 IP 数为 23=8 ，排除一个主机号位全 0 的网络地址和一个主机号位全 1 的广播地址，每个子网内的最大可分配地址个数为 8-1-1=6。

本题选 B。

冲突域：连接在同一导线上的所有工作站的集合，或者说是同一物理网段上所有节点的集合或以太网上竞争同一带宽的节点集合。这个域代表了冲突在其中发生并传播的区域。在 OSI 模型中，冲突域被看作是物理层的概念。

广播域：接收同样广播消息的节点的集合。如：在该集合中的任何一个节点传输一个广播帧，则所有其他能收到这个帧的节点都被认为是该广播帧的一部分。在 OSI 模型中，广播域被看作是数据链路层的概念。

广播风暴 (broadcast storm) ：指当广播数据充斥网络无法处理，并占用大量网络带宽，导致正常业务不能运行，甚至彻底瘫痪，这就发生了“广播风暴”。一个数据帧或包被传输到本地网段（由广播域定义）上的每个节点就是广播；由于网络拓扑的设计和连接问题，或其他原因导致广播在网段内大量复制，传播数据帧，导致网络性能下降，甚至网络瘫痪，这就是广播风暴。

I 不能抑制广播风暴。中继器是工作在物理层上的连接设备。适用于完全相同的两个网络的互连，主要功能是通过对数据信号的重新发送或者转发，来扩大网络传输的距离。中继器既不能分割冲突域也不能分割广播域。

II 不能抑制广播风暴。集线器是工作在物理层上的连接设备，是一个多端口的转发器。集线器既不能分割冲突域也不能分割广播域。

Ⅲ 不能抑制广播风暴。网桥是工作在数据链路层上的连接设备，网桥的两个端口分别有一条独立的交换信道，不是共享一条背板总线。网桥只能分割冲突域不能分割广播域。

IV 能抑制广播风暴。路由器是工作在网络层的连接设备，路由器能够连接不同类型网络并能够选择数据传送路径的网络设备。

综上，仅 IV 能抑制广播风暴。

本题选 D。

本题考察 TCP 流量控制与拥塞控制。

发送方的发送窗口的上限值要取接收方接收窗口和拥塞窗口这两个值中较小的一个。即

发送方的发送窗口 = min{拥塞窗口, 接收方接收窗口}

初始时，假设发送方的发送窗口为当前拥塞窗口大小 4000 KB。并发送两个最大段长。如图 (a) 所示。

当前拥塞窗口为 4000 字节，即 cwnd = 4000 KB。每个发送段为 1000 KB，当成功收到主机乙发送的第一个段的确认段后，发送窗口将已被确认的段移出，并继续向前移动 1000 KB，未被确认的已发送的第二段 1000 KB 仍停留在发送窗口中。

确认段中通告的接收窗口大小为 2000 字节，即 rwnd = 2000 KB。此时调整发送方的发送窗口为 swnd = min{cwnd, rwnd} = min{4000 KB, 2000 KB} = 2000 KB。由于未被确认的已发送的第二段 1000 KB 仍停留在发送窗口中。如图 (b) 所示。

还剩余 2000 KB - 1000 KB =1000 KB 可以发送。

本题选 A。

DNS 递归查询过程如下图所示。

主机发送一条 DNS 查询后，因为本地域名服务器无缓存，本地域名服务器会向相关根域名服务器发送一条查询请求，根域名服务器递归查询，将获得的结果返回给本地域名服务器，再返回给主机。

本题选 A。

（1）算法的基本设计思想：
可以将这个问题看做是把数组 ab 转换成数组 ba（a 代表数组的前 p 个元素，b 代表数组中余下的 n - p 个元素），先将 a 逆置得到 $a^{-1}b$，再将 b 逆置得到 $a^{-1}b^{-1}$，最后将整个 $a^{-1}b^{-1}$ 逆置得到（$a^{-1}b^{-1}$）$^{-1}$ = ba。设 Reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3（p = 3）个位置的过程如下：
Reverse(0,p - 1)得到 cbadefgh；
Reverse(p,n - 1)得到 cbahgfed；
Reverse(0,n - 1)得到 defghabc；
注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。
（2）使用 c 语言描述算法如下：

void Reverse(int R[],int from,int to) {
    int i,temp;
    for(i = 0; i < (to - from + 1)/2; i++)
    {   temp = R[from + i]; R[from + i] = R[to - i]; R[to - i] = temp; }
} // Reverse
void Converse(int R[],int n,int p){
    Reverse(R,0,p - 1);
    Reverse(R,p,n - 1);
    Reverse(R,0,n - 1);
}

（3）上述算法中三个 Reverse 函数的时间复杂度分别为 O(p/2)、O((n - p)/2) 和 O(n/2)，故所设计的算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
另解，借助辅助数组来实现：
算法思想：创建大小为 p 的辅助数组 S，将 R 中前 p 个整数依次暂存在 S 中，同时将 R 中后 n - p 个整数左移，然后将 S 中暂存的 p 个数依次放回到 R 中的后续单元。
时间复杂度为 O(n)，空间复杂度为 O(p)。 

(1) 操作码占 4 位，则该指令系统最多可有 2^4=16 条指令；操作数占 6 位，寻址方式占 3 位，于是寄存器编号占 3 位，则该机最多有 2^3=8 个通用寄存器；主存容量 128KB，按字编址，计算机字长为 16 位，划分为128KB/2B=216 个存储单元，故 MDR 和 MAR 至少各需 16 位。

(2) PC 和 Rn 可表示的地址范围均为 0～2^16-1，而主存地址空间为 2^16，故转移指令的目标地址范围是 0000H～FFFFH（0～2^16-1）。

(3) 汇编语句“add (R4), (R5) +”，对应的机器码为 0010 0011 0001 0101B=2315H。

该指令执行后，寄存器 R5 和存储单元 5678H 的内容会改变。执行后，R5 的内容从 5678H 变成 5679H。存储单元 5678H 中的内容变成该加法指令计算的结果 5678H＋1234H=68ACH。

解答：

(1) 数据 Cache 有 8 个 Cache 行，每个 Cache 行大小为 64B，Cache 中每个字块的 Tag 字段的位数是 28-9＝19 位，此外还需使用一个有效位，合计 20 位。因此，数据 Cache 的总容量应为：8×(64＋20／8)B＝532B。

(2) 数组 a 在主存的存放位置及其与 Cache 之间的映射关系如下图所示：

数组按行优先方式存放，首地址为 320，数组元素占四个字节。a[0][31]所在的主存块对应的 Cache 行号为：(320＋31×4) DIV 64 = 6 ；

a[1][1]所在的主存块对应的 Cache 行号为：

(320＋256×4＋1×4) DIV 64 MOD 8 = 5 。

(3) 编译时 i、j、sum 均分配在寄存器中，故数据访问命中率仅考虑数组 a 的情况。

① 该程序的特点是数组中的每一个元素仅被使用一次。数组 a 按行优先存放，数据 Cache 正好放下数组半行中的全部元素，即元素的存储顺序与使用次序高度的吻合，每个字块的 16 个 int 型元素中，除访问的第一个不会命中，接下来的 15 个都会命中。访问全部字块都符合这一规律，故命中率为 15／16，即程序 A 的数据访问命中率是 93.75%。

② 程序 B 按照数组的列执行外层循环，在执行内层循环的过程中，将连续访问不同行的同一列的数据，不同行的同一列数组使用的是同一个 Cache 单元，每次都不会命中，故命中率是 0

由于从 Cache 读数据比从主存读数据快很多，所以程序 A 的执行比程序 B 快得多。

(1) 用位图表示磁盘的空闲状态。每一位表示一个磁盘块的空闲状态，共需要16384 / 32 = 512个字 = 512×4个字节 = 2KB，正好可放在系统提供的内存中。

(2) 采用CSCAN调度算法，访问磁道的顺序和移动的磁道数如下表所示：

移动的磁道数为20 + 90 + 20 + 40 = 170，故总的移动磁道时间为170ms。
由于转速为6000r/m，则平均旋转延迟为5ms，总的旋转延迟时间 = 20ms。
由于转速为6000r/m，则读取一个磁道上一个扇区的平均读取时间为0.1ms，总的读取扇区的时间平均读取时间为0.1ms，总的读取扇区的时间为0.4ms。
综上，读取上述磁道上所有扇区所花的总时间为190.4ms。

(3) 采用FCFS（先来先服务）调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务。 

(1) 由于该计算机的逻辑地址空间和物理地址空间均为$64KB = 2^{16}B$，按字节编址，且页的大小为$1K = 2^{10}$，故逻辑地址和物理地址的地址格式均为：
\[
  \begin{array}{|c|c|}
    \hline
    \texttt{页号 / 页框号（6 位）} & \texttt{页内偏移量（10位）} \\
    \hline
  \end{array}
\]
$17CAH = 0001 0111 1100 1010B$，可知该逻辑地址的页号为$000101B = 5$。

(2) 根据FIFO算法，需要替换装入时间最早的页，故需要置换装入时间最早的0号页，即将5号页装入7号页框中，所以物理地址为$0001 1111 1100 1010B = 1FCAH$。

(3) 根据CLOCK算法，如果当前指针所指页框的使用位为0，则替换该页；否则将使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从2号页框开始，前4次查找页框号的顺序为$2→4→7→9$，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位为0，故淘汰2号页框对应的2号页，把5号页装入2号页框中，并将对应用位置设置为1，所以对应的物理地址是$0000 1011 1100 1010B = 0BCAH$。 

(1) 当主机甲和主机乙同时向对方发送数据时，信号在信道中发生冲突后，冲突信号继续向两个方向传播。这种情况下两台主机均检测到冲突需要经过的时间最短，等于单程的传播时延t0 = 2km/200 000km/s = 0.01ms。
主机甲（或主机乙）先发送一个数据帧，当该数据帧即将到达主机乙（或主机甲）时，主机乙（或主机甲）也开始发送一个数据帧，这时，主机乙（或主机甲）将立刻检测到冲突，而主机甲（或主机乙）要检测到冲突，冲突信号还需要从主机乙（或主机甲）传播到主机甲（或主机乙），因此甲乙两台主机均检测到冲突所需的最长时间等于双程的传播时延2*t0 = 0.02ms。

(2) 主机甲发送一个数据帧的时间，即发送时延t1 = 1518×8b/10Mbps = 1.2144 ms；主机乙每成功收到一个数据帧后，向主机甲发送确认帧，确认帧的发送时延t2 = 64×8b/10Mbps = 0.0512ms；主机甲收到确认帧后，即发送下一数据帧，故主机甲的发送周期T = 数据帧发送时延t1 + 确认帧发送时延t2 + 双程传播时延 = t1 + t2 + 2*t0 = 1.2856 ms；于是主机甲的有效数据传输率为1500×8/T = 12000b/1.2856 ms ≈ 9.33 Mbps。（以太网有效数据1500字节，即以太网帧的数据部分）