科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
某网络拓扑及各链路带宽如图所示。网络按电路交换方式运行时，主机\(\text{H1}\)与\(\text{H2}\)建立一条带宽为\( 10 \ \text{Mb/s} \)的电路，建立电路时间为\( 32\mu\text{s} \)；按分组交换方式运行时，分组长度为\( 400 \ \text{B} \)，忽略分组首部开销。现\(\text{H1}\)向\(\text{H2}\)发送一个\( 2\text{MB} \)（\( 1\text{M}=10^6 \)）的文件，分别采用电路交换、报文交换、分组交换方式时，\(\text{H2}\)至少需要\( T_{\text{cs}} \)、\( T_{\text{ms}} \)、\( T_{\text{ps}} \)时间才能接收到全部文件内容，则\( T_{\text{cs}} \)、\( T_{\text{ms}} \)、\( T_{\text{ps}} \)满足的关系是（）。
A. \( T_{\text{cs}}>T_{\text{ms}}>T_{\text{ps}} \) B. \( T_{\text{ms}}>T_{\text{ps}}>T_{\text{cs}} \) C. \( T_{\text{ms}}>T_{\text{cs}}>T_{\text{ps}} \) D. \( T_{\text{ps}}>T_{\text{ms}}>T_{\text{cs}} \)
一台新接入网络的主机 \( H \) 通过 DHCP 服务器动态请求 IP 地址过程中，与 DHCP 服务器交换 DHCP 报文过程如下图所示。封装 DHCP 的 REQUEST 报文的 IP 数据报的目的 IP 地址和源 IP 地址分别是（）
A. \( 192.168.5.1 \)，\( 0.0.0.0 \)
B. \( 192.168.5.1 \)，\( 192.168.5.9 \)
C. \( 255.255.255.255 \)，\( 0.0.0.0 \)
D. \( 255.255.255.255 \)，\( 192.168.5.9 \)
主机甲通过 TCP 向主机乙发送数据的部分过程如下图，seq 为序号，ack-seq 为确 认序号，rcwnd 为接收窗口。甲在 t0 时刻的拥塞窗口和发送窗口均为 2000B，拥塞 控制阈值为 8000B，MSS=1000B。甲始终以 MSS 发送 TCP 段。若甲在 t1 时刻收到 如图所示的确认段，则甲在未收到新的确认段之前，还可以继续向乙发送的 TCP 段数是（ ）
A.2 B.3 C.4 D.5
评分及理由
（1）得分及理由（满分4分）
得0分。学生的基本设计思想是采用双重循环遍历所有i和j（0≤i≤j≤n-1）的组合，计算A[i]与A[j]的乘积并取最大值存入res[i]。虽然思路正确，但题目要求“时间和空间上尽可能高效的算法”，而双重循环的时间复杂度为O(n²)，不符合高效要求。标准答案给出了O(n)的线性算法，因此学生的设计思想在效率上不满足题目要求，故扣4分。
（2）得分及理由（满分7分）
得2分。学生的代码实现了双重循环，逻辑上可以计算出正确结果，但存在以下问题：
1. 代码中使用了“×”符号（可能是识别错误，实际应为“*”），但根据禁止扣分规则，字符识别错误不扣分。
2. 内层循环j从0开始，但题目要求j≥i，学生的代码计算了所有j（包括j
由于算法效率低下，不符合“尽可能高效”的要求，扣5分。
（3）得分及理由（满分2分）
得2分。学生正确分析了算法的时间复杂度为O(n²)，空间复杂度为O(1)，与代码实现一致，因此得满分。
题目总分：0+2+2=4分
（10分）某工程包含12个活动，使用下图所示的AOE网描述，图中各边上标注了活动及其持续时间。
请回答下列问题（活动均用活动名表示）。
（1）完成该工程的最短时间是多少？哪些活动是关键活动？（3分）
（2）若以最短时间完成工程，则与活动e同时进行的活动可能有哪些？（3分）
（3）时间余量最大的活动是哪个？其时间余量是多少？（2分）
（4）假设工程从时刻0启动，因某种原因，活动b在时刻6开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，b的持续时间最多是多少？若不改变b的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？（2分）（注意，无过程或原因要求可以只写答案）
评分及理由
（1）得分及理由（满分3分）
学生答案中给出了最短时间为12，关键活动为a、e、m、n，与标准答案完全一致。尽管学生列出了顶点和活动的最早最晚时间表，但这是解题过程的一部分，且最终结论正确。根据评分要求，思路正确不扣分，额外分析不扣分。因此本题得3分。
（2）得分及理由（满分3分）
学生答案指出与活动e同时进行的活动可能为b、c、d，与标准答案完全一致。因此本题得3分。
（3）得分及理由（满分2分）
学生答案指出时间余量最大的活动是j，余量为6，与标准答案完全一致。因此本题得2分。
（4）得分及理由（满分2分）
学生答案给出了b的持续时间最多为4，以及可以压缩活动k的持续时间，这两个要点均与标准答案一致。因此本题得2分。
题目总分：3+3+2+2=10分
评分及理由
（1）得分及理由（满分3分）
学生答案正确给出了块内地址6位、Cache组号6位，以及虚拟地址VA11~VA6可作为Cache索引。与标准答案完全一致。得3分。
（2）得分及理由（满分2分）
学生正确计算了d[100]的虚拟地址为0180 01B0H。对于Cache组号，学生答案为“6”，标准答案为“06H”，两者数值一致，只是表示形式不同，不扣分。得2分。
（3）得分及理由（满分5分）
本题分三小问：偏移量、缺失率、平均访问时间。
① 偏移量：学生答案为“20H”，正确。得1分。
② 缺失率：学生分析思路正确（识别出129次缺失，4096次访问），计算结果为3.12%，与标准答案3.15%的微小差异可能源于四舍五入，且其计算过程（129/4096）正确，因此不扣分。得2分。
③ 平均访问时间：学生计算了总时钟周期数33734，但题目要求的是“数组元素的平均访问时间”，即每次访问的平均时间。标准答案为8.3个时钟周期。学生答案“33734个时钟”是总时间，不符合问题要求，属于逻辑错误。应扣1分。
本小题总计得分：1+2+0 = 3分。
（4）得分及理由（满分2分）
学生正确回答了数组d分布在3页中，缺页次数为3次。与标准答案一致。得2分。
题目总分：3+2+3+2=10分
（11分）对于上题中计算机M和程序P，假定P的部分机器级代码如下所示，其中，R0～R4为通用寄存器，SEXT表示按符号扩展；M中补码除法器逻辑结构如下所示。
...
//x在R2中，i在R4中
//数组d的首地址在R3中
mov R1, (R3+R4*4) //R1←d[i]
scov R1 //{R0,R1}←SEXT(R1)
idiv R1, R2 //R1←{R0,R1}/R2
...
请回答下列问题。
（1）若执行idiv指令的除运算时，d[i]=0x87654321、x=0xff，则补码除法器中寄存器R、Q和Y的初始内容分别是什么（用十六进制表示）？图中哪个部件包含计数器？在补码除法器执行过程中，由ALUop所控制的ALU运算有几种？（6分）
（2）假设idiv指令执行过程中会检测并触发除法异常，则执行idiv指令时，哪些情况下会发生除法异常（要求给出此时d[i]和x的十六进制表示机器数）？发生除法异常时，在异常响应过程中CPU需要完成哪些操作？（5分）
评分及理由
（1）得分及理由（满分6分）
学生答案中：
- R初始值：给出0x87654321，标准答案为0xffffffff。错误。根据补码除法（如不恢复余数法）的初始化规则，对于被除数d[i]=0x87654321（负数），其双倍字长扩展应为符号扩展，即高32位应为全1（0xffffffff），学生答案直接用了原数，属于逻辑错误。
- Q初始值：给出0x87654321，标准答案为0x87654321。正确。
- Y初始值：给出0x000000ff，标准答案为0xfffffffe。错误。除数x=0xff，为补码正数，但在补码除法器中，除数通常需要符号扩展并与被除数位数对齐（32位），且根据图示结构，Y初始值应为除数左移一位（或符号扩展后左移）？标准答案给出0xfffffffe，即0xff符号扩展为32位0x000000ff再左移一位？此处需明确：若除数为32位，Y初始值应为除数符号扩展后左移一位（n位除法左移n位），但常见教材中补码除法初始化时Y为除数（符号扩展至与被除数高位部分等长），标准答案0xfffffffe可能是将0xff（000000FF）符号扩展为32位后视为-1的补码（FFFFFFFF）再左移一位得FFFFFFFE。学生答案0x000000ff未进行正确符号扩展和移位，逻辑错误。
- 计数器位置：学生答“控制器CU中包含计数器”，与标准答案“b中的控制逻辑包含计数器”基本一致，正确。
- ALU运算种类：学生答“有移位运算，除法运算”，标准答案为“加法和减法”。ALUop控制的是算术逻辑单元的运算，在补码除法器中主要是加/减操作，移位通常由移位器完成。学生答案混淆了ALU运算和除法器整体操作，逻辑错误。
扣分：R、Y初始值错误各扣1分，ALU运算种类错误扣1分，其余部分正确。本小题满分6分，扣3分，得3分。
（2）得分及理由（满分5分）
学生答案中：
- 除法异常情况：只提到“当X=0H时”，即除数为0异常，正确。但未提及溢出异常（被除数为-2^31且除数为-1的情况），遗漏一种情况。
- CPU响应操作：给出“关中断，保存断点，中断服务程序寻址”，与标准答案“关中断，修改CPU状态为内核态，保存断点（PC和PSWR中的值），跳转到异常处理程序”基本一致，但缺少“修改CPU状态为内核态”，不过核心操作已涵盖，可不扣分。
扣分：遗漏溢出异常情况，扣2分。本小题满分5分，扣2分，得3分。
题目总分：3+3=6分
评分及理由
（1）信号量定义及初值（满分约2分）
得分：1分。理由：学生定义了三个信号量TQ（铁锹互斥）、mutex（互斥锁）、NeedWater（通知浇水），以及一个整型变量empty（坑的数量）。其中TQ和mutex的初值正确，NeedWater初值正确。但存在以下问题：1. 题目要求“定义尽可能少的信号量”，使用整型变量empty不符合信号量同步的常规做法，且对empty的访问未用信号量保护（虽然用了mutex，但empty本身应设计为信号量以实现同步）。标准答案使用sk和empty两个信号量分别控制可挖坑数量和可用坑数量，更为规范。2. 缺少控制“树坑数量小于3时甲才可以挖树坑”的同步信号量（标准答案中的sk），学生用if(empty < 3)判断，但empty是共享变量，在多线程环境下需严格同步，且if判断无法阻塞等待，不符合PV操作原语。因此扣1分。
（2）甲进程同步逻辑（满分约2分）
得分：0.5分。理由：甲进程中，先通过mutex保护对empty的判断，若empty<3则申请铁锹(TQ)。但这里存在严重逻辑错误：1. if(empty < 3)判断后，无论条件是否成立都会执行signal(mutex)并继续执行“挖树坑”，这违反了“当树坑数量小于3时，甲才可以挖树坑”的约束（当empty>=3时甲不应挖坑）。2. 挖坑后直接signal(TQ)释放铁锹，但挖坑前可能并未成功申请到铁锹（当empty>=3时不会wait(TQ)），导致释放未持有的信号量错误。3. empty++操作用mutex保护正确，但未通知乙有坑可用（缺少类似signal(empty)的操作）。因此扣1.5分。
（3）乙进程同步逻辑（满分约2分）
得分：1分。理由：乙进程中，先判断empty>0，然后通过mutex保护empty--，之后放树苗、申请铁锹填土、释放铁锹、通知丙浇水。基本流程正确，且通知丙的信号量使用正确。但存在以下问题：1. if(empty>0)判断同样存在同步问题，应用wait操作阻塞等待。2. 缺少对“填土”前铁锹互斥的保护（已有wait(TQ)正确）。3. 乙完成后未释放“可挖坑数量”资源（即未通知甲可以继续挖坑）。因此扣1分。
（4）丙进程同步逻辑（满分约1分）
得分：1分。理由：丙进程正确等待NeedWater信号量后浇水，逻辑正确。未提及水桶互斥，但题目中水桶只有一个，理论上也需互斥，不过标准答案也未对水桶设互斥（浇水未用信号量保护），因此不扣分。
题目总分：1+0.5+1+1=3.5分
（8分）某系统中进程的虚拟地址空间包括内核区、用户栈、运行时堆、可读写数据段、只读代码段等区域，其布局如图所示，图中阴影部分表示未占用区域。现有C语言程序的部分代码如下。
char * ptr;
void main( )
{
int length;
ptr=(char *)malloc(100);
scanf("%s",ptr);
length=strlen(ptr);
printf("length=%d\n",length);
free(ptr);
}
请回答下列问题。
（1）上述程序执行时，其进程控制块位于哪个区域？执行scanf( )等待键盘输入时，该进程处于什么状态？（2分）
（2）main( )函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？（3分）
（3）变量ptr被分配在哪个区域？若变量length没有被分配在寄存器中，则会被分配在哪个区域？ptr指向的字符串位于哪个区域？（3分）
评分及理由
（1）得分及理由（满分2分）
学生答案：PCB位于内核区，处于阻塞态。
标准答案：PCB位于内核区，执行scanf()时进程处于阻塞态。
分析：学生答案与标准答案完全一致，正确指出了进程控制块的位置和进程在等待I/O时的状态。
得分：2分。
（2）得分及理由（满分3分）
学生答案：位于只读代码区，scanf和printf需要执行驱动。
标准答案：main()函数的代码位于只读代码段（.text），其直接调用的scanf()和printf()需要执行驱动程序。
分析：学生答案正确指出了main()函数代码的位置以及需要驱动程序实现的函数。答案完整且正确。
得分：3分。
（3）得分及理由（满分3分）
学生答案：ptr分配在可读写数据区中，length会被分配在用户栈中，ptr指向的字符串位于运行时堆中。
标准答案：ptr位于读/写数据段，length位于用户栈段，ptr指向的内存单元位于堆区。
分析：学生答案与标准答案在核心逻辑上完全一致。表述上“可读写数据区”即“读/写数据段”，“用户栈”即“用户栈段”，“运行时堆”即“堆区”。所有要点均正确。
得分：3分。
题目总分：2+3+3=8分
（9分）某公司在承建国家重大工程项目时，工程部需要较长时间驻扎在偏远山区，工程部网络需要连接公司总部网络。假设综合考虑方案的技术可行性、安全性与经济性等因素后，决定租用我国自主建设的天通一号卫星通信链路，连接工程部网络的路由器R1和公司总部网络的路由器R2，如题47图所示。S1和S2为千兆以太网交换机；TR1和TR2为卫星信号地面收发设备，实现全双工调制解调。天通一号卫星轨道高度是36 000 km，电磁波信号传播速度为300 000 km/s。租用的卫星链路为R1和R2之间提供对称全双工信道，每个方向的数据传输速率为200 kb/s。
请回答下列问题。
（1）若忽略卫星信号中继以及TR1和TR2调制解调的时间开销，则R1到R2之间卫星链路的单向传播时延是多少？主机H向总部服务器传输数据时可以达到的最大吞吐量是多少？若忽略各层协议数据包的首部开销以及以太网内的传播时延，则主机H向总部服务器上传一个4000 B大小的工程进度报告文件，至少需要多长时间？（3分）
（2）现需要基于GBN滑动窗口协议为卫星链路设计单向可靠的数据链路层协议SLP，支持R1向R2发送数据，SLP数据帧长为1500 B，忽略ACK帧长度。若要求SLP的单向信道利用率不低于80%，则SLP的发送窗口至少为多少？SLP帧的序号字段至少需要多少位？（3分）
（3）若公司总部为工程部网络分配的IP地址空间是10.10.10.0/24，工程部进一步将该IP地址空间分配给3个子网，其中生活区子网可分配IP地址数不少于120个，作业区子网和管理区子网可分配IP地址数均不少于60个，且主机H已正确配置了IP地址，则作业区子网、管理区子网和生活区子网的子网地址分别是什么（给出CIDR地址形式）？（3分）
评分及理由
（1）得分及理由（满分3分）
学生答案中单向传播时延计算正确（0.24 s = 240 ms），最大吞吐量正确（200 kb/s），文件传输最少时间计算正确（0.4 s = 400 ms）。虽然公式书写时在传播时延计算中未明确体现“2×”的来源（即信号需上行至卫星再下行至地面，总路径为2倍轨道高度），但数值结果正确。文件传输时间计算中，学生使用了“4000B / 200kb/s + 0.24s”，这与标准答案“240×10^{-3} + (4000×8)/(200×10^3)”本质相同（注意学生写法中“4000B / 200kb/s”隐含了单位转换，因为1B=8b，所以4000B对应32000b，除以200kb/s即得0.16s，加上0.24s得0.4s）。因此，本题答案完全正确，得3分。
（2）得分及理由（满分3分）
学生正确计算了发送窗口至少为8，帧序号至少为4位。计算过程清晰：先求帧传输时间T0=0.06s，然后利用信道利用率公式（发送窗口×T0）/（T0+2×传播时延）≥80%，解得x≥7.2，取整得8。对于GBN协议，发送窗口W_s与序号位数k满足2^k ≥ W_s+1，代入W_s=8得2^k ≥9，故k≥4。答案与标准答案一致，得3分。
（3）得分及理由（满分3分）
学生给出的三个子网CIDR地址分别为：作业区10.10.10.0/26，管理区10.10.10.64/26，生活区10.10.10.128/25。标准答案为：作业区10.10.10.64/26，管理区10.10.10.0/26，生活区10.10.10.128/25。学生将作业区和管理区的子网地址互换，但题目要求“作业区子网和管理区子网可分配IP地址数均不少于60个”，两者规模相同，子网划分方案可以互换，只要满足生活区子网（≥120个地址）使用/25，其余两个子网使用/26即可。因此，学生的划分方案在逻辑上是正确的，只是子网命名与标准答案不同，但题目并未指定哪个子网必须对应哪个具体地址块，只要划分合理即正确。故得3分。
题目总分：3+3+3=9分
The road of your choice, you have to go on !
粤ICP备16082171号-1
