参考答案：D

答案解析：m、n 是两个升序链表，长度分别为 m 和 n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最小值。 

方法一：分段分析

这道题思维上有一定难度。

• 先分析 3 后面的元素，即 n=4,5,…,n ， p3=n 都是可以实现的，即该元素在进栈后立即出栈。
• 再分析 3 自身，一个元素不可能出栈两次，可以直接排除。
• 最后分析 3 前面的元素 1 和 2 。
  • 若 p1=1 且 p2=3 ，出栈序列可以为 1,3,2,… 此时 p3=2 。
  • 若 p1=2 且 p2=3 ，出栈序列可以为 2,3,1,… 此时 p3=1 。

综上，只有 3 自身被排除， p3 可能取值的个数共计 n−1 。

本题选C。

方法二：找规律

若 n=3 ，则出栈序列有5种，分别是 1,2,3 、 1,3,2 、 2,1,3 、 2,3,1 、 3,2,1 。当 p2=3 时，有2种情况，分别是1,3,2 和2,3,1 ，p3 可能取值的个数是2。

若 n=4 ，则出栈序列有14种，分别是

当 p2=3 时，有5种情况，分别是 4,3,2,1 、2,3,4,1 、 2,3,1,4 、 1,3,4,2 和1,3,2,4 ，p3 可能取值的个数是3。

综上，可以猜测若 p2=3 ，则 p3 可能取值的个数是 n−1 。

本题选C。

方法一：模拟

本题要求模拟平衡二叉树（AVL树）的插入过程。

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

旋转法

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

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

由于关键字是从小到大插入，出现的都是RR平衡旋转。

中序遍历法

下面介绍中序遍历法，中序遍历法本质是利用AVL树的性质从结果出发直接找出调整后AVL树的根结点。

第一步：标记出插入不平衡结点从所在子树上的根结点到插入结点路径上的3个元素，标记3个元素为橙色，再标记3个橙色元素中间元素为红色，红色元素即为调整后子树的根结点，左边橙色元素为调整后子树左子树根结点，右边橙色元素为调整后子树右子树根结点。

第二步：写出子树的中序遍历序列，调整前后AVL树的中序遍历序列保持不变，将剩余结点加入到调整后的子树中。

此时，所有关键字都已经插入到AVL树中。

题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，即结点 2、4 和 6 ，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。

本题选D。

方法二：贪心

当然，模拟完整的AVL树插入过程非常麻烦，由于AVL树一定是平衡的，总共 7 个结点，我们很容易构造出一棵满二叉树，满二叉树的根结点和两个孩子结点为符合题目要求的结点，总共有 3 个结点。

题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。

本题选D。

参考答案：B

答案解析：利用三叉树的 6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为(2 + 3) * 3 + (4 + 5) * 2 + (6 + 7) * 1 = 46。

方法一：模拟

T 的带权（外部）路径长度最小是 (2+3)×3+(4+5)×2+(6+7)×1=46 。

本题选B。

方法二：贪心

下面提供秒题解法。

题目要求“最小”，四个选项中A选项最小，直接选A？

如果是这样你就错了， (2+3+4+5+6+7)×1=27 ，A选项表示一棵六叉树。

与 T 为三叉树矛盾，所以我们只能在剩余三个选项中选最小值。

本题选B。

后序线索二叉树的遍历序列即二叉树后序遍历序列，根据题意，很容易画出示意图：

X 的右线索指的是 X 的父结点。

本题选A。

二叉排序树又称二叉搜索树，本题考察二叉搜索树的性质。

方法一：性质

很明显，本题要求我们分两种情况讨论。

若 v 是 T1 的叶结点，为情况一，直接删除，再插入 v ， v 会复原到原来的位置，则 T1 与 T3 相同。

若 v 不是 T1 的叶结点，为情况二或情况三，再插入 v ， v 会变成叶结点，则 T1 与 T3 不同。

仅II、III正确。

本题选C。

方法二：断言

二叉搜索树的删除非常复杂，如果没有掌握也没有关系。

若 v 是 T1 的叶结点，插入 v ， v 还是叶结点，则 T1 与 T3 相同。

若 v 不是 T1 的叶结点，插入 v ， v 会变成叶结点，则 T1 与 T3 不同。

仅II、III正确。

虽然这样推导不严谨，但足够高效就行。

本题选C。

参考答案：C

答案解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

本题考察度的定义：某顶点的度为以该顶点为端点的边的数目。

我们将顶点依次编号为 1,2,3,4 。

方法一：观察邻接矩阵

顶点 1 的度为包含 1 为端点的边数，即第一行和第一列非零元素的个数。

顶点 2 的度为包含 2 为端点的边数，即第二行和第二列非零元素的个数。

顶点 3 的度为包含 3 为端点的边数，即第三行和第三列非零元素的个数。

顶点 4 的度为包含 4 为端点的边数，即第四行和第四列非零元素的个数。

本题选C。

方法二：画出有向图

本题选C。

参考答案：D

答案解析：D 选项是深度优先遍历不是广度优先遍历的顺序。

方法一：模拟

广度优先搜索就是用一圈一圈扩散的方式进行搜索。

我们依次以A、B、C、D四个选项中序列的第一个元素为起点画出下面这个广度优先搜索过程，用颜色由深入浅标记这个扩散过程，颜色相同的结点在同一层，输出序列中，颜色相同的结点的关键字即同一层结点的关键字一定相邻。

