2024 年 408 真题

1）算法基本设计思想

初始化：首先，我们需要一个数组来存储每个顶点的入度。我们遍历邻接矩阵，计算每个顶 点的入度。

初始一个计数器作为变量用于记录有多少个入度为 0 的节点。

遍历每个节点：首先计算每个顶点的入度，然后在每次迭代中找到并移除了入度为 0 的顶点。 如果在任何时刻存在多个入度为 0 的顶点，那么就返回 0，表示存在多个有效的拓扑序列。如 果成功完成了拓扑排序，那么就返回 1，表示存在唯的拓扑序列。

2）算法实现

1）散列表 HT 如下：

装填因子等于散列表中已经被填充的位置的数量除以散列表的总长度，因此本题的填装因子是 7/11。

2）查找关键字 14 的比较序列：

1. 首先，我们计算 14 的散列地址：$H(14) = (14 \times 3)\%11 = 42\%11 = 9$。
2. 我们查看散列表中索引为 9 的位置，发现哪里存储的是关键字 3，此时产生哈希冲突。
3. 由于我们使用的是二次探查，所以计算下一个散列地址：$H_1 = (H_0 + 1^1) \% 11 = (9 + 1) \% 11 = 10$。 发现那哪里存储的是关键字 18，再次遇到哈希冲突。
4. 继续计算下一个散列地址：$H_2 = (H_0 +2^2) \%11 = (9 + 4) \% 11 = 2$，找到关键字 14，

3）查找关键字 8 失败时的哈希地址

1. 计算 8 的散列地址：$H(8) = (8 \times 3) \% 11 = 24 \% 11 = 2$，索引为 2 的位置发现关键字 18，遇到冲突。
2. 使用二次探查，计算下一个散列地址：$H_1 = (H_0 + 1^1) \% 11 = (2 + 1) \% 11 = 3$。索引为 3 的位置 存储的是关键字 7，遇到冲突。
3. 我们继续使用一次探查，计算下一个散列地址：$H_2 = (H_0 + 2^2) \% 11 = (2 + 4) \% 11 = 6$，索引为 6 的位置存储的是关键字 9，遇到冲突。
4. 我们继续使用二次探查，计算下一个散列地址：$H_3 = (H_0 + 3^3) \% 11 = (2 + 9) \% 11 = 0$。索引为 0 的位置存储的是关键字 11，遇到冲突。
5. 我们继续使用二次探查，计算下一个散列地址：$H_4 = (H_0 + 4^4) \% 11 = (2 + 16) \% 11 = 7$，发现索引为 7 的位置是空的，确认查找失败，散列地址是 7。

1） 从 43 题 (a) 图可以看到，Y 寄存器 rs1 和 rs2 用 5 位表示，所以计算机 M 最多的是 2=32 个寄存器。 根据指令 R[rd] ← [rs1] << shamt 可知，shamt 表示左移。

shamt：计算机的机器字长是 32 位，所以 shamt 表示左移的最大范围不能超过 32，所以只需要 5bit 就可以表示对应的范围：$log_{2}32 = 5$。

2）ALUBsrc = O，它的作用是支持 lw 指令和 imm 的偏移（R[rd] ← M[R[rs1]+imm]）

F 的计算如下：

  8765 4321
+ 9876 5432
------------
 11FDB 9753

由于计算机的机器字长是 32 位，所以最高位的 1 舍掉，F = 1FDB 9753H:

OF 是溢出位，我们计算的结果发现确实发生了溢出和进位，所以 OF=1。

CF 是进位位，我们计算的结果发现确实发生了溢出和进位，所以 CF=1。

溢出的判断方法是，最高位进位（异或）次高位，计算过程发现最高位进位，次高位没有进 位，所以 CF 是标志判断是否溢出。

3） slli 代表左移指令，s11i 指令的高 12 位（即 IR[31:20]）的最高位为 0，因此无论进行零扩展 还是符号扩展，都是在高位补 0，效果等价，因此 Ext 可以是 0 也可以是 1。

4）R[rd] ← M[R[rs1]+imm] 这条指令的意思是，rs1 里的内容加上立即数，等于真正要访问的内存地址。

