【参考答案】D

解析 观察程序发现，语句 “A[j] 与 A[j + 1] 对换;” 执行频率较高，且该语句并不影响双重 for 循环判断语句，但会影响 if 的判断语句。当 A 数组的所有元素都逆序时，该语句一直执行，此时为最坏情况。该语句在最坏情况下的频度是 O(n²)，选 D。

【参考答案】D

【解析】删除 p 之后结点，因题中没有 free 的要求，只需将 p 的 next 指针指向其后继结点的 next 指针，因此执行“p->next=p->next->next;”

【参考答案】C

【解析】

根据栈 “先进后出” 的原则，逐一分析各个选项：

选项 A（543612）
进栈顺序：6 进→5 进→5 出→4 进→4 出→3 进→3 出→6 出→2 进→1 进→1 出→2 出。
合法序列。

选项 B（453126）
进栈顺序：6 进→5 进→4 进→4 出→5 出→3 进→3 出→2 进→1 进→1 出→2 出→6 出。
合法序列。

选项 C（346521）
进栈顺序：6 进→5 进→4 进→3 进→3 出→4 出→此时栈内元素为 5、6（栈顶为 5），但下一个出栈元素为 6，需先弹出 5，因此无法直接弹出 6。
不合法序列。

选项 D（234156）
进栈顺序：6 进→5 进→4 进→3 进→2 进→2 出→3 出→4 出→1 进→1 出→5 出→6 出。
合法序列。

综上，选项 C 违反了栈的操作规则，因此不是合法的出栈序列。

【参考答案】B

【解析】删除一个元素则front+1，插入两个元素则rear+2，因此是2 和4。

【参考答案】B

【解析】这类题目可以从选项出发，通过模拟计算后缀表达式的结果与中缀表达式比较得出答

案，也可以通过本节中所说的办法将中缀表达式转化成后缀表达式获得。A 不符合后缀表达式的形式，D 先计算F+G，显然不对。对于C，若进行计算，弹出AB+ 执行A+B 压栈，弹出C*，

相当于执行(A+B)*C，错误。对于B，弹出AB+ 执行(A+B)，压入(A+B)，弹出(A+B)，C，D，

-，执行(C-D)，压入(C-D)，(A+B)，再弹出至*，执行(A+B)*(C-D)，后面也都符合表达式。

参考答案：C
解析：上三角矩阵第 1 行 6 个元素，第 2 行 5 个，以此类推，A35是第 3 行的第 3 个元素，因此答案为6 + 5 + 3 = 14

【参考答案】C

【解析】设叶结点数是 n，利用结点数目与度的关系，有x+2y+3z=n+x+y+z-1，得n=1+y+2z。

【参考答案】C

【解析】设二叉树中\(n = n_0 + n_1 + n_2\)，结点总数\(=2n = n_0 + n_1 + n_2 = n_1 + 2n_2 + 1\)，则\(n_1 = 2(n - n_2) - 1\)，所以\(n_1\)是个奇数，那么该二叉树中不可能有偶数个度为 1 的结点。

【参考答案】C

【解析】先序遍历中祖先必然先被遍历，后代是后面才会被遍历的，A错:若m在n的右子树里面，则中序遍历序列里n定在m 的前面，B错:若m 在n的右子树里面，后序遍历序列里m 定在n的前面，选C;层次遍历中，祖先一定在后代的前面被遍历，D错

【参考答案】D

【解析】并非每个结点通过线索化都可以直接找到其前驱和后继。查找后序后继是需要知道其双亲结点的，二叉链表没有存放双亲的指针。

【参考答案】C

【解析】本题容易误选D。要注意的是，本题问的是顶点v在边表中出现的次数，即不关心顶点表中v的出现次数。根据邻接表的结构可知，在有向图中，顶点v出现在边表中的次数即等于顶点v的入度。选择C。

【参考答案】D

【解析】CPU 执行时间=指令条数×CPI×时钟周期，假设该程序有x条指令，则计算机A的执行时间为 2.4ns×4x，计算机B的执行时间为 4ns×2x，计算机A执行时间是计算机B的 1.2倍，故计算机B的速度是计算机A的 1.2倍。B 选项的同义表述为计算机B的速度是计算机 A的 2.2 倍，所以错误。

【参考答案】D

【解析】n + 1 位补码表示的最大整数的形式为011 · · · 11，真值为2^n − 1，D 的表述有误，选D。考生应该熟练掌握这4 种常见的补码二进制形式。

【参考答案】A