本题选D。

方法二：找错误选项

我发现命题组设置错误选项一般比较无脑，D选项出现了无脑的a, b, c, d这种顺序，明显就是一个深度优先搜索顺序，直接排除。

本题选D。

参考答案：C

答案解析：根据 AOE 网的定义可知，关键路径上的活动时间同时减少，可以缩短工期。

方法一：完整推理

参考答案：A

答案解析：一棵高度为 2 的 5 阶 B 树，根结点只有到达 5 个关键字的时候才能产生分裂，成为高度为 2 的 B 树。

方法一：公式法

本题选A。

方法二：构造法

m 阶B树每个结点（除根结点）关键字数量 n 为 ⌈m/2⌉−1≤n≤m−1 。本题要求为5阶B树， 2≤n≤4 。

又该B树的高度为2，根结点至少有两棵子树，很容易构造出题目要求的B树。

该B树总共5个关键字。

本题选A。

方法三：选项排序 + 贪心

下面提供秒题解法。

题目要求“最少”，四个选项中A选项最少。

本题选A。

参考答案：C

答案解析：基数排序的第 1 趟排序是按照个位数字来排序的，第 2 趟排序是按然十位数字的大小进行排序的，答案是 C 选项。

本题考察基数排序，直接进行模拟即可，按照从低位到高位的顺序进行。

本题选C。

tips：本题中 007 没有简单写作 7 ，如果遇到高位缺失的情况，要记得自己补 0 。

根据表格可得，基准程序CPI为2×50%+3×20%+4×10%+5×20%=3，即平均执行一条指令需要3个时钟周期，又因为主频为1.2GHz，所以每秒执行指令数为1.2G/3=0.4G=400M，即该机的MIPS数是400。

本题选C。

解析：IEEE 754 单精度浮点数格式为 C640 0000H，二进制格式为 1100 0110 0100 0000 0000 0000 0000 0000

IEEE754浮点数的格式如下：

本题选A。

乘以2等价于算术左移1位， 补[x]补=11110100 ，得 补补[2x]补=[x<<1]补=11101000 。

除以2等价于算术右移1位， 补[y]补=10110000 ，得 补补[y/2]补=[y>>1]补=11011000 。

补补补[z]补=[2x]补+[y/2]补=11101000+11011000=(1)11000000 。括号内为最高位进位，最高位进位与符号位相同，均为1，没有溢出，所以z的机器数为11000000。

本题选A。

设校验的位数为k，数据位的位数为n，海明码能纠正一位错需要满足关系 2^k≥n+k+1 ，当 n=8 时， 16=2^4>8+4+1=13 ，所以k至少为4。

本题选C。

计算机采用页式存储管理，一般格式为  。计算机按字节编址，页面大小为4KB= 2^12 B，页内地址占低12位，虚拟地址空间大小为4GB= 2^32 B，虚页号占高32-12=20位。

虚拟地址  ，查找TLB中03FFFH对应的页表项，有效位为1，页框号为0153H，物理地址为  。

本题选A。

变址寻址方式下有效地址EA=®+A=1000H+2000H=3000H，操作数S=(3000H)=4000H。所谓寻址，指的是寻找操作数的地址或下一条将要执行的指令地址。每台计算机的指令系统都有自身的一套寻址方式，不同计算机的寻址方式的名称和含义也不同。变址寻址就是把变址寄存器的内容与指令中给出的形式地址A相加，形成操作数有效地址，即EA=(变址寄存器)+A。操作数S与地址码和变址寄存器的关系为S=((变址寄存器)+A)。

变址寄存器为R，变址寻址有效地址EA=(R)+A=1000H+2000H=3000H，变址寻址方式下访问到的操作数为(EA)=(3000H)=4000H。

本题选D。

在输入流水线是任务连续（没有发生任何流水线阻塞）的理想情况下，一条 k 段流水线能够在 k+n−1 个时钟周期内完成 n 个任务，设时钟周期为 Δt ，时钟频率为 f ，则流水线的实际吞吐率为

本题中CPU采用4级流水线执行100条指令，CPU的主频是1.03GHz，这里k=4，n=100，f=1.03GHz。代入公式得：流水线的吞吐率 = 100条指令×1.03GHz/(4+100-1)＝ 1.0×10^9 条指令/秒。

本题选C。

解答：PCI是一种由英特尔公司1991年推出的用于定义局部总线的标准。此标准允许在计算机内安装多达10个遵从PCI标准的扩展卡。从1992年创立规范到如今，PCI总线已成为了计算机的一种标准总线。PCI总线取代了早先的ISA总线。当然与在PCI总线后面出现专门用于显卡的AGP总线，与现在PCI Express总线相比，速度要慢。PCI有许多优点，比如即插即用、中断共享等。PCI、AGP、PCI Express都是局部总线标准。

USB是一种连接外部设备的I/O总线标准，属于设备总线，是设备和设备控制器之间的接口。

本题选B。

RAID技术分为几种不同的等级，分别可以提供不同的速度，安全性和性价比。

RAID0：无冗余和无校验的磁盘阵列。

RAID1：镜像磁盘阵列。

RAID2：采用纠错的海明码的磁盘阵列。

RAID3：位交叉奇偶校验的磁盘阵列。

RAID4：块交叉奇偶校验的磁盘阵列。

RAID5：无独立校验的奇偶校验的磁盘阵列。

