程序員面試手冊(cè)：概念、編程問題及面試題

Contents 目　錄
譯者序
前　言
致　謝
第1章　編程基礎(chǔ)1
1.1　變量1
1.2　數(shù)據(jù)類型1
1.3　數(shù)據(jù)結(jié)構(gòu)2
1.4　抽象數(shù)據(jù)類型3
1.5　內(nèi)存與變量3
1.6　指針4
1.6.1　指針的聲明4
1.6.2　指針的使用5
1.6.3　指針的操縱6
1.6.4　數(shù)組與指針7
1.6.5　動(dòng)態(tài)內(nèi)存分配7
1.6.6　函數(shù)指針7
1.7　參數(shù)傳遞的方式8
1.7.1　實(shí)際參數(shù)與形式參數(shù)8
1.7.2　參數(shù)傳遞的語義8
1.7.3　各種編程語言所支持的參數(shù)傳遞方式9
1.7.4　按值傳遞9
1.7.5　按結(jié)果傳遞10
1.7.6　有可能發(fā)生的參數(shù)沖突10
1.7.7　按值-結(jié)果傳遞11
1.7.8　按引用傳遞（別名機(jī)制）11
1.7.9　按名稱傳遞12
1.8　綁定12
1.8.1　靜態(tài)綁定（前期綁定）13
1.8.2　動(dòng)態(tài)綁定（后期綁定）13
1.9　作用域13
1.9.1　靜態(tài)作用域13
1.9.2　動(dòng)態(tài)作用域14
1.10　存儲(chǔ)類別15
1.10.1　存儲(chǔ)類別為auto的變量15
1.10.2　存儲(chǔ)類別為extern的變量16
1.10.3　存儲(chǔ)類別為register的變量18
1.10.4　存儲(chǔ)類別為static的變量19
1.11　存儲(chǔ)空間的安排19
1.12　編程方式22
1.12.1　無結(jié)構(gòu)的編程22
1.12.2　過程式的編程22
1.12.3　模塊式的編程22
1.12.4　面向?qū)ο蟮木幊?3
1.13　面向?qū)ο缶幊痰幕靖拍?3
1.13.1　類與對(duì)象24
1.13.2　封裝24
1.13.3　抽象25
1.13.4　數(shù)據(jù)隱藏25
1.13.5　多態(tài)25
1.13.6　繼承26
1.13.7　繼承的類型26
1.13.8　動(dòng)態(tài)綁定27
1.13.9　消息傳遞28
第2章　腳本語言83
2.1　解釋器與編譯器83
2.1.1　編譯器83
2.1.2　解釋器84
2.1.3　編譯器與解釋器的區(qū)別84
2.2　什么是腳本語言84
2.3　shell腳本編程85
2.3.1　命令的重定向與管道85
2.3.2　變量86
2.3.3　命令行參數(shù)87
2.3.4　命令替換88
2.3.5　算術(shù)擴(kuò)展88
2.3.6　控制結(jié)構(gòu)88
2.3.7　函數(shù)92
2.4　Perl94
2.4.1　從“Hello world!”程序開始94
2.4.2　Perl的命令行參數(shù)95
2.4.3　Perl的數(shù)據(jù)類型與變量95
2.4.4　引用98
2.4.5　聲明變量98
2.4.6　變量的作用域99
2.4.7　字符串字面量99
2.4.8　Perl的標(biāo)準(zhǔn)輸入端100
2.4.9　Perl語言的運(yùn)算符101
2.4.10　條件語句110
2.4.11　循環(huán)113
2.4.12　子例程115
2.4.13　字符串操作117
2.4.14　包/模塊118
2.5　Python118
2.5.1　什么是Python118
2.5.2　布爾類型119
2.5.3　整數(shù)119
2.5.4　字符串119
2.5.5　列表與元組121
2.5.6　函數(shù)122
2.5.7　把代碼包裝成模塊123
第3章　與設(shè)計(jì)有關(guān)的面試題124
3.1　術(shù)語介紹124
3.2　技巧125
3.3　可供練習(xí)的其他設(shè)計(jì)問題179
第4章　操作系統(tǒng)的概念180
4.1　術(shù)語介紹180
4.2　與操作系統(tǒng)概念有關(guān)的問題183
第5章　計(jì)算機(jī)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)188
5.1　介紹188
5.2　局域網(wǎng)與廣域網(wǎng)188
5.3　數(shù)據(jù)包分割與多路復(fù)用189
5.4　終端設(shè)備190
5.5　中介設(shè)備190
5.6　集線器、交換機(jī)與路由器的定義191
5.7　介質(zhì)192
5.8　端對(duì)端網(wǎng)絡(luò)與客戶端/服務(wù)器網(wǎng)絡(luò)192
5.9　互聯(lián)網(wǎng)是如何運(yùn)作的193
5.10　OSI模型與TCP/IP模型的區(qū)別196
5.11　客戶端/服務(wù)器結(jié)構(gòu)與互聯(lián)網(wǎng)197
5.12　ARP與RARP198
5.13　子網(wǎng)199
5.14　路由器的工作原理200
5.15　單播、廣播、多播201
5.16　tracert/traceroute及ping命令的工作原理202
5.17　什么是QoS203
第6章　數(shù)據(jù)庫概念204
6.1　術(shù)語介紹204
6.2　與數(shù)據(jù)庫概念有關(guān)的問題206
第7章　智力題213
7.1　智力題213
第8章　算法介紹217
8.1　什么是算法217
8.2　為什么要做算法分析218
8.3　算法分析的目標(biāo)218
8.4　什么是運(yùn)行時(shí)間分析218
8.5　怎樣對(duì)比不同的算法218
8.6　什么是增長(zhǎng)率219
8.7　幾種常見的增長(zhǎng)形式219
8.8　算法分析的類型220
8.9　漸近表示法221
8.10　大O表示法221
8.11　大Ω表示法222
8.12　大Θ表示法223
8.13　算法分析為什么又叫漸近分析225
8.14　漸近分析指南225
8.15　三種表示法的性質(zhì)227
8.16　常用的對(duì)數(shù)公式與求和公式227
8.17　分治算法的主定理227
8.18　與分治算法的主定理有關(guān)的問題228
8.19　遞減式遞推（減而治之）算法的主定理229
8.20　另一種遞減式遞推（減而治之）算法的主定理229
8.21　與算法分析有關(guān)的問題230
第9章　遞歸與回溯240
9.1　介紹240
9.2　什么是遞歸240
9.3　為什么要用遞歸的辦法解決問題240
9.4　遞歸函數(shù)的格式241
9.5　演示遞歸調(diào)用時(shí)的內(nèi)存占用情況241
9.6　遞歸與迭代242
9.7　運(yùn)用遞歸時(shí)的注意事項(xiàng)243
9.8　遞歸算法舉例243
9.9　與遞歸有關(guān)的問題243
9.10　什么是回溯245
9.11　回溯算法舉例245
9.12　與回溯有關(guān)的問題245
第10章　鏈表248
10.1　什么是鏈表248
10.2　將鏈表用作抽象的數(shù)據(jù)類型248
10.3　為什么要用鏈表249
10.4　數(shù)組概述249
10.5　比較鏈表、數(shù)組與動(dòng)態(tài)數(shù)組250
10.6　單鏈表251
10.7　雙鏈表256
10.8　循環(huán)鏈表261
10.9　節(jié)省內(nèi)存的雙鏈表266
10.10　松散鏈表268
10.11　跳躍鏈表273
10.12　與鏈表有關(guān)的問題276
第11章　棧295
11.1　什么是棧295
11.2　怎樣使用棧296
11.3　將棧用作抽象數(shù)據(jù)類型296
11.4　棧的運(yùn)用296
11.5　實(shí)現(xiàn)297
11.6　對(duì)比各種實(shí)現(xiàn)方式302
11.7　與棧有關(guān)的問題303
第12章　隊(duì)列324
12.1　什么是隊(duì)列324
12.2　如何使用隊(duì)列324
12.3　將隊(duì)列用作抽象數(shù)據(jù)類型325
12.4　異常325
12.5　運(yùn)用325
12.6　實(shí)現(xiàn)326
12.7　與隊(duì)列有關(guān)的問題331
第13章　樹337
13.1　什么是樹337
13.2　術(shù)語表337
13.3　二叉樹339
13.4　二叉樹的類型339
13.5　二叉樹的性質(zhì)340
13.6　遍歷二叉樹342
13.7　泛化樹（N叉樹）362
13.8　通過線索二叉樹來遍歷369
13.9　表達(dá)式樹376
13.10　異或樹379
13.11　二叉搜索樹380
13.12　平衡二叉搜索樹395
13.13　AVL樹396
13.14　其他形式的樹413
13.14.1　紅黑樹413
13.14.2　伸展樹414
13.14.3　擴(kuò)充樹（增強(qiáng)樹）414
13.14.4　區(qū)間樹（區(qū)段樹）415
13.14.5　替罪羊樹416
第14章　優(yōu)先級(jí)隊(duì)列與堆418
14.1　什么是優(yōu)先級(jí)隊(duì)列418
14.2　將優(yōu)先級(jí)隊(duì)列用作抽象數(shù)據(jù)結(jié)構(gòu)418
14.3　運(yùn)用419
14.4　實(shí)現(xiàn)419
14.5　堆與二叉堆420
14.6　二叉堆421
14.7　與優(yōu)先級(jí)隊(duì)列和堆有關(guān)的問題428
第15章　圖算法442
15.1　介紹442
15.2　術(shù)語表442
15.3　圖的運(yùn)用446
15.4　將圖用作抽象的數(shù)據(jù)結(jié)構(gòu)446
15.4.1　鄰接矩陣446
15.4.2　鄰接列表447
15.4.3　鄰接集合449
15.4.4　表示圖的方法的對(duì)比449
15.5　圖的遍歷449
15.5.1　深度優(yōu)先搜索（DFS）450
15.5.2　廣度優(yōu)先搜索（BFS）454
15.5.3　對(duì)比DFS與BFS456
15.6　拓?fù)渑判?57
15.7　最短路徑算法458
15.8　最小生成樹465
15.9　與圖算法有關(guān)的問題469
第16章　排序475
16.1　什么是排序475
16.2　為什么要排序475
16.3　排序算法的分類方式475
16.3.1　按照比較的次數(shù)來分類475
16.3.2　按照交換操作的次數(shù)來分類476
16.3.3　按照內(nèi)存使用量來分類476
16.3.4　按照是否遞歸來分類476
16.3.5　按照是否穩(wěn)定來分類476
16.3.6　按照適應(yīng)性來分類476
16.4　其他的分類方式476
16.5　冒泡排序477
16.6　選擇排序478
16.7　插入排序479
16.8　希爾排序481
16.9　歸并排序483
16.10　堆排序485
16.11　快速排序485
16.12　樹排序488
16.13　線性時(shí)間的排序算法489
16.14　計(jì)數(shù)排序489
16.15　桶排序490
16.16　基數(shù)排序490
16.17　拓?fù)渑判?91
16.18　外部排序491
16.19　與排序有關(guān)的問題492
第17章　搜索500
17.1　什么是搜索500
17.2　為什么要搜索500
17.3　各種類型的搜索500
17.4　在無序的數(shù)據(jù)中執(zhí)行線性搜索501
17.5　在已經(jīng)排好序/有序的數(shù)組中執(zhí)行線性搜索501
17.6　二分搜索501
17.7　對(duì)比幾種基本的搜索算法502
17.8　符號(hào)表與哈希502
17.9　字符串搜索算法502
17.10　與搜索有關(guān)的問題503
第18章　選擇算法530
18.1　什么是選擇算法530
18.2　通過排序來選擇530
18.3　基于分區(qū)的選擇算法531
18.4　線性選擇算法—中位數(shù)的中位數(shù)算法531
18.5　把最小的k個(gè)元素找出來531
18.6　與選擇算法有關(guān)的問題531
第19章　符號(hào)表541
19.1　介紹541
19.2　什么是符號(hào)表541
19.3　實(shí)現(xiàn)符號(hào)表542
19.4　比較實(shí)現(xiàn)符號(hào)表的各種方式543
第20章　哈希544
20.1　什么是哈希544
20.2　為什么要使用哈希544
20.3　將哈希表用作抽象數(shù)據(jù)結(jié)構(gòu)544
20.4　哈希技術(shù)的原理545
20.5　哈希技術(shù)的組成要素546
20.6　哈希表546
20.7　哈希函數(shù)547
20.8　負(fù)載因子547
20.9　沖突547
20.10　沖突解決技術(shù)548
20.11　單獨(dú)鏈接法548
20.12　開放定址548
20.12.1　線性探測(cè)548
20.12.2　二次探測(cè)549
20.12.3　二次哈希550
20.13　比較各種沖突解決技術(shù)550
20.14　哈希技術(shù)如何把復(fù)雜度降為O(1)551
20.15　哈希技術(shù)551
20.16　哪些問題不適合用哈希表解決551
20.17　Bloom過濾器552
20.17.1　工作原理552
20.17.2　選擇合適的哈希函數(shù)553
20.17.3　設(shè)置長(zhǎng)度合適的位向量553
20.17.4　空間方面的優(yōu)勢(shì)553
20.17.5　時(shí)間方面的優(yōu)勢(shì)554
20.17.6　實(shí)現(xiàn)554
20.18　與哈希有關(guān)的問題554
第21章　字符串算法565
21.1　介紹565
21.2　字符串匹配算法565
21.3　蠻力法566
21.4　Rabin-Karp字符串匹配算法566
21.5　用有限狀態(tài)機(jī)來實(shí)現(xiàn)字符串匹配算法567
21.5.1　狀態(tài)機(jī)的運(yùn)作過程568
21.5.2　構(gòu)建有限狀態(tài)機(jī)時(shí)的注意事項(xiàng)568
21.5.3　匹配算法568
21.6　KMP算法569
21.6.1　前綴表569
21.6.2　匹配算法571
21.7　Boyce-Moore算法573
21.8　適合用來保存字符串的數(shù)據(jù)結(jié)構(gòu)573
21.9　用哈希表來保存字符串574
21.10　用二叉搜索樹來存放字符串574
21.11　前綴樹574
21.11.1　什么是前綴樹574
21.11.2　為什么要使用前綴樹575
21.11.3　聲明前綴樹575
21.11.4　向前綴樹中插入字符串576
21.11.5　在前綴樹中查找字符串576
21.11.6　用前綴樹來表示字符串有什么缺點(diǎn)577
21.12　三元搜索樹577
21.12.1　聲明三元搜索樹577
21.12.2　向三元搜索樹中插入字符串578
21.12.3　在三元搜索樹中查找字符串580
21.12.4　顯示三元搜索樹中的全部字符串580
21.12.5　在三元搜索樹中查找最長(zhǎng)的字符串581
21.13　比較二叉搜索樹、前綴樹及三元搜索樹581
21.14　后綴樹581