2024年考研408计算机统考真题在线测评（附答案）

第41题

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

typedef struct //图的类型定义
{
int numVertices, numEdges;//图的顶点数和有向边数
char VerticesList[MAXV];//顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

请设计算法

int uniquely(MGraph G)

，判定G 是否存在唯一的拓扑序列，若是，则返回1，否则返回 0。要求如下。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

参考答案

1）算法基本设计思想

建立图 G 各顶点的入度表indegree[]。选择入度为0的顶点 v，将v 的所有邻接点的入度减1，重复执行这个过程。若每次选中的入度为0的顶点有且仅有一个，且共进行了 G.numVertices 次，则意味着存在唯一的拓扑序列，返回 1，否则不存在拓扑序列，或者存在多个拓扑序列，返回0。

2）算法实现

int uniquely(MGraph g)
{
  // 表示每个顶点的入度
  int inDegrees[g.numVertices];
  for (int v = 0; v < g.numVertices; v++) {
    for (int i = 0; i < g.numVertices; i++) {
      inDegrees[v] += g.Edge[i][v];
    }
  }
 // 遍历 numVertices 轮，每一轮判断是否 有且仅有 唯一的入度为 0 的顶点
  for (int v = 0; v < g.numVertices; v++) {
    // 入度为 0 的顶点个数
    int count0 = 0;
    // 来记录这一轮入度为 0 的顶点编号
    int targetv = -1;
    for (int i = 0; i < g.numVertices; i++) {
      if (inDegrees[i] == 0) {
        targetv = i;
        count0++;
      }
    }
    // 不存在唯一的拓扑序列
    if (count0 != 1) {
      return 0;
    }
    // 进行入度修改
    for (int j = 0; j < g.numVertices; j++) {
      inDegrees[j] -= g.Edge[targetv][j];
    }
  }
  // 存在唯一的拓扑序列
  return 1;
}

第42题

将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空、长度为 11 的散列表HT 中，散列函数H(key) = (key×3)%11。H(key)计算出的初始散列地址为H0，发生冲突时探查地址序列是H1 , H2 , H3 , …，其中，Hk =(H0 + k2)%11，k = 1, 2, 3, …。

请回答下列问题。

（1）画出所构造的HT，并计算HT 的装填因子。

（2）给出在HT 中查找关键字 14 的关键字比较序列。

（3）在HT 中查找关键字 8，确认查找失败时的散列地址是多少？

参考答案

1）

填装因子是7/11。

2）H(14)=(14×3)%11=42%11=9，H₁=（H₀+1¹)%11=(9+1)%11=10。H₂=（H₀+2²)%11=(9+4)%11=2，找到关键字 14。

3）H(8)=(8×3)%11=24%11=2，H₁=（H₀+1¹)%11=(2+1)%11=3，H₂=（H₀+2²)%11=(2+4)%11=6，H₃=（H₀+3²)%11=(2+9)%11=0，H₄=（H₀+4²)%11=(2+16)%11=7。

第43题

假定计算机M 字长为 32 位，按字节编址，采用 32 位定长指令字，指令add、slli 和 lw 的格式、编码和功能说明如题 43 图（a）所示。

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

请回答下列问题。

（1）计算机M 最多有多少个通用寄存器？为什么shamt 字段占 5 位？

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

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

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

（5）若一条指令的机器码是A040A103H，则该指令一定是lw 指令，为什么？若执行该指令时，R[01H]=FFFF A2D0H，则所读取数据的存储地址是什么？

参考答案

1）log₂32=5

2）F = 1FDB 9753H:

OF=1。

CF=1。

 CF 是标志判断是否溢出。

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

4）Ext=1，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 指令。

FFFFFA04 + FFFFA2D0 = lFFFF9CD4H。

第44题

对于题 43 中的计算机M，C 语言程序P 包含的语句“sum+=a[i];”在M 中对应的指令序列S 如下。

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]

已知变量i、sum 和数组a 都为int 型，通用寄存器r1~r5 的编号为 01H～05H。请回答下列问题。

（1）根据指令序列S 中每条指令的功能，写出存放数组a 的首地址、变量i 和sum 的通用寄存器编号。

（2）已知M 为小端方式计算机，采用页式存储管理方式，页大小为 4KB。若执行到指令序列S中第 1 条指令时，i = 5且r1和r3 的内容分别为 0000 1332H 和 0013DFF0H，从地址 0013DFF0H 开始的存储单元内容如题 44 图所示，则执行“sum+=a[i];”语句后，a[i]的地址、a[i]和sum 的机器数分别是什么（用十六进制表示）？a[i]所在页的页号是多少？此次执行中，数组a至少存放在几页中？

（3）指令“slli r4, r2, 2”的机器码是什么（用十六进制表示）？若数组a 改为short 类型，则指令序列S 中slli 指令的汇编形式应是什么？

参考答案

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

2）a[i] 的机器数 = FFFF ECDCH，sum 的机器数 =  0000 000EH，a[i] 所在页页号=0013EH，数组 a 至少存放在 2 页中。

3）机器码 = 0000 0000 0010 0001 0001 0010 0001 0011B = 0021 1213H。若 a 改为 short 类型，slli 指令的汇编形式应该是 slli r4, r2, 1。

第45题

某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32位，页表项的大小为 4 字节，页大小为 4MB，虚拟地址结构如下。

进程P 的页表起始虚拟地址为B8C0 0000H，被装载到从物理地址 6540 0000H 开始的连续主存空间中。

请回答下列问题，要求答案用十六进制表示。

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

（2）进程P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？

参考答案

1）页表项虚拟地址 = 页表起始虚拟地址 + 页号 × 4 

 B8C00000H + 048H $\times$ 4 = B8C00120H

页表项物理地址 = 页表起始物理地址 + 页号× 4 

65400000H + 048H $\times$ 4 = 65400120H

页框号 

10 1110 1010B = 2EAH

2）进程 P 的页表所在页的页号

10 1110 0011B = 2E3H

该页对应的页表项的虚拟地址 

B8C00000H + 2E3H $\times$ 4 = B8C00B8CH

该页表项中的页框号

01 1001 0101B = 195H

第46题

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

（1）假设进程P1和P2 均需要执行C1，实现C1 的代码是否为临界区？为什么？

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

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

参考答案

1）是的，它涉及到对共享资源（在这里是缓冲区 B）的修改，而这个修改需要被同步，以防止数据的不一致性。

2）

// 进程 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）

// 进程 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)的修改，而这个修改需要被同步,以防止数据的不一致性。

第47题

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

请回答下列问题。

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

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

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

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

（5）若 R14 和 R15 均收到分别由 R11、R12、R13 通告的到达网络 136.5.16.0/20 的可达性信息为：

则在无策略约束情况下，R14和R15 更新路由表后，各自路由表中到达网络 136.5.16.0/20 路由的下一跳分别是什么（用路由器名称表示）？

参考答案

1）AS4 应选择 OSPF 作为内部网关协议。

2）应该被设置为 16。

3）2×30=60 秒。

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

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

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

5）R14 的下一跳为 R11，R15 的下一跳为 R13。