科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
支持 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控制递归终止）。
最后输出所有差值为min的结点。
// 当前的绝对值差值最小值
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，并在差值大于等于min时停止查找（通过flag控制）。该思路与标准答案一致，表述清晰、完整，符合题目要求。因此给予满分。
（2）得分及理由（满分8分）
得分：7分
理由：学生的代码实现整体思路正确，采用了中序遍历、全局变量记录最小差值和flag控制递归终止。但存在两处较明显的逻辑问题：
① 在else if (diff == min)分支中，学生试图收集与当前min值相等的结点，但根据题目要求“查找树中关键字与K之差的绝对值最小的所有结点”，标准答案在遇到diff == min时仅输出preNode和当前结点（即相邻的两个结点，因为中序序列递增，差值相等只可能发生在相邻结点），而学生代码中通过数组min_data收集所有满足diff == min的结点，这会导致错误输出。例如，如果min=3，中间多个连续结点与K的差值都是3，但根据二叉搜索树的中序性质，只有当当前结点与前一结点的差值相等时才可能有多个最小值结点，学生的收集方式会错误地收集不相邻的结点，逻辑不够严谨。因此扣1分。
② 在diff > min时设置flag=1是正确的，但学生代码中未在diff < min时重置flag，当找到更小的差值后，flag仍为0，不影响后续遍历，此部分正确；然而，在学生代码中，当diff == min时并未设置flag，而是继续遍历，这可能导致重复收集，但结合中序性质，若diff == min发生在已经找到更小值之后，则不应继续，但学生未处理此情况，存在潜在逻辑漏洞。但因标准答案中类似的处理方式也较简单，且主要问题在于收集所有相等差值的逻辑错误，因此从轻扣分。
总体代码结构清晰，变量命名合理，基本功能正确，故扣1分，得7分。
题目总分：4+7=11分
第一个序列不能得到，第二个序列可以得到。 Pj<Pk<Pi . 5 以1开头的出栈序列有M个，以2开头的出栈序列有M个，全部出栈序列有 $$C_k = \frac{1}{k+1}C_{2k}^k$$个。
评分及理由
（1）得分及理由（满分2分）
学生回答“第一个序列不能得到，第二个序列可以得到”，与标准答案一致，判断正确。学生没有提及具体原因，但问题只要求判断是否能得到，答案正确。
得分：2分
（2）得分及理由（满分2分）
学生回答“Pj<Pk<Pi”，这表示 P_i>P_k>P_j，与标准答案“Pi>Pk>Pj”完全一致。学生正确表达了出栈序列中不可能出现的大小关系。
得分：2分
（3）得分及理由（满分2分）
学生只写了一个数字“5”，没有列出具体序列。但问题只要求“2开头的序列个数有多少个”，答案“5”正确，且标准答案中序列数为5。未列出序列不扣分，因为问题只要求个数。
得分：2分
（4）得分及理由（满分4分）
学生回答“以1开头的出栈序列有M个，以2开头的出栈序列有M个”，与标准答案一致，正确。对于全部出栈序列，学生写的是“$$C_k = \frac{1}{k+1}C_{2k}^k$$个”，虽然写法不规范（括号位置可能有歧义），但数学表达式本质与标准答案“\(\frac{C_{2k}^k}{k+1}\)个”相同，都是卡特兰数公式，因此答案正确。
得分：4分
题目总分：2+2+2+4=10分
主存单元宽度：8 位 通用寄存器宽度：16 位 op1 和 op2 可以相同，因为两者在指令中占据不同位。op2 和 op3 不能相同，因为两者在指令中占据相同位，若相同会导致指令冲突。 R2 中的内容变为 9BCEH，R9 中的内容保持不变为 F001H。 ① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010。
评分及理由
（1）得分及理由（满分2分）
学生回答：“主存单元宽度：8 位 通用寄存器宽度：16 位”。判断正确，与标准答案一致。得2分。
理由：按字编址的16位计算机中，主存单元（即存储芯片的基本单元）通常对应8位（字节），而寄存器宽度与机器字长一致为16位。
（2）得分及理由（满分2分）
学生回答：“op1 和 op2 可以相同，因为两者在指令中占据不同位。op2 和 op3 不能相同，因为两者在指令中占据相同位，若相同会导致指令冲突”。判断正确（op1与op2可相同，op2与op3不可相同），且解释合理。得2分。
理由：op1位于R型指令的低4位，op2位于I型指令的高4位，所在位域不冲突故可重复编码；op2与op3均位于指令的高4位，若相同则无法区分I型和M型指令，故不可相同。
（3）得分及理由（满分2分）
学生回答：“R2 中的内容变为 9BCEH，R9 中的内容保持不变为 F001H”。计算结果正确（ABCDH + F001H = 1 9BCEH，但16位寄存器截取低16位得9BCEH），且对R9不变描述正确。得2分。
理由：指令为R型加法，结果存入R2，R9不变。加法结果正确。
（4）得分及理由（满分4分）
学生回答：“① = 1110，② = 0000 0100，③ = 1111 1011，④ = 0000 0000 0010”。所有答案均与标准答案完全一致（①为M型取数指令op3=1110；②为R型中表示左移操作码0010对应的rt与rs字段组合，实际上学生写出的“0000 0100”符合标准格式，将高4位rt和低4位rs正确给出；③为立即数-5的补码表示（1111 1011）正确，且位置对应I型的imm8字段；④为存数指令的目标地址偏移offset（2）的12位表示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，不可以相同 ， 因为左移指令的 shamt需零扩展，而 M 型 offset 需符号扩展，扩展方式不同 会导致冲突
评分及理由
（1）得分及理由（满分1分）
学生回答正确，名称与标准答案一致。得1分。
（2）得分及理由（满分2分）
学生回答“只需要1位”，理由正确，能够说明用于区分符号扩展和零扩展。得2分。
（3）得分及理由（满分4分）
学生回答“MARsrc=0, ALUA Src=0, ALUBsrc=1, RegWr = 0”，其中“ALUA Src”写法与标准答案“ALUAsrc”略有书写格式差异，但含义完全一致，且所有取值均正确。得4分。
（4）得分及理由（满分2分）
学生回答“ALUBsrc=2，RegWsrc=1，RegDst=1，RegWr=1，不可以相同，因为左移指令的shamt需零扩展，而M型offset需符号扩展，扩展方式不同会导致冲突”。其中RegWsrc应为RegWsrc（书写略有差异但含义正确），所有控制信号取值及理由均正确。得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。
时间片由 50 ms 改为 100 ms：时间片增大，进程因时间片用完而让出 CPU 的次数减少，更多进程可能一次运行完成，从而降低进程切换频率，CPU 调度次数减少。
时钟中断间隔由 10 ms 改为 1 ms：中断更频繁，每次中断均需进行调度检查，可能增加上下文切换次数与中断处理时间，系统开销增大。
评分及理由
（1）得分及理由（满分5分）
学生回答中，中断次数“22次”和调度次数“7次”与标准答案一致，因此这一部分得2分（总分5分中，中断次数和调度次数各占1分左右，但需结合整体推理）。
然而，对于第一次调度的时刻，学生回答“P1的90ms；P2的10ms；P3的140ms；P4的20ms”，但标准答案要求的是“P1,P2,P3,P4在什么时刻进行第一次调度”，并且标准答案明确指出：在10ms时第一次调度P2，20ms时第一次调度P4，90ms时第一次调度P1，140ms时第一次调度P3。学生的回答中，P2的第一次调度时刻正确（10ms），但表述不规范（写为“P2的10ms”应理解为10ms）；P4的第一次调度时刻正确（20ms），表述为“20ms”正确；P1的第一次调度时刻错误，学生写为“90ms”，但实际上P1在90ms时是第二次调度（第一次调度应在更早？注意P1在10ms就绪，但从未被调度过，直到90ms时才第一次被调度？标准答案中，P1确实是在90ms时第一次被调度，因为之前没有机会，所以学生的“90ms”对于P1的第一次调度是正确的；但P3的第一次调度时刻，标准答案是在140ms，学生写“140ms”正确。因此，对于第一次调度时刻，所有进程的时刻均正确，但学生表述为“P1的90ms；P2的10ms；P3的140ms；P4的20ms”这种列表形式可能不够清晰，但内容正确，不扣分。
另外，学生后面的运行过程描述（P4从20ms到90ms，P1从90ms到140ms等）与标准答案基本一致，逻辑正确。
因此，第（1）小题学生得满分5分。
（2）得分及理由（满分2分）
对于时间片由50ms改为100ms的影响，学生回答“CPU调度次数减少”，与标准答案“减少”一致，得1分。
对于中断间隔从10ms改为1ms的影响，学生回答“系统开销增大”，与标准答案“增大”一致，得1分。
因此，第（2）小题学生得满分2分。
题目总分：5+2=7分
131 最多需要读2个盘块（一个索引节点块+一个数据块） ， 最大文件数应为(4096×4KB)/128B=2^17=131072个
删除目录 dir1（非空）需递归删除其下文件 file，再删除自身，对元数据的操作包括：
- 删除文件 file：
- 根据 file 的索引节点（节点号 1000）释放其占用的所有数据块（包括直接块、间接块及间接块本身），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将节点 1000 对应位清零。
- 修改 dir1 的目录数据块，删除 file 的目录项。
- 删除目录 dir1：
- 释放 dir1 目录文件占用的数据块（存放目录项的数据块），在磁盘位示图中将对应位清零。
- 在索引节点位示图中将 dir1 的索引节点（节点号 201）对应位清零。
- 修改父目录 dir 的目录数据块，删除 dir1 的目录项。
评分及理由
（1）得分及理由（满分3分）
学生答案共包含三个子问题：
- file的索引节点所在盘块号：学生答“131”，与标准答案相符，计算正确（一个盘块32个索引节点，1000/32=31.25，盘块号100+31=131）。得1分。
- 访问偏移21460字节需读盘块数：学生答“最多需要读2个盘块（一个索引节点块+一个数据块）”。标准答案认为21460在一级间接地址中，需读2个盘块（索引节点块+数据块）。学生答案正确，得1分。
- 最大文件数：学生答“(4096×4KB)/128B=2^17=131072个”。标准答案为2^17个。学生答案正确，得1分。
（1）小问得分：3分
（2）得分及理由（满分5分）
学生分析删除dir1的元数据操作，整体思路正确，但存在一个小错误：
- 学生提到“修改dir1的目录数据块，删除file的目录项”。根据目录结构，file在dir1下，删除file时，需删除dir1中file的目录项，但dir1本身是一个目录文件，其数据块中存放了file的目录项。学生表述“修改dir1的目录数据块”不够精确，标准答案要求“删除dir目录中dir1的目录项内容”。但此错误属于表述不够严谨，未造成逻辑错误，且学生后续正确指出了删除dir1时需修改父目录dir的目录项。总体思路正确，不扣分。
- 其他操作（释放file数据块、释放索引节点、更新位图、释放dir1数据块、更新位图）均完整且正确，无逻辑错误。
（2）小问得分：5分
题目总分：3+5=8分
（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） C 确定 Si 成功接收文件的时间为 20 ms。
评分及理由
（1）得分及理由（满分3分）
学生回答正确指出“三次握手”，且确认序号计算正确（1000+1=1001），与标准答案一致。未发现逻辑错误。
得分：3分
（2）得分及理由（满分2分）
学生回答正确指出拥塞窗口增至3MSS（1500B），发送窗口为min(1500B,1000B)=1000B，与标准答案完全一致。未发现逻辑错误。
得分：2分
（3）得分及理由（满分2分）
学生回答正确包含seq=2001、ack_seq=3002、FIN=1，与标准答案一致。但未明确说明需要“四次挥手”，虽然数值正确，但题干问的是“需要几次挥手”，标准答案明确要求回答“四次挥手”，学生未写出该部分，属于回答不完整。由于该小问分值2分，缺少一次握手的描述扣1分。
得分：1分
（4）得分及理由（满分2分）
学生回答“20ms”正确，与标准答案一致。未发现逻辑错误。
得分：2分
题目总分：3+2+1+2=8分
The road of your choice, you have to go on !
粤ICP备16082171号-1
