2025年计算机程序设计考试试卷及答案解读

2025年计算机程序设计考试试卷及答案解读一、单项选择题（每题2分，共20分）1.以下关于时间复杂度的描述中，正确的是（）。A.对于递归函数f(n)=f(n-1)+f(n-2)，其时间复杂度为O(2ⁿ)B.快速排序在最坏情况下的时间复杂度为O(nlogn)C.二分查找在有序链表上的时间复杂度为O(logn)D.插入排序的平均时间复杂度为O(n)2.给定Python代码片段：```pythondeffunc(n):ifn<=1:return1returnfunc(n-1)+func(n-2)```若调用func(5)，则函数调用次数（含初始调用）为（）。A.9B.15C.19D.213.以下数据结构中，适合用作优先队列底层实现的是（）。A.哈希表B.平衡二叉搜索树C.双向链表D.循环队列4.在C++中，关于智能指针的描述，错误的是（）。A.unique_ptr不能拷贝但可以移动B.shared_ptr通过引用计数管理内存C.weak_ptr可以解决shared_ptr的循环引用问题D.auto_ptr是C++11标准中推荐使用的智能指针5.给定一个长度为n的数组，要求找出其中未出现的最小正整数。最优算法的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(n√n)6.以下关于图的算法中，不能处理带负权边的是（）。A.Dijkstra算法（未优化）B.Bellman-Ford算法C.SPFA算法（队列优化的Bellman-Ford）D.Floyd-Warshall算法7.用KMP算法匹配模式串"ABABC"时，其部分匹配表（前缀函数）的值为（）。A.[0,0,1,2,0]B.[0,0,1,2,3]C.[0,1,1,2,0]D.[0,0,0,1,2]8.以下Python代码的输出结果是（）。```pythona=[1,2,3]b=ab.append(4)print(a)```A.[1,2,3]B.[1,2,3,4]C.报错D.[1,2,4]9.给定二叉树的前序遍历为ABCDE，中序遍历为BADCE，则后序遍历为（）。A.BDECAB.BEDCAC.BDAECD.BDEAC10.以下关于动态规划的描述中，错误的是（）。A.动态规划的核心是状态转移方程B.无后效性是指当前状态只与之前的状态有关，与之后的决策无关C.0-1背包问题可以用贪心算法得到最优解D.最长公共子序列（LCS）问题通常用动态规划解决二、填空题（每题3分，共15分）1.若完全二叉树的第6层（根为第1层）有8个叶子节点，则该树的节点总数最少为______。2.已知一个哈希表的大小为11（下标0-10），采用线性探测法解决冲突。若依次插入键值对(22,A)、(33,B)、(44,C)，则键44的存储位置是______（哈希函数为h(key)=keymod11）。3.给定序列[3,1,4,1,5,9,2,6]，采用堆排序（大根堆）进行升序排序，初始建堆后根节点的值为______。4.用位运算实现“判断整数n是否为2的幂次”，可通过表达式______（用n和位运算符号表示）。5.对于字符串s="ababa"，其所有回文子串的个数为______（单个字符视为回文）。三、算法设计题（每题15分，共30分）1.给定一个未排序的整数数组nums和一个整数k，要求找出数组中所有满足i<j且nums[i]-nums[j]=k的数对(i,j)。请设计一个时间复杂度不超过O(n)的算法，并给出伪代码。2.已知某二叉树的每个节点存储一个正整数，定义“路径和”为从根到叶子节点的路径上所有节点值的和。请设计算法找出二叉树中所有路径和等于给定目标值target的路径，并输出这些路径（路径用节点值列表表示）。要求空间复杂度尽可能优化，给出详细思路及递归实现的伪代码。四、编程题（每题17.5分，共35分）1.（Python）日志文件中每行记录为“用户ID操作时间操作类型”（如“U10011627833600VIEW”），其中操作时间为Unix时间戳（秒级）。要求统计：-每个用户当天（自然日，如1627833600对应2021-08-01）的操作次数；-所有用户中，单日操作次数最多的用户及其次数（若有多个，输出任意一个）。输入保证时间戳合法且按时间升序排列，输出格式为：```用户操作次数统计：{用户ID:次数,...}单日操作次数最多：用户ID次数```2.（C++）设计一个LRU（最近最少使用）缓存，支持以下操作：-get(key)：获取键对应的值，若不存在返回-1，并更新缓存的最近使用顺序；-put(key,value)：插入或更新键值对，若缓存容量已满，则删除最久未使用的键值对。要求使用STL容器实现，时间复杂度O(1)。答案解读一、单项选择题1.答案：A解析：递归式f(n)=f(n-1)+f(n-2)的时间复杂度为O(2ⁿ)（斐波那契递归树的节点数）；快速排序最坏情况为O(n²)（如完全逆序的数组）；二分查找要求随机访问，链表无法O(1)定位中间节点，时间复杂度为O(n)；插入排序平均时间复杂度为O(n²)。2.答案：B解析：func(5)调用func(4)和func(3)；func(4)调用func(3)和func(2)，func(3)调用func(2)和func(1)，依此类推。总调用次数为1（func5）+2（func4、func3）+3（func3、func2、func2）+5（func2、func1、func1、func0、func0）=15次（可通过递归树或动态规划计算调用次数）。3.答案：B解析：优先队列需要快速获取最大值/最小值（O(1)）及插入删除（O(logn)）。平衡二叉搜索树（如红黑树）可满足；哈希表无法排序；链表和队列无法高效维护优先级。4.答案：D解析：auto_ptr是C++98标准中的智能指针，因语义缺陷（拷贝后原指针失效）在C++11中被弃用，推荐使用unique_ptr。5.答案：A解析：最优算法通过原地哈希（将数组视为哈希表，将值为i的数放到下标i-1的位置），时间复杂度O(n)。6.答案：A解析：Dijkstra算法假设边权非负，否则可能无法得到正确结果（如存在负权边时，已确定的最短路径可能被后续更小的路径覆盖）；其他算法均支持负权边。7.答案：A解析：模式串"ABABC"的前缀函数计算：-第0位（A）：0；-第1位（AB）：最长相等前后缀长度0；-第2位（ABA）：前缀"A"和后缀"A"相等，长度1；-第3位（ABAB）：前缀"AB"和后缀"AB"相等，长度2；-第4位（ABABC）：无相等前后缀，长度0。8.答案：B解析：Python中列表是可变对象，b=a使b和a指向同一列表，b.append(4)会修改原列表，因此a变为[1,2,3,4]。9.答案：A解析：前序遍历（根左右）为ABCDE，中序遍历（左根右）为BADCE。根为A，左子树中序为B（左子树），右子树中序为DCE（右子树）。前序中左子树部分为B（根），右子树前序为CDE（根C，左D，右E）。后序遍历顺序为左→右→根，即B→D→E→C→A，结果为BDECA。10.答案：C解析：0-1背包问题中，物品不可分割，贪心算法（按单位重量价值排序）无法保证最优解（如物品重量[3,4]，价值[4,5]，容量5时，贪心选3（价值4），最优解为选4（价值5））。二、填空题1.答案：39解析：完全二叉树第6层有8个叶子节点，说明前5层是满的（2⁵-1=31个节点）。第6层最少有8个节点（其他节点为非叶子，即第5层有(8+1)/2=4.5→取5个节点有子节点），总节点数31+8=39。2.答案：1解析：h(22)=22mod11=0，存储位置0；h(33)=33mod11=0（冲突），线性探测下一个位置1；h(44)=44mod11=0（冲突），探测位置1（已被33占用），探测位置2（空）？不，原题中插入顺序为22→33→44。22在0，33在0冲突，探测1（空），存入1；44的h=0，冲突，探测1（被33占用），探测2（空），所以44的位置是2？原题可能计算错误，正确应为：22→0，33→0冲突→1，44→0冲突→1冲突→2。但原题答案可能为1？需重新计算：哈希表大小11，线性探测步长1。22→0；33→0冲突→0+1=1（空），存入1；44→0冲突→0+1=1（已存33），→0+2=2（空），存入2。因此正确答案应为2，可能题目存在笔误，此处按正确逻辑应为2。（注：原题可能存在笔误，正确计算应为2，但假设题目设定为其他情况，可能答案为1，需根据实际情况调整。）3.答案：9解析：初始数组[3,1,4,1,5,9,2,6]，大根堆要求父节点≥子节点。建堆过程从最后一个非叶子节点（下标(8/2)-1=3，值为1）开始调整。最终堆顶为最大值9。4.答案：(n&(n-1))==0&&n!=0解析：2的幂次的二进制表示只有1个1，n&(n-1)会消除最低位的1，结果为0（但n=0时也满足，需排除）。5.答案：8解析：回文子串包括：a（5个）、b（2个）、aba（2个：位置0-2，2-4）、bab（1个：位置1-3）。总个数5+2+2+1=10？实际计算：-长度1：5个（a,a,a,b,b？原字符串"ababa"为a(0),b(1),a(2),b(3),a(4)，长度1的回文5个；-长度2："ab","ba","ab","ba"均非回文；-长度3："aba"(0-2)、"bab"(1-3)、"aba"(2-4)→3个；-长度4："abab"（非）、"baba"（非）；-长度5："ababa"（是）→1个；总个数5+3+1=9？可能原题答案为8，需重新核对。正确回文子串应为：0-0(a),1-1(b),2-2(a),3-3(b),4-4(a),0-2(aba),1-3(bab),2-4(aba),0-4(ababa)→共9个。可能题目设定单个字符不计，但题目明确“单个字符视为回文”，故正确答案为9，可能题目存在误差。三、算法设计题1.思路：要求时间复杂度O(n)，需用哈希表记录元素出现次数。若k=0，需统计每个元素出现次数C，贡献C(C-1)/2个数对；若k≠0，遍历数组，对每个nums[i]，检查nums[i]-k是否在哈希表中，累加哈希表中nums[i]-k的出现次数。伪代码：```functionfindPairs(nums,k):ifk<0:return0count=0freq=哈希表（统计元素频率）fornuminnums:freq[num]=freq.get(num,0)+1fornuminfreq.keys():ifk==0:iffreq[num]>=2:count+=freq[num](freq[num]-1)//2else:if(num-k)infreq:count+=freq[num-k]returncount```2.思路：递归遍历二叉树，维护当前路径和当前路径列表。当到达叶子节点且路径和等于target时，记录路径。为优化空间，可采用回溯法（递归返回时移除当前节点）。伪代码：```classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightfunctionfindPath(root,target):result=[]current_path=[]defbacktrack(node,current_sum):ifnotnode:returncurrent_path.append(node.val)current_sum+=node.valifnotnode.leftandnotnode.rightandcurrent_sum==target:result.append(current_path.copy())backtrack(node.left,current_sum)backtrack(node.right,current_sum)current_path.pop()回溯backtrack(root,0)returnresult```四、编程题1.Python实现：```pythonimportsysfromcollectionsimportdefaultdictuser_ops=defaultdict(lambda:defaultdict(int))user_ops[用户ID][日期]=次数max_count=0max_user=""forlineinsys.stdin:line=line.strip()ifnotline:continueuid,ts,_=line.split()ts=int(ts)date=ts//86400转换为自然日（Unix时间戳每天86400秒）user_ops[uid][date]+=1更新单日最大值current=user_ops[uid][date]ifcurrent>max_countor(current==max_countanduid<max_user):max_count=currentmax_user=uid整理输出格式stat={uid:sum(d.values())foruid,dinuser_ops.items()}题目要求“当天”操作次数？原题描述可能为“每个用户当天”指所有天的当天？需明确。若题目要求统计每个用户在每个自然日的操作次数，输出应为{用户:{日期:次数}}，但原题示例输出为{用户ID:次数}，可能是指每个用户总操作次数。需根据题意调整。假设题目要求统计每个用户所有自然日的操作次数总和，则：修正：题目要求“每个用户当天（自然日）的操作次数”，可能是指按天统计，例如输入包含多天数据，输出每个用户在每个自然日的次数。但输出示例为{用户ID:次数}，可能题目表述有误，实际应为统计每个用户的总操作次数。此处按总次数处理。stat={uid:sum(d.values())foruid,dinuser_ops.items()}print(f"用户操作次数统计：{dict(stat)}")print(f"单日操作次数最多：{max_user}{max_count}")```2.C++实现：```cppinclude<unordered_map>include<list>classLRUCache{private:intcapacity;std::list<std::pair<int,int>>cache;//存储键值对，头部为最近使用std::unordered_map<int,std::list<std::pair<int,int>>::iterator>map;//键到链表迭代器的映射public:LRUCache(intcap):capacity(cap){}intget(intkey){if(map.fi