2021年12月考研的408试题，本篇为大题部分，小题见上一篇。

声明：

• 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
• 0y和0c分别表示十六进制形式补码和二进制形式补码。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
• 参与计算的英文字母变量用的是手写体。
• 对原题一些容易误会的文字做了修改。
• 图片使用亿图图示等绘制。

§二 综合应用：

第41～47题，共70分。

№41（13分）

已知非空二叉树BT的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {
    int SqBiTreeNode[MAX_SIZE]; // 保存二叉树结点值的数组
    int ActualElemNum;                // 实际占用的数组元素个数
}* SqBiTree;

其中MAX_SIZE是已定义的常量，BT中不存在的结点在数组SqBiTreeNode中用-1表示。例如，对于下图所示的两棵非空二叉树BT1和BT2，

的存储结果如下：

BT1.SqBiTreeNode = {40,25,60,-1,30,-1,80,-1,-1,27};    BT1.ActualElemNum = 10;
BT2.SqBiTreeNode = {40,50,60,-1,30,-1,-1,-1,-1,-1,35}; BT2.ActualElemNum = 11;

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为“左小右大型”二叉搜索树，若是，则返回true，否则，返回false。

问答：

1️⃣给出算法的基本设计思想？

〖𝟙〗采用这种存储方式的就是完全二叉树，对于下标为k的结点，其左孩下标为2k+1，右孩下标为2k+2，亲下标为⌊(k-1)/2⌋。在判断时要注意：〔当前结点的值大于左孩结点的值且小于右孩子结点的值〕只是〔该树是二叉搜索树〕的必要条件，〔该树是二叉搜索树〕 ⇔ 〔当前结点的值大于左子树最大值且小于右孩子结点最小值〕。

方法1，中序遍历，我们知道中序遍历一棵二叉搜索树会得到一个升序序列，用一个变量val记录中序过程中已遍历结点的最大值，若当前结点k的值小于等于val，可以返回false，否则，将val更新为当前结点k的值。

方法2，倒序遍历，记录以当前结点k右子树中的最小值和左子树中的最大值，保存在数组Rmin和Lmax中，若Lmax[k] < SqBiTreeNode[k] < Rmin[k]不成立，可以返回false，否则，继续往上。

2️⃣根据设计思想，采用C/C++描述算法，关键之处给出注释？

〖𝟚〗如下👇。

/* 
 方法1，参数k表示当前结点的下标，主程序调用时k=0，从根结点开始。
*/
bool isBST(SqBiTree bt, int k = 0, int val = -1)
{
    if (k >= bt->ActualElemNum || bt->SqBiTreeNode[k] == -1)
        return true; // 空结点不处理
    if (!isBST(bt, 2 * k + 1, val)) // 左子树
        return false;
    if (bt->SqBiTreeNode[k] <= val)
        return false;
    else
        val = bt->SqBiTreeNode[k];
    if (!isBST(bt, 2 * k + 2, val)) // 右子树
        return false;
    return true;
}

/* 
 方法2，这里用缺省参数统一函数接口。
*/
bool isBST(SqBiTree bt, int k = 0, int val = -1)
{
    int* Rmin = (int*)malloc(sizeof(int) * bt->ActualElemNum);
    int* Lmax = (int*)malloc(sizeof(int) * bt->ActualElemNum);
    memcpy(Rmin, bt->SqBiTreeNode, sizeof(int) * bt->ActualElemNum);
    memcpy(Lmax, bt->SqBiTreeNode, sizeof(int) * bt->ActualElemNum);
    for (int k = bt->ActualElemNum - 1; k > 0; k--)
    {
        if (bt->SqBiTreeNode[k] == -1)
            continue; // 空结点不处理
        pa = (k - 1) / 2; // 亲结点
        if (k % 2 == 0 && bt->SqBiTreeNode[pa] < Rmin[k]) // 亲结点的值小于右子树的最小
            Rmin[pa] = Rmin[k];
        else if (k % 2 == 1 && bt->SqBiTreeNode[pa] > Lmax[k]) // 亲结点的值大于左子树的最大
            Lmax[pa] = Lmax[k];
        else
            return false;
    }
    free(Rmin);
    free(Lmax);
    return true;
}

№42（10分）

现有n｛n是大于1000000的正整数｝个数保存在一维数组M中，需要查找M[]中最小的10个数。

问答：

1️⃣设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思想即可，不需要程序实现？

〖𝟙〗利用大根堆！用M[]的前10个数初始化一个能容纳10个元素的大根堆，堆顶就是10个数里最大的，顺序遍历剩余数，若当前遍历到的数比堆顶数小，则弹出堆顶数再将当前数加入堆，遍历完大根堆中的10个数即是所求。

