D。通过模拟出入栈操作， 可以判断入栈序列in和出栈序列 out 是否合法。因此，已知 in 序列可以判断 out 序列是否为可能的出栈序列； 已知 out 序列也可以判断in序列是否为 可能的入栈序列，A和B错误。如果每个元素入栈后立即出栈， 则 in 序列和 out 序列相同， C错误。如果所有元素都入栈后才依次出栈， 则 in 序列和 out 序列互为倒序， D 正确。

D。 图 1 是满足条件的二叉树 T1, 图 2 是满足条件的 二叉树 T2， 结点中有值表示这个结点是编码字符。 T1 和 T2 的结点数不同， A错误。 T1的高 度等于 T2 的高度， B错误。 出现频次不同的字符在 T1 中也可能处千相同的层， C错误。 对 千定长编码集， 所有字符一定都在 T2 中处于相同的层， 而且都是叶子结点。

归并的含义是将两个或两个以上的有序表合并成一个新的有序表”， 而二路归并是将两个有序表合并为一个新的有序表。

D。【解析】直接插入排序和快速排序的特点如下表所示。

可见， I、II、III、IV 都是采用直接插入排序而不采用快速排序的可能原因。

按照题意，程序P执行的时钟周期数为10000×80%×1+10000×20%×10=28000，程序P的平均CPI为28000/10000=2.8，计算机主频为1GHz，CPU执行时间为28000/(1G/s)=28μs。

本题选A。

A. −2^32∼2^31−1

B. −2^31∼2^31−1

C. −2^32∼2^32−1

D. −2^31∼2^32−1

 位补码最高1位为符号位，剩余 n−1 位为数值位，表示范围为 −2^(n−1)∼2^(n−1)−1 。

32位补码最高1位为符号位，剩余31位为数值位，表示范围为 −2^31∼2^31−1 。

本题选B。

采用分页虚拟存储管理方式，虚拟地址格式为  。

虚拟地址空间大小为4GB= 2^32B，页大小为4KB= 2^12B，按字节编址，页内地址占低12位，虚拟地址占32位，虚页号占高32-12=20位。

虚拟地址  ，虚页号为00082H=8×16+2=130，查该进程页表得，虚页号130对应的存在位为1，实页号为018H，主存地址为24位，实页号占高24-12=12位，查表得到的实页号正好12位，高位不需要去0或者补0，拼接得到主存地址  。

本题选C。

组相联映射格式为 主存字块标记 组号 块内地址

主存块大小为64B= 2^6B，按字节编址，块内地址占低6位，数据区容量为32KB，总共有32KB/64B= 2^9 行，采用8路组相联映射方式，每8行为1组，有 2^9/8=2^6 组，组号占中间6位，主存地址为32位，主存字块标记占高32-6-6=20位。

Cache采用8路组相联映射方式，首先根据组号定位到某一分组，然后根据主存字块标记和该分组中的每一行的Tag进行比较，需要比较8行，所以比较器的个数为8，主存字块标记为20位，所以比较器位数为20位。

2018年题44图中出现了比较器，这道题中Cache采用2路组相联映射方式，有2个比较器，接受Cache行中的Tag。

本题选A。

A正确。因为该内存条包含8个8192×8192×8位的DRAM芯片，所以该内存条的容量为8×8192×8192×8bit=512MB。

B正确。存储器总线宽度为64位，而每个芯片一次只能传输8位，需要使用8体多模块交叉编址方式才能实现。

D正确。芯片内行数是8192，一行的大小是8192×8bit，行缓冲长度就是一行的大小。

本题选C。

方法一：定义法。

指令集体系结构 (Instruction Set Architecture, ISA) 是软件和硬件之间接口的一个完整定义。ISA定义了一台计算机可以执行的所有指令的集合，每条指令规定了计算机执行什么操作，所处理的操作数存放的地址空间以及操作数类型。ISA规定的内容包括数据类型及格式，指令格式，寻址方式和可访问地址空间的大小，程序可访问的寄存器个数、位数和编号，控制寄存器的定义，I/O空间的编制方式，中断结构，机器工作状态的定义和切换，输入输出结构和数据传送方式，存储保护方式等。因此，可以看出，指令集体系结构是指软件能够感知到的部分，也称软件可见部分。

I和III正确。

本题选B。

方法二：排除法

时钟周期的长度取决于计算机的硬件设计和时钟频率。时钟频率指的是时钟信号每秒钟发生的次数。时钟频率越高，每秒钟CPU执行的时钟周期数就越多，CPU的运行速度也就越快。II错误。

加法器的进位方式是指在执行加法运算时，如何处理进位（carry）的传递和处理方式。常见的加法器进位方式有无进位加法器和进位传递加法器。加法器的进位方式主要由具体的硬件设计和实现决定。IV错误。

本题选B。

地址码占6位，指令字长16位，二地址指令指令码占16-6×2=4位，最多可以表示 2^4=16 条二地址指令，二地址指令有12条，剩余16-12=4种情况，此时对于一地址指令，二地址指令的高位地址码融入二地址指令指令码作为一地址指令的指令码，最多可以表示 4×2^6=256 条一地址指令，一地址指令有254条，剩余256-254=2种情况，此时对于零地址指令，低位地址码融入一地址指令指令码作为零地址指令的指令码，最多可以表示 2×2^6=128 条零地址指令。

本题选D。

正确的过程是：

预处理（Preprocessing）：在这个阶段，预处理器根据预处理指令（如宏定义、条件编译等）对源代码进行处理。预处理器会展开宏定义、包含头文件等，生成经过预处理的源代码。

编译（Compilation）：在这个阶段，编译器将预处理后的源代码转换为汇编代码。编译器对代码进行词法分析、语法分析、语义分析，生成相应的中间代码或汇编代码。

汇编（Assembly）：在这个阶段，汇编器将汇编代码转换为机器码指令。汇编器将汇编代码中的每条指令翻译成机器码表示。