【解析】IEEE 754 单精度浮点数（32 位）的组成为：符号位（第1 位），阶码（第2∼9 位），数值位（后23 位）。该数的机器数为0100 0010 1110 0100 1000 0000 0000 0000B，阶码为10000101=133，由于阶码用移码表示，所以实际值=133-127=6，所以该数=457/256×2^6=114.25。

提示：本题所用计算方法为将数值位中的最低位作为最小单位，本题最低位为1/256，由数值有效部分110 0100 1 按照1+8+64+128+256(隐含位)=457，最终得到457/256。

【参考答案】D

【解析】IEEE 754 单精度浮点数格式：数符（1 位）+ 阶码（8 位）+ 尾数（23 位），尾数最高位的“1”是被隐藏的。

先将−9 转换成二进制为−1001B = −1.001×2^3，然后计算阶码E，有E −127 = 3，因此E = 130，转换成二进制为1000 0010，又因为符号位为1，故−9 的IEEE 754 表示为1100 0001 0001 0000 0000 0000 0000 0000B，即C110 0000H。

根据题目中 int 和 short 的长度规定，分析如下：

变量 x 的赋值：
unsigned short x = 32768;

unsigned short为 16 位，范围 0~65535。

32768 的二进制表示为1 0000 0000 0000 0000（17 位）。

截断为 16 位后得到1000 0000 0000 0000，即0x8000。

变量 y 的赋值：
unsigned int y = x;

unsigned int为 32 位，需将 16 位的x零扩展到 32 位。

x的 16 位值0x8000扩展后为0000 0000 0000 0000 1000 0000 0000 0000，即0x00008000。

答案：D. 8000H，00008000H

【参考答案】D

【解析】执行的是减法运算，加法器的低位进位输入Cin = 1，[A]补 = BCH，[-B]补 = 8FH，A - B = [A]补 + [-B]补 = [A]补 + [-B]补 = BCH + 8FH = 01001011B，参与运算的两个数符号位为 1，结 果符号位为 0，发生溢出，溢出标志 OF = 1，最高位进位 Cout = 1，最高数值位进位为 0，D 对。 提示：计算机可以通过将最高位进位与最高数值位异或来判断溢出。本题中前者为 1，后者为 0，两者异或后 OF = 1。

【参考答案】A

【解析】字长16 位=2B，即一个地址单元可以放2 个字节，总容量为128KB，需要64K 个地址

单元，所以寻址范围是64K。

【参考答案】C

【解析】根据局部性原理设计的存储器层次化结构，能提高每层命中率，从而在相邻两层存储器

间，使得速度向较高层靠近的同时，让容量和价格向较低层靠近。

参考答案：C

解析：题目中 SRAM 容量为 1024K×32 ，按字节编址，因为 1024K = 2^20 ，log₂2²⁰ = 20，所以地址线有 20 条。每读写 4B 数据，数据线数量为 4×8 = 32 条。

【参考答案】 C

【解析】由于分为8组，所以组号y为3（\(2^{3}=8\)）。块大小64B，所以块内地址z为6（\(2^{6}=64\)）。主存共8192块且块大小为64B，则主存地址一共19位（\(\log_{2}8192+\log_{2}64 = 13 + 6 = 19\)），所以标记位 \(x = 19 - 3 - 6 = 6\) 。

【参考答案】D

【解析】D 不存在，页缺失，说明信息不在主存，Cache 存的是主存信息的副本，即Cache 内容

是主存内容的子集，故Cache 一定也没有该信息。

【参考答案】B

【解析】多道批处理系统相比于单道批处理系统，有了多道程序设计技术。这项技术可以使程

序轮流使用CPU，CPU 始终处于忙碌状态，提高CPU 利用率。交换技术、覆盖技术和紧凑技

术都是内存管理的内容。所以正确答案为B 选项。

【参考答案】B

【解析】I/O 指令是对I/O 设备进行操作的指令，只能操作系统在内核态执行，读时钟指令、加

法指令和陷入指令可以在用户态执行，其中陷入指令只能在用户态执行。选B。

【参考答案】A

【解析】微内核的用户空间和内核空间分离，用户服务的崩溃不会影响到内核空间，因此可靠

性较好。微内核需要增加服务时，只需要在用户空间增加模块，不需要修改内核，因此具有较

好的可扩展性和可移植性。微内核由于各模块之间的通信要经过内核的消息传递，系统运行效

率较低。所以正确答案为A 选项。

【参考答案】C

【解析】并行的进程之间，可以利用信号量等机制实现同步、互斥等关系，但是并不是所有并行（或并发）进程间都有相互依赖或制约的关系，所以C 选项错误。一个简单的例子：一个系统中，有一个音乐播放进程，有一个聊天进程，这两个进程运行时可以没有任何联系。A、B、D选项均是对进程特点的正确叙述。

