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

声明：

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

§二 综合应用：

第41～47题，共70分。

№41（13分）

2023年10月26日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序展开，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图𝐃𝐆采用邻接矩阵存储，类型定义如下：

typedef struct {
    int numVertices, numEdges;  // 顶点数和边数
    char VerticesList[MAXV];    // 顶点表
    int EdgeMatrix[MAXV][MAXV]; // 邻接矩阵
}* DirectedGraph;

请设计算法，对给定的非空有向图DG，判断DG是否存在唯一的拓扑序列。若是则返回true，否则返回false。

问答：

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

〖𝟙〗拓扑排序算法有基于DFS、BFS两种，20年№6说道DFS可用于求逆拓扑有序序列，这里给出更简单的基于BFS的解法，也叫Kahn算法。

①借助队列，遍历邻接矩阵获得全部顶点的入度数组，将所有入度为0的顶点加入队列𝑸，并实时检查队列𝑸的长度，若大于1则拓扑序列不唯一！
②当队列不空时，弹出队首顶点𝑢，移除𝑢的所有出边，将𝑢所连的所有顶点𝑣的入度减1，若变为0则𝑣加入队尾，重复该过程，实时检查队列𝑸的长度，直到队列为空！
③当队列变空时，若入度数组元素全变为0，则存在唯一的拓扑序列！否则说明DG中存在环，不存在拓扑序列！

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

〖𝟚〗如下👇。拓扑排序相关可以练习力加第207题。

bool isUniqueTopo(DirectedGraph DG)
{
    queue<int> que; // 辅助队列。
    int indegree[DG->numVertices] = {0};
    for (int u = 0; u < DG->numVertices; u++)
    {
        for (int v = 0; v < DG->numVertices; v++)
            // DG->EdgeMatrix[v][u]==1表示有一条<v,u>，计入度。
            indegree[u] += DG->EdgeMatrix[v][u];
        if (indegree[u] == 0)
            que.push(u); // u的入度为0，入队。
    }
    if (que.size() > 1)
        return false;

    // 广度优先搜索。
    while (!que.empty())
    {
        int u = que.front();
        que.pop(); // 弹出队首。
        for (int v = 0; v < DG->numVertices; v++)
            if (DG->EdgeMatrix[u][v] == 1)
                indegree[v]--; // 移除边<u,v>。
            if (indegree[v] == 0)
                que.push(v);
        if (que.size() > 1)
            return false;
    }
    // 辅助队列变空了。
    for (int v = 0; v < DG->numVertices; v++)
        if (indegree[v] != 0)
            return false;
    return true;
}

№42（10分）

将关键字数列20,3,11,18,9,14,7依次存储到初始值为空、长度为11的散列表𝐇𝐓中，散列函数𝑯𝒂𝒔𝒉(𝑘𝑒𝑦)＝𝑘𝑒𝑦×𝟹％𝟷𝟷，𝑯𝒂𝒔𝒉(𝑘𝑒𝑦)计算出的初始散列地址为𝑯₀，发生冲突时探查地址序列是𝑯₁,𝑯₂,𝑯₃,･･･，其中，𝑯ₖ＝(𝑯₀+𝑘²)％𝟷𝟷，𝑘＝1,2,3,･･･。

问答：

1️⃣画出所构造的𝐇𝐓，并计算𝐇𝐓的填装因子？

〖𝟙〗如下👇，填装因子＝7/11。

𝑘𝑒𝑦20311189147
𝑯₀590105910
𝑯₁6100
𝑯₂23
index012345678910
value11147209318

2️⃣给出后续在𝐇𝐓中查找关键字14的关键字比较序列？

〖𝟚〗依次为𝐇𝐓[9]=3,𝐇𝐓[10]=18,𝐇𝐓[2]=14✅。

3️⃣后续在𝐇𝐓中查找关键字8，确认查找失败时散列地址是多少？

〖𝟛〗对于关键字8，𝑯₀=2,𝑯₁=3,𝑯₂=6,𝑯₃=0,𝑯₄=7❎。

№43（13分）

假定计算机𝐌字长32位，按字节编址，采用32位定长指令字。指令add、slli、lw的格式、编码、功能说明如题43-附1所示｛和21年№43相像｝。

