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

声明：

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

二、综合应用：

第41～47题，共70分。

「41」（13分）、

定义三元组(a,b,c)，〔a,b,c均为正数〕，距离𝐷=|𝒶-𝒷|+|𝒷-𝒸|+|𝒸-𝒶|。给定3个非空整数集合S₁,S₂,S₃，都是升序的。设计一个尽可能高效的算法，从3个集合中各挑1个整数组成三元组(a,b,c)，使得距离最小。例如：S₁={-1,0,9},S₂={-25,-10,10,11},S₃={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10,9)。

问答：

1️⃣给出算法的基本设计思想？说明你所设计算法的时间复杂度和空间复杂度？

𝟙、题目中的距离事实上就是2×(max-min)，max,min分别为三元组最大最小值。用ans记录最小距离，3个下标i1,i2,i3分别用于遍历S₁,S₂,S₃，每次记最大最小值分别是a,c。定住a，让c后移增大，尝试更新ans。时间复杂度𝜪(n1+n2+n3)，空间复杂度𝜪(1)。

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

𝟚、如下。

int max(int a, int b, int c)
{
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}
int min(int a, int b, int c)
{
    return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
int MinDistOfTriple(int Arr1[], int Arr2[], int Arr3[], int n1, int n2, int n3)
{
    int ans = 0x3FFFFFFF;
    int i1 = 0, i2 = 0, i3 = 0;
    int a, c;
    while (i1 < n1 && i2 < n2 && i3 < n3)
    {
        a = max(Arr1[i1], Arr2[i2], Arr3[i3]);
        c = min(Arr1[i1], Arr2[i2], Arr3[i3]);
        if (a - c < ans)
            ans = a - c;
        if (Arr1[i1] == c)
            i1++;
        else if (Arr2[i2] == c)
            i2++;
        else
            i3++;
    }
    return 2 * ans;
}

「42」（10分）、

若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集的不等长编码，每个字符的编码均为二进制的0/1序列，最长为L位，且具有前缀特性。

问答：

1️⃣哪种数据结构适宜保存上述具有前缀特性的不等长编码？

𝟙、二叉哈夫曼树。左分支代表0，右分支代表1，叶结点中保存字符。

2️⃣基于你所设计的数据结构，简述从0/1串到字符串的译码过程？

𝟚、从左至右依次扫描0/1串中的各位。从根结点开始，根据串中当前位沿当前结点的左孩子或右孩子下移，直到到达叶结点为止。打印叶结点中保存的字符。然后从根结点开始重复这个过程，直到扫描0/1串结束，译码完成。

3️⃣简述判定某字符集的不等长编码是否具有前缀特性的过程？

𝟛、。

「43」（13分）、

有实现𝓍×𝓎的两个C语言函数如下，假定某机器M中ALU只能进行加减运算和逻辑运算。

unsigned umul(unsigned x, unsighed y) { return x * y; }
int imul(int x, int y) { return x * y; }

问答：

1️⃣若M的指令系统中没有乘法指令，但有加法·减法·移位等指令，则在M上也能实现上述两个函数中的乘法运算，为什么？

𝟙、乘法运算可以由加法和移位组合实现。

2️⃣若M的指令系统中有乘法指令，则基于ALU·移位器·寄存器以及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？

𝟚、控制循环次数，控制加法和移位操作。

3️⃣针对以下三种情况：①没有乘法指令；②有使用ALU和移位器实现的乘法指令；③有使用阵列乘法器实现的乘法指令。函数umul()在哪种情况下执行时间最长？哪种情况下执行的时间最短？

𝟛、最慢的是①，软件方式实现的，需要反复
执行多条指令，每条指令都需要取指·译码·取数·执行·保存结果；对于②，一条指令完成的，需要多个时钟周期；最快的是③，一条指令在一个时钟周期完成。

4️⃣𝓃位整数乘法指令可保存2𝓃位乘积，当仅取低n位作为乘积时，其结果可能会发生溢出。当𝓃=32,𝓍=exp(32)-l,𝓎=2时，有符号整数乘法指令和无符号整数乘法指令得到的𝓍×𝓎的2𝓃位乘积的十六进制分别是什么？此时函数umul()和imul()的返回结果是否溢出？对于无符号整数乘法运算，当仅取乘积的低𝓃位作为乘法结果时，如何用2𝓃位乘积进行溢出判断？

𝟜、有符号整数乘法指令和无符号整数乘法指令得到的64位积都是0x0000 0000 FFFF FFFE。作为函数umul()的结果不溢出，作为函数imul()的结果溢出。对于无符号整数乘法，若乘积高𝓃位全为0，不溢出。

「44」（10分）、

假定主存地址为32位，按字节编址，指令Cache·数据Cache，与主存之间均采用8路组相联映射方式，直写策略和LRU替换算法，数据区容量各为32KB。主存块大小为64B，开始时Cache均为空。

问答：

1️⃣Cache每一行中：主存标记占几位？替换算法控制位占几位？是否有修改位？

𝟙、块内偏移log(64)=6位，两Cache各有32KB÷64B=512块，512÷8=64行，Cache行号log(64)=6位。主存地址：［主存标记20位｜Cahce行号6位｜块内偏移6位］。采用8路组相联映射，每行LRU控制位占3位。采用直写策略，没有修改位。

2️⃣有如下C语言程序段，若数组s[]及变量k均为int型，int型变量占4B，变量k分配在寄存器中，数组s[]在主存中的起始地址为0x008000C0，则该程序段执行过程中，访问数组s的数据Cache缺失次数为多少？

for (k = 0; k < 1024; k++)
    s[k] = 2 * s[k];

𝟚、0x008000C0低6位全0，代表数组s[]的起始地址在一个主存块的的开始位置。对每个数组变量先读再写，1个块容纳64B÷4B=16个数组变量，总是只有对第1个变量的读缺失，共1024÷16=64个块，缺失16次。

3️⃣若CPU最先开始的访问操作是读取主存单元0x00010003中的指令，简要说明从Cache中访问该指令的过程，包括Cache缺失处理过程？

𝟛、因指令Cache初始为空，访问该指令时缺失，从Memory调入指令Cache的0号行的任意一列，主存标记填入0x00010，有效位置1，修改替换算法控制位，最后从块内地址0b000011读出该指令。

「45」（7分）、

现有5个操作A,B,C,D,E，操作C必须在A和B完成后执行，操作E必须在C和D完成后执行。

问答：

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

𝟙、画出5个操作之间的拓扑图👇，每条有向边上一个信号量，初值为0，起点处V(signal)一下，终点处P(wait)一下。

semaphore ac = 0, bc = 0, ce = 0, de = 0;
CoBegin
    OperationA()
    {
        /*doing_A_thing;*/
        V(ac);
    }
    OperationB()
    {
        /*doing_B_thing;*/
        V(bc);
    }
    OperationC()
    {
        P(ac);
        P(bc);
        /*doing_C_thing;*/
        V(ce);
    }
    OperationD()
    {
        /*doing_D_thing;*/
        V(de);
    }
    OperationE()
    {
        P(ce);
        P(de);
        /*doing_E_thing;*/
    }
CoEnd

「46」（8分）、

某32位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为4字节，虚拟地址结构为：［页目录号10位｜页面号10位｜页内偏移量12位］，某C程序中数组a[1024][1024]的起始虚拟地址为0x10800000，单个元素占4B，该程序运行时，其进程的页目录起始物理地址为0x00201000。

问答：

1️⃣数组元素a[1][2]的虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为0x00301，则所在页面对应的页表项的物理地址是什么？

𝟙、a[1][2]的虚拟地址是0x10800000+(1×1024+2)×4=0x10801008，对应页目录号66，页面号1。对应的页目录项的物理地址是0x00201000+66×4=0x00201108，所在页面对应页表项的物理地址是0x00301000+1×4=0x00301004。

2️⃣数组a[][]在虚拟地址空间中所占的区域是否必须连续？在物理地址空间中所占区域是否必须连续？

𝟚、由数组的随机存取特点，在虚拟地址空间中所占的区域必须连续；相邻虚拟页在物理内存可以不相邻，在物理地址空间中所占的区域可以不连续。

3️⃣已知数组a[][]按行优先方式存放，若对数a[][]分别按行遍历和按列遍历，则哪种遍历方式的局部性更好？

𝟛、一个页面能容纳exp(12)×1B÷4B=1024个数组元素，刚好是a[][]的一行。同一行的元素都在一个页面中，同一列的元素都在不同页面中，a[][]按行遍历局部性更好。

「47」（9分）、

某校园网有两个局域网，通过路由器R1,R2,R3互联后接入Internet，S1和S2为以太网交换机。局域网采用静态IP地址配置，路由器部分接口及各主机的IP地址如下图👇，假设NAT转换表结构如下表👇。

问答：

1️⃣为使H2和H3能够使用默认端号访问到Web服务器，需要进行什么配置？

𝟙、Web服务器在R2的内网中，H2和H3想访问Web服务器，要发IP数据报给R2，R2得配置NAT👇，Web相关的默认端口号是80。

2️⃣若H2主动访问Web务器时，将HTTP请求报文封装到IP数据报P中发送，则H2发送P的源IP地址和目的IP地址分别是什么？经过R3转发后，P的源IP地址和目的IP地址分别是什么？经过R2转发后，P的源IP址和目的IP地址分别是什么？

𝟚、如下表👇。