科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
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。这种方法虽然正确，但空间复杂度为O(n)，而题目要求"尽可能高效的算法"，标准答案给出了空间复杂度O(1)的更优解法。不过题目并未明确要求空间复杂度必须为O(1)，且学生的思路是正确可行的。根据评分说明"算法的基本设计思想描述或算法实现中部分正确，根据算法复杂度酌情给分"，此处扣1分，得3分。
（2）得分及理由（满分7分）
学生代码实现基本正确，但存在以下问题：
1. 代码中max变量在比较时没有更新，应在if(count[i]>max)后添加max = count[i];，这是一个逻辑错误，扣2分。
2. 数组初始化int count[n] = 0;在C/C++中语法不正确，应为int count[n] = {0};，但考虑到可能是识别错误，不扣分。
3. 代码逻辑清晰，注释恰当，基本实现了算法思想。
综合扣2分，得5分。
（3）得分及理由（满分2分）
学生正确分析了算法的时间复杂度O(n)和空间复杂度O(n)，与实现的算法一致，得2分。
题目总分：3+5+2=10分
评分及理由
（1）得分及理由（满分5分）
学生回答中提出了按概率降序排列（P_A≥P_B≥P_C≥P_D）的思路，这与标准答案一致，得2分。但学生错误地选择了折半查找法，并给出了错误的排列("for","do","while","repeat")和错误计算的平均查找长度1.8。正确的查找方法应为顺序查找，平均查找长度应为2.1。由于逻辑错误（选择错误查找方法），扣2分。计算错误扣1分。最终得分为：2（排列正确）- 2（查找方法错误）- 1（计算错误）= 0分。
（2）得分及理由（满分5分）
学生回答中提出了按概率降序排列（P_A≥P_B≥P_C≥P_D）的思路，并正确选择了顺序查找方法，得3分。平均查找长度计算正确为2.1，得2分。最终得分为：3（排列和查找方法正确）+ 2（计算正确）= 5分。
题目总分：0+5=5分
评分及理由
（1）得分及理由（满分3分）
学生答案中给出了CPU主频800MHz和总线时钟频率200MHz，但未明确写出时钟周期计算过程。第一次识别结果中给出了CPU时钟周期=1/800MHz，总线时钟周期=1/200MHz，带宽=800MB/s，这些都与标准答案一致。第二次识别结果虽然只写了频率值，但根据上下文判断可能是识别问题。因此给3分。
（2）得分及理由（满分1分）
学生两次识别结果都回答"8次"，但标准答案为1次。因为Cache块大小为32字节，而每次突发传送32字节，所以只需要1次总线事务。这个逻辑错误明显，扣1分。
（3）得分及理由（满分2分）
学生第一次识别结果为50ns，第二次识别结果为10ns 50ns，都不正确。标准答案为85ns，需要计算地址传送、存储器准备数据和数据传输的时间。这个计算错误，扣2分。
（4）得分及理由（满分3分）
学生计算过程存在多处错误：指令条数写成了114条（应为100条），缺失次数计算错误（应为100×1.2×5%=6次），缺失损失时间使用错误的50ns（应为85ns），最终结果2970ns错误。虽然思路正确（分别计算命中和未命中时间），但计算过程和结果都有明显错误，扣3分。
题目总分：3+0+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分）
学生回答“字节，127条”，与标准答案一致。第一问正确说明存储器按字节编址（1分），第二问正确给出向后最多跳转127条指令（2分）。得3分。
（2）得分及理由（满分5分）
学生正确分析了两种情况：当CF=1, ZF=0, NF=0时不转移，PC=200EH（1分）；当CF=0, ZF=0, NF=1时转移，并正确计算偏移量OFFSET=-29（即E3H补码），通过PC=200CH+2+2×(-29)=1FD4H得出结果（2分）。计算过程完整正确。得5分。
（3）得分及理由（满分3分）
学生回答“Z=0时转移，NF⊕CF=1时转移”，这与标准答案“C=Z=1, N=0”不符。无符号数比较小于等于时转移的条件是CF=1或ZF=1，即C和Z检测位应设为1，N检测位设为0。学生给出的逻辑表达式不准确，未能正确设置C、Z、N的值。得0分。
（4）得分及理由（满分3分）
学生回答“PSW标志，指令寄存器”，但问题要求给出三个部件的名称或功能。学生只给出了两个，且未明确对应部件编号。部件①应为指令寄存器，部件②应为移位寄存器（左移一位），部件③应为加法器。学生答案不完整且未正确对应。得0分。
题目总分：3+5+0+0=8分
评分及理由
（1）信号量定义及含义（满分4分）
得分：4分
理由：学生定义了两个信号量，contain（对应标准答案中的empty）初值为500，用于控制博物馆容纳人数；mutex初值为1，用于出入口互斥控制。信号量含义和初值都正确，符合标准答案要求。
（2）mutex的P、V操作（满分2分）
得分：2分
理由：学生在进门和出门操作前后都正确使用了P(mutex)和V(mutex)操作，确保出入口的互斥访问，与标准答案完全一致。
（3）contain的P、V操作（满分1分）
得分：1分
理由：学生在进门前使用P(contain)控制人数，在出门后使用V(contain)释放人数，操作顺序和位置都正确。
题目总分：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分）
学生答案：页大小4KB正确，页表最大占用16MB错误。标准答案中页大小为4KB（由12位页内偏移量决定），页表项数为2^20，每个页表项4字节，因此页表最大占用4MB。学生计算为16MB，存在逻辑错误。扣2分，得1分。
（2）得分及理由（满分2分）
学生答案：页目录号=LA/2^22，页表索引=(LA/2^12)%2^10。虽然使用了除法和取模运算，但表达式正确反映了逻辑地址的划分方式，与标准答案的移位和掩码操作等价。根据评分说明，用其他运算方法但基本原理正确同样给分。因此不扣分，得2分。
（3）得分及理由（满分3分）
学生答案：代码页面2起始物理地址00901000H正确；但页表项物理地址计算错误（00B00000H和00B01000H），页框号格式错误（应为5位十六进制数）。标准答案中，页表起始地址00200000H，第一个页表项对应第8页，物理地址应为00200020H；页框号应从页表项中提取，学生给出的页框号格式不正确且数值错误。存在多处逻辑错误，扣2分，得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，下一跳153.14.3.2，接口S0。与标准答案一致，得2分。
- 第二个路由项：目的网络194.17.20.128/25，下一跳为空（直接连接），接口E0。与标准答案一致，得2分。
- 第三个路由项：目的网络194.17.20.0/25（第二次识别结果），下一跳194.17.24.2，接口S1。但标准答案中AS2的子网聚合应为194.17.20.0/23，学生写成了194.17.20.0/25，这是一个逻辑错误，因为194.17.20.0/25无法覆盖194.17.21.0/24子网。因此该路由项不正确，扣2分。
此外，第一次识别结果中还有不完整的路由项（194.17.21），但根据禁止扣分规则，识别错误不扣分。
本小题得分：2 + 2 + 0 = 4分。
（2）得分及理由（满分1分）
学生回答E0，与标准答案一致。根据最长匹配原则，目的IP地址194.17.20.200匹配194.17.20.128/25（E0接口）而非194.17.20.0/23。得1分。
（3）得分及理由（满分2分）
学生回答RIP（第一次识别结果中有额外错误信息，但根据禁止扣分规则，识别错误不扣分）。但RIP是内部网关协议（IGP），而R1和R2属于不同自治系统（AS1和AS2），应使用外部网关协议BGP。因此回答RIP是错误的，扣1分。对于封装协议，学生未回答，扣1分。
本小题得分：0分。
题目总分：4+1+0=5分
The road of your choice, you have to go on !
粤ICP备16082171号-1