指令 31 25 24 20 19 15 14 12 11 7 6 0 指令功能说明 add 0000000 rs2 rs1 000 rd 0110011 R[rd] ← R[rs1] + R[rs2] slli 0000000 shamt rs1 010 rd 0010011 R[rd] ← R[rs1] << shamt lw imm rs1 010 rd 0000011 R[rd] ← M[R[rs1] + imm]
题43-附1

其中，𝑹[𝒙]表示通用寄存器𝒙的内容，𝑴[𝒙]表示地址为𝒙的主存单元内容，shamt为移位位数，imm为补码表示的偏移量。题43-附2给出了计算机𝐌的部分数据通路及控制信号｛用带箭头虚线表示｝，其中，A和B分别表示从通用寄存器rs1和rs2中读出的内容；𝑰𝑹[31:20]表示指令寄存器中的高12位；控制信号Ext为0、1时扩展器分别实现零扩展、符号扩展，ALUctr为000、001、010时ALU分别实现加、减、逻辑左移运算。

问答：

1️⃣计算机𝐌最多有几个通用寄存器？为什么shamt占5位？

〖𝟙〗看图，通用寄存器编号均占5位，最多32个。通用寄存器中的数有32位，所以shamt占5位，表示逻辑左移范围为0～31。

2️⃣执行指令add时，控制信号ALUBsrc的取值应是什么？若rs1和rs2寄存器内容分别是ℍ8765_4321和ℍ9876_5432，则指令add执行后，ALU输出端F、OF、CF的结果分别是什么？若本次add处理的是无符号整数，则应该根据哪个标志位判断是否溢出？

〖𝟚〗MUX是多路选择器，执行指令add时直接将操作数B送入ALU即可，ALUBsrc取0。ℍ8765_4321+ℍ9876_5432＝ℍ1_1EDB_9753，F＝ℍ1EDB_9753；负+负=正，有溢出，OF＝1；有进位，CF＝1；需要注意的是：OF指示有符号数加减是否发生溢出，CF指示无符号数加减是否发生进／借位。若处理的是无符号整数，不能用OF判溢出，只能用CF。

3️⃣执行指令slli时，控制信号Ext的取值可以是0也可以是1，为什么？

〖𝟛〗执行指令slli时𝑰𝑹[31]＝0，零扩展或符号扩展结果是一样的。

4️⃣执行指令lw时，控制信号Ext、ALUctr的取值分别是什么？

〖𝟜〗Ext＝1，imm为补码表示的偏移量，符号扩展才能保持imm的真值不变。ALUctr＝000，将A端的𝑹[rs1]和B端的imm相加。

5️⃣若一条指令的机器码是A040_A103，则该指令一定是lw，为什么？若执行该指令时，R[ℍ01]＝ℍFFFF_A2D0，则所读取数据的主存地址是什么？

〖𝟝〗𝑰𝑹[6:0]＝0000011，只能是lw。从指令机器码中读出imm＝𝔹1010,0000,0100＝ℍFFFF_FA04，会去主存地址ℍFFFF_A2D0+ℍFFFF_FA04＝ℍFFFF_9CD4读取数据。

№44（10分）

对于题43中的计算机𝐌，C语言程序𝐏包含的语句sum += a[i];在𝐌中对应的指令序列𝐒如题44-附1。已知变量i、sum、数组a都为int型，通用寄存器r1～r5的编号为ℍ01～ℍ05。

slli r4, r2, 2    ; R[r4] ← R[r2] << 2
add r4, r3, r4    ; R[r4] ← R[r3] + R[r4]
lw r5, 0(r4)      ; R[r5] ← M[R[r4] + 0]
add r1, r1, r5    ; R[r1] ← R[r1] + R[r5]
题44-附1
Address01234567
0013 DFF0FFFFFF7C70FEFFFF
0013 DFF80000000C3C0201FF
0013 E000F0F10000DCECFFFF
0013 E008FFFF010200000102
题44-附2

问答：

1️⃣根据指令序列𝐒中每条指令的功能，写出存放数组a首地址、变量i、变量sum的通用寄存器编号？

