2026年专业基础试题(附答案)

2026年专业基础试题(附答案)一、单项选择题（每题2分，共30分）1.若某算法的时间复杂度表达式为T(n)=2n²+3nlog₂n+5，则其渐近时间复杂度可表示为（）A.O(n²)B.O(nlogn)C.O(n³)D.O(n)2.操作系统中，进程从等待状态转换为就绪状态的可能原因是（）A.时间片用完B.进程被调度C.等待的I/O操作完成D.进程执行完毕3.TCP/IP协议栈中，负责将网络层数据包封装成数据链路层帧的是（）A.应用层B.传输层C.网络层D.数据链路层4.关系数据库中，若一个关系模式满足“所有非主属性完全函数依赖于主码”，则该模式至少属于（）A.1NFB.2NFC.3NFD.BCNF5.8位二进制补码表示的整数-128，其对应的十六进制形式是（）A.80HB.FFHC.7FHD.00H6.二分查找算法能够正确执行的前提条件是（）A.数组元素无序B.数组元素升序排列C.数组元素降序排列D.数组元素部分有序7.虚拟内存管理的核心特征不包括（）A.离散性B.一次性C.多次性D.对换性8.IP协议的主要功能是（）A.提供可靠的端到端传输B.实现网络层的路由与寻址C.完成数据链路层的差错校验D.处理应用层的会话管理9.关系数据库中，主码的最基本特性是（）A.可重复B.允许空值C.唯一标识元组D.包含所有属性10.深度为5的满二叉树中，叶子节点的数量是（）A.15B.16C.31D.3211.操作系统的文件系统中，索引节点（i-node）主要存储的信息是（）A.文件内容B.文件元数据（如权限、大小、指针）C.文件访问记录D.文件备份数据12.CSMA/CD协议的工作流程可概括为（）A.先听后发，边发边听，冲突停止，随机重发B.先发后听，冲突重发C.随机发送，冲突避让D.固定时间槽发送13.关系代数中，选择运算（σ）的作用是（）A.从关系中选取满足条件的元组B.从关系中选取满足条件的属性列C.合并两个关系的元组D.连接两个关系的属性14.栈的典型应用场景不包括（）A.括号匹配B.递归调用C.层次遍历二叉树D.中缀表达式转后缀表达式15.死锁避免的核心算法是（）A.银行家算法B.资源分配图化简算法C.时间片轮转算法D.最短作业优先算法二、填空题（每空2分，共16分）1.8位二进制补码能表示的整数范围是______。2.快速排序的平均时间复杂度是______，最坏时间复杂度是______。3.TCP协议实现可靠传输的两个关键机制是______和______。4.关系数据库中，第三范式（3NF）要求消除______对主码的传递函数依赖。5.页式存储管理中，逻辑地址由页号和页内偏移量组成，页号用于查找______。三、简答题（每题8分，共40分）1.简述进程与线程的主要区别。2.说明TCP三次握手的具体过程及其目的。3.什么是死锁？列举死锁发生的四个必要条件。4.快速排序的基本思想是什么？请描述其划分过程的关键步骤。5.解释数据库规范化中第三范式（3NF）的定义，并举例说明如何将不满足3NF的关系模式分解为3NF。四、计算题（共34分）1.（10分）给定权值集合{3,5,7,9,11}，构造哈夫曼树，并计算其带权路径长度（WPL）。2.（12分）某页式存储管理系统中，页大小为4KB，逻辑地址空间为32位，页表项大小为4字节。（1）若采用一级页表，页表需要占用多少内存空间？（2）若采用二级页表，假设第一级页表占10位，第二级页表需要占多少位？3.（12分）已知某二叉树的先序遍历序列为ABDGHCEIF，中序遍历序列为GDHBAEICF。（1）画出该二叉树的结构；（2）写出该二叉树的后序遍历序列。答案一、单项选择题1.A2.C3.D4.B5.A6.B7.B8.B9.C10.B11.B12.A13.A14.C15.A二、填空题1.-128～+1272.O(nlogn)；O(n²)3.确认重传；滑动窗口4.非主属性5.页表三、简答题1.进程与线程的主要区别：（1）调度单位：进程是资源分配的基本单位，线程是CPU调度的基本单位；（2）资源占用：进程拥有独立的资源（如内存、文件），线程共享所属进程的资源；（3）并发性：同一进程内的线程间并发开销更小，不同进程间并发需通过进程间通信；（4）系统开销：创建/销毁进程的开销大于线程，线程切换的开销更小。2.TCP三次握手过程：（1）客户端发送SYN=1，随机序列号seq=x，请求建立连接（第一次握手）；（2）服务器回复SYN=1，ACK=1，确认号ack=x+1，随机序列号seq=y（第二次握手）；（3）客户端发送ACK=1，确认号ack=y+1（第三次握手）。目的：同步双方初始序列号，确认双方收发能力正常，防止历史连接的重复初始化。3.死锁是指多个进程因竞争资源而陷入互相等待的状态，若无外力干预将无法继续执行。四个必要条件：（1）互斥条件：资源同一时间只能被一个进程使用；（2）占有等待条件：进程已占有至少一个资源，同时等待其他资源；（3）不可抢占条件：资源只能由占有者主动释放，不可被强行抢占；（4）循环等待条件：进程间形成资源等待的环形链。4.快速排序的基本思想是分治：选择一个枢轴（pivot），将数组划分为小于枢轴和大于枢轴的两部分，递归对两部分排序。划分过程关键步骤：（1）选择枢轴（如数组首元素、中间元素或随机选择）；（2）设置左右指针，左指针从左向右找大于枢轴的元素，右指针从右向左找小于枢轴的元素；（3）交换左右指针指向的元素，重复直到指针相遇；（4）将枢轴交换到正确位置，完成一次划分。5.第三范式（3NF）要求关系模式中，所有非主属性既不部分依赖于主码，也不传递依赖于主码。例：关系模式R（学号，姓名，系号，系主任），主码为学号。非主属性“系主任”通过“系号”传递依赖于学号（学号→系号→系主任），不满足3NF。分解为R1（学号，姓名，系号）和R2（系号，系主任），R1中所有非主属性完全依赖于学号，R2中主码为系号，非主属性系主任完全依赖于系号，均满足3NF。四、计算题1.哈夫曼树构造步骤：（1）合并最小权值3和5，提供新节点8（权值3+5=8），剩余权值{7,8,9,11}；（2）合并7和8，提供新节点15（7+8=15），剩余权值{9,11,15}；（3）合并9和11，提供新节点20（9+11=20），剩余权值{15,20}；（4）合并15和20，提供根节点35（15+20=35）。哈夫曼树结构：根35，左孩子15（左7，右8（左3，右5）），右孩子20（左9，右11）。WPL=3×3（3的路径长度3）+5×3（5的路径长度3）+7×2（7的路径长度2）+9×2（9的路径长度2）+11×2（11的路径长度2）=9+15+14+18+22=78。2.（1）页大小4KB=2¹²B，页内偏移占12位，逻辑地址32位，页号占32-12=20位。一级页表项数=2²⁰，每个页表项4字节，页表总大小=2²⁰×4=4MB。（2）二级页表中，第一级页表占10位，剩余页号位数=20-10=10位，因此第二级页表占10位。3.（1）二叉树结构推导：先序遍历首元素A为根，中序遍历中A左侧GDHB为左子树，右侧EICF为右子树。左子树先序序列为BDGH，首元素B为左子树根；中序中B左侧GDH为左子树，无右侧。左子树先序BDGH中B的左子树先序为DGH，首元素D为根；中序GDH中D左侧G为左子树