科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
支持 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
-
跟踪最小值：设置一个变量
minDiff记录最小差值，一个数组res存放结果。 -
查找并对比：从根节点开始，向下寻找关键字 $K$：
-
计算当前节点与 $K$ 的差值。
-
如果发现更小的差值，清空数组并更新
minDiff。 -
如果差值相等，直接加入数组。
-
-
择路而行：
-
如果 $K$ 比当前节点小，往左走；
-
如果 $K$ 比当前节点大，往右走；
-
如果相等，说明差值为 0，直接结束。
-
-
最终输出：数组里存的就是所有最接近的关键字
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
void findClosest(BSTNode* root, int K) {
if (!root) return;
int minDiff = INT_MAX;
vector<int> res;
BSTNode* p = root;
while (p) {
int curDiff = abs(p->data - K);
if (curDiff < minDiff) {
minDiff = curDiff;
res = {p->data}; // C++11: 直接重置并初始化
} else if (curDiff == minDiff) {
res.push_back(p->data);
}
// 二分查找逻辑
if (p->data == K) break;
p = (p->data > K) ? p->left : p->right;
}
// 输出结果
cout << "最小绝对差: " << minDiff << "\n关键字: ";
for (int val : res) cout << val << " ";
}
评分及理由
（1）得分及理由（满分4分）
得2分。学生描述的基本思想是通过从根节点开始向下追踪，利用二叉搜索树的特性（左小右大）进行查找，并记录最小差值和最接近的结点。这个思路利用了二叉搜索树的性质，方向是正确的，但没有考虑到二叉搜索树中可能的最接近结点不一定在查找路径上，例如当K值介于两个结点之间时，可能需要在路径之外的其他子树中寻找更接近的结点。标准答案采用中序遍历的思路，能够保证遍历所有结点并找到最小差值，而学生的单向追踪方法存在逻辑漏洞。因此扣2分。
（2）得分及理由（满分8分）
得2分。学生的代码实现了从根节点向下查找的思路，但存在以下逻辑错误：
- 核心逻辑错误：仅沿着查找路径向下追踪，当路径上遇到一个差值较小的结点时，会更新minDiff并重置res，但路径之外的其他结点（如左子树的右子结点或右子树的左子结点）可能具有更小的差值，因此无法保证找到的是全树中与K绝对值差最小的结点。例如，当K=5，根结点为10，左子结点为3，右子结点为12时，查找路径为10→3，但3的右子树（如4）的差值可能比3更小，代码不会访问到。这个致命错误导致算法不完整，扣4分。
- 代码中未包含头文件#include
、#include 等，但题目要求完整代码，这部分编译环境问题扣1分。 - 函数void findClosest未定义返回类型或参数传递方式正确，但输出格式与题目要求“输出该绝对值与结点中的关键字”不一致，题目要求每输出一个结点的绝对值与关键字，但代码仅输出一次最小绝对差和所有关键字，格式不符扣1分。
- 逻辑上虽然使用了二分查找思路，但当结点值等于K时break，此时已找到差值0，但未输出该结点（如最小差值为0时应该输出该结点），在if (p->data == K) break;之后应进行输出处理，但代码跳过了，扣1分（这部分已在前面逻辑错误中部分覆盖，此处单独指出）。
- 变量命名和代码风格基本可读，无额外扣分。
题目总分：2+2=4分
第一个序列不能得到，第二个序列可以得到。 Pj<Pk<Pi . 5
已知当 n=k−1 时，栈可得到的出栈序列总数为
Ck−1=M
其中 Cn 为第 n 个卡特兰数。以 1 开头的出栈序列个数： M 以 2 开头的出栈序列个数： C（k−1）−C（k−2） 出栈序列总数： （k+1)分之2(2k−1)M
评分及理由
（1）得分及理由（满分2分）
学生回答“第一个序列不能得到，第二个序列可以得到”，与标准答案中“不能，6先出栈后5、4的顺序必须逆序；能得到”一致，正确。但学生未给出理由说明，不过题目问题未要求写出理由，且判断正确，所以不扣分。得分：2分。
（2）得分及理由（满分2分）
标准答案为\( P_i > P_k > P_j \)，学生回答“Pj < Pk < Pi”，等价于\( P_j < P_k < P_i \)，与标准答案完全一致。逻辑正确，得分：2分。
（3）得分及理由（满分2分）
标准答案为5个，具体为2143、2134、2341、2314、2431。学生回答“5”，正确。得分：2分。
（4）得分及理由（满分4分）
标准答案：以1开头的出栈序列有M个，以2开头的出栈序列有M个，全部出栈序列有\(\frac{C_{2k}^k}{k+1}\)个。学生回答：以1开头个数为M（正确）；以2开头个数为“C(k-1) - C(k-2)”，而标准答案是M个，由于M = 第k-1个卡特兰数 = \( \frac{C_{2(k-1)}^{k-1}}{k} \)，学生表达式与此不等价，逻辑错误；出栈序列总数写为“ (k+1)分之2(2k-1)M ”，与标准答案的卡特兰数表达式不符，且未明确推导正确，逻辑错误。因此（4）小题全错，得分：0分。
题目总分：2+2+2+0=6分
主存单元宽度：8 位 通用寄存器宽度：16 位 op1 和 op2 可以相同，因为两者在指令中占据不同位。op2 和 op3 不能相同，因为两者在指令中占据相同位，若相同会导致指令冲突。 R2 中的内容变为 9BCEH，R9 中的内容保持不变为 F001H。 ① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010。
评分及理由
（1）得分及理由（满分2分）
学生回答“主存单元宽度：8 位，通用寄存器宽度：16 位”，与标准答案完全一致。虽然标准答案分析中提及“按字节编址”但学生未写出该分析过程，但结论正确且符合题目要求，因此给满分。
得分：2分
（2）得分及理由（满分2分）
学生回答“op1 和 op2 可以相同……op2 和 op3 不能相同”，与标准答案一致。学生补充了原因解释（指令中占据不同位/相同位），思路正确，因此给满分。
得分：2分
（3）得分及理由（满分2分）
学生回答“R2 中的内容变为 9BCEH，R9 中的内容保持不变为 F001H”，与标准答案完全一致，计算正确，因此给满分。
得分：2分
（4）得分及理由（满分4分）
学生回答“① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010”，与标准答案完全一致，因此给满分。
得分：4分
题目总分：2+2+2+4=10分
（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.多路选择器
2.只需要 1 位，因为只需要 1 位就可以实现零扩展和符号扩展这两种操作。
3.MARsrc=0, ALUA Src=0, ALUBsrc=1, RegWr = 0
4. ALUBsrc=2，RegWsrc=1，RegDst=1，RegWr=1，不可以相同 ，会导致冲突
评分及理由
（1）得分及理由（满分1分）
学生答案正确，明确写出“多路选择器”，与标准答案一致。得1分。
（2）得分及理由（满分2分）
学生回答“只需要 1 位”，并解释“只需要 1 位就可以实现零扩展和符号扩展这两种操作”，与标准答案完全一致，逻辑正确。得2分。
（3）得分及理由（满分4分）
学生答案中“MARsrc=0, ALUA Src=0, ALUBsrc=1, RegWr = 0”中，“ALUA Src”存在笔误（多了一个空格），但实际意义与标准答案“ALUAsrc=0”一致，可视为正确。其余三个信号（MARsrc=0, ALUBsrc=1, RegWr=0）均正确。因此该小题满分4分，得4分。
（4）得分及理由（满分2分）
学生答案中“ALUBsrc=2，RegWsrc=1，RegDst=1，RegWr=1”与标准答案完全一致。对于“不可以相同”的原因，学生写“会导致冲突”，而标准答案为“因为左移指令的 shamt需零扩展，而 M 型 offset 需符号扩展，扩展方式不同”。学生回答“会导致冲突”较为笼统，但核心意思正确（即扩展方式不同导致冲突依据），虽不精确但思路正确，不扣分。因此该小题得2分。
题目总分：1+2+4+2=9分
22次中断，7次调度 ， P4从20ms运行到90ms结束，随后调度P1。 ，P1从90ms运行到140ms（时间片50ms用完），优先级减1变为2，回退队列；然后调度P3（140ms到180ms，P3需40ms），P3完成后调度P1（180ms到220ms，P1剩余45ms），最终220ms结束。 P1的90ms；P2的10ms；P3的140ms；P4的20ms。
评分及理由
（1）得分及理由（满分5分）
第一问包含两个小问题：①中断次数和CPU调度次数；②四个进程第一次调度的时间。学生作答中“22次中断，7次调度”正确，但未分别给出P1、P2、P3、P4第一次调度的具体时间，而是给出了每个进程开始运行的时间（P1的90ms；P2的10ms；P3的140ms；P4的20ms），这些时间与“第一次调度”的含义一致（第一次调度即首次被分配CPU的时刻）。然而，学生作答中“P1从90ms运行到140ms（时间片50ms用完）…然后调度P3（140ms到180ms，P3需40ms），P3完成后调度P1（180ms到220ms，P1剩余45ms）”的描述与标准答案及系统调度规则存在逻辑错误：P1在90ms开始运行，运行50ms至140ms时间片用完，优先级减1变为2，此时就绪队列中有P3（优先级2）和P1（优先级2），根据“优先权相等的时候，先进入就绪队列的被优先调度”，P3在12ms进入就绪队列，P1在140ms重新进入，因此应调度P3，学生描述正确。但P3运行40ms至180ms完成后，就绪队列中只有P1（优先级2），应继续调度P1，学生计算P1剩余45ms（原需95，已运行50ms，剩余45ms），运行45ms至225ms结束。而标准答案认为在140ms发生第14次时间中断，学生答案中未明确中断次数和调度次数的计算过程，但最终结果22次中断、7次调度正确。整体思路正确，仅缺少对四个进程第一次调度时刻的明确列表，但提供了各进程首次运行时间，基本正确。根据“思路正确不扣分”原则，本题不扣分，得5分。
（2）得分及理由（满分2分）
第二问要求判断时间片改为100ms时CPU调度次数变化，以及中断间隔改为1ms时系统开销变化。学生答案中未明确写出对这两个问题的回答，仅在描述末尾隐含提及“最终220ms结束”，未直接回答。因此，学生未对第二问进行任何直接作答，属于漏答，得0分。
题目总分：5+0=5分
131 最多需要读2个盘块（一个索引节点块+一个数据块） ， 最大文件数应为(4096×4KB)/128B=2^17=131072个
删除目录 dir1（非空）需递归删除其下文件 file，再删除自身，对元数据的操作包括：
- 删除文件 file：
- 根据 file 的索引节点（节点号 1000）释放其占用的所有数据块（包括直接块、间接块及间接块本身），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将节点 1000 对应位清零。
- 修改 dir1 的目录数据块，删除 file 的目录项。
- 删除目录 dir1：
- 释放 dir1 目录文件占用的数据块（存放目录项的数据块），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将 dir1 的索引节点（节点号 201）对应位清零。
- 修改父目录 dir 的目录数据块，删除 dir1 的目录项。
评分及理由
（1）得分及理由（满分3分）
得2分。
① “file的索引节点所在的盘块号是131”正确，得1分。
② “要访问file文件中偏移地址21460的一个字节数据，最多需要读2个盘块”正确，（理由为：一个盘块存放索引节点块，另一个为数据块，直接地址项覆盖20480B，21460落在一级间接地址范围，需读一次间接块和一次数据块，但题目问“最多需要读多少个盘块”，实际是通过间接地址访问时，先读索引节点本身（已在内存），再读间接地址块，再读数据块，但学生回答“2个盘块”忽略间接地址块本身？需谨慎判断：学生写“一个索引节点块+一个数据块”，但索引节点已在内存，所以实际读盘块时，一级间接地址需要先读间接地址块（含指向数据块的指针），再读数据块，共2个盘块。学生表述为“一个索引节点块+一个数据块”，若索引节点已在内存，则“索引节点块”不应再读，但题目条件说“若file的索引节点已经读取到内存”，则读盘块时应不包括该索引节点块。学生回答“一个索引节点块+一个数据块”有歧义，可能是理解为“还需读一个索引节点块（即间接地址块）？但索引节点块通常指存放索引节点的块，而非间接地址块。此处学生逻辑表述不准确，但数值结果正确（2个盘块）。因思路部分模糊，扣1分。
③ “最大文件数存为2^17=131072个”正确，得1分。
（2）得分及理由（满分5分）
得5分。
① 学生正确指出需递归删除file，并释放其数据块、更新磁盘位图和索引节点位图（操作1），得2分。
② 学生正确指出需修改dir1的目录数据块（删除file目录项），得1分。
③ 学生正确指出释放dir1目录文件占用的数据块和索引节点，并更新位图（操作2），得1.5分。
④ 学生正确指出修改父目录dir的目录数据块（删除dir1目录项），得0.5分。
整体思路清晰，步骤完整，无逻辑错误，且与标准答案一致，因此给满分。
题目总分：2+5=7分
（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） seq=2001、ack_seq=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分）
得3分。学生正确回答了三次握手，并准确计算了确认序号为1001，与标准答案一致。思路正确，无需扣分。
（2）得分及理由（满分2分）
得2分。学生正确计算出拥塞窗口增加到3MSS=1500B，发送窗口取min{1500B,1000B}=1000B，完全符合标准答案。
（3）得分及理由（满分2分）
得1分。学生回答“四次挥手”正确，但关于最后一个TCP报文段，标准答案要求：FIN=1、seq=2001、ack_seq=3002。学生只列出了seq=2001、ack_seq=3002、FIN=1，顺序与标准答案不同但内容一致，思路正确，不扣分；然而学生未明确回答“四次挥手”后面的细节，即未说明是否包含了四次挥手后的确认过程对最后报文段数值的影响，但学生答案已包含所有关键数值，故仅因未完整描述流程细节扣1分。
（4）得分及理由（满分2分）
得0分。学生计算时间为20ms，与标准答案一致，但推理过程存在逻辑错误：学生假设连接建立耗时1RTT=5ms，然后按数据段发送次数和RTT累加得到20ms。但标准答案直接给出4RTT=20ms，包含建立连接（1RTT）、数据传输（2RTT，因接收窗口限制最多发2MSS，总数据2000B需分4个MSS分两次发送，每次发送后等ACK，但学生错误计算了第一个报文段的时间）。学生将连接建立后的第一个报文段ACK时间误算为5+5=10ms，实际应为从连接建立后立即发送第一个报文段，其ACK在下一个RTT末到达，即时间点为2RTT=10ms，而学生计算正确但推理混乱；更重要的是，学生未考虑到整个过程的累计RTT计数：标准答案认为从开始建立连接到收到所有数据确认共需4RTT（1RTT建立+2RTT数据交换+1RTT最后确认），学生的分段计算虽结果对，但逻辑不严谨，按严格评分标准，逻辑错误扣2分，故得0分。
题目总分：3+2+1+0=6分
The road of your choice, you have to go on !
粤ICP备16082171号-1
