C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)面試常見問(wèn)題及答案單鏈表和雙向鏈表的核心差異是什么？單鏈表每個(gè)節(jié)點(diǎn)僅保存指向下一個(gè)節(jié)點(diǎn)的指針（next），只能單向遍歷；雙向鏈表每個(gè)節(jié)點(diǎn)額外保存指向前驅(qū)節(jié)點(diǎn)的指針（prev），支持雙向遍歷。雙向鏈表的插入和刪除操作在已知目標(biāo)節(jié)點(diǎn)時(shí)更高效（無(wú)需遍歷查找前驅(qū)），但空間占用更大（每個(gè)節(jié)點(diǎn)多一個(gè)指針）。例如，刪除單鏈表中間節(jié)點(diǎn)需要先找到前驅(qū)節(jié)點(diǎn)（O(n)時(shí)間），而雙向鏈表可直接通過(guò)prev指針操作（O(1)時(shí)間）。如何實(shí)現(xiàn)單鏈表的反轉(zhuǎn)？常見方法有迭代法和遞歸法。迭代法使用三個(gè)指針：prev（初始為NULL）、curr（初始為頭節(jié)點(diǎn)）、next（保存curr的下一個(gè)節(jié)點(diǎn)）。循環(huán)中每次將curr->next指向prev，然后prev、curr、next依次后移，直到curr為NULL，最終prev即為新頭節(jié)點(diǎn)。遞歸法需明確終止條件（當(dāng)前節(jié)點(diǎn)或下一個(gè)節(jié)點(diǎn)為空時(shí)返回當(dāng)前節(jié)點(diǎn)），遞歸調(diào)用反轉(zhuǎn)后續(xù)節(jié)點(diǎn)后，將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)next置NULL。例如，鏈表1->2->3->4，迭代法第一輪操作后變?yōu)镹ULL<-1，curr移至2，最終反轉(zhuǎn)結(jié)果為4->3->2->1。怎樣檢測(cè)鏈表中是否存在環(huán)？經(jīng)典方法是快慢指針（Floyd判圈算法）?？熘羔樏看我苿?dòng)2步，慢指針每次移動(dòng)1步。若鏈表無(wú)環(huán)，快指針會(huì)先到達(dá)NULL；若有環(huán)，快慢指針最終會(huì)在環(huán)內(nèi)相遇。數(shù)學(xué)上，設(shè)環(huán)入口前長(zhǎng)度為L(zhǎng)，環(huán)長(zhǎng)度為C，慢指針進(jìn)入環(huán)時(shí)快指針在環(huán)內(nèi)位置為d（d<C），則每移動(dòng)t步后，慢指針位置為tmodC，快指針位置為(d+2t)modC。當(dāng)t=C-d時(shí)，(d+2(C-d))modC=(2C-d)modC=(C-d)modC=t，此時(shí)相遇。若要找到環(huán)的入口，相遇后將慢指針移回頭節(jié)點(diǎn)，快慢指針均每次移動(dòng)1步，再次相遇點(diǎn)即為入口（證明：設(shè)相遇時(shí)慢指針走了L+x，快指針走了L+x+nC，且快指針路程是慢指針2倍，故L+x+nC=2(L+x)，得L=nC-x。當(dāng)慢指針從頭出發(fā)走L步，快指針從相遇點(diǎn)走L步（即nC-x步），此時(shí)快指針位置為x+(nC-x)=nC，即環(huán)入口）。用兩個(gè)棧模擬隊(duì)列的入隊(duì)和出隊(duì)操作，如何實(shí)現(xiàn)？定義棧A（入隊(duì)棧）和棧B（出隊(duì)棧）。入隊(duì)時(shí)直接將元素壓入棧A；出隊(duì)時(shí)若棧B非空，彈出棧頂元素；若棧B為空，將棧A所有元素依次彈出并壓入棧B，再?gòu)棾鰲ｍ斣?。需注意?dāng)棧A和棧B均為空時(shí)，出隊(duì)操作應(yīng)報(bào)錯(cuò)。例如，入隊(duì)順序1、2、3，棧A為[1,2,3]（棧頂為3），第一次出隊(duì)時(shí)將棧A元素彈出壓入棧B，棧B變?yōu)閇3,2,1]（棧頂為1），彈出1；第二次出隊(duì)直接彈出棧B的2，無(wú)需操作棧A。棧在括號(hào)匹配問(wèn)題中的具體應(yīng)用？遍歷字符串時(shí)，遇到左括號(hào)（如'('、'['、'{'）壓入棧；遇到右括號(hào)時(shí)，檢查棧是否為空（為空則不匹配），否則彈出棧頂元素，判斷是否與當(dāng)前右括號(hào)匹配（如棧頂是'('則匹配')'）。遍歷結(jié)束后若棧非空，說(shuō)明左括號(hào)多余。例如，字符串"([)]"的處理：'('入棧，'['入棧，遇到')'時(shí)棧頂是'['，不匹配，返回false。二叉樹前序、中序、后序遍歷的非遞歸實(shí)現(xiàn)差異？前序遍歷用棧保存待訪問(wèn)節(jié)點(diǎn)，先訪問(wèn)當(dāng)前節(jié)點(diǎn)，再將右子節(jié)點(diǎn)、左子節(jié)點(diǎn)壓棧（保證左子節(jié)點(diǎn)先出棧）。中序遍歷需先遍歷左子樹，將當(dāng)前節(jié)點(diǎn)壓棧后持續(xù)訪問(wèn)左子節(jié)點(diǎn)，直到左子節(jié)點(diǎn)為空時(shí)彈出棧頂節(jié)點(diǎn)訪問(wèn)，再轉(zhuǎn)向右子節(jié)點(diǎn)。后序遍歷有兩種方法：一是使用兩個(gè)棧，第一個(gè)棧按前序的逆序（根->右->左）壓棧，第二個(gè)棧接收彈出元素，最終順序?yàn)樽?>右->根；二是單棧記錄訪問(wèn)狀態(tài)（標(biāo)記是否已處理右子樹），第一次訪問(wèn)節(jié)點(diǎn)時(shí)標(biāo)記為未處理，壓棧后訪問(wèn)左子樹；再次彈出時(shí)若標(biāo)記為未處理，則標(biāo)記為已處理并重新壓棧，然后訪問(wèn)右子樹；若標(biāo)記為已處理則訪問(wèn)該節(jié)點(diǎn)。二叉搜索樹（BST）的性質(zhì)及插入刪除操作要點(diǎn)？BST中任意節(jié)點(diǎn)的左子樹所有節(jié)點(diǎn)值小于該節(jié)點(diǎn)值，右子樹所有節(jié)點(diǎn)值大于該節(jié)點(diǎn)值。插入時(shí)從根節(jié)點(diǎn)開始，若插入值小于當(dāng)前節(jié)點(diǎn)值則遞歸左子樹，否則遞歸右子樹，直到找到空位置插入。刪除分三種情況：節(jié)點(diǎn)無(wú)子女，直接刪除；節(jié)點(diǎn)只有一個(gè)子女，用子女替換該節(jié)點(diǎn)；節(jié)點(diǎn)有兩個(gè)子女，找到右子樹的最小節(jié)點(diǎn)（或左子樹的最大節(jié)點(diǎn)）替換該節(jié)點(diǎn)值，然后刪除該最小節(jié)點(diǎn)（此時(shí)最小節(jié)點(diǎn)最多只有一個(gè)右子女）。例如，刪除有兩個(gè)子女的節(jié)點(diǎn)5，找到右子樹最小節(jié)點(diǎn)6，將5的值改為6，然后刪除原6節(jié)點(diǎn)（可能是葉子節(jié)點(diǎn)或只有右子節(jié)點(diǎn)）。AVL樹和紅黑樹的核心區(qū)別？AVL樹是嚴(yán)格平衡樹（任意節(jié)點(diǎn)左右子樹高度差不超過(guò)1），插入/刪除時(shí)可能觸發(fā)多次旋轉(zhuǎn)（最多兩次）以恢復(fù)平衡；紅黑樹是弱平衡樹（通過(guò)顏色標(biāo)記和五條規(guī)則保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍），插入/刪除時(shí)通過(guò)顏色調(diào)整和最多兩次旋轉(zhuǎn)保持平衡。AVL樹查詢效率更高（樹高度更低），但插入/刪除操作更耗時(shí)；紅黑樹適合頻繁插入刪除的場(chǎng)景（如C++STL的map、set）。例如，插入操作在AVL樹中可能需要O(logn)次旋轉(zhuǎn)，而紅黑樹最多兩次旋轉(zhuǎn)。堆的結(jié)構(gòu)特性及堆排序的步驟？堆是完全二叉樹，分為大頂堆（父節(jié)點(diǎn)值≥子節(jié)點(diǎn)）和小頂堆（父節(jié)點(diǎn)值≤子節(jié)點(diǎn)）。堆排序步驟：1.建堆（從最后一個(gè)非葉子節(jié)點(diǎn)開始向前調(diào)整，每個(gè)節(jié)點(diǎn)與子節(jié)點(diǎn)比較，將最大的交換到父節(jié)點(diǎn)位置）；2.交換堆頂元素（最大值）與堆尾元素，堆大小減一；3.調(diào)整堆頂元素（重新堆化）；4.重復(fù)步驟2-3直到堆大小為1。建堆的時(shí)間復(fù)雜度是O(n)（非葉子節(jié)點(diǎn)數(shù)為n/2，每個(gè)節(jié)點(diǎn)調(diào)整次數(shù)與層數(shù)相關(guān)，總次數(shù)為n/21+n/42+...+1logn=n-logn-1）。堆排序整體時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1)，但不穩(wěn)定（如序列[3,2,3]，堆排序可能交換兩個(gè)3的順序）?？焖倥判虻姆謪^(qū)（partition）實(shí)現(xiàn)及優(yōu)化策略？經(jīng)典分區(qū)方法（Lomuto分區(qū)）選擇最后一個(gè)元素為樞軸（pivot），用指針i記錄小于pivot的元素邊界，遍歷數(shù)組時(shí)若當(dāng)前元素≤pivot，交換i和當(dāng)前位置元素，i遞增。遍歷結(jié)束后交換i和pivot位置，返回i作為分區(qū)點(diǎn)。優(yōu)化策略：1.隨機(jī)選擇樞軸（避免有序數(shù)組導(dǎo)致最壞O(n2)時(shí)間）；2.三數(shù)取中法（取首、中、尾的中位數(shù)作為樞軸）；3.小數(shù)組切換插入排序（當(dāng)子數(shù)組長(zhǎng)度≤10時(shí)改用插入排序，減少遞歸開銷）；4.尾遞歸優(yōu)化（對(duì)較短的子數(shù)組先遞歸，較長(zhǎng)的子數(shù)組用循環(huán)處理，減少棧深度）。例如，數(shù)組[3,1,4,2,5]選擇樞軸4，遍歷后i指向3（元素3的位置），交換i和樞軸位置，分區(qū)為[3,1,2,4,5]，分區(qū)點(diǎn)為3（索引3）。歸并排序的分治過(guò)程及空間復(fù)雜度優(yōu)化？歸并排序?qū)?shù)組遞歸分成兩半，直到子數(shù)組長(zhǎng)度為1，然后合并兩個(gè)有序子數(shù)組。合并時(shí)用臨時(shí)數(shù)組保存結(jié)果，比較兩個(gè)子數(shù)組的當(dāng)前元素，將較小的放入臨時(shí)數(shù)組，直到其中一個(gè)子數(shù)組遍歷完，將剩余元素復(fù)制到臨時(shí)數(shù)組，最后將臨時(shí)數(shù)組復(fù)制回原數(shù)組。空間復(fù)雜度為O(n)（需要臨時(shí)數(shù)組），但可通過(guò)原地合并優(yōu)化（如使用鏈表結(jié)構(gòu)或交換元素位置），但會(huì)增加時(shí)間復(fù)雜度。歸并排序是穩(wěn)定排序，時(shí)間復(fù)雜度始終為O(nlogn)，適合外排序（處理大文件）。如何判斷兩個(gè)二叉樹是否相同？需同時(shí)滿足：1.當(dāng)前節(jié)點(diǎn)值相同；2.左子樹相同；3.右子樹相同。遞歸實(shí)現(xiàn)：若兩樹均為空，返回true；若一者為空另一非空，返回false；否則比較當(dāng)前節(jié)點(diǎn)值，遞歸判斷左子樹和右子樹是否相同。迭代實(shí)現(xiàn)可使用隊(duì)列或棧，按層序遍歷同時(shí)比較對(duì)應(yīng)節(jié)點(diǎn)的值和子節(jié)點(diǎn)存在性。例如，樹A：1->2->3，樹B：1->2->3，返回true；若樹B的右子節(jié)點(diǎn)為4，返回false。圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的實(shí)現(xiàn)差異及應(yīng)用場(chǎng)景？DFS用棧（或遞歸）實(shí)現(xiàn)，優(yōu)先訪問(wèn)當(dāng)前節(jié)點(diǎn)的未訪問(wèn)鄰接節(jié)點(diǎn)，直到無(wú)法繼續(xù)再回溯。BFS用隊(duì)列實(shí)現(xiàn)，按層訪問(wèn)節(jié)點(diǎn)，先訪問(wèn)當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)，再依次處理這些節(jié)點(diǎn)的鄰接節(jié)點(diǎn)。DFS空間復(fù)雜度為O(h)（h為樹高），BFS為O(w)（w為最大寬度）。DFS適合尋找路徑存在性、拓?fù)渑判颍籅FS適合尋找最短路徑（無(wú)權(quán)圖）、層序遍歷。例如，在迷宮問(wèn)題中，BFS能保證找到的第一條路徑是最短的，而DFS可能先找到較長(zhǎng)路徑。KMP算法的核心思想及部分匹配表（next數(shù)組）的構(gòu)建？KMP算法通過(guò)預(yù)處理模式串，構(gòu)建next數(shù)組（記錄每個(gè)位置的最長(zhǎng)相等前綴后綴長(zhǎng)度），避免主串指針回溯。next數(shù)組構(gòu)建方法：初始化next[0]=-1，i=0，j=-1；當(dāng)i<模式串長(zhǎng)度-1時(shí)，若j==-1或模式串[i]==模式串[j]，則i++，j++，next[i]=j；否則j=next[j]。例如，模式串"ABABC"的next數(shù)組為[-1,0,0,1,2]。匹配時(shí)主串指針i和模式串指針j，若字符匹配則i++，j++；若不匹配且j≠-1，j=next[j]；若j等于模式串長(zhǎng)度，說(shuō)明匹配成功，記錄位置并重置j=next[j]。哈希表的沖突解決方法及各自優(yōu)缺點(diǎn)？開放定址法（線性探測(cè)：沖突時(shí)探測(cè)下一個(gè)位置；二次探測(cè)：探測(cè)i2位置；雙重哈希：用兩個(gè)哈希函數(shù)計(jì)算步長(zhǎng)），優(yōu)點(diǎn)是無(wú)需額外空間，缺點(diǎn)是可能產(chǎn)生聚集現(xiàn)象（線性探測(cè)尤其明顯）。鏈地址法（每個(gè)桶維護(hù)一個(gè)鏈表），優(yōu)點(diǎn)是沖突處理簡(jiǎn)單，平均查找時(shí)間短，缺點(diǎn)是需要額外指針空間，緩存不友好。公共溢出區(qū)法（沖突元素存入溢出區(qū)），適合沖突較少的場(chǎng)景。例如，Java的HashMap在JDK8前用鏈地址法，當(dāng)鏈表長(zhǎng)度≥8時(shí)轉(zhuǎn)為紅黑樹，避免鏈表過(guò)長(zhǎng)導(dǎo)致查找時(shí)間退化為O(n)。內(nèi)存泄漏的常見場(chǎng)景及檢測(cè)方法？場(chǎng)景包括：malloc后未調(diào)用free，重復(fù)malloc覆蓋指針導(dǎo)致原內(nèi)存無(wú)法釋放，動(dòng)態(tài)分配的數(shù)組未正確釋放，類中未重寫析構(gòu)函數(shù)導(dǎo)致成員指針未釋放。檢測(cè)方法：1.工具法（如Valgrind的memcheck，VisualStudio的CRT調(diào)試庫(kù)）；2.重載malloc/free，記錄分配和釋放的地址及調(diào)用棧；3.手動(dòng)檢查（代碼審查，確保每個(gè)malloc對(duì)應(yīng)一個(gè)free，循環(huán)中動(dòng)態(tài)分配的內(nèi)存及時(shí)釋放）。例如，在循環(huán)中編寫"charp=(char)malloc(10);"但未在循環(huán)內(nèi)free，會(huì)導(dǎo)致每次循環(huán)泄漏10字節(jié)。結(jié)構(gòu)體和聯(lián)合體的區(qū)別？結(jié)構(gòu)體（struct）中各成員占用獨(dú)立內(nèi)存空間，總大小是各成員大小之和（考慮內(nèi)存對(duì)齊）；聯(lián)合體（union）中所有成員共享同一塊內(nèi)存空間，總大小是最大成員的大小（需滿足所有成員的對(duì)齊要求）。結(jié)構(gòu)體用于存儲(chǔ)不同類型的相關(guān)數(shù)據(jù)（如學(xué)生信息包含姓名、年齡、成績(jī)）；聯(lián)合體用于同一數(shù)據(jù)的不同表示（如IP地址可表示為4字節(jié)數(shù)組或32位整數(shù)）。例如，structS{inta;charb;}占8字節(jié)（int占4，char占1，對(duì)齊補(bǔ)3）；unionU{inta;charb;}占4字節(jié)（int和char共享前4字節(jié)）。指針和數(shù)組的關(guān)系及常見誤區(qū)？數(shù)組名是指向首元素的常量指針（如intarr[5];arr等價(jià)于&arr[0]），但數(shù)組名不能自增（arr++非法）。指針可以指向數(shù)組的任意位置（intp=arr+2;指向arr[2]）。誤區(qū)包括：認(rèn)為數(shù)組名是指針變量（實(shí)際是常量），混淆sizeof(arr)（數(shù)組總大?。┖蛃izeof(p)（指針大小，通常4或8字節(jié)），越界訪問(wèn)數(shù)組（如arr[5]訪問(wèn)未分配內(nèi)存）。例如，函數(shù)參數(shù)中的數(shù)組會(huì)退化為指針（voidfunc(intarr[])等價(jià)于voidfunc(intarr)），因此無(wú)法在函數(shù)內(nèi)部用sizeof(arr)獲取數(shù)組長(zhǎng)度。預(yù)處理指令define和const的區(qū)別？define是編譯前的宏替換，無(wú)類型檢查；const是編譯期的常量，有類型信息。define在替換時(shí)可能產(chǎn)生副作用（如defineSQUARE(x)xx，SQUARE(a+1)會(huì)展開為a+1a+1）；const變量不會(huì)。define無(wú)法調(diào)試（預(yù)處理階段已替換），const變量可以調(diào)試。const變量存儲(chǔ)在數(shù)據(jù)段（全局）或棧（局部），define替換后的常量可能存儲(chǔ)在代碼段（如字面量）。例如，definePI3.14和constdoublePI=3.14，前者在代碼中所有PI被替換為3.14，后者是一個(gè)只讀變量。動(dòng)態(tài)數(shù)組（如用realloc實(shí)現(xiàn)）和鏈表的選擇依據(jù)？動(dòng)態(tài)數(shù)組（如intarr=(int)malloc(nsizeof(int))，用realloc調(diào)整大?。┲С諳(1)隨機(jī)訪問(wèn)，插入/刪除元素（尤其中間位置）需移動(dòng)元素（O(n)時(shí)間），內(nèi)存連續(xù)（緩存友好）。鏈表（單/雙向）插入/刪除元素（已知位置）為O(1)時(shí)間（雙向鏈表），但隨機(jī)訪問(wèn)需O(n)時(shí)間，內(nèi)存不連續(xù)（緩存不友好）。選擇依據(jù)：需頻繁隨機(jī)訪問(wèn)選動(dòng)態(tài)數(shù)組；需頻繁插入刪除選鏈表；數(shù)據(jù)量未知且可能頻繁擴(kuò)展選鏈表（動(dòng)態(tài)數(shù)組的realloc可能導(dǎo)致數(shù)據(jù)遷移）。例如，實(shí)現(xiàn)棧選動(dòng)態(tài)數(shù)組（頂部操作O(1)），實(shí)現(xiàn)隊(duì)列選鏈表（頭部刪除O(1)）或循環(huán)數(shù)組。如何實(shí)現(xiàn)一個(gè)線程安全的棧？需使用互斥鎖（mutex）保護(hù)入棧、出棧操作。入棧時(shí)加鎖，壓入元素后解鎖；出棧時(shí)加鎖，檢查棧是否為空，彈出元素后解鎖。若需更高并發(fā)，可使用無(wú)鎖數(shù)據(jù)結(jié)構(gòu)（如CAS（Compare-And-Swap）操作），但實(shí)現(xiàn)復(fù)雜。例如，用pthread_mutex_t定義鎖，入棧函數(shù)中調(diào)用pthread_mutex_lock，執(zhí)行push操作，然后pthread_mutex_unlock。需注意鎖的粒度（避免長(zhǎng)時(shí)間持有鎖影響性能）和死鎖問(wèn)題（如按固定順序加鎖）。哈夫曼樹的構(gòu)造步驟及應(yīng)用？構(gòu)造步驟：1.將所有節(jié)點(diǎn)作為獨(dú)立樹（權(quán)值為節(jié)點(diǎn)值）；2.選擇兩棵權(quán)值最小的樹，合并為新樹（新樹根權(quán)值為兩樹權(quán)值之和）；3.重復(fù)步驟2直到只剩一棵樹。應(yīng)用包括哈夫曼編碼（前綴編碼，最小帶權(quán)路徑長(zhǎng)度，用于數(shù)據(jù)壓縮）。例如，字符頻率A(5),B(9),C(12),D(13),E(16),F(45)，構(gòu)造哈夫曼樹時(shí)先合并A(5)和B(9)得14，再合并C(12)和14得26，接著合并D(13)和26得39，然后合并E(16)和39得55，最后合并55和F(45)得100。各字符編碼為A(1110),B(1111),C(110),D(100),E(101),F(0)，總編碼長(zhǎng)度最小。拓?fù)渑判虻膶?shí)現(xiàn)方法及應(yīng)用場(chǎng)景？拓?fù)渑判蛴糜谟邢驘o(wú)環(huán)圖（DAG），輸出一個(gè)線性序列，使得所有邊u->v中u出現(xiàn)在v之前。實(shí)現(xiàn)方法：1.計(jì)算每個(gè)節(jié)點(diǎn)的入度；2.將入度為0的節(jié)點(diǎn)加入隊(duì)列；3.取出隊(duì)列節(jié)點(diǎn)u，加入結(jié)果序列，遍歷u的所有鄰接節(jié)點(diǎn)v，將v的入度減1，若減為0則加入隊(duì)列；4.重復(fù)直到隊(duì)列為空。若結(jié)果序列長(zhǎng)度小于節(jié)點(diǎn)數(shù)，說(shuō)明圖中有環(huán)。應(yīng)用場(chǎng)景包括任務(wù)調(diào)度（任務(wù)間有依賴關(guān)系）、課程安排（先修課程）。例如，課程依賴C1->C2,C1->C3,C2->C4,C3->C4，拓?fù)渑判蚩赡転镃1,C2,C3,C4或C1,C3,C2,C4。最短路徑算法Dijkstra和Floyd的區(qū)別？Dijkstra算法用于單源最短路徑（非負(fù)權(quán)邊），用優(yōu)先隊(duì)列（堆）優(yōu)化，時(shí)間復(fù)雜度O((V+E)logV)。Floyd算法用于所有點(diǎn)對(duì)最短路徑（允許負(fù)權(quán)邊，不允許負(fù)權(quán)環(huán)），時(shí)間復(fù)雜度O(V3)。Dijkstra基于貪心策略，每次選擇當(dāng)前最短距離的節(jié)點(diǎn)；Floyd基于動(dòng)態(tài)規(guī)劃，維護(hù)距離矩陣d[i][j]，逐步考慮中間節(jié)點(diǎn)k，更新d[i][j]=min(d[i][j],d[i][k]+d[k][j])。例如，圖中節(jié)點(diǎn)A到B權(quán)3，A到C權(quán)5，B到C權(quán)1，Dijkstra計(jì)算A到C的最短路徑為A->B->C（總權(quán)4）；Floyd會(huì)計(jì)算所有節(jié)點(diǎn)對(duì)的最短路徑，如B到A無(wú)路徑則距離為∞。內(nèi)存對(duì)齊的原因及規(guī)則？原因：1.硬件限制（某些CPU只能訪問(wèn)對(duì)齊的內(nèi)存地址，否則拋出異常）；2.提高訪問(wèn)效率（對(duì)齊的內(nèi)存訪問(wèn)只需一次總線操作，未對(duì)齊可能需要多次）。規(guī)則：1.每個(gè)成員的起始地址必須是其大小的整數(shù)倍（如int占4字節(jié)，起始地址%4=0）；2.結(jié)構(gòu)體總大小必須是所有成員最大對(duì)齊數(shù)的整數(shù)倍（如成員有char（1）、int（4），總大小為8（4的倍數(shù)））；3.嵌套結(jié)構(gòu)體的對(duì)齊數(shù)為其內(nèi)部成員的最大對(duì)齊數(shù)。例如，struct{chara;intb;}的大小為8（char占1，補(bǔ)3字節(jié)，int占4，總8）。如何實(shí)現(xiàn)一個(gè)高效的LRU緩存？LRU（最近最少使用）緩存需支持O(1)時(shí)間的插入、刪除、查找操作。常用雙向鏈表（維護(hù)訪問(wèn)順序，最近訪問(wèn)的節(jié)點(diǎn)放在頭部）和哈希表（鍵到鏈表節(jié)點(diǎn)的映射）結(jié)合。插入時(shí)若緩存已滿，刪除鏈表尾部節(jié)點(diǎn)（最久未使用）并從哈希表中刪除；查找時(shí)若存在，將對(duì)應(yīng)節(jié)點(diǎn)移到鏈表頭部（更新訪問(wèn)順序）。例如，緩存容量3，訪問(wèn)順序1、2、3、4，此時(shí)緩存為4、3、2（假設(shè)每次新訪問(wèn)放頭部），再訪問(wèn)3，緩存變?yōu)?、4、2。C++中可用std::list和std::unordered_map實(shí)現(xiàn)，Java中可用LinkedHashMap。堆和棧的內(nèi)存管理區(qū)別？堆（動(dòng)態(tài)內(nèi)存）由程序員手動(dòng)分配（malloc）和釋放（free），空間較大（受限于虛擬內(nèi)存），分配效率較低（需維護(hù)空閑塊鏈表）。棧（自動(dòng)內(nèi)存）由編譯器自動(dòng)管理（函數(shù)調(diào)用時(shí)壓棧，返回時(shí)彈棧），空間較?。ㄍǔ譓B），分配效率高（僅需移動(dòng)棧指針）。堆內(nèi)存的生命周期由程序員控制（可能泄漏），棧內(nèi)存生命周期與函數(shù)作用域綁定。例如，局部變量存儲(chǔ)在棧中（inta=5;），動(dòng)態(tài)分配的內(nèi)存存儲(chǔ)在堆中（intp=(int)malloc(4);）。如何判斷一個(gè)數(shù)是否是2的冪？2的冪的二進(jìn)制表示中只有一個(gè)1（如8=1000）。n&(n-1)可消除最低位的1，若結(jié)果為0則是2的冪（需排除n=0的情況）。例如，n=8，n-1=7（0111），8&7=0；n=6（0110），n-1=5（0101），6&5=4≠0。特殊情況n=0時(shí)，0&-1=0，但0不是2的冪，故條件應(yīng)為n>0且(n&(n-1))==0。字符串反轉(zhuǎn)的原地實(shí)現(xiàn)方法？使用雙指針，左指針指向頭部，右指針指向尾部，交換兩指針字符后左指針右移，右指針左移，直到左指針≥右指針。例如，字符串"hello"反轉(zhuǎn)，交換h和o（變?yōu)閛ellh），交換e和l（變?yōu)閛lleh）。需注意空字符串或單字符的情況（無(wú)需操作）。如何合并兩個(gè)有序鏈表？遞歸法：若l1->val<l2->val，l1->next=merge(l1->next,l2)，返回l1；否則l2->next=merge(l1,l2->next)，返回l2。終止條件是l1或l2為空時(shí)返回另一個(gè)鏈表。迭代法：創(chuàng)建啞節(jié)點(diǎn)dummy，用指針curr跟蹤當(dāng)前節(jié)點(diǎn)，比較l1和l2的當(dāng)前值，將較小的連接到curr->next，然后移動(dòng)對(duì)應(yīng)鏈表指針，直到其中一個(gè)鏈表為空，將剩余鏈表連接到curr->next。例如，鏈表1->3->5和2->4->6，合并后為1->2->3->4->5->6。判斷一個(gè)鏈表是否為回文結(jié)構(gòu)？方法一：將鏈表值存入數(shù)組，用雙指針判斷數(shù)組是否回文（時(shí)間O(n)，空間O(n)）。方法二：找到鏈表中點(diǎn)（快慢指針，快指針到末尾時(shí)慢指針到中點(diǎn)），反轉(zhuǎn)后半部分鏈表，比較前半部分和后半部分是否相同，最后恢復(fù)鏈表。例如，鏈表1->2->2->1，中點(diǎn)為第二個(gè)2，反轉(zhuǎn)后半部分為1->2，比較前半部分1->2和后半部分1->2，相同則為回文。計(jì)算兩個(gè)有序數(shù)組的中位數(shù)？若合并后數(shù)組長(zhǎng)度為奇數(shù)，中位數(shù)是中間元素；偶數(shù)則是中間兩數(shù)的平均。高效方法（O(log(m+n))）：使用二分查找，每次排除不可能包含中位數(shù)的半?yún)^(qū)。假設(shè)數(shù)組A和B，長(zhǎng)度m≤n，尋找i（A的前i個(gè)元素）和j（B的前j個(gè)元素，j=(m+n+1)/2-i），使得A[i-1]≤B[j]且B[j-1]≤A[i]。例如，A=[1,3],B=[2],m=2,n=1，i=1,j=1（(2+1+1)/2-1=1），A[i-1]=1≤B[j]=2，B[j-1]=2≤A[i]=3，中位數(shù)為max(1,2)=2（總長(zhǎng)度3，奇數(shù)）。實(shí)現(xiàn)memcpy函數(shù)需注意什么？memcpy用于內(nèi)存塊復(fù)制，原型為voidmemcpy(voiddest,constvoidsrc,size_tn)。需處理源和目標(biāo)內(nèi)存重疊的情況（此時(shí)應(yīng)使用memmove）。復(fù)制時(shí)按字節(jié)操作，需強(qiáng)制轉(zhuǎn)換為char指針。例如，當(dāng)dest在src和src+n之間時(shí)，直接復(fù)制會(huì)覆蓋未復(fù)制的源數(shù)據(jù)，應(yīng)從后往前復(fù)制。正確實(shí)現(xiàn)：if(dest<=src||(char)dest>=(char)src+n)從前往后復(fù)制；否則從后往前復(fù)制。如何查找數(shù)組中重復(fù)的數(shù)字？方法一：哈希表記錄出現(xiàn)次數(shù)，遍歷數(shù)組找到第一個(gè)次數(shù)>1的數(shù)（時(shí)間O(n)，空間O(n)）。方法二：原地交換（數(shù)組長(zhǎng)度n，元素在0~n-1之間），遍歷數(shù)組，若nums[i]≠i，將nums[i]與nums[nums[i]]交換，若nums[i]==nums[nums[i]]則找到重復(fù)數(shù)。例如，數(shù)組[2,3,1,0,2,5]，i