科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
。
某以太网拓扑及交换机当前转发表如下图所示，主机 00-e1-d5-00-23-a1 向主机 00-e1-d5-00-23-c1 发送 1 个数据帧，主机 00-e1-d5-00-23-c1 收到该帧后，向主机 00-e1-d5-00-23-a1 发送 1 个确认帧，交换机对这两个帧的转发端口分别是（ ）。
A. {3}和{1}
B. {2,3}和{1}
C. {2,3}和{1,2}
D. {1,2,3}和{1}
，传播时延为 50 ms ，主机乙发送一个确认帧的时延为 t2 ，因为乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，所以 t2=0 ，传播时延为 50 ms 。一个周期 T=0.08 ms+50 ms+0 ms+50 ms=100.08 ms 。因为数据链路层采用后退 N 帧协议 (GBN) 传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。甲的发送窗口尺寸为1000，1000个帧的发送时延为 1000t1=80 ms<T ，满足要求。
评分及理由
（1）得分及理由（满分3分）
学生作答内容为空白，未给出任何算法设计思想，因此该小题不得分。
得分：0分
（2）得分及理由（满分4分）
学生作答内容为空白，未给出二叉树结点的数据类型定义，因此该小题不得分。
得分：0分
（3）得分及理由（满分6分）
学生作答内容为空白，未给出算法描述及代码，因此该小题不得分。
得分：0分
题目总分：0+0+0=0分
（10分）某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表的接口名构造出来的网络拓扑。
请回答下列问题。
⑴ 本题中的网络可抽象为数据结构中的哪种结构？（1分）
⑵ 针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据定义，并画出对应题42表的链式存储结构示意图（示意图中仅以ID标识结点）。（5分）
⑶ 按照迪杰斯特拉（Dijkstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。（4分）
评分及理由
（1）得分及理由（满分1分）
学生答案为“图结构”，未明确写出“无向图”或“网状结构”，但结合上下文和图示，本质含义符合标准答案中“可以抽象为无向图”的描述。根据评分标准，若给出“与图含义相似的描述”即可得满分。学生的答案过于简化（仅“图结构”），未完全表达题意，但属于识别或表述简略，未造成实质错误，判断为学生有正确的思路但表述不完整。为严格起见，扣0.5分。最终得分0.5分。
（2）得分及理由（满分5分）
学生设计了两类链式结构：Link（用于路由器间链路）和Net（用于网络），并在LSI结构体中用两个指针L和N分别指向这两类链表，表头存储在Table数组中（Router为路由器地址）。这种设计属于标准答案中“将网络抽象为一类结点，写出含8个表头结点的链式存储结构”的变体，也符合“两种不同的结构分别表示Link和Net，同时在表头结点中定义了多个指针，分别指向两种类型的结点构成的两个链表”的评分说明。但设计存在以下不足：①Link和Net结构体中均缺失关键字段，如Link中无目的路由器IP（仅有ID，但不含IP信息），Net中无掩码（Mask）；②未给出具体的链式存储结构示意图，也没有详细展示如何表示题目中的LSI表内容；③结构体定义不完整且存在逻辑问题（如两个结构体互相包含对方的next指针，但没有清晰区分）。综合来看，数据类型定义部分能体现学生理解需要用链式保存链路和网络信息，但实现细节错误较多，且未按要求画出示意图。结合标准答案评分说明，数据类型定义（3分）学生可得到1分（思路正确但细节严重不完整），示意图（2分）为0分。故本小题得1分。
（3）得分及理由（满分4分）
学生正确列出了从R1到达4个子网的最短路径及费用：192.1.1.0/24（1）、192.1.5.0/24（3）、192.1.6.0/24（4）、192.1.7.0/24（8），并标注了路径经过的路由器（R1→…）。具体路径与标准答案一致，且费用正确。标准答案的步骤顺序为192.1.1.0、192.1.5.0、192.1.6.0、192.1.7.0，学生给出的顺序与此相同，满足“符合代价不减的次序”。但学生未像标准答案那样明确给出“路径”与“代价”的对应表格结构，实际上已列出完整信息，核心内容正确。因此给满分4分。
题目总分：0.5+1+4=5.5分
评分及理由
（1）得分及理由（满分6分）
学生给出了3条以下路由项，但存在严重问题。标准答案要求3条路由项：
① 192.1.1.0/24 → E0（学生答对）；
② 192.1.6.0/23 → L0（学生写成192.1.0.0/21且下一跳写成了192.1.6.0/24，目的网络聚合错误，下一跳也不正确）；
③ 192.1.5.0/24 → L1（学生完全遗漏）。
因此仅第一条正确，最多给2分。
（2）得分及理由（满分2分）
学生回答通过L0接口转发，正确得1分；但TTL回答“62”，标准答案为61（经过R1、R2、R4共3个路由器，64-3=61）。学生可能将“减3”误算为“减2”，此处属于逻辑错误，扣1分。
（3）得分及理由（满分1分）
学生回答增加Prefix 0.0.0.0/0 和 Metric 10，与标准答案一致，得1分。
题目总分：2+1+1=4分
（12分）某程序中有如下循环代码段P：“for (int i=0; i＜N; i++) sum += A[i];”。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为08048100H，对应的汇编代码和机器代码如下表所示。
执行上述代码的计算机 M 采用 32 位定长指令字，其中分支指令 bne 采用如下格式：
Op为操作码，Rs和Rd为寄存器编号，OFFSET为偏移量，用补码表示。请回答下列问题，并说明理由。
(1) M的存储器编址单位是什么？（2分）
(2) 已知sll指令实现左移功能，数组A中每个元素占多少位？（2分）
(3) 题44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne指令内容，推断出bne指令的转移目标地址计算公式。（3分）
(4) 若M采用如下“按序发射、按序完成”的5级指令流水线：IF（取指）、ID（译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件不采取任何转发措施，分支指令的执行均引起3个时钟周期阻塞，则P中那些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？（5分）
评分及理由
（1）得分及理由（满分2分）
回答“M地址单位为B”，即按字节编址，与标准答案完全一致。理由正确，得2分。
（2）得分及理由（满分2分）
回答“每个元素应占2B即16位”错误。根据标准答案，指令中sll左移两位（即乘以4），且按字节编址，数组元素地址间隔应为4个地址单位，故每个元素占4B（32位）。学生答2B属于计算错误，逻辑错误。由于该错误并非识别误写（两个“2B”均一致），应扣2分，本题得0分。
（3）得分及理由（满分3分）
学生正确识别OFFSET字段为FFFAH（即-6），并给出了计算公式“(PC)+4+OFFSET*4”，与标准答案完全一致。虽未详细推导，但核心答案正确，给3分。
（4）得分及理由（满分5分）
标准答案指出因数据相关发生阻塞的指令为第2、3、4、6条，第6条发生控制冒险，且第5条与下轮第1条无数据相关是因为第6条阻塞了3个周期。学生回答“1,2,3,4数据相关”错误，错误将指令1也计算在内，且漏掉了指令6的数据相关；同时“第6条控制冒险”正确，但解释部分错误地将无数据相关的原因归因于“第6条阻塞期间R2值已写入”，而标准答案指的是下一轮第1条与当前第5条之间的数据相关，并非R2。核心错误较多，不能得满分。数据相关部分（标准答案给3分）完全错误，控制冒险（1分）正确，无数据相关的原因解释错误（标准答案给1分，此处不得分）。故本题得1分。
题目总分：2+0+3+1=6分
评分及理由
（1）得分及理由（满分1分）
学生作答：两次识别均为“1000”，与标准答案一致，理由正确。得1分。
（2）得分及理由（满分3分）
第一小问：学生计算“32B × 16 = 512B”，正确，得1分。
第二小问：标准答案为指令Cache命中率约为99.98%（1000次循环共6000次取指，仅第一次缺失，命中5999次）。学生给出命中率5/6，显然错误——可能是将6条指令的第一次循环当作仅1次缺失来计算，却未考虑1000次循环。该错误属于逻辑性计算错误，非识别误写。此小问满分2分，得0分。
本小题合计得1分。
（3）得分及理由（满分7分）
溢出异常判断：学生答“第4条可能溢出”，正确，得2分。
缺页异常判断：学生答“第3条缺页异常”，正确，得1分。
读磁盘次数：学生答“至少1次”，正确，得2分。
读TLB次数：标准答案为至少1001次（访问A[0]时先查TLB产生缺页，缺页处理后重新执行该指令再查一次，之后999次各查一次，共1001次）。第一次识别为1001次，正确，得2分；第二次识别为1000次，但两次识别存在歧义，按规则只要有一次正确即给分。故本小点得2分。
本小题合计：2+1+2+2=7分。
题目总分：1+1+7=9分
评分及理由
（1）得分及理由（满分3分）
学生回答：“将1-29块前移，然后写入第30块，29块每块需读1次，写1次，最后再写1次，共59次；起始块号减1；块数加1。”
第1问（访盘次数）：学生指出需移动前29条记录，每次移动需1次读和1次写，共58次，再加上写入新记录的1次写，总计59次，与标准答案完全一致，逻辑正确且计算准确。
第2问（FCB变化）：学生回答“起始块号减1；块数加1”，标准答案为“起始块号和文件长度会发生改变”。学生的“块数加1”等价于文件长度加1，“起始块号减1”与标准答案“起始块号改变”一致，核心逻辑正确，只是用词略有不同，不影响得分。
因此，本题得3分。
（2）得分及理由（满分4分）
学生回答：“至少要从头读至29块，修改第29块链接指针，再写入至指向块，读29次，写2次，共31次；4字节链接指针可表示最大为232-1，故该文件系统设块号从0开始，最多232块，即232×1KB=4GB。”
第1问（访盘次数）：学生计算读29次（找到第29块），写2次（一次写新块，一次写修改后的第29块），共31次，与标准答案完全一致，逻辑清晰，计算正确。
第2问（文件最大长度）：标准答案为4G×1020B=4080GB，并注明若按1024×232B=4096GB计算给1分。学生计算为232×1KB=4GB，此计算忽略了每个块中4B链接指针所占用的空间，数据部分应为1020B而非1KB，导致结果错误。按照评分说明，此类错误应给1分。
因此，本题中访盘次数部分（2分）正确，文件最大长度部分（2分）只给1分，共计3分。
题目总分：3+3=6分
评分及理由
（1）信号量含义和初值（满分2分）
学生定义了 `empty=1000`、`full=0`、`mutex=1`、`mutex_1=1`。empty表示空缓冲区数（初值1000正确），full表示产品数（初值0正确），mutex用于缓冲区互斥访问（初值1正确），mutex_1用于控制消费者连续取产品（初值1正确，但注释“确保每次取1件”表述不准确，不影响核心含义）。四个信号量的含义和初值均正确，得2分。
（2）生产者进程同步与互斥（满分3分）
生产者进程：`P(empty)`申请空位，`P(mutex)`互斥访问缓冲区，放入产品后`V(mutex)`释放互斥，`V(full)`增加产品数。生产者与消费者的同步（empty/full），生产者之间的互斥（mutex）均正确，得3分。
（3）消费者进程连续取10件产品的控制逻辑（满分2分）
消费者进程：先`P(mutex_1)`再进入for循环取产品，但for循环条件为`i<0`（两次识别均如此），导致循环体一次都不会执行，无法实现“连续取10件产品”的要求。逻辑错误：循环次数应为10次（如`i<10`），此处为明显的编码错误而非手写误写（误写通常不会将10写成0，且两次识别均一致）。此外，消费者取产品时`P(full)`、`P(mutex)`、`V(mutex)`、`V(empty)`的同步互斥操作正确，但循环结构错误使整体功能失效。因此控制消费者连续取产品数量不正确，扣2分，得0分。
（4）消费者之间互斥操作（满分1分）
消费者通过`mutex_1`实现同一时刻仅一个消费者进入连续取产品周期（`P(mutex_1)`和`V(mutex_1)`），消费者之间的互斥逻辑正确。但由于循环条件错误导致功能无法执行，该部分逻辑上的“互斥”结构仍正确，判定部分有效得1分。综合判定本项得1分。
（5）题目总分：2+3+0+1=6分
The road of your choice, you have to go on !
粤ICP备16082171号-1