2️⃣说明你所设计的算法平均情况下的时间复杂度和空间复杂度？

〖𝟚〗时间复杂度𝜪(n)，顺序遍历𝜪(n)，堆调整最多𝜪(log(10))。空间复杂度𝜪(1)，额外用了一个大小为10的堆。

№43（15分）

某CPU中部分数据通路如下图所示，其中，GPRs为通用寄存器组；FR为标志寄存器，用于存放ALU产生的标志信息；带箭头虚线表示控制信号，如控制信号Read、Write分别表示主存读、主存写，MDRin表示内部总线上数据写入MDR，MDRout表示MDR的内容送内部总线。

问答：

1️⃣设ALU的输入端A、B及输出端F的最高位分别为A₁₅、B₁₅、F₁₅，FR中的符号标志、溢出标志分别为SF、OF，则SF的逻辑表达式是什么？A加B、A减B时OF的逻辑表达式分别是什么？要求逻辑表达式的输入变量是且只能是A₁₅、B₁₅、F₁₅？

〖𝟙〗符号标志表示运算结果的正负性，SF=F₁₅。
对于有符号数补码加法运算，〔正加正得负〕或〔负加负得正〕，都是溢出的表现，OF=¬A₁₅∧¬B₁₅∧F₁₅∨A₁₅∧B₁₅∧¬F₁₅。有符号数补码减法运算同理，〔正减负得负〕或〔负减正得正〕，都是溢出的表现，OF=¬A₁₅∧B₁₅∧F₁₅∨A₁₅∧¬B₁₅∧¬F₁₅。

2️⃣为什么要设置暂存器Y和Z？

〖𝟚〗由于在单总线结构中，每一时刻总线上只有一个数据有效，而ALU有2个输入端，不能同时输入数据，其中1个需要借助暂存器Y，与此同时，ALU输出端产生结果时总线也不会恰好空闲，需要借助暂存器Z，以等待总线空闲。

3️⃣若GPRs的输入端rs、rd分别为所读、写的通用寄存器的编号，则GPRs中最多有多少个通用寄存器？rs和rd来自图中的哪个寄存器？已知GPRs内部有一个地址译码器和一个多路选择器，rd应连接地址译码器还是多路选择器？

〖𝟛〗GPRs中最多有exp(4)=16个通用寄存器。rs和rd来自图中的IR“指令寄存器”。rd应连接地址译码器。

4️⃣取指令阶段｛不考虑PC的自增｝的控制信号序列是什么？若从发出主存读命令到主存读出数据并传送到MDR共需5个时钟周期，则取指令阶段至少需要几个时钟周期？

〖𝟜〗取指令阶段需要完成的步骤❶从PC读出指令地址写入MAR，控制信号{PCout,MARin}；❷读主存且读到的数据写入MDR，控制信号{Read}；❸MDR的内容写入IR，控制信号{MDRout,IRin}。❶❸各1个时钟周期，❷由题意是5个时钟周期，共7个。

5️⃣图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？

〖𝟝〗控制信号由CU“控制单元”产生。IR“指令寄存器”、FR“标志寄存器”的输出信号会连到CU的输入端。

№44（8分）

假设某磁盘驱动器中有4个双面盘片，每个盘面有20000个磁道，每个磁道有500个扇区，每个扇区可记录512B的数据，盘片转速为7200RPM“转/分”，平均寻道时间为5ms。

问答：

1️⃣每个扇区包含数据及其地址信息，地址信息分为3个字段。这3个字段的名称各是什么？对于该磁盘，各字段至少占多少位？

〖𝟙〗3个字段分别是［柱面号、盘面号、扇区号］。每个盘面有20000个磁道，柱面号至少⌈log(20000)⌉=15位；共8个盘面，盘面号至少⌈log(8)⌉=3位；每个磁道有500个扇区，扇区号至少⌈log(500)⌉=8位。

2️⃣访问一个扇区的平均耗时约为多少？

〖𝟚〗平均寻道时间题干已给，平均延迟时间等于磁盘转半圈所需时间，平均传输时间等于一个扇区划过磁头下方所需时间。该磁盘转一圈的时间=60×exp10(3)÷7200=8.33ms，因此访问一个扇区的平均耗时约为5+8.33÷2+8.33÷500=9.18ms。

3️⃣若采用周期挪用DMA方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为64b，则在一个扇区读写过程中，DMA控制器向CPU发送了多少次总线请求？若CPU检测到DMA控制器的总线请求信号时也需要访问主存，则DMA控制器是否可以获得总线使用权？

