簡介這是《數(shù)據(jù)結構與算法分析Java語言描述》第三版配套的習題答案文檔面向正在學習數(shù)據(jù)結構與算法的計算機專業(yè)學生、考研備考者以及需要鞏固Java算法基礎的開發(fā)者。內容覆蓋教材第一章的核心練習包含英文原版習題的完整解答過程資源包內含1個docx文檔大小約1.52MB方便閱讀、批注與打印。已有2429人學習下載。文檔詳細解答了文件處理、遞歸算法、數(shù)學歸納法證明、數(shù)列求和、模運算及大O符號估計等經(jīng)典題目例如processFile方法的遞歸實現(xiàn)、ones(int n)的二進制位數(shù)求和以及對對數(shù)性質的歸納證明通過逐題研讀可深入理解算法分析中的數(shù)學推導方法與復雜度估計思路。1. 數(shù)據(jù)結構與算法分析Java語言描述第三版習題答案一份能直接照跑的解題參考數(shù)據(jù)結構與算法分析Java語言描述第三版是很多軟件專業(yè)學生的噩夢來源——教材好買課后題答案卻只能靠同學口口相傳網(wǎng)上流傳的版本還經(jīng)常缺章少頁。這份docx把前三章的習題解答完整整理了出來從遞歸函數(shù)、數(shù)學歸納法證明到復雜度排序、鏈表節(jié)點交換覆蓋的正是最容易被卡住的章節(jié)。它不是給每道題貼一句結論而是給出能直接編譯運行的Java代碼和完整推導過程適合正在啃課本的在校生、準備Java面試的開發(fā)者以及想自己動手驗證算法結論的自學者。如果你也被一道歸納題卡了兩小時這份答案能省下大把翻論壇的時間。2. 第一章答案拆解遞歸寫法、數(shù)學歸納法與數(shù)列求和實用技巧2.1 遞歸兩件套processFile與ones(int n)習題1.4講的是帶#include指令的文件遞歸處理。它的解法是一段典型的遞歸下降邏輯processFile( fileName ): 打開 fileName 逐行讀取 如果當前行是 #include SomeFile: 遞歸調用 processFile( SomeFile ) 處理當前文件內容 關閉文件這段描述說明了文件I/O里最常見的遞歸場景嵌套包含的頭文件無法用單層循環(huán)解決因為包含深度不確定而遞歸天然匹配這個“未知深度”的樹形結構。更關鍵的是題目里提到的自引用檢測——維護一個“尚未結束處理”的文件列表進入遞歸前先查這個列表重復出現(xiàn)就說明存在循環(huán)包含得立刻終止。實際做代碼靜態(tài)掃描時這個列表通常用HashSet存文件絕對路徑遇到重復路徑直接跳過否則會無限遞歸棧溢出。習題1.5是另一個更純粹的遞歸例子計算一個整數(shù)二進制表示中1的個數(shù)public static int ones(int n) { if (n 2) { return n; } return n % 2 ones(n / 2); }邏輯說明n % 2取出最低位n / 2把整數(shù)右移一位遞歸累加每一位的值。以ones(13)為例13的二進制是110113%21遞歸66%20遞歸33%21遞歸112直接返回1合計10113。這個遞歸深度等于二進制位數(shù)所以時間復雜度是O(log n)。參數(shù)說明n按非負整數(shù)設計。如果你把負數(shù)傳進來Java的/2向零取整-1%2結果是-1而不是1返回值會違背“二進制中1的個數(shù)”的定義同樣的邏輯用Python跑取余結果又不一樣。這就是跨語言移植的第一個坑——遞歸的數(shù)學語義在Java里要謹慎對待負數(shù)邊界。2.2 數(shù)學歸納法從log X X到斐波那契上界習題1.7(a)要證明log X X對X0恒成立。答案用的歸納結構值得反復看先驗證0X≤1區(qū)間此時log X≤0顯然小于X再驗證1X≤2log X≤1≤X然后假設pX≤2p區(qū)間成立推導2pY≤4p區(qū)間log Y 1 log(Y/2)而Y/2落在(p, 2p]內由歸納假設log(Y/2) Y/2所以log Y 1 Y/2 ≤ Y/2 Y/2 Y。這個“區(qū)間倍增、區(qū)間覆蓋”的思路比直接對X放縮更嚴謹因為log X在接近0處是負無窮直接證明很麻煩。習題1.11(b)的斐波那契上界F_k φ^kφ為黃金比例也用了歸納法但技巧性更強。關鍵觀察是φ滿足φ 1 φ2變形得φ?1 φ?2 1。歸納步驟F_{k1} F_k F_{k-1} φ^k φ^(k-1) φ^(k1)(φ?1 φ?2) φ^(k1)第三節(jié)習題1.10的模運算題還展示了快速冪的數(shù)學基礎2?16≡1 (mod 5)所以21??(2?)2?≡12?≡1 (mod 5)。這種“先找循環(huán)節(jié)再取模”的手法在后面學快速冪算法時會反復遇到。2.3 錯位相減從4/3到20/27的數(shù)列求和推導習題1.8是這份答案里最容易讓人看得一頭霧水的地方因為docx排版把公式拆散了。理順之后其實是標準的錯位相減鏈。先看基礎公式Σ_{i0}^∞ 1/4^i 4/3基于這個結果求S Σ_{i1}^∞ i/4^i。列兩個等式S 1/4 2/16 3/64 … 4S 1 2/4 3/16 4/64 …用4S - S錯位相減左邊得3S右邊除了首項1之外剩下的就是Σ_{i1}^∞ 1/4^i 1/3。所以3S 1 1/3 4/3S 4/9。繼續(xù)求Σ_{i1}^∞ i2/4^i同樣設它為S做4S - S后得到3S 1 3/4 5/16 7/64 …把右邊拆成1 Σ(2i1)/4^i再利用Σi/4^i 4/9和Σ1/4^i 1/3算出3S 1 8/9 1/3 20/9S 20/27。習題1.12的平方和、立方和公式同樣可以用歸納法或直接代數(shù)推導完成答案里給出的是歸納版本平方和Σ(2i-1)N2立方和Σi3(N(N1)/2)2。這里有個經(jīng)驗遇到這種被排版打亂的公式先按題目編號回到教材原題確認求和符號的上下標再按“列等式、錯位相減、拆項”三步走基本都能復原。文檔里的推導對錯判斷標準很簡單——最終結果代回去能不能自洽。3. 第二章算法分析答案詳解復雜度排序、運行時間推算與循環(huán)陷阱3.1 復雜度函數(shù)排序記住這張表習題2.1給出一串函數(shù)要求按增長率從小到大排列。答案的排序是序號函數(shù)說明12/N, 37常數(shù)級2/N隨N增大趨近于02√N低于任何多項式N^kk0.5時3N線性4N log log N比線性略高5N log N, N log(N2)同階log(N2)2logN常數(shù)可忽略6N log2N比N log N高一個log因子7N^1.5介于N log2N和N2之間8N2, N2 logN平方級9N3立方級102^(N/2), 2^N指數(shù)級判斷這類排序題核心規(guī)則只有三條多項式之間比最高次冪對數(shù)函數(shù)比任何正次冪增長慢指數(shù)函數(shù)比任何多項式增長快。最容易錯的是N log N和N log(N2)很多人以為后者更快其實差一個常數(shù)2漸近上完全同階。排序結果怎么驗證直接取N10?代進去算近似值或者畫一張雙對數(shù)坐標圖立刻能看出哪幾個函數(shù)擠在一起。面試里問“N log N和N log(N2)誰增長快”是經(jīng)典陷阱答案是“一樣快”。3.2 運行時間推算從0.5ms到62.5ms的直覺建立習題2.11假設某算法處理當前輸入耗時0.5ms輸入規(guī)模擴大5倍問各復雜度下的新耗時復雜度計算新耗時O(N)0.5 × 52.5 msO(N log N)0.5 × 5 × (log5N / logN)略大于2.5 msO(N2)0.5 × 2512.5 msO(N3)0.5 × 12562.5 ms這里的O(N log N)項沒法給精確倍數(shù)因為log5N/logN和N有關。N越小這個比值越大N趨近無窮時它趨近1。實際工作中我一般估算成“比線性倍率大一點點”如果面試官追問就給出這個公式。習題2.12反過來問時間限制擴大12000倍輸入規(guī)模能擴大多少答案分別是線性擴大12000倍平方級擴大√12000≈109.54倍立方級擴大12000^(1/3)≈22.9倍N log N級別答案是“約425000”——但要注意這不是固定倍率它依賴基線N。假設基線N100N log N約664時間擴大12000倍后要解M log M ≈ 664×12000M才約等于425000。理解這點比背數(shù)字重要因為真實系統(tǒng)的性能估算永遠依賴當前基線的位置。3.3 六段代碼復雜度循環(huán)層數(shù)相乘為什么翻車習題2.7給了六段循環(huán)嵌套代碼答案是嚴肅的算法分析訓練?？焖僬f結論代碼段外層中層內層實際復雜度IN無無O(N)IINN無O(N2)IIINNNO(N3)IVN/2N無O(N2)VNi2jO(N?)VINNNO(N?)最值得展開的是VI。它的三層循環(huán)每一層都到N但內層有一句if條件只有條件成立才進入最內層的O(N)操作。答案說這個條件總共只成立O(N2)次所以總時間是O(N2)×O(N)O(N?)而不是O(N?)。這就是“循環(huán)層數(shù)相乘”的局限——它只在所有分支等概率進入時成立。遇到帶條件的內層循環(huán)必須統(tǒng)計條件成立次數(shù)而不是直接數(shù)循環(huán)層數(shù)。這道題在面試里也常變體出現(xiàn)一個看起來O(N3)的三重循環(huán)因為一個if (ij k)硬生生變成O(N2)考察的就是你會不會用條件頻率代替循環(huán)深度。3.4 隨機排列與有序矩陣搜索從洗牌到線性掃描習題2.8討論三種生成隨機排列的算法。第一種逐位隨機生成重復就重試期望復雜度O(N2 log N)第二種用集合維護已選元素降到O(N log N)第三種是Fisher-Yates洗牌的變體線性完成。答案特別指出如果洗牌算法里把swap(a[i], a[randint(i, n-1)])改成randint(0, n-1)均勻性會立刻被破壞。證明方式很巧妙——N3時randint(0,2)共有27種等概率交換序列而6個排列無法被27整除所以排列不可能是等概率的。習題2.27是有序矩陣搜索矩陣每行每列都遞增從右上角開始當前值大于目標就左移小于目標就下移最多NM次比較。這是一道高頻面試題比二分查找更考察“利用有序性”的思維。習題2.28的最大差值問題則是一維掃描的經(jīng)典——維護掃描到當前位置前的最小值用當前值減最小值更新答案一趟O(N)收工。這兩道題在答案里都給了完整推演建議直接背下來當模板。4. 第三章鏈表答案實戰(zhàn)printLots、節(jié)點交換、交集并集與Josephus問題4.1 printLots(L, P)同步推進兩個迭代器習題3.1要求打印鏈表L中由位置列表P指定的所有元素且P中的位置是遞增的。答案用兩個迭代器同步推進避免了每次從頭遍歷鏈表import java.util.Iterator; import java.util.List; public static AnyType void printLots(ListAnyType L, ListInteger P) { IteratorAnyType iterL L.iterator(); IteratorInteger iterP P.iterator(); AnyType itemL null; Integer itemP 0; int start 0; while (iterL.hasNext() iterP.hasNext()) { itemP iterP.next(); System.out.println(Looking for position itemP); while (start itemP iterL.hasNext()) { start; itemL iterL.next(); } System.out.println(itemL); } }邏輯說明iterP每次取一個位置itemPiterL在內層循環(huán)里推進itemP - start步把start更新到當前位置。兩個迭代器都只往一個方向走總體代價是O(|L| |P|)而不是O(|L|×|P|)。要注意P必須遞增如果P是無序列表這個算法直接失效得改用哈希表緩存下標。邊界條件需要注意當itemP超過鏈表長度時內層循環(huán)會因iterL.hasNext()為false而退出此時itemL是鏈表的最后一個節(jié)點會被重復打印。嚴格的做法是在內層循環(huán)結束后判斷start itemP是否成立不成立就說明位置越界。答案省略了這個保護實際復用時要自己加。4.2 swapWithNext單鏈表與雙鏈表的指針重連習題3.2要求交換相鄰兩個節(jié)點。單鏈表的做法是操作待交換節(jié)點的前驅beforeppublic static void swapWithNext(Node beforep) { Node p beforep.next; Node afterp p.next; // p和afterp假定都不為null p.next afterp.next; beforep.next afterp; afterp.next p; }雙鏈表版本則需要同時維護prev和next答案的寫法是public static void swapWithNext(Node p) { Node beforep p.prev; Node afterp p.next; p.next afterp.next; beforep.next afterp; afterp.next p; p.next.prev p; p.prev afterp; afterp.prev beforep; }邏輯說明雙鏈表交換的頭疼之處在于四個方向都要斷鏈。p.next afterp.next先把p的后繼接到afterp后面p.next.prev p把p的新后繼的prev指回pafterp.prev beforep讓afterp的prev指向beforep之后beforep.next afterp和afterp.next p完成剩余兩處連接。順序可以微調但最后一步一定是補p.prev afterp否則p的prev還指著afterp下次遍歷會死循環(huán)。兩個版本都沒做空指針檢查。如果在鏈表的tail上調用雙鏈表版本afterp.next是nullp.next.prev p會空指針。真正放進生產(chǎn)代碼前必須加判空或者約定“禁止對尾節(jié)點調用此方法”。4.3 intersection與union有序表合并的統(tǒng)一模板習題3.4和3.5是配套題分別求兩個有序鏈表的交集和并集。交集的答案核心是二路歸并public static AnyType extends Comparable? super AnyType void intersection(ListAnyType L1, ListAnyType L2, ListAnyType Intersect) { ListIteratorAnyType iterL1 L1.listIterator(); ListIteratorAnyType iterL2 L2.listIterator(); AnyType itemL1 null, itemL2 null; if (iterL1.hasNext() iterL2.hasNext()) { itemL1 iterL1.next(); itemL2 iterL2.next(); } while (itemL1 ! null itemL2 ! null) { int compareResult itemL1.compareTo(itemL2); if (compareResult 0) { Intersect.add(itemL1); itemL1 iterL1.hasNext() ? iterL1.next() : null; itemL2 iterL2.hasNext() ? iterL2.next() : null; } else if (compareResult 0) { itemL1 iterL1.hasNext() ? iterL1.next() : null; } else { itemL2 iterL2.hasNext() ? iterL2.next() : null; } } }邏輯說明compareTo返回負值說明L1的元素小鏈表L1推進正值說明L2的小鏈表L2推進相等則收入結果集、兩邊同時推進。整個過程和歸并排序的merge階段一模一樣。并集版本只在分支處理上不同相等時加一個并推進兩邊不等時加較小的那個再推進對應鏈表。這里有個容易被忽略的細節(jié)extends Comparable? super AnyType這個泛型約束不是裝飾它允許AnyType自身實現(xiàn)Comparable也允許它的父類實現(xiàn)Comparable。實際工程里如果你定義了一個子類繼承字符串包裝類這個約束能在編譯期就兜住類型不匹配。題目答案里反復出現(xiàn)這個簽名值得在IDE里敲一遍體會它的作用。4.4 Josephus問題從M mod N到反向搜索習題3.6的Josephus問題是鏈表章節(jié)的壓軸題N個人圍成一圈每數(shù)到M就刪除問最后留下誰。最樸素的做法是每次都從頭遍歷M步總復雜度O(N·M)。答案給出兩個實用改進。第一個改進是M mod N當M大于當前剩余人數(shù)時繞圈多走的完整圈數(shù)沒有意義取模可以避免大量無效遍歷。第二個改進是反向搜索當M超過剩余人數(shù)的一半時從當前位置往前找N - M步等價于往后找M步。這兩個改進疊加后最壞時間復雜度是O(N·min(M, N))但多數(shù)情況下遠快于這個上界。實際寫的時候還要補一層邊界處理M1時直接刪頭節(jié)點即可O(1)N1時連刪除都不用做。典型的翻車現(xiàn)場是把M mod N寫錯成M % size但size在刪除過程中不斷變化取模時機不同結果就不同。正確做法是每次刪除前用最新size取模而不是只在開始時取一次。5. 避坑指南習題答案在學習與復現(xiàn)時最容易翻車的四個細節(jié)5.1 公式亂碼與排版拆解現(xiàn)象docx里出現(xiàn)“4S ? 1 ? 2 ? 3 ?.442”這種斷行亂碼連求和符號都被拆成碎片。原因原文檔排版時混用了公式編輯器域代碼和普通文本不同軟件渲染時對上下標、分數(shù)線的支持不一致尤其用在線預覽或文本編輯器打開時幾乎必亂。解決用Office或WPS打開不要用記事本類的工具。遇到亂碼公式根據(jù)題號回到教材原題對照按“列出等式、錯位相減、代入已知結果”三步自己重推一遍比盯著亂碼猜要快得多。5.2 泛型代碼缺import導致編譯失敗現(xiàn)象直接復制3.1節(jié)的printLots代碼javac報“找不到List”或“找不到Iterator”。原因答案文檔省略了import java.util.*。這在競賽代碼里常見但直接照抄到IDE里必然編譯失敗。解決開頭補全三行import java.util.List;、import java.util.Iterator;、import java.util.ListIterator;。如果你在Eclipse或IDEA里多數(shù)情況下快捷鍵自動補全但建議理解每個import對應哪個接口面試時被問到能說清楚。5.3 printLots越界與非法位置輸入現(xiàn)象L有5個元素P里傳了位置100程序不報錯打印出鏈表的最后一個元素。原因內層while (start itemP iterL.hasNext())在鏈表耗盡時靜默退出itemL停在最后一個節(jié)點上。題目默認P中位置合法但實際傳參沒有這種保證。解決在內層循環(huán)結束后檢查start itemP不相等直接拋IllegalArgumentException或者在調用前用L.size()和P的每個元素做一次合法性校驗。5.4 循環(huán)復雜度直接相乘導致誤判現(xiàn)象看到三層嵌套循環(huán)就寫O(N3)看到更深的嵌套直接寫O(N?)結果2.7(VI)的正確答案是O(N?)。原因循環(huán)層數(shù)相乘只在無條件進入內層時成立遇到if分支就必須統(tǒng)計成立次數(shù)。很多人栽在“內層O(N2)操作對外層每次循環(huán)都執(zhí)行”的錯誤假設上。解決逐層分析。先確認最內層語句是否每次都被執(zhí)行統(tǒng)計條件成立的總次數(shù)再乘以單次執(zhí)行代價。養(yǎng)成“先算執(zhí)行次數(shù)再算單次代價”的習慣復雜度分析就不容易翻車。6. 把習題答案變成面試素材驗證、改寫與追問拿到這份答案最高效的用法不是“看”而是“跑”。我習慣把每段Java代碼復制到IDE里寫一個main方法做單元驗證。比如ones(int n)用標準庫的Integer.bitCount(n)做基準循環(huán)0到1000逐個斷言public static void main(String[] args) { for (int i 0; i 1000; i) { int expected Integer.bitCount(i); int actual ones(i); if (expected ! actual) { System.out.println(Mismatch at i); } } }這一步能把“我以為我懂了”變成“我確認它是對的”。跑通之后再想兩個追問ones的遞歸深度是多少對int輸入最多遞歸31次。能不能改成循環(huán)當然能while (n 0) { count n % 2; n / 2; }。能不能更快用n (n - 1)逐次消掉最低位的1循環(huán)次數(shù)等于1的個數(shù)而非位數(shù)。這三個追問在Java面試里出現(xiàn)的頻率不低答案文檔只給了遞歸版后面兩層要靠自己推。另一類面試高頻點是復雜度排序表。建議按3.1節(jié)的表格默寫三遍直到能在一分鐘內從2/N排到2^N。遇到“N log N和N log(N2)誰快”這種送命題能脫口而出“同階”才算過關。最后是鏈表題的改寫。把printLots改成用L.get(itemP)的隨機訪問版本對比一下性能差異你就明白為什么題目強調“鏈表上不能用下標”。把swapWithNext加空指針保護再補一個單元測試覆蓋“尾部節(jié)點交換拋異?！钡膱鼍啊@些改動讓教材答案變成了生產(chǎn)級代碼面試官問到邊界處理時你也能接得住。從那以后我拿到任何一份習題答案都強制自己先盲寫一遍再對照把所有代碼跑起來驗證過才敢說“會了”。這份docx雖然排版亂、公式散但核心推導和代碼都是對的值得花一下午消化。希望幫到你。本文還有配套的精品資源點擊獲取