I正确。磁盘镜像：将数据同时写入两个或多个磁盘，以实现冗余备份。如果一个磁盘发生故障，数据仍然可以从备份磁盘中恢复，提高了数据的可靠性。

Ⅱ错误。条带化：将数据分散存储在多个磁盘上，以提高数据访问的速度。条带化可以在多个磁盘上并行读取和写入数据，但它本身并没有提供数据冗余的功能。

Ⅲ正确。奇偶校验：通过在数据块中添加额外的奇偶校验位，可以检测和纠正数据错误。在RAID中，奇偶校验位用于计算数据块的校验信息，并存储在其他磁盘上。如果一个磁盘发生故障，可以使用奇偶校验信息重新计算丢失的数据，并进行恢复。

Ⅳ错误。增加Cache机制：Cache机制通常是通过在RAID控制器上添加高速缓存（例如内存或固态硬盘）来提高数据访问速度。

虽然条带化和增加Cache机制可以提高性能，但其本身并不直接提高RAID的可靠性。可靠性的提升更多地依赖于数据冗余和错误检测与纠正的机制，如磁盘镜像和奇偶校验。

本题选B。

解析：磁盘转速是 10 000 转/分钟，平均转一转的时间是 6ms，因此平均查询扇区的时间

是 3ms，平均寻道时间是 6ms，读取 4 KB 扇区信息的时间为 0.2ms，信息延迟的时间为

0.2ms，总时间为 3+6+0.2+0.2=9.4ms

本题选B。

中断I/O方式是一种常见的I/O数据传输方式，它通过CPU的中断处理机制来完成数据传输。当外部设备准备好数据或需要CPU的处理时，它会发送中断请求，CPU暂停当前任务并转而处理中断请求。数据传输通过CPU的介入和中断处理程序来完成。

DMA方式是一种高效率的数据传输方式，它通过直接访问内存而不需要CPU的介入。DMA控制器直接将数据从外部设备传输到内存中，或者从内存传输到外部设备中。DMA传输过程中不需要CPU的干预，仅在传输一个或多个数据块的开始和结束时，才需要CPU干预。DMA方式适用于所有外部设备，尤其对于需要较高数据传输速率的设备，它可以明显减少CPU的负载并提高系统性能。

中断I/O方式和DMA方式都可以应用于不同类型的外部设备，没有限制适用于特定速度的设备。DMA方式相比中断I/O方式减少了CPU的干预，提高了数据传输速度。DMA方式适用于需要高速数据传输的设备，例如硬盘驱动器、图形卡等，但不仅限于这些设备。所以中断I/O方式和DMA方式都可以应用于各种类型的外部设备，但中断I/O方式不适用于需要高速数据传输的设备。D错误。

本题选D。

A正确。假设用户在删除某文件的过程中，操作系统删除此文件所在的目录，且该目录下除该文件外还有其他文件的目录项，则会导致无法访问其他文件，显然操作系统不允许这样的事情发生，推出矛盾。

B错误。在删除文件时，操作系统会删除文件所在目录中的目录项，以清除与文件的关联。

C错误。文件控制块 (file control block, FCB) 是操作系统中用于管理文件的数据结构，它存储了与文件相关的各种属性和信息，以及对文件的操作和控制的各种指针和标志。在删除文件时，操作系统通常会清除或更新与该文件相关的文件控制块。

D错误。在读取或写入文件时，操作系统会使用内存缓冲区来提高文件IO的效率。当文件删除时，操作系统通常会释放与该文件关联的内存缓冲区，以回收内存资源。

本题选A。

CD-ROM 是一种光盘存储介质，具有顺序读取的特点。在视频文件中，通常需要随机访问不同的数据块来实现快速播放和定位。因此，选择一种数据块组织方式能够最好地支持随机访问和快速定位是关键。

本题选A。

当用户程序发出磁盘I/O请求后，处理流程如下：

1. 用户程序：用户程序发出磁盘I/O请求，通常通过系统调用的方式将请求传递给操作系统。
2. 系统调用处理程序：系统调用处理程序是操作系统中的一部分，负责接收用户程序的系统调用请求，并进行相应的处理。在磁盘I/O请求的情况下，系统调用处理程序会将请求传递给相应的设备驱动程序。
3. 设备驱动程序：设备驱动程序是操作系统中负责管理和控制设备的模块。对于磁盘I/O请求，设备驱动程序会根据请求中所涉及的设备信息，计算出数据所在磁盘的柱面号、磁头号、扇区号。这些信息用于指定磁盘上正确的位置进行数据读取或写入。
4. 中断处理程序：中断处理程序是一段特殊的代码，用于处理硬件中断或异常事件。当设备驱动程序计算出数据所在磁盘的柱面号、磁头号、扇区号后，它会将这些信息传递给磁盘控制器，并发起磁盘I/O操作。当磁盘I/O操作完成时，磁盘控制器会触发中断，操作系统会转入中断处理程序进行后续的处理。

本题选C。

设文件块大小x，每个地址项大小为y，文件采用混合索引，地址索引最大为k级，i级地址索引数量为ni，直接地址索引视为0级索引，则文件最大长度为。

本题选A。

为了使处理时间最短，系统连续处理数据块。

方法一：模拟

由于数据缓冲区可以复用，类比多道批处理系统中多个程序的运行，画出运行的甘特图（也称横道图）如图 (a) 所示。进程从外设读入并分析 2 个数据块的最短时间是300。

本题选C。

