科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
支持 VLAN 划分的以太网交换机，已按端口划分了两个 VLAN。VLAN 划分结果及部分端口连接主机的 MAC 地址如图所示
下列具有不同目的 MAC 地址（DA）和源 MAC 地址（SA）的以太网帧F1~F4中，H3会接收到的是（ ）
F1：（DA）00-1A-2B-3C-4D-03；（SA）00-1A-2B-3C-4D-01
F2：（DA）00-1A-2B-3C-4D-03；（SA）00-1A-2B-3C-4D-05
F3：（DA）FF-FF-FF-FF-FF-FF；（SA）00-1A-2B-3C-4D-02
F4：（DA）00-1A-2B-3C-4D-03；（SA）00-1A-2B-3C-4D-06
A. 仅F1、F2 B. 仅F1、F3
C. 仅F2、F4 D. 仅F3、F4
某网络在 t0 刻的网络拓扑和 R1 的路由表如下图所示。R1~R4 是路由器，基于链路状态路由算法计算路由。S0~S4 是路由器 R1 的接口，链路上的数值为链路费用，若 t1（t1>t0）时刻，R1 检测到 R1 到 R2 的链路断开，则 R1 再重新计算路由并进行充分路由聚合后的表中路由项的数量（ ）
$$ \begin{array}{|c|c|} \hline \textbf{R1路由表} & \textbf{} \\ \hline \textbf{目的网络} & \textbf{接口} \\ \hline 199.10.20.0/27 & \text{S1} \\ \hline 199.10.20.32/27 & \text{S2} \\ \hline —— & —— \\ \hline 199.10.20.128/25 & \text{S3} \\ \hline 199.10.21.125/32 & \text{S4} \\ \hline 0.0.0.0/0 & \text{S0} \\ \hline \end{array} $$
A. 3 B. 4 C. 5 D. 6
由于二叉搜索树的中序遍历序列为递增序列，本算法采用中序递归遍历二叉树，并记录当前找到的最小绝对值差值 min。
遍历过程中，每访问一个结点时计算目标值与当前结点值之差的绝对值：
- 若该值小于
min，则更新min； - 若该值大于或等于
min，说明后续结点的差值会更大，此时可停止查找（可通过标志变量flag控制递归终止）。
// 当前的绝对值差值最小值
int min = INT_MAX;
// 最小绝对值差值是否已经找到
int flag = 0;
// 存储待输出的结点关键字
int min_data[2];
int min_idx = 0;
void searchMinDiff(BTNode *root, int K) {
if (!root) return;
if (flag) return;
searchMinDiff(root->left, K);
// 中序遍历
int diff = abs(K - root->data);
if (diff < min) {
min = diff;
min_data[0] = root->data;
min_idx = 1;
} else if (diff == min) {
min_data[min_idx++] = root->data;
} else {
flag = 1;
}
searchMinDiff(root->right, K);
}
void solve(BTNode *root, int K) {
searchMinDiff(root, K);
printf("min diff: %d\n", min);
for (int i = 0; i < min_idx; i++) {
printf("min element: %d\n", min_data[i]);
}
}
评分及理由
（1）得分及理由（满分4分）
得分：4分
理由：你的算法基本思想描述清晰、正确。你准确地指出了利用二叉搜索树中序遍历的递增性质，通过比较差值与当前最小值`min`来判断是否继续查找，并提到了使用`flag`标志位控制递归终止。这与标准答案的核心思想完全一致，因此获得满分。
（2）得分及理由（满分8分）
得分：6分
理由：你的代码实现整体逻辑正确，但存在一处稍显不足的地方，导致无法完美处理题目要求输出的所有情况。
- 优点：
- 函数结构清晰，使用了`searchMinDiff`和`solve`两个函数，逻辑分离。
- 中序遍历框架、`flag`标志位控制递归终止、通过比较`diff`与`min`来更新最小值或终止递归的实现均正确。
- 扣分点（逻辑错误）：扣2分
- 问题描述：你的代码在输出时，只记录了`min_data`数组中的关键值，但在最终输出时，没有同时输出最小绝对值之差本身（虽然在`solve`函数中你已经打印了`min diff`，但这属于额外操作）。更关键的是，题目要求“输出该绝对值与结点中的关键字”。标准答案在发现`my_abs >= min`时立即进行输出，能确保所有符合条件的节点（即最后一批与最小值相等和略大于最小值的节点）都被输出。而你的代码是在遍历结束后，通过`min_data`数组来输出。这本身没有问题，但当最小值对应的节点有多个时，你的逻辑是可行的（代码中`else if (diff == min)`分支处理了这种情况）。然而，你的逻辑在处理完最后一个与`min`相等的节点后，由于下一个节点的`diff`必定大于等于`min`，你的`else`分支会设置`flag=1`并直接返回，此时`min_data`数组已经记录了所有与`min`相等的节点，所以这部分输出是没问题的。
- 真正的扣分原因：但是，标准答案考虑到了一个边界情况：当整个树中只有一个节点，或者遍历到最后一个节点时，其`diff`等于当前`min`。在这种情况下，标准答案在递归返回前会设置`flag=1`，而你的代码逻辑中，`diff==min`时不会触发`flag=1`。这会导致虽然你能正确记录数据，但在遍历结束后，`flag`没有被正确设置，虽然这在你的`solve`函数中不影响最终的循环输出，但逻辑上不够严谨。更重要的是，你的代码缺少一个至关重要的步骤：当遍历结束（递归自然返回）且`flag`从未被设置为1时，你仍然需要输出结果，但这在你的`searchMinDiff`函数内部并没有处理。你依赖的是在`solve`函数中打印。这种做法与题目要求的“在查找过程中输出”的思路不一致，且如果题目要求被查找函数本身负责输出，你的实现就不符合要求了。 标准答案的核心思路是在递归过程中，一旦找到符合条件的值（即所有差值最小的节点）就立即输出并停止。你的做法是在遍历结束后再输出，虽然结果可能正确，但处理逻辑与标准答案的“边查边输出”有偏差，且在递归函数内没有直接实现输出功能，这是一个逻辑上的不完成。但考虑到你的整体思路是完整的，且能通过数组记录结果，我们判定为一个小逻辑偏差，扣2分。
- 总结：综合来看，你的代码逻辑基本正确，能够完成任务，但输出处理方式与标准答案的“即时输出”不同，且在递归函数内没有完成题目的输出要求，存在逻辑上的不完善，因此扣除2分。
题目总分：4+6=10分
第一个序列不能得到，第二个序列可以得到。 Pj<Pk<Pi . 5
已知当 n=k−1 时，栈可得到的出栈序列总数为
Ck−1=M
其中 Cn 为第 n 个卡特兰数。
评分及理由
（1）得分及理由（满分2分）
学生回答“第一个序列不能得到，第二个序列可以得到”，该判断与标准答案一致。但标准答案中要求判断两个序列，第一个序列{2,3,1,6,4,7,5,4,8}中有重复数字4，这本身已不合法，学生未指出此逻辑错误（重复数字使得序列长度与n=9矛盾，无法由1..9的入栈序列得到）。由于判断结果正确（不能得到），且第二个序列判断正确（能得到），未完全扣到细节但整体判断无误，因此给满分。得分：2分。
（2）得分及理由（满分2分）
学生回答“Pj < Pk < Pi”，标准答案为“Pi > Pk > Pj”，两者等价（即Pi最大，Pj最小，Pk中间），但表述顺序不同。学生写的“Pj < Pk < Pi”实际上是Pj最小、Pk中间、Pi最大，与标准答案大小关系一致，因此正确。得分：2分。
（3）得分及理由（满分2分）
学生仅回答“5”，未列出具体序列。标准答案要求给出具体个数，答案5是正确的，但未列出序列不扣分（因为只要求个数）。因此给满分。得分：2分。
（4）得分及理由（满分4分）
学生回答“已知当n=k-1时，栈可得到的出栈序列总数为 C_{k-1} = M”，并将卡特兰数写为Cn（通常卡特兰数公式为C_{2n}^n/(n+1)）。但问题要求回答n=k时以1开头的个数、以2开头的个数、以及总序列个数，学生未给出任何具体回答（没有回答以1开头的个数、以2开头的个数、总个数），仅做了无关陈述。因此完全未作答，不得分。得分：0分。
题目总分：2+2+2+0=6分
主存单元宽度：8 位 通用寄存器宽度：16 位 op1 和 op2 可以相同，因为两者在指令中占据不同位。op2 和 op3 不能相同，因为两者在指令中占据相同位，若相同会导致指令冲突。 R2 中的内容变为 98CEH，R9 中的内容保持不变为 F001H。 ① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010。
评分及理由
（1）得分及理由（满分2分）
学生回答：“主存单元宽度：8 位 通用寄存器宽度：16 位”。
标准答案为：主存单元宽度8位，通用寄存器宽度16位。学生答案完全正确，无逻辑错误。得分：2分。
（2）得分及理由（满分2分）
学生回答：“op1 和 op2 可以相同，因为两者在指令中占据不同位。op2 和 op3 不能相同，因为两者在指令中占据相同位，若相同会导致指令冲突。”
标准答案为：OP1和OP2可以相同，OP2和OP3不可以相同。学生回答正确，思路清晰，理由正确。无逻辑错误。得分：2分。
（3）得分及理由（满分2分）
学生回答：“R2 中的内容变为 98CEH，R9 中的内容保持不变为 F001H。”
标准答案为：R2的内容为ABCDH + F001H = 9BCEH，R9内容不变为F001H。学生计算结果为98CEH，与标准答案9BCEH不符。
正确计算：ABCDH + F001H = (A + F) = 19H（进位1），(B + 0) = BH，加上进位为CH，(C + 0) = CH，(D + 1) = EH，结果为9BCEH（注意最高位溢出，实际16位结果为9BCEH）。学生可能误算为98CEH，存在逻辑错误。得分：0分。
（4）得分及理由（满分4分）
学生回答：“① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010。”
标准答案为：①是1110；②是0000 0100；③是1111 1011；④是0000 0000 0010。学生答案与标准答案完全一致，无逻辑错误。得分：4分。
题目总分：2+2+0+4=8分
（15分）假定43题中计算机C的部分数据通路如题44所示。
图中带箭头虚线代表控制信号 IR.rt、IR.rs 分别表示 IR 中的 rt、rs 字段，IR₁₁₋₀为 IR 的低12位，要求取指令周期完成 PC 增量操作，请回答下列问题
（1）①②是同一类部件，其名称是什么（1分）
（2）I 型指令中 imm8 可以是带符号或无符号整数，M 型指令中 offset 是带符号整数，则EXTOP 至少有几位？为什么？（2 分）
（3）取指周期中 MARSrC、ALUA SrC、ALUB SrC、RegWr 的取值各是什么？（4 分）
（4）左移指令周期中 ALUB SrC、Regwsrc、RegDst、Regwr 的取值各是什么？Extop 是否可以与 M 型指令中的 EXTop 相同？为什么？（2 分）
(1) 多路选择器
R 型指令需要用到寄存器编号 rs 和 rt，M 型指令需要用到寄存器 0 和 15，所以需要通过二路选择器进行选择。
(2) 只需要 1 位，因为只需要 1 位就可以实现零扩展和符号扩展这两种操作。
MARSrc=0, ALUA Src=0, ALUB Src=1, RegWr = 0
(4) 左移指令需要通过扩展器获取到左移的立即数，所以 ALUB Src=2，计算结果通过 ALU 写回到通用寄存器中，所以 RegWSrc=1，RegWr=1，写入的寄存器位 R[rt]，所以 RegDst=1。
综上：ALUB Src=2, RegWSrc=1, RegDst=1, RegWr=1
评分及理由
（1）得分及理由（满分1分）
得1分。学生回答“多路选择器”正确，与标准答案一致，理由虽稍多余但不影响得分。
（2）得分及理由（满分2分）
得2分。学生回答“1位”正确，并解释了通过1位即可实现零扩展和符号扩展两种操作，与标准答案一致，理由充分。
（3）得分及理由（满分4分）
得0分。学生回答“MARSrc=0, ALUA Src=0, ALUB Src=1, RegWr = 0”，但标准答案要求顺序为 MARsrc、ALUAsrc、ALUBsrc、RegWr。学生将“MARsrc”误写为“MARSrc”，且将“ALUAsrc”误写为“ALUA Src”（多了空格），但最核心的错误是：学生未按题目要求给出4个控制信号的答案，而是直接在（3）中写了答案却未正确编号，实际答案内容虽数值正确，但格式混乱，且学生将（3）的答案与（4）的说明混在一起（学生作答中（3）位置没有独立列出答案，而是直接放在（2）之后），导致无法明确其意图。按严格判卷规则，答案未按顺序清晰列出，视为回答不完整，扣4分。
（4）得分及理由（满分2分）
得0分。学生回答“ALUB Src=2, RegWSrc=1, RegDst=1, RegWr=1”，但标准答案要求的是“ALUBsrc=2，RegWsrc=1，RegDst=1，RegWr=1，不可以相同”。学生未回答“Extop 是否可以与 M 型指令中的 EXTop 相同？为什么？”这一关键问题，导致回答不完整。按题目要求，此部分包含两个子问题：控制信号取值和扩展方式比较，学生只回答了前者，遗漏后者，扣2分。
题目总分：1+2+0+0=3分
中断次数、CPU 调度次数与各进程首次调度时刻模拟调度过程，考虑时钟中断每 10 ms 发生一次，进程到达、完成及调度事件如下：
10 ms：P1、P2 到达，CPU 空闲，调度 P2 运行（首次调度）。
20 ms：时钟中断，P2 运行 10 ms 后被更高优先级的 P4 抢占，调度 P4 运行（首次调度）。70 ms：时钟中断，P4 时间片用完，优先级减 1，调度 P2 运行。80 ms：时钟中断，P2 完成，调度 P4 运行。90 ms：时钟中断，P4 完成，调度 P1 运行（首次调度）。140 ms：时钟中断，P1 时间片用完，优先级减 1，调度 P3 运行（首次180 ms：时钟中断，P3 完成，调度 P1 运行。225 ms：P1 完成，所有进程结束中断次数：从 10 ms 开始，时钟中断时刻为 10, 20, …, 220 ms，共 22 次。
CPU 调度次数：共 7 次（10 ms、20 ms、70 ms、80 ms、90 ms、140 ms、180 ms）。
首次调度时刻：
- P1:90 ms
- P2:10 ms
- P3:140 ms
- P4:20 ms
时间片由 50 ms 改为 100 ms：时间片增大，进程因时间片用完而让出 CPU 的次数减少，更多进程可能一次运行完成，从而降低进程切换频率，CPU 调度次数减少。 时钟中断间隔由 10 ms 改为 1 ms：中断更频繁，每次中断均需进行调度检查，可能增加上下文切换次数与中断处理时间，系统开销增大。
评分及理由
（1）得分及理由（满分5分）
学生对于中断次数和CPU调度次数的计算结果（22次中断，7次调度）与标准答案一致，这部分正确，可得2分。但学生在调度过程的描述中存在多处逻辑错误：
- 20ms时：学生认为“P2运行10ms后被更高优先级的P4抢占”，但标准答案中P2并未被抢占，而是在10ms开始运行后，20ms时钟中断时，P4才到达（14ms）并进入就绪队列，此时系统比较优先级（P4优先权5 > P2的4）故调度P4。学生的描述未明确时间点（20ms时P4已到达），但核心错误在于后续的调度顺序：学生认为“70ms调度P2、80ms调度P4”是错误的。根据规则，P4运行到90ms才结束（P4需60ms，从20ms到90ms共70ms），中间只有时间中断，不存在其他进程抢占（P2、P1、P3的优先级均低于P4）。标准答案中，P4从20ms运行到90ms结束，随后调度P1。学生错误地在80ms调度了P4（此时P4已在运行）并提前在70ms调度了P2，导致整体流程混乱。
- 学生后续调度（如180ms调度P1、225ms结束）与标准答案不符。标准答案中，P1从90ms运行到140ms（时间片50ms用完），优先级减1变为2，回退队列；然后调度P3（140ms到180ms，P3需40ms），P3完成后调度P1（180ms到220ms，P1剩余45ms），最终220ms结束。学生却多加了额外的调度事件（如180ms调度P1后又到225ms结束），且未考虑P3的首次调度时刻（标准答案为140ms，学生为140ms正确，但后续流程错误）。
- 首次调度时刻：P1的90ms正确；P2的10ms正确；P3的140ms正确（但后续流程错误不影响首次调度时刻）；P4的20ms正确。因此首次调度时刻部分得2分，但调度过程错误扣2分（逻辑错误扣分）。
综上，学生因调度过程逻辑错误，扣2分，但中断次数、调度次数和首次调度时刻基本正确，故（1）题得分：3分（5分满分扣2分）。
（2）得分及理由（满分2分）
学生回答“CPU调度次数减少，系统开销增大”与标准答案一致，且理由正确（时间片增大减少切换，中断间隔减小增加开销）。因此得2分。
题目总分：3+2=5分
131 2 4096×32=131072 。
删除目录 dir1（非空）需递归删除其下文件 file，再删除自身，对元数据的操作包括：
- 删除文件 file：
- 根据 file 的索引节点（节点号 1000）释放其占用的所有数据块（包括直接块、间接块及间接块本身），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将节点 1000 对应位清零。
- 修改 dir1 的目录数据块，删除 file 的目录项。
- 删除目录 dir1：
- 释放 dir1 目录文件占用的数据块（存放目录项的数据块），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将 dir1 的索引节点（节点号 201）对应位清零。
- 修改父目录 dir 的目录数据块，删除 dir1 的目录项。
评分及理由
（1）得分及理由（满分3分）
学生答案中：
- “131”计算正确，与标准答案一致。每个盘块可存储32个索引节点（4KB/128B=32），索引节点号1000在第32页内偏移第8个（1000 mod 32=8），起始盘块号100，故盘块号=100+floor(1000/32)=100+31=131，正确，获得1分。
- “2”错误。正确答案最多需要读2个盘块（一个索引节点块+一个数据块），学生未解释或明确给出此数值，仅写“2”但未说明含义，且后续分析中未体现读取过程，无法判断是否答对。根据上下文，学生可能混淆了“需要读的盘块数”与“地址项层级”，实际应为2个盘块，但学生未给出完整推理，故不得分。
- “4096×32=131072”是错误的。标准答案要求最大文件数应为(4096×4KB)/128B=2^17=131072个，但学生仅写了乘法结果，未明确说明这是最大文件数，且计算过程与索引节点表总容量无关（索引节点表占用4096个盘块，每个盘块32个索引节点，总数为4096×32=131072），但学生未正确表述“最多可以存放多少个文件”这一问题的答案，且未正确关联到索引节点表总容量。此外，学生答案中缺少对“最多需要读多少个盘块”的明确回答。本题共3小问，学生仅答对第一小问（盘块号），故得1分。
（2）得分及理由（满分5分）
学生答案正确描述了删除目录dir1的步骤：先递归删除子文件file，再删除dir1自身，包括释放索引节点、数据块、位图更新以及目录项删除。与标准答案一致，获得满分5分。
题目总分：1+0+5=6分
（9分）假设C建立一条TCP连接，向服务器Si上传一个总长度为2000B的计算任务描述文件。已知C的拥塞窗口初始阈值为8MSS，MSS=500B，Si对收到每个TCP段进行确认，且确认段不封装数据。接收窗口rwnd始终为1000B，RTT=5ms，C建立连接时选择的初始序号为1000，Si选择的初始序号为2000，SYN、ACK、FIN为标志位，seq为序号，ack_seq为确认序号。在整个文件传输过程中未出现任何重传或报文丢失。
（1）C与Si建立TCP连接过程需要几次握手？C收到的SYN=1，ACK=1的TCP段的确认序号是多少？
（2）当C接收Si发送的ACK=1，seq=2001，ack_seq=2001，rwnd=1000确认段后，C的拥塞窗口增加到多少？C的发送窗口设置为多少？
（3）C与Si释放TCP连接过程需要几次挥手？C收到最后一个TCP报文段的序号（seq），确认序号（ack_seq），FIN的值分别是多少？
（4）忽略报文段传输时延，且时间从C请求建立TCP连接时刻算起，则C确定Si已成功接收到文件的时间是多少？
（1）TCP 连接需要 三次握手。C 收到的 SYN=1、ACK=1 的 TCP 段是第二次握手，其确认序号为 C 的初始序号加 1，即 1000 + 1 = 1001。
（2）收到该确认段时，C 的拥塞窗口增加 1 MSS，从 2 MSS 增加到 3 MSS 即 1500B。发送窗口取拥塞窗口和接收窗口的最小值，即 min(3 MSS, 1000 B) = 1000 B。
（3）TCP 连接释放需要 四次挥手。C 收到的最后一个报文段是 Si 发送的 FIN+ACK 段，其序列号 seq 为 Si 的初始序号加 1（SYN 消耗一个序号），即 2000 + 1 = 2001；确认序号为 C 的 FIN 序号加 1，C 发送的数据最后一个字节序号为 3000，FIN 段序号为 3001，故确认号为 3001 + 1 = 3002；FIN 标志位为 1。
（4）从连接建立开始，忽略报文段传输时延，连接建立耗时 1 RTT = 5 ms。数据传输过程中，受接收窗口限制，每次最多发送 2 MSS，共需传输 4 MSS。第一个报文段在连接建立后发送，其 ACK 在 1 RTT 后到达（5 + 5 = 10 ms），随后发送两个报文段，其 ACK 在下一个 RTT 后到达（10 + 5 = 15 ms），接着发送最后一个报文段，其 ACK 在再一个 RTT 后到达（15 + 5 = 20 ms）。故 C 确定 Si 成功接收文件的时间为 20 ms。
评分及理由
（1）得分及理由（满分3分）
学生回答正确。对于三次握手的次数判断无误，确认序号计算正确（初始序号1000+1=1001），符合TCP连接建立机制。得3分。
（2）得分及理由（满分2分）
学生回答正确。拥塞窗口从2MSS增加到3MSS（1500B），发送窗口取拥塞窗口与接收窗口最小值（1000B）的理由充分且计算正确。得2分。
（3）得分及理由（满分2分）
学生回答存在逻辑错误。题目中C发送的总数据长度为2000B（4个MSS），初始序号为1000，因此C最后发送的数据字节序号范围是1000~2999（共2000字节），数据发送完成后C发送FIN段，其序号应为3000（而非3001）。学生对FIN段序号的解释中，误认为C的FIN段序号为3001，导致最后的确认序号计算为3002，与标准答案的seq=2001、ack_seq=3002不一致。虽然最终确认序号结果巧合正确（3002），但推导过程逻辑错误，且seq值应为2001（来自Si的初始序号2000+SYN消耗1），学生正确回答了seq=2001和FIN=1。本题应扣1分，得1分。
（4）得分及理由（满分2分）
学生回答正确。对传输时间分析合理：连接建立1RTT，数据传输受接收窗口限制分4次发送（每次2MSS=1000B），总耗时从连接建立算起共4RTT=20ms。得2分。
题目总分：3+2+1+2=8分
The road of your choice, you have to go on !
粤ICP备16082171号-1
