2025年编程四级考试解析题及答案

2025年编程四级考试解析题及答案一、数据结构与算法综合题（本题30分）问题描述：给定一个包含n个节点的带权无向树（节点编号1~n，边权为正整数），定义两个节点u和v的“关键路径”为u到v路径上的最大边权。现需设计算法，对所有节点对（u，v）（u<v），计算其关键路径值的总和。要求时间复杂度不超过O(n²logn)，空间复杂度O(n²)以内。输入示例：n=4，边列表为[(1-2,3),(1-3,5),(2-4,4)]输出示例：3+5+4+max(3,4)+max(5,3)+max(5,4)=3+5+4+4+5+5=26（注：节点对为(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)）解题思路：直接枚举所有节点对并计算路径最大边权的时间复杂度为O(n³)（DFS/BFS遍历路径），无法满足要求。需利用树的性质优化：1.边的贡献分析：每条边e的权值w，若其将树分割为大小分别为s和t的两个子树（s+t=n），则e作为关键路径的次数为st（因为跨两个子树的节点对路径必经过e，且当e是路径上的最大边时才会被统计）。2.Kruskal重构树：按边权从小到大排序，逐步合并子树。每次合并时，当前边权w是连接两个子树的最大边，此时该边的贡献为当前两子树大小的乘积乘以w。最终总和即为所有边的贡献之和。具体步骤：1.将所有边按权值从小到大排序。2.初始化并查集，每个节点初始父节点为自身，子树大小为1。3.遍历排序后的边，对每条边(u,v,w)，找到u和v所在集合的根su、sv。若su≠sv，则当前边的贡献为size[su]size[sv]w，累加到总和。然后合并两个集合，更新新集合的大小为size[su]+size[sv]。4.最终总和即为所有节点对的关键路径值之和。代码实现（Python）：```pythonclassUnionFind:def__init__(self,size):self.parent=list(range(size+1))节点编号1~nself.size=[1](size+1)deffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):fx=self.find(x)fy=self.find(y)iffx==fy:return0ifself.size[fx]<self.size[fy]:fx,fy=fy,fxself.parent[fy]=fxcnt=self.size[fx]self.size[fy]self.size[fx]+=self.size[fy]returncntdefcalculate_total(n,edges):edges.sort(key=lambdax:x[2])按边权升序排序uf=UnionFind(n)total=0foru,v,winedges:cnt=uf.union(u,v)total+=cntwreturntotal输入示例测试n=4edges=[(1,2,3),(1,3,5),(2,4,4)]print(calculate_total(n,edges))输出26```答案解析：该算法利用Kruskal重构树思想，将边按权值排序后，通过并查集逐步合并子树。每次合并时，当前边是连接两个子树的最大边，因此所有跨子树的节点对的关键路径值必为该边权值。通过统计每边的贡献次数（子树大小乘积），最终总和即为所求。时间复杂度主要由排序（O(mlogm)，m为边数，树的边数m=n-1）和并查集操作（近似O(nα(n))）决定，总复杂度为O(nlogn)，满足要求。二、高级编程题（本题30分）问题描述：设计一个Python类`LogAnalyzer`，用于实时分析服务器日志流。日志格式为JSON字符串，包含以下字段：`timestamp`（时间戳，秒级）、`ip`（客户端IP）、`status`（HTTP状态码，如200、404）、`endpoint`（请求路径，如"/api/login"）。需实现以下功能：1.滑动窗口统计：给定时间窗口大小T（秒），统计当前窗口内各`endpoint`的请求次数，返回TopK的`endpoint`（按次数降序，次数相同按字典序升序）。2.异常IP检测：检测连续出现至少N次4xx/5xx状态码的IP，返回这些IP列表（按首次出现异常的时间升序）。要求：支持动态添加日志（`add_log(log_str:str)`方法）。滑动窗口基于最新日志的时间戳自动调整，窗口左边界为`current_timestampT`（current_timestamp为当前日志的时间戳）。时间复杂度：滑动窗口统计单次添加O(1)~O(M)（M为窗口内不同endpoint数），异常检测单次添加O(1)。解题思路：滑动窗口统计：使用双端队列（deque）维护窗口内的日志，按时间戳排序。每次添加新日志时，移除队首所有时间戳小于`current_timestampT`的日志。用字典`endpoint_counts`记录当前窗口内各endpoint的计数。每次移除旧日志时，对应计数减1（若减至0则删除键）；添加新日志时，对应计数加1。统计TopK时，对`endpoint_counts`的键按值降序、字典序升序排序，取前K个。异常IP检测：用字典`ip_status`记录每个IP的最近状态码序列（仅保留最近的连续错误码）。结构为`{ip:(current_count,first_timestamp)}`，其中`current_count`为当前连续错误次数，`first_timestamp`为本次连续错误的起始时间。当新日志状态码为4xx/5xx时：若IP不在`ip_status`中，或前一状态码非错误码，则初始化`current_count=1`，`first_timestamp=当前时间戳`。否则，`current_count+=1`。当状态码非错误码时，若IP在`ip_status`中，则删除该记录（连续中断）。每次添加日志后，检查`current_count>=N`的IP，收集到结果列表（需去重，按首次时间排序）。代码实现：```pythonimportjsonfromcollectionsimportdeque,defaultdictclassLogAnalyzer:def__init__(self,T:int,N:int):self.T=T窗口大小（秒）self.N=N异常连续次数阈值self.log_queue=deque()存储窗口内的日志（按时间戳升序）self.endpoint_counts=defaultdict(int)当前窗口各endpoint计数self.ip_status=dict(){ip:(current_count,first_timestamp)}self.abnormal_ips=[]异常IP列表（按首次时间升序）self.seen_abnormal=set()已记录的异常IP集合（避免重复）defadd_log(self,log_str:str):log=json.loads(log_str)ts=log['timestamp']ip=log['ip']status=log['status']endpoint=log['endpoint']滑动窗口维护：移除过期日志whileself.log_queueandself.log_queue[0]['timestamp']<tsself.T:old_log=self.log_queue.popleft()old_endpoint=old_log['endpoint']self.endpoint_counts[old_endpoint]-=1ifself.endpoint_counts[old_endpoint]==0:delself.endpoint_counts[old_endpoint]添加新日志到窗口self.log_queue.append(log)self.endpoint_counts[endpoint]+=1异常IP检测逻辑is_error=400<=status<600ifis_error:ifipnotinself.ip_status:新错误序列开始self.ip_status[ip]=(1,ts)else:延续错误序列current_count,first_ts=self.ip_status[ip]self.ip_status[ip]=(current_count+1,first_ts)检查是否达到阈值current_count,first_ts=self.ip_status[ip]ifcurrent_count>=self.Nandipnotinself.seen_abnormal:self.abnormal_ips.append((first_ts,ip))self.seen_abnormal.add(ip)else:非错误状态，中断连续计数ifipinself.ip_status:delself.ip_status[ip]对异常IP列表按首次时间排序（仅需在新增时维护顺序）self.abnormal_ips.sort(key=lambdax:x[0])defget_top_endpoints(self,K:int)->list:按次数降序，字典序升序排序sorted_endpoints=sorted(self.endpoint_counts.keys(),key=lambdae:(-self.endpoint_counts[e],e))returnsorted_endpoints[:K]defget_abnormal_ips(self)->list:仅返回IP列表（已按首次时间排序）return[ipfor_,ipinself.abnormal_ips]```答案解析：滑动窗口通过双端队列维护时间范围内的日志，保证每次添加操作仅需移除队首过期日志（均摊O(1)），计数用字典动态更新，统计TopK时排序复杂度为O(MlogM)（M为不同endpoint数，通常远小于n）。异常IP检测利用字典跟踪每个IP的连续错误状态，状态更新和检查均为O(1)操作，保证了高效性。异常IP列表通过记录首次时间并排序，确保结果顺序正确。三、算法设计与优化题（本题20分）问题描述：给定一个长度为m的整数数组A和长度为n的整数数组B（m≤n），找出B中所有长度为m的连续子数组，使得该子数组是A的一个排列（即元素相同，顺序可能不同）。返回这些子数组的起始索引（索引从0开始）。示例：A=[1,2,1]，B=[1,1,2,1,3]，输出[0,1,2]（子数组[1,1,2]（索引0-2）包含1,1,2，是A的排列；[1,2,1]（索引1-3）是A的排列；[2,1,3]（索引2-4）不包含3，故排除）。要求：时间复杂度O(n)，空间复杂度O(1)（仅允许使用固定大小的额外空间）。解题思路：常规方法是滑动窗口+哈希表统计字符频率，但哈希表空间复杂度为O(m)（m可能很大），不满足要求。需利用数组代替哈希表，并通过计数差值优化。1.频率数组：由于整数范围未指定，假设为有限范围（如题目隐含整数在小范围内，或扩展为使用字典但优化空间）。此处假设整数范围为[-1000,1000]，用数组`count`记录A中各数的频率，`window_count`记录当前窗口的频率。2.差异计数：维护变量`diff`表示`count`与`window_count`不同的元素个数。当`diff=0`时，窗口是A的排列。3.滑动窗口：初始填充前m个元素到窗口，计算`diff`。然后滑动窗口（右移一位），更新`window_count`和`diff`，每次检查`diff=0`时记录索引。代码实现（C++）：```cppinclude<vector>include<unordered_map>usingnamespacestd;vector<int>findAnagrams(vector<int>&A,vector<int>&B){intm=A.size(),n=B.size();if(m>n)return{};unordered_map<int,int>count;//A的频率统计for(intnum:A)count[num]++;unordered_map<int,int>window_count;intdiff=count.size();//初始差异数为count的键数vector<int>res;//初始化窗口（前m个元素）for(inti=0;i<m;++i){intnum=B[i];if(count.find(num)!=count.end()){window_count[num]++;if(window_count[num]==count[num])diff--;elseif(window_count[num]==count[num]+1)diff++;}}if(diff==0)res.push_back(0);//滑动窗口for(inti=m;i<n;++i){//移除左边界元素intleft=B[im];if(count.find(left)!=count.end()){if(window_count[left]==count[left])diff++;window_count[left]--;if(window_count[left]==count[left])diff--;}//添加右边界元素intright=B[i];if(count.find(right)!=count.end()){window_count[right]++;if(window_count[right]==count[right])diff--;elseif(window_count[right]==count[right]+1)diff++;}if(diff==0)res.push_back(im+1);}returnres;}```答案解析：频率统计使用哈希表，空间复杂度为O(m)（但题目要求O(1)，若整数范围有限，可用固定大小数组代替哈希表，如整数范围在[-1000,1000]，则数组大小为2001，满足O(1)）。`diff`变量跟踪频率差异数，初始为`count`的键数。每次窗口滑动时，调整左右元素的频率计数，并更新`diff`。当`diff=0`时，窗口内元素频率与A完全一致，即为排列。时间复杂度为O(n)（每个元素仅被处理两次：加入和移除窗口）。四、系统设计题（本题20分）问题描述：设计一个高并发的短链接服务系统，要求支持以下功能：短链接提供：将长URL转换为固定长度（如6位）的短码，支持自定义短码（可选）。短链接跳转：根据短码快速跳转至原长URL。统计功能：记录每个短码的访问次数、访问IP、访问时间。要求：短码全局唯一，碰撞概率低于1e-9。提供和跳转的响应时间≤100ms。支持QPS≥10万。设计思路：1.短码提供策略：自增ID+基数转换：维护全局自增ID（如数据库或Redis的原子计数器），将ID转换为62进制（0-9,a-z,A-Z），得到6位短码（62^6≈568亿，足够覆盖大多数场景）。