方法二：公式法

从外设读入 1 个数据块到系统缓冲区的时间为T，从系统缓冲区读入 1 个数据块到用户工作区的时间为M，对用户工作区中的 1 个数据块进行分析的时间为C。

假设连续从外设读入并分析 n 个数据块，同2011年题31，总结出图 (b) 中的公式。

连续输入情况下，单缓冲区处理每块数据用时 max{C,T}+M （C和T并行）

单缓冲区仅处理 n 块数据用时 (n−1)(max{C,T}+M)+T+M+C （中间n-1段包含C和T并行，第一个数据块的T和M以及最后一个数据块的C无法并行执行）。

本题中，T=100，M=5，C=90，n=2，代入 (n−1)(max{C,T}+M)+T+M+C 得在单缓冲区读入并分析完该文件的时间是300。

本题选C。

【解析】需要在系统内核态执行的操作是整数除零操作（需要中断处理）和read系统调用函数，sin（）函数调用是在用户态下进行的。

I正确。整数除以零导致异常。该异常会导致处理器从用户态切换到内核态，以便内核能够处理异常情况。

II错误。调用数学库函数如 sin() 不会导致用户进程切换到内核态。这样的函数调用仅在用户态执行，然后返回结果给用户进程。

III正确。read 系统调用用于从文件描述符读取数据。当用户进程调用 read 系统调用时，它必须切换到内核态，以便内核可以执行读取文件的操作。这涉及到访问和操作内核数据结构，因此用户进程会从用户态切换到内核态。

综上，I和III正确。

本题选B。

【答案】D

【解析】用户平时开机时首先启动的是存于主板上ROM中的BIOS程 序 （注意：不是操 作系统），其次再由它去调用硬盘中的操作系统（如Windows系统），将操作系统的程序自动 加载到内存中的系统区，这段区域是RAM ,答案选D。

在计算机开机后，初始的引导过程是由BIOS (Basic Input Output System) 负责的。BIOS是存储在计算机的ROM中的固件程序，负责初始化硬件和进行引导操作。通常情况下，操作系统的引导程序由BIOS从硬盘、固态硬盘或其他可引导设备的引导扇区加载到RAM中。

一旦操作系统的引导程序被加载到RAM中，控制权将转移到这个引导程序，它进一步加载和初始化操作系统的其他部分，并将操作系统完全加载到RAM中供后续执行。

本题选D。

I错误。处理越界错误（即访问超出进程地址空间范围的内存）是一种不合法或无效的内存访问错误。

II正确。页面置换是将一个当前驻留在物理内存中的页面替换出去以腾出空间，从而将所需的页面加载到物理内存中。这个过程涉及到选择要替换的页面和载入所需的页面。常见的页面置换算法包括FIFO、LRU算法等。

III正确。操作系统通过分配内存的方式腾出空间，从而将所需的页面加载到物理内存中。

综上，仅 II、III正确。

本题选B。

通常情况下，进程优先级的设置规则如下：

1. 响应时间原则：要求快速响应的进程优先级高。一般情况下，系统进程优先级高于用户进程优先级，前台进程优先级高于后台进程优先级。
2. 系统资源利用率原则：I/O密集型进程优先级高。
3. 综合考虑原则：除上述两点，综合考虑系统的整体性和平衡性。

从I/O时间占比角度分析：

在I/O密集型进程中，I/O操作的速度和效率是主要瓶颈，因为它更多的时间花在等待 I/O 操作完成上，而不是在需要持续 CPU 计算的任务上，CPU的处理能力往往有闲置。因此，为了有效利用系统资源，应当给予这类进程较高的优先级。

当一个进程在等待 I/O 操作完成时，操作系统可以将 CPU 时间分配给其他可执行的进程，从而实现资源的更有效利用。这种情况下，给予 I/O 占比高的进程较高的优先级，有助于确保系统能够更灵活地响应 I/O 操作，从而提高整体的系统资源利用率。

在本题中，P1的I/O时间占比<P2的I/O时间占比<P3的I/O时间占比，因此合理的进程优先级设置应为P3>P2>P1。

从CPU时间占比角度分析：

类比短进程优先算法，将I/O时间不占用CPU，计算时间占用CPU，可以让计算时间较短（或计算时间占比较少）的进程优先执行，从而降低平均周转时间，提高CPU和I/O设备的并行度。

在本题中，P1的计算时间占比>P2的计算时间占比>P3的计算时间占比，因此合理的进程优先级设置应为P3>P2>P1。

综上，综合考虑进程的计算 (CPU) 时间和 I/O 时间，合理的进程优先级设置应为P3>P2>P1。

本题选B。

银行家算法是避免死锁的方法，选项A、D错。

并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态；死锁状态必定是不安全状态。所以选项B对，选项C错。

A错误。银行家算法是一个避免死锁的著名算法，它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

B正确。当系统处于安全状态时，系统中一定无死锁进程，且存在至少一种执行序列，使得所有进程能够顺利完成而不会进入死锁状态。

C错误。当系统处于不安全状态时，系统无法找到一种执行顺序，使得每个进程都能在其所需资源得到满足时执行，并在执行完毕后释放资源，可能导致死锁的发生。但不安全状态下，不一定会产生死锁，比如有进程提前归还了一些资源，那么系统可能会重新回到安全状态。

D错误。银行家算法是一种避免死锁策略，而破坏了死锁必要条件是一种预防死锁策略。