【参考答案】A

【解析】先来先服务一定是非抢占式，时间片轮转一定是抢占式的，优先级和短进程优先既可以是非抢占的，也可以是抢占的。

【参考答案】C

【解析】本题考查了临界资源和临界区的基本概念，同一时间只能由一个进程使用的资源称为临界资源，临界资源是互斥共享资源，I 和II 正确；程序中访问临界资源的那一部分代码称为临界区，III 正确，IV 错误，故本题选C。

【参考答案】C

【解析】生产者和消费者要互斥访问缓冲区，故两者存在互斥关系，B 和D 错误；生产者和消费者协作完成生产和消费，消费者负责消费生产者生产的产品，存在一种先生产后消费的同步关系，A 错误，故本题选C。

【参考答案】A

【解析】管程一次只允许一个进程进入，这是由管程的互斥性决定的，A 错误；管程包含了面向对象的思想，将表达共享资源的数据结构和对其进行操作的进程封装在一个对象中，并封装了同步操作，从而对进程隐藏同步的细节，简化了调用同步功能的接口，B 正确；管程机制可以便于集中管理分散于不同进程的临界区，C 正确；管程是进程同步工具，避免了信号量机制中大量且分散的同步操作，D 正确。题干要求选择错误选项，故本题选 A。

【参考答案】B

【解析】极端法：假设每个进程已获得3 个同类资源，则只要有可用的资源，总能有一个进程可以获得第4 个，然后顺利执行，而不会产生死锁。在极端情况下，12 个资源被分给4 个进程，每个进程获得3 个，是有可能产生死锁的，而再增加一个资源，就必然不会产生死锁，此时的资源数量是13。故本题选B。

【参考答案】C

【解析】一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁的必要条件中的不可剥夺条件，可以通过剥夺资源法来破坏，所以本题选C。

【参考答案】D

【解析】计算机网络中的共享资源是指加入网络的用户能够使用网络中各个计算机系统的各种资源，包括软件、硬件以及数据资源等，A 错误。分布式系统是建立在计算机网络之上的软件系统，B 错误。计算机网络最基本的功能是资源共享，C 错误。计算机网络在逻辑组成上可以分为通信子网和资源子网，D 正确，因此答案为D。

【参考答案】B

【解析】一个载波信号码元有4 个有效离散值说明一个码元需要log₂4 = 2 个比特表示，信号传输速率为64kb/s，则波特率为64 ÷ 2 = 32kBaud，因此答案为B。

【参考答案】B

【解析】中继器和放大器无法保证可靠传输和存储转发，同样也无法做到复用和分用，ACD 错误。但是都能用于网络延伸和范围扩大，但是原理不同，放大器作用于模拟信号，只是简单地放大信号，中继器作用于数字信号，将信号整形放大再转发出去，因此答案为B。

【参考答案】B

【解析】电路管理是物理层的功能，注意不要与数据链路层的链路管理功能混淆。电路通常指信号传输的实际物理载体（也称物理链路），而数据链路是在电路的基础之上附加上了链路通信协议。电路管理功能管理的是物理链路，链路管理功能管理的是数据链路。

参考答案：C

解析：GBN 协议的接收窗口大小为 1，所以 \(W_R + W_T=1 + W_T\leq2^3\)，可得 \(W_T\leq7\)，选 C。

【参考答案】B

【解析】冲突域最大距离变短，则最大往返时间减少，即争用期减少，可以更早确定无冲突，所以最短帧长可以减少，选项A 错误。注意区分传输速率和传播速率，传输速率提高则可以更快的发完原有的最短帧长，所需时间比争用期短，解决办法为提高最短帧长，选项B 正确。上层协议使用TCP 的概率增加与最短帧长度无关，选项C 错误。减少中继器数量可以减小因中继器而产生的转发时延，使最大往返时间减少，即争用期减少，需要减少最短帧长度，选项D 错误。因此答案为B。

【参考答案】B

【解析】由于隐蔽站、暴露站等问题，在无线局域网中进行冲突检测（CD）的意义不大，所以转而使用冲突避免（CA）这一方法尽可能地减少冲突发生的可能性，因此答案为B。

【参考答案】D

【解析】由于交换机支持并行传输，且可以工作在全双工状态下，所以其最大带宽为所有端口

带宽之和的两倍，为2 × (24 × 100Mbps + 2 × 1Gbps) = 8.8Gbps，因此答案为D。

(1) 顺序遍历坐标为偶数的元素，与后一个元素比较，如果前一个元素与后一个元素不一样，则前一个元素为目标值。

