科目组合
数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
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.由于ai的范围小于数组长度，因此可以用一个辅助数组统计序列A中各个元素出现的次数，然后再遍历查看辅助数组中的值是否存在大于长度一半的元素，有则输出这个元素的索引
2.
public static int findMajor(int [] arr) {
// 辅助数组
int [] temp = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
//序列中出现过的数的次数统计到辅助数组上
temp[arr[i]]++;
}
for (int i = 0; i < arr.length; i++) {
//遍历辅助数组中是否有主元素
if(temp[i] > arr.length/2){
return i;
}
}
return -1;
}
3.时间复杂度O(n),空间复杂度O(n)
评分及理由
（1）得分及理由（满分4分）
得分：4分
理由：学生提出的使用辅助数组统计元素出现次数，然后遍历查找是否存在出现次数超过n/2的元素，这个思路是正确的。虽然与标准答案的摩尔投票法不同，但题目要求"尽可能高效的算法"，且学生的算法时间复杂度为O(n)，满足要求。根据评分说明"思路正确不扣分"，因此给满分。
（2）得分及理由（满分7分）
得分：7分
理由：学生用Java语言正确实现了算法，代码逻辑清晰。使用辅助数组temp统计每个元素出现次数，然后遍历temp数组查找主元素。代码实现正确，关键步骤有注释说明。虽然实现方法与标准答案不同，但算法正确且满足题目要求。
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了算法的时间复杂度O(n)和空间复杂度O(n)，与实现的算法一致。根据评分说明，时间复杂度与空间复杂度分析正确可各得1分。
题目总分：4+7+2=13分
1.元素排列为do、while、for、repeat，使用顺序查找，查找成功的平均查找长度为0.35*1+0.35*2+0.15*3+0.15*4=2.1
2.元素排列为do、while、for、repeat，使用顺序查找，查找成功的平均查找长度为0.35*1+0.35*2+0.15*3+0.15*4=2.1
评分及理由
（1）得分及理由（满分5分）
学生回答中，元素排列为"do"、"while"、"for"、"repeat"，这实际上是将查找概率最高的两个元素（"do"和"while"，概率均为0.35）放在最前面，符合按查找概率降序排列的原则。采用顺序查找方法正确，平均查找长度计算过程和结果均正确（2.1）。因此，本小题得5分。
（2）得分及理由（满分5分）
学生回答中，元素排列与第（1）问相同，采用顺序查找方法。在链式存储结构下，按查找概率降序排列并使用顺序查找是可行的方案之一，平均查找长度计算正确。虽然标准答案中还给出了二叉排序树的方案（可能得到更低的平均查找长度），但学生的方案是有效的且符合题目要求。因此，本小题得5分。
题目总分：5+5=10分
1.CPU时钟周期为1.25ns ，总线的时钟周期为5ns，总线带宽为4B * 200M /1s = 800MB/s
2.8个
3.传送地址耗时5ns，第一个体准备数据40ns，最后传送数据到总线5ns，第二个体在第一个5ns就可传送地址，因此一个完成一次读突发传送事务所需时间为40+5+5*7=85ns
4.访问cache消耗的时钟周期数为100*1.2*4=480，耗时为480*1.25=600ns；cache未命中时，需要额外访问主存消耗的时间为120*0.05*85=510ns
总耗时为1110ns
评分及理由
（1）得分及理由（满分3分）
学生答案正确计算了CPU时钟周期（1.25ns）、总线时钟周期（5ns）和总线带宽（800MB/s）。计算过程和结果与标准答案一致。得3分。
（2）得分及理由（满分1分）
学生答案回答“8个”是错误的。标准答案指出Cache块大小为32字节，而每次突发传送可以传输32字节，因此只需要1个读突发传送总线事务即可完成一个主存块的读取。学生可能错误地认为每个体需要单独的事务，但这里突发传送一次就能完成整个块的传输。得0分。
（3）得分及理由（满分2分）
学生答案计算过程为“40+5+5*7=85ns”，虽然具体步骤描述与标准答案略有不同（学生提到“第二个体在第一个5ns就可传送地址”可能表述不够准确），但最终结果正确，且计算逻辑合理（考虑了地址传送、存储器准备数据和数据传输时间）。得2分。
（4）得分及理由（满分3分）
学生答案计算了Cache命中时的耗时（600ns）和Cache缺失时的额外开销（510ns），但总耗时计算为1110ns。标准答案中命中时的指令执行时间为500ns，而学生计算为600ns，这是因为学生使用了“100*1.2*4=480”周期数，再乘以1.25ns得到600ns，但标准答案中命中时的指令执行时间直接基于指令条数和CPI计算（100×4×1.25 ns=500ns），未乘以1.2的访存系数（因为CPI已包含访存）。学生在此处存在逻辑错误，多计算了访存次数的影响。但Cache缺失额外开销计算正确（510ns）。根据标准答案的评分说明，计算公式正确但运算结果不正确可酌情给分，此处给予部分分数。得1分。
题目总分：3+0+2+1=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.按字节编址，因为指令字长为16位，且下条指令地址为PC+2，向后最多可跳转128条
2.N=1且NF=1，说明需要发生转移，OFFSET为-29（十进制），因此执行后PC的值为200CH+2H-3AH=1FD4H；N=1,Z=1,但ZF和NF=0，因此不需要转移，PC值为200C+2H = 200EH
3.C=1，Z=1，N=0
4.①指令寄存器②移位器，让offset左移一位③ALU加法器
评分及理由
（1）得分及理由（满分3分）
学生回答“按字节编址”正确（1分），但“向后最多可跳转128条”错误（应最多跳转127条），因为OFFSET为8位补码范围是-128~127，向后跳转对应正偏移量最大127。扣1分，得2分。
（2）得分及理由（满分5分）
第一问：学生正确判断需要转移（1分），并给出正确结果1FD4H（2分），但计算过程中写“OFFSET为-29”错误（应为-29D，但实际E3H补码为-29D，此处不扣分），且“200CH+2H-3AH”中“3AH”应为“29*2=58=3AH”的简写，计算过程基本正确，得3分。
第二问：学生正确判断不转移（1分），并给出正确结果200EH（1分），得2分。本小题总计5分。
（3）得分及理由（满分3分）
学生回答“C=1，Z=1，N=0”与标准答案完全一致，得3分。
（4）得分及理由（满分3分）
学生回答“①指令寄存器”“②移位器，让offset左移一位”“③ALU加法器”与标准答案功能描述一致，得3分。
题目总分：2+5+3+3=13分
num=500;//博物馆初始剩余人数
mutex=1;//访问出入口的信号量
cobegin
参观者进程i:
{
p(num);
p(mutex);
进门;
v(mutex);
参观;
p(mutex);
出门;
v(mutex);
v(num);
}
coend
评分及理由
（1）信号量定义部分得分及理由（满分4分）
学生使用了num和mutex两个信号量，但未使用标准的信号量声明方式（如Semaphore），且未明确说明信号量的含义。num初值500正确，mutex初值1正确。但信号量含义说明缺失，扣2分。得2分。
（2）mutex的P、V操作得分及理由（满分2分）
学生对出入口的互斥控制正确：在进门和出门操作前后正确使用了P(mutex)和V(mutex)操作。得2分。
（3）empty（对应num）的P、V操作得分及理由（满分1分）
学生对人数控制的P、V操作正确：在进门前P(num)，在出门后V(num)，逻辑正确。得1分。
题目总分：2+2+1=5分
（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.页大小是4KB，页表最大是1M*4B=4MB
2.页目录号=LA/2^22，页表索引=LA%2^22/2^12
3.物理地址1为00200020H，物理地址2为00200022H，页框号1为00900H，页框号2为00901H，物理地址3为00901000H
评分及理由
（1）得分及理由（满分3分）
学生答案正确。页大小4KB（1分），页表最大4MB（2分）。计算过程正确，得3分。
（2）得分及理由（满分2分）
学生答案存在逻辑错误。页目录号表达式"LA/2^22"在整数除法下正确，但页表索引表达式"LA%2^22/2^12"存在错误：
- 应先取LA除以2^12的商，再对2^10取模得到页表索引
- 学生表达式先对2^22取模会丢失高位信息，计算结果不正确
扣1分，得1分。
（3）得分及理由（满分3分）
学生答案存在多处错误：
- 物理地址1正确（00200020H）
- 物理地址2错误，应为00200024H（8×4=32=20H，第9页表项地址应为00200020H+4=00200024H）
- 页框号1格式错误，应为00900H（缺少H后缀）
- 页框号2错误，应为00901H
- 物理地址3错误，应为00901000H
根据评分说明，物理地址部分共1分，页框号部分共1分，物理地址3给1分。学生物理地址1正确得0.5分，页框号基本正确得1分，物理地址3正确得1分，共得2.5分。
题目总分：3+1+2.5=6.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.
2.E0
3.BGP、IP
评分及理由
（1）得分及理由（满分6分）
学生给出的路由表有4项，而标准答案要求通过路由聚合减少到3项。学生正确聚合了AS1中的153.14.5.0/24（给2分），正确给出了194.17.20.128/25直连路由（给2分）。但在AS2的聚合中，学生没有将194.17.20.0/25和194.17.21.0/24聚合为194.17.20.0/23，而是分别列出（每条1分，共2分），这违反了"路由项尽可能少"的要求。但由于每条路由内容正确，按部分正确可酌情给分，扣除1分。本小题得分：2+2+1=5分。
（2）得分及理由（满分1分）
学生回答"E0"正确，符合最长匹配原则。得分：1分。
（3）得分及理由（满分2分）
学生回答"BGP"正确（给1分），但回答"IP"不正确，应该是封装在TCP中（扣1分）。得分：1分。
题目总分：5+1+1=7分
The road of your choice, you have to go on !
粤ICP备16082171号-1
