2025年計(jì)算機(jī)編程測試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.關(guān)于紅黑樹的性質(zhì)，以下描述錯(cuò)誤的是（）A.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)必須是黑色C.所有葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是紅色D.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑包含相同數(shù)量的黑色節(jié)點(diǎn)2.對(duì)長度為n的有序數(shù)組進(jìn)行二分查找，在最壞情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)3.以下操作系統(tǒng)調(diào)度算法中，屬于搶占式調(diào)度的是（）A.先來先服務(wù)（FCFS）B.短作業(yè)優(yōu)先（SJF）C.時(shí)間片輪轉(zhuǎn)（RR）D.高響應(yīng)比優(yōu)先（HRRN）4.在TCP/IP協(xié)議棧中，HTTP/2默認(rèn)使用的端口號(hào)是（）A.80B.443C.8080D.80005.關(guān)系型數(shù)據(jù)庫中，事務(wù)的“隔離性”（Isolation）指的是（）A.事務(wù)一旦提交，其結(jié)果不可撤銷B.事務(wù)執(zhí)行過程中不受其他事務(wù)干擾C.事務(wù)必須包含所有操作作為一個(gè)整體D.事務(wù)操作前后數(shù)據(jù)保持一致性6.以下設(shè)計(jì)模式中，用于解決對(duì)象間一對(duì)多依賴關(guān)系，當(dāng)一個(gè)對(duì)象狀態(tài)改變時(shí)通知所有依賴對(duì)象的是（）A.工廠模式B.觀察者模式C.單例模式D.策略模式7.編譯過程中，將源代碼轉(zhuǎn)換為詞法單元（Token）的階段是（）A.語法分析B.詞法分析C.語義分析D.代碼提供8.Java中，以下哪種垃圾回收算法適用于新生代且需要復(fù)制存活對(duì)象到另一塊內(nèi)存區(qū)域（）A.標(biāo)記-清除算法B.標(biāo)記-整理算法C.復(fù)制算法D.分代收集算法9.Python中，全局解釋器鎖（GIL）的主要作用是（）A.保證多線程間的內(nèi)存安全B.提高多線程執(zhí)行效率C.支持協(xié)程調(diào)度D.優(yōu)化垃圾回收性能10.分布式系統(tǒng)中，CAP定理的“C”指的是（）A.一致性（Consistency）B.可用性（Availability）C.分區(qū)容錯(cuò)性（PartitionTolerance）D.正確性（Correctness）二、填空題（每空2分，共20分）1.在快速排序的分區(qū)（Partition）過程中，假設(shè)選擇數(shù)組最后一個(gè)元素作為基準(zhǔn)（pivot），以下Python代碼的作用是將小于等于pivot的元素移到左側(cè)。請(qǐng)補(bǔ)全橫線處的代碼：```pythondefpartition(arr,low,high):pivot=arr[high]i=low1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]return______```2.Java中，使用`Thread`類創(chuàng)建多線程時(shí)，需要重寫的方法是______；若使用`synchronized`關(guān)鍵字實(shí)現(xiàn)同步，其鎖的對(duì)象可以是______（任填一種合法類型）。3.TCP三次握手中，客戶端首先發(fā)送______報(bào)文；服務(wù)器收到后回復(fù)______報(bào)文；最后客戶端發(fā)送______報(bào)文完成連接建立。4.哈希表中解決沖突的常用方法有______（如開放尋址法）和______（如鏈地址法）。5.動(dòng)態(tài)規(guī)劃解決最長公共子序列（LCS）問題時(shí)，狀態(tài)轉(zhuǎn)移方程為：若`X[i-1]==Y[j-1]`，則`dp[i][j]=dp[i-1][j-1]+1`；否則`dp[i][j]=max(______,______)`。三、編程題（共60分）1.（20分）給定一個(gè)只包含括號(hào)的字符串`s`（由`(`和`)`組成），計(jì)算其中有效括號(hào)的最大嵌套深度。有效括號(hào)定義為正確閉合的括號(hào)序列，例如`"((()())())"`的最大嵌套深度為3（最內(nèi)層括號(hào)深度為3）。要求：輸入：字符串`s`（長度≤10?）輸出：整數(shù)，表示最大嵌套深度示例：輸入`"(()())((()))"`，輸出`3`2.（40分）實(shí)現(xiàn)一個(gè)函數(shù)`min_edit_distance(s1,s2)`，計(jì)算兩個(gè)字符串`s1`和`s2`的最小編輯距離。編輯操作定義為：插入一個(gè)字符（成本1）刪除一個(gè)字符（成本1）替換一個(gè)字符（成本1，若字符相同則成本0）交換相鄰兩個(gè)字符（成本1，僅當(dāng)兩個(gè)字符相鄰且交換后更接近目標(biāo)字符串時(shí)可用）要求：輸入：兩個(gè)字符串`s1`、`s2`（長度均≤100）輸出：整數(shù)，表示最小編輯距離示例：輸入`s1="abcde",s2="abced"`，輸出`1`（交換'd'和'e'）；輸入`s1="kitten",s2="sitting"`，輸出`3`（替換'k'→'s'，替換'e'→'i'，插入'g'）--答案一、單項(xiàng)選擇題1.C（紅黑樹的葉子節(jié)點(diǎn)是黑色NIL節(jié)點(diǎn)）2.C（二分查找最壞情況為O(logn)）3.C（時(shí)間片輪轉(zhuǎn)屬于搶占式調(diào)度）4.B（HTTP/2默認(rèn)使用443端口（HTTPS），HTTP/1.1默認(rèn)80）5.B（隔離性指事務(wù)間互不干擾）6.B（觀察者模式實(shí)現(xiàn)一對(duì)多通知）7.B（詞法分析提供Token）8.C（復(fù)制算法用于新生代）9.A（GIL保證線程安全但限制多線程并行）10.A（CAP中的C是一致性）二、填空題1.`i+1`（返回基準(zhǔn)元素的最終位置）2.`run()`；對(duì)象實(shí)例/類對(duì)象（如`this`或`MyClass.class`）3.SYN；SYN+ACK；ACK4.開放尋址法；鏈地址法（或拉鏈法）5.`dp[i-1][j]`；`dp[i][j-1]`三、編程題1.最大嵌套深度解答思路：遍歷字符串，維護(hù)當(dāng)前深度計(jì)數(shù)器。遇到`(`時(shí)深度加1，遇到`)`時(shí)深度減1，記錄過程中的最大深度。代碼：```pythondefmax_nesting_depth(s:str)->int:max_depth=0current_depth=0forcharins:ifchar=='(':current_depth+=1ifcurrent_depth>max_depth:max_depth=current_depthelifchar==')':current_depth-=1returnmax_depth```2.最小編輯距離（含交換操作）解答思路：動(dòng)態(tài)規(guī)劃擴(kuò)展，狀態(tài)`dp[i][j]`表示`s1前i個(gè)字符`轉(zhuǎn)換為`s2前j個(gè)字符`的最小成本。除常規(guī)插入、刪除、替換外，當(dāng)`s1[i-1]==s2[j-2]`且`s1[i-2]==s2[j-1]`（i,j≥2）時(shí)，考慮交換操作，成本為`dp[i-2][j-2]+1`。代碼：```pythondefmin_edit_distance(s1:str,s2:str)->int:m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]初始化邊界foriinrange(m+1):dp[i][0]=i刪除s1前i個(gè)字符forjinrange(n+1):dp[0][j]=j插入s2前j個(gè)字符動(dòng)態(tài)規(guī)劃填充foriinrange(1,m+1):forjinrange(1,n+1):常規(guī)操作：插入、刪除、替換replace_cost=0ifs1[i-1]==s2[j-1]else1dp[i][j]=min(dp[i-1][j]+1,刪除dp[i][j-1]+1,插入dp[i-1][j-1]+replace_cost替換