〖𝟙〗🛅ℍ03存数组a首地址、🛅ℍ02存变量i、🛅ℍ01存变量sum。int型数组的元素寻址表达式&a[i] = (a + i * 4)，正好跟第1、2条指令对应上R[r4] ← R[r3] + R[r2] * 4，累加sum = sum + a[i]跟第4条指令对应上R[r1] ← R[r1] + R[r5]。

2️⃣已知机器𝐌采用小端方式、页式存储管理方式，页大小为4KB。若执行到指令序列𝐒中第一条指令时i=5，且r1、r3 的内容分别为ℍ0000_1332、ℍ0013_DFF0，从地址ℍ0013_DFF0开始的存储单元内容如题44-附2所示，则执行语句sum += a[i];后，a[i]的地址、a[i]的机器数、sum的机器数分别是什么，用十六进制表示？a[i]所在页面号是多少？此次执行中，数组a至少存放在几个页面中？

〖𝟚〗\&a[i]＝ℍ0013_DFF0+5×4=ℍ0013_E004，a[i]＝｛小端表示的｝DCEC_FFFF＝ℍFFFF_ECDC，sum＝ℍ0000_1332+ℍFFFF_ECDC＝ℍ0000_100E。虚拟地址结构为［页面号20位｜页内偏移12位］，a[i]所在页面号是ℍ0013E，此次执行，数组a至少存放在ℍ0013D、ℍ0013E两个页面中。

3️⃣汇编语句slli r4, r2, 2的机器码是什么，用十六进制表示？若数组a改为short类型，则指令序列𝐒中第1条slli的汇编形式应是什么？

〖𝟛〗照着题43给的机器码写即可，0000000 00010 00010 010 00100 0010011＝ℍ0021_2213。

№45（7分）

某计算机按字节编址，采用页式虚拟存储管理方式，虚地址和实地址长度均为32位，页表项的大小为4B，页大小为4MB，虚地址结构为：［页面号10位｜页内偏移22位］，进程𝐏的页表起始虚地址为ℍB8C0_0000，被装载到从实地址ℍ6540_0000开始的连续内存空间中。

问答：

1️⃣若CPU在执行进程𝐏的过程中，访问虚拟地址ℍ1234_5678时发生了缺页异常，经过缺页异常处理和MMU地址转换后得到的实地址是ℍBAB4_5678，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚地址和实地址分别是什么？该页表项的页框号更新后的值是什么？

〖𝟙〗很绕，要分清进程𝐏的页表在内存中占用的页面和进程𝐏代码占用的页面。➊本次访问ℍ1234_5678，在𝔹00,0100,1000＝ℍ048＝72号页面；➋页表项下标72的虚地址＝ℍB8C0_0000+72×4＝ℍB8C0_0120，实地址＝ℍ6540_0120；➌页框号更新为ℍBAB4_5678的前10位𝔹10,1110,1010＝746。

2️⃣进程𝐏的页表所在页面号是多少？该页面对应的页表项的虚地址是多少？该页表项中的页框号是多少？

〖𝟚〗同第1️⃣问的做法。➊进程𝐏的页表所在页面号为ℍB8C0_0000取前10位＝ℍ2E3＝739；➋页表项下标739的虚地址＝ℍB8C0_0000+739×4＝ℍB8C0_0B8C，实地址＝ℍ6540_0B8C；➌页框号为ℍ6540_0B8C的前10位＝ℍ195＝405。

№46（8分）

计算机中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区𝐁用于存放一个数据分组，对𝐁的操作有C1、C2、C3三种。C1将一个分组写入𝐁中，C2从𝐁中读出一个分组，C3对𝐁中的分组进行修改，要求：𝐁为空时才能执行C1，𝐁非空时才能执行C2和C3。

问答：

1️⃣假设进程P1、P2均需要执行C1，实现C1代码是否为临界区，为什么？

〖𝟙〗是，需要实现两个进程对𝐁的互斥写，否则数据就乱了。

2️⃣设𝐁初始为空，进程P1执行C1一次，进程P2执行C2一次，请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值？

〖𝟚〗定义信号量group表示P1、P2之间的同步关系，P1先写P2再读，初值为0表示𝐁为空。