本题选B。

OSI 参考模型 (Open System Interconnection Reference Model) 是一个由国际标准化组织提出的概念模型，旨在为各种计算机互连构成网络提供标准框架。该模型将通信系统划分为七层，从下到上依次为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

应用层的相邻层的是表示层。

A 错误。对话管理是由会话层实现的。

B 正确。数据格式转换是由表示层实现的。

C 错误。路由选择是由网络层实现的。

D 错误。可靠数据传输可在多个层中实现，例如是由数据链路层、传输层。

本题选 B。

10 BaseT 是双绞线以太网，采用 10 Mbps 基带传输，10 表示 10兆比特每秒，Base 表示基带传输，T 代表双绞线。10 BaseT 采用曼彻斯特编码。

曼彻斯特编码是一种用电平跳变来表示二进制数据 0 和 1 的编码方法，它通过在每个二进制位中间加入一个电平跳变来同时传输数据和时钟信号。

如图 (a) 所示，若正跳变表示 0，负跳变表示 1，则图中信号波形表示比特串为 00110110，选项 A 符合要求。

如图 (b) 所示，若正跳变表示 1，负跳变表示 0，则图中信号波形表示比特串为 11001001，没有符合要求的选项。

本题选 A。

报文交换是一种存储转发技术。将整个报文作为一个单元发送。

分组交换又称报文分组交换，或包交换，是一种存储转发技术。将报文分解成若干段，每一段报文加上交换时所需的地址、控制和差错校验信息，按规定的格式构成一个数据单位，通常被称为“报文分组”或“包”。

注意本题中 1M= 10^6 ，1 k = 10^3 ，这样修改是为了方便计算。

采用报文交换时，如图 (a) 所示，每段链路的发送时延 = 报文大小/数据传输速率 = 8 Mb / 10Mbps = 800 ms，每段链路的传播时延被忽略，由于通过路由器转发，总共有两段链路，总共时延为 800 ms × 2 = 1 600 ms。

采用分组交换时，如图 (b) 所示，分组大小为10kb，每个分组的发送时延 = 分组大小/数据传输速率 = 10 kb / 10Mbps = 1 ms，所有分组的发送时延相当于一个报文的发送时延，为 800 ms，一个分组的发送时延为 1 ms，每段链路的传播时延被忽略，总共时延为 800 ms + 1 ms = 801 ms。

本题选 D。

介质访问控制 (medium access control, MAC)：是解决当局域网中共用信道的使用产生竞争时，如何分配信道的使用权问题。分为静态划分信道（信道划分介质访问控制）、动态划分信道。

冲突：是指信道上有两个或两个以上站点同时发送数据，在信道上就会产生信号的混合，这样哪个站点都辨别不出真正的数据是什么。

静态划分信道：也叫信道划分介质访问控制，主要有有四种控制的⽅法：频分多路复用(FDM)、时分多路复用 (TDM)、波分多路复用 (WDM)、码分多路复用（CDM）。静态划分信道不会产生冲突。

动态分配信道：信道并非在用户通信时固定分配给用户，分为轮询访问介质访问控制和随机访问介质访问控制。随机访问介质访问控制指所有站点可以随机发送信息，发送信息时占用信道的全部带宽。包括 ALOHA、CSMA、CSMA/CD、CSMA/CA。随机访问介质访问控制可能发生冲突。

A 错误。CDMA (Code Division Multiple Access) 码分多址，属于静态划分信道。它采用编码和分配不同的码片给每个用户，从而实现信号的隔离和并行。CDMA被广泛应用于移动通信系统中。

B 正确。CSMA (Carrier Sense Multiple Access) 载波监听多点接入，属于动态划分信道中的随机访问介质访问控制。是一种允许多个设备在同一信道发送信号的协议，站点在发送数据之前会先监听信道是否有其他站点在发送数据，如果有站点正在发送数据，其他站点会进行退避操作，只有在信道空闲时才发送。然而，即使进行了退避，仍然可能会发生碰撞，特别是在高负载情况下。如果恰巧有两个同时在信道上发送数据，则信号在共享信道上就会产生冲突。

C 错误。TDMA (Time Division Multiple Access) 表示时分多址，属于静态划分信道。在 TDMA 中，时间被划分成若干个时间片，每个用户被分配一个或多个时间片来传输数据。

D 错误。FDMA (Frequency Division Multiple Access) 表示频分多址，属于静态划分信道。在 FDMA 中，可用的频谱被划分为多个不重叠的频带，每个用户被分配一个独特的频带进行数据传输。

本题选 B。

HDLC 协议使用比特填充来进行字节填充。在进行组帧时，如果出现连续 5 个 1，则在后面加入一个 0。因此，对给定的比特串 01111100 01111110 组帧后应为 0111110 001111110 10 ，新加入的 0 用红色标记。

本题选 A。

以太网帧的格式如下：

直通交换 (cut-through switching)：网络设备（例如路由器或交换机）一旦接收到目的地址，就开始转发帧（或分组）。

存储转发 (store-and-forward switching)：网络设备必须完整接收整个帧（或分组）后再进行转发。

对于以太网交换机的直通交换方式 (cut-through switching)，当输出端口无排队时，转发一个不包括前导码的以太网帧，只要接收完以太网的目的 MAC 地址（即以太网帧的前 6 字节）就可将帧直接转发，无需缓存帧和校验帧。

本题选 B。