计算偏移地址，偏移地址可正可负，可以访问现在代码上边的代码，也可以访问下边的。

所以是符号扩展，Ext=1，然后表示加法，所以根据 (b) 图可知 ALUctr=O00

5）A040 A103H = 1010 0000 0100 0000 1010 0001 0000 0011B，6~0 位 = 0000011，中间的 14~12 位 = 010， 最高的 12 位为 A04H。其他两个指令 add 和 slli 的高 12 位都是 000H，所以该指令一定是 lw 指令。

6）A040 A103H = 1010 0000 0100 0000 1010 0001 0000 0011B，6~0 位 = 000 0011，中间的 14~12 位 = 010， 最高的 12 位为 A04。imm 是 31~25，也就是 A404 组（注意是符号扩展）

扩展完 1111 1111 1111 1111 1111 1010 0000 0100，十六进制是 FFFF FA04。 rs1 里的内容加上立即数，等于真正要访问的内存地址，R[O1H]=FFFF A2DOH， 所以 FFFFFA04 + FFFFA2D0 = lFFFF9CD4H。

1）slli r4,r2,2：这条指令将寄存器 r2 的值左移 2 位，2 结果存储在寄存器 r4 中。在 C 语言中， 这对应于数组索引的计算（即 i*4，因为每个 int 类型占 4 字节）。因此，我们可以推 断出寄存器 r2 存储的是变量 i 的值，即的寄存器编号位 02H。

add r4,r3,r4：这条指令将寄存器 r3 和 r4 的值相加，结果存储在寄存器 r4 中。这对应于 计算数组元素的内存地址（即&a[i]）。因此，我们可以推断出寄存器 r3 存储的是数组 a 的首地址，即 a 的寄存器编号为 03H。

add r1,rl,r5：这条指令将寄存器 r1 和 r5 的值相加，结果存储在寄存器 r1 中。这对应于 累加操作（即 sum+=a[i])。因此，我们可以推断出寄存器 r1 存储的是变量 sum 的值，即 sum 的寄存器编号为 01H。

所以，数组 a 的首地址、变量 i 和 sum 的通用寄存器编号分别为 03HH、02 和 01H。

2） 执行 sum+=a[i] 语句后，i = 6，我们直到 1 占 32 位所以一次占 4 个位置。

• i=0 时，占 FF FF FF 7C
• i=1 时，占 70 FE FF FF
• i=2 时，占 00 00 00 00
• i=3 时，占 3C 02 01 FF
• i=4 时，占 FF FF FF 7C
• i=5 时，占 F0 F1 00 00
• i=6 时，占 DC EC FF FF

所以 a[i] 的地址 = 0013 E000 + 第四个地址 = 0013 E004H

a[i]的机器数按照小端编址，所以 DC 作为最低位放在最右边，以此类推可得：a[i] 的机器数 = FFFF FCDCH

sum 的机器数 = 0000 1332H + FFFF ECDCH = 1 0000 000EH。由于只有 23 位，所以最高位舍掉后答案为 0000 000EH。

页大小为 4KB = $2^{12}$B，所以页内地址占 12 位，去掉后 12 位剩余的则是 20 位页号，a[i] 所在页页号=0013EH。

我们有 20 位页号，根据题目可知数组跨页号了 0013e 和 0013d，所以数组 a 至少存放在 2 页中。

3）slli r4,r2,2 // R[r4]←R[r2]<<2

通用寄存器 r1→r5 的编号位 01H→05H。

• 6~0：由表可得：0010011
• 11~7：rd = r2 = 00010
• 14~12：由表可知为 010
• 19~15：rd = r4 = 00100
• 24~20：shamt = 2，可以为 2420：
• 31~25：由表可知为 000 0000

机器码 = 0000 0000 0010 0001 0010 0010 0001 0011B = 0021 2313H。

若 a 改为 short 类型，slli 指令的汇编形式应该是 slli r4, r2, 1。

1）首先，我们需要确定虚拟地址 12345678H 对应页号。由于页号占 10 位， 1234 5678H = 0001 0010 0011 0100 0101 0110 0111 1000B。

计算得到：

页内偏移量（22 位）= 11 0100 0101 0110 0111 1000B = 35678H