semaphore mutex = 1, empty = 0;
ProcessP1       ProcessP2
    C1              P(group)
    V(group)        C2

3️⃣设𝐁初始不为空，进程P1和P2各执C3一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值？

〖𝟛〗定义信号量mutex表示对𝐁的互斥访问，初值为1表示有1个𝐁。

semaphore mutex = 1;
ProcessP1       ProcessP2
    P(mutex)        P(mutex)
    C3              C3
    V(mutex)        V(mutex)

№47（9分）

网络空间是继陆海空天之后的“第五疆域”，网络技术是网络疆域建设与治理的基础。路由算法与协议是网络核心技术之一，对其准确认知，合理选择与应用，对于网络建设十分重要。假设现有互联网中的4个自治系统互连拓扑示意图如题47-附1所示。其中，AS1运行的内部网关协议为RIP；AS3规模较小，自治系统内任意两个主机间通信，经过路由器数量不超过15个；AS4规模较大，自治系统内任意两个主机间通信，经过路由器数量可能超过20个。

问答：

1️⃣若仅有RIP和OSPF内部网关协议供选择，则AS4应选择哪个协议？

〖𝟙〗RIP规定最大路由跳数为15，所以AS4只能选OSPF，且OSPF更灵活易扩展适合大型网络。

2️⃣若AS3中的某主机向本自治系统内另一主机发送1个IP分组，为确保该IP分组能够被正常接收，则该IP分组的初始TTL值应该至少设置为多少？

〖𝟚〗每经过一个路由器，TTL值就会减1，当TTL值为0时，IP分组将被丢弃。AS3中的主机设置TTL至少为15+1＝16。

3️⃣假设AS1中的路由器同一时刻启动，启动后立即构建并交换初始距离向量，之后每隔30s交换一次最新的距离向量，则从交换初始距离向量时刻算起，R11～R16路由器均获得到达网络210.2.3.0/24的正确路由，至少需要多长时间？均获得到达网络210.2.4.0/24的正确路由，至少需要多长时间？

〖𝟛〗30s，60s。交换初始距离向量后，R14、R11、R15都知道了到达网络210.2.3.0/24的正确路由，再过30s，R12、R13、R16也知道了。交换初始距离向量后，R16、R13、R15都知道了到达网络210.2.4.0/24的正确路由，再过30s，R12、R14知道，再过30s，R11知道。

4️⃣R44向R13通告到达网络136.5.16.0/20路由时，由BGP哪类会话完成？通过哪个BGP报文通告？R13通过BGP的哪类会话将该网络可达性信息通告给R14和R15？

〖𝟜〗概念题。eBGP会话。BGP-UPDATE报文。iBGP会话。

BGP"BorderGatewayProtocol"“边界网关协议”，有external、internal两种会话、OPEN、UPDATE、KEEPALIVE、NOTIFICATION四种报文。

5️⃣若R14、R15均收到分别由R11、R12、R13通告的到达网络136.5.16.0/20的可达性信息如下。则在无策略约束情况下，R14、R15更新路由表后，各自路由表中到达网络136.5.16.0/20路由的下一跳分别是什么，用路由器名称表示？

目的网络：136.5.16.0/20，AS路径：AS2-AS8-AS19，     下一跳：R11。
目的网络：136.5.16.0/20，AS路径：AS3-AS7-AS11-AS19，下一跳：R12。
目的网络：136.5.16.0/20，AS路径：AS4-AS10-AS19，    下一跳：R13。

〖𝟝〗就近原则，R14下一跳R11，再经过AS2等到达目标网络；R15下一跳R13，经过AS4等到达目标网络。

BGP路由选择策略先后顺序为：➊选择本地偏好"LocalPreference"值最高的路由｛本题未提及｝。➋选择具有AS跳数最少的路由。➌热土豆路由算法"HotPotatoRoutingAlgorithm"，选择本AS内跳数最少的路由，使得分组尽快离开本AS。➍选择BGP 标识符数值最小的路由｛本题未提及｝。

最后修改于：2025年08月16日
© 允许规范转载
如果觉得我的文章对你有用请狠狠地打赏我