解答：

设原来插入新结点前指向 p 的直接后继结点的指针为 q ，题目要求在 p 和 q 之间插入新的结点 s 。

双向链表插入结点的时候要修改四个指针，这四个指针的修改顺序没有强制要求，也就是有 4!=24 种连接顺序，但是这里注意要按照题目要求的顺序连线。

初始为图(a)。四个指针的初始状态为：

p->next = q; q->prev = p; s->next = null; s->prev = null;

最终状态为：

p->next = s; q->prev = s; s->next = q; s->prev = p;

先按照题目要求执行前两步：

s->next = q; 注意此时 q = p->next，即 s->next = p->next; 此时变为图(b)。

p->next = s; 此时变为图(c)。

还有两条线没有连，目标是得到图(d)。还需要连接 s->prev = p; 和 q->prev = s; 注意此时 q = s->next，即 s->next->prev = s; 找了一圈发现没有这种写法，命题组在这里加大了难度，把写法复杂化，我们只能逐一分析选项了。按照选项的指针在图(c)上运行：

A选项，等价于 q->prev = p; s->prev = p; 第一句错误。

B选项，等价于 s->prev = s; s->prev = p; 第一句错误。

C选项，等价于 s->prev = p; q->prev = s; 正确。

D选项，等价于 s->prev = null; q->prev = p; 第一句和第二句均错误。

本题选C。

解答：

三元组存储矩阵的表示方法出现在2017年第3题，三元组表的表项存储了行row、列col、值value三种信息，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出，即 I 和 III 。

本题选A。

解答：

构建哈夫曼树：

每个关键字的查找长度为：

注意，题目要求求加权平均长度，这里的权重就是频次。

