科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是（）。
A．LRN B．NRL C．RLN D．RNL
不可以，设有三个节点A，B，C，AB之间举例为1，BC之间距离为2，AC之间距离为2，初始节点A，目标节点C，从A出发，选B，当前节点为B，根据算法会选择节点C，得出结论AC之间最短路径为ABC，长度为3，但实际是AB，长度为2
评分及理由
（1）得分及理由（满分10分）
学生回答“不可以”，判断正确，得2分。学生尝试举例说明，但所举例子存在逻辑错误：学生描述“AC之间距离为2”，这意味着存在一条从A直接到C的边，权值为2。按照题目描述的算法，从初始顶点A开始，选择“离u最近且尚未在最短路径中的一个顶点v”。此时，离A最近的顶点是B（距离1）和C（距离2）。算法会选择B（因为最近），然后将当前顶点u更新为B。接下来，从B出发，选择离B最近且未在路径中的顶点。由于C距离B为2，且A已在路径中，所以会选择C。最终路径为A->B->C，总长度为3。学生声称“实际是AB，长度为2”，这里“AB”应为“AC”的笔误。但即使修正为AC，实际最短路径长度是2（A->C），而算法得到长度为3，确实说明了算法失败。然而，学生例子中的图（A-B:1, B-C:2, A-C:2）与标准答案例子不同，但同样能证明算法缺陷（贪心局部最优可能导致全局非最优）。学生例子本身是有效的反例，因此举例部分应得分。但学生表述存在明显笔误（“实际是AB”），可能造成理解歧义，扣1分。此外，学生未像标准答案那样明确指出“不一定能”或“不能”，但结论正确。综合考量，本小题得分为7分（满分10分）。扣分点：表述存在笔误/不严谨，扣1分；论证完整性和清晰度略逊于标准答案，扣2分。
题目总分：7分
1.用两个指针，A指针在前，B指针与A指针间隔为5，A指向最后一个节点时，B指向所需元素
2.(1) A指针出发，向前移动k步
(2) A向前一步，B向前一步
(3) 重复(2)，直到A->next == null
3.
find(node* head){
int cnt = k; //计数器
node* p = head; // p指针
node* q = head; // q指针
// p先出发
while (k--) {
p = p->next;
}
while( p-> next != null ) {
p = p->next; // 同时向后
q = q->next;
}
return q；
}
评分及理由
（1）得分及理由（满分5分）
得分：3分
理由：学生的基本设计思想描述基本正确，提到了使用两个指针并保持间隔k，当A指针到达末尾时，B指针即为所求。这与标准答案的核心思想一致。但是，学生的描述存在不严谨之处：第一句“间隔为5”中的“5”应为“k”，这是一个明显的笔误或概念混淆。此外，描述过于简略，没有明确指出初始时两个指针的位置关系以及移动的触发条件。因此扣2分。
（2）得分及理由（满分5分）
得分：3分
理由：学生的实现步骤基本遵循了双指针法的逻辑，分为“A先移动k步”和“AB同步移动直到A到末尾”两个阶段。步骤框架正确。但是，步骤描述存在严重缺陷：第一步“A指针出发，向前移动k步”没有考虑链表长度可能小于k的情况，如果链表长度小于k，此步骤中p指针会变成空指针（NULL），后续对p->next的访问将导致错误。步骤描述中缺少对边界条件的判断和处理。因此扣2分。
（3）得分及理由（满分5分）
得分：1分
理由：学生的代码实现存在多处逻辑错误和语法问题：
- 函数签名不完整，未定义参数类型和返回值类型。
- 变量`k`未定义，直接使用。
- 第一个`while (k--)`循环在移动指针`p`时，未检查`p`是否已为`NULL`。若链表长度小于k，此循环将导致访问空指针的`next`域，程序崩溃。
- 第二个循环条件`while( p-> next != null )`有误。当`p`移动k步后，应判断`p`本身是否为`NULL`（以确定链表长度是否足够）。此外，循环条件应为`p != NULL`（标准答案）或`p->next != NULL`（会导致q停在倒数第k+1个结点）。此处条件使用`p->next`会导致最终`q`指向倒数第k+1个结点，结果错误。
- 返回值是结点指针`q`，而题目要求成功时返回1并输出data值，失败时返回0。代码完全没有实现题目要求的输出和返回逻辑。
- 代码中使用了未定义的`node`类型，应为题目中定义的`LNode`或`LinkList`。
题目总分：3+3+1=7分
1.中断响应时间：(18+2)*5*/500=0.2us， 每隔4B/0.5M B/s =8us， 占比：0.2/8 = 2.5%
2.间隔时间：5000B/5M B/s = 1ms，DMA：1000*5/500MHZ = 0.01ms，占比：0.01 = 1%
评分及理由
（1）得分及理由（满分4分）
得分：4分
理由：学生作答的思路与标准答案不同，但逻辑正确，计算结果准确。学生通过计算每次中断服务所需时间（0.2us）和中断请求间隔时间（8us），进而计算出时间占比为2.5%，与标准答案一致。思路清晰，计算无误，因此给满分。
（2）得分及理由（满分4分）
得分：2分
理由：学生作答存在逻辑错误和计算错误。
1. 逻辑错误：学生计算“DMA：1000*5/500MHZ = 0.01ms”这一步，其分子“1000*5”的含义不明确，似乎试图用DMA次数乘以某个CPI？这与题目中给出的“DMA预处理和后处理的总开销为500个时钟周期”条件不符。正确的计算应为：总时钟周期数 = DMA次数 * 每次DMA开销 = 1000 * 500 = 500,000个周期。然后除以CPU主频（500MHz，即5e8周期/秒）得到总时间。
2. 计算错误：基于上述错误逻辑，学生得出的DMA处理总时间0.01ms（即1e-5秒）是错误的。正确的总时间应为 500,000 / (500 * 10^6) = 0.001秒 = 1ms。最终CPU时间占比应为 (0.001秒) / (1秒) = 0.1%，但学生得出的占比是1%，计算错误。
3. 部分正确：学生正确计算了DMA传送间隔时间（1ms）和1秒内的DMA次数（1000次），这部分思路正确。但由于核心的计算过程存在上述逻辑与计算错误，导致最终答案错误，因此扣除2分。
题目总分：4+2=6分
评分及理由
（1）得分及理由（满分13分）
学生答案给出了执行阶段 C5 到 C8 四个节拍的功能和控制信号。分析如下：
- C5：功能“MAR←(R1)”和控制信号“R1out, MARin”正确。这步将R1的内容（即内存地址）送入MAR。
- C6：功能“MDR←M(MAR)”和控制信号“MemR, MDRinE”正确。这步根据MAR的地址从内存读取数据到MDR。
- C7：功能“A←(R0)”和控制信号“R0out, Ain”正确。这步将R0中的数据暂存到寄存器A中。
- C8：功能“AC←A + MDR”和控制信号“ADD, ACin”存在逻辑错误。指令要求将R0的数据与从内存读出的数据（现在在MDR中）相加。在C7，R0的数据已存入A；在C6，内存数据已存入MDR。因此，C8的正确操作应该是将A和MDR的内容通过ALU相加，结果存入AC。学生的功能描述“AC←A + MDR”在逻辑上是正确的，但其给出的控制信号“ADD, ACin”不完整，缺少将MDR的内容送上内总线的控制信号“MDRout”。没有这个信号，ALU无法获取MDR中的数据。这是一个关键的控制信号遗漏，属于逻辑错误。
- 缺失步骤：学生的答案缺少将运算结果（在AC中）写回内存的步骤。根据指令功能“结果送入R1的内容所指主存单元中保存”，至少还需要两个节拍：将AC的内容送入MDR，然后将MDR的内容写入内存。学生答案在C8后结束，导致功能未完成。
综合来看，学生答案完成了取操作数和部分运算，但关键的加法操作控制信号不完整，且完全缺失了结果写回的步骤。因此，不能给满分。
参考标准答案，完整的执行阶段需要5或6个节拍。学生答案只提供了4个，且第4个节拍有控制信号遗漏。考虑到其正确完成了前三个节拍，并在C8表达了正确的运算意图（尽管控制信号不全），可以给予部分分数。
扣分点：C8控制信号缺失“MDRout”，扣2分；缺失结果写回内存的完整步骤（通常需2个节拍），扣4分。
得分：13 - 2 - 4 = 7分。
题目总分：7分
Semophore mutex = 1; // 互斥锁
Semophore empty = N; // 空位置
Semophore odd = 0; // 记录奇数个数
Semophore even = 0; // 记录偶数个数
P1{
while(1){
int num = pruduce(); // 生成数据
p(empty); // 检测缓冲区是否有空位置
p(mutex); // 互斥访问
put(num);
v(mutex); // 退出临界区
if(num&1==0) v(even); // 放一个偶数
else v(odd); // 放一个奇数
}
}
P2 {
while(1){
p(odd);// 看是否有奇数
p(mutex); //进入临界区
getodd();
counterodd();
v(mutex); // 推出临界区
v(empty); // 释放一个空间
}
}
P3 {
while(1){
p(even); // 看是否有偶数
p(mutex); // 进入临界区
geteven();
countereven();
v(mutex); // 退出临界区
v(empty); // 释放一个空间
}
}
评分及理由
（1）得分及理由（满分7分）
得分：5分
理由：
- 优点：学生答案的整体框架正确。定义了四个必要的信号量（mutex, empty, odd, even），含义与标准答案一致。P1、P2、P3三个进程的同步与互斥逻辑基本正确：P1先检查空位(empty)，再互斥访问缓冲区(mutex)，放入数据后根据奇偶性通知对应消费者(V(odd)或V(even))。P2和P3先等待对应奇偶信号(P(odd)/P(even))，再互斥访问缓冲区，取出数据并统计，最后释放空位(V(empty))。使用了while(1)循环，符合生产者-消费者模型的持续运行特点。
- 扣分点：
- 逻辑错误（-1分）：在P2和P3进程中，将统计操作（counterodd()/countereven()）放在了互斥区（mutex保护）内。根据题目描述，countodd()和counteven()是统计操作，通常不涉及对共享缓冲区的访问，因此没有必要放在互斥区内。将它们放在互斥区内虽然不会导致错误，但会不必要地延长临界区长度，降低并发效率，属于设计上的瑕疵。标准答案中，统计操作是在释放互斥锁之后进行的。
- 逻辑错误（-1分）：学生代码中判断奇偶的语句为
if(num&1==0)。在C/C++运算符优先级中，==的优先级高于&。因此，该表达式实际等价于if(num & (1==0))，即if(num & 0)，结果永远为假。这将导致P1永远只执行V(odd)，而不会执行V(even)，使得P3进程永远无法被唤醒。这是一个严重的逻辑错误。正确的写法应为if((num & 1) == 0)或直接使用if(num % 2 == 0)。
- 其他：信号量拼写有误（Semophore应为Semaphore），变量名有拼写错误（pruduce应为produce），但不影响核心逻辑理解，不扣分。学生答案与标准答案在代码结构上略有不同（如循环位置、统计函数调用位置），但只要逻辑正确，不扣分。
题目总分：5分
1.访问2362H，页面大小4KB，2362/0xFFF=2，则访问2号页面，有效位为1，访问254362H，其中TLB未命中，需要两次内存访问，一次TLB访问，共210ns，并记入TLB
访问1565H，页面大小4KB，15655/0xFFF=1，缺页，共需两次TLB访问，一次缺页中断处理，一次内存访问，共100000210ns
访问25A5H，页面大小4KB，25A5/0xFFF=2，TLB命中，只需一次内存访问，一次TLB访问，共110ns
2.101565H,程序只有两个页框，根据LRU算法，2号页面刚被访问过，所以替换0号页面，1565H/0xFFF=1，故为1号页面，实地址等于页框号+页内偏移，即101565H
评分及理由
（1）得分及理由（满分6分）
学生答案对三个虚地址的访问时间计算基本正确，思路与标准答案一致。
- 对于2362H：学生正确得出页号为2，有效位为1，并计算了访问时间210ns（10ns TLB + 100ns 页表 + 100ns 内存）。虽然表述中“访问254362H”和“需要两次内存访问”的措辞不够严谨（访问页表是一次内存访问，访问数据是另一次内存访问，共两次），但核心计算过程和结果正确。得2分。
- 对于1565H：学生正确得出页号为1，发生缺页，并计算了访问时间100000210ns。其计算过程（两次TLB访问、一次缺页处理、一次内存访问）与标准答案（10+100+10^8+10+100）的逻辑一致，结果正确。得2分。
- 对于25A5H：学生正确得出页号为2，TLB命中，并计算了访问时间110ns（10ns TLB + 100ns 内存）。得2分。
本小题共得6分。
（2）得分及理由（满分2分）
学生正确给出了虚地址1565H的物理地址为101565H，并说明了理由：驻留集大小为2，根据LRU算法，淘汰0号页面，将1号页面装入原0号页的页框（101H），从而合成物理地址。理由充分，结论正确。
本小题得2分。
题目总分：6+2=8分
\begin{array}{|c|c|c|c|}
\hline
\texttt{目的网络IP地址} & \texttt{子网掩码} & \texttt{下一跳IP地址} & \texttt{接口} \\
\hline
\end{array}
\]
1.不少于120个，故至少需要7位主机号，原子网号为24位，故只能有最高位1位网络号，即A：202.118.1.128/25，B：202.118.1.0/25
2. 目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.128 /25 直接交付 E1
202.118.1.0 /25 直接交付 E2
202.118.2.1 /32 202.118.2.2 L0
130.118.2.2 /32 202.118.2.2 L0
3. 目的网络IP地址 子网掩码 下一跳IP地址 接口
202.118.1.0 /24 202.118.2.1 L0
评分及理由
（1）得分及理由（满分3分）
学生答案正确地将202.118.1.0/24划分为两个/25子网，并说明了需要7位主机号（2^7-2=126≥120），划分结果正确（202.118.1.0/25和202.118.1.128/25）。虽然子网分配顺序与标准答案可能不同，但题目允许两种分配方案，且学生明确写出了A和B，思路和结果均正确。因此得3分。
（2）得分及理由（满分4分）
学生答案存在多处错误：
1. 路由表格式中“下一跳IP地址”一栏，对于直连网络应留空或写“—”，学生写“直接交付”虽可理解但不够规范，此处不扣分。
2. 到域名服务器的主机路由错误：目的网络IP地址应为域名服务器的地址202.118.3.2，学生写成了202.118.2.1（这是R1自己的L0接口地址）和130.118.2.2（此地址在题目中未出现，疑似笔误）。这是一个严重的逻辑错误，导致该路由项无效。
3. 到互联网的默认路由缺失。学生没有给出目的网络为0.0.0.0、子网掩码为0.0.0.0的默认路由。
由于第2、3点错误，该部分答案只能得到部分分数。考虑到学生正确给出了两个局域网的路由（2分），但域名服务器路由完全错误且缺少默认路由，扣2分。因此得2分。
（3）得分及理由（满分2分）
学生正确使用了路由聚合技术，将202.118.1.0/25和202.118.1.128/25聚合为202.118.1.0/24，并正确指定下一跳为202.118.2.1，接口为L0。答案与标准答案一致。因此得2分。
题目总分：3+2+2=7分
The road of your choice, you have to go on !
粤ICP备16082171号-1