链接（Linking）：在这个阶段，链接器将各个源文件编译生成的目标文件及所需的库文件合并在一起，生成最终的可执行目标文件。链接器会解析符号引用关系，将函数和变量的引用与其定义进行匹配，并进行地址重定位等操作，使得程序能够正确地执行。

因此，预处理→编译→汇编→链接 是正确的过程。

本题选A。

A正确。中断I/O方式适用于键盘、针式打印机等字符型设备。这类设备数据传输慢，以字符为单位进行传输，中断I/O方式可以实现在输入/输出操作期间暂停CPU的执行，并在设备准备好数据后，通过触发中断来通知CPU进行数据传输。

B正确。若采用中断I/O方式，当外设准备好数据后，想CPU发出中断请求，CPU暂时中止现行程序，转去运行中断服务程序，由中断服务程序完成数据传送。

C错误。若外设准备数据时间小于中断处理时间，则可能导致数据丢失，以输入设备为例，设备为进程准备的数据会先写入设备控制器的缓冲区（缓冲区大小有限，通常只能暂存几个字节），缓冲区没写满一次，就会向CPU发出一次中断请求，CPU响应并处理中断的过程，就是将缓冲区中的数据“取走”的过程，因此若外设准备数据的时间小于中断数理时间，则可能导致外设往缓冲区写入数据的速度快于CPU从缓冲区取走数据的速度，从而导致缓冲区的数据被覆盖，进而导致数据丢失。

D正确。外设为某进程准备数据时，CPU可以运行其他进程。在中断I/O方式中，当外设准备好数据并发送中断请求时，CPU会切换到中断处理程序来处理数据传输，而不会阻塞其他进程的执行。这使得多任务操作系统可以同时执行多个进程，提高系统的并发性和效率。

本题选C。

A正确。MIMD是Multiple Instruction, Multiple Data的缩写，表示多指令流多数据流。多核处理器是一种在单个芯片上集成了多个独立的处理核心的处理器。每个核心都可以独立执行指令，访问内存，并处理不同的数据集。多核处理器具有高并行性，可同时执行多个任务。多核处理器属于MIMD结构。

B正确。SIMD是Single Instruction, Multiple Data的缩写，表示单指令流多数据流。向量处理器是一种特殊的处理器，能够以并行方式对一组数据执行相同的操作或指令。它通过在单个指令中同时处理多个数据元素来提高计算效率。向量处理器适用于涉及大规模数据并行计算的领域，如科学计算、图形处理等。向量处理器属于SIMD结构。

C错误。硬件多线程技术不仅可用于多核处理器，还可用于单核处理器。硬件多线程技术允许在一个物理处理核心上同时运行多个线程。通过在处理核心上切换执行不同的线程，可以隐藏内存访问延迟和指令等待时间，提高处理器的利用率。

D正确。SMP是shared memory multiprocessor的缩写，表示共享内存多处理器，多个处理器核心共享同一物理内存空间。这种系统架构允许多个处理器核心同时访问相同的内存地址，从而实现并发执行、数据共享和通信等功能。SMP是一种常见的多处理器系统架构，被广泛应用于高性能计算、服务器和大规模计算任务等领域。

本题选C。

A正确。多道程序系统可以同时运行多个进程，使它们在系统中并发执行。通过调度算法，系统可以在不同进程之间进行快速切换，实现并发执行。

B正确。在计算机的早期，多道程序系统中CPU一次读取多个程序放入内存，不必支持虚拟存储管理。

C正确。在多道程序系统中，多个进程可能同时访问和使用共享资源，如内存、文件系统、设备等。为了避免冲突和资源竞争，操作系统需要实现对共享资源的管理，例如使用锁机制或信号量等机制来协调进程对共享资源的访问。

D不正确。进程数越多，由于竞争CPU的资源，实际上可能降低CPU利用率。

本题选D。

A正确。中断向量表是用于处理各种硬件中断和异常的数据结构。在操作系统初始化过程中，需要创建中断向量表并初始化其中的中断向量。中断向量表将每个中断的唯一编号映射到相应的中断处理程序地址，以便在发生对应的中断或异常时，能够正确地进行处理。

B错误。文件系统的根目录是文件系统的最顶层目录，包含着文件和子目录的层次结构。根目录通常是在文件系统格式化或创建的过程中创建的，而不是在操作系统初始化过程中创建。操作系统初始化时可能会加载和初始化文件系统，但根目录本身通常是在文件系统创建过程中创建的。

C错误。硬盘分区表是记录硬盘上分区信息的数据结构，用于标识硬盘上的分区位置和大小，并记录每个分区的起始扇区和类型等信息。硬盘分区表通常是在磁盘分区或格式化过程中创建的，而不是在操作系统初始化过程中创建。

D错误。文件系统的索引节点表是记录文件元数据和索引信息的数据结构，用于记录文件的属性（如权限、大小、创建时间等）以及文件数据在存储设备上的位置，以实现对文件的管理和访问控制。索引节点表通常是在文件系统格式化或创建的过程中创建的，并在操作系统初始化时加载和初始化。

本题选A。

按时间序列进程分析：

1. 0ms时刻，只有P0进入就绪队列，开始运行P0。
2. 10ms时刻，P1、P2进入就绪队列，P0运行了10ms-0ms=10ms，其CPU执行时间为100ms，剩余CPU执行时间为100ms-10ms=90ms。就绪队列中存在P0、P1、P2三个进程。系统采用基于优先权的抢占式进程调度算法，三个进程中P2的优先级值最小，值越小优先权越高，P2抢占执行。
3. 15ms时刻，P3进入就绪队列，P2运行了15ms-10ms=5ms，其CPU执行时间为20ms，剩余CPU执行时间为20ms-5ms=15ms。就绪队列中存在P0、P1、P2、P3四个进程，此时所有进程都以就绪，系统采用基于优先权的抢占式进程调度算法，值越小优先权越高，优先级值从小到大依次为P3、P2、P0、P1，此时P3抢占执行。