页号（10 位）= 00 0100 1000B = 048H

然后，我们需要找到这个页号对应的页表项的虚拟地址和物理地址。由于页表项的大小为字节，我们可 以通过将页号乘以 4 得到页表项的偏移量。然后将这个偏移量加到页表的起始地址上，就可以得到页表项 的虚拟地址和物理地址。进程 P 的页表起始虚拟地址为 B8C0 0000H，物理地址 654 0000H。

计算得到：页表项虚拟地址 = 页表起始虚拟地址 + 页号4 = B8C00000H + 048H4 = B8C00120， 页表项物理地址 = 页表起始物理地址 + 页号4 = 65400000H + 048H4 = 65400120H。

最后，我们需要更新页表项中的页框号。由于经过 U 地址转换后得到的物理地址是 BAB4 5678H，我们可 以通过右移 22 位得到页框号。

计算得到：页框号 = 物理地址 BAB45678H 的前 10 位，即 10 1110 1010B = 2EAH。

2）首先，我们需要确定进程即的页表所在页的页号。由于页表起始虚拟地址位 B8C0OO00H，我们可以通过右移 22 位得到页号。

计算得到：

进程 P 的页表所在页的页号等于 B8C0 0000 的前 10 位，即 10 1110 0011B = 2E3H。 然后，我们需要找到这个页号对应的页表项的虚拟地址。由于页表项的大小为 4 字节，我们可以通过将页号 乘以 4 得到页表项的偏移量。然后将这个偏移量加到页表的起始地址上，就可以得到顷表项的虚拟地址。

计算得到：

该页对应的页表项的虚拟地址 = B8C0 0000H + 2E3H*4 = B8C0 0B8CH。

最后，我们需要确定贡表项中的页框号。由于页表被装在到从物理地址 65400000 开始的连续主存空间中，我们可以通过右移 22 位得到页框号。

计算得到：

该页表项中的页框号等于物理地址 6540 0000H 的前 10 位，即 01 1001 0101B = 195H。

1）是的，实现 C1 的代码可以被视为临界区。临界区是指在并发编程中，当多个进程同时访 问和修改共享数据时，必须进行互斥访问的代码区域。 在这个例子中，进程 P1 和 P2 都需要执行 C1,即它们都需要将一个数据分组写入缓冲区 B。 如果这两个进程同时执行 C1,那么它们可能会试图同时写入数据分组，这可能会导致数 据的不一致性。因此，我们需要确保在任何时刻，只有一个进程可以执行 C1。这就需要 将执行 C1 的代码区域定义为临界区，并使用适当的同步机制（如互斥锁或信号量）来保 证在同一时刻只有个进程可以进入临界区。 所以，实现 C1 的代码是临界区，因为它涉及到对共享资源（在这里是缓冲区 B)的修改， 而这个修改需要被同步，以防止数据的不一致性。

2）在这个问题中，我们可以使用两个信号量：一个用于保护缓使区 B（我们称之为 mutex）, 另一个用于同步进程 PI 和 P2（我们称之为 full）。mutex 用于确保在同一时刻只有一个进程可以访问缓冲区 B，而 full 用于表示缓冲区 B 是否已满。

初始时，mutex 的值为 1，表示缓冲区 B 是可用的：fu1I 的值为 0，表示缓冲区 B 是空的。

以下是进程 P1 和 P2 的代码：

// 进程 P1
P1() {
    wait(mutex);    // 请求访问缓冲区 B
    执行 C1，将一个数据分组写入 B 中
    signal(mutex);  // 释放缓冲区 B 的使用权
    signal(full);   // 表示缓冲区 B 已满
}

// 进程 P2
P2() {
    wait(full);     // 等待缓冲区 B 变满
    wait(mutex);    // 请求访问缓冲区 B
    执行 C1，从 B 中读出一个数组分组
    signal(mutex);  // 释放缓冲区 B 的使用权
}

在这个代码中，wait() 操作表示请求一个信号量，如果信号量的值大于 0，那么就将其减 1：如果信号量的值为 0，那么就阻塞，直到信号量的值大于 0。signal()操作表示释放一 个信号量，将其值加 1。