根据 TCP 的工作原理，当一个主机接收到另一端发送的数据后，它会对发送端已经成功接收的字节的序号进行确认，返回 TCP 段的确认号为接收到的最后一个字节号的下一个字节号。

主机甲收到来自主机乙的 TCP 段，序号为 1913，有效载荷为 100 字节，即主机甲接收主机乙传来的 TCP 字节流的 1913~2012 号字节，主机甲希望主机乙发送的下一个期望收到的字节号为 1913 + 100 = 2013 或 2012 + 1 = 2013，即甲立即发送给乙的 TCP 段的确认号为 2013。

主机甲收到来自主机乙的 TCP 段的确认号为 2046，即乙希望甲发送从字节号 2046 开始的数据，即甲立即发送给乙的 TCP 段的序号为 2046。

本题选 B。

SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议，是用于在网络上发送电子邮件的标准协议。SMTP 可以实现将邮件从你的一台主机发送到一个邮件服务器。该邮件服务器会查找接收者的邮件服务器，并使用 SMTP 将邮件转发到接收者的邮件服务器。SMTP 只支持传送 7 位的 ASCII 码内容。

I 正确。

II 正确。

III 正确。

IV 错误。支持从邮件服务器向用户代理发送邮件的协议是 POP3 和 IMAP。

综上，仅 I、II 和 III 正确。

本题选 A。

（1）给出算法的基本设计思想:（4分）
算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。
算法可分为以下两步：
① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
② 判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。 

（2）算法实现：（7分）

int Majority ( int A[ ], int n )
{
    int i, c, count=1;         // c 用来保存候选主元素，count 用来计数
    c = A[0];                 // 设置 A[0]为候选主元素
    for ( i=1; i<n; i++ )      // 查找候选主元素
        if ( A[i] == c )
            count++;           // 对 A 中的候选主元素计数
        else
            if ( count > 0)    // 处理不是候选主元素的情况
                count--;
            else              // 更换候选主元素，重新计数
            { c = A[i];
                count = 1;
            }
    if ( count>0 )
        for ( i=count=0; i<n; i++ )  // 统计候选主元素的实际出现次数
            if ( A[i] == c )
                count++;
    if ( count> n/2 ) return c;    // 确认候选主元素
    else return -1;                // 不存在主元素
}

【（1）、（2）的评分说明】
① 若考生设计的算法满足题目的功能要求且正确，则（1）、（2）根据所实现算法的效率
  给分，细则见下表： 

int Majority1 ( int A[ ], int n)// 采用计数排序思想，时间：O ( n ), 空间：O ( n )
{
    int k, * p, max;
    p = ( int * ) malloc ( sizeof ( int ) * n);  // 申请辅助计数数组
    for ( k=0; k < n ; k++ ) p [k] =0;  // 计数数组清 0
    max = 0;
    for ( k=0; k<n; k++ )
    { p[ A[k] ] ++;  // 计数器+1
        if (p[A[k] ]>p [ max ] ) max = A[k];  // 记录出现次数最多的元素
    }
    if ( p[ max ] > n/2 ) return max;
    else return -1;
}

② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。
③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
④ 参考答案中只给出了使用 C 语言的版本，使用 C++或 Java 语言的答案视同使用 C 语言。

（3）说明算法复杂性：（2 分）
参考答案中实现的程序的时间复杂度为 O（n），空间复杂度为 O（1）。
【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给1 分。 

【答案要点】
（1）采用顺序存储结构，数据元素按其查找概率降序排列。（2 分）
采用顺序查找方法。（1 分）
查找成功时的平均查找长度=$0.35×1 + 0.35×2 + 0.15×3 + 0.15×4 = 2.1$。（2 分）
（2）
【答案一】
采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。（2 分）
采用顺序查找方法。（1 分）
查找成功时的平均查找长度=$0.35×1 + 0.35×2 + 0.15×3 + 0.15×4 = 2.1$。（2 分）
【答案二】
采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。（2 分） 

采用二叉排序树的查找方法。（1分）
查找成功时的平均查找长度 = 0.15×1 + 0.35×2 + 0.35×2 + 0.15×3 = 2.0。（2分）
【（1）、（2）的评分说明】
① 若考生以实际元素表示“降序排列”，同样给分。
② 若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给2分；若计算过程正确，但结果错误，给1分。 
③ 若考生给出其他更高效的查找方法且正确，可参照评分标准给分。 

(1) 第一问，因为CPU主频为800MHz，所以CPU的时钟周期为1/800MHz=1.25ns。

第二问，因为总线时钟频率为200MH，所以总线时钟周期为1/200MHz=5ns。

因为存储器总线宽度为32bit=4B，所以总线带宽为4B×200MHz=800MB/s或4B/5ns=800MB/s。

(2) 因为总线支持突发传送总线事务，每次突发传送32字节，Cache块大小是32B，需要32B/32B=1次突发传送，所以需要一个读突发传送总线事务来完成一个主存块的读取。

(3) 每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。

传输地址时间：因为传送地址需要一个总线时钟周期，即5ns。

存储器准备数据时间：每次突发传送32字节，存储器总线宽度为32位，所以总线需要分32B/32bit=8次传送，因为主存采用8体交叉（默认低位交叉）存储方式，即可以用流水线方式处理，存储周期是40ns，每隔一个总线时钟周期启动一个流水线段，8个流水线段需要时间为40ns+(8-1)×5ns=75ns。

