科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
某网络拓扑及各链路带宽如图所示。网络按电路交换方式运行时，主机\(\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分）
学生给出的基本设计思想是采用两层循环遍历，对于每个A[i]，通过内层循环计算A[i]与所有A[j]（j从0到n-1）乘积的最大值。虽然这种方法在功能上能够正确计算出结果，但题目要求“时间和空间上尽可能高效的算法”，而该算法的时间复杂度为O(n²)，并非高效解法。标准答案中给出了O(n)的线性扫描方法，更为高效。因此，学生的设计思想虽然正确但效率较低，根据评分要求“思路正确不扣分”，但考虑到题目明确要求“尽可能高效”，而学生未达到该要求，此处扣1分。得分为3分。
（2）得分及理由（满分7分）
学生给出的代码实现了两层循环遍历，对于每个i，内层循环j从0到n-1（实际应为j从i到n-1，因为题目要求0≤i≤j≤n-1，但学生代码中j从0开始，这会导致计算了i>j的情况，属于逻辑错误）。此外，代码中使用了未定义的常量“-INF”，应使用标准库中的INT_MIN或类似的最小值定义。由于存在逻辑错误（j的起始条件错误）和代码不完整（未定义INF），根据打分要求“逻辑错误扣分”，此处扣3分。得分为4分。
（3）得分及理由（满分2分）
学生正确分析了算法的时间复杂度为O(n²)和空间复杂度为O(1)，与代码实现一致。虽然该复杂度并非最优，但分析正确，因此不扣分。得分为2分。
题目总分：3+4+2=9分
（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同时进行的有c、d、b。与标准答案“b、c、d”一致（顺序无关）。得3分。
（3）得分及理由（满分2分）
学生答案：时间余量最大的为j，余量为6。与标准答案完全一致。得2分。
（4）得分及理由（满分2分）
学生答案第一部分：“b的持续时间为3”。标准答案为“b的持续时间最多是4”。学生答案错误。该问包含两个小问，第一小问错误，扣1分。
学生答案第二部分：“压缩k的持续时间可以保证不延期”。与标准答案一致。第二小问正确，得1分。
本小题总计得1分。
题目总分：3+3+2+1=9分
评分及理由
（1）得分及理由（满分3分）
学生答案：主存地址中cache组号占6位，块内地址也占6位。VA中cache组号可做为索引。
标准答案：Cache组号字段为6位，块内地址字段为6位。虚拟地址中VA₁₁~VA₆可作为Cache索引。
评分分析：学生正确回答了主存地址中Cache组号和块内地址的位数（各6位），得2分。对于虚拟地址中哪些位可作为Cache索引，学生回答“VA中cache组号可做为索引”，表述模糊，未明确指出是虚拟地址的低12位中的哪几位（即VA₁₁~VA₆）。考虑到题目要求虚拟地址中哪些位可作为索引，学生答案未达到精确要求，扣1分。
得分：2分
（2）得分及理由（满分2分）
学生答案：d[100]的VA = 01800020H + 100×4 = 018001B0H，cache组号为6。
标准答案：d[100]的虚拟地址为0180 01B0H，Cache组号是06H。
评分分析：学生正确计算了d[100]的虚拟地址（018001B0H），得1分。对于Cache组号，学生答案为“6”，标准答案为“06H”。在数值上“6”与“06H”等价，且题目未要求必须用十六进制表示，因此不扣分。学生答案正确。
得分：2分
（3）得分及理由（满分5分）
学生答案：偏移量为16 B，缺失129次，一共访问了4096次。P(缺失率) = 129/4096×100%。访问时间 = [(1 - P)×2 + P×200]×4096 = 33734个时钟周期。
标准答案：d[0]在其所在主存块内的偏移量是20H。Cache缺失率≈ 3.15%；平均访问时间=2+200p=8.3个时钟周期。
评分分析：
1. 偏移量：学生答案为“16 B”，标准答案为“20H”。20H（十六进制）= 32（十进制），即32字节。由于主存块大小为64B，块内地址占6位，可寻址0-63字节。d[0]的虚拟地址为0180 0020H，低6位（块内偏移）为20H（即32）。学生答案“16 B”错误，扣1分。
2. 缺失率：学生正确识别出缺失次数为129次，总访问次数为2048次读+2048次写=4096次，并给出了缺失率计算公式129/4096×100%，思路正确。但未计算出百分比数值（3.15%）。题目要求“计算结果要求用百分比表示，保留两位小数”，学生未给出计算结果，扣1分。
3. 平均访问时间：学生计算了总访问时间（33734个时钟周期），但题目问的是“数组元素的平均访问时间”，即每次访存的平均时间。学生用总时间除以总访问次数（33734/4096≈8.24）可得到平均时间，与标准答案（8.3）接近，但表述为“访问时间 = ... = 33734个时钟周期”不符合题目所问。扣1分。
此外，学生未区分“平均访问时间”与“总访问时间”，且计算过程未体现平均访问时间公式（2+200p），存在逻辑表述不完整的问题。
得分：2分（缺失次数和总访问次数正确得1分，缺失率公式正确得1分，其余部分有误）
（4）得分及理由（满分2分）
学生答案：d分布在3个页中，访问d所引起的缺页次数为3次。
标准答案：数组d分布在3个页中，缺页次数为3次。
评分分析：学生答案完全正确。
得分：2分
题目总分：2+2+2+2=8分
（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的初始值：第一次识别为0xFFFFFFFF，第二次识别为0xFFFFFFFF。这与标准答案（0xffffffff）一致，正确。
- Q的初始值：第一次识别未给出，第二次识别为0xFFFFFFFF。标准答案为0x87654321。学生答案错误。根据指令流程，`scov R1`将R1符号扩展为64位存入{R0,R1}，R0为符号扩展的高32位，R1为原值。在除法器初始化时，被除数的高32位（R0）应放入R寄存器，低32位（R1）应放入Q寄存器。因此Q应为d[i]的原值0x87654321。此处逻辑错误，扣2分。
- Y的初始值：第一次识别为0x87654321，第二次识别为0x87654321。标准答案为0xfffffffe。Y寄存器应存放除数x（R2）的值。题目给出x=0xff，这是一个8位立即数，在执行idiv指令时，需要将其符号扩展为32位。0xff（二进制11111111）符号扩展后为0xffffffff。但标准答案给出的是0xfffffffe，这可能是题目或答案有特殊设定（如x=0xff，但R2中实际存放的是0xfffffffe？）。然而，根据学生作答上下文，其将Y识别为被除数d[i]的值，这是对寄存器功能理解的根本性错误。此处逻辑错误，扣2分。
- 计数器位置：两次识别均指出“图b中Cn包含计数器”。标准答案为“b中的控制逻辑包含计数器”。学生答案基本正确，得1分。
- ALU运算种类：两次识别均指出有加、减法。标准答案为“包含加法和减法”。正确，得1分。
本小题扣分点：Q和Y的初始值错误，各扣2分。其余部分正确。
得分：1（计数器）+ 1（ALU运算）= 2分。
（2）得分及理由（满分5分）
学生答案中：
- 除法异常情况1：两次识别均提到“当Y的值为0时触发异常”。这对应除数为0的情况，思路正确。但表述中“Y的值”应为除数（即x）的值。考虑到识别和表述可能不精确，且核心逻辑（除数为0）正确，不扣分。
- 除法异常情况2：第一次识别为“当Y的值为 0x800000时, Q的值为 0xfffffff时”；第二次识别为“当Y的值为0X800000时，Q的值为0Xffffffff时”。这试图描述溢出异常，即被除数为最小负数（-2^31）且除数为-1的情况。标准答案中，d[i]（被除数低32位，即Q初始值）为0x80000000，x（除数，即Y初始值）为0xffffffff。学生答案中数值（0x800000, 0xfffffff/0xffffffff）存在识别不全或错误，但基本指向了正确的组合。根据“禁止扣分”原则，对于识别错误（如少写0）导致的逻辑错误不扣分。因此，此部分思路正确，得相应分数。
- 异常响应操作：两次识别均列出“① 关中断 ② 保存断点 ③ 引向中断服务程序”。这与标准答案“关中断，修改CPU状态为内核态。保存断点（PC和PSWR中的值）。跳转到异常处理程序。”在核心步骤上一致。学生答案未明确提及“修改CPU状态为内核态”，但“引向中断服务程序”包含了跳转的含义。考虑到回答的完整性，此处扣1分。
本小题扣分点：异常响应操作描述不够完整，扣1分。
得分：4分。
题目总分：2+4=6分
评分及理由
（1）信号量定义及初值（满分约2分）
学生定义了四个信号量：empty=3（对应可挖坑数量）、mutex=1（铁锹互斥）、full=0（对应已挖坑未种树）、full2=0（对应已种树待浇水）。与标准答案相比，思路基本正确，但命名与标准答案不完全一致（标准答案用 sk、empty、water），这并不扣分。信号量初值设置合理，符合题意“树坑数量小于3时甲才可以挖坑”（初始 empty=3 表示最多可挖3个坑，相当于标准答案的 sk=3）。此处没有逻辑错误，但学生将 empty 用于表示可挖坑数，而标准答案中 empty 表示可使用的树坑数（即已挖坑未种树），两者含义相反但配合后续 wait/signal 使用仍能构成同步关系，属于思路正确但命名习惯不同，不扣分。因此本部分给满分2分。
（2）甲、乙、丙三人的同步互斥实现（满分约4分）
甲：正确使用 wait(empty) 限制挖坑数量不超过3，wait(mutex) 获取铁锹，挖坑后 signal(mutex) 释放铁锹，signal(full) 通知乙有坑可种。逻辑正确，得1.5分。
乙：在第一次识别中，乙的代码有错误：wait(full) 后 wait(mutex) 正确，但操作后 signal(mutex) 正确，却 signal(full) 错误（应为 signal(empty) 或类似表示坑位释放的信号，以允许甲继续挖坑），且缺少对丙的通知（应 signal(full2)）。第二次识别中乙的代码修正为：wait(full)、wait(mutex)、填土、signal(mutex)、signal(full)、signal(full2)。这里 signal(full) 明显错误，因为 full 表示已挖坑未种树，乙种树后应增加可挖坑数（即 signal(empty)），而不是继续 signal(full)。这会导致同步逻辑混乱：乙种树后没有释放坑位资源，甲可能无法继续挖坑；同时乙向 full 发送信号可能导致乙自己重复执行。这是一个逻辑错误，扣1分。但乙正确使用了 mutex 保护铁锹，并正确 signal(full2) 通知丙浇水，这部分正确不扣分。
丙：第一次识别中丙的代码有严重错误：wait(full2) 后浇水，但后面有“3”和 signal(mutex)、signal(full2)，明显是识别杂音或错误。第二次识别中丙的代码正确：wait(full2) 后浇水，没有多余操作，符合同步要求。根据“两次识别中只要有一次正确则不扣分”的原则，丙的实现不扣分，得1分。
此外，整体流程能体现挖坑、种树、浇水的顺序，但乙中的 signal(full) 错误影响同步正确性。因此本部分扣1分，得3分（甲1.5 + 乙0.5 + 丙1）。
（3）信号量作用说明（满分约1分）
学生没有在代码注释中完整说明每个信号量的作用，仅在 mutex 处注明“铁锹的互斥”。题目要求“说明所用信号量的作用及其初值”，学生只给出了初值，没有完整说明作用，因此扣0.5分。得0.5分。
题目总分：2+3+0.5=5.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位于内核区，执行scanf等待输入时进程处于阻塞态。与标准答案完全一致。得2分。
（2）得分及理由（满分3分）
学生答案存在部分错误。main()函数的代码应位于只读代码段（.text），而非“共享库的存储映射区”，此部分逻辑错误。但学生正确指出了scanf和printf需要调用系统函数（或执行驱动程序），这部分正确。因此，针对“main()函数的代码位于哪个区域？”扣1分；针对“其直接调用的哪些函数的功能需要通过执行驱动程序实现？”得2分。本小题得2分。
（3）得分及理由（满分3分）
学生答案完全正确。ptr作为全局变量位于读写数据段；length作为局部变量（若不在寄存器）位于用户栈；ptr指向的字符串由malloc分配，位于堆区。与标准答案完全一致。得3分。
题目总分：2+2+3=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分）
学生答案中：单向传播时延240ms正确；最大吞吐量200Kb/s正确（标准答案为200 kb/s，单位识别为Kb/s可视为等价）；传输时延计算160ms正确；总时间400ms正确。因此该小题得满分3分。
（2）得分及理由（满分3分）
学生答案中：计算发送窗口n=8正确；但序号位数推导有误。学生写的是“序号 $2^{n}-1 = 8$ $\Rightarrow n = 4$”，这里n既代表窗口大小又代表位数，符号混用，但最终得到序号至少4位是正确的（标准答案也是4位）。虽然推导过程不严谨（GBN应满足$2^k \ge W_s+1$，学生用了$2^n-1=8$，实际$2^4-1=15$，不等于8），但最终结果正确，且题目要求“至少需要多少位”，答案正确。考虑到识别可能带来的符号混淆，且最终答案正确，不扣分。得满分3分。
（3）得分及理由（满分3分）
学生答案只给出了两个子网：作业区10.10.10.64/26和生活区10.10.10.128/25，缺少管理区子网。标准答案要求三个子网地址各1分。因此只能给2分（作业区和生活区正确）。管理区子网缺失，扣1分。
题目总分：3+3+2=8分
The road of your choice, you have to go on !
粤ICP备16082171号-1
