科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
A. h，c，a，b，d，e，g，f
B. e，a，f，g，b，h，c，d
C. d，b，c，a，h，e，f，g
D. a，b，c，d，h，e，f，g
下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）
A. c 和 e
B. d 和 e
C. f 和 d
D. f 和 h
某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB（快表）采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H进行虚实地址变换的结果是（ ）。
A. 0153180H
B. 0035180H
C. TLB缺失
D. 缺页
。计算机按字节编址，页面大小为4KB= 2^12 B，页内地址占低12位，虚拟地址空间大小为4GB= 2^32 B，虚页号占高32-12=20位。
，查找TLB中03FFFH对应的页表项，有效位为1，页框号为0153H，物理地址为 
。
。设系统缓冲区和用户工作区均采用单缓冲，从外设读入 1 个数据块到系统缓冲区的时间为 100，从系统缓冲区读入 1 个数据块到用户工作区的时间为 5，对用户工作区中的 1 个数据块进行分析的时间为 90（如下图所示）。
进程从外设读入并分析 2 个数据块的最短时间是（ ）。
A. 200
B. 295
C. 300
D. 390
某系统正在执行三个进程 P1、P2 和 P3，各进程的计算 (CPU) 时间和 I/O 时间比例如下表所示。
为提高系统资源利用率，合理的进程优先级设置应为（ ）。
A. P1>P2>P3
B. P3>P2>P1
C. P2>P1=P3
D. P1>P2=P3
若下图为 10 BaseT 网卡接收到的信号波形，则该网卡收到的比特串是（ ）。
A. 0011 0110
B. 1010 1101
C. 0101 0010
D. 1100 0101
评分及理由
（1）得分及理由（满分4分）
得2分。学生的基本设计思想是使用一个辅助数组记录每个元素出现的次数，然后遍历该数组找到出现次数超过n/2的元素。这种方法虽然正确，但不符合题目要求的"尽可能高效"（题目期望的时间复杂度O(n)，空间复杂度O(1)的算法）。学生的方案空间复杂度为O(n)，不是最优解，因此扣2分。
（2）得分及理由（满分7分）
得4分。学生的代码实现逻辑正确，能够正确统计每个元素的出现次数并找出主元素。但存在以下问题：
1. 使用了O(n)的额外空间，不符合最优解要求（扣2分）
2. 代码中假设了元素值都在0到n-1范围内，虽然题目确实给出了这个条件，但标准答案的方法更具通用性（扣1分）
代码核心逻辑正确，能够完成主元素的查找功能。
（3）得分及理由（满分2分）
得1分。学生正确分析了时间复杂度为O(n)，但空间复杂度分析为O(n)而不是最优的O(1)，因此扣1分。
题目总分：2+4+1=7分
评分及理由
（1）得分及理由（满分5分）
学生答案中，元素排列方式正确（按查找概率从大到小排列），查找方法正确（顺序查找），这两点符合标准答案要求，应得3分。但在计算平均查找长度时，公式写错（分母不应有总和概率，因为概率总和为1），且计算结果错误（1.95），而正确结果应为2.1。由于计算过程有误，扣2分。因此，本小题得3分。
（2）得分及理由（满分5分）
学生答案中，元素排列方式正确（按查找概率从大到小排列），查找方法正确（顺序查找），这两点符合标准答案中的答案一要求，应得3分。但在计算平均查找长度时，同样公式写错且计算结果错误（1.95），而正确结果应为2.1。由于计算过程有误，扣2分。因此，本小题得3分。
题目总分：3+3=6分
评分及理由
（1）得分及理由（满分3分）
CPU时钟周期计算正确（1.25ns，学生答案中0.00125μs=1.25ns），得1分；总线时钟周期计算正确（5ns，学生答案中0.005μs=5ns），得1分；总线带宽计算错误（学生计算为8×10⁸ B/s，标准答案为800 MB/s，学生计算过程有误），扣1分。本小题得2分。
（2）得分及理由（满分1分）
正确判断需要一个读突发传送总线事务，得1分。
（3）得分及理由（满分2分）
学生计算总时间为50ns，但标准答案为85ns。学生未考虑8体交叉存储的并行特性以及数据传输需要8个总线时钟周期，计算过程不完整，扣2分。本小题得0分。
（4）得分及理由（满分3分）
学生计算过程混乱，未正确区分Cache命中和缺失的情况，计算出的715ns与标准答案1010ns相差较大。命中时的指令执行时间计算错误（学生计算为5ns，应为500ns），缺失开销计算错误，扣3分。本小题得0分。
题目总分：2+1+0+0=3分
（14分）某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位/借位标志CF、零标志ZF和符号标志NF。假定为该机设计了条件转移指令，其格式如下：
其中，00000为操作码OP；C、Z和N分别为CF、ZF和NF的对应检测位，某检测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，若C=1，Z=0，N=1，则需检测CF和NF的值，当CF=1或NF=1时发生转移；OFFSET是相对偏移量，用补码表示。转移执行时，转移目标地址为(PC)+2+2×OFFSET；顺序执行时，下条指令地址为(PC)+2。请回答下列问题。
(1) 该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？（3分）
(2) 某条件转移指令的地址为200CH，指令内容如下图所示，若该执行时CF=0，ZF=0，NF=1，则该指令执行后PC的值是多少？若该指令执行时CF=1，ZF=0，NF=0，则该指令执行后PC的值又是多少？请给出计算过程。（5分）
(3) 实现“无符号数比较小于等时转移”功能的指令中，C、Z和N应各是什么？（3分）
(4) 以下是该指令对应的数据通路示意图，要求给出中部件①~③的名称或功能说明。（3分）
评分及理由
（1）得分及理由（满分3分）
学生答案中正确指出存储器按字节编址（因为指令字长16位=2B，顺序执行时PC+2），得1分。但关于向后跳转最多可跳转的指令数，学生回答"128条指令"有误，因为OFFSET范围-128~127，向后跳转对应正偏移量，最多127条指令。此处逻辑错误扣1分。因此本小题得2分。
（2）得分及理由（满分5分）
学生正确分析了两种情况：第一种情况（CF=0,ZF=0,NF=1）正确判断需要转移，并正确计算出PC=1FD4H；第二种情况（CF=1,ZF=0,NF=0）正确判断不需要转移，PC=200EH。计算过程完整正确。虽然学生将OFFSET直接写为-29而不是通过补码分析，但最终计算结果正确，不扣分。本小题得5分。
（3）得分及理由（满分3分）
学生回答"C=1,ZF=1,NF=0"完全正确，与标准答案一致。对于无符号数比较小于等于时转移，需要检测CF（借位）和ZF（相等），即C=1,Z=1,N=0。本小题得3分。
（4）得分及理由（满分3分）
学生回答：①程序状态寄存器（保存标志位）基本正确；②指令寄存器正确；③MAR（地址寄存器）错误，应该是加法器。标准答案中③是加法器（用于地址相加）。此处逻辑错误扣1分。本小题得2分。
题目总分：2+5+3+2=12分
评分及理由
（1）信号量定义及初值（满分4分）
得分：4分
理由：学生定义了三个信号量：mutex=1（用于出入口互斥）、empty=500（博物馆剩余容量）、full=0（博物馆当前人数）。其中mutex和empty的定义与标准答案一致，含义和初值正确各得2分。虽然多定义了full信号量，但这是额外的正确思路，根据评分要求不扣分也不加分。
（2）对mutex的P、V操作（满分2分）
得分：2分
理由：在进门和出门操作前后正确使用了P(mutex)和V(mutex)操作，实现了出入口的互斥访问，与标准答案完全一致。
（3）对empty的P、V操作（满分1分）
得分：0分
理由：学生使用了empty和full两个信号量来控制人数，虽然逻辑上是正确的，但在进门后使用了V(full)，在出门前使用了P(full)，这与标准答案只使用empty信号量的方案不同。根据评分要求，虽然思路正确不扣分，但题目明确要求使用必要的信号量，且标准答案中只使用empty，学生的方案虽然功能正确但使用了多余的信号量，因此对empty的P、V操作部分不能给分。
题目总分：4+2+0=6分
（8分）某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。
(1) 若使用一级页表的分页存储管理方式，逻辑地址结构为：
\[
\begin{array}{|c|c|}
\hline
\texttt{页号（20位）} & \texttt{页内偏移量（12位）} \\
\hline
\end{array}
\]
则页的大小是多少字节？页表最大占用多少字节？（3分）
(2) 若使用二级页表的分页存储管理方式，逻辑地址结构为：
\[
\begin{array}{|c|c|c|}
\hline
\texttt{页目录号（10位）} & \texttt{页表索引（10位）} & \texttt{页内偏移量（12位）} \\
\hline
\end{array}
\]
设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。（2分）
(3) 采用 (1) 中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。（3分）
评分及理由
（1）得分及理由（满分3分）
学生正确计算出页大小为 4KB（得1分）。但在计算页表最大占用时，错误地认为页表最大占用一个页的大小（即 2^12 字节），而正确答案应为 2^20 × 4B = 4MB。这是逻辑错误，扣2分。因此本小题得1分。
（2）得分及理由（满分2分）
学生给出的页目录号表达式 LA/2^22 正确（得1分）。页表索引表达式 LA/2^12 % 2^10 虽然形式与标准答案不同，但通过除法和取模运算正确提取了中间10位，思路正确且结果等价（得1分）。因此本小题得2分。
（3）得分及理由（满分3分）
学生正确识别出代码段占用2个页面（页号8和9），但在计算页表项物理地址时出现错误：
- 页表项物理地址应为 00200000H + 页号×4，学生计算为 00200000H + 页号（漏乘4）
- 因此得到错误地址 00200008H 和 00200009H（扣1分）
- 页框号计算错误（应为00900H和00901H，但学生未正确从页表项获取）（扣1分）
- 代码页面2起始物理地址 00901000H 计算正确（得1分）
因此本小题得1分。
题目总分：1+2+1=4分
（9分）假设 Internet 的两个自治系统构成的网络如题 47 图所示，自治系统 AS1 由路由器 R1 连接两个子网构成；自治系统 AS2 由路由器 R2、R3 互联并连接 3 个子网构成。各子网地址、R2 的接口名、R1 与 R3 的部分接口 IP 地址如题 47 图所示。
请回答下列问题。
(1) 假设路由表结构如下表所示。
\[
\begin{array}{|c|c|c|}
\hline
\texttt{目的网络} & \texttt{下一跳} & \texttt{接口} \\
\hline
\end{array}
\]
请利用路由聚合技术，给出 R2 的路由表，要求包括到达题 47 图中所有子网的路由，且路由表中的路由项尽可能少。（6分）
(2) 若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组，R2 会通过哪个接口转发该 IP 分组？（1分）
(3) R1 与 R2 之间利用哪个路由协议交换路由信息？该路由协议的报文被封装到哪个协议的分组中进行传输？（2分）
评分及理由
（1）得分及理由（满分6分）
学生给出了三个路由项：
① 153.14.5.0/24 → R1 → S0：正确，与标准答案一致，得2分。
② 194.17.20.128/25 → 无 → E0：正确，与标准答案一致，得2分。
③ 194.17.20.0/23 → R3 → S1：正确，与标准答案一致，得2分。
三个路由项均正确，且路由项数量最少，符合路由聚合要求。因此本小题得6分。
（2）得分及理由（满分1分）
学生分析目的IP地址194.17.20.200与194.17.20.0/23匹配，认为应从S1接口转发。但根据最长匹配原则，该IP地址同时匹配194.17.20.0/23（掩码23位）和194.17.20.128/25（掩码25位），应选择更具体的194.17.20.128/25路由项，通过E0接口转发。学生答案逻辑错误，未应用最长匹配原则。因此本小题得0分。
（3）得分及理由（满分2分）
学生未完整回答本题。第一部分"R1与R2之间利用"后面内容缺失，无法判断是否回答了BGP协议；第二部分未回答封装协议。因此本小题得0分。
题目总分：6+0+0=6分
The road of your choice, you have to go on !
粤ICP备16082171号-1