传送数据时间：传送32位数据需要一个总线时钟周期，即5ns。

总共需要时间为5ns+75ns+5ns=85ns。

(4) 无论数据是否存放到 Cache 中，CPU 都是先访问 Cache， 只有当 Cache 中找不到数据时，才会去访问内存，并把内存中的数据读⼊到 Cache 中，CPU 再从 CPU Cache 读取数据。

方法一：BP的CPU执行时间包括Cache命中时的指令执行时间和Cache缺失时带来的额外开销。

指令访问Cache执行时间：BP共执行了100条指令，无论数据是否存放到 Cache 中，CPU 最终都要从 CPU Cache 读取数据，因为Cache命中时的CPI为4，即每条指令访问Cache的CPI为4，CPU的时钟周期为1.25ns，所以从指令访问Cache执行时间是100×4×1.25ns=500ns。

指令访问主存执行时间：因为BP共执行了100条指令，平均每条指令需要1.2次访存，Cache缺失率是5%，Cache缺失率=Cache缺失次数/访存次数，访存次数=指令数×平均每条指令需要的访存次数，（注意，不同指令需要的访存次数不一定相同。）得到Cache缺失次数=指令数×平均每条指令需要的访存次数×Cache缺失率=1.2×100×5%=6。缺失后需要加载一个Cache块，Cache块大小为32字节，每次突发传送32字节，缺失后需要32B/32B=1次突发传送，根据(3)的计算结果，一次读突发传送总线事务所需的时间是85ns，所以指令执行过程中因Cache缺失造成的额外开销=Cache缺失次数×每次Cache缺失需要的突发传送次数×每次突发传送总线事务所需的时间=6×1×85ns=510ns。

BP的CPU执行时间=指令访问Cache执行时间+指令访问主存执行时间=500ns+510ns=1010ns。

方法二：BP的CPU执行时间包括Cache直接命中时的指令执行时间和Cache缺失时的指令执行时间。

Cache直接命中时的指令执行时间：BP共执行了100条指令，Cache缺失率是5%，Cache命中时的CPI为4，即每条指令访问Cache的CPI为4，CPU的时钟周期为1.25ns，所以Cache直接命中时的指令执行时间是100×4×1.25ns×(1-5%)=475ns。

Cache未能直接命中时的指令执行时间：因为BP共执行了100条指令，平均每条指令需要1.2次访存，Cache缺失率是5%，Cache缺失率=Cache缺失次数/访存次数，访存次数=指令数×平均每条指令需要的访存次数，（注意，不同指令需要的访存次数不一定相同。）得到Cache缺失次数=指令数×平均每条指令需要的访存次数×Cache缺失率=1.2×100×5%=6。缺失后需要加载一个Cache块，Cache块大小为32字节，每次突发传送32字节，缺失后需要32B/32B=1次突发传送，根据(3)的计算结果，一次读突发传送总线事务所需的时间是85ns，所以指令执行过程中因Cache缺失造成的额外开销=Cache缺失次数×每次Cache缺失需要的突发传送次数×每次突发传送总线事务所需的时间=6×1×85ns=510ns。然后重新访问Cache块加载数据，Cache命中时的CPI为4，重新访问Cache块加载数据的时间是100×4×1.25ns×5%=25ns。总开销510ns+25ns=535ns。

BP的CPU执行时间=Cache直接命中时的指令执行时间+Cache未能直接命中时的指令执行时间=475ns+535ns=1010ns。

注：实际上，在现代计算机中，访问cache未命中，无需要再访问一次Cache，因为再访问一次Cache相比直接将获取到的数据直接送入CPU开销更大。

(1) 第一问。因计算机采用16位定长指令字格式，且下条指令地址为(PC)+2，PC自增是一个指令字长的字长数，16bit/2=8bit=1B，所以编址单位是字节。

第二问。观察条件转移指令格式，偏移OFFSET为8位补码，范围为-128~127，所以相对于当前条件转移指令，PC自增后偏移，向后偏移OFFSET最小为-128，向后最多可跳转 |1−128|=127 条指令。

(2) 指令中C=0，Z=1，N=1，所以根据本题中检测位的定义，应根据ZF和NF的值来判断是否转移，ZF=1或NF=1时发生转移，即 ZF∨NF=1 时发生转移，否则不发生转移。

第一问。当CF=0，ZF=0，NF=1时， ZF∨NF=1 ，需转移。已知指令中偏移量为11100011B，符号扩展后为1111111111100011B，左移一位（乘2）后1111111111000110B=FFC6H，转移执行时，转移目标地址为(PC)+2+2×OFFSET=200CH+2H+FFC6H=1FD4H。

第二问。当CF=1，ZF=0，NF=0时， ZF∨NF=0 ，不转移。PC 的值为200CH+2H=200EH。

(3) 无符号数比较小于等时转移，设a<=b为真，移项得a-b<=0为真，所以CF=1或ZF=1为真，因为C、Z和N分别为CF、ZF和NF的对应检测位，所以指令中的C、Z和N应分别设置为C=1，Z=1，N=0。

(4) 部件①存放指令。推出：部件①为指令寄存器IR；从指令中可以取出OFFSET，以执行后续操作。

计算式(PC)+2+2×OFFSET中，先执行OFFSET乘以2（算数左移1位），再执行加法，2×OFFSET加上(PC)+2（右边的加法器执行(PC)+2操作）。数据通路从IR出来了后先经过部件②再经过部件③。可以推出：部件②为移位寄存器SR；部件③为加法器ALU。

