科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
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分）
该学生的算法设计思想是构造一个计数数组来统计每个元素出现的次数，然后遍历计数数组寻找出现次数大于 n/2 的元素。这一思路完全正确，能够正确找出主元素。虽然与标准答案的摩尔投票法不同，但属于另一种正确且更直观的解题方法，思路描述清晰完整，没有逻辑错误，因此给4分。
（2）得分及理由（满分7分）
代码逻辑正确：初始化计数数组、统计每个元素的出现次数、遍历计数数组判断是否有元素出现次数大于 n/2，并正确返回结果。代码包含必要注释，关键步骤解释清楚，符合题目要求。由于计数数组大小为 n+1，而题目保证了 a_i < n，因此不会出现数组越界问题。代码完整实现了其设计思想，无逻辑错误，因此给7分。
（3）得分及理由（满分2分）
学生给出的时间复杂度为 O(n)（三次遍历均为线性），空间复杂度为 O(n)（使用了大小为 n+1 的辅助数组），与其算法实现完全一致，因此给2分。
题目总分：4+7+2=13分
评分及理由
（1）得分及理由（满分5分）
学生作答：排列为{“do”, “while”, “for”, “repeat”}（顺序查找）——这实际上是按查找概率降序（0.35, 0.35, 0.15, 0.15）排列；使用顺序查找方法；计算ASL=0.35×1+0.35×2+0.15×3+0.15×4=2.1。与标准答案完全一致，方法、排列和计算均正确，应得满分5分。
（2）得分及理由（满分5分）
学生作答部分一：仍按该排列顺序查找，ASL=2.1。此题的标准答案允许两种方法——“链式顺序查找”或“二叉排序树”，但学生把顺序存储时已用过的排列直接用于链式顺序查找，实际上是重复了第（1）问的方案，且未明确说明“链式存储+顺序查找”可达到2.1，该方案本身在链式存储下是可行且正确的（与答案一相符），故这部分的思路和计算均正确。部分二：构造二叉排序树，树为根do，do左孩子for，for左孩子repeat，do右孩子while。该树对应的查找次数：do为1次，while为2次，for为2次，repeat为3次，因此ASL计算应为0.35×1+0.35×2+0.15×2+0.15×3=1.8，学生的计算式书写为“1×0.35+2×0.35+2×0.15+3×0.15”，结果应为2.0（因顺序不同但结果应为0.35+0.7+0.3+0.45=1.8），但学生给出的结果是1.80，经计算发现其算式结果实为1.8，但书写顺序标注的3次和2次与树结构对应有误（for应为2次、repeat应为3次，但算式将2×0.35写为2×0.35（while）且把2×0.15写成for的2次，3×0.15写成repeat的3次，实际计算结果0.35+0.7+0.3+0.45=1.8，数值正确），但该排列下计算的ASL=1.8并不小于链式顺序查找2.1，但标准答案要求的是“更短”的查找方法，学生给出了两种方案，前者为2.1（合法但并非最优，题目只要求能更短即可，而2.1与题目给定的折半查找2.2相比已更短，因此只要提供正确方案即可，但学生第（2）问只需提供一种满足“更短”的方法，但顺序查找ASL为2.1，虽比2.2短但非最优，标准答案还要求“用更高效方法且正确”才给分，学生提供了二叉排序树法且ASL=1.8是优于2.1的，但该树的构建和计算存在问题——树结构ASL应为1.8但学生以排序顺序计算，需验证树的正确性：学生所写的树（根do，for为do左孩子，repeat为for左孩子，while为do右孩子）则各元素查找次数为do 1次，for 2次，repeat 3次，while 2次，ASL=0.35×1+0.15×2+0.15×3+0.35×2=0.35+0.3+0.45+0.7=1.8，学生算式“1×0.35+2×0.35+2×0.15+3×0.15”中的权重对应不匹配（do 1次、while 2次、for 2次、repeat 3次，但学生排列为“repeat, for, do, while”顺序），导致算式对应的排列与树不一致，但最终结果1.8仍是正确的（因为乘法交换律下数值一致），总体核心逻辑正确，可以认为该部分构造合理且ASL计算值正确。由于第（2）问只需一个正确方案即可，学生已给出合理方案，两个方案都正确则只按一个给分（评分要求禁止重复给分），故第（2）问可得5分。
题目总分：5+5=10分
评分及理由
（1）得分及理由（满分3分）
学生正确计算了CPU时钟周期为1.25ns（1分）、总线时钟周期为5ns（1分），总线带宽计算为800MB/s（1分）。三项均与标准答案一致，故得3分。
（2）得分及理由（满分1分）
学生正确判断Cache块大小为32B，一次突发传送总线事务可读取32B，因此只需1次读突发传送总线事务，得1分。尽管学生提到“需读8次数据”和“3个总线时钟”等额外描述，但这些并非题目所问，且不影响核心正确答案，不构成逻辑错误，也不额外扣分。
（3）得分及理由（满分2分）
学生计算总线事务时间为90ns，而标准答案为85ns，计算错误。分析过程：学生将地址传送时间3个总线时钟（15ns）加上存储器准备数据时间75ns（40ns + 7×5ns）得到90ns。但标准答案认为地址传送只需1个总线时钟周期（5ns），且读突发过程中数据传送与存储器准备重叠适当计算，总时间为5ns（地址）+40ns（第一个体准备）+8×5ns（数据传送）=85ns。学生的额外逻辑（3个时钟传送地址）不正确，但能够识别突发传送与存储器准备的重叠特点，有一定思路，不过最终时间不正确。因此此小题扣1分，得1分。
（4）得分及理由（满分3分）
学生计算命中时指令执行时间正确：100条指令×CPI=4×1.25ns=500ns（1分）。计算缺失开销时使用缺失每次90ns（但错误值），访存总次数120次、缺失率5%得到6次缺失，缺失开销为6×90=540ns，总时间为500+540=1040ns? 但学生写720ns，实际上是6×90再额外按某种计算得720ns（可能误写），且最终总时间1220ns与标准答案1010ns不符，主要原因是第(3)小题的缺失损失90ns错误。但学生整体公式正确（指令执行时间+缺失开销），应考虑其思路正确但结果因前面错误连带错误，故此处只给1分（命中部分正确得1分，缺失部分计算过程因缺失损失错误而结果错误，但缺失次数计算正确可酌情给1分，总时间计算形式正确可再给1分？综合考虑，因缺失损失错误导致最终结果不正确，且缺失开销计算有误，故给1分，总共得1分）。
题目总分：3+1+1+1=6分
（注：第(3)题学生逻辑有误，第(4)题因第(3)题连带的计算错误，故总得分为6分。）
（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分）
按字节编址判断正确，得1分。但“反向offset共9位”属于误写（实际应为8位补码），且“9位补码最大可表示2^7”表述含混，未明确给出“最多可跳转127条指令”或“−128~127”这一关键取值范围，故第二问不得分。共得1分。
（2）得分及理由（满分5分）
第一问判断转移正确（NF=1且N=1需转移），得1分；但转移目标地址计算完全错误（将OFFSET误认为8位后的处理、左移与加法结果均不正确），未给出正确PC值，故其余2分不得分。第二问不转移判断正确，得1分，且PC=200EH计算正确，得1分。共得2分。
（3）得分及理由（满分3分）
正确答案为C=1，Z=1，N=0。学生作答“C=1，Z=1，N=0”完全正确，得3分。
（4）得分及理由（满分3分）
①指令寄存器（IR）正确，得1分；②移位寄存器正确，得1分；③加法器/ALU正确，得1分。共得3分。
题目总分：1+2+3+3=9分
评分及理由
（1）信号量定义及初始化（满分4分）
学生定义了两个信号量：condition = 500（表示博物馆容量）和mutex = 1（互斥信号量）。condition初值500与标准答案中的empty = 500作用相同（均表示可用容量，通过P/V控制可进入人数），初值正确；mutex = 1初值正确。对于含义说明，学生注明“容量”“互斥信号量”，虽然表述简洁，但明确表达了两个信号量的用途，符合题意要求。根据标准答案评分说明第①条，“信号量初值给1分，说明含义给1分，两个信号量的初值和含义共4分”，因此本项得4分。
（2）互斥信号量mutex的P、V操作（满分2分）
学生在进门前后分别执行P(mutex)和V(mutex)，在出门前后分别执行P(mutex)和V(mutex)，正确实现了出入口的互斥，与标准答案一致。本项满分2分。
（3）容量信号量的P、V操作（满分1分）
学生在进门之前执行P(condition)，出门之后执行V(condition)，正确实现了对参观人数的控制，与标准答案的P(empty)和V(empty)逻辑相同。本项满分1分。
题目总分：4+2+1=7分
（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分）
第1小问中，页大小计算正确（\(2^{12}\)B = 4KB，1分），页表项数计算正确（\(2^{20}\)项，1分），页表最大占用空间计算正确（\(2^{22}\)B = 4MB，1分），共得3分。
（2）得分及理由（满分2分）
学生给出页目录号\( = LA \gg 22\)，页表索引\( = LA \gg 12 \mod 2^{10}\)。页目录号表达式正确（1分），页表索引表达式正确（1分），共得2分。
（3）得分及理由（满分3分）
1. 第一个页表项物理地址：页表起始地址0020 0000H + 8×4 = 0020 0020H，计算正确（得分0.5分）。
2. 第二个页表项物理地址：0020 0024H，计算正确（得分0.5分）。
3. 页框号1：学生写为00900，实际物理地址0090 0000H对应的页框号应为00900H，但页框号通常以16进制表示。学生未写H，且第1次识别写为00900（疑似笔误），第2次识别仍写为00900，未标注H。但通过上下文可知，其意图为00900H，且根据评分标准，若判断为误写，可不扣分。因此页框号1正确（得分0.5分）。
4. 页框号2：00901H（下一页，即00900H+1），学生写为00901（未加H），同上判断为误写，页框号2正确（得分0.5分）。
5. 代码页面2的起始物理地址：学生未明确给出。该地址应为0090 1000H（因为第二个页面起始物理地址 = 0090 0000H + 4KB = 0090 1000H）。学生未写出，但根据其页框号2为00901H，可推出物理地址为0090 1000H，但学生未作答此项，因此扣1分。
综上所述，第（3）小问获得2分。
题目总分：3+2+2=7分
（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分）
学生给出的路由表包含三条路由项，但存在明显错误：第一条目的网络“154.14.5.728/25”地址错误（正确应为153.14.5.0/24聚合路由），且该路由未体现AS1内两个/25子网的聚合；第三条“194.17.20.0/22”错误，该前缀包含AS2中所有子网，但路由表中同时包含了单独的子网194.17.20.128/25，这时长前缀掩码/22与更短前缀/25同时存在，会引发歧义且路由项并非最少；标准答案应给出：153.14.5.0/24、194.17.20.0/23（不含.128/25）、194.17.20.128/25三条路由。学生仅第二条路由（194.17.20.128/25）完全正确。第三条路由目的网络错误（应为194.17.20.0/23，而非/22），且缺少第一条正确路由（153.14.5.0/24）。虽然第一条地址存在笔误，但“154”与“153”易混淆，可视为误写，不过即便将“154”视为“153”，“.5.728/25”仍不符合有效IPv4地址，核心逻辑错误，不能给分。因此，仅准确给出1条路由项，根据评分标准，每条正确路由项给2分，此小题共给2分。
（2）得分及理由（满分1分）
标准答案为根据最长匹配原则，R2将通过E0接口转发目的地址194.17.20.200的分组。学生回答“E0”，并解释说明为E0（若为E6笔误），回答正确，给1分。
（3）得分及理由（满分2分）
R1与R2之间属于不同自治系统，应使用BGP（或BGP4）交换路由信息，且BGP报文封装在TCP协议中传输。学生回答“BGP、TCP协议的传输层报文”，正确，给2分。
题目总分：2+1+2=5分
The road of your choice, you have to go on !
粤ICP备16082171号-1
