2025年編程四級(jí)考試解析題及答案一、數(shù)據(jù)結(jié)構(gòu)與算法綜合題（本題30分）問(wèn)題描述：給定一個(gè)包含n個(gè)節(jié)點(diǎn)的帶權(quán)無(wú)向樹(shù)（節(jié)點(diǎn)編號(hào)1~n，邊權(quán)為正整數(shù)），定義兩個(gè)節(jié)點(diǎn)u和v的“關(guān)鍵路徑”為u到v路徑上的最大邊權(quán)?，F(xiàn)需設(shè)計(jì)算法，對(duì)所有節(jié)點(diǎn)對(duì)（u，v）（u<v），計(jì)算其關(guān)鍵路徑值的總和。要求時(shí)間復(fù)雜度不超過(guò)O(n2logn)，空間復(fù)雜度O(n2)以內(nèi)。輸入示例：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（注：節(jié)點(diǎn)對(duì)為(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)）解題思路：直接枚舉所有節(jié)點(diǎn)對(duì)并計(jì)算路徑最大邊權(quán)的時(shí)間復(fù)雜度為O(n3)（DFS/BFS遍歷路徑），無(wú)法滿足要求。需利用樹(shù)的性質(zhì)優(yōu)化：1.邊的貢獻(xiàn)分析：每條邊e的權(quán)值w，若其將樹(shù)分割為大小分別為s和t的兩個(gè)子樹(shù)（s+t=n），則e作為關(guān)鍵路徑的次數(shù)為st（因?yàn)榭鐑蓚€(gè)子樹(shù)的節(jié)點(diǎn)對(duì)路徑必經(jīng)過(guò)e，且當(dāng)e是路徑上的最大邊時(shí)才會(huì)被統(tǒng)計(jì)）。2.Kruskal重構(gòu)樹(shù)：按邊權(quán)從小到大排序，逐步合并子樹(shù)。每次合并時(shí)，當(dāng)前邊權(quán)w是連接兩個(gè)子樹(shù)的最大邊，此時(shí)該邊的貢獻(xiàn)為當(dāng)前兩子樹(shù)大小的乘積乘以w。最終總和即為所有邊的貢獻(xiàn)之和。具體步驟：1.將所有邊按權(quán)值從小到大排序。2.初始化并查集，每個(gè)節(jié)點(diǎn)初始父節(jié)點(diǎn)為自身，子樹(shù)大小為1。3.遍歷排序后的邊，對(duì)每條邊(u,v,w)，找到u和v所在集合的根su、sv。若su≠sv，則當(dāng)前邊的貢獻(xiàn)為size[su]size[sv]w，累加到總和。然后合并兩個(gè)集合，更新新集合的大小為size[su]+size[sv]。4.最終總和即為所有節(jié)點(diǎn)對(duì)的關(guān)鍵路徑值之和。代碼實(shí)現(xiàn)（Python）：```pythonclassUnionFind:def__init__(self,size):self.parent=list(range(size+1))節(jié)點(diǎn)編號(hào)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])按邊權(quán)升序排序uf=UnionFind(n)total=0foru,v,winedges:cnt=uf.union(u,v)total+=cntwreturntotal輸入示例測(cè)試n=4edges=[(1,2,3),(1,3,5),(2,4,4)]print(calculate_total(n,edges))輸出26```答案解析：該算法利用Kruskal重構(gòu)樹(shù)思想，將邊按權(quán)值排序后，通過(guò)并查集逐步合并子樹(shù)。每次合并時(shí)，當(dāng)前邊是連接兩個(gè)子樹(shù)的最大邊，因此所有跨子樹(shù)的節(jié)點(diǎn)對(duì)的關(guān)鍵路徑值必為該邊權(quán)值。通過(guò)統(tǒng)計(jì)每邊的貢獻(xiàn)次數(shù)（子樹(shù)大小乘積），最終總和即為所求。時(shí)間復(fù)雜度主要由排序（O(mlogm)，m為邊數(shù)，樹(shù)的邊數(shù)m=n-1）和并查集操作（近似O(nα(n))）決定，總復(fù)雜度為O(nlogn)，滿足要求。二、高級(jí)編程題（本題30分）問(wèn)題描述：設(shè)計(jì)一個(gè)Python類(lèi)`LogAnalyzer`，用于實(shí)時(shí)分析服務(wù)器日志流。日志格式為JSON字符串，包含以下字段：`timestamp`（時(shí)間戳，秒級(jí)）、`ip`（客戶端IP）、`status`（HTTP狀態(tài)碼，如200、404）、`endpoint`（請(qǐng)求路徑，如"/api/login"）。需實(shí)現(xiàn)以下功能：1.滑動(dòng)窗口統(tǒng)計(jì)：給定時(shí)間窗口大小T（秒），統(tǒng)計(jì)當(dāng)前窗口內(nèi)各`endpoint`的請(qǐng)求次數(shù)，返回TopK的`endpoint`（按次數(shù)降序，次數(shù)相同按字典序升序）。2.異常IP檢測(cè)：檢測(cè)連續(xù)出現(xiàn)至少N次4xx/5xx狀態(tài)碼的IP，返回這些IP列表（按首次出現(xiàn)異常的時(shí)間升序）。要求：支持動(dòng)態(tài)添加日志（`add_log(log_str:str)`方法）?；瑒?dòng)窗口基于最新日志的時(shí)間戳自動(dòng)調(diào)整，窗口左邊界為`current_timestampT`（current_timestamp為當(dāng)前日志的時(shí)間戳）。時(shí)間復(fù)雜度：滑動(dòng)窗口統(tǒng)計(jì)單次添加O(1)~O(M)（M為窗口內(nèi)不同endpoint數(shù)），異常檢測(cè)單次添加O(1)。解題思路：滑動(dòng)窗口統(tǒng)計(jì)：使用雙端隊(duì)列（deque）維護(hù)窗口內(nèi)的日志，按時(shí)間戳排序。每次添加新日志時(shí)，移除隊(duì)首所有時(shí)間戳小于`current_timestampT`的日志。用字典`endpoint_counts`記錄當(dāng)前窗口內(nèi)各endpoint的計(jì)數(shù)。每次移除舊日志時(shí)，對(duì)應(yīng)計(jì)數(shù)減1（若減至0則刪除鍵）；添加新日志時(shí)，對(duì)應(yīng)計(jì)數(shù)加1。統(tǒng)計(jì)TopK時(shí)，對(duì)`endpoint_counts`的鍵按值降序、字典序升序排序，取前K個(gè)。異常IP檢測(cè)：用字典`ip_status`記錄每個(gè)IP的最近狀態(tài)碼序列（僅保留最近的連續(xù)錯(cuò)誤碼）。結(jié)構(gòu)為`{ip:(current_count,first_timestamp)}`，其中`current_count`為當(dāng)前連續(xù)錯(cuò)誤次數(shù)，`first_timestamp`為本次連續(xù)錯(cuò)誤的起始時(shí)間。當(dāng)新日志狀態(tài)碼為4xx/5xx時(shí)：若IP不在`ip_status`中，或前一狀態(tài)碼非錯(cuò)誤碼，則初始化`current_count=1`，`first_timestamp=當(dāng)前時(shí)間戳`。否則，`current_count+=1`。當(dāng)狀態(tài)碼非錯(cuò)誤碼時(shí)，若IP在`ip_status`中，則刪除該記錄（連續(xù)中斷）。每次添加日志后，檢查`current_count>=N`的IP，收集到結(jié)果列表（需去重，按首次時(shí)間排序）。代碼實(shí)現(xiàn)：```pythonimportjsonfromcollectionsimportdeque,defaultdictclassLogAnalyzer:def__init__(self,T:int,N:int):self.T=T窗口大?。耄﹕elf.N=N異常連續(xù)次數(shù)閾值self.log_queue=deque()存儲(chǔ)窗口內(nèi)的日志（按時(shí)間戳升序）self.endpoint_counts=defaultdict(int)當(dāng)前窗口各endpoint計(jì)數(shù)self.ip_status=dict(){ip:(current_count,first_timestamp)}self.abnormal_ips=[]異常IP列表（按首次時(shí)間升序）self.seen_abnormal=set()已記錄的異常IP集合（避免重復(fù)）defadd_log(self,log_str:str):log=json.loads(log_str)ts=log['timestamp']ip=log['ip']status=log['status']endpoint=log['endpoint']滑動(dòng)窗口維護(hù)：移除過(guò)期日志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檢測(cè)邏輯is_error=400<=status<600ifis_error:ifipnotinself.ip_status:新錯(cuò)誤序列開(kāi)始self.ip_status[ip]=(1,ts)else:延續(xù)錯(cuò)誤序列current_count,first_ts=self.ip_status[ip]self.ip_status[ip]=(current_count+1,first_ts)檢查是否達(dá)到閾值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:非錯(cuò)誤狀態(tài)，中斷連續(xù)計(jì)數(shù)ifipinself.ip_status:delself.ip_status[ip]對(duì)異常IP列表按首次時(shí)間排序（僅需在新增時(shí)維護(hù)順序）self.abnormal_ips.sort(key=lambdax:x[0])defget_top_endpoints(self,K:int)->list:按次數(shù)降序，字典序升序排序sorted_endpoints=sorted(self.endpoint_counts.keys(),key=lambdae:(-self.endpoint_counts[e],e))returnsorted_endpoints[:K]defget_abnormal_ips(self)->list:僅返回IP列表（已按首次時(shí)間排序）return[ipfor_,ipinself.abnormal_ips]```答案解析：滑動(dòng)窗口通過(guò)雙端隊(duì)列維護(hù)時(shí)間范圍內(nèi)的日志，保證每次添加操作僅需移除隊(duì)首過(guò)期日志（均攤O(1)），計(jì)數(shù)用字典動(dòng)態(tài)更新，統(tǒng)計(jì)TopK時(shí)排序復(fù)雜度為O(MlogM)（M為不同endpoint數(shù)，通常遠(yuǎn)小于n）。異常IP檢測(cè)利用字典跟蹤每個(gè)IP的連續(xù)錯(cuò)誤狀態(tài)，狀態(tài)更新和檢查均為O(1)操作，保證了高效性。異常IP列表通過(guò)記錄首次時(shí)間并排序，確保結(jié)果順序正確。三、算法設(shè)計(jì)與優(yōu)化題（本題20分）問(wèn)題描述：給定一個(gè)長(zhǎng)度為m的整數(shù)數(shù)組A和長(zhǎng)度為n的整數(shù)數(shù)組B（m≤n），找出B中所有長(zhǎng)度為m的連續(xù)子數(shù)組，使得該子數(shù)組是A的一個(gè)排列（即元素相同，順序可能不同）。返回這些子數(shù)組的起始索引（索引從0開(kāi)始）。示例：A=[1,2,1]，B=[1,1,2,1,3]，輸出[0,1,2]（子數(shù)組[1,1,2]（索引0-2）包含1,1,2，是A的排列；[1,2,1]（索引1-3）是A的排列；[2,1,3]（索引2-4）不包含3，故排除）。要求：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)（僅允許使用固定大小的額外空間）。解題思路：常規(guī)方法是滑動(dòng)窗口+哈希表統(tǒng)計(jì)字符頻率，但哈希表空間復(fù)雜度為O(m)（m可能很大），不滿足要求。需利用數(shù)組代替哈希表，并通過(guò)計(jì)數(shù)差值優(yōu)化。1.頻率數(shù)組：由于整數(shù)范圍未指定，假設(shè)為有限范圍（如題目隱含整數(shù)在小范圍內(nèi)，或擴(kuò)展為使用字典但優(yōu)化空間）。此處假設(shè)整數(shù)范圍為[-1000,1000]，用數(shù)組`count`記錄A中各數(shù)的頻率，`window_count`記錄當(dāng)前窗口的頻率。2.差異計(jì)數(shù)：維護(hù)變量`diff`表示`count`與`window_count`不同的元素個(gè)數(shù)。當(dāng)`diff=0`時(shí)，窗口是A的排列。3.滑動(dòng)窗口：初始填充前m個(gè)元素到窗口，計(jì)算`diff`。然后滑動(dòng)窗口（右移一位），更新`window_count`和`diff`，每次檢查`diff=0`時(shí)記錄索引。代碼實(shí)現(xiàn)（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的頻率統(tǒng)計(jì)for(intnum:A)count[num]++;unordered_map<int,int>window_count;intdiff=count.size();//初始差異數(shù)為count的鍵數(shù)vector<int>res;//初始化窗口（前m個(gè)元素）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);//滑動(dòng)窗口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;}```答案解析：頻率統(tǒng)計(jì)使用哈希表，空間復(fù)雜度為O(m)（但題目要求O(1)，若整數(shù)范圍有限，可用固定大小數(shù)組代替哈希表，如整數(shù)范圍在[-1000,1000]，則數(shù)組大小為2001，滿足O(1)）。`diff`變量跟蹤頻率差異數(shù)，初始為`count`的鍵數(shù)。每次窗口滑動(dòng)時(shí)，調(diào)整左右元素的頻率計(jì)數(shù)，并更新`diff`。當(dāng)`diff=0`時(shí)，窗口內(nèi)元素頻率與A完全一致，即為排列。時(shí)間復(fù)雜度為O(n)（每個(gè)元素僅被處理兩次：加入和移除窗口）。四、系統(tǒng)設(shè)計(jì)題（本題20分）問(wèn)題描述：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接服務(wù)系統(tǒng)，要求支持以下功能：短鏈接提供：將長(zhǎng)URL轉(zhuǎn)換為固定長(zhǎng)度（如6位）的短碼，支持自定義短碼（可選）。短鏈接跳轉(zhuǎn)：根據(jù)短碼快速跳轉(zhuǎn)至原長(zhǎng)URL。統(tǒng)計(jì)功能：記錄每個(gè)短碼的訪問(wèn)次數(shù)、訪問(wèn)IP、訪問(wèn)時(shí)間。要求：短碼全局唯一，碰撞概率低于1e-9。提供和跳轉(zhuǎn)的響應(yīng)時(shí)間≤100ms。支持QPS≥10萬(wàn)。設(shè)計(jì)思路：1.短碼提供策略：自增ID+基數(shù)轉(zhuǎn)換：維護(hù)全局自增ID（如數(shù)據(jù)庫(kù)或Redis的原子計(jì)數(shù)器），將ID轉(zhuǎn)換為62進(jìn)制（0-9,a-z,A-Z），得到6位短碼（62^6≈568億，足夠覆蓋大多數(shù)場(chǎng)景）。