2025年计算机编程测试题及答案

2025年计算机编程测试题及答案一、单项选择题（每题2分，共20分）1.关于红黑树的性质，以下描述错误的是（）A.每个节点要么是红色，要么是黑色B.根节点必须是黑色C.所有叶子节点（NIL节点）是红色D.从任一节点到其每个叶子的所有路径包含相同数量的黑色节点2.对长度为n的有序数组进行二分查找，在最坏情况下的时间复杂度为（）A.O(n)B.O(nlogn)C.O(logn)D.O(n²)3.以下操作系统调度算法中，属于抢占式调度的是（）A.先来先服务（FCFS）B.短作业优先（SJF）C.时间片轮转（RR）D.高响应比优先（HRRN）4.在TCP/IP协议栈中，HTTP/2默认使用的端口号是（）A.80B.443C.8080D.80005.关系型数据库中，事务的“隔离性”（Isolation）指的是（）A.事务一旦提交，其结果不可撤销B.事务执行过程中不受其他事务干扰C.事务必须包含所有操作作为一个整体D.事务操作前后数据保持一致性6.以下设计模式中，用于解决对象间一对多依赖关系，当一个对象状态改变时通知所有依赖对象的是（）A.工厂模式B.观察者模式C.单例模式D.策略模式7.编译过程中，将源代码转换为词法单元（Token）的阶段是（）A.语法分析B.词法分析C.语义分析D.代码提供8.Java中，以下哪种垃圾回收算法适用于新生代且需要复制存活对象到另一块内存区域（）A.标记-清除算法B.标记-整理算法C.复制算法D.分代收集算法9.Python中，全局解释器锁（GIL）的主要作用是（）A.保证多线程间的内存安全B.提高多线程执行效率C.支持协程调度D.优化垃圾回收性能10.分布式系统中，CAP定理的“C”指的是（）A.一致性（Consistency）B.可用性（Availability）C.分区容错性（PartitionTolerance）D.正确性（Correctness）二、填空题（每空2分，共20分）1.在快速排序的分区（Partition）过程中，假设选择数组最后一个元素作为基准（pivot），以下Python代码的作用是将小于等于pivot的元素移到左侧。请补全横线处的代码：```pythondefpartition(arr,low,high):pivot=arr[high]i=low1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]return______```2.Java中，使用`Thread`类创建多线程时，需要重写的方法是______；若使用`synchronized`关键字实现同步，其锁的对象可以是______（任填一种合法类型）。3.TCP三次握手中，客户端首先发送______报文；服务器收到后回复______报文；最后客户端发送______报文完成连接建立。4.哈希表中解决冲突的常用方法有______（如开放寻址法）和______（如链地址法）。5.动态规划解决最长公共子序列（LCS）问题时，状态转移方程为：若`X[i-1]==Y[j-1]`，则`dp[i][j]=dp[i-1][j-1]+1`；否则`dp[i][j]=max(______,______)`。三、编程题（共60分）1.（20分）给定一个只包含括号的字符串`s`（由`(`和`)`组成），计算其中有效括号的最大嵌套深度。有效括号定义为正确闭合的括号序列，例如`"((()())())"`的最大嵌套深度为3（最内层括号深度为3）。要求：输入：字符串`s`（长度≤10⁵）输出：整数，表示最大嵌套深度示例：输入`"(()())((()))"`，输出`3`2.（40分）实现一个函数`min_edit_distance(s1,s2)`，计算两个字符串`s1`和`s2`的最小编辑距离。编辑操作定义为：插入一个字符（成本1）删除一个字符（成本1）替换一个字符（成本1，若字符相同则成本0）交换相邻两个字符（成本1，仅当两个字符相邻且交换后更接近目标字符串时可用）要求：输入：两个字符串`s1`、`s2`（长度均≤100）输出：整数，表示最小编辑距离示例：输入`s1="abcde",s2="abced"`，输出`1`（交换'd'和'e'）；输入`s1="kitten",s2="sitting"`，输出`3`（替换'k'→'s'，替换'e'→'i'，插入'g'）--答案一、单项选择题1.C（红黑树的叶子节点是黑色NIL节点）2.C（二分查找最坏情况为O(logn)）3.C（时间片轮转属于抢占式调度）4.B（HTTP/2默认使用443端口（HTTPS），HTTP/1.1默认80）5.B（隔离性指事务间互不干扰）6.B（观察者模式实现一对多通知）7.B（词法分析提供Token）8.C（复制算法用于新生代）9.A（GIL保证线程安全但限制多线程并行）10.A（CAP中的C是一致性）二、填空题1.`i+1`（返回基准元素的最终位置）2.`run()`；对象实例/类对象（如`this`或`MyClass.class`）3.SYN；SYN+ACK；ACK4.开放寻址法；链地址法（或拉链法）5.`dp[i-1][j]`；`dp[i][j-1]`三、编程题1.最大嵌套深度解答思路：遍历字符串，维护当前深度计数器。遇到`(`时深度加1，遇到`)`时深度减1，记录过程中的最大深度。代码：```pythondefmax_nesting_depth(s:str)->int:max_depth=0current_depth=0forcharins:ifchar=='(':current_depth+=1ifcurrent_depth>max_depth:max_depth=current_depthelifchar==')':current_depth-=1returnmax_depth```2.最小编辑距离（含交换操作）解答思路：动态规划扩展，状态`dp[i][j]`表示`s1前i个字符`转换为`s2前j个字符`的最小成本。除常规插入、删除、替换外，当`s1[i-1]==s2[j-2]`且`s1[i-2]==s2[j-1]`（i,j≥2）时，考虑交换操作，成本为`dp[i-2][j-2]+1`。代码：```pythondefmin_edit_distance(s1:str,s2:str)->int:m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]初始化边界foriinrange(m+1):dp[i][0]=i删除s1前i个字符forjinrange(n+1):dp[0][j]=j插入s2前j个字符动态规划填充foriinrange(1,m+1):forjinrange(1,n+1):常规操作：插入、删除、替换replace_cost=0ifs1[i-1]==s2[j-1]else1dp[i][j]=min(dp[i-1][j]+1,删除dp[i][j-1]+1,插入dp[i-1][j-1]+replace_cost替换