計算機考研指導全書

第1篇數據結構
第1章緒論 2
1.1基本概念和術語 2
1.2算法和算法評價 3
1.2.1算法 3
1.2.2算法評價 4
例題精析 4
習題精選 5
參考答案 5
第2章線性表 7
2.1線性表的定義和基本操作 7
2.1.1線性表的定義 7
2.1.2線性表的基本操作 7
2.2線性表的順序存儲結構及實現 8
2.2.1線性表的順序存儲 8
2.2.2順序表上基本操作的實現 9
2.3線性表的鏈式存儲結構及實現 11
2.3.1單鏈表 11
2.3.2雙鏈表 15
2.3.3循環鏈表 16
2.3.4靜態鏈表 17
2.4順序存儲和鏈式存儲的對比 18
例題精析 19
習題精選 20
參考答案 22
第3章棧、隊列和數組 30
3.1棧和隊列的基本概念 30
3.1.1棧的基本定義和運算 30
3.1.2隊列的基本定義和運算 31
3.2棧的存儲結構及其基本運算的實現 31
3.2.1棧的順序存儲結構 31
3.2.2棧的鏈式存儲結構 32
3.3隊列的存儲結構及其基本運算的實現 33
3.3.1隊列的順序存儲結構 33
3.3.2隊列的鏈式存儲結構 35
3.3.3雙端隊列 35
3.4棧和隊列的應用 36
3.4.1棧在括號匹配中的應用 36
3.4.2棧在表達式計算中的應用 36
3.4.3棧在遞歸中的應用 37
3.4.4隊列在層次遍歷中的應用 37
3.4.5隊列在計算機系統中的應用 38
3.5特殊矩陣的壓縮存儲 38
3.5.1對稱矩陣的壓縮存儲 38
3.5.2三角矩陣的壓縮存儲 39
3.5.3三對角矩陣的壓縮存儲 40
例題精析 40
習題精選 41
參考答案 43
第4章樹與二叉樹 48
4.1樹的基本概念和性質 48
4.2二叉樹 49
4.2.1二叉樹的定義及其主要特征 49
4.2.2二叉樹的順序存儲結構和鏈式存儲結構 50
4.2.3二叉樹的遍歷 51
4.2.4線索二叉樹的基本概念和構造 53
4.3樹、森林 55
4.3.1樹的存儲結構 55
4.3.2樹、森林和二叉樹的轉換 56
4.3.3樹和森林的遍歷 57
4.4樹與二叉樹的應用 57
4.4.1二叉排序樹 57
4.4.2平衡二叉樹 60
4.4.3赫夫曼（Huffman）樹和赫夫曼編碼 62
例題精析 63
習題精選 67
參考答案 70
第5章圖 78
5.1圖的基本概念 78
5.2圖的存儲結構 79
5.2.1鄰接矩陣 79
5.2.2鄰接表 80
5.2.3十字鏈表 82
5.2.4鄰接多重表 83
5.3圖的遍歷 84
5.3.1深度優先搜索 84
5.3.2廣度優先搜索 85
5.4圖的基本應用 87
5.4.1最小生成樹 87
5.4.2最短路徑 89
5.4.3拓撲排序 91
5.4.4關鍵路徑 93
例題精析 94
習題精選 96
參考答案 99
第6章查找 103
6.1基本概念 103
6.2順序查找 104
6.2.1一般線性表的順序查找 104
6.2.2有序表的順序查找 105
6.3折半查找 105
6.4B—樹和B+樹 106
6.4.1B—樹的概念 106
6.4.2B—樹的查找 107
6.4.3B—樹的插入 108
6.4.4B—樹的刪除 108
6.4.5B+樹的基本概念 109
6.5散列（Hash）表 110
6.5.1散列表的基本概念 110
6.5.2散列函數 110
6.5.3處理沖突的方法 111
6.5.4散列法性能分析 112
例題精析 112
習題精選 114
參考答案 115
第7章排序 119
7.1排序的基本概念 119
7.2插入排序 120
7.2.1直接插入排序 120
7.2.2折半插入排序 120
7.2.3希爾排序 121
7.3交換排序 122
7.3.1冒泡排序 122
7.3.2快速排序 122
7.4選擇排序 124
7.4.1簡單選擇排序 124
7.4.2堆排序 124
7.5二路歸並排序 126
7.6基數排序 127
7.7不同排序算法的比較 128
7.8外部排序 129
7.8.1外部排序的方法 130
7.8.2多路平衡歸並與敗者樹 131
7.8.3置換—選擇排序（生成初始歸並段） 132
7.8.4最佳歸並樹 133
例題精析 134
習題精選 135
參考答案 138
第2篇計算機組成原理
第1章計算機系統概論 144
1.1計算機發展歷程 144
1.1.1計算機的發展 144
1.1.2計算機的分類 145
1.2計算機系統層次結構 145
1.2.1計算機硬件的基本組成 145
1.2.2計算機系統的層次結構 146
1.2.3計算機軟件的分類 147
1.2.4計算機的工作過程 148
1.3計算機性能指標 149
1.3.1計算機的主要性能指標 149
1.3.2幾個專業術語的概念 150
例題精析 150
習題精選 150
參考答案 152
第2章數據的表示和運算 154
2.1數制與編碼 154
2.1.1進位計數制及其相互轉換 154
2.1.2真值和機器數 155
2.1.3BCD碼 155
2.1.4字符與字符串 156
2.1.5校驗碼 157
2.2定點數的表示和運算 159
2.2.1數的機器碼表示 159
2.2.2定點數的表示 161
2.2.3定點數的運算 162
2.2.3強制類型轉換 165
2.3浮點數的表示和運算 166
2.3.1浮點數的表示法 166
2.3.2浮點數的加／減運算 168
2.4算術邏輯單元（ALU） 169
2.4.1串行加法器和並行加法器 170
2.4.2算術邏輯單元的功能和結構 172
例題精析 174
習題精選 175
參考答案 178
第3章存儲器系統的層次結構 182
3.1存儲器的分類 182
3.1.1存儲器的分類 182
3.1.2存儲器的性能指標 183
3.2存儲器的層次結構 183
3.3半導體隨機存取存儲器 184
3.3.1存儲芯片的基本結構 184
3.3.2SRAM存儲器 184
3.3.3DRAM存儲器 184
3.3.4存儲器的讀、寫周期 185
3.3.5SRAM和DRAM的比較 186
3.4只讀存儲器 186
3.5存儲器與CPU的連接 187
3.5.1連接原理 187
3.5.2存儲容量的擴展 187
3.5.3存儲芯片的地址分配和片選 189
3.5.4存儲器與CPU的連接 189
3.6雙口RAM和多模塊存儲器 190
3.6.1雙端口RAM 190
3.6.2多模塊存儲器 190
3.7高速緩沖存儲器 192
3.7.1程序訪問的局部性原理 192
3.7.2Cache的基本工作原理 192
3.7.3Cache和主存的映像方式 193
3.7.4Cache中主存塊的替換算法 194
3.7.5Cache寫策略 194
3.8虛擬存儲器 195
3.8.1基本概念 195
3.8.2頁式虛擬存儲器 195
3.8.3段式虛擬存儲器 196
3.8.4段頁式虛擬存儲器 196
3.8.5TLB（快表） 197
3.8.6虛擬存儲器與Cache的比較 197
例題精析 197
習題精選 200
參考答案 204
第4章指令系統 209
4.1指令格式 209
4.1.1指令的基本格式 209
4.1.2定長操作碼指令格式 210
4.1.3擴展操作碼指令格式 211
4.2指令的尋址方式 211
4.2.1有效地址的概念 211
4.2.2數據尋址和指令尋址 211
4.3CISC和RISC的基本概念 215
例題精析 216
習題精選 218
參考答案 221
第5章中央處理器（CPU） 224
5.1CPU的功能和基本結構 224
5.1.1CPU的功能 224
5.1.2CPU的基本結構 224
5.2指令執行過程 225
5.2.1指令的執行 225
5.2.2指令周期 226
5.2.3指令執行方案 227
5.3數據通路的功能和基本結構 227
5.3.1數據通路的功能 227
5.3.2數據通路的基本結構 228
5.4控制器的功能和工作原理 229
5.4.1控制器的地位與結構 229
5.4.2硬布線控制器 230
5.4.3微過程控制器 232
5.5指令流水線 237
5.5.1指令流水線的基本概念 237
5.5.2影響流水線的因素 238
5.5.3流水線的分類 239
5.5.4流水線的性能指標 240
例題精析 241
習題精選 243
參考答案 247
第6章總線 252
6.1總線概述 252
6.1.1總線的基本概念 252
6.1.2總線的分類 253
6.1.3總線的結構與性能指標 253
6.2總線仲裁 254
6.2.1集中仲裁方式 254
6.2.2分布仲裁方式 256
6.3總線操作和定時 256
6.3.1數據的傳輸 256
6.3.2同步定時方式 256
6.3.3異步定時方式 256
6.4總線標准 257
例題精析 258
習題精選 258
參考答案 260
第7章輸入／輸出（I／O）系統 263
7.1I／O系統基本概念 263
7.2外部設備 264
7.2.1輸入設備 264
7.2.2輸出設備 264
7.2.3外存儲器 265
7.3I／O接口（I／O控制器） 267
7.3.1I／O接口的功能 267
7.3.2I／O接口的基本結構 267
7.3.3I／O接口的類型 268
7.3.4I／O端口及其編址 268
7.4I／O方式 268
7.4.1程序查詢方式 269
7.4.2程序中斷方式 269
7.4.3DMA方式 272
例題精析 274
習題精選 276
參考答案 278
第3篇操作系統
第1章操作系統概述 283
1.1操作系統的概念、特征、功能和提供的服務 283
1.1.1操作系統的基本概念 283
1.1.2操作系統的特征 283
1.1.3操作系統的功能 284
1.2操作系統的發展與分類 285
1.3操作系統的運行環境 286
1.4操作系統的體系結構 288
例題精析 289
習題精選 289
參考答案 291
第2章進程管理 293
2.1進程與線程 293
2.1.1進程概念 293
2.1.2進程的狀態與轉換 294
2.1.3進程控制 295
2.1.4進程組織 296
2.1.5進程與程序的區別 297
2.1.6進程通信 297
2.1.7線程概念與多線程模型 298
2.2處理器調度 300
2.2.1調度的基本概念 300
2.2.2調度時機、切換與過程 301
2.2.3進程的調度方式 302
2.2.4調度的基本准則 302
2.2.5典型調度算法 303
2.3進程同步 305
2.3.1進程同步的基本概念 305
2.3.2實現臨界區互斥的基本方法 306
2.3.3信號量 309
2.3.4管程 311
2.3.5經典同步問題 311
2.4死鎖 316
2.4.1死鎖的概念 316
2.4.2死鎖處理策略 317
2.4.3死鎖預防 318
2.4.4死鎖避免 318
2.4.5死鎖檢測和解除 320
例題精析 321
習題精選 325
參考答案 329
第3章內存管理 336
3.1內存管理基礎 336
3.1.1內存管理的概念 336
3.1.2覆蓋與交換 339
3.1.3連續分配管理方式 339
3.1.4非連續分配管理方式 341
3.2虛擬內存管理 348
3.2.1虛擬內存的基本概念 348
3.2.2請求分頁管理方式 350
3.2.3頁面置換算法 351
3.2.4頁面分配策略 353
3.2.5抖動和工作集 354
例題精析 355
習題精選 358
參考答案 361
第4章文件管理 367
4.1文件系統基礎 367
4.1.1文件概念 367
4.1.2文件的邏輯結構 368
4.1.3目錄結構 368
4.1.4文件共享 371
4.1.5文件保護 372
4.2文件系統實現 373
4.2.1文件系統層次結構 373
4.2.2目錄實現 373
4.2.3文件實現 374
4.3磁盤組織與管理 377
4.3.1磁盤的結構 377
4.3.2磁盤調度算法 378
4.3.3磁盤的管理 381
例題精析 382
習題精選 383
參考答案 387
第5章輸入／輸出（I／O）管理 391
5.1I／O管理概述 391
5.1.1I／O設備 391
5.1.2I／O控制方式 392
5.2I／O核心子系統 395
5.2.1I／O層次結構 395
5.2.2高速緩存與緩沖區 395
5.2.3設備分配與回收 397
5.2.4SPOOLing技術（假脫機技術） 399
5.2.5出錯處理 399
例題精析 400
習題精選 401
參考答案 402
第4篇計算機網絡
第1章計算機網絡體系結構 406
1.1計算機網絡概述 406
1.1.1計算機網絡的概念、組成與功能 406
1.1.2計算機網絡的分類 407
1.1.3計算機網絡的標准化及相關組織 407
1.1.4計算機網絡的性能指標 407
1.2計算機網絡體系結構與參考模型 408
1.2.1計算機網絡的分層結構 408
1.2.2計算機網絡協議、接口、服務等概念 408
1.2.3ISO／OSI參考模型和TCP／IP模型 409
例題精析 411
習題精選 411
參考答案 412
第2章物理層 415
2.1通信基礎 415
2.1.1物理層相關的基本概念 415
2.1.2奈奎斯特定理與香農定理 416
2.1.4編碼與調制 417
2.1.5電路交換、報文交換與分組交換 418
2.1.6數據報與虛電路 420
2.2傳輸介質 421
2.2.1傳輸介質簡介 421
2.2.2物理層接口的特性 422
2.3物理層設備 422
2.3.1中繼器 422
2.3.2集線器（Hub） 422
例題精析 423
習題精選 424
參考答案 426
第3章數據鏈路層 429
3.1數據鏈路層的功能 429
3.2組幀 430
3.3差錯控制 430
3.3.1檢錯編碼 430
3.3.2糾錯編碼 431
3.4流量控制與可靠傳輸機制 431
3.4.1流量控制、可靠傳輸與滑動窗口機制 431
3.4.2單幀滑動窗口與停止—等待協議 432
3.4.3多幀滑動窗口與后退N幀協議 433
3.4.4多幀滑動窗口與選擇重傳協議 433
3.5介質訪問控制 433
3.5.1信道划分介質訪問控制 433
3.5.2隨機訪問介質訪問控制 435
3.5.3輪詢訪問介質訪問控制 436
3.6局域網 436
3.6.1局域網的基本概念與體系結構 436
3.6.2以太網與IEEE802.3437
3.6.4令牌環網的基本原理 441
3.7廣域網 441
3.7.1廣域網的基本概念 441
3.7.2PPP協議 442
3.7.3HDLC協議 443
3.8數據鏈路層設備 444
3.8.1網橋的概念和基本原理 444
3.8.2局域網交換機及其工作原理 445
例題精析 446
習題精選 448
參考答案 452
第4章網絡層 458
4.1網絡層的功能 458
4.1.1異構網絡互連 458
4.1.2路由選擇與轉發 459
4.1.3擁塞控制 459
4.2路由算法 459
4.2.1靜態路由與動態路由 459
4.2.2距離向量路由算法 460
4.2.3鏈路狀態路由算法 460
4.2.4層次路由 460
4.3IPv4461
4.3.1IPv4分組 461
4.3.2IPv4地址與網絡地址轉換NAT 462
4.3.3子網划分與子網掩碼、CIDR 464
4.3.4ARP協議、DHCP協議與ICMP協議 466
4.4IPv6468
4.4.1IPv6的主要特點 468
4.4.2IPv6地址 469
4.5路由協議 470
4.5.1自治系統 470
4.5.2域內路由與域間路由 470
4.5.3內部網關協議：RIP協議 470
4.5.4內部網關協議：OSPF協議 471
4.5.5外部網關協議：BGP協議 473
4.6IP組播 474
4.6.1IP組播的概念 474
4.6.2IP組播地址 475
4.7網絡層設備 476
4.7.1路由器的組成和功能 476
4.7.2路由表與路由轉發 477
例題精析 478
習題精選 481
參考答案 485
第5章傳輸層 490
5.1傳輸層提供的服務 490
5.1.1傳輸層的功能 490
5.1.2傳輸層的尋址與端口 491
5.1.3無連接服務與面向連接服務 492
5.2用戶數據報協議UDP 492
5.2.1UDP數據報 493
5.2.2UDP校驗 493
5.3傳輸控制協議TCP 494
5.3.1TCP報文段 494
5.3.2TCP連接管理 496
5.3.3TCP可靠傳輸 498
5.3.4TCP流量控制與擁塞控制 499
例題精析 502
習題精選 503
參考答案 505
第6章應用層 508
6.1網絡應用模型 508
6.1.1客戶／服務器模型 508
6.1.2P2P模型 508
6.2DNS系統 509
6.2.1層次域名空間 509
6.2.2域名服務器 509
6.2.3域名解析過程 510
6.3文件傳輸協議FTP 511
6.3.1FTP協議的工作原理 511
6.3.2控制連接與數據連接 511
6.4電子郵件 512
6.4.1電子郵件系統的組成結構 512
6.4.2電子郵件的格式與MIME 513
6.4.3SMTP協議與POP3協議 514
6.5萬維網WWW 514
6.5.1WWW的概念與組成結構 514
6.5.2超文本傳輸協議HTTP 515
例題精析 517
習題精選 518
參考答案 520
參考文獻 522