〖𝟛〗磁盘控制器中的数据缓冲区每读满1次，DMA控制器就要向CPU发起1次总线请求，在一个扇区读写过程中要发起512B÷64b=64次。DMA可以优先于CPU获得总线使用权，否则缓冲区的数据就丢失了。

№45（7分）

某文件系统的磁盘块大小为4KB，目录项由文件名和索引结点号构成，每个索引结点占256B，其中包含直接地址项10个，一级、二级、三级间接地址项各1个，每个地址项占4B。该文件系统中子目录stu的结构如图3所示，stu包含子目录course和文件doc，course子目录包含文件course1和course2。各文件的文件名、索引结点号、占用磁盘块的块号如图4所示。

问答：

1️⃣目录文件stu中每个目录项的内容是什么？

〖𝟙〗如下👇。

2️⃣文件doc占用的磁盘块的块号x的值是多少？

〖𝟚〗由图4可知，文件doc、文件course1对应的索引结点号都是10，本质上是同一个文件，x=30。

3️⃣若目录文件course的内容已在内存，则打开文件course1并将其读入内存，需要读几个磁盘块？

〖𝟛〗目录文件course的内容已在内存，course1、course2对应的索引结点号就是已知的，❶读course1之索引结点所在磁盘号，以获取course1文件本体存放位置；❷读course1文件本体的内容入内存。共2个。

4️⃣若文件course2的大小增长到6MB，则为了存取course2需要使用该文件索引结点的哪几级间接地址项？

〖𝟜〗文件course2需要6MB÷4KB=1536个磁盘块，直接地址项可记10个块，一级间接地址项可记4KB÷4B=1024个块，二级间接地址项可记1024×1024个块，用到二级间接地址项就够了。

№46（8分）

某进程的两个线程T1、T2并发执行A、B、C、D、E、F共6个函数，其中T1依次执行A、E、F，T2依次执行B、C、D。图5表示上述6个操作的执行顺序所必须满足的约束：C在A和B完成后执行，D和E在C完成后执行，F在E完成后执行。

问答：

1️⃣请使用信号量的P(wait)V(signal)操作描述T1、T2之间的同步关系，并说明所用信号量的作用及其初值？

〖𝟙〗首先，AEF之间的先后顺序、BCD之间的先后顺序是T1、T2内部的事，不需要信号量控制，要控制的是AC之间、CE之间，2个信号量，初值为0，起点处V(signal)一下，终点处P(wait)一下。

semaphore ac = 0, ce = 0;
Thread1:            Thread2:
    FunctionA();        FunctionB();
    V(ac);              P(ac);
    P(ce);              FunctionC();
    FunctionE();        V(ce);
    FunctionF();        FunctionD();

№47（9分）

某网络拓扑如题图所示，R为路由器，S为以太网交换机，AP是802.11接入点，路由器的E0口和DHCP服务器的IP地址配置如图中所示；H1和H2属于同一个广播域，但不属于同一个冲突域；H2和H3属于同一个冲突域；H4和H5已经接入网络，并通过DHCP动态获取了IP地址。现有路由器、100BaseT以太网交换机"Switch"、100BaseT集线器"Hub"三类设备各若干台｛100BaseT即传输速率100Mbps｝。

问答：

1️⃣设备1、设备2应该分别选择哪类设备？

〖𝟙〗由题意H1、H2、H3所属域关系可知，设备1应选Switch，设备2应选Hub。

2️⃣若信号传播速度为2×exp10(8)m/s，以太网最小帧长为64B，信号通过设备2时会产生额外1.51us的时间延迟，则H2和H3之间可以相距的最远距离是多少？

〖𝟚〗设可以相距最远l，2×(l÷(2×exp10(8)m/s)+1.51us)≤64B÷100Mbps，得l=210m。

3️⃣在H4通过DHCP动态获取IP地址过程中，H4首先发送了DHCP报文M，M是哪种DHCP报文？路由器E0口能否收到封装M的以太网帧？S向DHCP服务器转发的封装M的以太网帧的目的MAC地址是什么？

〖𝟛〗DHCP发现"DISCOVER"报文。路由器E0能收到，由于H4发送的DHCP发现报文是广播的形式，所以同一个广播域内的全部设备都能收到。广播帧，目的MAC地址是FF-FF-FF-FF-FF-FF。

4️⃣若H4向H5发送一个IP分组P，则H5收到的封装P的802.11帧的地址1、地址2、地址3分别是什么？

〖𝟜〗802.11帧的3个地址分别是：源发送时［AP,FROM,TO］，AP转发时［TO,AP,FROM］，｛接收者、发送者、再是第三者｝。故H5收到的应是［00-11-11-11-11-E1,00-11-11-11-C1,00-11-11-11-11-D1］。