科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
1）
DFS 前序遍历二叉树，记录根到当前节点的路径。
每当进入一个节点，计算根到该节点的路径和。
如果路径和等于 k，则输出当前路径（从 path[0] 到 path[pathLen-1]）。
递归遍历左子树和右子树。回溯时恢复 pathLen。
2）
void FindValidPaths(BiTree T, int k, int *path, int pathLen) {
if (T == NULL) return;
// 将当前节点加入路径
path[pathLen] = T->val;
pathLen++;
// 检查从根到当前节点的路径和是否等于 k
int sum = 0;
for (int i = 0; i < pathLen; i++) {
sum += path[i];
}
if (sum == k) {
printPath(path, pathLen);
}
// 递归遍历左子树和右子树
FindValidPaths(T->lchild, k, path, pathLen);
FindValidPaths(T->rchild, k, path, pathLen);
// 回溯：pathLen 在递归返回后自动恢复（因为传值），所以不需要显式删除
// 实际上 pathLen 是值传递，递归返回后回到原来的值
}
3）
时间复杂度：每个节点访问一次，在访问每个节点时，计算从根到当前节点的路径和需要 O(路径长度)，路径长度最大为树高 h。所以总复杂度为 O(n × h)，在平衡树中 h = log n，最坏链状树 h = n，所以最坏 O(n²)，平均 O(n log n)。
空间复杂度：递归栈空间 O(h)，路径数组空间 O(h)，所以总空间复杂度 O(h)。
评分及理由
（1）得分及理由（满分4分）
得分：4分
理由：学生的设计思想与标准答案完全一致，都采用了DFS前序遍历、路径记录和回溯的思想。明确提到了路径记录、路径和检查、递归遍历子树以及回溯操作，思路清晰完整。
（2）得分及理由（满分7分）
得分：6分
理由：
- 代码整体结构正确，实现了前序遍历和路径记录
- 正确实现了路径和的计算和检查
- 正确实现了左右子树的递归遍历
- 扣分项：缺少printPath函数的实现（1分）。虽然学生提到了printPath函数，但在代码中没有给出具体实现，这是一个重要的逻辑缺失。
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了时间复杂度和空间复杂度。时间复杂度分析为O(n×h)，并区分了最坏情况和平均情况；空间复杂度分析为O(h)，与标准答案一致。
题目总分：4+6+2=12分
1）
总比较次数 = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 3 = 21
ASL = 21 / 8 = 2.625
2）
查找路径：15→20→18
比较次数：3
3）
15
/ \
8 18
/ \ \
5 12 25
/
10
删除过程：用直接前驱 18 替换 20，然后删除原 18 节点（叶子节点）。
评分及理由
（1）得分及理由（满分4分）
学生通过图形展示了BST结构，但图形中节点排列存在部分错误（如18和25的位置关系不符合BST规则），不过从文字描述和ASL计算来看，学生正确理解了BST的构造逻辑和ASL计算方法。ASL计算结果（2.625）与标准答案一致，且计算过程完整。图形错误可能为识别问题或绘制偏差，但核心逻辑正确。扣1分。
得分：3分
（2）得分及理由（满分3分）
学生正确给出了查找路径（15→20→18）和比较次数（3次），与标准答案完全一致。无逻辑错误。
得分：3分
（3）得分及理由（满分3分）
学生给出的删除后BST结构正确（用18替换20后调整子树），但删除过程描述存在逻辑错误：标准方法应使用中序后继（25）而非直接前驱（18）进行替换。学生错误地使用直接前驱替换，导致子树连接关系混乱（如18的右子树应连接25，但图中未体现）。扣2分。
得分：1分
题目总分：3+3+1=7分
（1）组号 6 位，块内地址 6 位，Cache 索引位 VA[11:6]
（2）a[512] 的 VA = 01C0 0830H，Cache 组号 = 2
（3）a[0] 块内偏移量 = 48 字节，缺失率 = 3.12%，平均访问时间 = 6.63 周期
（4）数组在 2 页中，缺页次数 = 2
评分及理由
（1）得分及理由（满分3分）
学生正确回答了组号位数（6位）、块内地址位数（6位）和Cache索引位（VA[11:6]），与标准答案完全一致。得3分。
（2）得分及理由（满分4分）
学生正确计算了a[512]的VA地址（01C00830H），但在计算Cache组号时出现错误：学生答案为2，而标准答案为32。组号计算错误扣2分。本题得2分。
（3）得分及理由（满分4分）
学生正确计算了a[0]的块内偏移量（48字节）、缺失率（3.12%）和平均访问时间（6.63周期）。虽然缺失率3.12%与标准答案3.13%有微小差异，但这是四舍五入导致的合理误差，不扣分。本题得4分。
（4）得分及理由（满分2分）
学生正确回答了数组分布在2页中，缺页次数为2次，与标准答案完全一致。得2分。
题目总分：3+2+4+2=11分
1)
VA=0040207CH
2)
寻址方式：相对寻址
偏移量：0BH
推导：00402057H + 2 + 0BH = 00402064H
3)
①源操作数是立即数 0x12345678，所以是 立即寻址。
②esi*4 + edx*4=(i * 64 + j) * 4;EA = 基地址 00431000H + (i * 64 + j) * 4
③00431000H在指令中以00 10 43 00H保存，故为小端方式
4）
00431000H可知对应cache行号为0xE0,初始Cache为空，第一次访问Cache缺失
评分及理由
（1）得分及理由（满分2分）
学生答案正确给出第11条指令虚拟地址为0040207CH，与标准答案一致。得2分。
（2）得分及理由（满分3分）
学生正确指出寻址方式为相对寻址，偏移量为0BH，推导过程正确（当前指令地址+指令长度+偏移量=目标地址）。得3分。
（3）得分及理由（满分3分）
①正确指出立即寻址（1分）；
②正确解释地址计算逻辑并给出EA公式（1分）；
③大小端判断理由不完整（仅提到地址字段的存储顺序，未分析立即数0x12345678的字节序列），但结论正确。根据严格评分标准扣0.5分，得0.5分。
本小题总分：1+1+0.5=2.5分
（4）得分及理由（满分2分）
学生结论正确（发生Cache缺失），但计算过程错误（错误得出Cache行号为0xE0，未正确拆分地址字段）。因缺少关键计算步骤且行号计算错误，扣1分，得1分。
题目总分：2+3+2.5+1=8.5分
1）
完成时间：P1=18, P2=11, P3=23
周转时间：P1=18, P2=8, P3=18
平均周转时间：(18 + 8 + 18) / 3 = 44 / 3 ≈ 14.67ms
2）
系统处于安全状态，一个安全序列是 P1→P2→P3
3）
semaphore S1 = 0;//P1与P2的同步
semaphore S2 = 0;//P2与P3的同步
P1() {
request(A, 1); // 申请打印机
// 使用打印机执行任务
// 运行时间 10ms（模拟）
release(A, 1); // 释放打印机
V(S1); // 通知 P1 已完成
}
P2() {
P(S1); // 等待 P1 完成
request(A, 1); // 申请打印机
request(B, 1); // 申请扫描仪
// 使用资源执行任务
// 运行时间 8ms
release(A, 1);
release(B, 1);
V(S2); // 通知 P2 已完成
}
P3() {
P(S2); // 等待 P2 完成
request(A, 1); // 申请打印机
// 使用打印机执行任务
// 运行时间 5ms
release(A, 1);
}
评分及理由
（1）得分及理由（满分2分）
学生答案中完成时间、周转时间计算完全正确，平均周转时间计算也正确。与标准答案一致。得2分。
（2）得分及理由（满分2分）
学生正确判断系统处于安全状态，并给出了正确的安全序列P1→P2→P3。虽然未展示详细计算过程，但结论正确。得2分。
（3）得分及理由（满分4分）
学生答案中存在以下问题：
1. 信号量定义正确，但伪代码中使用了P/V操作的标准写法（P(S1)、V(S1)），与题目要求的wait/signal不一致，但语义正确，此处不扣分。
2. 主要问题：P2进程中缺少对P1完成打印的等待条件的具体实现。根据题目要求"P1必须完成打印机使用（即P1运行结束）后，P2才能开始使用扫描仪"，但学生代码中P2在等待S1信号后立即申请打印机和扫描仪，没有体现"P1运行结束后P2才能使用扫描仪"的精确同步要求。这里存在逻辑不完整，扣1分。
3. 其他部分（资源请求释放、信号量使用）基本正确。得3分。
题目总分：2+2+3=7分
1)
页号位数：4，页内偏移位数：12
0x1A3F 的页号 = 1，页内偏移 = 2623
2)
FIFO：
块数为3：15次；
块数为4：10次；
LRU：
块数为3：12次；
块数为4：8次；
FIFO中15>10未出现Belady异常
3）
物理块数 3，LRU，缺页次数 = 12，总访问次数 = 20。
缺页率 p=1220=0.6
内存访问时间 Tm=100ns
缺页处理时间 Tf=20000ns
有效访问时间：
EAT=(1−p)×Tm+p×TfEAT=12040.0 ns
评分及理由
（1）得分及理由（满分2分）
学生答案：页号位数4，页内偏移位数12，逻辑地址0x1A3F的页号为1，页内偏移为2623，与标准答案完全一致。计算过程正确，得2分。
（2）得分及理由（满分3分）
学生答案：FIFO算法在块数为3时缺页15次，块数为4时缺页10次；LRU算法在块数为3时缺页12次，块数为4时缺页8次；并正确判断FIFO未出现Belady异常。所有数据与标准答案一致，得3分。
（3）得分及理由（满分2分）
学生答案：物理块数为3，采用LRU算法，缺页次数12次，总访问次数20次，缺页率p=0.6，内存访问时间100ns，缺页处理时间20000ns，但计算有效访问时间EAT时，公式使用EAT=(1-p)×Tm+p×Tf，计算结果为12040.0ns，与标准答案12100.0ns不符。标准答案的正确计算应为：EAT = (1-p)×Tm + p×(Tm + Tf) = 0.4×100 + 0.6×(100+20000) = 40 + 0.6×20100 = 40 + 12060 = 12100.0ns。学生在计算中忽略了缺页时也需要一次内存访问时间，导致结果错误。因此扣1分，得1分。
题目总分：2+3+1=6分
-
子网掩码 255.255.255.224，网络地址 192.168.1.0/27，可用 IP 192.168.1.1～192.168.1.30
-
第一次握手：SYN=1 ACK=0 seq=1000 ack=0；第二次握手：SYN=1 ACK=1 seq=2000 ack=1001
-
8KB/200ms=327.68 kbps
-
ICMP 类型 3 代码 0，因为目的网络不可达
评分及理由
（1）得分及理由（满分3分）
学生答案：子网掩码255.255.255.224，网络地址192.168.1.0/27，可用IP 192.168.1.1～192.168.1.30
标准答案：子网掩码255.255.255.192，网络地址192.168.1.0，可用IP 192.168.1.1～192.168.1.62
评分：0分
理由：学生选择了/27子网掩码（255.255.255.224），这只能提供30个可用IP地址，虽然满足20台主机需求，但题目要求划分4个均等子网。使用/27只能划分8个子网，不符合题目要求的4个子网。此外，学生给出的可用IP范围192.168.1.1～192.168.1.30中包含了主机A的IP地址192.168.1.30，但网络地址和广播地址计算错误。
（2）得分及理由（满分2分）
学生答案：第一次握手：SYN=1 ACK=0 seq=1000 ack=0；第二次握手：SYN=1 ACK=1 seq=2000 ack=1001
标准答案：第一次握手：SYN=1，ACK=0，seq=1000，ack=无；第二次握手：SYN=1，ACK=1，seq=2000，ack=1001
评分：1分
理由：第二次握手的关键字段完全正确（SYN=1，ACK=1，seq=2000，ack=1001）。但第一次握手中ack字段应为空或不设置，学生写为ack=0是不正确的。由于第二次握手完全正确，给1分。
（3）得分及理由（满分1分）
学生答案：8KB/200ms=327.68 kbps
标准答案：320 kbps
评分：0分
理由：学生计算过程过于简化，没有考虑单位转换。正确的计算应该是：窗口大小8KB=8192字节=65536比特，RTT=200ms=0.2秒，吞吐量=65536/0.2=327680bps=320kbps（按1024换算）。学生直接写8KB/200ms=327.68kbps，虽然数值接近，但缺乏正确的计算过程和单位转换，且结果不准确。
（4）得分及理由（满分3分）
学生答案：ICMP类型3代码0，因为目的网络不可达
标准答案：ICMP目的不可达报文，类型3，代码0，原因：R2到主机C所在网络的链路故障导致网络不可达
评分：3分
理由：学生准确给出了ICMP报文类型（类型3）、代码（0）和原因（目的网络不可达），与标准答案完全一致，解释简洁但正确。
题目总分：0+1+0+3=4分
The road of your choice, you have to go on !
粤ICP备16082171号-1
