計算機考研指導全書

《計算機考研指導全書》是2016年9月電子工業出版社出版的圖書，作者是王道論壇。

基本介紹

• 中文名：計算機考研指導全書
• 作者：王道論壇
• 出版時間：2016年9月
• 出版社：電子工業出版社
• 頁數：540 頁
• ISBN：9787121283413
• 定價：69 元
• 開本：16 開

內容簡介

本書是計算機專業研究生入學考試四門主幹課程的綜合複習用書，內容分為數據結構篇、計算機組成原理篇、作業系統篇、計算機網路篇。全書嚴格按照最新計算機考研大綱，對大綱所涉及的知識點進行集中梳理，精選名校歷年考研真題，給出詳細的解題思路，力求達到講練結合、靈活掌握、舉一反三的功效，並力求內容精煉、重點突出、深入淺出。同時，創新的“書本+線上”的學習方式與網上答疑，可大大提高考生的複習效果，達到事半功倍的複習效率。

圖書目錄

第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.4 B-樹和B+樹 106

6.4.1 B-樹的概念 106

6.4.2 B-樹的查找 107

6.4.3 B-樹的插入 108

6.4.4 B-樹的刪除 108

6.4.5 B+樹的基本概念 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.3 BCD碼 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.2 SRAM存儲器 184

3.3.3 DRAM存儲器 184

3.3.4 存儲器的讀、寫周期 185

3.3.5 SRAM和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.2 Cache的基本工作原理 192

3.7.3 Cache和主存的映射

方式 193

3.7.4 Cache中主存塊的替換

算法 194

3.7.5 Cache寫策略 194

3.8 虛擬存儲器 195

3.8.1 基本概念 195

3.8.2 頁式虛擬存儲器 195

3.8.3 段式虛擬存儲器 196

3.8.4 段頁式虛擬存儲器 196

3.8.5 TLB（快表） 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.3 CISC和RISC的基本概念 215

例題精析 216

習題精選 218

參考答案 221

第5章 中央處理器（CPU） 224

5.1 CPU的功能和基本結構 224

5.1.1 CPU的功能 224

5.1.2 CPU的基本結構 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.1 I/O系統基本概念 263

7.2 外部設備 264

7.2.1 輸入設備 264

7.2.2 輸出設備 264

7.2.3 外存儲器 265

7.3 I/O接口（I/O控制器） 267

7.3.1 I/O接口的功能 267

7.3.2 I/O接口的基本結構 267

7.3.3 I/O接口的類型 268

7.3.4 I/O連線埠及其編址 268

7.4 I/O方式 268

7.4.1 程式查詢方式 269

7.4.2 程式中斷方式 269

7.4.3 DMA方式 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.1 I/O管理概述 391

5.1.1 I/O設備 391

5.1.2 I/O控制方式 392

5.2 I/O核心子系統 395

5.2.1 I/O層次結構 395

5.2.2 高速快取與緩衝區 395

5.2.3 設備分配與回收 397

5.2.4 SPOOLing技術（假脫機技術） 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.3 ISO/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 乙太網與IEEE 802.3 437

3.6.4 令牌環網的基本原理 441

3.7 廣域網 441

3.7.1 廣域網的基本概念 441

3.7.2 PPP協定 442

3.7.3 HDLC協定 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.3 IPv4 461

4.3.1 IPv4分組 461

4.3.2 IPv4地址與網路地址轉換NAT 462

4.3.3 子網劃分與子網掩碼、

CIDR 464

4.3.4 ARP協定、DHCP協定與ICMP協定 466

4.4 IPv6 468

4.4.1 IPv6的主要特點 468

4.4.2 IPv6地址 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.6 IP組播 474

4.6.1 IP組播的概念 474

4.6.2 IP組播地址 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.1 UDP數據報 493

5.2.2 UDP校驗 493

5.3 傳輸控制協定TCP 494

5.3.1 TCP報文段 494

5.3.2 TCP連線管理 496

5.3.3 TCP可靠傳輸 498

5.3.4 TCP流量控制與擁塞

控制 499

例題精析 502

習題精選 503

參考答案 505

第6章 套用層 508

6.1 網路套用模型 508

6.1.1 客戶/伺服器模型 508

6.1.2 P2P模型 508

6.2 DNS系統 509

6.2.1 層次域名空間 509

6.2.2 域名伺服器 509

6.2.3 域名解析過程 510

6.3 檔案傳輸協定FTP 511

6.3.1 FTP協定的工作原理 511

6.3.2 控制連線與數據連線 511

6.4 電子郵件 512

6.4.1 電子郵件系統的組成

結構 512

6.4.2 電子郵件的格式與

MIME 513

6.4.3 SMTP協定與POP3

協定 514

6.5 全球資訊網WWW 514

6.5.1 WWW的概念與組成

結構 514

6.5.2 超文本傳輸協定HTTP 515

例題精析 517

習題精選 518

參考答案 520

參考文獻 522