综上，从0ms开始到4个进程都运行结束为止，进程执行序列为P0、P2、P3、P2、P0、P1，发生进程调度的总次数为6。

本题选C。

使用银行家算法，保证可用资源大于或等于某进行尚需资源，该进程可以输出到序列，并回收该进程已分配资源。若所有进程均可被输出到序列，则存在安全序列，该输出序列为安全序列，否则不存在安全序列。

该时刻可用资源只能满足P0的需求，将资源分配给P0，P0完成后，系统分配资源的情况如表(a)所示，此时可用资源能满足剩余所有进程，即P1和P2。

系统中存在的安全序列的个数为1×2!=2。

本题选B。

在计算机系统中，CPU有两种运行模式：用户态和内核态（也称特权态）。

用户态是指进程执行在受限的环境下，只能访问自己的地址空间和受限的资源，不能直接访问操作系统核心代码或硬件资源。在用户态下运行的进程执行的指令被称为非特权指令，因为这些指令没有对系统的底层资源进行直接的控制和访问权限。

内核态是指操作系统内核执行在特权模式下，具有对系统的完全控制和访问权限，可以执行特权指令和访问系统的底层资源。在内核态下运行的代码可以执行特权指令，控制系统的运行和访问所有资源。

CPU处于用户态时只能执行非特权指令。CPU处于内核态时即能执行非特权指令也能特权指令。

综上，C正确，A、B和D错误。

本题选C。

I正确。进程P需要读文件，说明进程P不具有执行所需的所有系统资源，进入阻塞态。

Ⅱ错误。进程P的时间片用完，说明进程P不占用CPU，进入就绪态。

Ⅲ正确。进程P申请外设，说明进程P不具有执行所需的所有系统资源，进入阻塞态。

Ⅳ正确。进程P执行信号量的wait()操作，说明进程P不具有执行所需的所有系统资源，如果信号量条件不满足，进入阻塞态。

综上，仅Ⅰ、Ⅲ、Ⅳ正确。

本题选D。

缺页异常处理过程是指在访问某个页时，发现该页不在内存中而需要从外存中调入的情况。

A正确。淘汰内存中的页并不是缺页异常处理的必要步骤。淘汰页是在内存空间不足时，为了给新的页腾出空间而选择淘汰一些旧的页。在处理缺页异常时，并不一定需要进行淘汰操作。

B错误。在处理缺页异常时，需要建立页号与页框号之间的对应关系，以便将对应的页调入内存或者进行其他操作。这是确保后续内存访问可以正确映射的步骤，是缺页异常处理过程中一定包含的操作。

C错误。当发生缺页异常时，需要将缺失的页从外存读入到内存中，以满足进程的访问需求。是缺页异常处理过程中一定包含的操作。

D错误。在页表中，通常会使用一位存在位来表示该页是否在内存中，当发生缺页异常处理完成时，需要修改页表中相应页的存在位，将其置为1，表示该页已经调入内存。

本题选A。

A错误。页面置换算法的选择会直接影响到系统的缺页率。不同的页面置换算法具有不同的策略和性能指标，会对缺页率产生影响。

B错误。工作集是指进程在其过去的t个虚拟执行时间中访问的页的集合。如果工作集较小，可以更容易将常用页面保留在内存中，从而减少缺页率。因此工作集的大小会对缺页率产生影响。

C错误。较多的进程意味着可能会有更多的内存页被占用，如果这些进行被分配的内存有限，则对内存资源的竞争会更加激烈，从而增加了发生页面置换的机会，导致更高的缺页率。

D正确。页缓冲队列是一种用于缓存磁盘上常用页数据的数据结构，通过减少对磁盘的直接访问，提高了系统的IO性能和响应速度。与缺页率无关。

本题选D。

在x86架构的处理器上，将CPU模式从用户态切换为内核态可以通过系统调用或陷阱来实现。以下是通常的步骤：

1. 用户程序通过发起系统调用或触发异常，例如访问特权指令或引发保护异常。
2. CPU接收到异常或中断信号后，会暂停用户态的执行，并保存用户态下的程序状态（如程序计数器、标志寄存器等）。
3. CPU切换到内核态，并将控制权交给内核。这通常通过将程序计数器指向内核代码的入口地址来实现。
4. 在内核态下，操作系统可以处理具体的系统调用或异常，并执行相应的内核代码。
5. 处理完系统调用或异常后，CPU可以将返回值等结果保存在合适的位置。
6. CPU通过加载用户程序保存的程序状态，将控制权切回用户态，恢复用户程序的执行。

I错误。保存断点和程序状态字由中断隐指令完成。中断隐指令并不是指令系统中的一条真正的指令，它没有操作码，所以中断隐指令是一种不允许、也不可能为用户使用的特殊指令。

Ⅱ正确。保存通用寄存器的内容由中断服务程序完成。中断服务程序是由操作系统提供和管理的。

Ⅲ正确。当用户程序发起系统调用时，CPU会切换到内核态，进入操作系统指定的系统调用服务程序中。在系统调用服务程序中，操作系统会根据系统调用号和参数来执行相应的操作，并返回结果给用户程序。

IV错误。将CPU模式从用户态改为内核态由硬件完成，硬件会执行一系列操作，包括将栈指针切换到内核栈，修改指令指针以跳转到相应的内核代码，修改特权级别等，从而实现CPU模式从用户态到内核态的切换。

综上，仅Ⅱ、Ⅲ正确。

本题选B。

驱动程序是与硬件设备交互的软件模块，它负责控制和管理设备的操作。驱动程序的设计和实现通常与设备的I/O控制方式密切相关。不同类型的设备可能采用不同的I/O控制方式，例如内存映射I/O、端口映射I/O、DMA等。驱动程序需要与设备的特定I/O控制方式进行交互，以正确地进行设备操作。

A不正确。驱动程序与I/O控制方式是相关的。

B正确。驱动程序负责设备的初始化工作，包括设置设备的寄存器、配置设备参数、启动设备等。

