2020年12月考研的408试题，本篇为大题部分，小题见上一篇。
声明：
- 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
- 0y和0c分别表示十六进制形式补码和二进制形式补码。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
- 参与计算的英文字母变量用的是手写体。
- 对原题一些容易误会的文字做了修改。
- 图片使用亿图图示等绘制。
二、综合应用：
第41～47题，共70分。
「41」（15分）、
已知无向连通图G由顶点集P和边集E组成，|E|>0，当G中度为奇数的顶点个数为≤2的偶数时，G存在包含所有边且长度为|E|的路径，称为EL"Euler"路径。设G采用邻接矩阵存储，类型定义如下👇，请设计算法int IsExistEL(MatrixGraph G)，判断G是否存在EL路径，若存在则返回1，否则返回0。
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表 MAXV为已知常量
bool Edge[MAXV][MAXV]; // 邻接矩阵 有边为true无边为false
} MatrixGraph; // 图类型别名问答：
1️⃣给出算法的基本设计思想？说明你所设计算法的时间复杂度和空间复杂度？
𝟙、题目已经给出算法思想。图G是无向连通的，遍历其邻接矩阵的每一行，行中true的个数为对应顶点的度。记录度为奇数的顶点个数，遍历完后，若该数为0或2则返回1，否则返回0。记顶点个数为n，时间复杂度𝜪(n^2)，空间复杂度𝜪(1)
2️⃣根据设计思想，采用C/C++描述算法，关键之处给出注释？
𝟚、如下👇。
int IsExistEL(MatrixGraph G)
{
int degree, odd_cnt = 0;
for (int i = 0; i < G.numVertices; i++)
{
degree = 0;
for (int j = 0; j < G.numVertices; j++)
{
degree += G.Edge[i][j]; // 依次计算每个顶点的度
}
if (degree % 2 == 1)
odd_cnt++; // 记录度为奇数的顶点个数
}
return (odd_cnt == 0 || odd_cnt == 2) ? 1 : 0;
}「42」（8分）、
已知某排序算法如下：
void CompareCountSort(int a[], int b[], int n)
{
int* count = (int*) malloc(sizeof(int) * n);
// int* count = new int[n]; C++方法
memset(count, 0, sizeof(int) * n); // 数组清零
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (a[i] < a[j]) count[j]++;
else count[i]++;
for (int i = 0; i < n; i++)
b[count[i]] = a[i];
free(count);
// delete count; C++方法
}问答：
1️⃣若有int a[] = {25, -10, 25, 10, 11, 19}, b[6];则调用CompareCountSort(a, b, 6)后数组b[]中的内容是什么？
𝟙、b[] = {-10, 10, 11, 19, 25, 25}。
2️⃣若数组a[]中含有n个元素，则算法执行过程中，元素之间的比较次数是多少？
𝟚、(n-1)+(n-2)+...+2+1=n(n-2)/2。
3️⃣该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法？
𝟛、该算法基于计数排序的思想，count[i]记录a[]有多少个元素不大于a[i]，最后将a[i]放到b[]对应下标为count[i]的位置。该算法不稳定，修改第8行。
#8 if (a[i] <= a[j]) count[j]++;
「43」（15分）、
假定机器M字长为16位，按字节编址，连接CPU和Memory的系统总线中，地址线20位，数据线8位，采用16位定长指令字，指令格式及其说明如下，op1,op2,op3为操作码，rs,rt,rd为通用寄存器编号，R[r]表示寄存器r的内容，imm为立即数，target为转移目标的形式地址。
问答：
1️⃣ALU的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器IR多少位？主存地址寄存器MAR和主存数据寄存器MDR各多少位？
𝟙、ALU的宽度与机器字长相同，16位。可寻址主存空间大小由地址线位数决定，exp(20)×1B=1MB。指令字定长16位，IR也是16位。地址线20位，MAR也是20位，数据线8位，MDR也是8位。
2️⃣R型格式最多可定义种操作？I型和J多少型格式总共最多可定义多少种操作？通用寄存器最多有多少个？
𝟚、op1占4位，R型格式最多exp(4)=16种操作。op2,op3共享高6位，且000000已归R型使用，I型和J型共最多exp(6)-1=63种操作。rs,rt,rd都是占2位，通用寄存器最多exp(2)=4个。
3️⃣假定op1为0010和0011时，分别表示有符号整数减法和有符号整数乘法，则机器代码0x01B2的功能是什么？若1,2,3号通用寄存器当前内容分别为0yB052,0y0008,0y0020，则分别执行机器代码0x01B2,0x01B3后，3号通用寄存器内容分别是什么？各自结果是否溢出？
𝟛、0x01B2=0b000000 011011 0010，功能为R[3]←R[1]-R[2]，R[3]=0yB052-0y0008=0yB052+0yFFF8=0yB04A，未溢出。0x01B3=0b000000 011011 0011，功能为R[3]←R[1]×R[2]，R[3]=0yB052×0y0008=0yB052<<3=0y8290，舍弃了高3位，发生了溢出。
4️⃣若采用I型格式的访存指令中偏移量imm为有符号整数，则地址计算时应对imm进行零扩展还是符号扩展？
𝟜、有符号整数采用符号扩展。
5️⃣无条件转移指令可以采用上述哪种指令格式？
𝟝、J型，直接修改PC完成跳转。
「44」（8分）、
假设机器M的主存地址为24位，按字节编址。采用分页存储管理方式，虚拟地址为30位，页大小为4KB。TLB采用2路组相联方式和LRU替换策略，共8组。
问答：
1️⃣虚拟地址中哪几位表示虚页号？哪几位表示页内偏移？
𝟙、页内偏移占log(4K)=12位，高30-12=18位就是虚页号。
2️⃣已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号。M的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？
𝟚、TLB组号占log(8)=3位，高18-3=15位就是TLB标记。
3️⃣假设TLB初始时为空，访问的虚页号依次为10,12,16,7,26,4,12,20，在此过程中，哪一个虚页号对应的TLB表项被替换？
𝟛、对8取余可得映射到的TLB组号依次是2,4,0,7,2,4,4,4，TLB有2路，只有映射到4号组的虚页号>2，根据LRU算法，访问20号页面时，4号页面对应的TLB表项将被替换。
4️⃣若将M中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？
𝟜、TLB表项就是TLB标记，增加2位。
「45」（7分）、
下面给出了整型信号量S的P(signal)V(wait)操作的功能描述，以及采用开／关中断指令实现信号量操作互斥的两种方法。
功能描述方法1方法2 semaphore S;
wait(S)
{
while (S <= 0) ;
S = S - 1;
}
signal(S)
{
S = S + 1;
}semaphore S;
wait(S)
{
关中断
while (S <= 0) ;
S = S - 1;
开中断
}
signal(S)
{
关中断
S = S + 1;
开中断
}semaphore S;
wait(S)
{
关中断
while (S <= 0)
{
开中断
关中断
}
S = S - 1;
开中断
}
signal(S)
{
关中断
S = S + 1;
开中断
}
问答：
1️⃣为什么在wait()和signal()操作中对信号量S的访问必须互斥进行？
𝟙、信号量也是一种临界资源，多个进程共享的变量。
2️⃣分别说明方法1和方法2是否正确？
𝟚、方法1错误，当进程1在wait()中，关中断状态下，进程2无法用signal()增加S，S≤0时while死循环。方法2正确，while循环体里有一个开中断，进程2就可以增加S，避免死循环。
3️⃣用户程序能否使用开／关中断指令实现临界区互斥？
𝟛、不行，开／关中断指令都是特权指令，用户态无法使用。
「46」（8分）、
某系统用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序。
问答：
1️⃣系统启动过程中❶操作系统初始化程序，❷分区引导程序，❸ROM中的引导程序，❹磁盘引导程序的执行顺序是什么？
𝟙、❸❹❷❶。启动系统时，最先运行ROM中的引导程序bootstrap，然后执行磁盘引导程序指示到具体分区上的操作系统，然后执行分区引导程序，引导该分区中的操作系统初始化。
2️⃣？把硬盘制作为启动盘时，需要完成：❶操作系统的安装，❷磁盘的低级格式化，❸磁盘的逻辑格式化，❹对磁盘进行分区，正确顺序是什么？
𝟚、❷❹❸❶。低级格式化通常硬盘出厂时已完成，作用是为每个磁道划分扇区，安排扇区在磁道中的排列顺序，并标记已损坏的扇区；将磁盘存储空间划分为相互独立的多个分区，如Windows中划C:盘D:盘，这些分区可以作多种用途，如安装不同的操作系统或应用程序；然后逻辑格式化，对扇区进行逻辑编号，建立逻辑盘的引导记录，文件分配表，文件目录表，数据区等，最后完成操作系统的安装。
3️⃣磁盘扇区的划分和文件系统根目录的建立分别在2️⃣的哪个操作中完成？
𝟛、由2️⃣所述解析可知，分别在低级格式化和逻辑格式化中完成。
「47」（9分）、
某网络拓扑如下，以太网交换机S通过路由器R与Internet互连。R的部分接口，本地域名服务器，主机H1,H2的IP地址和MAC地址如图中所示。为H1配置IP地址时，也配好了域名服务器和默认网关。在𝓉0时刻，H1的ARP表和S的交换表均为空，也没有Web服务器的域名与其IP地址映射关系的记录，H1在此刻利用浏览器通过域名www.abc.com请求访问Web服务器。在𝓉1时刻，S第一次收到了封装HTTP请求报文的以太网帧，假设从𝓉0至𝓉1期间网络未发生任何与此次与Web访问无关的网络通信。
问答：
1️⃣从𝓉0至𝓉1期间，H1除了HTTP之外还运行了哪个应用层的协议？从应用层到链数层，该应用层协议报文是通过哪些协议进行逐层封装的？
𝟙、还有DNS，以将域名转换为IP地址。DNS报文⮕UDP报⮕IP数据报⮕CSMA/CD帧。以太网单播帧：有线是IEEE802.3CSMA/CD帧，无线是IEEE802.11CSMA/CA帧。
2️⃣若S的交换表结构为⟨MAC地址,S的接口⟩，则𝓉1时刻S交换表的内容是什么？
𝟚、⟨00-11-22-33-44-cc,4⟩,⟨00-11-22-33-44-bb,1⟩,⟨00-11-22-33-44-aa,2⟩。
3️⃣从𝓉0至𝓉1期间，H2至少会接收到几个与此次Web访问相关的帧？接收到的是什么帧？帧的目的MAC地址是什么？
𝟛、2次，均是封装有ARP请求报文的以太网帧，目的MAC地址都是FF-FF-FF-FF-FF-FF。第1次是查询本地域名服务器的MAC地址，第2次是查询路由器R的MAC地址。