(2) 算法实现：

int func(int *A, int n) {
    for (int i = 0; i < n - 1; i += 2) {
        // 每次比较一对数字,不相等则前一个元素为目标元素
        if (A[i] != A[i + 1]) { return A[i]; }
    }
    return A[n-1]; // 最后一个元素为目标元素
}

(3) 算法中需要顺序遍历数组，时间复杂度为O(n)。

【参考答案】

(1) 一定能得到所有字符对应的编码长度都相同的哈夫曼树，对N个出现频率相同的字符构造哈夫曼树，得到高度为\((\log_2N)+1\)的满二叉树，每个字符的编码长度为\(\log_2N\)。

(2) 每个编码的长度为\(\log_2N\)，共有N个字符，最小带权路径长度WPL为\(N\times\log_2N\)。

(3) 对于长度为M的字符序列，ASCII码占7bit，压缩前需要7M bit存储，压缩后，每个字符的编码长度为\(\log_2N\)，压缩后需要\(M\times\log_2N\)M bit存储，压缩比是\((\log_2N)/7\) 。

【参考答案】

(1) R2 = 0000 FF38H，R4 = FFFF FF38H，R5 = 0000 0064H，R6 = 0000 01F4H。 us2为unsigned short类型，其值为65336 = \(2^{16}-200 = FF38H\)，将其分配到32位寄存器需要进行零扩展，所以R2 = 0000 FF38H； m1为unsigned short类型，us1 + us2 = 65636，超出unsigned short的最大表示范围65535，因此会溢出到无符号数65636% \(2^{16}\) = 100 = 0064H，分配到32位寄存器需要进行零扩展，所以R5 = 0000 0064H； us2 = 65336 = FF38H，将其转换为short类型，机器数不变，改变解释方式，可知s2为负数，将其分配到32位寄存器需要进行符号扩展，所以R4 = FFFF FF38H； m2为unsigned short类型，us1 - us2 = -65036，因此会溢出到无符号数 - 65036% \(2^{16}\) = 500 = 01F4H，分配到32位寄存器需要进行零扩展，所以R6 = 0000 01F4H。

(2) n1 = 100，n2 = 500。us1 = 300，按有符号数解释s1 = 300。s2的机器数为FF38H，按有符号数解释s2 = -200。s1 + s2 = 100，s1 - s2 = 500，结果均在short型变量表示范围内，未发生溢出。所以n1 = 100，n2 = 500。

(3) m1 = us1 - us2，由于us1 < us2，因此会产生借位，所以CF = 1；结果不为0，所以ZF = 0。

(4) 计算机内部判断CF的逻辑表达式为CF = Cin⊕ Cout，其中Cin为低位进位输入，当执行减法时Cin = 1，执行加法时Cin = 0，Cout为最高位进位输出； 当执行有符号加/减运算时也会按上述规则产生CF标志位，这是因为加法器对于无/有符号加减法是统一的，在电路层面数据只是一个二进制串，所以会同等产生各标志位。但需要注意的是，对于有符号加/减运算，CF标志位是没有意义的。

【参考答案】

(1) 由于数组按行优先存储，所以空间局部性较好，每个元素只被访问一次，所以时间局部性较差。
(2) 由于每个主存块为 16 字节，则每个块可以存储 4 个 float 数组元素。直接映射方式，一共 32/16 = 2 行，行号 1 位为 32 位地址中的倒数第 5 位，起始地址 0000 0040H 位于一个块的起始位置。由于数组 x 需要占用物理地址中的连续的 2 块，因此分别对应 Cache 中的 0、1 行，数组 y 紧随其后，也对应 0、1 行，因此循环内的语句执行时，依次访问 x 与 y 数组的同一元素，将会导致 Cache 同一块中的内容不停地在 x 数组与 y 数组之间切换，比如计算到 x [1]×y [1] 时，原本 Cache 第 0 行存放的是 y [0] 至 y [3] 元素，需要先将 x [0] 至 x [3] 换入，再将 y [0] 至 y [3] 换入，因此每次访问都不会命中，命中率为 0%。
(3) 二路组相联，块大小为 8 字节，共有 2 组。其他条件不变，则每个块可以存储两个数组元素，x [0]~x [1]、x [2]~x [3] 依次对应 0、1 组以此类推，y [0]~y [1]、y [2]~y [3] 也依次对应 0、1 组，每组可以容纳两个数组相同位置的两个元素，比如 x [0]、y [0] 和 y [0]、y [1] 可以分别换入到 0 组的 0 路、1 路中，访问 0 号元素时未命中，访问 1 号元素均可以命中，因此命中率为 50%。
(4) 数组 x 的大小将占据 3 个 Cache block 的大小，数组 y 占据 2 个。x 数组中三个块对应的 Cache 行号分别为 0、1、0，实际程序不会访问 8~11 号元素，y 数组中两个块对应的 Cache 行号是 1、0，访问同一位置的元素时，两个数组占据的 Cache 行不冲突，则访问数组 x 和数组 y 的第 0、4 号元素不命中（共 4 次），其余的元素可以命中，命中率为 12/16×100% = 75%。

