2025年计算机程序设计员考试题和答案

2025年计算机程序设计员考试题和答案一、单项选择题（每题2分，共30分）1.以下关于算法时间复杂度的描述中，正确的是：A.若递归算法的递推式为T(n)=2T(n/2)+n²，则其时间复杂度为O(n²)B.冒泡排序的最优时间复杂度为O(nlogn)C.插入排序的平均时间复杂度与堆排序相同D.对于长度为n的数组，选择排序的比较次数始终为n(n-1)/22.处理高频插入、删除且需要保持有序的数据集时，最适合的数据结构是：A.二叉搜索树（未平衡）B.跳表C.哈希表D.有序数组3.以下关于面向对象编程的描述，错误的是：A.多态的实现依赖虚函数表（vtable）B.抽象类中至少包含一个纯虚函数C.子类可以重写父类的非虚函数D.构造函数不能声明为虚函数4.Rust语言中，以下操作会导致所有权转移的是：A.将变量作为参数传递给打印函数（println!宏）B.使用&符号创建变量的不可变引用C.对i32类型变量执行赋值操作（如x=y）D.在函数中返回变量的引用5.操作系统中，以下不属于死锁产生必要条件的是：A.互斥条件B.不可抢占条件C.循环等待条件D.资源静态分配条件6.数据库事务的隔离级别中，“可重复读”与“读已提交”的主要区别在于：A.是否允许脏读B.是否允许不可重复读C.是否允许幻读D.是否强制使用索引7.编译器优化技术中，循环展开主要用于优化：A.指令级并行性B.内存访问局部性C.分支预测准确性D.寄存器分配效率8.TCP协议中，流量控制的实现主要依赖：A.滑动窗口机制B.超时重传机制C.拥塞避免算法D.校验和字段9.以下关于动态规划与贪心算法的描述，正确的是：A.动态规划需要满足最优子结构，贪心算法不需要B.贪心算法的每一步选择都是局部最优，动态规划需要全局比较C.动态规划适用于无后效性问题，贪心算法适用于有后效性问题D.两者都需要存储所有子问题的解10.设计哈希函数时，为减少冲突，最关键的是：A.提高计算速度B.使哈希值分布均匀C.支持动态扩展D.处理负键值11.并发编程中，互斥锁（Mutex）与信号量（Semaphore）的主要区别是：A.互斥锁只能由持有者释放，信号量可由任意线程释放B.互斥锁用于同步，信号量用于互斥C.互斥锁支持多个线程同时访问，信号量限制单个线程D.互斥锁的初始值为1，信号量的初始值只能为012.C++中，以下智能指针中，不能共享所有权的是：A.std::shared_ptrB.std::unique_ptrC.std::weak_ptrD.以上都可以13.分布式系统中，CAP定理的三个特性不包括：A.一致性（Consistency）B.可用性（Availability）C.分区容错性（PartitionTolerance）D.持久性（Persistence）14.以下属于监督学习任务的是：A.聚类分析（Clustering）B.关联规则挖掘（AssociationRuleMining）C.分类（Classification）D.降维（DimensionalityReduction）15.静态代码分析工具的主要作用是：A.检测运行时错误B.优化代码执行效率C.发现潜在的语法或逻辑缺陷D.提供测试用例二、填空题（每空1分，共20分）1.快速排序的平均时间复杂度是____，最坏情况下的时间复杂度是____。2.红黑树中，每个节点要么是红色要么是黑色，根节点必须是____色，红色节点的子节点不能是____色。3.Python提供器函数中，使用____关键字逐个返回值，提供器对象的____方法可向提供器发送数据。4.操作系统中，进程的三种基本状态是运行态、就绪态和____；线程的调度由____完成（填“内核”或“用户空间”）。5.数据库ACID特性中，A代表____，C代表____，I代表____，D代表____。6.深度优先搜索（DFS）通常使用____数据结构实现，广度优先搜索（BFS）通常使用____数据结构实现。7.动态规划的状态转移方程需要满足____性（即无后效性）和____性（即最优子结构）。8.C++虚函数的实现依赖于____表（英文缩写），该表在____时（填“编译”或“运行”）提供。9.哈希冲突的解决方法中，开放寻址法包括线性探测、____和____等方式。10.TCP连接建立需要____次握手，断开连接需要____次挥手。三、编程题（共50分）1.（15分）给定一个整数数组nums（可能包含重复元素），找出所有满足i<j<k且nums[i]+nums[j]+nums[k]==0的三元组（i,j,k）。要求输出结果中不包含重复的三元组。示例：输入nums=[-1,0,1,2,-1,-4]，输出[[-1,-1,2],[-1,0,1]]。2.（15分）设计一个函数process_logs，处理用户行为日志数据。输入为按时间排序的事件列表，每个事件格式为{"user_id":str,"timestamp":int（秒级，当天0-86399）,"event":"login"或"logout"}。要求统计每个用户当天的活跃时长（登录到退出的时间段总和，若最后一次事件是login且无logout，则活跃时长算至当天结束86399秒）。需处理重复login/logout（如连续login或连续logout，仅保留有效事件对）。示例：输入events=[{"user_id":"A","timestamp":100,"event":"login"},{"user_id":"A","timestamp":200,"event":"login"},//重复login，忽略{"user_id":"A","timestamp":500,"event":"logout"},{"user_id":"B","timestamp":1000,"event":"login"},{"user_id":"B","timestamp":2000,"event":"logout"},{"user_id":"B","timestamp":3000,"event":"login"}//无logout，算至86399]，输出{"A":400（500-100）,"B":(2000-1000)+(86399-3000)=66399}。3.（20分）实现一个LRU（最近最少使用）缓存，要求支持以下操作：get(key)：若key存在，返回value；否则返回-1。put(key,value)：若key存在，更新value并将该键置为最近使用；若不存在，插入新键值对。当缓存容量满时，删除最久未使用的键值对。要求时间复杂度O(1)，用C++或Python实现（任选一种语言）。答案一、单项选择题1.A2.B3.C4.C5.D6.B7.A8.A9.B10.B11.A12.B13.D14.C15.C二、填空题1.O(nlogn)、O(n²)2.黑、红3.yield、send4.阻塞态（等待态）、内核5.原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）6.栈、队列7.无后效、最优子结构8.vtable、编译9.二次探测、双重哈希（或伪随机探测）10.三、四三、编程题1.解答（Python）：```pythondefthree_sum(nums):nums.sort()n=len(nums)res=[]foriinrange(n):ifnums[i]>0:break排序后首元素>0，无可能解ifi>0andnums[i]==nums[i-1]:continue去重left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal<0:left+=1eliftotal>0:right-=1else:res.append([nums[i],nums[left],nums[right]])去重left和right的重复值whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1returnres```2.解答（Python）：```pythondefprocess_logs(events):fromcollectionsimportdefaultdictuser_events=defaultdict(list)按用户分组并过滤无效事件foreventinevents:uid=event["user_id"]ts=event["timestamp"]typ=event["event"]ifnotuser_events[uid]:空列表直接添加user_events[uid].append((ts,typ))continuelast_typ=user_events[uid][-1][1]iftyp=="login"andlast_typ=="login":连续login，保留最后一个user_events[uid][-1]=(ts,typ)eliftyp=="logout"andlast_typ=="logout":连续logout，保留最后一个user_events[uid][-1]=(ts,typ)else:user_events[uid].append((ts,typ))计算活跃时长result=defaultdict(int)foruid,evtsinuser_events.items():total=0i=0whilei<len(evts):ifevts[i][1]=="login":ifi+1<len(evts)andevts[i+1][1]=="logout":total+=evts[i+1][0]evts[i][0]i+=2else:最后一个是login，无logouttotal+=86399evts[i][0]i+=1else:无效logout（无对应login），跳过i+=1result[uid]=totalreturndict(result)```3.解答（C++，使用双向链表+unordered_map）：```cppinclude<unordered_map>usingnamespacestd;structNode{intkey,val;Nodeprev,next;Node(intk,intv):key(k),val(v),prev(nullptr),next(nullptr){}};classLRUCache{private:intcapacity;unordered_map<int,Node>cache;Nodehead,tail;//头尾哨兵节点voidmove_to_head(Nodenode){//断开原链接node->prev->next=node->next;node->next->prev=node->prev;//插入头部node->prev=head;node->next=head->next;head->next->prev=node;head->next=node;}voidadd_to_head(Nodenode){node->prev=head;node->next=head->next;head->next->prev=node;head->next=node;}voidremove_tail(){Nodedel=tail->prev;cache.erase(del->key);del->prev->next=tail;tail->prev=del->prev;deletedel;}public:LRUCache(intcap):capacity(cap){head=newNode(0,0);