2025年編碼考試題及答案一、單項選擇題（每題2分，共20分）1.以下關(guān)于Python數(shù)據(jù)結(jié)構(gòu)的描述中，正確的是（）A.列表（list）的元素必須是同一數(shù)據(jù)類型B.元組（tuple）的元素不可變，因此無法通過任何方式修改C.集合（set）的元素是無序且不重復(fù)的D.字典（dict）的鍵可以是列表類型答案：C解析：列表元素可以是任意類型（A錯誤）；元組本身不可變，但若元素是可變對象（如列表），其內(nèi)容可修改（B錯誤）；集合的特性是無序、唯一（C正確）；字典的鍵必須是不可變類型（列表可變，不能作為鍵，D錯誤）。2.執(zhí)行以下Java代碼后，輸出結(jié)果是（）```javapublicclassTest{publicstaticvoidmain(String[]args){inta=5;intb=a+++--a;System.out.println(b);}}```A.9B.10C.8D.7答案：B解析：a初始為5。a++是先取值后自增，此時a++的值為5，a變?yōu)?；--a是先自減后取值，此時a自減為5，--a的值為5。因此b=5+5=10。3.以下算法的時間復(fù)雜度為O(nlogn)的是（）A.冒泡排序B.快速排序（平均情況）C.插入排序D.順序查找答案：B解析：冒泡排序和插入排序的平均時間復(fù)雜度為O(n2)（A、C錯誤）；快速排序平均時間復(fù)雜度為O(nlogn)（B正確）；順序查找為O(n)（D錯誤）。4.對于長度為n的有序數(shù)組，使用二分查找的最壞時間復(fù)雜度是（）A.O(1)B.O(n)C.O(logn)D.O(n2)答案：C解析：二分查找每次將搜索范圍減半，最壞情況下需要log?n次比較，時間復(fù)雜度為O(logn)。5.以下關(guān)于數(shù)據(jù)庫事務(wù)的ACID特性描述中，錯誤的是（）A.原子性（Atomicity）：事務(wù)中的操作要么全部完成，要么全部不完成B.一致性（Consistency）：事務(wù)執(zhí)行前后數(shù)據(jù)庫狀態(tài)保持一致C.隔離性（Isolation）：多個事務(wù)并發(fā)執(zhí)行時，彼此互不干擾D.持久性（Durability）：事務(wù)一旦提交，對數(shù)據(jù)庫的修改永久保存答案：C解析：隔離性指多個事務(wù)并發(fā)執(zhí)行時，一個事務(wù)的執(zhí)行不應(yīng)影響其他事務(wù)的執(zhí)行結(jié)果，而非“互不干擾”（C錯誤）。6.以下Python代碼的輸出結(jié)果是（）```pythondeffunc(x):returnlambday:xyf=func(10)print(f(5))```A.10B.5C.50D.15答案：C解析：func返回一個lambda函數(shù)，該函數(shù)接收y并返回xy。f=func(10)時，x被綁定為10，調(diào)用f(5)即計算105=50。7.以下關(guān)于TCP和UDP的描述中，正確的是（）A.TCP是無連接的，UDP是面向連接的B.TCP適用于實時性要求高的場景（如視頻通話）C.UDP不保證數(shù)據(jù)的可靠傳輸D.TCP的傳輸效率高于UDP答案：C解析：TCP是面向連接的（A錯誤）；UDP無連接、不保證可靠傳輸?shù)珜崟r性好（C正確）；TCP因需要握手、確認(rèn)機(jī)制，效率低于UDP（D錯誤）；實時性要求高的場景常用UDP（B錯誤）。8.執(zhí)行以下C語言代碼后，變量c的值是（）```cinta=3,b=5;intc=(a>b)?a++:b++;```A.3B.4C.5D.6答案：C解析：條件表達(dá)式中a>b為假，執(zhí)行b++，但b++是先取值后自增，因此c取b的當(dāng)前值5，之后b變?yōu)?。9.以下關(guān)于二叉樹的描述中，正確的是（）A.完全二叉樹一定是滿二叉樹B.滿二叉樹的葉子節(jié)點都在同一層C.二叉樹的前序遍歷順序是左子樹→根→右子樹D.平衡二叉樹的左右子樹高度差可以大于1答案：B解析：滿二叉樹所有葉子節(jié)點在最后一層，且所有非葉子節(jié)點都有兩個子節(jié)點（B正確）；完全二叉樹不一定是滿二叉樹（A錯誤）；前序遍歷順序是根→左→右（C錯誤）；平衡二叉樹左右子樹高度差不超過1（D錯誤）。10.以下SQL語句中，用于修改表結(jié)構(gòu)的是（）A.UPDATEB.ALTERC.INSERTD.DELETE答案：B解析：ALTER用于修改表結(jié)構(gòu)（如添加列、修改列類型）；UPDATE修改數(shù)據(jù)（A錯誤）；INSERT插入數(shù)據(jù)（C錯誤）；DELETE刪除數(shù)據(jù)（D錯誤）。二、填空題（每空2分，共20分）1.Python中，使用`__________`關(guān)鍵字定義提供器函數(shù)，提供器通過`__________`語句返回值。答案：yield；yield2.Java中，接口的方法默認(rèn)是`__________`修飾的，抽象類中可以包含`__________`方法（非抽象方法）。答案：publicabstract；具體（或非抽象）3.快速排序的核心思想是`__________`，其平均時間復(fù)雜度為`__________`。答案：分治（或分區(qū)交換）；O(nlogn)4.數(shù)據(jù)庫中，索引的作用是`__________`，常見的索引類型包括`__________`（至少寫兩種）。答案：提高查詢效率；主鍵索引、唯一索引、普通索引（或B樹索引、哈希索引等）5.給定字符串`s="ababa"`，其最長回文子串的長度是`__________`；若使用動態(tài)規(guī)劃求解，狀態(tài)轉(zhuǎn)移方程為`dp[i][j]=(s[i]==s[j])&&(ji<2||dp[i+1][j-1])`，其中`dp[i][j]`表示`__________`。答案：5；子串s[i..j]是否為回文串三、編程題（共60分）1.（15分）編寫一個Python函數(shù)`count_substring(s:str,t:str)->int`，統(tǒng)計字符串`s`中包含子串`t`的所有不重疊出現(xiàn)次數(shù)。例如，當(dāng)`s="ababa",t="aba"`時，輸出1（因為"ababa"中"aba"出現(xiàn)在0-2位，但下一個可能的起始位置是2，此時子串為"ba"，不匹配，因此不重疊出現(xiàn)次數(shù)為1）。參考代碼：```pythondefcount_substring(s:str,t:str)->int:ifnottorlen(t)>len(s):return0count=0i=0t_len=len(t)whilei<=len(s)t_len:ifs[i:i+t_len]==t:count+=1i+=t_len不重疊，跳過t的長度else:i+=1returncount```2.（20分）設(shè)計一個Java類`LRUCache`，實現(xiàn)最近最少使用（LRU）緩存。要求支持以下操作：`get(intkey)`返回對應(yīng)值（不存在返回-1）；`put(intkey,intvalue)`插入或更新值，若緩存容量已滿則刪除最久未使用的鍵值對。要求時間復(fù)雜度為O(1)。參考代碼：```javaimportjava.util.HashMap;importjava.util.Map;classNode{intkey,value;Nodeprev,next;publicNode(intkey,intvalue){this.key=key;this.value=value;}}classDoubleLinkedList{Nodehead,tail;publicDoubleLinkedList(){head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicvoidaddToHead(Nodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}publicvoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}publicNoderemoveTail(){Nodelast=tail.prev;removeNode(last);returnlast;}}publicclassLRUCache{privateMap<Integer,Node>map;privateDoubleLinkedListcache;privateintcapacity;publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();cache=newDoubleLinkedList();}publicintget(intkey){if(!map.containsKey(key))return-1;Nodenode=map.get(key);cache.removeNode(node);cache.addToHead(node);//訪問后移到頭部returnnode.value;}publicvoidput(intkey,intvalue){if(map.containsKey(key)){Nodenode=map.get(key);node.value=value;cache.removeNode(node);cache.addToHead(node);}else{NodenewNode=newNode(key,value);if(map.size()==capacity){NodetailNode=cache.removeTail();map.remove(tailNode.key);//刪除最久未使用的}map.put(key,newNode);cache.addToHead(newNode);}}}```3.（25分）給定一個整數(shù)數(shù)組`nums`和一個整數(shù)`k`，編寫一個Python函數(shù)`max_sum_subarray(nums:list,k:int)->int`，找出數(shù)組中和最大的連續(xù)子數(shù)組（長度至少為1，最多為k）。例如，`nums=[1,2,-1,3],k=2`，最大和為`2+(-1)`？不，正確示例應(yīng)為：當(dāng)k=2時，可能的子數(shù)組有[1],[2],[-1],[3],[1,2],[2,-1],[-1,3]，和分別為1,2,-1,3,3,1,2，最大為3（子數(shù)組[3]或[1,2]）。需注意子數(shù)組長度可小于等于k。參考代碼：```pythondefmax_sum_subarray(nums:list,k:int)->int:n=len(nums)ifn==0ork<=0:return0max_sum=nums[0]current_sum=0滑動窗口結(jié)合前綴和優(yōu)化prefix=[0](n+1)foriinrange(n):prefix[i+1]=prefix[i]+nums[i]維護(hù)一個雙端隊列保存可能的最小前綴和索引fromcollectionsimportdequeq=deque()q.append(0)初始前綴和為0的索引foriinrange(1,n+1):移除超出窗口范圍的索引（ij<=k→j>=i-k）whileqandq[0]<ik:q.popleft()當(dāng)前最大和為prefix[i]最小prefix[j]current_max=prefix[i]prefix[q[0]]ifcurrent_max>max_sum:max_sum=current_max維護(hù)隊列：保持prefix[j]遞增，移除比當(dāng)前prefix[i]大的元素whileqandprefix[i]<=prefix[q[-1]]:q.pop()q.append(i)returnmax_sum```解析：該算法使用前綴和數(shù)組和雙端隊列優(yōu)化，時間復(fù)雜度為O(n)。前綴和數(shù)組`prefix[i]`表示前i個元素的和，子數(shù)組`nums[j..i-1]`的和為`prefix[i]prefix[j]`。通過維護(hù)一個雙端隊列保存可能的最小`prefix[j]`索引（j在[i-k,i-1]范圍內(nèi)），確保每次能快速找到最小`prefix[j]`，從而計算當(dāng)前窗口內(nèi)的最大子數(shù)組和。四、綜合應(yīng)用題（共20分）某電商平臺需要統(tǒng)計用戶在購物車中添加商品的行為數(shù)據(jù)，其中一條日志的格式為：`"用戶ID,商品ID,操作時間,操作類型（add/remove）"`。請編寫一個Python程序，實現(xiàn)以下功能：（1）讀取日志文件`log.txt`，每行一條日志；（2）統(tǒng)計每個用戶的購物車最終狀態(tài)（即所有操作完成后，用戶購物車中剩余的商品ID列表，按操作時間倒序排列，若時間相同則按商品ID升序排列）；（3）將結(jié)果輸出到`result.txt`，格式為`用戶ID:商品ID1,商品ID2,...`（商品順序按要求排列）。參考代碼：```pythonfromcollectionsimportdefaultdictdefprocess_logs(input_file,output_file):存儲用戶操作記錄：{用戶ID:[(時間戳,商品ID,操作類型)]}user_ops=defaultdict(list)讀取日志并解析withopen(input_file,'r',encoding='utf-8')asf:forlineinf:line=line.strip()ifnotline:continueparts=line.split(',')iflen(parts)!=4:continue跳過格式錯誤的行user_id,item_id,time_str,op=parts假設(shè)時間戳為可比較的字符串（如"2025-01-0112:00:00"）user_ops[user_id].append((time_str,item_id,op))處理每個用戶的最終購物車狀態(tài)result={}foruser_id,opsinuser_ops.items():按操作時間升序排序（便于處理順序）ops_sorted=sorted(ops,key=lambdax:(x[0],x[1]))cart=set()記錄每個商品的最后操作時間