2025年高頻計算機(jī)面試題庫及答案1.反轉(zhuǎn)鏈表時，迭代法和遞歸法的實現(xiàn)步驟及時間空間復(fù)雜度差異？迭代法實現(xiàn)步驟：初始化三個指針prev（初始為null）、curr（頭節(jié)點(diǎn)）、next（臨時保存curr下一個節(jié)點(diǎn)）。循環(huán)中，先保存curr.next到next，然后將curr.next指向prev，接著prev和curr分別后移（prev=curr，curr=next），直到curr為null時結(jié)束，prev即為新頭節(jié)點(diǎn)。時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。遞歸法實現(xiàn)步驟：遞歸終止條件是當(dāng)前節(jié)點(diǎn)或下一個節(jié)點(diǎn)為null，返回當(dāng)前節(jié)點(diǎn)（即尾節(jié)點(diǎn)作為新頭）。遞歸調(diào)用處理子問題（反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之后的部分），然后將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)（即原后繼節(jié)點(diǎn)的next指向自己），最后將當(dāng)前節(jié)點(diǎn)的next設(shè)為null（斷開原連接）。時間復(fù)雜度O(n)，空間復(fù)雜度O(n)（遞歸棧深度）。差異核心在于遞歸隱含使用棧空間，迭代則是原地操作。2.二叉樹中如何找到兩個節(jié)點(diǎn)的最近公共祖先（LCA）？若樹是二叉搜索樹（BST），利用其性質(zhì)：LCA的值介于兩節(jié)點(diǎn)值之間（或等于其中一個）。從根節(jié)點(diǎn)開始，若當(dāng)前節(jié)點(diǎn)值大于兩節(jié)點(diǎn)值，遞歸左子樹；若小于則遞歸右子樹；否則當(dāng)前節(jié)點(diǎn)即為LCA。若是普通二叉樹，采用后序遍歷：遞歸左右子樹，若左子樹找到一個節(jié)點(diǎn)、右子樹找到另一個節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)是LCA；若僅左子樹找到，返回左子樹結(jié)果；僅右子樹找到則返回右子樹結(jié)果；都沒找到返回null。特殊情況：若其中一個節(jié)點(diǎn)是另一個的祖先，直接返回該祖先節(jié)點(diǎn)。示例代碼（普通二叉樹）：```javapublicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null||root==p||root==q)returnroot;TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null)returnroot;returnleft!=null?left:right;}```3.堆排序的核心步驟是什么？如何優(yōu)化其穩(wěn)定性？核心步驟：①建堆（將數(shù)組調(diào)整為大頂堆或小頂堆，從最后一個非葉子節(jié)點(diǎn)開始向前遍歷，執(zhí)行下沉操作）；②排序（將堆頂元素與末尾元素交換，縮小堆范圍，重新調(diào)整堆，重復(fù)直到堆為空）。堆排序不穩(wěn)定的原因是交換堆頂與末尾元素時，可能破壞相同值元素的相對順序。優(yōu)化穩(wěn)定性需額外記錄元素原始位置，或在比較時優(yōu)先按原始位置排序（如將元素封裝為對象，包含值和索引，比較時若值相同則按索引排序），但這會增加空間復(fù)雜度（O(n)），實際應(yīng)用中堆排序因不穩(wěn)定性較少用于需要穩(wěn)定排序的場景。4.進(jìn)程與線程的本質(zhì)區(qū)別是什么？為什么多線程比多進(jìn)程更高效？本質(zhì)區(qū)別：進(jìn)程是資源分配的最小單位（擁有獨(dú)立的內(nèi)存空間、文件描述符等），線程是CPU調(diào)度的最小單位（共享進(jìn)程資源，僅擁有獨(dú)立的棧和寄存器）。多線程更高效的原因：①線程創(chuàng)建/銷毀開銷?。o需分配新內(nèi)存空間，只需分配?？臻g）；②線程間通信無需經(jīng)過內(nèi)核（共享內(nèi)存直接通信，而進(jìn)程間通信需通過管道、消息隊列等內(nèi)核機(jī)制）；③上下文切換代價低（線程切換僅需保存/恢復(fù)寄存器和棧，進(jìn)程切換需保存/恢復(fù)所有資源和頁表）。但需注意，多線程受限于GIL（如Python）或CPU核心數(shù)，并非絕對高效。5.虛擬內(nèi)存的作用及實現(xiàn)機(jī)制？作用：①擴(kuò)展物理內(nèi)存（將部分?jǐn)?shù)據(jù)存于磁盤，程序無需等待物理內(nèi)存足夠即可運(yùn)行）；②隔離進(jìn)程（每個進(jìn)程擁有獨(dú)立虛擬地址空間，避免地址沖突）；③提高內(nèi)存利用率（通過頁面置換，按需加載必要數(shù)據(jù)）。實現(xiàn)機(jī)制：基于頁表（記錄虛擬頁到物理頁的映射）和缺頁中斷。當(dāng)程序訪問的虛擬頁未加載到物理內(nèi)存時，觸發(fā)缺頁中斷，操作系統(tǒng)從磁盤讀取該頁到內(nèi)存（若內(nèi)存不足則通過頁面置換算法如LRU、FIFO淘汰部分頁），更新頁表后恢復(fù)程序執(zhí)行。虛擬地址空間通常分為用戶空間和內(nèi)核空間（如Linux中32位系統(tǒng)用戶空間3GB，內(nèi)核空間1GB）。6.死鎖的四個必要條件是什么？如何預(yù)防和避免死鎖？四個必要條件：互斥（資源同一時間只能被一個進(jìn)程使用）、占有且等待（進(jìn)程持有資源并請求其他資源）、不可搶占（資源只能被持有者主動釋放）、循環(huán)等待（進(jìn)程間形成資源請求環(huán)）。預(yù)防方法：破壞必要條件。①破壞互斥：使用可共享資源（如只讀文件），但多數(shù)資源本身是互斥的（如打印機(jī)），此方法適用場景有限；②破壞占有且等待：要求進(jìn)程一次性申請所有所需資源（需預(yù)知所有資源，可能導(dǎo)致資源浪費(fèi)）；③破壞不可搶占：允許系統(tǒng)搶占進(jìn)程資源（需支持資源狀態(tài)保存，如CPU資源）；④破壞循環(huán)等待：對資源編號，要求進(jìn)程按遞增順序申請（避免環(huán)的形成）。避免方法：動態(tài)檢測資源分配狀態(tài)，使用銀行家算法（模擬資源分配，確保系統(tǒng)處于安全狀態(tài)）。但銀行家算法因計算復(fù)雜度高，實際中多用于理論分析。7.TCP三次握手的具體過程？為什么不能兩次或四次？過程：①客戶端發(fā)送SYN=1，seq=x（初始序號）的報文，進(jìn)入SYN_SENT狀態(tài)；②服務(wù)器收到后發(fā)送SYN=1，ACK=1，seq=y，ack=x+1的報文，進(jìn)入SYN_RCVD狀態(tài)；③客戶端發(fā)送ACK=1，seq=x+1，ack=y+1的報文，進(jìn)入ESTABLISHED狀態(tài)，服務(wù)器收到后也進(jìn)入該狀態(tài)。不能兩次的原因：防止失效的連接請求報文段被服務(wù)器接收。若客戶端發(fā)送的SYN因網(wǎng)絡(luò)延遲滯留，客戶端超時重發(fā)新SYN并建立連接，舊SYN到達(dá)時，若兩次握手則服務(wù)器直接建立連接，導(dǎo)致客戶端無此連接需求而浪費(fèi)資源。三次握手讓客戶端確認(rèn)服務(wù)器收到了自己的SYN，避免上述問題。不能四次的原因：服務(wù)器的SYN和ACK可合并發(fā)送（SYN+ACK），減少一次報文交互，提升連接建立效率。8.HTTP1.1與HTTP2.0的主要區(qū)別？如何解決隊頭阻塞問題？主要區(qū)別：①二進(jìn)制分幀（HTTP2將報文拆分為二進(jìn)制幀，多路復(fù)用，而HTTP1.1是文本格式，按請求順序處理）；②多路復(fù)用（一個TCP連接可并發(fā)處理多個請求/響應(yīng)，HTTP1.1需通過長連接（keep-alive）或多連接實現(xiàn)并發(fā)）；③頭部壓縮（HPACK算法壓縮請求頭，減少冗余數(shù)據(jù)，HTTP1.1每次請求需重復(fù)發(fā)送完整頭部）；④服務(wù)器推送（服務(wù)器主動向客戶端發(fā)送資源，如HTML引用的CSS/JS，HTTP1.1需客戶端逐個請求）。HTTP1.1的隊頭阻塞：因請求按順序處理，若一個請求的響應(yīng)未到達(dá)，后續(xù)請求需等待。解決方式：使用CDN分散請求、并行多連接（瀏覽器通常限制6-8個）、雪碧圖合并資源等。HTTP2通過多路復(fù)用，不同請求的幀交錯傳輸，接收方按流標(biāo)識符重組，徹底解決了應(yīng)用層的隊頭阻塞（但TCP層仍可能因丟包導(dǎo)致阻塞，需結(jié)合TLS1.3等優(yōu)化）。9.事務(wù)的ACID特性分別指什么？MySQL如何實現(xiàn)這些特性？ACID：原子性（Atomicity，事務(wù)要么全做要么全不做）、一致性（Consistency，事務(wù)執(zhí)行前后數(shù)據(jù)保持合法狀態(tài)）、隔離性（Isolation，事務(wù)間互不干擾）、持久性（Durability，事務(wù)提交后數(shù)據(jù)永久保存）。實現(xiàn)：①原子性：通過undolog（回滾日志）實現(xiàn)，事務(wù)執(zhí)行時記錄數(shù)據(jù)修改前的狀態(tài)，異常時根據(jù)undolog回滾。②一致性：依賴原子性、隔離性和應(yīng)用層邏輯共同保證，如約束檢查（主鍵、外鍵）在事務(wù)執(zhí)行中自動觸發(fā)。③隔離性：通過鎖（共享鎖、排他鎖）和MVCC（多版本并發(fā)控制，InnoDB的undo日志提供數(shù)據(jù)快照）實現(xiàn)，不同隔離級別（讀未提交、讀已提交、可重復(fù)讀、串行化）對應(yīng)不同的鎖策略和快照可見性規(guī)則。④持久性：通過redolog（重做日志）實現(xiàn)，事務(wù)提交時先將redolog寫入磁盤（WAL，預(yù)寫日志），數(shù)據(jù)頁修改延遲刷新到磁盤，崩潰時通過redolog恢復(fù)未持久化的數(shù)據(jù)。10.索引的類型有哪些？什么情況下不適合創(chuàng)建索引？類型：①按數(shù)據(jù)結(jié)構(gòu)：B+樹索引（MySQL默認(rèn)，適合范圍查詢）、哈希索引（Redis使用，適合等值查詢，不支持范圍）、全文索引（針對文本內(nèi)容，MySQL的FULLTEXT）；②按字段數(shù)量：單列索引、復(fù)合索引（多字段聯(lián)合，遵循最左匹配原則）；③按約束：主鍵索引（唯一且非空）、唯一索引（值唯一，允許null）、普通索引（無約束）；④按存儲方式：聚集索引（數(shù)據(jù)行與索引存儲在一起，InnoDB主鍵為聚集索引，一個表僅有一個）、非聚集索引（索引與數(shù)據(jù)分開存儲，需回表查詢）。不適合索引的情況：①字段更新頻繁（索引維護(hù)增加寫開銷）；②數(shù)據(jù)區(qū)分度低（如性別字段，僅“男/女”，索引效果差）；③表數(shù)據(jù)量?。ㄈ頀呙璞人饕檎腋欤虎懿樵儣l件不涉及索引字段（如WHERE條件為未索引的字段）；⑤覆蓋索引無法滿足（非聚集索引查詢需回表，若回表成本高于全表掃描則不適用）。11.synchronized和ReentrantLock的區(qū)別？如何選擇？區(qū)別：①鎖獲取方式：synchronized是關(guān)鍵字，JVM隱式管理（自動釋放）；ReentrantLock是類（java.util.concurrent.locks），需顯式調(diào)用lock()和unlock()（通常在finally塊中釋放）。②鎖特性：ReentrantLock支持公平鎖（按等待隊列順序獲?。┖头枪芥i（默認(rèn)，提高吞吐量），synchronized僅非公平；ReentrantLock可響應(yīng)中斷（lockInterruptibly()）、嘗試獲取鎖（tryLock()），synchronized無法中斷等待。③條件變量：ReentrantLock通過Condition對象支持多個等待隊列（如生產(chǎn)者-消費(fèi)者模型中區(qū)分讀/寫等待），synchronized僅一個wait/notify隊列。④性能：早期版本synchronized因重量鎖性能差，JDK6后引入偏向鎖、輕量級鎖、自旋鎖優(yōu)化，兩者性能接近，高競爭場景下ReentrantLock更靈活。選擇：簡單同步用synchronized（代碼簡潔）；需要公平鎖、可中斷、嘗試鎖或多條件變量時用ReentrantLock。12.JVM內(nèi)存模型中各區(qū)域的作用及常見異常？JVM內(nèi)存分為：①程序計數(shù)器（PC寄存器）：記錄當(dāng)前線程執(zhí)行的字節(jié)碼行號，線程私有，無OOM（OutOfMemoryError）。②Java虛擬機(jī)棧：存儲棧幀（局部變量表、操作數(shù)棧、動態(tài)鏈接、方法出口），線程私有。若線程請求棧深度超過限制（如遞歸未終止），拋StackOverflowError；若動態(tài)擴(kuò)展時內(nèi)存不足，拋OOM。③本地方法棧：與虛擬機(jī)棧類似，服務(wù)于本地方法（如native方法），HotSpot將其與虛擬機(jī)棧合并，異常同虛擬機(jī)棧。④堆（Heap）：存放對象實例和數(shù)組，線程共享。若對象分配時內(nèi)存不足，拋OOM（如“Javaheapspace”）。⑤方法區(qū)（元空間，JDK8后）：存儲類信息、常量、靜態(tài)變量、即時編譯代碼等，線程共享。若類元數(shù)據(jù)過多（如動態(tài)提供大量類），拋OOM（“Metaspace”）。⑥運(yùn)行時常量池：方法區(qū)的一部分，存儲編譯期提供的常量和符號引用，JDK7后移至堆中，異常同堆。13.CAP定理的具體含義？分布式系統(tǒng)中如何權(quán)衡？CAP指一致性（Consistency，所有節(jié)點(diǎn)同一時間看到相同數(shù)據(jù)）、可用性（Availability，每次請求都能收到非錯誤響應(yīng)）、分區(qū)容錯性（Partitiontolerance，網(wǎng)絡(luò)分區(qū)時系統(tǒng)仍能運(yùn)行）。定理指出三者無法同時滿足，最多滿足兩個。權(quán)衡策略：①CP（一致性+分區(qū)容錯）：犧牲可用性，如ZooKeeper、HBase。網(wǎng)絡(luò)分區(qū)時，為保證一致性，可能拒絕部分請求（如Master節(jié)點(diǎn)不可達(dá)時，集群進(jìn)入不可寫狀態(tài)）。②AP（可用性+分區(qū)容錯）：犧牲強(qiáng)一致性，保證最終一致性，如Redis（異步復(fù)制）、Eureka（自我保護(hù)機(jī)制）。用戶可能讀到舊數(shù)據(jù)，但最終會同步。③CA（一致性+可用性）：放棄分區(qū)容錯，適用于單機(jī)或網(wǎng)絡(luò)可靠環(huán)境（如傳統(tǒng)單體應(yīng)用），但分布式系統(tǒng)中網(wǎng)絡(luò)分區(qū)不可避免，CA實際難以實現(xiàn)。實際設(shè)計需根據(jù)業(yè)務(wù)場景選擇，如金融交易強(qiáng)調(diào)一致性（CP），電商首頁推薦強(qiáng)調(diào)可用性（AP）。14.如何實現(xiàn)一個線程安全的單例模式？雙重檢查鎖定的原理？餓漢式（線程安全）：類加載時初始化實例，無線程問題，但可能浪費(fèi)資源（實例未使用時已創(chuàng)建）。```javapublicclassSingleton{privatestaticfinalSingletonINSTANCE=newSingleton();privateSingleton(){}publicstaticSingletongetInstance(){returnINSTANCE;}}```懶漢式（線程不安全）：延遲初始化，但多線程下可能創(chuàng)建多個實例。雙重檢查鎖定（DCL，線程安全且高效）：```javapublicclassSingleton{privatevolatilestaticSingletonINSTANCE;//volatile禁止指令重排privateSingleton(){}publicstaticSingletongetInstance(){if(INSTANCE==null){//第一次檢查，減少同步開銷synchronized(Singleton.class){if(INSTANCE==null){//第二次檢查，防止多線程同時通過第一次檢查INSTANCE=newSingleton();//可能因指令重排導(dǎo)致其他線程獲取到未初始化的實例，需volatile}}}retu