2025年计算机科学与技术学科期末考试试卷及答案

2025年计算机科学与技术学科期末考试试卷及答案一、单项选择题（共15题，每题2分，共30分）1.对于长度为n的无序数组，快速排序在最坏情况下的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(n³)2.操作系统中，进程从等待状态转换为就绪状态的可能原因是（）。A.进程时间片用完B.进程获得CPUC.I/O操作完成D.进程调用exit()3.在TCP/IP协议栈中，HTTP协议属于（）。A.网络接口层B.网际层C.传输层D.应用层4.关系数据库中，若一个关系模式满足所有非主属性完全依赖于候选码，则该模式至少属于（）。A.1NFB.2NFC.3NFD.BCNF5.编译过程中，词法分析阶段的主要任务是（）。A.识别语法错误B.将源程序转换为目标代码C.生成符号表D.识别单词符号6.计算机组成原理中，直接寻址方式下，操作数的有效地址是（）。A.指令中的地址码B.寄存器中的值C.内存中的地址D.程序计数器的值7.机器学习中，以下属于监督学习的是（）。A.K-means聚类B.关联规则挖掘C.支持向量机分类D.主成分分析8.软件工程中，敏捷开发的核心原则是（）。A.严格遵循需求文档B.快速迭代与客户反馈C.瀑布式阶段划分D.大规模文档驱动9.数据挖掘中，若某关联规则的支持度为0.3，置信度为0.8，则表示（）。A.30%的事务包含规则前件，其中80%同时包含后件B.80%的事务包含规则前件，其中30%同时包含后件C.30%的事务同时包含前件和后件，80%的前件事务包含后件D.80%的事务同时包含前件和后件，30%的前件事务包含后件10.操作系统中，死锁的必要条件不包括（）。A.互斥条件B.请求与保持条件C.不可抢占条件D.环路等待条件E.空闲让进条件11.某IP地址为0，其子网掩码为，则该地址的网络号是（）。A.B.C.0D.012.数据库索引中，B+树的叶子节点存储的是（）。A.数据记录的指针B.索引键值和数据记录C.索引键值和子节点指针D.仅索引键值13.分治算法的核心步骤不包括（）。A.分解问题B.递归求解子问题C.合并子问题解D.动态规划优化14.操作系统文件系统中，inode结构通常存储的信息是（）。A.文件内容B.文件元数据（如权限、大小、时间戳）C.文件路径D.文件缓存15.计算机指令周期中，取指周期的主要操作是（）。A.从内存读取操作数B.从寄存器读取指令C.从内存读取指令到指令寄存器D.执行指令的运算操作二、填空题（共10题，每题2分，共20分）1.TCP三次握手中，第二次握手的报文段包含的标志位是______。2.数据库事务的四个特性（ACID）是原子性、一致性、隔离性和______。3.操作系统调度算法中，短作业优先（SJF）属于______（抢占式/非抢占式）调度。4.计算机网络中，DNS的主要作用是将______转换为IP地址。5.线索二叉树中，每个节点的左线索指向其______（前驱/后继）节点（假设中序线索化）。6.编译原理中，语法分析的输入是______（词法分析的输出）。7.BP神经网络中，误差反向传播的核心是通过______调整神经元权重。8.UML用例图的基本元素包括用例、参与者和______。9.K-means聚类算法的核心是通过迭代优化______（目标函数）。10.虚拟内存的理论基础是______（局部性原理/并行性原理）。三、简答题（共5题，每题8分，共40分）1.简述虚拟内存的工作原理及其优点。2.比较TCP和UDP协议的特点，并分别列举其典型应用场景。3.说明B树与B+树的主要区别，并解释B+树为何更适合作为数据库索引结构。4.进程与线程的主要区别是什么？多线程编程适用于哪些场景？5.数据库事务的隔离级别有哪些？不同隔离级别如何影响并发控制的性能与数据一致性？四、算法设计题（共3题，每题12分，共36分）1.给定一个带权有向图（顶点集合为V，边集合为E，权值均为非负数），要求用Dijkstra算法求从源点s到所有其他顶点的最短路径。请：（1）描述算法的核心步骤；（2）给出伪代码实现；（3）分析时间复杂度（假设使用优先队列优化）。2.动态规划算法常用于解决最优化问题。请针对最长公共子序列（LCS）问题：（1）定义状态变量；（2）推导状态转移方程；（3）举例说明计算过程（如序列X=“ABCBDAB”，Y=“BDCAB”）。3.线索二叉树是一种通过线索（指针）快速访问前驱和后继的二叉树结构。假设二叉树节点结构体定义为：```ctypedefstructThreadNode{intdata;structThreadNodelchild,rchild;intltag,rtag;//0表示子节点，1表示线索}ThreadNode,ThreadTree;```要求设计中序线索二叉树的遍历算法（输出节点数据序列），并说明遍历过程如何利用线索提高效率。五、综合应用题（共2题，每题15分，共30分）1.设计一个分布式电商系统的商品缓存方案。要求：（1）说明缓存层的部署架构（如集中式/分布式）；（2）选择缓存一致性策略（如Cache-Aside、Write-Through等）并解释其实现；（3）设计缓存失效策略（如TTL、LRU等）及多级缓存（如本地缓存+分布式缓存）的协同机制；（4）分析可能的缓存击穿、穿透问题及解决方案。2.设计一个在线教育平台的数据库架构。要求：（1）绘制简化的ER图（包含用户、课程、教师、订单四个实体及关键属性）；（2）设计核心数据表结构（如用户表、课程表、订单表），并说明字段类型及约束；（3）提出索引优化策略（如主键、外键、联合索引）；（4）设计订单支付事务的处理流程（需满足ACID特性）。答案一、单项选择题1.C2.C3.D4.B5.D6.A7.C8.B9.C10.E11.A12.B13.D14.B15.C二、填空题1.SYN+ACK2.持久性3.非抢占式4.域名5.前驱6.单词符号序列7.梯度下降8.关联关系9.簇内误差平方和10.局部性原理三、简答题1.虚拟内存工作原理：利用磁盘空间模拟内存，将进程的部分数据加载到内存，其余暂存磁盘。通过页表记录页的内存/磁盘位置，当访问缺失页时触发缺页中断，将目标页调入内存（可能置换旧页）。优点：突破物理内存限制，允许多进程并发运行；提高内存利用率；简化程序开发（无需手动管理内存）。2.TCP特点：面向连接、可靠传输（确认重传）、面向字节流、有拥塞控制；UDP特点：无连接、不可靠、面向数据报、低延迟；典型场景：TCP用于HTTP、SMTP（需可靠传输）；UDP用于视频流、DNS（实时性优先）。3.B树与B+树区别：B树的节点存储数据和索引键，叶子节点无顺序；B+树仅叶子节点存储数据（且有序），内部节点仅存索引键，所有叶子节点通过指针连接。B+树优势：范围查询效率高（可顺序遍历叶子节点）；索引更紧凑（内部节点无数据）；适合磁盘存储（减少I/O次数）。4.进程与线程区别：进程是资源分配的基本单位，线程是CPU调度的基本单位；进程间独立（通信需IPC），线程共享进程资源（通信高效）；进程切换开销大，线程切换开销小。多线程场景：I/O密集型任务（如Web服务器）、并行计算（如图像处理）、需要共享状态的任务（如实时数据处理）。5.隔离级别（从低到高）：读未提交（ReadUncommitted）、读已提交（ReadCommitted）、可重复读（RepeatableRead）、串行化（Serializable）。影响：隔离级别越低，并发性能越高，但可能出现脏读、不可重复读、幻读；级别越高，数据一致性越强，但并发性能下降（如串行化接近单线程）。四、算法设计题1.Dijkstra算法（1）核心步骤：①初始化距离数组dist[]（dist[s]=0，其余为∞），优先队列保存（距离，顶点）；②取出队列中距离最小的顶点u，遍历其邻接顶点v，若dist[v]>dist[u]+weight(u,v)，则更新dist[v]并将v加入队列；③重复直到队列为空。（2）伪代码：```pythondefdijkstra(graph,s):n=len(graph)dist=[inf]ndist[s]=0heap=[(0,s)]visited=[False]nwhileheap:current_dist,u=heapq.heappop(heap)ifvisited[u]:continuevisited[u]=Trueforv,weightingraph[u]:ifdist[v]>current_dist+weight:dist[v]=current_dist+weightheapq.heappush(heap,(dist[v],v))returndist```（3）时间复杂度：使用优先队列（堆），每次操作O(logn)，总时间O((V+E)logV)（V为顶点数，E为边数）。2.LCS问题（1）状态变量：dp[i][j]表示X的前i个字符和Y的前j个字符的LCS长度。（2）状态转移方程：若X[i-1]==Y[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。（3）计算示例（X=“ABCBDAB”，Y=“BDCAB”）：构造5×6的dp表（i=0~5，j=0~6）：-dp[0][j]=0，dp[i][0]=0；-i=1（X[0]=A），j=1（Y[0]=B）：不等，dp[1][1]=0；-i=2（X[1]=B），j=1（Y[0]=B）：相等，dp[2][1]=1；-最终dp[5][6]=4（LCS为“BCAB”或“BDAB”）。3.中序线索二叉树遍历算法（1）算法步骤：①找到中序遍历的第一个节点（最左子节点）；②依次访问当前节点的后继：若rtag=1，直接通过rchild找到后继；否则，找右子树的最左子节点。（2）代码实现：```cvoidinOrderTraverse(ThreadTreeT){ThreadNodep=T;while(p!=NULL){//找最左子节点（中序第一个节点）while(p->ltag==0)p=p->lchild;printf("%d",p->data);//访问后继while(p->rtag==1&&p->rchild!=NULL){p=p->rchild;printf("%d",p->data);}p=p->rchild;//进入右子树（可能为子节点或线索）}}```（3）效率提升：通过线索直接跳转前驱/后继，无需递归或栈，时间复杂度O(n)，空间复杂度O(1)。五、综合应用题1.分布式电商缓存方案（1）部署架构：采用“本地缓存（JVM缓存）+分布式缓存（Redis集群）”多级架构。本地缓存用于高频热点数据（如秒杀商品），分布式缓存用于全局商品数据。（2）一致性策略：选择Cache-Aside模式（读：先查缓存，未命中则查数据库并更新缓存；写：先更新数据库，再删除缓存）。避免Write-Through的同步写延迟，同时通过延迟双删（删除缓存后等待一段时间再次删除）解决主从数据库同步导致的脏数据问题。（3）失效策略：-TTL（生存时间）：普通商品缓存设置30分钟~2小时，热点商品设置更长（如1天）；-LRU（最近最少使用）：Redis配置maxmemory-policy为allkeys-lru，淘汰冷数据；-协同机制：本地缓存设置更小的TTL（如5分钟），并通过消息队列（如Kafka）同步分布式缓存的更新事件，触发本地缓存的主动失效。（4）缓存问题解决：-缓存击穿（热点key失效）：使用互斥锁（如Redis的setnx）控制仅一个线程回源加载，其他线程等待；-缓存穿透（查询不存在的key）：缓存空值（设置短TTL）或使用布隆过滤器预校验。2.在线教育平台数据库架构（1）ER图（简化）：-实体：用户（用户ID，姓名，手机号，注册时间）；-课程（课程ID，名称，教师ID，价格，创建时间）；-教师（教师ID，姓名，职称，简介）；-订单（订单ID，用户ID，课程ID，支付金额，支付状态，支付时间）。-关系：用户与订单（1:N）；教师与课程（1:N）；用户与课程（M:N，通过订单关联）。（2）核心表结构：-用户表（user）：user_id（BIGINT，主键），username（VARCHAR(50)），phon