C正确。在驱动程序执行期间，可能需要等待设备的操作完成或等待其他资源的可用性。这可能导致执行驱动程序的进程进入阻塞态，直到条件满足。

D正确。驱动程序提供对设备的读/写操作的接口，应用程序可以通过系统调用调用驱动程序提供的读/写方法以与设备进行数据交换。

本题选A。

B。【解析】主机所在网络的网络地址可以通过主机的 IP 地址和子网掩码逐位相与得到。 子网掩码 255.255.192.0 的二进制前 18 位为 1、 后 14 位为 0, 把主机1P地址的后 14 位变为 0, 得到的结果为 183.80.64.0, 即为主机所在网络的网络地址。

D。【解析】默认网关可以理解为离当前主机最近的路由器的端口地址，所以是 192:168.1.62,而该主机的子网掩码和网关的子网掩码也相同，／27 即为 255.255.255.224。

B。【解析】SDN 对上层开发者提供的编程接口称为北向接口， 而南向接口则负责控制平面和数据平面间的通信，所以 SDN 控制器向数据平面的 SDN 交换机下发流表时使用南向接口。

D。【解析】TCP 连接的释放过程如下图所示。 题目问的是最少时间，所以当服务器 S 收到客户 C 发送的 FIN 请求 后不再发送数据，而是立马发送 FIN 请求（即第＠步和第＠步同时发生，忽略FIN-WAIT-2和CLOSE-WAIT状态）。 C收到S发来的FIN报文段后， 进入CLOSED状态还需等到兀ME-WAIT结束， 总用时至少为IRTT+ 2MSL = 50 + 800x 2 = 1650ms。 S进入CLOSED状态需要经过3次报文段的传输时间， 即l.5RTT= 75ms。

B。【解析】HTTP/1.1默认使用流水线的持久连接，所有请求都是连续发送的。 题目要求最少时间，最理想的流程是 TCP在第三次握手的报文段中捎带HTTP请求，以及TCP连接后慢开始阶段不考虑拥塞情况。 假设接收方有足够大的缓存空间， 即发送窗口等同于拥塞窗口， 总共需要经过：第1个RTT, 进行TCP连接， 此时服务器S的发送窗口 ＝lMSS, 并在第三次握手时捎带HTTP请求；第2个RTT,服务器S发送大小为lMSS的html文件， 主机C确认后服务器S的发送窗口变为2MSS;第3个RTT, 服务器S发送大小为2MSS的图像文件，主机C确认后服务器S的发送窗口变为4MSS;第4个RTT, 服务器S发送剩下的lMSS图像文件， 完成传输， 总共需要4个RTT, 即40ms。

解答：

注意本题二叉树以静态数组的方式表示，数组起始下标为0。

先画出二叉树，然后将其填充为完全二叉树，按照层序遍历顺序填写编号：

如果根结点下标为0（适用于C/C++语言数组）有 ：

left_child_id = parent_id * 2 + 1;
right_child_id = parent_id * 2 + 2;

如果根结点下标为1，这时候题目会写明条件。

为了方便解答，结构体中的Elemtype默认为int。

方法一：递归

利用二叉搜索树的性质：设 x 是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key，如果y是x右子树中的一个结点，那么y.key≥x.key。

C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 20011
#define false 0
#define true 1

typedef int bool;

typedef struct {                    // MAX_SIZE为已定义常量
    int SqBiTNode[MAX_SIZE];        // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

bool helper(SqBiTree T, int i, long long lower, long long upper) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
        return true;
    }
    if (T.SqBiTNode[i] <= lower || T.SqBiTNode[i] >= upper) {
        return false;
    }
    return helper(T, 2 * i + 1, lower, T.SqBiTNode[i]) && helper(T, 2 * i + 2, T.SqBiTNode[i], upper);
}

bool isValidBST(SqBiTree T) {
    return helper(T, 0, LONG_MIN, LONG_MAX);
}

