科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
某网络拓扑及各链路带宽如图所示。网络按电路交换方式运行时，主机\(\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分）
得分：2分
理由：学生作答的基本设计思想是：对于每个A[i]，根据其正负，在其后的子数组（A[i]到A[n-1]）中寻找最大值（若A[i]为正）或最小值（若A[i]为负）来相乘。这个思路在逻辑上是正确的，能够计算出题目要求的res[i]值。但是，该思路描述不够完整和精确。题目要求是“A[i]与A[j]（0≤i≤j≤n-1）乘积的最大值”，这意味着对于每个i，需要在其自身及之后的所有元素中寻找一个j，使得乘积最大。学生的思路中，对于正数找“最大的正数”，这个限定“正数”是不必要的，因为如果后面有绝对值很大的负数，与正数相乘可能得到更大的负数（如果目标是最大值，这显然不是我们想要的），但根据乘积最大化的原则，正数应该与后面的最大值相乘（无论正负，因为如果最大值是负数，乘积为负，但正数乘以自身或更大的正数可能得到更大的正数，所以逻辑上需要的是全局最大值）。学生的文字描述“找到其中最大的正数”存在逻辑瑕疵，没有考虑到最大值可能是负数的情况（尽管对于正数A[i]，与负数相乘结果更小，所以实际上应该找最大值，但最大值如果是负数，乘积为负，而A[i]与自身相乘至少是非负的，所以最大值策略仍然正确，但描述不准确）。同时，对于A[i]=0的情况处理是合理的。由于思路核心正确但表述有缺陷，扣2分。
（2）得分及理由（满分7分）
得分：4分
理由：学生的代码实现了其所述思路，但存在几处逻辑错误和缺陷：
1. 对于A[i] > 0的情况，代码中初始化`int max = 0;`，然后在内层循环中寻找`A[j] > max`的值。这里的问题在于，如果A[i]之后的所有元素都小于0，那么max将保持为0，导致`res[i] = A[i] * 0 = 0`。但实际上，A[i]是正数，与后面任何一个元素（包括自身）相乘，至少应该等于A[i]*A[i]（当j=i时），这个值可能大于0。例如，A = [2, -5, -10]，对于i=0，A[0]=2为正，后面最大元素应该是2（自身）或-5（但-5<2），但按照代码逻辑，max初始为0，所有A[j]都小于0，所以max保持0，res[0]=0，而正确结果应该是2*2=4。因此，这里应该初始化为`int max = A[i];`或者`int max = INT_MIN;`，然后从j=i开始比较。这是一个逻辑错误。
2. 对于A[i] < 0的情况，代码初始化`int min = INT_MAX;`是正确的，因为要找最小值。但内层循环从j=i开始，能够包含自身，逻辑正确。
3. 代码中对于A[i]==0的处理正确。
4. 代码中使用了`INT_MAX`，需要包含头文件`
5. 代码整体结构清晰，关键注释也有给出。
由于存在上述逻辑错误（主要在第1点），扣3分。
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了算法的时间复杂度为O(n²)（因为双重循环），空间复杂度为O(1)（只使用了常数个额外变量）。这与代码实现相符，因此给满分。
题目总分：2+4+2=8分
（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/(2048×2)≈3.15%，与标准答案一致。得2分。
- 平均访问时间：学生计算过程为2×(1-3.15%)+(200+2)×3.15%=8.03个时钟周期。标准答案为2+200p=8.3个时钟周期。学生公式中“(200+2)”有误，应为“200”（缺失损失已包含缺失时间，无需再加命中时间），导致结果（8.03）与标准答案（8.3）存在偏差。此为核心计算逻辑错误，扣1分。得1分。
（4）得分及理由（满分2分）
学生正确计算出数组d分布在3页，缺页次数为3次。与标准答案一致。得2分。
题目总分：3+2+4+2=11分
（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、Q、Y的初始内容，学生回答“R: 8765 4321H”、“Q: 8765 4321H 0000 0000H”、“Y: FFFF FFFFH”。
根据标准答案，R应为0xffffffff（即符号扩展后的高32位），学生答错；Q应为0x87654321（被除数低32位），学生答错（多写了0000 0000H）；Y应为0xfffffffe（除数取负后的补码），学生答错。
这三部分均错误，应扣分。但考虑到学生可能将Q理解为被除数整体（64位）而写出两部分，且Y的答案与标准答案相差较大，属于逻辑错误。
- 对于“图中哪个部件包含计数器”，学生答“控制逻辑包含计数器”，与标准答案一致，正确。
- 对于“ALUop所控制的ALU运算有几种”，学生答“加、减、算术左移”，但标准答案为加法和减法两种。算术左移通常由移位器完成，不属于ALUop控制的ALU运算，因此学生多答了“算术左移”，属于逻辑错误。
综合来看，本小题共6分，其中R、Q、Y各占1分（共3分），计数器部分占1分，ALU运算种类占2分。学生计数器部分正确得1分，其余部分均错误，故得1分。
（2）得分及理由（满分5分）
学生答案中：
- 对于除法异常情况，学生指出两种：①除数为0（x=0x00000000），正确；②溢出异常，给出x=0xffffffff，d[i]=0x10000000H。标准答案为d[i]=0x80000000（即-2^31），学生写为0x10000000H，数值错误（0x10000000H不是-2^31的补码表示），属于逻辑错误。
- 对于异常响应操作，学生答“关中断，保存断点，转到相应的中断处理程序”，与标准答案基本一致（标准答案还包括修改CPU状态为内核态，学生未明确写出，但“中断服务”可能隐含此意，且核心操作已涵盖）。此处可视为正确。
本小题共5分，其中异常情况占3分（除0异常1分，溢出异常2分），异常响应操作占2分。学生除0异常正确得1分，溢出异常错误扣2分，异常响应操作正确得2分，故得3分。
题目总分：1+3=4分
评分及理由
（1）得分及理由（满分7分）
学生答案定义了5个信号量：empty-keng（初值3，控制可挖坑数量）、full-keng（初值0，表示已挖未种坑数）、tree（初值0，表示已种未浇水树数）、Qiu（初值1，铁锹互斥）、tong（初值1，水桶互斥）。
与标准答案对比：
- 信号量设计思路正确，均能实现同步互斥要求。
- empty-keng 对应标准答案的 sk，full-keng 对应 empty，tree 对应 water，Qiu 对应 mutexT，tong 是额外为水桶定义的互斥信号量。
- 题目要求“定义尽可能少的信号量”，标准答案未为水桶单独设信号量，因为浇水不与其他操作冲突（铁锹用于挖坑和填土，水桶只用于浇水，且丙单独浇水，无需互斥）。学生为水桶设互斥信号量虽无逻辑错误，但未满足“尽可能少”的要求，属于冗余。
- 学生答案中乙的流程为：P(full-keng) -> P(Qiu) -> 放树填土 -> V(Qiu) -> V(empty-keng) -> V(tree)。其中 V(empty-keng) 使可挖坑数+1，符合“树坑数量小于3时甲可挖”的约束（通过empty-keng初值3和P(empty-keng)实现）。
- 丙的流程中 P(tree) 和 P(tong) 顺序可能导致死锁风险较低（因为tree由乙释放，tong初始可用），但若丙先拿到tong再等tree，可能浪费水桶资源，不过题目未严格要求顺序，且主要同步逻辑正确。
扣分点：
- 信号量数量未尽可能少（多定义了一个水桶互斥信号量），扣1分。
- 其他部分逻辑正确，同步关系完整。
得分：6分（满分7分）。
题目总分：6分
（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分）
学生两次识别结果均正确指出进程控制块位于内核区，执行scanf()等待键盘输入时进程处于阻塞态。与标准答案完全一致。得2分。
（2）得分及理由（满分3分）
学生两次识别结果均正确指出main()函数代码位于只读代码段（第一次识别为“R段代码段”，可理解为只读代码段，不扣分）。对于需要驱动程序实现的函数，第一次识别为scanf()和printf()，第二次识别为scanf()和printf()（但表述为“系统调用”，驱动程序是实现系统调用的底层模块，此表述在操作系统语境下可接受，且与标准答案一致）。因此答案正确。得3分。
（3）得分及理由（满分3分）
本题有三个小问。学生两次识别结果均正确指出length变量分配在用户栈，ptr指向的字符串位于运行时堆（即堆区）。对于变量ptr的分配区域，学生的两次识别结果存在矛盾：第一次识别先说“ptr被分配在运行时堆区”，紧接着又说“ptr被分配在可读写数据段”；第二次识别重复了同样的矛盾表述。根据C语言语义，ptr是一个全局指针变量，其本身应存储在可读写数据段（.data或.bss），而非堆区。学生虽然给出了正确位置“可读写数据段”，但同时也给出了错误位置“运行时堆区”，造成了逻辑矛盾。因此，对于“ptr被分配在哪个区域”这一问，不能给分。其余两问正确。故本小题扣1分，得2分。
题目总分：2+3+2=7分
（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.4s（即400ms），但标准答案为240ms。学生错误地将距离乘以2（即考虑了往返），而题目要求的是单向传播时延，应为36000km / 300000km/s = 0.12s = 120ms，但标准答案中给出的240ms是考虑了信号从R1到卫星再到R2的总路径（即2倍轨道高度），因此单向传播时延为2×36000/300000=0.24s=240ms。学生计算为0.4s，存在逻辑错误，扣1分。
最大吞吐量回答正确（200kb/s），不扣分。
最少时间计算中，学生使用了错误的传播时延（0.4s）和错误的数据传输时间（4000B/200kb/s，注意单位换算，应为4000×8/200000=0.16s），得到0.56s，而正确答案为0.24s+0.16s=0.4s。因传播时延错误导致结果错误，扣1分。
本小题共扣2分，得1分。
（2）得分及理由（满分3分）
学生计算信道利用率公式为：80% = (n × (1500B/200kb/s)) / (0.8s + 1500B/200kb/s)。其中0.8s应为往返传播时延（RTT），即2×240ms=0.48s，但学生写为0.8s（可能是误写，但根据上下文判断，0.8s与0.48s差异较大，且学生计算中使用了0.8s，导致分母偏大，计算结果n=12，而标准答案为8）。因此，公式中的RTT值错误，属于逻辑错误，扣1分。
发送窗口计算结果为12（标准答案为8），错误，扣1分。
帧序号位数计算为4位，虽然窗口值错误，但学生可能基于2^k ≥ W_s+1计算，若W_s=12，则2^k≥13，k至少为4，但标准答案中W_s=8，k≥4，结果巧合正确。但因其窗口计算错误，序号位数推导过程不严谨，但结果正确，不扣分。
本小题共扣2分，得1分。
（3）得分及理由（满分3分）
学生给出的三个子网CIDR地址与标准答案完全一致：作业区子网10.10.10.64/26，管理区子网10.10.10.0/26，生活区子网10.10.10.128/25。全部正确，得3分。
题目总分：1+1+3=5分
The road of your choice, you have to go on !
粤ICP备16082171号-1