3）在这个问题中，我们可以使用一个信号量：一个用于保护缓冲区 B（我们称之为 mutex） mutex/用于确保在同一时刻只有一个进程可以访问缓冲区 B。 初始时，mutex 的值为 1，表示缓冲区 B 是可用的。 以下是进程 P1 和 P2 的代码：

// 进程 P1
P1() {
    wait(mutex);     // 请求访问缓冲区 B
    执行 C3,对 B 中的数据分组进行修改
    signal(mutex);   // 释放对缓冲区 B 的访问
}
// 进程 P2
P2() {
    wait(mutex);     // 请求访问缓冲区 B
    执行 C3,对 B 中的数据分组进行修
    signal(mutex);   // 释放对缓冲区 B 的访问
}

在这个代码中，wait() 操作表示请求一个信号量，如果信号量的值大于 0，那么就将其减 1:如果信号量的值为 0，那么就阻塞，直到信号量的值大于 0。signal() 操作表示释放一 个信号量，将其值加 1。

所以，实现 C3 的代码是临界区，因为它涉及到共享资源（在这里是缓冲区 B）的修改，而 这个修改需要被同步，以防止数据的不一致性。

1）AS4 应选择 OSPF 协议。理由：

• RIP（Routing Information Protocol） 采用 跳数（hop count） 作为度量标准，最大跳数限制为 15，超过 15 跳的网络将被视为不可达。因此，AS4 内部通信可能超过 20 个路由器的情况下，RIP 不能正常工作。
• OSPF（Open Shortest Path First） 采用 链路状态路由，支持大规模网络，并且没有严格的跳数限制，适合规模较大的自治系统（如 AS4）。

因此，AS4 应选择 OSPF 作为内部网关协议。

2）应该被设置为 16。

AS3 内部任意两个主机之间通信，最多需要经过 15 个路由器。

TTL（Time To Live） 值在每经过一个路由器时减 1，若 TTL 变为 0，分组将被丢弃。因此，为了确保 IP 分组能够到达目标主机，初始 TTL 至少应设置为 16，这样即使经过 15 个路由器，TTL 仍剩 1，可以成功到达目标主机。

3）AS1 运行的是 RIP（Routing Information Protocol），采用 距离向量路由算法，每 30 秒 交换一次最新的距离向量，并使用 逐跳扩散（Bellman-Ford 算法） 更新路由表。

假设网络 210.2.4.0/24 最初只被某个路由器（如 R1）知道，其他路由器需要逐步学习该路由信息。

每次 RIP 更新，信息只能传播 1 跳，即相邻路由器在下一次交换后获得该路由。

直到 R11~R16 均获得正确路由时，最好情况下至少需要经历 2 跳（从 R14 出发，经过 2 个周期传播至每个路由器）。

每次传播耗时 30 秒，则 2 跳需要 2 × 30 = 60 秒。

4）如果路由器属于不同的自治系统，它们之间运行 eBGP（External BGP） 进行路由通告。 如果路由器属于同一个自治系统，它们之间运行 iBGP（Internal BGP） 来传播外部学到的 BGP 路由信息。

在 BGP 中，路由更新信息使用 UPDATE（更新）报文 进行通告，包含 网络前缀（136.5.16.0/20） 及其路径属性（如 AS Path、下一跳等）。

R44 → R13：通过 eBGP 会话，使用 UPDATE 报文通告路由信息。

R13 → R14, R15：通过 iBGP 会话，使用 UPDATE 报文通告路由信息。

5）在 BGP（边界网关协议）中，默认情况下，路由选择遵循以下决策过程（无策略约束时）：

1. 最短 AS 路径优先（首要准则）：BGP 会优先选择 AS 路径最短 的路由。
2. 若 AS 路径相同，则选取最小的下一跳路由 ID（RID）或基于其他 BGP 规则。

分析 R14 和 R15 的可选路由：

R11 和 R13 的 AS 路径长度均为 3，比 R12（路径长度 4） 更短，因此 R12 的路由会被排除。

R14 离 R11 更近，R15 离 R13 更近。 所以 R14 的下一跳为 R11，R15 的下一跳为 R13。