int main() {
    int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
    SqBiTree bt1;
    memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
    bt1.ElemNum = 10;
    for (int i = 0; i < bt1.ElemNum; ++i) {
        bt1.SqBiTNode[i] = a1[i];
    }
    int ans1 = isValidBST(bt1);
    if (ans1 == true) {
        printf("T1 is a binary search tree\n");
    } else {
        printf("T1 is not a binary search tree\n");
    }
    int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
    SqBiTree bt2;
    memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
    bt2.ElemNum = 11;
    for (int i = 0; i < bt2.ElemNum; ++i) {
        bt2.SqBiTNode[i] = a2[i];
    }
    int ans2 = isValidBST(bt2);
    if (ans2 == true) {
        printf("T2 is a binary search tree\n");
    } else {
        printf("T2 is not a binary search tree\n");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。在递归调用的时候二叉树的每个结点最多被访问一次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。

方法二：中序遍历

利用二叉搜索树的性质的推论：中序遍历为单调递增序列。

递归遍历：

考虑保存整个中序遍历序列，最后进行检查。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 20011
#define false 0
#define true 1

typedef int bool;

typedef struct {                    // MAX_SIZE为已定义常量
    int SqBiTNode[MAX_SIZE];        // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

void inorder(SqBiTree T, int i, int *a, int *j) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
        return;
    }
    inorder(T, 2 * i + 1, a, j);
    a[(*j)++] = T.SqBiTNode[i];
    inorder(T, 2 * i + 2, a, j);
}

bool isValidBST(SqBiTree T){
    int *a = (int *)malloc(sizeof(int) * MAX_SIZE);
    int j = 0;
    inorder(T, 0, a, &j);
    for(int k = 0; k < j - 1; k++) {
        if(a[k] >= a[k + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
    SqBiTree bt1;
    memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
    bt1.ElemNum = 10;
    for (int i = 0; i < bt1.ElemNum; ++i) {
        bt1.SqBiTNode[i] = a1[i];
    }
    int ans1 = isValidBST(bt1);
    if (ans1 == true) {
        printf("T1 is a binary search tree\n");
    } else {
        printf("T1 is not a binary search tree\n");
    }
    int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
    SqBiTree bt2;
    memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
    bt2.ElemNum = 11;
    for (int i = 0; i < bt2.ElemNum; ++i) {
        bt2.SqBiTNode[i] = a2[i];
    }
    int ans2 = isValidBST(bt2);
    if (ans2 == true) {
        printf("T2 is a binary search tree\n");
    } else {
        printf("T2 is not a binary search tree\n");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，中序遍历数组大小为 n ，因此需要额外的 O(n) 的空间。

优化空间复杂度，使用一个变量 prev 记录前驱。由于非空二叉树T的结点值均为正数，初始化 prev=0 。

C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 20011
#define false 0
#define true 1

typedef int bool;

typedef struct {                    // MAX_SIZE为已定义常量
    int SqBiTNode[MAX_SIZE];        // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

bool inorder(SqBiTree T, int i, int* prev) {
    if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
        return true;
    }
    if (!inorder(T, 2 * i + 1, prev)) {
        return false;
    }
    if (prev > T.SqBiTNode[i]) {
        return false;
    }
    prev = T.SqBiTNode[i];
    return inorder(T, 2 * i + 2, prev);
}

bool isValidBST(SqBiTree T) {
    int prev = 0;
    return inorder(T, 0, prev);
}

int main() {
    int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
    SqBiTree bt1;
    memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
    bt1.ElemNum = 10;
    for (int i = 0; i < bt1.ElemNum; ++i) {
        bt1.SqBiTNode[i] = a1[i];
    }
    int ans1 = isValidBST(bt1);
    if (ans1 == true) {
        printf("T1 is a binary search tree\n");
    } else {
        printf("T1 is not a binary search tree\n");
    }
    int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
    SqBiTree bt2;
    memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
    bt2.ElemNum = 11;
    for (int i = 0; i < bt2.ElemNum; ++i) {
        bt2.SqBiTNode[i] = a2[i];
    }
    int ans2 = isValidBST(bt2);
    if (ans2 == true) {
        printf("T2 is a binary search tree\n");
    } else {
        printf("T2 is not a binary search tree\n");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，因此需要额外的 O(n) 的空间。

迭代遍历：

迭代遍历是对递归遍历的改进，如果中途检测到不符合二叉搜索树性质，可以直接终止，加速程序运行，但无法降低算法时间复杂度。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 20011
#define false 0
#define true 1

typedef int bool;

typedef struct {                    // MAX_SIZE为已定义常量
    int SqBiTNode[MAX_SIZE];        // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

bool isValidBST(SqBiTree T) {
    int *stk = (int *)malloc(sizeof(int) * MAX_SIZE);
    int top = 0;    // 栈顶指针
    int prev = -1;    // 初始前驱下标
    int curr = 0;    // 初始指向根结点
    while (top > 0 || (curr < T.ElemNum && T.SqBiTNode[curr] != -1)) {
        while (curr < T.ElemNum && T.SqBiTNode[curr] != -1) {
            stk[top++] = curr;
            curr = curr * 2 + 1;
        }
        curr = stk[--top];
        // 如果中序遍历得到的结点的值小于前驱，说明不是二叉搜索树
        if (T.SqBiTNode[curr] < (prev == -1 ? INT_MIN : T.SqBiTNode[prev])) {
            return false;
        }
        prev = curr;
        curr = curr * 2 + 2;
    }
    return true;
}

int main() {
    int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
    SqBiTree bt1;
    memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
    bt1.ElemNum = 10;
    for (int i = 0; i < bt1.ElemNum; ++i) {
        bt1.SqBiTNode[i] = a1[i];
    }
    int ans1 = isValidBST(bt1);
    if (ans1 == true) {
        printf("T1 is a binary search tree\n");
    } else {
        printf("T1 is not a binary search tree\n");
    }
    int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
    SqBiTree bt2;
    memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
    bt2.ElemNum = 11;
    for (int i = 0; i < bt2.ElemNum; ++i) {
        bt2.SqBiTNode[i] = a2[i];
    }
    int ans2 = isValidBST(bt2);
    if (ans2 == true) {
        printf("T2 is a binary search tree\n");
    } else {
        printf("T2 is not a binary search tree\n");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。栈最多存储 n 个结点，因此需要额外的 O(n) 的空间。

Morris遍历：

Morris遍历是对迭代遍历的进一步优化。

Morris是就是著名的计算机科学家J.H.Morris，他还与D.E.Knuth和V.R.Pratt一起提出了KMP算法。

Morris中序遍历伪代码如下：

PRINT-BINARY-TREE(T)
    x = T.root
    y = NIL  // rightmost node in x's left subtree
    while x ≠ NIL
        y = x.left
        if y ≠ NIL
            while y.right ≠ NIL and y.right ≠ x
                y = y.right
            if y.right == NIL 
                y.right = x
                x = x.left
                continue
            else y.right = NIL
        print x.key   
        x = x.right

本质是构造出类似中序遍历线索二叉树的二叉树，构造线索指向后继（下图中用虚线表示）。但注意，若能通过二叉树的孩子指针找到后继的线索（例如二叉树T1中关键字25所在结点到关键字27所在结点的线索），则该线索无需构造，如下图所示：

二叉树静态数组的Morris遍历难度比指针结点表示的二叉树大，由于没有空指针和指针变换，考虑用空结点记录中序遍历后继指针指向。为了区分指针和数字，且避开缺省值-1，下标值从-2开始储存。因为这里所有元素为正，即 x.key≥1 ，我们要存储下标，因为树不为空，所以 y.right 的下标大于等于0，要避开所有正数和缺省-1，结构体SqBiTNode数组中没有填充的部分默认为0，也要完美避开，存负的下标值-2，这样就符合小于等于-2，正好没有产生任何冲突。

由于 x 左子树的最右结点不可能右孩子，所以完全可以直接用空结点存储中序遍历后继结点下标，但是如果是需要记录会发生冲突的线索比如后序遍历的后继线索，这样做就会出现冲突，一旦出现冲突，就需要开辟 O(n) 的数组记录。用静态数组表示的二叉树的Morris遍历的空间复杂度为 O(1) 不简单是巧合。

修改指针这部分是真的复杂，目前想到的办法通过正负号来区分里面存的是下标还是元素值，保证此算法是一个原地算法。这个思路可以参考2018年第41题，其最优解为原地哈希，都是运用负号进行标记，两者原地构造存储有异曲同工之妙。

这里默认MAX_SIZE足够大，不会造成记录后继指针指向时数组越界。

C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 20011
#define false 0
#define true 1

typedef int bool;

typedef struct {                    // MAX_SIZE为已定义常量
    int SqBiTNode[MAX_SIZE];        // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

bool isValidBST(SqBiTree T) {
    int prev = -1;  // 前驱结点下标，初始化为NIL
    int x = 0;  // 初始指向根结点下标，初始化为根结点下标 x = T.root
    int y = -1;  // x 左子树的最右结点下标，初始化为NIL y = NIL
    while (x < T.ElemNum && T.SqBiTNode[x] != -1) {   // while x != NIL
        y = 2 * x + 1;  // y = x.left
        if (y < T.ElemNum && T.SqBiTNode[y] != -1) {   // if y != NIL
            while (T.SqBiTNode[2 * y + 2] != -1 && T.SqBiTNode[2 * y + 2] != 0 && -T.SqBiTNode[2 * y + 2] - 2 != x) {   // while (y.right != NIL && y.right != x)
                y = T.SqBiTNode[2 * y + 2] < -1 ? -T.SqBiTNode[2 * y + 2] - 2 : 2 * y + 2;  // y = y.right
            }
            if (T.SqBiTNode[2 * y + 2] == -1 || T.SqBiTNode[2 * y + 2] == 0) {   // if (y.right == NIL)
                T.SqBiTNode[2 * y + 2] = -(x + 2);  // y.right = x
                x = 2 * x + 1;   // x = x.left
                continue;
            } else {
                T.SqBiTNode[2 * y + 2] = -1;  // y.right = NIL
            }
        }
        if (T.SqBiTNode[x] < (prev == -1 ? -MAX_SIZE : T.SqBiTNode[prev])) {  // 比较当前结点和前驱结点的值检查是否违反二叉搜索树性质
            return false;
        }
        prev = x;   // 更新前驱结点下标
        x = T.SqBiTNode[2 * x + 2] < -1 ?  -T.SqBiTNode[2 * x + 2] - 2 : 2 * x + 2;   // x = x.right
    }
    return true;
}

int main(int argc, const char * argv[]) {
    int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
    SqBiTree bt1;
    memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
    bt1.ElemNum = 10;
    for (int i = 0; i < bt1.ElemNum; ++i) {
        bt1.SqBiTNode[i] = a1[i];
    }
    int ans1 = isValidBST(bt1);
    if (ans1 == true) {
        printf("T1 is a binary search tree\n");
    } else {
        printf("T1 is not a binary search tree\n");
    }
    int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
    SqBiTree bt2;
    memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
    bt2.ElemNum = 11;
    for (int i = 0; i < bt2.ElemNum; ++i) {
        bt2.SqBiTNode[i] = a2[i];
    }
    int ans2 = isValidBST(bt2);
    if (ans2 == true) {
        printf("T2 is a binary search tree\n");
    } else {
        printf("T2 is not a binary search tree\n");
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

解答：

K-SMALLEST-ELEMENTS(A, n, k)
    for i = 1 to k
        min_id = i
        for j = i to n
            if A[j] < A[min_id]
                min_id = j;
        exchange A[min_id] with A[i]
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，需要遍历 10 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

评分：5分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。

当然这里可以进行优化，每次记录两个变量，找出最小值和次小值，这样只需要遍历 k/2 次数组。

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。

进一步优化，直接记录 k 个变量，或者一个长度为 k 的辅助数组，使用插入排序或者冒泡排序的方法，找出最小的 k 个数，这样只需要遍历 1 次数组。

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(n) ，中间过程额外需要大小为 k 的辅助数组。

评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，都可以进行大幅优化。

以上这些优化手段都无法降低时间复杂度。

伪代码如下：

MAX-HEAPIFY(A, i, n)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ n and A[l] > A[i]
        largest = l
    else largest = i
    if r ≤ n and A[r] > A[largest]
        largest = r
    if largest ≠ i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A, n)
    for i = ⌊n / 2⌋ down to 1  // 也可用floor函数表示向下取整
        MAX-HEAPIFY(A, i, n)

K-SMALLEST-ELEMENTS(A, n, k)
    BUILD-MAX-HEAP(A, k)
    for i = k + 1 to n
        if A[i] < A[1]
            A[1] = A[i]
            MAX-HEAPIFY(A, 1, k)
    return A[1 : 10]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，由于堆大小为常量，所以建堆，维护堆的代价为 O(1) ，仅需要遍历一遍数组，该算法时间复杂度为 O(n) 。
• 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(nlog⁡k) ，所以建堆的代价为 O(k) ，每次维护堆的代价为 O(log⁡k) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlog⁡k) 。
• 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。

评分：9分，虽然当 k 为常数时时间复杂度为最优，实际上时间复杂度不是最优，可以继续进行优化。

当然，这里也可以使用优先队列，本质思想是一致的。

如果使用二叉堆作为优先队列，为插入建堆，明显不如直接用堆好。

• 时间复杂度： O(nlog⁡k) ，插入建堆的代价为 O(klog⁡k) ，每次维护堆的代价为 O(log⁡k) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlog⁡k) 。
• 空间复杂度： O(k) ，该算法用了大小为 k 的堆的辅助数组，该算法的空间复杂度为 O(k) 。

用二叉堆作为优先队列并不能对时间复杂度进行优化。

评分：8分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，可以继续进行优化。

当然可以使用更高级的数据结构实现优先队列，比如用Emde Boas树实现，时间复杂度降为 O(nlog⁡log⁡k) ，但是仍然可以继续进行优化。

方法三：选择算法（快速排序思想）

题目已经给出重要提示：“平均情况下的比较次数尽可能少”，明显指向随机化选择算法。也是本题的最优解。

为什么给出这个结论呢？“平均情况下”意思是不需要考虑最坏情况，哪些算法最坏情况下的时间复杂度和平均情况下的时间复杂度有区别呢？我们很容易想到快速排序，那么快速排序是如何进行优化的呢？其中一个最常规的方法就是随机化，当然同理，如果学过《算法导论》的同学马上能联想到选择算法。还有一个条件就是“比较次数尽可能少”，这个什么意思呢？绝大部分排序算法都是基于比较的排序算法，其中性能最好的就是快速排序，这道题没有要求我们对所有数进行排序，所以没必要使用平均情况下时间复杂度为 O(nlog⁡n) 的随机化快速排序算法，只需要使用平均情况下时间复杂度为 O(n) 的随机化选择算法算法。两者思路非常相近，都使用了随机化和划分数组技巧。

牢记：408题目中每一个条件都是有用的！

其实选择算法在2016年第43题已经进行过考察，也就是吃透真题非常重要，往年考过的知识点很有可能再考。

虽然RANDOMIZED-SELECT和RANDOMIZED-QUICKSORT代码非常相似，但这方法绝对不是能在没有学习过RANDOMIZED-SELECT算法的情况下在考场上随机应变能想出来的，如果你做到了，完全可以说是天才。408非常强调平时积累的。

递归版伪代码如下：

PARTITION(A, p, r)
    x = A[r] // the pivot
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1  // new index of pivot

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-SELECT(A, p, r, i)
    if p == r
        return A[p] // 1 ≤ i ≤ r - p + 1 when p == r means that i = 1
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q] // the pivot value is the answer
    else if i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

K-SMALLEST-ELEMENTS(A, n, k)
    RANDOMIZED-SELECT(A, 1, n, k)
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

迭代版伪代码如下：

PARTITION(A, p, r)
    x = A[r] // the pivot
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1  // new index of pivot

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-SELECT(A, n, i)
    p = 1
    r = n
    q = 0
    k = 0
    while TRUE 
        q = RANDOMIZED-PARTITION(A, p, r);
        k = q - p + 1;
        if i == k 
            return A[q]  // the pivot value is the answer
        elseif i < k
            r = q - 1
        else p = q + 1
            i = i - k

K-SMALLEST-ELEMENTS(A, n, k)
    RANDOMIZED-SELECT(A, n, k)
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
• 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 k 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 k 的元素即为最小的 k 个数，时间复杂度 O(n) 。
• 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。

可以发现，此算法时间复杂度和空间复杂度不受参数 k 影响，性能非常优秀。

评分：10分，时间复杂度和空间复杂度均为最优。

总结

本题本质就是Top-K问题，对排序算法思想进行了深入考察，Top-K问题非常经典，并不要求最终数组完全有序，只需要部分有序或者部分相对有序，所以充分利用排序算法的性质就能实现。

解答：

(1) 第一问。符号标志SF表示输出结果F的正负性，F的最高位（符号位）为 F15 ，因此 SF=F15 。

(2) 因为在单总线结构中，每个时刻总线上只有一个数据有效，而ALU有两个输入端和一个输出端。因此，当ALU运算时，首先需要用暂存器Y缓存其中一个输入端的数据，在通过总线传送另一个输入端的数据。当ALU的输出端产生运算结果，但由于该节拍总线被占用，因此需要暂存器Z，用来缓存ALU的输出端数据。

(3) 第一问。由图可知，通用寄存器rs和rd都是4bit，因此通用寄存器组GPRs在最多有 2^4=16 个通用寄存器。

第二问。rs和rd都是寄存器编号，对应寄存器用于存储指令中的操作数，指令寄存器IR中存储指令，所以rs和rd来自指令寄存器IR。

第三问。rd是寄存器编号，应该连接地址译码器。

(4) 第一问。取指周期（不考虑PC增量操作）的过程如下

(PC)→MAR和1→R不存在冲突，可以并行执行。

所以信号序列为①PCout = 1, MARin = 1, Read = 1 ②MDRout = 1, IRin = 1。其中值为0的寄存器输入/输出控制信号以及值为任意的其他控制信号均省略。

第二问。T0至少需要1个时钟周期，从发出主存读命令到主存读出数据并传送到MDR共需5个时钟周期，即T1需要5个时钟周期，T2至少需要1个时钟周期，因此取指阶段至少需要1+5+1=7个时钟周期。

(5) 第一问。图中控制信号由控制单元CU产生。

第二问。指令寄存器IR和标志寄存器FR的输出信号会连接到控制部件的输入端。

解答：

(1) 磁盘地址格式为  ，本题中只有一个磁盘驱动器，不需要考虑驱动器号。每个扇区的地址信息分为3个字段，分别为柱面号（磁道号）、盘面号（磁头号）、扇区号。每个盘面有20000个磁道，该磁盘共有20000个柱面，柱面号字段至少占 ⌈log⁡20000⌉=15 位。该磁盘有4个双面盘片，共计4×2=8个盘面，盘面号字段至少占 ⌈log⁡8⌉=3 位。每个磁道有500个扇区，扇区号至少占 ⌈log⁡500⌉=9 位。

(2) 一个扇区的平均访问时间 = 平均寻道时间 + 平均延迟时间 + 传输时间。

平均寻道时间 = 5ms。

平均延迟时间（盘片转半圈时间） =  。

传输时间（盘片转一个扇区时间） = 。

所以一个扇区的平均访问时间约为 5ms + 4.167ms + 0.017ms = 9.183ms。

(3) 第一问。磁盘控制器中的数据缓冲区每充满一次，DMA控制器就需要发出一次总线请求，磁盘控制器中的数据缓冲区大小为64位，每个扇区可记录512字节的数据，则在一个扇区读写过程中，DMA控制器向CPU发送了512B/64bit=64次总线请求。

第二问。由于采用周期挪用DMA方式，因此若CPU检测到DMA控制器的总线请求信号时也需要访问主存，则DMA请求的优先级更高，DMA控制器是可以获得总线使用权。

第三问。若无法按时完成数据传输，后来磁盘控制器中的数据缓冲区的数据可能会覆盖其先前还未传输的数据，造成数据丢失。

解答：

(1) 由题45(a)图可知，stu目录下有course和doc两个文件，查题45(b)图中的表可知，course的索引节点号为2，doc的索引节点号为10。因为目录项由文件名和索引节点号构成，所以目录文件stu中两个目录项的内容是：

(2) 查题45(b)图中的表可知，文件doc和文件course1的索引节点号都是10，说明两者共享同一个索引节点，指向同一个文件，所以两者的磁盘块号相同。文件course1占用的磁盘块的块号为30，所以文件doc占用的磁盘块的块号 x 的值为30。

(3) 需要读2个磁盘块。先读course1的索引节点所在的磁盘块，再读course1的内容所在的磁盘块。若目录文件course的内容已在内存，course1的目录项在文件course的目录中，根据course1的目录项可知其索引节点号为10，首先读取10号索引节点所在的磁盘块，索引节点中包含文件的地址项，然后读取30号磁盘块的内容。

(4) 存取course2需要使用索引节点的一级和二级间接地址项。文件course2的大小增长到6MB，磁盘块大小为4KB，文件course2需占用6MB/4KB=1536个磁盘块。每个地址项占4B，一个磁盘块可容纳4KB/4B=1024个地址项。每个索引节点包含直接地址项10个，一级、二级和三级间接地址项各1个。所以直接地址项可记录10×1=10个磁盘块，直接地址项和一级间接地址可记录10×1+1×1024=1034，直接地址项、一级间接地址和二级间接地址可记录10×1+1×1024+1× 1024^2 =1049610。文件course2中的地指项位于100号索引节点，即对应一个索引节点，占用1536个磁盘块，1034<1536≤1049610。所以存取course2需要使用到索引节点的的间接地址项包括一级和二级间接地址项。

解答：

题目已经给出了AOV网。

列出前置关系：

进行拓扑排序：

A, B, C, D, E, F

每个同步关系一个信号量。即每个AOV网中每条边（表示一个同步关系）构造一个信号量，默认初始为0。

semaphore S_AC = 0;    //控制操作A和C的执行顺序
semaphore S_BC = 0;    //控制操作B和C的执行顺序
semaphore S_CD = 0;    //控制操作C和D的执行顺序
semaphore S_CE = 0;    //控制操作C和E的执行顺序
semaphore S_EF = 0;    //控制操作E和F的执行顺序

cobegin
Process T1() {
    // process A
    完成操作A;
    signal(S_AC);    // V(S_AC);
    // process E
    wait(S_CE);    // P(S_CE);
    完成操作E;
    signal(S_EF);    // V(S_EF);
    // process F
    wait(S_EF);    // P(S_EF);
    完成操作F;
}
Process T2() {
    // process B
    完成操作B;
    signal(S_BC);    // V(S_BC);
    // process C
    wait(S_AC);    // P(S_AC);
    wait(S_BC);    // P(S_BC);
    完成操作C;
    signal(S_CD);    // V(S_CD);
    signal(S_CE);    // V(S_CE);
    // process D
    wait(S_CD);    // P(S_CD);
    完成操作D;
}
coend

上述同步关系可以进行简化，同一个线程中的同步关系可以不用设置信号量，跨线程执行的只有 C 的前置 A 和 E 的前置 C。只需要删除不跨线程的信号量即可，简化后如下：

semaphore S_AC = 0;    //控制操作A和C的执行顺序
semaphore S_CE = 0;    //控制操作C和E的执行顺序

cobegin
Process T1() {
    // process A
    完成操作A;
    signal(S_AC);    // V(S_AC);
    // process E
    wait(S_CE);    // P(S_CE);
    完成操作E;
    // process F
    完成操作F;
}
Process T2() {
    // process B
    完成操作B;
    // process C
    wait(S_AC);    // P(S_AC);
    完成操作C;
    signal(S_CE);    // V(S_CE);
    // process D
    完成操作D;
}
coend

当然，考场上时间紧迫，没有优化到最简也是没有关系的。

1)设备1选择IOOBaseT以太网交换机，设备2选择100BaseT集线器。因为物理层设备既不能隔离冲突域也不能隔离广播域， 链路层设备可以隔离冲突域但不能隔离广播域。
2)假设H2与H3之间的最远距离是D, 根据CSMNCD协议的工作原理有

最短帧长＝总线传播时延x数据传输速率x2

本题中由于使用100BaseT局域网标准， 所以 数据传输速率 为100Mbps, 总线传播时延由两部分组成， 一 部分是信号传播时延 ， 另一部分是信号通过设备 2 时产生的额外l.51µs时间延迟。代入公式为64B = (1.51µs + D/(2x10^8m/s))x100Mbps, 注意单位换算， 最终解
得D=210m。
3) M是DHCP 发现报文(DISCOVER报文）。路由器E0 接口能收到封装M的以太网帧，由于H4 发送的DHCP发现报文是广播的形式，所以同一个广播域内的所有设备和接口都可以收到该以太网帧。由千是广播帧， 所以目的MAC地址是全1, s 向DHCP服务器转发
的封装M的以太网帧的目的MAC地址是FF-FF-FF-FF-FF-FF 。
4)在H5收到的帧中 ， 地址1、地址2 和地址3分别是00-11-11-11-11-El、00-11-11-11-11-C1 和00-11-11-11-11-Dl 。 该帧来自A P， 地址l代表接收端的地址， 地址2代表 AP的地址，地址3 是发送端的地址。