2026年计算机练习题及解析附答案

2026年计算机练习题及解析附答案一、单项选择题（每题2分，共40分）1.已知某完全二叉树有127个节点，其中度为1的节点数量是（）A.0B.1C.63D.64解析：完全二叉树节点数n=2^h-1时为满二叉树，此时所有节点度为0或2。127=2^7-1，说明该树是满二叉树，不存在度为1的节点。答案：A2.对序列（5,3,7,2,8,4,6,1）进行快速排序，以第一个元素为基准，一次划分后的结果是（）A.(1,3,2,4,5,8,6,7)B.(3,2,4,1,5,8,7,6)C.(4,3,2,1,5,8,7,6)D.(2,3,4,1,5,8,7,6)解析：快速排序一次划分过程：基准5，左指针i=0，右指针j=7（值1）。j左移找比5小的元素（1,4,2,3），i右移找比5大的元素（7,8）。交换i=2（7）和j=3（2）→序列变为(5,3,2,7,8,4,6,1)；继续i=3（7）>5，j=6（6）>5→j=5（4）<5，交换i=3（7）和j=5（4）→(5,3,2,4,8,7,6,1)；i=4（8）>5，j=7（1）<5，交换i=4（8）和j=7（1）→(5,3,2,4,1,7,6,8)；此时i=5（7）>5，j=4（1）<5，i>j，交换基准5和j=4（1）→(1,3,2,4,5,7,6,8)。但选项中无此结果，实际正确划分应为所有小于5的在左，大于的在右。原序列中小于5的元素是3,2,4,1（共4个），大于的是7,8,6（3个），正确划分后基准5位于第4位（索引4），左侧为(3,2,4,1)，右侧为(7,8,6)，即序列为(3,2,4,1,5,7,8,6)。选项B符合。答案：B3.某32位计算机的虚拟地址空间为4GB，页大小为4KB，页表项大小为4B。若采用三级页表，且顶级页表占1页，则中间页表和次级页表的页内偏移分别需要（）位。A.10,10B.10,12C.12,10D.12,12解析：虚拟地址32位，页大小4KB=2^12B，页内偏移12位。剩余20位用于页号。三级页表结构：顶级页表项数=1页/4B=1024项（2^10），占10位；剩余20-10=10位，中间页表和次级页表各占10位。答案：A4.下列关于TCP流量控制的描述中，错误的是（）A.接收方通过窗口字段通知发送方可发送的最大数据量B.窗口大小为0时，发送方会启动持续计时器C.窗口大小可以动态调整以适应网络带宽变化D.流量控制通过滑动窗口机制实现，与拥塞控制无关解析：流量控制关注接收方缓存能力，拥塞控制关注网络拥塞程度，但两者都通过调整窗口大小实现，存在关联（如拥塞时窗口可能被限制）。选项D错误。答案：D5.某计算机主存容量为8GB，采用字节编址，Cache采用4路组相联映射，块大小为64B，Cache容量为256KB。主存地址中，组号字段的位数是（）A.10B.12C.14D.16解析：Cache容量256KB=2^18B，块大小64B=2^6B，总块数=2^18/2^6=2^12块。4路组相联，组数=2^12/4=2^10组，组号需10位。主存地址格式：标记+组号+块内偏移（6位）。答案：A二、综合应用题（共60分）1.（15分）已知无向图G的邻接表如下（顶点编号1-5，边按输入顺序存储）：顶点1：2→3→4顶点2：1→3→5顶点3：1→2→5顶点4：1→5顶点5：2→3→4（1）画出G的邻接矩阵。（2）写出从顶点1出发的广度优先搜索（BFS）序列（队列优先访问编号小的顶点）。（3）判断G是否为欧拉图，说明理由。解析：（1）邻接矩阵（行/列1-5）：[0,1,1,1,01,0,1,0,11,1,0,0,11,0,0,0,10,1,1,1,0]（2）BFS过程：队列初始{1}，访问1→出队，邻接顶点2、3、4（按顺序，选小的），入队顺序2、3、4→队列{2,3,4}。访问2→出队，邻接顶点1（已访问）、3（未访问）、5（未访问），入队5→队列{3,4,5}。访问3→出队，邻接顶点1（已访问）、2（已访问）、5（未访问？5未被访问过吗？此时5在队列中但未访问）→无新顶点。访问4→出队，邻接顶点1（已访问）、5（未访问），但5已在队列→无新顶点。访问5→出队，邻接顶点2（已访问）、3（已访问）、4（已访问）。最终序列：1,2,3,4,5。（3）欧拉图要求所有顶点度数为偶数。计算各顶点度数：1-3度（邻接2、3、4），2-3度（邻接1、3、5），3-3度（邻接1、2、5），4-2度（邻接1、5），5-3度（邻接2、3、4）。存在多个奇数度顶点（1、2、3、5），故不是欧拉图。2.（15分）某操作系统采用可变分区管理，内存分配采用首次适应算法。初始内存空闲分区为[100KB,200KB]（起始地址100，大小200）。依次执行以下请求：（1）进程A申请150KB（2）进程B申请80KB（3）进程A释放150KB（4）进程C申请120KB（5）进程B释放80KB（1）画出每次操作后的内存分配图（用地址-大小表示空闲分区）。（2）若将首次适应算法改为最佳适应算法，第（4）步进程C申请120KB时是否能分配？说明理由。解析：（1）初始空闲分区：[100,200]（地址100，大小200）。①进程A申请150KB：首次适应找到第一个足够分区（100-200），分配后剩余[250,50]（地址250，大小50）。②进程B申请80KB：扫描空闲分区[250,50]（不足），无其他分区？初始内存总大小应为100+200=300KB？可能初始空闲分区是[0,300]？题目描述可能有误，假设初始空闲分区为[0,300]（更合理）。重新计算：初始空闲：[0,300]。①A申请150KB→分配[0,150]，剩余[150,150]。②B申请80KB→首次适应找到[150,150]，分配[150,80]，剩余[230,70]。③A释放150KB→合并相邻空闲区，[0,150]和[150,80]不相邻（中间是A的150KB？释放A后，空闲区为[0,150]和[230,70]。④C申请120KB→首次适应扫描[0,150]（足够），分配[0,120]，剩余[120,30]，空闲区为[120,30]和[230,70]。⑤B释放80KB→原B占用[150,80]（地址150-230），释放后与[120,30]（地址120-150）相邻，合并为[120,110]（30+80=110），空闲区为[120,110]和[230,70]。（2）最佳适应算法下，第④步时空闲分区为[0,150]（A释放的）和[230,70]（B分配后的剩余）。C申请120KB，最佳适应选择最小足够的分区，即[0,150]（150≥120），可以分配。3.（15分）某网络拓扑如下：主机A（IP:192.168.1.2/24）→路由器R1（接口E0:192.168.1.1/24，E1:10.0.0.1/24）→路由器R2（接口E0:10.0.0.2/24，E1:172.16.0.1/16）→主机B（IP:172.16.100.5/16）。（1）主机A发送数据到主机B，源MAC地址和目的MAC地址在R1的E0接口时分别是什么？（2）R1收到数据后，如何确定转发接口？（3）若R2的E1接口MTU为1500B，数据报总长度为2000B（首部20B），需要分片吗？若需要，写出分片后的标识、标志位、片偏移字段。解析：（1）主机A发送到R1的E0接口，源MAC是A的MAC地址，目的MAC是R1的E0接口MAC地址（ARP解析得到）。（2）R1的路由表需包含172.16.0.0/16的目标网络，下一跳为R2的E0接口（10.0.0.2），出接口为E1（10.0.0.1）。R1根据目的IP172.16.100.5匹配路由表，选择E1接口转发。（3）MTU=1500B，IP首部20B，数据部分最大1480B。原数据报数据部分1980B（2000-20）。需要分片：第一片：标识同原数据报，MF=1，片偏移=0，数据长度1480B（总长度=1480+20=1500B）。第二片：标识同原，MF=1，片偏移=1480/8=185，数据长度1480B（总长度=1480+20=1500B）。第三片：MF=0，片偏移=(1480×2)/8=370，数据长度1980-1480×2=20B（总长度=20+20=40B）。4.（15分）某计算机CPU主频为2GHz，采用5段指令流水线（取指IF、译码ID、执行EX、访存MEM、写回WB），各段耗时均为1ns。假设不存在结构相关，数据相关采用转发技术处理，分支指令占比15%，分支预测准确率80%，预测错误时需冲刷3个流水线寄存器。（1）计算流水线的加速比（相对于非流水线）。（2）计算流水线的实际CPI（考虑分支预测）。（3）若将流水线改为6段，每段耗时0.8ns，分支预测错误时冲刷4个寄存器，其他参数不变，是否提高性能？解析：（1）非流水线执行n条指令时间：n×5×1ns=5nns。流水线执行时间：(5+n-1)×1ns=(n+4)ns。加速比=5n/(n+4)，当n→∞时，加速比≈5。（2）CPI=1（理想）+分支带来的stall。分支占比15%，预测错误率20%，每次错误冲刷3个周期（即3个stall）。实际CPI=1+0.15×0.2×3=1+0.09=1.09。（3）6段流