2022年12月考研的408试题，本篇为大题部分，小题见上一篇。
声明：
- ℍ和𝔹分别表示十六进制数和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
- 参与计算的英文字母变量用的是手写体。
- 对原题一些容易误会的文字做了修改。
- 图片使用亿图图示等绘制。
§二 综合应用：
第41～47题，共70分。
№41（13分）
已知有向图DG采用邻接矩阵存储，类型定义如下：
typedef struct {
int numVertices, numEdges; // 顶点数和边数
char VerticesList[MAXV]; // 顶点表
int EdgeMatrix[MAXV][MAXV]; // 邻接矩阵
}* DirectedGraph;其中MAXV是已定义的常量，将图中出度大于入度的顶点称为“K顶点”。例如：在下图中，顶点a、b都是K顶点。
请设计算法，对给定的非空有向图DG，输出图中所有的K顶点，并返回K顶点的个数。
问答：
1️⃣给出算法的基本设计思想？
〖𝟙〗二重循环遍历邻接矩阵，对顶点u,v，若EdgeMatrix[u][v]
2️⃣根据设计思想，采用C/C++描述算法，关键之处给出注释？
〖𝟚〗如下👇。
int PrintKVertices(DirectedGraph DG)
{
int answer = 0;
for (int u = 0; u < DG->numVertices; u++)
{
int outDegree = 0; // 顶点u的出度总计
int inDegree = 0; // 顶点u的入度总计
for (int v = 0; v < DG->numVertices; v++)
{
outDegree += DG->EdgeMatrix[u][v]; // 边(u,v)存在则出度+1
inDegree += DG->EdgeMatrix[v][u]; // 边(v,u)存在则入度+1
}
if (outDegree > inDegree)
{
printf("%c ", DG->VerticesList[u]); // 顶点表中记录的信息
answer++;
}
}
return answer;
}№42（10分）
对含有n｛n是很大的正整数｝个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存m个记录，请回答以下问题。
问答：
1️⃣若文件中有19个记录，其关键字依次是51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100。当m=4时，可生成几个初始归并段？每个归并段各是什么？
〖𝟙〗考察置换-选择排序过程如下。
2️⃣对任意m｛n
〖𝟚〗假设n个记录开始就是升序的，第一个初始归并段的长度就可以达到最大n；而最小是m。
№43（14分）
已知机器M字长为32位，按字节编址｛1字节1个地址｝，采用请求调页策略的虚拟存储管理方式，虚拟地址32位，页大小为4KB；数据Cache采用4路组相联映射方式，数据区大小为8KB，主存块大小为32B。现有C语言程序段如下：
int a[24][64];
......
for (i = 0; i < 24; i++)
for (j = 0; j < 64; j++)
a[i][j] = 10;
已知二维数组a按行优先存储，在虚拟地址空间中分配的起始地址为ℍ0042_2000，sizeof(int)=4，假定在M上执行上述程序段之前数组a不在内存，且在该程序段执行过程中不会发生页面置换。
问答：
1️⃣数组a分布在几个页面中？对于数组a的访问，会发生几次缺页异常？页面异常的地址各是什么？
〖𝟙〗ℍ0042_2000
2️⃣不考虑变量i、j，该程序段的数据访问是否具有时间局部性？
〖𝟚〗不具有，因为数组中每个元素只访问1次。若循环体改成a[i][j] += 10;就具有时间局部性了。
3️⃣M的虚拟地址（A31～A0）中哪几位作Cache块内地址？哪几位作Cache行号？元素a1的虚拟地址是多少？其所在主存块对应的Cache行号是多少？
〖𝟛〗Cache块大小同主存块，log(32)=5，A4～A0作Cache块内地址。Cache需要有32KB÷32B=256个块，即256÷4=64行，log(64)=6，A10～A5作Cache行号。元素a1的虚拟地址是ℍ0042_2000+64×4=ℍ0042_2100，取出A10～A5可知其所在主存块对应的Cache行号是𝔹00,1000=8。
4️⃣数组a总共占多少主存块？假设上述程序段执行过程中数组a的访问不会和其他数据发生Cache访问冲突，则数组a的Cache命中率是多少？若将循环中i和j的次序按如下方式调换，则数组a的Cache命中率又是多少？
int a[24][64];
......
for (j = 0; j < 64; j++)
for (i = 0; i < 24; i++)
a[i][j] = 10;
〖𝟜〗占⌈24×64×4÷32⌉=192个主存块，对数组a调入Cache的过程如下，可知每8个元素就每生1次Cache缺失，命中率为1-1/8=87.5%。Cache的数据区足以装下数组a所有元素，循环方式调换后命中率依旧是87.5%。
№44（9分）
题43中C程序段在M上的部分机器级代码如下，每个机器级代码行中依次包含序号、虚拟地址、机器代码、汇编代码。
for (i = 0; i < 24; i++) 1 00401072 C7 45 F8 00 00 00 00 mov[ebp-8], 0 2 00401079 EB 09 jmp ℍ00401084 3 0040107B 8B 55 F8 mov eax, [ebp-8] 7 00401088 7D 32 jge ℍ004010BC for (j = 0; j < 64; j++) 8 0040108A C7 45 FC 00 00 00 00 mov[ebp-4], 0 a[i][j] = 10; 19 004010AE C7 84 82 00 20 42 00 0A 00 00 00 mov[ecx+edx*4+ℍ00422000], ℍ0A 20 ... ... ...
问答：
1️⃣第20条汇编代码的虚拟地址是多少？
〖𝟙〗ℍ0040_10AE
2️⃣已知第2条jmp和第7条jge都是跳转指令，其操作码分别是ℍEB和ℍ7D，跳转目标地址分别为ℍ0040_1084和ℍ0040_10BC，这两条指令分别采用什么寻址方式？请给出第2条指令jmp的跳转目标地址计算过程？
〖𝟚〗容易看出来是相对寻址，注意到PC的自增，第2条指令jmp的跳转目标地址ℍ0040_1084
3️⃣已知第19条指令mov的功能是a[i][j] ← 10，其中ecx和edx为寄存器名，ℍ0042_2000是数组a的首地址，指令中源操作数采用什么寻址方式？已知edx中存放的是变量j，ecx中存放的是什么？根据该指令的机器码判断M采用的是大端还是小端方式？
〖𝟛〗立即数寻址，源操作数ℍ0A就位于机器代码中。ecx中存放的是a[i][]｛i确定时｝的首地址，即i×64×4。数组a的首地址以00 20 42 00的方式存放在机器代码中，不适合人类阅读，是小端方式。
4️⃣第1次执行第19条指令时，取指令过程中是否会发生缺页异常？为什么？
〖𝟜〗不会，因为第19条在ℍ00401号页面中，该页面早已调入内存。
№45（7分）
现要求学生使用指令swap和布尔型变量lock实现临界区互斥。lock为线程间共享的变量。lock的值为TRUE时线程不能进入临界区，为FALSE时线程能够进入临界区。某同学编写的实现临界区互斥的伪代码如下（a）所示。
某同学写的伪代码newSwap()的代码 bool lock = FALSE;
...
{ // 进入区
bool key = TRUE;
if (key == TRUE)
swap key lock // 指令 硬件交换
} // 进入区
{临界区}
{ // 退出区
lock = TRUE;
} // 退出区
...void newSwap(bool* a, bool* b)
{
bool c = *a;
*a = *b;
*b = *c;
}
问答：
1️⃣（a）的伪代码中哪些语句存在错误？将其改为正确的语句，不得增加语句条数？
〖𝟙〗第5行if (key == TRUE)应改为while (key == TRUE)以确保进入区lock==FALSE时的一直等待，第10行lock = TRUE;应改为lock = FALSE;退出区解锁。
2️⃣（b）给出了交换两个变量值的函数newSwap()的代码，是否可以用函数调用语句newSwap(&key, &lock)代替指令swap key, lock以实现临界区互斥？为什么？
〖𝟚〗不行，软件方式不具备原子性，一旦执行函数newSwap时发生线程切换就无法正确实现临界区的互斥。
№46（8分）
进程P通过执行系统调用从键盘接收一个字符的输入。已知此过程中与进程P相关的操作包括：①将进程P插入就绪队列；②将进程P插入阻塞队列；③将字符从键盘控制器读人系统缓冲区；④启动键盘中断处理程序；⑤进程P从系统调用返回；⑥用户在键盘上输入字符。以上编号①～⑥仅用于标记操作，与操作的先后顺序无关。
问答：
1️⃣按照正确的操作顺序，操作①的前一个和后一个操作分别是哪一个？操作⑥的后一个操作分别是哪一个？
〖𝟙〗难点，正确的顺序应是②⑥④③①⑤。
2️⃣在上述哪个操作之后，CPU一定从进程P切换到其它进程？在上述哪个操作之后，CPU调度程序才能选中进程P执行？
〖𝟚〗操作②之后CPU一定从进程P切换给其它进程使用。操作①之后CPU调度程序才能选中进程P。
3️⃣完成上述哪个操作的代码属于键盘驱动程序？
〖𝟛〗操作③。
4️⃣键盘中断处理程序执行时，进程P处于什么状态？CPU处于内核态还是用户态？
〖𝟜〗键盘中断处理程序执行时，进程P处于阻塞态，CPU处于内核态，内核态才能处理中断。
№47（9分）
某网络拓扑如下图所示，主机H登录到FTP服务器后，向服务器上传一个大小为18000B的文件F。假设H为传输F建立数据连接时，选择的初始序号为100，MSS=1000B，拥塞控制的初始阈值是4MSS，RTT=10ms，忽略TCP的传输时延。在F的传输过程中，H均以MSS的段长向服务器发送数据，未发生差错、丢包、乱序现象。MSS"MaximumSegmentSize"“最大报文段长度”。
整个过程如下，
问答：
1️⃣FTP的控制连接是持久的还是非持久的？FTP的数据连接是持久的还是非持久的？H登录FTP服务器时，建立的TCP连接是控制连接还是数据连接？
〖𝟙〗FTP的控制连接是持久的，数据连接是非持久的。H登录FTP服务器时，建立的是控制连接，传输文件开始时才建立数据连接。
2️⃣H通过数据连接发送F时，F的第一个字节序号是多少？在断开数据连接的过程中，FTP服务器发送的第二次挥手ACK段的确认序号是多少？
〖𝟚〗101，18102。
3️⃣H通过数据连接发送F的过程中，当H收到确认序号为2101的确认时，H的拥塞窗口调整为多少？收到确认序号为7101的确认段时，H的拥塞窗口调整为多少？
〖𝟛〗3MSS，5MSS。
4️⃣H从请求建立数据连接开始，到确认F已被服务全部接收为止，至少需要多长时间？在这期间应用层数据的平均发送速率是多少？
〖𝟜〗6RTT=60ms，18000B÷60ms=2.4Mbps。