加权平均长度为 (3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5 。

如果不考虑权重，会错误计算为 (3+3+3+3+2+2)/6≈2.67 ，从而误选C。

本题选B。

方法一：递归法

首先按照后序遍历左右根的递归遍历顺序自下而上，从左到右将 f, d, b, e, c, a 填入二叉树。

然后按照先序遍历根左右的递归顺序输出先序序列 a, e, d, f, b, c 。

本题选A。

方法二：环线法

首先构造环线按后序遍历顺序填入后序序列 f, d, b, e, c, a 。

然后按照环线进行先序遍历输出先序序列 a, e, d, f, b, c 。

本题选A。

注：补充一下二叉树前序遍历、中序遍历、后序遍历的特征：

按照箭头方向遍历。

• 前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。
• 中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。
• 后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。

解答：

无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可以用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更加高效。III正确。

I 和 II 是最小生成树算法，也可直接排除。

本题选B。

解答：

I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高度加一。I 正确。

II.

• 如果删除的关键字位于叶结点：
  • 在叶结点中删除该关键字，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果删除该结点后关键字个数 n≥⌈m/2⌉−1 ，没有后续操作，如果该结点删除关键字后关键字个数 n<⌈m/2⌉−1 ，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。无论上述哪种情况，此时叶结点一定发生变化。
• 如果删除的关键字位于非叶结点：
  • 用被删除关键字的后继关键字替换被删除关键字，该后继关键字为于被删除关键字的右子树的最下层最左边，即一定位于叶结点，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果该结点删除关键字后关键字个数 n≥⌈m/2⌉−1 ，没有后续操作，如果删除该结点后关键字个数 n<⌈m/2⌉−1 ，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。此时叶结点一定发生变化。

综上，无论删除关键字是位于叶结点还是位于非叶结点，一定有叶结点发生变化。II 正确。

III. B树中所有结点均可以存储关键字，若查找的关键字位于非叶结点，则不可能查找到叶结点。III错误。

IV. 插入新的关键字，插入后进行调整，新插入的关键字不一定位于叶结点中。可以用依次将关键字5, 6, 9, 14, 8, 2, 12, 15, 13插入初始为空的4阶B树进行模拟，最后13位于非叶结点中。也就是插入关键字后若被插入关键字所在的结点需要进行调整（结点发生分裂），且被插入的关键字此时恰为该结点的第 ⌈m/2⌉ 个关键字，则该关键字会上溢到该结点的父结点，如此迭代，也就是在这种情况下被插入的关键字最终一定位于非叶结点中。

综上，I 和 II 正确。

本题选B。

解答：

由于元素数量过大，不方便画图，采用公式法。

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

二叉搜索树高度为 ℎ=⌈log⁡(n+1)⌉=⌊log⁡n⌋+1 。

代入 n=600 ，解得 ℎ=10 。

本题选B。

解答：

本题为送分题，牢记八大排序表格。

稳定的排序有：插入排序、冒泡排序、归并排序、基数排序。

不稳定的排序有：选择排序、希尔排序、快速排序、堆排序。

本题选C。

解答：

快速排序一个非常重要的性质是枢轴左边的关键字全部小于或等于枢轴，枢轴右边的关键字全部大于或等于枢轴。

由于序列比较长，正向推导不容易观察，可以代入选项后分析。

A选项，枢轴为11 ，左边 68 > 11 。该选项错误。

B选项，枢轴为70 ，右边 23 < 70 。该选项错误。

C选项，枢轴为80，右边 48 < 80 。该选项错误。

D选项，枢轴为81。该选项正确。

本题选D。

解答：

short为16位有符号整型，最高位为符号位， −8190=(8192−2)=−((2^13−1)−1) ， 2^13−1 的二进制表示为 13 个 1，[x]原=1001 1111 1111 1110B，将原码除符号位外取反加1转换为补码，[x]补=1110 0000 0000 0010B=E002H。

本题选A。

本题选A。

本题选C。

解答：

int为32位有符号整型，int 为 32 位有符号短整型，用补码表示，最高位为符号位，表示范围为 −2^31∼2^31−1 。当 x=10, y=-20 时，x-y=30，显然在表示范围之内，不溢出，OF=0。

当 x=10, y=-20 时，[x]补=[x]原=0000 0000 0000 0000 0000 0000 0000 1010B=0000000AH，[y]原=1000 0000 0000 0000 0000 0000 0001 0100B，[y]补=1111 1111 1111 1111 1111 1111 1110 1100=FFFFFFECH，被减数和减数均视为无符号数，显然0000000AH不够减FFFFFFECH，0000000AH需要最高位的更高位借1，该减法发生借位，CF=1。

本题选B。

解答：

指令字由操作码、寻址特征和地址码三个字段组成，寻址特征字段用来指明指令属于那种寻址方式。若寻址方式是寄存器直接寻址，则地址码所指的通用寄存器存放的是操作数，若寻址方式是寄存器间接寻址，则地址码所指的通用寄存器存放的是操作数的地址。

本题选A。

数据通路由组合逻辑元件（操作元件）和时序逻辑元件（状态元件）组成。下列给出的元件中，属于操作元件的是（ ）。

I. 算术逻辑部件（ALU）

II. 程序计数器（PC）

III. 通用寄存器组（GPRs）

IV. 多路选择题（MUX）

A. 仅I、II

B. 仅I、IV

C. 仅II、III

D. 仅I、II、IV

解答：

组合逻辑元件（操作元件）不含存储信号的记忆单元，任何时刻产生的输出取决于当前的输入，加法器、算术逻辑单元（ALU）、译码器、多路选择器、三态门等都属于操作原件。时序逻辑元件（状态元件）包含存储记忆单元，各类寄存器和存储器，如通用寄存器组（GPRs）、程序计数器（PC）、状态/移位/暂存/锁存寄存器等，都属于状态元件。

本题选B。

I1     add s2, s1, s0   // R[s2] ← R[s1] + R[s0]
I2     load s3, 0(s2)   // R[s3] ← M[R[s2] + 0]
I3     beq t2, s3, L1   // if R[t2] = R[s3] jump to L1
I4     addi t2, t2, 20  // R[t2] ← R[t2] + 20
I5 L1: 

若采用转发（旁路）技术处理数据冒险，采用硬件阻塞方式处理控制冒险，则在 I1~I4 执行过程中，发生流水线阻塞的指令有（ ）。

A. 仅 I3

B. 仅 I2、I4

C. 仅 I3、I4

D. 仅 I2、I3、I4

解答：

I2和I1之间存在数据冒险，属于写后读数据冒险（read after write Data Hazard, RAW Data Hazard）：读取某数据操作必须在写入该数据操作之后执行，否则可能产生错误。I1在WB段才将新值写回寄存器R[s2]，但I2的EX段就要读R[s2]以计算访存的有效地址，I1在EX段结束时就已生成R[s2]的新值，被存放在EX→M流水段寄存器中，采用转发技术后，可以直接从该流水段寄存器中取出数据送到ALU输入端，这样I2执行时ALU用的是R[s2]的新值，解决了I1和I2的数据冒的险。

I3和I2之间存在数据冒险，属于装入-使用数据冒险（load-use Data Hazard）：LOAD指令和随后使用LOAD指令所加载数据的后续指令之间存在的依赖关系，即使用某数据操作必须在装入该数据之后执行，否则可能产生错误。仅用转发线路无法解决I2和I3之间的数据相关问题，需要用转发技术结合装入-使用阻塞解决。原因在于I2的功能是从内存中取数，只有在M段结束时才能从主存中得到R[s3]的新值，即先装入后使用，但I3的EX段就要用到R[s3]，I3需要阻塞1个时钟周期，等到I2的M段结束之后，从I2的M→WB流水段寄存器中取到R[s3]的新值。

常考的数据冒险有：写后读（read after write, RAW）数据冒险、写后写（write after write, RAW）数据冒险、读后写（write after read, WRA）数据冒险、装入-使用（load-use）数据冒险等。

在按序发射，按序流动的流水线中，可能出现写后读（RAW）数据冒险和装入-使用（load-use）数据冒险。

I4和I3之间存在控制冒险，beq指令在EX段计算转移目的地址，在M段确定是否将PC值更新为转移目的地址。因此在I4和I3日之间需要进行阻塞，I4的IF段要在I3的M段结束之后才能开始执行。I4的执行需要被阻塞3个时钟周期。

假设采用软件插入NOP指令的方法进行阻塞，指令的执行过程如下图所示。

本题选C。

解答：

每次传输包含传输地址、准备数据、传输数据三个阶段，总线时钟频率为 1GHZ，时钟周期为1ns，在总线上传输一个数据或地址需要一个的时钟周期，每次传输地址需要1ns，传输数据需要1ns，主存每次准备一个64位数据需要6ns，所以每次传输需要8ns。

由于总线不支持突发传送方式，所以每次只能传输一个总线宽度，总线宽度为64位，主存块大小为32B，所以需要传输32B/64bit=4次。读取一个主存块需要的时间为4×8ns=32ns。

本题选D。

解答：

A正确。CPU在执行指令期间会持续检测是否发生异常事件，例如除零错误、地址越界、非法指令等。如果检测到异常事件，CPU将立即终止当前指令的执行并跳转到异常处理程序。

B正确。CPU在执行完一条指令后会检测是否有中断请求。

C正确。开中断时，如果检测到中断请求，CPU将完成当前指令的执行后，立即进行中断响应，跳转到相应的中断服务程序来处理中断。即便是多重中断，CPU正在处理某个中断的过程中，由于中断屏蔽字的存在，CPU检测不到处理优先级更低的中断请求信号，若检测到中断请求信号，则说明其处理优先级更高，会立即响应。

D错误。外部设备并不会主动向CPU发送中断结束信号。CPU在接收到中断请求信号后，会执行中断处理程序，通过中断处理程序来处理相应的中断，中断服务程序执行结束后CPU会自行返回（中断服务程序最后一条指令是返回指令）。

本题选D。

解答：

A正确。查询方式下，通过 CPU 执行查询程序进行 I/O 操作。

B正确。中断方式下，通过 CPU 执行中断服务程序进行 I/O 操作。

C错误。DMA方式在预处理和后处理阶段需要CPU来处理，而数据传输阶段由DMA控制器完成。

D正确。对于SSD、网络适配器等高速设备采用DMA方式输入/输出。由于SSD、网络适配器等设备具有较高的速度和较大的数据传输能力，采用DMA方式能够更有效地利用设备的性能，提高数据传输速度。

本题选C。

与宏内核操作系统相比，下列特征中微内核操作系统具有的是（ ）。

Ⅰ. 较好的性能

Ⅱ. 较高的可靠性

Ⅲ. 较高的安全性

Ⅳ. 较强的可扩展性

A. Ⅱ、Ⅳ

B. Ⅰ、Ⅱ、Ⅲ

C. Ⅰ、Ⅲ、Ⅳ

D. Ⅱ、Ⅲ、Ⅳ

解答：

微内核是提供操作系统核心功能的内核的精简版本，它设计成在很小的内存空间内增加移植性，提供模块化设计，以使用户安装不同的接口。

微内核操作系统的优点：

①提高了系统的可扩展性。

②增强了系统的可靠性。

③可移植性强。

④提供了对分布式系统的支持

⑤融入了面相对象的技术。

I错误。微内核操作系统相比宏内核操作系统运行效率有所降低。在微内核操作系统中，因为客户和服务器、服务器和服务器直接的通信都需要通过微内核，所以在完成一次客户对操作系统提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模式与上下文的切换。

Ⅱ正确。微内核操作系统的设计理念是将核心操作系统功能限制在最小的内核中，将其他功能模块以外部服务的形式运行在用户态。这种设计使得操作系统核心更小、更简单，减少了代码复杂度和错误产生的可能性，从而提高了系统的可靠性。

Ⅲ正确。微内核操作系统通过将功能划分为不同的服务来实现，这些服务以独立的地址空间运行，彼此之间隔离，因此相对较容易实现安全性控制。由于核心内核非常简单，少量的核心代码意味着较少的漏洞和攻击面，从而提高了系统的安全性。

Ⅳ正确。微内核操作系统的设计使得各个功能模块以外部服务的形式存在，可以动态地加载和卸载这些服务模块，从而实现系统的灵活可扩展性。新的功能可以以插件或模块的形式添加，而不需要修改核心内核，这样可以减少对系统其他模块的影响，提高了系统的可扩展性。

综上，Ⅱ、Ⅲ、Ⅳ正确。

本题选D。

解答：

中断向量表是用于存储中断处理程序入口地址的数据结构。中断向量表的索引对应着中断类型号或中断向量号，而其中存储的值是对应中断类型的处理程序的入口地址。

使用数组作为中断向量表的数据结构有以下几个优点：

①快速访问：数组通过索引可以直接定位到对应位置的中断处理程序入口地址，具有常量时间复杂度的访问性能。这是因为中断类型号或中断向量号是连续的整数，可以通过简单的计算得到对应的数组下标。

②紧凑存储：由于中断类型号或中断向量号是连续的整数，使用数组可以直接按照顺序将中断处理程序的入口地址存储在连续的内存空间中，这样可以节省内存空间。

因此，中断向量表适合采用数组作为数据结构。

四个选项中也只有选项A支持随机访问。

本题选A。

解答：

因为物理内存大小为16 GB，页大小为4 KB，页框大小与页大小相等，页框数量最大为16 GB/4 KB = 2^22 。因为采用位图法，每个页框状态只需要1个比特位表示，所以位图所占的空间大小为 2^22 ×1 bit = 512 KB。

本题选C。

解答：

A错误。阻塞过程完成时，某进程从运行态进入阻塞态。

B错误。执行 CPU 调度完成时，某进行从就绪态进入运行态。

C错误。在操作系统中，当一个进程发起某种需要等待的操作（如等待I/O操作完成或等待某个信号），它会被标记为睡眠状态，然后被放入等待队列中。当满足等待条件时，操作系统会将进程从等待队列中唤醒，使其重新变为可执行状态。

D正确。当CPU执行系统调用时，会触发从内核态转换到用户态。系统调用是用户程序通过请求操作系统提供的服务或资源的一种机制，当用户程序需要执行特权操作或获取系统资源时，会通过系统调用发出请求。在执行系统调用期间，CPU会从用户态切换到内核态，以便操作系统执行相应的操作。完成系统调用后，CPU将再次切换回用户态，继续执行用户程序。因此，执行系统调用是导致CPU从内核态转换到用户态的操作。

本题选D。

解答：

A错误。发生键盘输入后，该线程可能需要等待键盘输入完成，说明该线程不具有执行所需的所有系统资源，进入阻塞态。

B错误。发生缺页异常后，该线程可能需要等待缺页处理程序处理完成，说明该线程不具有执行所需的所有系统资源，进入阻塞态。

C正确。该线程主动出让CPU后，不再不占用CPU，进入就绪态。

D错误。该线程执行信号量的wait()操作，说明该线程不具有执行所需的所有系统资源，如果信号量条件不满足，则进入阻塞态。

本题选C。

解答：

A正确。每个进程在运行时都被分配了独立的虚拟地址空间。

B正确。C语言中malloc()函数用于动态内存分配，返回的是一个指向分配内存的虚拟地址。

C正确。操作系统可以对进程的不同部分设置不同的权限，例如只读、可读写等。

D错误。虚拟地址空间的大小由操作系统决定。计算机系统一般按字节编址，32位操作系统的虚拟地址空间的大小为 2^32B=4GB ，64位操作系统的虚拟地址空间大小为 2^64B 。

本题选D。

解答：

按时间序列进程分析：

0ms时刻，只有P1进入就绪队列，开始运行P0。

20ms时刻，P2进入就绪队列，P1运行了20ms-0ms=20ms，其CPU执行时间为60ms，剩余CPU执行时间为60ms-20ms=40ms。就绪队列中存在P1和P2两个进程。系统采用基于优先权的抢占式进程调度算法，P2优先级值比P1优先级值大，值越大优先权越高，P2抢占执行。

30ms时刻，P3进入就绪队列，P2运行了30ms-20ms=10ms，其CPU执行时间为42ms，剩余CPU执行时间为42ms-10ms=32ms。就绪队列中存在P1、P2、P3三个进程，此时所有进程都以就绪，系统采用基于优先权的抢占式进程调度算法，值越大优先权越高，优先级值从大到小依次为P3、P2、P1，此时P3抢占执行。

30ms+13ms=43ms时刻，P3执行完毕，P2执行。

43ms+32ms=75ms时刻，P2执行完毕，P1执行。

75ms+40ms=115ms时刻，P1执行完毕，此时所有进程均已执行完毕。

进程周转时间 = 进程完成时刻-进程进入就绪队列的时刻。

P1周转时间 = P1进程完成时刻-P1进程进入就绪队列的时刻 = 115ms-0ms = 115ms；

P2周转时间 = P2进程完成时刻-P2进程进入就绪队列的时刻 = 75ms-20ms = 55ms；

P3周转时间 = P3进程完成时刻-P3进程进入就绪队列的时刻 = 43ms-30ms = 13ms；

P1、P2和P3的平均周转时间 = (P1周转时间 + P2周转时间 + P3周转时间)/3 = 61ms。

本题选B。

解答：

每个进程的虚拟地址空间是独立的，它们使用的页号是相对于各自的地址空间的。对于进程 R 和 S 共享的数据 data，可能位于不同的页面中，因此其对应的页号 p1 和 p2 不一定相等。

一段数据物理地址空间是确定的，对应的起始页框号是唯一的。对于进程 R 和 S 共享的数据 data，位于同一个页框中，因此两个页所对应的页框号分别为 f1 和 f2 一定相等。

本题选C。

解答：

索引节点是文件系统中用来记录文件的元数据的数据结构，包括索引节点编号、文件大小、访问权限、修改日期、数据的位置等。索引节点和文件一一对应，它跟文件内容一样会被持久化到磁盘，所以，索引节点同样占磁盘。

链接计数是文件系统用于统计一个文件被引用的次数，每当有一个进程打开该文件时，链接计数就会加1。当进程关闭文件时，文件系统会相应地将链接计数减1。当链接计数减到0时，表示没有任何进程打开该文件了，文件系统可以将其相关的资源进行释放。

A错误。进程P可以通过目录中文件F的目录项再次访问文件F，暂时不能删除。

B正确。由于初始时文件F仅被进程P打开并访问，索引节点中的链接计数为1。当进程P关闭文件F时，文件系统需要完成的操作是将文件内存索引节点中的链接计数减1，此时索引节点中的链接计数减1后为0，表示没有任何进程打开该文件了，文件系统可以将其相关的资源进行释放，包括文件F的索引节点所占的内存空间，文件F的所占的内存空间。

C错误。题目要求关闭文件F，没有要求删除文件F。只有执行删除文件F，文件磁盘索引节点中的链接计数减1，当磁盘索引节点引用计数为0的时候，会释放F的索引节点所占的外存空间，如果该索引节点为硬链接的索引节点，那么还需要释放文件F指向的文件实体所占的外存空间。当释放F的索引节点所占的外存空间后，该索引节点不复存在，也就无法在外存中通过该索引节点访问文件F。

D错误。题目要求关闭文件F，没有要求删除文件F，磁盘索引节点计数中的链接计数不受影响。

本题选B。

解答：

Ⅰ正确。设备分配需要考虑设备的类型。不同类型的设备有不同的特性和操作方式，因此在进行设备分配时需要根据设备的类型进行相应的处理。

Ⅱ正确。设备分配需要考虑设备的访问权限。某些设备可能需要受限制地访问，只允许特定的进程或用户进行访问，而其他进程或用户则被禁止访问。

Ⅲ正确。设备分配时需要考虑设备的占用状态。如果设备已经被其他进程或用户占用，那么在进行设备分配时就需要进行相应的冲突检测和资源管理，以确保设备的正确分配和互斥使用。

Ⅳ正确。设备分配涉及到逻辑设备与物理设备的映射关系。在计算机系统中，逻辑设备是通过操作系统层面进行管理的，而物理设备则是实际的硬件设备。设备分配需要建立逻辑设备与物理设备之间的映射关系，以便进行设备的访问和控制。

综上所述，设备分配需要考虑Ⅰ、Ⅱ、Ⅲ、Ⅳ。

本题选D。

D

C

B

C

D

A

B

D

解答：

⑴

⑵ 根据上述思路，C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;      // 图中顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

int printVertices(MGraph G) {
    int indegrees[G.numVertices];
    int outdegrees[G.numVertices];
    memset(indegrees, 0, sizeof(indegrees));
    memset(outdegrees, 0, sizeof(outdegrees));
    // 遍历无向图统计所有点的出度和入度
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            outdegrees[i] += G.Edge[i][j];
            indegrees[j] += G.Edge[i][j];
        }
    }
    int count = 0;
    // 遍历indegrees和outdegrees数组统计出度大于入度的顶点
    for (int i = 0; i < G.numVertices; i++) {
        if (outdegrees[i] > indegrees[i]) {
            printf("%c", G.VerticesList[i]);
            count++;
        }
    }
    return count;
}

