直擊招聘:程序員面試筆試數據結構深度解析 | 被動收入的投資秘訣 - 2024年9月
![](https://www.books.com.tw/img/CN1/154/10/CN11541047.jpg)
直擊招聘:程序員面試筆試數據結構深度解析
本書彙集國內外眾多著名IT企業近幾年的資料結構面試筆試真題並予以解析,按知識點類型對常見的資料結構難點和疑點進行了系統歸納和透徹剖析,並提供了一定數量的自測題以便於讀者自我檢驗。
全書邏輯清晰、通俗易懂,適合參加IT企業校園招聘和麵試筆試環節的同學複習,也適合資料結構和演算法設計程式設計愛好者以及在校學生閱讀和提高。
李春葆,武漢大學教授,主要研究方向為資料採擷和演算法設計,從事近30年電腦C/C++語言、資料結構和演算法設計等課程的一線本科教學工作,具備豐富的教學經驗,曾參於深圳名企的筆試和麵試題庫建設。出版多本C/C++語言、資料結構、演算法設計與分析及資料庫開發方面的精品教材和教學輔導書。
李筱馳:
美國俄亥俄州立大學電腦科學專業碩士畢業,曾參加穀歌等名企面試,具備比較豐富的企業筆試和麵試經驗。目前在西雅圖亞馬遜總部工作。
第1章 資料結構基礎 1
常見考點 1
1.1 資料結構的概念 1
1.1.1 要點歸納 1
1.1.2 面試題解析 2
1.2 演算法描述和分析 5
1.2.1 要點歸納 5
1.2.2 面試題解析 6
1.3 演算法設計手段——遞迴 8
1.3.1 要點歸納 8
1.3.2 面試題解析 16
1.4 自測題和參考答案 31
1.4.1 自測題 31
1.4.2 參考答案 33
第2章 線性表Ⅰ——陣列 36
常見考點 36
2.1 線性表順序存儲結構 36
2.1.1 要點歸納 36
2.1.2 面試題解析 38
2.2 陣列的基本演算法設計 39
2.2.1 要點歸納 39
2.2.2 面試題解析 45
2.3 有序數組的演算法設計 55
2.3.1 要點歸納 55
2.3.2 面試題解析 59
2.4 多維陣列 63
2.4.1 要點歸納 63
2.4.2 面試題解析 64
2.5 自測題和參考答案 70
2.5.1 自測題 70
2.5.2 參考答案 71
第3章 線性表Ⅱ——鏈表 77
常見考點 77
3.1 線性錶鏈式存儲結構概述 77
3.1.1 要點歸納 77
3.1.2 面試題解析 78
3.2 單鏈表演算法設計 79
3.2.1 要點歸納 79
3.2.2 面試題解析 82
3.3 雙鏈表演算法設計 101
3.3.1 要點歸納 101
3.3.2 面試題解析 101
3.4 迴圈鏈表演算法設計 104
3.4.1 要點歸納 104
3.4.2 面試題解析 104
3.5 自測題和參考答案 113
3.5.1 自測題 113
3.5.2 參考答案 114
第4章 字串 121
常見考點 121
4.1 字串基礎 121
4.1.1 要點歸納 121
4.1.2 面試題解析 122
4.2 字串匹配演算法設計 133
4.2.1 要點歸納 133
4.2.2 面試題解析 135
4.3 自測題和參考答案 146
4.3.1 自測題 146
4.3.2 參考答案 147
第5章 棧 149
常見考點 149
5.1 棧基本演算法設計 149
5.1.1 要點歸納 149
5.1.2 面試題解析 151
5.2 棧應用演算法設計 155
5.2.1 要點歸納 155
5.2.2 面試題解析 156
5.3 自測題和參考答案 179
5.3.1 自測題 179
5.3.2 參考答案 180
第6章 佇列 184
常見考點 184
6.1 佇列基本演算法設計 184
6.1.1 要點歸納 184
6.1.2 面試題解析 186
6.2 佇列應用演算法設計 189
6.2.1 要點歸納 189
6.2.2 面試題解析 191
6.3 自測題和參考答案 201
6.3.1 自測題 201
6.3.2 參考答案 202
第7章 樹和二叉樹 205
常見考點 205
7.1 樹 205
7.1.1 要點歸納 205
7.1.2 面試題解析 208
7.2 二叉樹概念 210
7.2.1 要點歸納 210
7.2.2 面試題解析 212
7.3 二叉樹遍歷及演算法設計 216
7.3.1 要點歸納 216
7.3.2 面試題解析 223
7.4 哈夫曼樹 262
7.4.1 要點歸納 262
7.4.2 面試題解析 263
7.5 自測題和參考答案 265
7.5.1 自測題 265
7.5.2 參考答案 267
第8章 圖 274
常見考點 274
8.1 圖的概念和存儲結構 274
8.1.1 要點歸納 274
8.1.2 面試題解析 277
8.2 圖的遍歷演算法及其應用 280
8.2.1 要點歸納 280
8.2.2 面試題解析 286
8.3 圖的應用 302
8.3.1 要點歸納 302
8.3.2 面試題解析 304
8.4 自測題和參考答案 340
8.4.1 自測題 340
8.4.2 參考答案 344
第9章 查找 352
常見考點 352
9.1 順序表的查找 352
9.1.1 要點歸納 352
9.1.2 面試題解析 354
9.2 二叉排序樹和平衡二叉樹 366
9.2.1 要點歸納 366
9.2.2 面試題解析 367
9.3 B樹和B+樹 381
9.3.1 要點歸納 381
9.3.2 面試題解析 382
9.4 雜湊表查找 382
9.4.1 要點歸納 382
9.4.2 面試題解析 386
9.5 自測題和參考答案 393
9.5.1 自測題 393
9.5.2 參考答案 395
第10章 排序 399
常見考點 399
10.1 插入排序 399
10.1.1 要點歸納 399
10.1.2 面試題解析 402
10.2 交換排序 404
10.2.1 要點歸納 404
10.2.2 面試題解析 406
10.3 選擇排序 416
10.3.1 要點歸納 416
10.3.2 面試題解析 418
10.4 歸併排序 423
10.4.1 要點歸納 423
10.4.2 面試題解析 424
10.5 基數排序和桶排序 429
10.5.1 要點歸納 429
10.5.2 面試題解析 431
10.6 外排序 435
10.6.1 要點歸納 435
10.6.2 面試題解析 436
10.7 自測題和參考答案 437
10.7.1 自測題 437
10.7.2 參考答案 438
附錄A 演算法索引 443
資料結構求解問題的思路是“資料邏輯結構→存儲結構→基本演算法實現→應用”,這一思路展示了計算邏輯思維,也就是用電腦求解問題的基本過程。
程式設計的第一步需要理解問題本身,提煉出資料邏輯結構和相關運算;然後實現資料的機內表示,也就是資料的存儲結構設計,好的存儲結構設計會達到事半功倍的效果;最後在存儲結構上實現資料的運算,即演算法實現。
常用的資料結構有線性表、棧、佇列、串、樹、二叉樹和圖等,除了圍繞這些資料結構的基本運算演算法設計外,還包含查找和排序演算法設計。
在面試筆試中資料結構的考點主要包含兩個方面:一是常用資料結構的基本知識點,包括各種資料結構的邏輯特點、存儲方式和運算演算法,如一個城市圖的存儲、在城市圖中查找兩個城市之間的最短路徑等;二是常用資料結構的應用知識點,能夠熟練地利用資料結構解決問題,如用棧或者佇列求解迷宮問題,用棧求解皇后問題等。
很多資料結構都是遞迴資料結構,遞迴也是求解問題的基本方法,所以面試者必須具有遞迴演算法設計能力,掌握從遞迴模型、遞迴演算法執行過程到遞迴演算法設計的一般方法,為二叉樹、圖等複雜資料結構演算法設計打下堅實的基礎。
本書系統歸納了資料結構常見的知識要點,彙集國內外眾多著名IT企業近幾年的資料結構面試筆試真題並予以解析,透徹地剖析了難點和疑點,每道面試題給出了難度標識,從一星到五星難度依次遞增。
在本書的編寫過程中參考了眾多網站和博客,無法一一列出,在此編者表示衷心感謝。
限於編者水準,書中難免存在遺漏,懇請讀者批評指正。
編者
2018年3月