科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
某网络拓扑及各链路带宽如图所示。网络按电路交换方式运行时，主机\(\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[j]（j≥i）计算乘积并取最大值。这种思路虽然正确，但并不是题目要求的“时间和空间上尽可能高效的算法”，因为其时间复杂度为O(n²)，而标准答案提供了O(n)的线性算法。由于题目明确要求“尽可能高效”，学生的设计思想未能达到最优效率，因此不能给满分。但思路本身逻辑正确，可以给部分分数。扣2分，得2分。
（2）得分及理由（满分7分）
学生根据其设计思想给出了C语言代码实现，代码逻辑与其描述一致，能够正确计算出每个res[i]的值。但是，代码存在一个逻辑错误：初始化`max = A[i] * A[i];` 假设了最大乘积至少是A[i]自乘，这在一般情况下成立，但如果A[i]为负数且其后存在绝对值更大的负数，乘积可能更大，而自乘可能不是最大值。不过，由于内循环会遍历所有j≥i，最终仍能找到最大值，因此这个初始化错误不影响最终结果，但可能引入不必要的计算。此外，算法效率低（O(n²)），不符合“尽可能高效”的要求。考虑到代码实现了基本功能，但效率不佳且有小瑕疵，扣3分，得4分。
（3）得分及理由（满分2分）
学生正确分析了其算法的时间复杂度为O(n²)，空间复杂度为O(1)。这与标准答案的O(n)时间复杂度不同，但学生对自己算法的复杂度分析是正确的。因此给满分2分。
题目总分：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，与标准答案完全一致。虽然学生列出了拓扑序列、ve、vl等计算过程，但核心结论正确。根据打分要求，思路正确不扣分，额外分析不扣分。因此得3分。
（2）得分及理由（满分3分）
学生作答中未回答第（2）问。根据题目要求，每个问题独立评分，未作答不得分。因此得0分。
（3）得分及理由（满分2分）
学生作答中未回答第（3）问。根据题目要求，每个问题独立评分，未作答不得分。因此得0分。
（4）得分及理由（满分2分）
学生作答中未回答第（4）问。根据题目要求，每个问题独立评分，未作答不得分。因此得0分。
题目总分：3+0+0+0=3分
评分及理由
（1）得分及理由（满分3分）
学生答案：主存中Cache组号字段占6位，块内地址字段占6位。虚拟页大小4KB = 2¹²B，页偏移占12位，故虚拟地址中的第7~12位可做为Cache索引。
标准答案：组号6位，块内地址6位，虚拟地址的VA₁₁~VA₆（即第7~12位，从1开始计数）可作为Cache索引。
分析：学生答案与标准答案完全一致，组号、块内地址位数正确，虚拟地址索引位说明正确。
得分：3分
（2）得分及理由（满分2分）
学生答案：d[100]的虚拟地址为0180 0020H + 190H = 0180 01B0H，所在主存对应的Cache组号为6。
标准答案：虚拟地址为0180 01B0H，Cache组号为06H（即6）。
分析：虚拟地址计算正确（100*4=400=0x190，0x1800020+0x190=0x18001B0）。组号计算正确（地址低12位为页内偏移，其中VA₁₁~VA₆为索引，0x1B0的二进制为0001 1011 0000，取第7~12位（从右往左第7到12位，即从低到高第6到11位）为0110，即6）。
得分：2分
（3）得分及理由（满分5分）
学生答案：d[0]所在主存块内偏移量为020H。一个主存块存储16个元素，每个循环访问两次同一个元素，故每访问32个元素会缺失一次，缺失率≈3.13%，平均访问时间≈7.20个周期。
标准答案：偏移量20H。缺失率3.15%，平均访问时间8.3个周期。
分析：
① d[0]偏移量：d[0]虚拟地址0x1800020，低12位（页内偏移）为0x020，块内偏移取低6位（块大小64B=2^6）为0x20，正确。得1分。
② 缺失率计算逻辑：学生认为一个块16个元素，每个元素在循环中被访问两次（读d[i]和写d[i]），所以每32次访存发生一次缺失。但标准答案分析表明，数组d分布在129个主存块中，每个块的第一次读操作会缺失，共129次缺失，总访存次数为2048*2=4096次，缺失率=129/4096≈3.15%。学生用1/32≈3.125%近似，忽略了数组跨越129个块而非128个块（因为起始地址不是块对齐的），导致微小误差。但思路基本正确，且计算结果3.13%与3.15%非常接近，可视为计算误差，不扣分。得2分。
③ 平均访问时间：学生公式为平均时间=缺失率×200 + (1-缺失率)×2，但计算时写为“3.13÷100×200 + 2×96.87÷100”，其中“2×96.87÷100”实际是命中时间×(1-缺失率)，但数值计算错误：3.13%×200=6.26，2×96.87%=1.9374，和约为8.1974，但学生得到7.20，说明计算过程有误。应扣1分。
得分：1+2-1=2分
（4）得分及理由（满分2分）
学生答案：d分布在2页中，引起2次缺页。
标准答案：分布在3个页中，引起3次缺页。
分析：数组大小2048*4B=8192B=8KB，页大小4KB，需要2页，但起始地址0x1800020不是页对齐的（页内偏移0x020），因此数组可能跨越3个页。具体：第一页从0x1800000到0x1800FFF，包含从0x1800020到0x1800FFF的字节；第二页从0x1801000到0x1801FFF；第三页从0x1802000到0x1802FFF，但数组只用到0x1800020+0x2000-1=0x180201F，因此确实跨越3页。学生忽略了起始地址不对齐的影响，答案错误。
得分：0分
题目总分：3+2+2+0=7分
（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分）
学生答案中：
- 对于Y的初始内容，学生答“FFH”，即0xFF，这与标准答案中Y=0xfffffffe不符。标准答案中Y是除数x的补码，x=0xff，其32位补码应为0x000000ff，但图中Y是n+1位（33位），且根据除法算法（如不恢复余数法），Y应存放除数绝对值的补码形式，且位数与被除数扩展后一致。学生答案“FFH”可能只考虑了低8位，是错误的。
- 对于寄存器R内容，学生答“87654321H”，即被除数d[i]的值，但标准答案中R初始值为0xffffffff（即-1的补码）。在补码除法中，被除数需要符号扩展为双倍字长放在{R, Q}中，R初始应为被除数高位的符号扩展。学生答案错误。
- 对于Q内容，学生答“00000000H”，但标准答案中Q初始为0x87654321（即被除数低32位）。学生答案错误。
- 对于“哪个部件包含计数器”，学生答“控制逻辑”，这与标准答案“b中的控制逻辑包含计数器”一致，正确。
- 对于“ALU运算有几种”，学生答“两种”，这与标准答案“加法和减法”一致，正确。
因此，该部分共6分，其中计数器部分（1分）和ALU运算种类（1分）正确，得2分；其余部分（R、Q、Y初始值）均错误，扣4分。得分为2分。
（2）得分及理由（满分5分）
学生答案中：
- 对于除法异常情况，学生只提到“除数为0”一种情况（x=00000000H），并给出了d[i]的例子（87654321H）。但标准答案还要求指出溢出异常（d[i]=0x80000000, x=0xffffffff）。学生遗漏了溢出异常情况。
- 对于异常响应操作，学生未给出具体操作描述，答案不完整。
因此，该部分共5分，学生仅正确指出除数为0异常（给1分），但未说明溢出异常（扣2分），且未描述异常响应操作（扣2分）。得分为1分。
题目总分：2+1=3分
（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()函数代码位于只读代码段。对于第二部分“直接调用的哪些函数的功能需要通过执行驱动程序实现？”，标准答案为scanf和printf。学生第一次识别提到“printf, free”，第二次识别提到“printf、free”。free函数通常不涉及驱动程序，而scanf需要驱动程序。学生答案中包含了printf（正确）和free（不正确），且遗漏了关键的scanf。因此，该部分回答不完整且有错误。扣1分，得2分。
（3）得分及理由（满分3分）
学生答案正确指出变量ptr被分配在可读可写数据段（即标准答案的读/写数据段）。对于变量length，标准答案为若不在寄存器则位于用户栈段，但学生两次识别均回答在“可读可写数据段”，这是错误的。对于ptr指向的字符串，标准答案位于堆区，学生第一次识别回答在“可读可写数据段”，第二次识别回答在“只读数据段”，均错误。该小题共三个空，答对一个，扣2分，得1分。
题目总分：2+2+1=5分
（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.24s（即240ms），与标准答案一致，得1分。
最大吞吐量部分，学生计算为48kb/s或6KB/s，但标准答案为200kb/s（即信道的数据传输速率），此处逻辑错误，因为吞吐量受限于信道速率，不应乘以时延，扣1分。
传输4000B文件所需时间，学生计算为0.16s，忽略了传播时延，而标准答案为400ms（即0.24s传播时延+0.16s传输时间），逻辑错误扣1分。
本小题得1分。
（2）得分及理由（满分3分）
学生正确给出了单向传播时延和RTT，得基础分。
信道利用率公式正确，但计算窗口大小时，学生得到W_T≥32，而标准答案为8，计算逻辑错误，扣1分。
序号字段位数学生答案为6位，标准答案为4位，因窗口计算错误导致序号位数错误，扣1分。
本小题得1分。
（3）得分及理由（满分3分）
学生给出的三个子网地址与标准答案完全一致：生活区10.10.10.128/25，作业区10.10.10.0/26，管理区10.10.10.64/26。
每个子网地址正确得1分，共3分。
题目总分：1+1+3=5分
The road of your choice, you have to go on !
粤ICP备16082171号-1