int main() {
    MGraph G;
    G.numEdges = 5;
    G.numVertices = 4;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[4] = {'a', 'b', 'c', 'd'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    int count = printVertices(G);
    printf("%d", count);
    return 0;
}

复杂度分析

• 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
• 空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。

时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;      // 图中顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

int printVertices(MGraph G) {
    int count = 0, indegree = 0, outdegree = 0;
    // 遍历无向图统计所有点的出度和入度
    for (int i = 0; i < G.numVertices; i++) {
        indegree = 0;    // i的入度
        outdegree = 0;   // i的出度
        for (int j = 0; j < G.numVertices; j++) {
            outdegree += G.Edge[i][j];
            indegree += G.Edge[j][i];
        }
        if (outdegree > indegree) {
            printf("%c", G.VerticesList[i]);
            count++;
        }
    }
    return count;
}

int main() {
    MGraph G;
    G.numEdges = 5;
    G.numVertices = 4;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[4] = {'a', 'b', 'c', 'd'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    int count = printVertices(G);
    printf("%d", count);
    return 0;
}

复杂度分析

• 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
• 空间复杂度： O(1) ，使用了常数个辅助变量。

(1)可生成 3 个初始归并段(2 分)
1、37,51,63,92,94,99(2 分)
2、14,15,23,31,48,56,60,90,166(2 分)
3、 8,17,43,100(2 分)

(2)最大可能长度为 n，最小可能长度为 m。(各占 1 分)

解答：

(1) 第一问。数组a分为2个页面存储。根据C语言程序段，数组a共有24×64=1536个元素，每个数组元素类型为int，sizeof(int)=4，即一个元素占4B内存，所以数组a占1536×4B=6KB内存。页面大小为4KB，数组元素在内存空间连续存放，需要占 ⌈6KB/4KB⌉=2 个页面。

第二问。对于数组a的访问，会发生2次缺页异常。因为在M上执行上述程序段之前数组a不在主存，且数组a分为2个页面存储。所以当访问这两个页面中第一个元素时，页面尚未调入内存，会产生缺页异常，总计2次缺页异常。

第三问。两个页故障地址分别是0042 2000H和0042 3000H。虚拟地址格式为，页面大小为4KB= 2^12 B，按字节编址，页内地址占低12位，虚拟地址为32位，虚页号占高32-12=20位。数组a在虚拟地址空间中分配的起始地址为0042 2000H，第一次缺页访问虚拟页号为0042 2H，数组元素在内存空间从低地址到高地址连续存放，所以第二次缺页访问虚拟页号为0042 3H，访问该页面第一个元素所在页内地址为000H，即访问位置为0042 3000H。所以两个页故障地址分别是0042 2000H和0042 3000H。

(2) 第一问。该程序段的数据访问没有时间局部性。

第二问。时间局部性是指如果某数据被访问过，不久以后该数据可能再次被访问。显然a中每个元素仅被访问1次，不存在重复访问，所以没有时间局部性。

(3) 第一问和第二问。组相联映射格式为  ，主存块大小为32B= 2^5 B，按字节编址，块内地址占低5位，数据区大小为8KB，有8KB/32B= 2^8 行，数据Cache采用4路组相联映射，有 2^8/4=2^6 组，组号占中间6位，虚拟地址为32位，主存字块标记占高32-5-6=21位。综上，虚拟地址中低5位（A4~A0）用作块内地址，低11位中高6位（A10~A5）用作Cache组号。

a[1][0]的虚拟地址0042 2100H。因为a的起始地址为0042 2000H，一行有64个元素，一个元素占4个地址单元，所以a[1][0]的虚拟地址是0042 2000H+(64×1+0)×4H=0042 2100H。

第四问。a[1][0]所在主存块对应的Cache组号是8。因为a[1][0]的虚拟地址0042 2100H =  ，组号001 000B=8。

(4) 第一问。数组a占192个主存块。根据(1)第一问的结论，数组a占6KB内存，主存块大小为32B，由于a的起始地址为0042 2000H =  ，第一个元素的块内地址是00000B=0，也就是数组a占用每个块都是用a中元素占满了，不存在数组a占了某个块的仅一部分内存空间的情况。所以数组a恰好占6KB/32B=192个主存块。

第二问。数组a的Cache命中率为87.5%。主存块大小为32B，数组a每个元素大小为4B，一个主存块包含32B/4B=8个元素，数组a按行优先存放，C语言程序段按行访问数组元素，每个元素仅访问一次，所以每访问每个主存块中第一个元素产生Cache缺失，剩余8-1=7次Cache命中，所以数组a的Cache命中率为7/8=87.5%。

第三问。数组a的Cache命中率为87.5%。将循环中i和j的次序调换后的C语言程序段按列访问数组元素，数据Cache采用4路组相联映射，a的起始地址为0042 2000H。

数组a按行优先存放，外层循环j总共有64次迭代，外层循环j的每8次迭代元素都会被映射到8个组中，数组a共有24行，外层循环j的每一次迭代只会映射到这8个组中某24/8=3行，每组有4行，3<4，所以外层循环的每一次迭代均不会发生对本次迭代中已经调入的主存块的替换。每个元素仅访问一次，所以每访问每个主存块中第一个元素产生Cache缺失，剩余8-1=7次Cache命中，所以数组a的Cache命中率为7/8=87.5%。

解答：

(1) 第20条指令的虚拟地址是004010B9H。第19条指令的虚拟地址是004010AEH，指令内容为“C7 84 82 00 20 42 00 0A 00 00 00”（从左到右为从低字节到高字节的内容），占11字节，根据题43，计算机M按字节编址，所以第19条指令占11个地址空间，所以第20条指令的虚拟地址是004010AEH+11=004010B9H。

(2) 第一问。第2条jmp指令和第7条jge指令都采用相对寻址方式。

第二问。相对寻址过程为首先执行(PC)+1→PC，然后执行EA=(PC)+A，第2条jmp指令内容为EB 09H，占2字节。根据题43，计算机M按字节编址，所以第2题条指令占2个地址空间，

第2条jmp指令地址为00401079H，下一条指令地址为00401079H+2H=0040107BH，或者直接读第3条指令地址为0040107BH，跳转目标地址为00401084H，跳转目标地址EA=下一条指令地址（=当前指令地址+当前指令字的编址单位数）+偏移A，即00401084H = 00401079H + 2H + A，解得A=9H。第2条指令jmp的跳转目标地址00401084H=00401079H+2H+9H。

(3) 第一问。第19条指令中源操作数采用立即寻址方式。根据第19条的汇编代码mov[ecx+edx*4+00422000h], 0Ah，mov为传送指令，源操作数0Ah为立即数，所以源操作数采用立即寻址方式。

第二问。ecx存放的是i×256。a[i][j]的地址=a[0][0]的地址+4(64i+j)=a[0][0]的地址+256i+4j，对应表达式ecx+edx*4+00422000h，a[0][0]的地址为00422000h，edx中存放的是变量j，显然ecx存放的是256i，即i×256。

第三问。计算机M采用的是小端方式。第19条指令内容“  ”（从左到右为从低字节到高字节的内容）中“00 20 42 00”（从左到右为从低字节到高字节的内容）部分对应00422000h，低字节内容在低地址，高字节内容在高地址，显示是小端方式。

(4) 第一次执行第19条指令时取指令过程中不会发生缺页异常。根据43题问题(1)中第三问，虚拟地址低12位为页内地址，高20位为虚页号。第19条指令地址  和第1条指令地址  的虚页号相同，位于同一页，访问第1条指令后，虚页号004010H的页面一定位于主存中，所以第19条指令时不会发生缺页异常。

解答：

本题问题(1)考察Swap指令的应用，问题(2)考察Swap指令用硬件逻辑实现的原因。

假设线程T0和T1均要访问临界区，伪代码如下：

bool lock = FALSE;    // 共享变量
...
void T0() {
    bool key = TRUE;
    if (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = TRUE;
    ...
}
void T1() {
    bool key = TRUE;
    if (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = TRUE;
    ...
}

(1) 按照上述伪代码执行，发现线程T1和T2均能够进入临界区，无法实现互斥访问临界区。

执行“swap key, lock;”后，key为FALSE，lock为TRUE，lock为TRUE满足进入临界区前上锁条件，key为FALSE可以进入临界区，所以key为TRUE应该起到拦截效果，同时为了进入临界区，需要进行轮询。所以第一处修改如下：

①进入区中的语句“if (key == TRUE) swap key, lock;”存在错误，修改为“while (key == TRUE) swap key, lock;”。

此外，退出临界区后需要进行解锁，否则其他线程无法访问临界区。所以第二处修改如下：

②退出区中的语句“lock = TRUE;”存在错误，修改为“lock = FALSE;”。

修改后如下线程T0和T1访问临界区的伪代码如下：

bool lock = FALSE;    // 共享变量
...
void T0() {
    bool key = TRUE;
    while (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = FALSE;
    ...
}
void T1() {
    bool key = TRUE;
    while (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = FALSE;
    ...
}

实现了多线程互斥访问临界区。

(2) 第一问。否。

第二问。Swap指令为原子操作。但用函数调用语句“newSwap(&key, &lock)”代替指令“swap key, lock”后，因为多个线程可以并发执行newSwap()，newSwap()执行时传递给形参b的是共享变量lock的地址，在newSwap()中对lock既有读操作又有写操作，并发执行时不能保证实现两个变量值的原子交换，从而会导致并发执行的线程同时进入临界区。

将newSwap代替swap后，修正后的线程T0和T1访问临界区的伪代码如下：

bool lock = FALSE;    // 共享变量
...
void T0() {
    bool key = TRUE;
    while (key == TRUE) {
        bool temp = key;   ①
        key = lock;        ②
        lock = temp;       ③
    }
    临界区;
    lock = FALSE;
    ...
}
void T1() {
    bool key = TRUE;
    while (key == TRUE) {
        bool temp = key;   ④
        key = lock;        ⑤
        lock = temp;       ⑥
    }
    临界区;
    lock = FALSE;
    ...
}

例如按照①②④⑤③⑥的顺序执行，则T0和T1能够同时进入临界区，进而产生冲突。

为了保证Swap指令的原子性，可使用的方案有通过软件加互斥锁实现或者通过硬件逻辑直接实现，相比使用软件加互斥锁实现的方案，通过硬件逻辑直接实现明显更加安全和高效。所以Swap指令是由硬件逻辑直接实现的，不会被中断。

解答：

(1) 正确的操作顺序如下：

②将进程P插入阻塞队列：由于进程P执行了从键盘接收输入的系统调用（例如执行C语言的scanf()函数），需要等待用户输入完成才能继续执行。因此，进程P会被插入阻塞队列，等待键盘中断处理程序的处理。

⑥用户在键盘上输入字符：用户在键盘上输入字符，键盘控制器会将字符传递给操作系统进行处理。

④启动键盘中断处理程序：当键盘控制器有新的输入字符时，会发出中断信号通知操作系统，启动相应的键盘中断处理程序。

③将字符从键盘控制器读入系统缓冲区：键盘控制器会将用户在键盘上输入的字符读入系统缓冲区，准备供后续处理。

①将进程P插入就绪队列：当键盘中断处理程序完成了对输入字符的处理，并且准备唤醒等待输入的进程时，会将进程P从阻塞队列移动到就绪队列，准备继续执行。

⑤进程P从系统调用返回：当进程P从阻塞队列移到就绪队列后，它会被调度执行。在该过程中，进程P会在系统调用结束后从系统调用返回，继续执行后续的指令。

综上，正确的操作顺序是②、⑥、④、③、①、⑤。

第一问。操作①的前一个操作是③，后一个操作是⑤。

第二问。操作⑥的后一个操作是④。

(2) 第一问。在上述操作中，CPU一定会从进程P切换到其他进程的操作是②将进程P插入阻塞队列。当进程P被插入阻塞队列后，它无法继续执行，因此CPU会在此时切换到其他可执行的进程。

第二问。在上述操作中，CPU调度程序才能选择进程P执行的操作是①将进程P插入就绪队列。当进程P被插入就绪队列后，CPU调度程序可以从就绪队列中选择它来执行。在此之前，进程P处于阻塞状态，不可被调度执行。只有当进程P被插入就绪队列后，CPU调度程序才有机会选择它作为下一个要执行的进程。

(3) 键盘驱动程序负责与硬件键盘进行交互，并将键盘输入的字符传递给操作系统进行处理。在完成键盘输入的过程中，键盘驱动程序会读取键盘控制器的输入，将字符存储到系统缓冲区中，以便其他进程或系统调用可以访问该字符。因此完成上述操作的代码属于键盘驱动程序的操作是③将字符从键盘控制器读入系统缓冲区。

(4) 第一问。当键盘中断处理程序执行时，进程P处于阻塞状态。因为当键盘中断处理程序被触发时，进程P已经执行了系统调用并被插入阻塞队列。该进程暂停执行，等待键盘输入的中断处理程序完成并将其从阻塞队列移动到就绪队列中。只有在进程P从阻塞队列移到就绪队列后，才有机会被CPU调度执行。因此，在键盘中断处理程序执行时，进程P处于阻塞状态或等待状态。

第二问。当键盘中断处理程序被触发时，CPU处于内核态。键盘中断处理程序通常在内核态下执行，因为它需要对硬件进行直接的访问和操作，例如读取键盘控制器、处理键盘输入等。在内核态下执行可以获得更高的权限和对系统资源的直接访问能力，从而快速响应中断并处理相应的操作。