【参考答案】

(1) 5个进程在运行过中的优先级如下表所示：

由题意可知，CPU会优先调度优先级低的进程，5个进程的执行顺序如下：

(2) 进程的周转时间 = 等待时间 + 执行时间，进程的响应时间是指用户提交请求到系统首次响应所用的时间。由进程执行的顺序图可知，$P_1$的周转时间 = 5 + 3 = 8s，$P_1$的响应时间 = 0 - 0 = 0s，$P_2$的周转时间 = 0 + 2 = 2s，$P_2$的响应时间 = 1 - 1 = 0s，$P_3$的周转时间 = 4 + 3 = 7s，$P_3$的响应时间 = 4 - 2 = 2s，$P_4$的周转时间 = 0 + 1 = 1s，$P_4$的响应时间 = 3 - 3 = 0s，$P_5$的周转时间 = 5 + 2 = 7s，$P_5$的响应时间 = 9 - 4 = 5s。

【参考答案】

Semaphore mutex_well = 1; //实现对水井这一互斥资源的互斥访问
Semaphore mutex_vat = 1; //实现对水缸这一互斥资源的互斥访问
Semaphore vat_empty = 10; //水缸剩余能容纳的水的桶数
Semaphore vat_full = 0; //水缸已容纳的水的桶数
Semaphore pail = 3; //空闲的水桶的数量

CoBegin{
    process 小和尚 {
        while(TRUE){
            P(vat_empty); //（同步）申请向水缸倒水，若水缸已满则等待
            P(pail); //申请使用空闲水桶，如没有空闲水桶则等待
            P(mutex_well); //（互斥）防止他人使用水井
            从井中取水;
            V(mutex_well); //（互斥）允许他人使用水井
            P(mutex_vat); //（互斥）防止他人使用水缸
            将水倒入水缸;
            V(mutex_vat); //（互斥）允许他人使用水缸
            V(vat_full); //（同步）水缸已用容量加1，若有老和尚喝水则通知
            V(pail); //释放一个空闲水桶，若有和尚在等待使用，则通知
        }
    }
    process 老和尚 {
        while(TRUE){
            P(vat_full); //（同步）申请从水缸取水，若水缸为空，则等待
            P(pail); //申请使用空闲水桶，如没有空闲水桶则等待
            P(mutex_vat); //（互斥）防止他人使用水缸
            从水缸取水;
            V(mutex_vat); //（互斥）允许他人使用水缸
            V(vat_empty); //（同步）水缸剩余容量加1，若有小和尚等打水则通知
            喝水;
            V(pail); //释放一个空闲水桶，若有和尚在等待使用，则通知
        }
    }
}CoEnd

【解析】

(1) 传播时延为 4.8μs。信号在信道中传播需要的时间为\(\frac{800m}{2×10^{8}m/s}=4μs\)。中间经过四个转发器，消耗时间为\(4×\frac{20bit}{100Mbit/s}=0.8μs\)。所以总的传播时延为\(4μs + 0.8μs = 4.8μs\)。

(2) 在\(t = 2.94×10^{-5}s\)时 B 完全收到 A 发送的帧。发送一帧的传输时延为\(\frac{1500bit}{100Mbit/s}=15μs\)，而单向传播时延为 4.8μs，所以当 B 收到 A 发送的第一个比特时（即检测到信道冲突时），发送还未结束。整体的时间线如下：

(a) \(t = 0\)，A 和 B 同时发送帧。

(b) \(t = 4.8μs\)，A 和 B 同时检测到冲突，均停止发送。

(c) \(t = 4.8μs + 4.8μs = 9.6μs\)，B 已发送的最后一个比特到达 A，A 检测到冲突结束，立即重传。

(d) \(t = 9.6μs + 4.8μs = 14.4μs\)，A 发送的第一个比特到达 B（此时 B 在退避中，未发送数据）。

(e) \(t = 14.4μs + 15μs = 29.4μs\)，A 发送的最后一个比特到达 B。

【注意】根据 CSMA/CD 的机制，B 的退避时间结束后，由于 A 还在发送数据，此时 B 会继续等待到信道空闲后才继续发送。