2025年计算机等级考试复试题及答案

2025年计算机等级考试复试题及答案一、单项选择题(每题1分，共20题，共20分)1.在数据结构中，以下关于栈和队列的叙述，正确的是（）。A.栈是先进先出的线性表B.队列是后进先出的线性表C.栈和队列都是操作受限的线性表D.栈和队列都只能采用顺序存储结构答案：C2.一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是（）。A.1，5，4，3，2B.2，3，4，1，5C.4，3，1，2，5D.5，4，3，2，1答案：C3.在关系数据库中，实现实体之间联系是通过（）。A.公共属性B.表C.关系模式D.记录答案：A4.下列排序算法中，平均时间复杂度为O(nlogn)且空间复杂度为O(1)的是（）。A.堆排序B.快速排序C.归并排序D.希尔排序答案：A5.在TCP/IP参考模型中，负责将数据包从源主机传送到目的主机，并提供端到端通信服务的是（）。A.网络接口层B.网际层C.传输层D.应用层答案：C6.一棵二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（）。A.DEBFCAB.DEBFCC.DEBCFAD.DBEFCA答案：A7.在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（）。A.调用语句B.命令C.消息D.口令答案：C8.在软件工程中，描述软件系统“做什么”的文档是（）。A.需求规格说明书B.概要设计说明书C.详细设计说明书D.测试计划答案：A9.在SQL语言中，用于修改表结构的命令是（）。A.UPDATEB.MODIFYC.ALTERD.CHANGE答案：C10.下列IP地址中，属于C类私有IP地址的是（）。A.B.C.D.答案：C11.下列存储器中，存取速度最快的是（）。A.高速缓存(Cache)B.内存(RAM)C.硬盘(HDD)D.U盘(Flash)答案：A12.在C语言中，若有定义`inta[3][4];`，则对数组元素引用错误的是（）。A.(a[1]+2)A.(a[1]+2)B.(&a[0][0]+4)B.(&a[0][0]+4)C.((a+1))[2]C.((a+1))[2]D.a[1,2]答案：D13.在数据库管理系统中，用于保证事务ACID特性中“一致性”(Consistency)的机制主要是（）。A.并发控制B.完整性约束C.安全性控制D.恢复机制答案：B14.下列协议中，工作在应用层的是（）。A.IPB.TCPC.HTTPD.ARP答案：C15.在操作系统中，引入缓冲技术的主要目的是（）。A.改善CPU和I/O设备之间速度不匹配的矛盾B.节省内存空间C.提高CPU的利用率D.提高I/O设备的效率答案：A16.若二叉树有5个度为2的结点，则该二叉树中的叶子结点数为（）。A.4B.5C.6D.10答案：C17.在软件测试中，黑盒测试法主要关注（）。A.程序内部逻辑结构B.程序数据结构C.程序功能需求D.程序编码规范答案：C18.将十六进制数1A3F转换成十进制数是（）。A.6719B.6718C.6717D.6716答案：A19.在C++中，用于动态分配内存的运算符是（）。A.mallocB.newC.allocD.create答案：B20.在计算机网络中，用于将域名解析为IP地址的协议是（）。A.HTTPB.FTPC.DNSD.SMTP答案：C二、多项选择题(每题2分，共10题，共20分。每题至少有两个正确选项，多选、少选、错选均不得分)1.下列属于操作系统主要功能的是（）。A.处理器管理B.存储器管理C.设备管理D.文件管理答案：A,B,C,D2.下列数据结构中，属于非线性结构的是（）。A.树B.队列C.图D.栈答案：A,C3.下列属于关系数据库基本操作的是（）。A.选择(Selection)B.投影(Projection)C.连接(Join)D.除(Division)答案：A,B,C4.下列IP地址中，属于有效主机IP地址的是（假设子网掩码为）（）。A.B.55C.D.56答案：B,C5.下列属于软件生命周期阶段的是（）。A.可行性研究与计划B.需求分析C.软件设计D.软件测试答案：A,B,C,D6.下列关于进程和线程的描述，正确的是（）。A.进程是资源分配的基本单位B.线程是CPU调度的基本单位C.一个进程可以包含多个线程D.线程间共享进程的资源答案：A,B,C,D7.下列算法中，属于贪心算法应用的是（）。A.哈夫曼编码B.Prim算法求最小生成树C.Dijkstra算法求单源最短路径D.快速排序答案：A,B,C8.在SQL中，下列聚合函数使用正确的是（）。A.COUNT()A.COUNT()B.SUM(salary)C.AVG(age)D.MAX(name)答案：A,B,C9.下列属于网络安全威胁的是（）。A.病毒B.木马C.拒绝服务攻击D.数据窃听答案：A,B,C,D10.在面向对象程序设计语言中，支持的特性包括（）。A.封装B.继承C.多态D.重载答案：A,B,C,D三、填空题(每空1分，共10空，共10分)1.在二叉树中，第i层上最多有______个结点。答案：2^(i-1)2.在关系模型中，二维表的行称为______，列称为______。答案：元组（或记录），属性（或字段）3.在ISO/OSI参考模型中，数据链路层的数据传输单位是______。答案：帧4.软件测试的两种基本方法是白盒测试和______。答案：黑盒测试5.在C语言中，用于从标准输入设备读取一个字符的函数是______。答案：getchar()6.一个算法的时间复杂度为O(n^2)，表明该算法的执行时间与______成正比。答案：问题规模n的平方7.IP地址2的网络类别是______类。答案：C8.在数据库的三级模式结构中，描述全体数据的逻辑结构和特征的是______。答案：模式（或概念模式）9.在操作系统中，进程的三种基本状态是就绪状态、运行状态和______。答案：阻塞状态（或等待状态）四、简答题(每题5分，共6题，共30分)1.简述栈和队列的主要区别，并各举一个实际应用例子。答案：主要区别：栈（Stack）是一种后进先出（LIFO）的线性表，只允许在表的一端（栈顶）进行插入和删除操作。队列（Queue）是一种先进先出（FIFO）的线性表，允许在表的一端（队尾）插入，在另一端（队头）删除。栈的应用例子：函数调用时的系统栈、表达式求值、括号匹配检查。队列的应用例子：操作系统中的进程就绪队列、打印任务队列、消息队列。2.什么是数据库的事务？事务具有哪些特性（ACID）？答案：事务是用户定义的一个数据库操作序列，这些操作要么全部执行，要么全部不执行，是一个不可分割的工作单位。事务的ACID特性包括：原子性（Atomicity）：事务中的所有操作要么全部完成，要么全部不完成，不会结束在中间某个环节。一致性（Consistency）：事务的执行必须使数据库从一个一致性状态变换到另一个一致性状态。隔离性（Isolation）：一个事务的执行不能被其他事务干扰，并发执行的各个事务之间不能互相干扰。持久性（Durability）：一个事务一旦提交，它对数据库中数据的改变就是永久性的，接下来的其他操作或故障不应该对其有任何影响。3.简述TCP和UDP协议的主要区别。答案：连接性：TCP是面向连接的协议，通信前需要建立连接（三次握手）；UDP是无连接的协议，发送数据前不需要建立连接。可靠性：TCP提供可靠的数据传输服务，通过确认、重传、流量控制、拥塞控制等机制保证数据无差错、不丢失、不重复、按序到达；UDP提供不可靠的传输服务，尽最大努力交付，但不保证可靠。报文结构：TCP是面向字节流的，将数据看作无结构的字节流，传输单位是报文段；UDP是面向报文的，对应用层交下来的报文，添加首部后就交付给IP层，传输单位是用户数据报。效率与开销：TCP协议复杂，首部开销大（20字节），传输效率相对较低；UDP协议简单，首部开销小（8字节），传输效率高。应用场景：TCP适用于要求可靠传输的应用，如文件传输（FTP）、网页浏览（HTTP）、电子邮件（SMTP）等。UDP适用于实时性要求高、能容忍少量丢失的应用，如视频会议、实时游戏、DNS查询等。4.什么是死锁？产生死锁的必要条件是什么？答案：死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。产生死锁的四个必要条件是：互斥条件：一个资源每次只能被一个进程使用。请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。5.简述面向对象程序设计中的封装、继承和多态三个基本概念。答案：封装：将数据和操作数据的方法（函数）捆绑在一起，形成一个独立的单元（即对象），并尽可能隐藏对象的内部实现细节，只对外提供有限的接口进行交互。封装提高了代码的安全性和可维护性。继承：允许创建分等级层次的类，子类可以继承父类的特征（属性和方法），并可以增加自己新的特征或修改父类的特征。继承实现了代码的重用，是建立类与类之间“是”（is-a）关系的重要手段。多态：指同一操作作用于不同的对象，可以有不同的解释，产生不同的执行结果。多态性允许使用父类类型的引用指向子类对象，并在运行时确定具体调用哪个子类的方法。多态提高了程序的灵活性和可扩展性，通常通过方法重写（Override）和父类引用指向子类对象来实现。6.简述软件测试中，白盒测试和黑盒测试的主要测试依据和常用方法。答案：白盒测试（结构测试）：主要依据：程序的内部逻辑结构。常用方法：逻辑覆盖测试（语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖、路径覆盖）、基本路径测试、循环结构测试等。黑盒测试（功能测试）：主要依据：软件的需求规格说明书，即程序的功能。常用方法：等价类划分法、边界值分析法、错误推测法、因果图法、场景法等。五、应用题(共4题，共70分)1.（计算类，15分）已知一棵二叉树的中序遍历序列为`CBEDAFIGH`，后序遍历序列为`CEDBIFHGA`。请：(1)画出这棵二叉树。(2)写出该二叉树的前序遍历序列。(3)将该二叉树转换为对应的森林。答案：(1)构造二叉树过程：后序最后一个节点`A`是根节点。在中序中，`A`左边`CBED`是左子树，右边`FIGH`是右子树。左子树部分：后序序列`CEDB`，最后一个`B`是左子树的根。中序`CBED`，`B`左边`C`是左孩子，右边`ED`是右子树。右子树部分：后序序列`IFHG`，最后一个`G`是右子树的根。中序`FIGH`，`G`左边`FI`是左子树，右边`H`是右孩子。递归构造，最终二叉树结构为：```A/\BG/\/\CDFH\E/I```(2)前序遍历序列：`A,B,C,D,E,I,G,F,H`(3)转换为森林：二叉树根节点`A`及其右子树`G`转换为森林中的树。`A`的左子树`B`作为`A`的孩子，`B`的左孩子`C`和右孩子`D`作为`B`的孩子，`D`的右孩子`E`作为`D`的孩子，`E`的左孩子`I`作为`E`的孩子。`G`的左孩子`F`和右孩子`H`作为`G`的孩子。因此森林由两棵树组成：树1的根为`A`，树2的根为`G`（在原始二叉树中`G`是`A`的右孩子，转换后成为独立的树根）。2.（分析类，20分）设有关系模式R（A,B,C,D,E,F），其函数依赖集F={A→BC,CD→E,B→D,BE→F,EF→A}。(1)求属性集{A,B}关于F的闭包(A,B)^+。(2)求R的候选码。(3)R最高属于第几范式？为什么？(4)若R不属于BCNF，请将其分解为BCNF，并保持无损连接性。答案：(1)计算{A,B}的闭包：初始：X={A,B}根据A→BC，加入B,C：X={A,B,C}根据B→D，加入D：X={A,B,C,D}根据CD→E，加入E：X={A,B,C,D,E}根据BE→F，加入F：X={A,B,C,D,E,F}故(A,B)^+={A,B,C,D,E,F}，即全属性集。(2)求候选码：由于(A,B)^+=U（全集），且A^+={A,B,C,D}≠U，B^+={B,D}≠U，所以{A,B}是候选码。检查其他属性组合：{A,C}^+={A,C,B,D,E,F}=U，且A^+和C^+都不等于U，所以{A,C}也是候选码。类似可检查{A,E},{A,F}等，但{A,E}^+={A,E,B,C,D,F}=U，且A^+和E^+都不等于U，所以{A,E}也是候选码。实际上，由于A可以决定BC，而BCDE等组合可以决定其他属性，候选码是那些包含A，并且与A一起能决定所有属性的最小属性集。通过分析，候选码有：{A,B}，{A,C}，{A,E}，{A,F}。因为A本身不能决定E和F，需要再结合一个能推出E或F的属性。从函数依赖看，要推出E需要C或B（结合A），要推出F需要B、E或F本身。所以最小组合是A加上B、C、E、F中的任意一个。(3)R最高属于第几范式：首先，所有属性都是主属性（因为所有属性都出现在候选码中），所以R至少满足3NF（没有非主属性对码的部分和传递依赖）。检查BCNF条件：每一个决定因素都包含候选码。在F中，存在函数依赖B→D，决定因素B不包含任何候选码（因为B单独不是候选码），所以R不满足BCNF。因此，R最高属于3NF。(4)分解为BCNF：选择违反BCNF的函数依赖B→D进行处理。B^+={B,D}。将R分解为：R1(B,D)，R2(A,B,C,E,F)=R{D}+{B}。在R1中，函数依赖B→D成立，且B是R1的候选码，满足BCNF。在R2中，函数依赖集为{A→BC,BE→F,EF→A,(CD→E不再存在，因为C和D不在同一个关系中，但可以推导出新的依赖?)}。实际上原F在R2上的投影需要计算。我们检查R2：属性{A,B,C,E,F}。原F中：A→BC保留（B,C都在R2中）。CD→E不保留，因为D不在R2中。B→D不保留，因为D不在R2中。BE→F保留。EF→A保留。另外，从A→BC可得A→B,A→C。现在检查R2是否满足BCNF。求R2的候选码：由于A→BC，所以A可以决定B,C；BE→F；EF→A。尝试求{A}^+={A,B,C}，不是全属性{A,B,C,E,F}。求{E,F}^+：由EF→A，得{A}，再由A→BC得{B,C}，所以{E,F}^+={E,F,A,B,C}，缺少？全了，{E,F}^+={E,F,A,B,C}？检查：EF→A，加入A；A→BC，加入B,C；现在有{A,B,C,E,F}，全了。所以{E,F}是候选码。类似可求{B,E}^+：BE→F，加入F；现在有{B,E,F}；EF→A，加入A；A→BC，加入B,C；所以{B,E}^+={A,B,C,E,F}，全了，所以{B,E}也是候选码。因此R2的候选码有{E,F}和{B,E}等。检查R2中的函数依赖：A→BC，决定因素A不包含候选码（A不是候选码，因为A不能决定E,F），所以R2不满足BCNF。继续分解R2，选择A→BC。A^+={A,B,C}。将R2分解为：R21(A,B,C)，R22(A,E,F)=R2{B,C}+{A}。在R21中，函数依赖A→BC成立，且A是候选码，满足BCNF。在R22中，属性为{A,E,F}。原F在R22上的投影：从EF→A成立。检查候选码：{E,F}^+={E,F,A}，所以{E,F}是候选码。函数依赖EF→A的决定因素{E,F}包含候选码，满足BCNF。最终分解结果为：R1(B,D),R21(A,B,C),R22(A,E,F)。验证无损连接性：初始表根据属性列和分解后的关系构建，可以通过算法验证该分解具有无损连接性。3.（综合类，20分）某系统采用动态分区分配方式管理内存，当前内存空闲分区情况如下表所示（按地址递增排列）：分区号起始地址大小(KB)状态1100K30空闲2130K60空闲3190K40空闲4230K100空闲5330K50空闲现有如下作业请求序列（按到达顺序）：作业A申请45KB，作业B申请70KB，作业C申请50KB，作业D申请25KB。请分别采用首次适应算法(FF)和最佳适应算法(BF)进行内存分配，并回答：(1)给出每种算法下，为各作业分配的内存分区起始地址（假设分配时从分区头部开始，且分配后剩余空间形成新的空闲分区）。(2)分析每种算法完成所有作业分配后的内存空闲分区表（按地址排序）。(3)比较两种算法在此次分配中的空间利用率（已分配空间/总空闲空间初始和，近似计算）。答案：初始总空闲空间=30+60+40+100+50=280KB。(1)首次适应算法(FF)：作业A申请45KB：从低地址开始找第一个≥45KB的空闲区。分区1(30KB)不够，分区2(60KB)满足，分配。起始地址：130K。分区2剩余15KB（起始地址130+45=175K，大小15KB）。作业B申请70KB：从低地址找。分区1(30KB)不够，新分区2(15KB)不够，分区3(40KB)不够，分区4(100KB)满足，分配。起始地址：230K。分区4剩余30KB（起始地址230+70=300K，大小30KB）。作业C申请50KB：从低地址找。分区1(30KB)不够，新分区2(15KB)不够，分区3(40KB)不够，新分区4(30KB)不够，分区5(50KB)刚好满足，分配。起始地址：330K。分区5分配完，被移除。作业D申请25KB：从低地址找。分区1(30KB)满足，分配。起始地址：100K。分区1剩余5KB（起始地址100+25=125K，大小5KB）。分配结果：A:130K,B:230K,C:330K,D:100K。(2)FF算法分配后的空闲分区表：按地址排序：分区1'：起始125K，大小5KB（由原1剩余）分区2'：起始175K，大小15KB（由原2剩余）分区3：起始190K，大小40KB（未分配）分区4'：起始300K，大小30KB（由原4剩余）（原分区5已分配）(3)最佳适应算法(BF)：将所有空闲分区按容量从小到大排序：30,60,40,100,50。作业A申请45KB：选择容量≥45KB且最小的分区。候选：60,100,50。最小是50KB的分区5。分配分区5。起始地址：330K。分区5剩余5KB（起始330+45=375K，大小5KB）。作业B申请70KB：当前空闲分区（按容量排序更新）：30,60,40,100,5。选择≥70KB的最小分区：100KB的分区4。分配分区4。起始地址：230K。分区4剩余30KB（起始230+70=300K，大小30KB）。作业C申请50KB：当前空闲分区：30,60,40,30,5。选择≥50KB的最小分区：60KB的分区2。分配分区2。起始地址：130K。分区2剩余10KB（起始130+50=180K，大小10KB）。作业D申请25KB：当前空闲分区：30,40,30,10,5。选择≥25KB的最小分区：30KB的分区1。分配分区1。起始地址：100K。分区1剩余5KB（起始100+25=125K，大小5KB）。分配结果：A:330K,B:230K,C:130K,D:100K。(4)BF算法分配后的空闲分区表：按地址排序：分区1'：起始125K，大小5KB（由原1剩余）分区2'：起始180K，大小10KB（由原2剩余）分区3：起始190K，大小40KB（未分配）分区4'：起始300K，大小30KB（由原4剩余）分区5'：起始375K，大小5KB（由原5剩余）(5)空间利用率比较：总申请空间=45+70+50+25=190KB。FF算法：分配后剩余空闲空间总和=5+15+40+30=90KB。初始空闲280KB，已分配190KB，利用率=190/280≈67.86%。BF算法：分配后剩余空闲空间总和=5+10+40+30+5=90KB。初始空闲280KB，已分配190KB，利用率=190/280≈67.86%。此次分配序列下，两种算法最终利用率相同，但碎片分布不同。4.（分析/设计类，15分）阅读以下C语言程序片段，并回答问题。```cinclude<s