科目组合
计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
某网络拓扑及各链路带宽如图所示。网络按电路交换方式运行时，主机\(\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] ≤ 0 则乘以全局最小值，若 A[i] > 0 则乘以全局最大值，结果存入 res[i]。
然而，这个思路是错误的。因为题目要求的是对于每个 A[i]，计算 A[i] 与 A[j]（i ≤ j ≤ n-1）乘积的最大值，即只考虑 i 及其右侧的元素。学生的做法使用了全局的最大最小值，忽略了 j 必须 ≥ i 的限制，因此逻辑错误。
例如，对于 A = {1, 4, -9, 6}，按照学生的算法：全局最大值 max=6，全局最小值 min=-9。计算 res[0] 时，A[0]=1>0，res[0]=1*6=6（正确，但这是巧合，因为全局最大值恰好在右侧）；计算 res[1] 时，A[1]=4>0，res[1]=4*6=24（正确，巧合）；计算 res[2] 时，A[2]=-9≤0，res[2]=-9*(-9)=81（正确，巧合，因为全局最小值恰好在右侧且就是自身）；计算 res[3] 时，A[3]=6>0，res[3]=6*6=36（正确，巧合）。虽然这个例子巧合地得到了正确结果，但算法本身是错误的。考虑另一个例子 A = {5, -1, 2}，正确结果应为 res = {10, -2, 2}（因为对于 i=0，最大乘积是 5*2=10；i=1，最大乘积是 -1*(-1)=1 或 -1*2=-2，取最大值 1？等等，这里需要仔细计算：对于 i=1，A[1]=-1，右侧元素有 -1 和 2，乘积分别为 1 和 -2，最大值是 1；但学生的算法：全局最大值 max=5，全局最小值 min=-1，res[0]=5*5=25（错误，应为 10），res[1]=-1*(-1)=1（正确），res[2]=2*5=10（错误，应为 2）。显然错误。
因此，学生的设计思想存在逻辑错误，不能得分。扣4分。
得分：0分
（2）得分及理由（满分7分）
学生根据错误的设计思想写出了代码。代码本身语法正确，但算法逻辑错误，原因同上：没有考虑 j 必须 ≥ i 的限制，错误地使用了全局最大最小值。
由于设计思想错误，代码实现也错误，因此不能得分。扣7分。
得分：0分
（3）得分及理由（满分2分）
学生给出的时间复杂度 O(n) 和空间复杂度 O(1) 是基于其错误算法分析的，虽然分析本身对于其算法是正确的，但由于算法整体错误，因此不能得分。扣2分。
得分：0分
题目总分：0+0+0=0分
（10分）某工程包含12个活动，使用下图所示的AOE网描述，图中各边上标注了活动及其持续时间。
请回答下列问题（活动均用活动名表示）。
（1）完成该工程的最短时间是多少？哪些活动是关键活动？（3分）
（2）若以最短时间完成工程，则与活动e同时进行的活动可能有哪些？（3分）
（3）时间余量最大的活动是哪个？其时间余量是多少？（2分）
（4）假设工程从时刻0启动，因某种原因，活动b在时刻6开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，b的持续时间最多是多少？若不改变b的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？（2分）（注意，无过程或原因要求可以只写答案）
评分及理由
（1）得分及理由（满分3分）
第1次识别结果中“最短时间”为“1, 2, 3”，这显然是识别错误（可能将“12”识别为三个数字）。第2次识别结果为“12”，且关键活动为“a, e, m, n”，与标准答案完全一致。根据“禁止扣分”规则第3条，只要其中一次识别正确则不扣分。因此，本题答案正确，得3分。
（2）得分及理由（满分3分）
两次识别结果均为“b, c, d”，与标准答案完全一致。得3分。
（3）得分及理由（满分2分）
第1次识别结果为“j, 其整为6”，其中“其整”应为“余量”的识别错误，但活动“j”和数字“6”正确。第2次识别结果为“丁， 流量为6”，其中“丁”应为“j”的识别错误，“流量”应为“余量”的识别错误。核心信息（活动j，余量6）在两次识别中均能对应正确信息。根据“禁止扣分”规则，此类识别错误不扣分。因此，本题答案正确，得2分。
（4）得分及理由（满分2分）
两次识别结果均为“4; k”和“4, k”，与标准答案“b的持续时间最多是4”和“可以压缩活动k”完全一致。得2分。
题目总分：3+3+2+2=10分
评分及理由
（1）得分及理由（满分3分）
学生答案：组号6位，块内地址6位，Cache索引VA6~VA11。
标准答案：组号6位，块内地址6位，Cache索引VA11~VA6（或VA6~VA11，顺序不影响）。
分析：学生答案与标准答案完全一致。组号计算正确（32KB/(64B*8)=64组，需6位），块内地址因块大小64B需6位，Cache索引使用虚拟地址的VA11~VA6（页内地址12位中的高6位）也正确。
得分：3分。
（2）得分及理由（满分2分）
学生答案：虚拟地址0180 01B0H；Cache组号2号。
标准答案：虚拟地址0180 01B0H；Cache组号06H（即十进制6）。
分析：虚拟地址计算正确（起始地址0180 0020H + 100*4 = 0180 01B0H）。但Cache组号计算有误。根据（1）中结论，Cache索引为VA11~VA6，对于地址0180 01B0H（二进制... 0001 1011 0000），取VA11~VA6（即第6到11位）应为000110（二进制）= 06H（十进制6）。学生答“2号”可能是计算错误或识别错误（如将“6”误识别为“2”）。根据禁止扣分规则，若判断为误写（如6误写为2）可不扣分，但此处学生两次识别结果均为“2号”，且与计算逻辑不符，应视为逻辑错误。因此扣1分。
得分：1分。
（3）得分及理由（满分5分）
学生答案：偏移量20H（仅第二次识别给出）；Cache缺失率3.15%（第一次）或3.5%（第二次）；平均访问时间8.24个时钟周期。
标准答案：偏移量20H；Cache缺失率3.15%；平均访问时间8.3个时钟周期。
分析：
①偏移量：d[0]的虚拟地址为0180 0020H，主存块大小64B=40H，块内偏移为地址低6位（即模64），20H mod 40H = 20H，正确。但学生仅在第二次识别中给出，第一次未给出。根据问题要求，需计算偏移量，若缺失应扣分。但考虑到识别可能遗漏，且第二次给出正确，此处不扣分。
②Cache缺失率：标准答案为3.15%。学生第一次识别为3.15%正确；第二次为3.5%错误。根据禁止扣分规则，以正确的一次为准，不扣分。
③平均访问时间：标准计算为2 + 200p = 2 + 200*3.15% = 8.3。学生答案为8.24，与使用p=3.15%计算结果（8.3）不一致，可能是计算过程取整误差或使用了错误p值（如3.5%得9.0）。但学生缺失率以3.15%计，平均时间应为8.3，8.24存在偏差，属计算错误，扣1分。
得分：4分（偏移量正确不扣，缺失率以正确计不扣，平均时间错误扣1分）。
（4）得分及理由（满分2分）
学生答案：3个页中；引起3次缺页。
标准答案：3个页；3次缺页。
分析：完全正确。数组大小2048*4B=8192B，页大小4KB，需2页余，加上起始地址偏移（0180 0020H页内偏移20H），共跨越3页。初始未调入主存，访问会引发3次缺页。
得分：2分。
题目总分：3+1+4+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的初始值：学生答“0000 0000H”，标准答案为“0xffffffff”。根据补码除法（不恢复余数法）的初始化规则，被除数d[i]=0x87654321（负数）需要符号扩展至高32位，即R应初始化为d[i]的符号位扩展，所以应为全1（0xffffffff）。学生答案错误。
- Q的初始值：学生答“8765 4321H”，与标准答案一致，正确。
- Y的初始值：学生答“FFFF FFFFH”，标准答案为“0xfffffffe”。Y中存放除数x的补码，x=0xff（即+255），其32位补码应为0x000000ff，但根据图中结构，Y可能存放的是除数左移一位（或取负等）？标准答案给出的是0xfffffffe（即-2的补码），这可能是对除数进行某种处理（如取负或左移）后的结果。学生答案与标准答案不符，且未体现处理过程，判断为错误。
- 计数器位置：学生答“控制逻辑包含计数器”，与标准答案“b中的控制逻辑包含计数器”一致，正确。
- ALU运算种类：学生答“加法、减法”，与标准答案一致，正确。
扣分：R和Y的初始值错误，各扣1分；其余部分正确。本小题满分6分，扣2分，得4分。
（2）得分及理由（满分5分）
学生答案中：
- 除法异常情况：
① 除0异常：学生提到，正确。
② 最小数除以-1异常：学生提到“最小数有除 -1异常”，并给出了d[i]=1000 0000H（即-2^31），x=FFFF FFFFH（即-1），与标准答案一致，正确。但学生额外写了“x: 0000 0001H”，可能是识别错误或笔误，根据禁止扣分原则，不扣分。
- CPU异常响应操作：学生答“关中断、保存断点(PC和PSW内容)、中断服务程序入口地址寻址”，与标准答案“关中断，修改CPU状态为内核态；保存断点（PC和PSWR中的值）；跳转到异常处理程序”基本一致，但缺少“修改CPU状态为内核态”这一项。标准答案中该操作是隐含或必要的，学生未提及，扣1分。
本小题满分5分，扣1分，得4分。
题目总分：4+4=8分
评分及理由
（1）信号量定义及初值（满分约2分）
得分：2分
理由：学生定义了四个信号量，与标准答案完全对应（尽管命名不同）：tieqiao（对应mutexT，互斥使用铁锹，初值1）、wakeng（对应sk，控制可挖坑数，初值3）、keng（对应empty，表示可用坑数，初值0）、jiaoshui（对应water，表示待浇水树苗数，初值0）。信号量作用说明清晰，初值正确。因此该部分得满分。
（2）甲进程的同步互斥实现（满分约2分）
得分：2分
理由：甲进程的逻辑与标准答案一致。先wait(wakeng)确保坑数小于3才可挖，再wait(tieqiao)获取铁锹，挖坑后释放铁锹并signal(keng)通知乙有坑可用。逻辑正确无误。
（3）乙进程的同步互斥实现（满分约2分）
得分：1分
理由：乙进程的整体框架正确，但存在一处逻辑错误。在第二次识别结果中，乙进程在“放树苗”后立即signal(wakeng)，这不符合题意。根据题目，乙的步骤是“放树苗入坑并填土”，填土需要使用铁锹，且填土完成后才应释放一个可挖坑名额（即signal(wakeng)）。标准答案中，signal(sk)是在填土并释放铁锹之后执行的。学生答案中signal(wakeng)提前到填土之前，会导致甲可能在乙填土完成前就又开始挖坑，虽然由于铁锹互斥可能不会产生严重错误，但逻辑顺序与题目描述的流程不符，属于逻辑错误。扣1分。其余部分（wait(keng)、获取释放铁锹、signal(jiaoshui)）正确。
（4）丙进程的同步互斥实现（满分约1分）
得分：1分
理由：丙进程的逻辑正确。wait(jiaoshui)等待浇水信号，浇水后循环。在第二次识别结果中完全正确。第一次识别结果中丙的代码有误（浇水后V(jiaoshui)），但根据“两次识别只要一次正确则不扣分”的原则，此处不扣分。
题目总分：2+2+1+1=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()时进程处于阻塞态。
学生答案中“内核态”是对“内核区”的误写或表述不精确，但结合上下文可以判断其意指PCB位于内核区域，核心逻辑正确。关于进程状态，回答“阻塞态”完全正确。
因此，本小题得分为2分。
（2）得分及理由（满分3分）
学生第一次识别结果存在明显识别错误（“大读写不可栈”），但第二次识别结果为“只读代码段；scanf()，printf()”。
标准答案：main()函数的代码位于只读代码段，其直接调用的scanf()和printf()需要执行驱动程序。
学生第二次识别的答案与标准答案完全一致，思路和内容均正确。
因此，本小题得分为3分。
（3）得分及理由（满分3分）
学生两次识别结果均为：“可读写数据段；用户栈；运行时堆”。
标准答案：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.24s（应为240ms，但0.24s=240ms，数值正确），最大吞吐量200kb/s（正确），最少时间400ms（正确）。第二次识别结果中单向传播时延为0.024s（错误，应为0.24s），但根据“两次识别只要有一次正确则不扣分”的原则，且第一次识别结果完全正确，因此本题得3分。
（2）得分及理由（满分3分）
学生两次识别结果均给出：发送窗口至少为8，序号字段至少4位。这与标准答案完全一致。因此本题得3分。
（3）得分及理由（满分3分）
学生第一次识别结果：作业段子网: 10.10.10.64/26（正确），管理段子网: 10.10.10.0/26（正确），监控段子网: 10.10.10.128/25（正确）。其中“作业段”、“管理段”、“监控段”应为“作业区”、“管理区”、“生活区”，但根据上下文判断为识别或书写问题，且CIDR地址形式完全正确。第二次识别结果中的地址错误，但依据“两次识别只要有一次正确则不扣分”的原则，本题得3分。
题目总分：3+3+3=9分
The road of your choice, you have to go on !
粤ICP备16082171号-1