本题考察记录型信号量的基本使用，资源信号量的命名直接用资源的名称命名即可。

某博物馆最多可以容纳 500 人同时参观，设博物馆的资源初始信号量为 museum=500 或 empty=500 。

有一个出入口，该出入口一次仅允许一个人通过，设出入口的资源初始信号量为 door=1 。由于资源数恰巧为 1 ，用一个互斥信号量 mutex=1 表示也是可以的。

由于这里人的所有操作都是可以手动（主动）调用信号量，不需要添加 while(1) 或者 while(true) 死循环。

semaphore museum = 500;    // 博物馆可容纳人数
semaphore door = 1;    // 出入口可容纳人数
cobegin
参观者进程i:
{
    P(museum);
    P(door);
    进门;
    V(door);
    参观;
    P(door);
    出门;
    V(door);
    V(museum);
}
coend

这道题P(museum)和P(door)的顺序上要先P(museum)再P(door)，也就是先保证博物馆未满再进人。如果先P(door)再P(museum)，我们假想一直特殊情况，此时有人进门了，博物馆恰好满了，一个人正好要进人博物馆，执行了P(door)，门就被堵死了，外面的人进不去，里面的人出不来。同理，最后V(museum)和V(door)的顺序上要先V(door)再V(museum)。

或者改写用empty和mutex命名，重写如下：

semaphore empty = 500;    // 博物馆可容纳人数
semaphore mutex = 1;    // 用于出入口资源的控制
cobegin
参观者进程i:
{
    P(empty);
    P(mutex);
    进门;
    V(mutex);
    参观;
    P(mutex);
    出门;
    V(mutex);
    V(empty);
}
coend

使用互斥锁mutex有一个原则，mutex控制的互斥操作里面只包含必要操作，P(empty)和V(empty)都防止互斥操作外面，这样可以不用进行上面那么繁琐的分析。

【答案要点】

（1）因为页内偏移量是 12 位，所以页大小为 4 KB，（1 分）
页表项数为 \(2^{32}/4K = 2^{20}\)，该一级页表最大为 \(2^{20}×4 B = 4 MB\)。（2 分）
（2）页目录号可表示为：(((unsigned int)(LA))>>22)&0x3FF。（1 分）
页表索引可表示为：(((unsigned int)(LA))>>12)&0x3FF。（1 分）

【评分说明】
① 页目录号也可以写成((unsigned int)(LA))>>22；如果两个表达式没有对 LA 进行类型转换，同样给分。
② 如果用除法和其他开销很大的运算方法，但对基本原理是理解的，同样给分。
③ 参考答案给出的是 C 语言的描述，用其他语言（包括自然语言）正确地表述了，同样给分。
（3）代码页面 1 的逻辑地址为 0000 8000H，表明其位于第 8 个页处，对应页表中的第 8 个页表项，所以第 8 个页表项的物理地址 = 页表起始地址 + 8×页表项的字节数 = 0020 0000H + 8×4 = 0020 0020H。由此可得如下图所示的答案。（3 分） 

【评分说明】共5个答数。物理地址1和物理地址2共1分；页框号1和页框号2共1分；物理地址3给1分。

(1) 题目要求利用路由聚合技术，使得 R2 的路由表中的路由项尽可能少。可以根据 R2 的接口进行划分。

153.14.5.0/25 和 153.14.5.128/25 都通过 R2 的 S0 接口连接 R2，可以将两者进行聚合。显然两者的前 24 位完全相同，将两者后 8 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。153.14.5.0/25 为 153.14.5.0xxxxxxx ，153.14.5.128/25 为 153.14.5.1xxxxxxx ，两者前 24 位完全相同，聚合为 153.14.5.xxxxxxxx ，即 153.14.5.0/24。

194.17.20.128/25 通过 R2 的 E0 接口连接 R2，单独构成一个路由。

194.17.20.0/25 和 194.17.21.0/24 都通过 R2 的 S0 接口连接 R2，可以将两者进行聚合。显然两者的前 16 位完全相同，将两者后 16 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。194.17.20.0/25 为 194.17.00010100.0xxxxxxx ，194.17.21.0/24 为 194.17.00010101.xxxxxxxx ，两者前 23 位完全相同，聚合为 194.17.0001010x.xxxxxxxx ，即 194.17.20.0/23。

最终得到 R2 的路由表如下：

(2) 查路由表，目的 IP 地址为 194.17.20.200 的 IP 分组和目的网络 194.17.20.128/25 和 194.17.20.0/23 的前3个十进制数相同，即前 24 个比特位均相同，根据最长前缀匹配原则，194.17.20.200 会被转发到子网 194.17.20.128/25，R2 会通过接口 E0 转发该 IP 分组。

(3) 由于 R1 和 R2 分属自治系统 AS1 和 自治系统 AS2，需要使用外部网关协议 (Exterior Gateway Protocol, EGP) 交换路由信息，由于 EGP 存在很多的局限性，IETF 边界网关协议工作组制定了标准的边界网关协议 (Border Gateway Protocol, BGP)，当前被广泛使用，目前已经升级到 4.0 版本，即 BGP4，BGP4 是最广泛使用的 BGP 版本，也是当前的域间路由标准。R1 与 R2 之间利用 BGP4（或 BGP）交换路由信息；BGP4 的报文被封装到 TCP 协议段中进行传输。