科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
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分）
得分：3分
理由：学生的算法设计思想使用了一个长度为n的计数数组来统计每个数字出现的次数，然后遍历计数数组找到出现次数超过n/2的元素。这种方法能够正确找出主元素，思路正确，但相比标准答案的摩尔投票法，空间复杂度为O(n)而不是O(1)，在空间效率上不如标准答案。考虑到题目要求"尽可能高效的算法"，这种解法在空间效率上有所不足，因此扣1分。
（2）得分及理由（满分7分）
得分：6分
理由：学生按照自己的设计思想实现了算法，代码逻辑正确，能够完成主元素的查找功能。代码结构清晰，注释恰当。但算法空间复杂度较高，没有达到最优，因此扣1分。代码中有一个小问题：在第二个循环中，应该检查R[j] > n/2，但题目要求m > n/2，如果m正好等于n/2+0.5（当n为奇数时），这个条件是正确的；但如果n为偶数，m需要大于n/2，这个条件也是正确的。不过代码实现是准确的。
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(n)，与实现的算法一致，分析准确。
题目总分：3+6+2=11分
评分及理由
（1）得分及理由（满分5分）
学生答案中，元素排列为"do"、"while"、"for"、"repeat"，这实际上是将查找概率最高的两个元素（p1=0.35和p4=0.35）放在最前面，符合按查找概率降序排列的原则。采用顺序查找方法正确，计算的平均查找长度2.1正确。与标准答案完全一致，得5分。
（2）得分及理由（满分5分）
学生采用了二叉搜索树（二叉排序树）的存储结构和查找方法，构建了以"for"为根节点的二叉排序树，并给出了正确的平均查找长度计算过程和结果2.0。这符合标准答案中的【答案二】方案，且计算正确。得5分。
题目总分：5+5=10分
评分及理由
（1）得分及理由（满分3分）
学生正确计算了CPU时钟周期（1.25 ns）、总线时钟周期（5 ns）和总线带宽（800 MB/s），与标准答案完全一致。得3分。
（2）得分及理由（满分1分）
学生正确指出Cache块大小为32字节，每次突发传送32字节，因此只需要一次突发传送事务。与标准答案一致。得1分。
（3）得分及理由（满分2分）
学生正确计算了地址传送时间（1个总线时钟周期，5 ns）、存储器准备数据时间（40 ns）和数据传送时间（8×5 ns=40 ns），并正确求和得到85 ns。与标准答案一致。得2分。
（4）得分及理由（满分3分）
学生计算了Cache命中时的指令执行时间（500 ns）和Cache缺失时间（425 ns），但错误地增加了访存时间（150 ns）。标准答案中不需要单独计算访存时间，因为Cache命中时的CPI已经包含了访存时间。正确的计算应该是：指令执行时间500 ns + 缺失开销510 ns = 1010 ns。学生多加了150 ns，存在逻辑错误。由于计算公式部分正确（命中时间和缺失时间计算正确），但多加了不必要的部分，扣1分。得2分。
题目总分：3+1+2+2=8分
（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分）
学生回答“按字编址”错误，标准答案为按字节编址。但学生正确识别了偏移量范围为-128~127，并得出向后最多可跳转127条指令。因此，编址部分扣1分，跳转指令数部分得2分。本小题得2分。
（2）得分及理由（满分5分）
学生正确判断了第一种情况（CF=0, ZF=0, NF=1）需要转移，并正确计算了PC值为1FD4H；第二种情况（CF=1, ZF=0, NF=0）不需要转移，PC值为200EH也正确。但在计算过程中，学生将OFFSET错误写为0000 1100（应为1110 0011），这可能是识别错误，但后续计算仍使用了正确的E3H值，因此不扣分。本小题得5分。
（3）得分及理由（满分3分）
学生正确给出了C=1, Z=1, N=0，与标准答案一致。本小题得3分。
（4）得分及理由（满分3分）
学生正确识别了部件①为指令寄存器，部件②为移位器（左移一位），部件③为加法器，与标准答案一致。本小题得3分。
题目总分：2+5+3+3=13分
评分及理由
（1）信号量定义及含义说明（满分4分）
得分：4分
理由：学生正确定义了两个信号量empty和mutex，并给出了正确的初值（empty=500，mutex=1），同时说明了它们的含义（empty表示可容纳人数，mutex表示互斥出入口）。这与标准答案完全一致。
（2）对mutex的P、V操作（满分2分）
得分：2分
理由：学生在进门和出门操作前后正确使用了P(mutex)和V(mutex)操作，实现了对出入口的互斥访问，与标准答案完全一致。
（3）对empty的P、V操作（满分1分）
得分：1分
理由：学生在进门前使用P(empty)检查是否有空闲位置，在出门后使用V(empty)释放位置，这与标准答案完全一致。
题目总分：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和页表最大占用4MB，与标准答案一致。得3分。
（2）得分及理由（满分2分）
学生给出了页目录号表达式 LA>>22 正确，但页表索引表达式 (LA<<10/2²²) 存在逻辑错误。标准答案应为 ((LA>>12)&0x3FF)，学生表达式先左移10位再除以2²²等价于右移12位，但缺少掩码操作，且左移可能导致溢出。由于表达式基本正确但不够精确，扣1分。得1分。
（3）得分及理由（满分3分）
学生计算物理地址1为0020 8000H错误（应为0020 0020H），物理地址2为0020 9000H错误（应为0020 0024H），页框号1为00900H正确（对应00900000H），页框号2为00901H正确（对应00901000H），物理地址3为0090 1000H正确。由于两个物理地址计算错误，扣2分。得1分。
题目总分：3+1+1=5分
（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（或SO，识别误差）
- 目的网络194.17.20.128/25，下一跳为空（正确），接口E0（或EO，识别误差）
- 目的网络194.17.20.0/23，下一跳194.17.24.2，接口S1
这三个路由项与标准答案完全一致，路由聚合正确，路由项数量最少。虽然接口名称有识别误差（SO应为S0，EO应为E0），但根据题目图示和上下文可判断为误写，不扣分。因此本小题得6分。
（2）得分及理由（满分1分）
学生答案正确指出R2通过E0接口转发该IP分组，理由是基于最长匹配原则（虽然学生未明确写出理由，但答案正确）。根据标准答案，此回答得1分。
（3）得分及理由（满分2分）
学生答案正确指出R1与R2之间使用BGP协议，并正确指出封装到TCP协议分组传输。与标准答案完全一致，因此得2分。
题目总分：6+1+2=9分
The road of your choice, you have to go on !
粤ICP备16082171号-1
