2025年计算机考试的重难点试题及答案

2025年计算机考试的重难点试题及答案一、数据结构与算法1.（综合题）已知一棵二叉树的中序遍历序列为DBEAFCG，后序遍历序列为DEBFGCA。（1）画出该二叉树的结构；（2）写出其先序遍历序列；（3）设计非递归算法实现该二叉树的后序遍历，要求用栈结构，给出伪代码。答案：（1）二叉树结构：根节点为A，左子树中序序列DBE，后序序列DEB，故左子树根为B；B的左子树中序D，后序D，故左孩子D；B的右子树中序E，后序E，故右孩子E。右子树中序FCG，后序FGC，根为C；C的左子树中序F，后序F，左孩子F；C的右子树中序G，后序G，右孩子G。结构如下：```A/\BC/\/\DEFG```（2）先序遍历序列：ABDECFG。（3）非递归后序遍历伪代码：```voidpostOrder(BiTreeT){StackS;BiTreep=T,r=NULL;//r记录最近访问的节点while(p||!isEmpty(S)){if(p){//向左走到最左push(S,p);p=p>lchild;}else{getTop(S,p);//取栈顶if(p>rchild&&p>rchild!=r){//右子树存在且未访问p=p>rchild;}else{//访问当前节点visit(p);pop(S);r=p;//记录最近访问的节点p=NULL;}}}}```二、操作系统2.（应用题）某系统有同类资源12个，供3个进程P1、P2、P3共享。已知各进程的最大需求、已分配资源数如下表：|进程|最大需求|已分配||||||P1|5|2||P2|6|4||P3|8|3|（1）计算各进程的剩余需求；（2）判断当前系统是否处于安全状态，若安全给出安全序列；若不安全说明理由。答案：（1）剩余需求=最大需求已分配，故P1:52=3；P2:64=2；P3:83=5。（2）系统剩余资源=总资源已分配总和=12(2+4+3)=3。需求矩阵Need=[3,2,5]，可用资源向量Available=[3]。安全性检查步骤：初始Work=Available=3，Finish=[False,False,False]。寻找满足Need≤Work的进程：P2的Need=2≤3，分配后Work=Work+Allocation[P2]=3+4=7，Finish[P2]=True。下一轮Work=7，寻找Need≤7的进程：P1的Need=3≤7，分配后Work=7+2=9，Finish[P1]=True。下一轮Work=9，P3的Need=5≤9，分配后Work=9+3=12，Finish[P3]=True。所有进程Finish均为True，系统处于安全状态，安全序列为P2→P1→P3（或P2→P3→P1等，只要满足顺序）。三、计算机网络3.（分析题）TCP连接建立过程中，主机A（IP:192.168.1.100）向主机B（IP:192.168.1.200）发起连接请求，初始序列号（ISN）分别为x和y。（1）画出三次握手的报文交互图，标注各报文的源/目的IP、端口（假设A端口为5000，B端口为80）、标志位（SYN、ACK）、序列号（seq）和确认号（ack）；（2）若第三次握手报文在传输中丢失，后续会发生什么？答案：（1）三次握手报文交互：第一次（A→B）：源IP192.168.1.100，源端口5000；目的IP192.168.1.200，目的端口80；标志位SYN=1；seq=x；无ack（ack=0）。第二次（B→A）：源IP192.168.1.200，源端口80；目的IP192.168.1.100，目的端口5000；标志位SYN=1，ACK=1；seq=y；ack=x+1（确认A的SYN）。第三次（A→B）：源IP192.168.1.100，源端口5000；目的IP192.168.1.200，目的端口80；标志位ACK=1；seq=x+1（A的下一个序列号）；ack=y+1（确认B的SYN）。（2）第三次握手丢失时，主机B未收到A的ACK确认，会超时重传第二次握手的SYN+ACK报文（包含seq=y，ack=x+1）。主机A收到后，会重新发送第三次握手的ACK报文（seq=x+1，ack=y+1）。若多次重传仍未收到A的ACK，B会认为连接建立失败，释放已分配的资源（如连接控制块）。四、数据库系统4.（综合题）某公司数据库包含以下关系模式：员工（员工号，姓名，部门号，职位）部门（部门号，部门名，经理员工号）项目（项目号，项目名，预算，部门号）参与（员工号，项目号，工时）（1）用关系代数表达式查询“部门名为‘研发部’的所有员工姓名”；（2）用SQL语句查询“参与至少2个项目的员工号及其参与的项目数”；（3）分析该数据库是否满足3NF，若不满足给出修改建议。答案：（1）关系代数表达式：π姓名(σ部门名=‘研发部’(部门⋈员工))（注：部门与员工通过部门号自然连接，筛选部门名为研发部，投影姓名）（2）SQL语句：SELECT员工号,COUNT(项目号)AS项目数FROM参与GROUPBY员工号HAVINGCOUNT(项目号)≥2;（3）检查3NF：员工关系：主码为员工号，非主属性姓名、部门号、职位完全依赖于主码，且不存在传递依赖（部门号是外码，不传递决定其他属性），满足3NF。部门关系：主码为部门号，非主属性部门名、经理员工号完全依赖于主码。经理员工号是员工号的外码，部门号→经理员工号，但经理员工号→部门号（一个经理只能属于一个部门），因此存在传递依赖（部门号→经理员工号→部门号），违反3NF。项目关系：主码为项目号，非主属性项目名、预算、部门号完全依赖于主码，无传递依赖，满足3NF。参与关系：主码为（员工号，项目号），工时完全依赖于主码，无传递依赖，满足3NF。修改建议：将部门关系拆分为部门（部门号，部门名）和经理（经理员工号，部门号），其中经理关系的主码为经理员工号，部门号为外码，消除传递依赖。五、计算机组成原理5.（计算题）某计算机字长32位，主存容量为1GB，采用直接映射的Cache，Cache容量为16KB，块大小为32字节。（1）计算主存地址各字段的位数（标记、块号、块内地址）；（2）若CPU访问主存地址为0x00012345（十六进制），计算该地址对应的Cache块号；（3）说明直接映射Cache中“标记”字段的作用。答案：（1）主存地址字段划分：块大小32字节=2^5，故块内地址占5位。Cache容量16KB=2^14B，块数=16KB/32B=512=2^9，故Cache块号（索引）占9位。主存容量1GB=2^30B，地址总位数30位。标记位数=3095=16位。（2）地址0x00012345转换为二进制：00000000000000010010001101000101（共32位，实际主存地址取低30位）。块内地址占低5位：0101（后5位）；索引（Cache块号）占中间9位：从第5位到第13位（0based），即地址的第5~13位（二进制位序号从0开始）。原地址二进制低30位为：0000000000010010001101000101（去掉最高两位0），中间9位（位5~13）是：001000110（即十进制的0x46，即70）。（3）标记字段的作用：由于直接映射中多个主存块会映射到同一个Cache块位置，标记字段用于存储主存块的高位地址，当访问Cache时，通过比较当前地址的标记字段与Cache中对应块的标记字段，判断是否命中。若匹配则命中，否则不命中。六、C++程序设计6.（分析题）阅读以下代码，回答问题：```cppinclude<iostream>usingnamespacestd;classBase{public:virtualvoidfunc(){cout<<"Base::func()"<<endl;}};classDerived:publicBase{public:voidfunc()override{cout<<"Derived::func()"<<endl;}};intmain(){Baseb=newDerived();b>func();//输出什么？deleteb;return0;}```（1）程序输出结果是什么？说明原因；（2）若将Base类中的func()声明为非虚函数（去掉virtual），输出结果会如何？为什么？（3）若Base类的析构函数未声明为virtual，可能导致什么问题？答案：（1）输出“Derived::func()”。原因：Base类的func()是虚函数，Derived类重写了该虚函数。通过基类指针指向派生类对象时，调用虚函数会触发动态绑定（晚绑定），实际调用派生类的func()。（2）若func()非虚，输出“Base::func()”。此时函数调用为静态绑定（早绑定），根据指针类型（Base）决定调用基类的func()，而非对象实际类型（Derived）。（3）若Base的析构函数未声明为virtual，当通过基类指针delete派生类对象时，只会调用基类的析构函数，而不会调用派生类的析构函数，导致派生类对象的资源（如动态分配的内存、打开的文件等）未被正确释放，引发内存泄漏或资源泄漏。七、软件工程7.（简答题）（1）敏捷开发中的Scrum框架包含哪些核心角色？（2）简述软件测试中“黑盒测试”与“白盒测试”的主要区别；（3）UML类图中，“泛化”与“实现”关系的符号和含义是什么？答案：（1）Scrum核心角色：产品负责人（Produc