CPU的功能

1）程序控制

2）操作控制

3）時間控制

4）數據處理

CPU的組成

運算器，控制器，寄存器，內部總線等組件組成

多核CPU

計算機系統結構概述

1）計算機體系結構

2）計算機組織

3）計算機實現

計算機體系結構分類

宏觀上：單處理系統，并行處理與多處理系統，分布式處理系統

微觀上：

? 1）Flynn分類法

? 2）馮澤云分類法

? 3）Handler分類法

? 4）Kuck分類法

指令系統

1）指令集體系結構的分類

2）CISC和RISC

陣列處理機，并行處理機和多處理機

存儲器的層次結構

CPU內部的通用寄存器組，CPU內部的Cache（高速緩存），CPU外部的Cache，主板上的主存儲器，主板外的聯機磁盤存儲器和脫機的磁帶存儲器和光盤存儲器

存儲器的分類

1）按存儲器位置分類

（1）內存。也稱主存，在主機內或主機板上，用來存放機器當前運行所需要的程序和數據

（2）外存。也稱輔存，如磁盤，磁帶和光盤

2）按存儲器構成材料分類

（1）磁存儲器

（2）半導體存儲器

（3）光存儲器

3）按存儲器工作方式分類

（1）讀/寫存儲器

（2）只讀存儲器

? ①固定只讀存儲器

? ②可編程的只讀存儲器

? ③可擦除可編程的只讀存儲器

? ④電擦除可編程的只讀存儲器

? ⑤閃速存儲器

4）按訪問方式分類

（1）按地址訪問存儲器

（2）按內容訪問的存儲器

5）按尋址方式分類

（1）隨機存儲器

（2）順序存儲器

（3）直接存儲器

相聯存儲器

高速緩存

1）高速緩存的組成

2）高速緩存的地址映像方法

（1）直接映像

（2）全相聯映像

（3）組相連映像

3）替換算法

（1）隨機替換算法

（2）先進先出算法

（3）近期最少使用算法

（4）優化替換算法

4）Cache的性能分析

容量越高，命中率越高，命中時間越長

5）多級Cache

L1容量較小，速度快，L2容量大

虛擬存儲器

虛擬地址

外存儲器

1）磁表面存儲器

2）光盤存儲器

3）固態硬盤

磁盤陣列技術

存儲域網絡

微型計算機中最常用的內存與接口的編址方法

1）內存與接口地址獨立編址方法

2）內存與接口地址統一編址方法

直接程序控制

1）無條件傳送

2）程序查詢方式

（1）降低了CPU的效率

（2）對外部的突發事件無法做出實時響應

中斷方式

1）中斷處理方法

（1）多中斷信號線法

（2）中斷軟件查詢法

（3）菊花鏈法

（4）總線仲裁法

（5）中斷向量表法

2）中斷優先級控制

（1）優先處理高優先級的中斷源

（2）中斷嵌套

直接存儲器存取方式

直接內存存取（Direct Memory Access，DMA）

輸入/輸出處理機（IOP）

總線的分類

1）數據總線（Data Bus，DB）

2）地址總線（Address Bus，AB）

3）控制總線（Control Bus，CB）

常見總線

1）ISA總線

2）EISA總線

3）PCI總線

4）PCI Express總線

5）前端總線

6）RS-232C

7）SCSI總線

8）SATA

9）USB

10）IEEE-1349

11）IEEE-488

計算機的安全等級

三類安全性包括技術安全性，管理安全性，政策法律安全性

1）TCSEC

2）CTCPEC

3）PC

4）ITSEC

5）CC

安全威脅

分為故意，偶然兩類

影響數據安全的因素

1）內部因素

2）外部因素

加密技術

1）對稱加密技術

（1）數據加密標準（Digital Encryption Standard，DES）

（2）三重DES（3DES，或稱TDEA）

（3）RC-5（Rivest Cipher5）

（4）國際數據加密算法（International Data Encryption Adleman，IDEA）

（5）高機加密標準（Advanced Encryption Standard，AES）

2）非對稱加密技術

3）密鑰管理

（1）密鑰產生

（2）密鑰備份和恢復

（3）密鑰更新

（4）多密鑰的管理

認證技術

完整的PKI系統：

1）認證機構

2）數字證書庫

3）密鑰備份及恢復系統

4）證書作廢系統

5）應用接口

PKI標準化問題

1）Hash函數與信息摘要

? MD5算法特點：

? （1）壓縮性

? （2）容易計算

? （3）抗修改性

? （4）強抗碰撞

2）數字簽名和數字加密

3）SSL協議（Secure Socker Layer，安全套接層）

（1）用戶和服務器的合法性認證

（2）加密數據以隱藏被傳送的數據

（3）保護數據的完整性

? 對通信過程進行安全保護

? （1）接通階段

? （2）密碼交換階段

? （3）會談密碼階段

? （4）檢驗階段

? （5）客戶認證階段

? （6）結束階段

4）數字時間戳技術

數字時間戳服務（Digital Time Stamp Service，DTS）

（1）需加時間戳的文件的摘要（Digest）

（2）DTS收到文件的日期的時間

（3）DTS的數字簽名

性能評測的常用方法

1）時鐘頻率

2）指令執行速度

3）等效指令速度法

4）數據處理速率（Processing Data Rate，PDR）

5）核心程序法

基準測試程序

1）整數測試程序

2）浮點測試程序

（1）理論峰值浮點速度

（2）Linpack基準測試程序

（3）Whetstone基準測試程序

3）SPEC基準程序（SPEC Benchmark）

4）TPC基準程序

低級語言和高級語言

編譯程序和解釋程序

程序設計語言的定義

程序設計語言的分類

1）程序設計語言發展概述

2）程序設計語言分類

（1）命令式和結構化程序設計語言

（2）面向對象的程序設計語言

（3）函數式程序設計語言

（4）邏輯型程序設計語言

程序設計語言的數據成分

1）常量和變量

2）全局量和局部量

3）數據類型

（1）基本類型

（2）特殊類型

（3）用戶定義類型

（4）構造類型

（5）指針類型

（6）抽象數據類型：類類型

程序設計語言的運算成分

程序設計語言的控制成分

1）順序控制

2）選擇控制

3）循環控制

4）C（C++）語言提供的控制語句

（1）復合語句

（2）if語句和switch語句

程序設計語言中的傳輸成分

函數

1）函數定義

2）函數聲明

3）函數調用

（1）值調用

（2）引用調用

匯編語言

1）指令語句

2）偽指令語句

3）宏指令語句

匯編程序

將源程序翻譯成機器指令程序

編譯過程概述

1）詞法分析

2）語法分析

3）語義分析

4）中間代碼生成

5）代碼優化

6）目標代碼生成

7）符號表管理

8）出錯處理

文法和語言的形式描述

1）字母表，字符串，字符串集合及運算

2）文法和語言的形式描述

（1）文法的定義

（2）文法的分類

（3）句子和語言

詞法分析

1）正規表達式和正規集

2）有限自動機

正規式與有限自動機之間的轉換

1）有限自動機轉換為正規式

2）正規式轉換為有限自動機

詞法分析器的構造

1）用正規式描述語言中的單詞構成規則

2）為每個正規式構造一個NFA，它識別正規式所表示的正規集

3）將構造處于的NFA轉換成等價的DFA

4）對DFA進行最小化處理，使其最簡

5）從DFA構造詞法分析器

詞法分析

1）上下文無關文法

2）自頂向下語法分析方法

3）自底向上語法分析方法

語法制導翻譯和中間代碼生成

1）中間代碼

2）常見語法結構的翻譯

3）動態存儲分配和過程調用的翻譯

中間代碼優化和目標代碼生成

1）中間代碼形式

2）目標代碼形式

3）寄存器的分配

4）計算次序的選擇

解釋程序的基本結構

高級語言編譯與解釋方式的比較

1）效率

2）靈活性

3）可移植性

線性表的定義

1）存在唯一的一個稱作“第一個”的元素

2）存在唯一的一個稱作“最后一個”的元素

3）除第一個元素外，序列中的每個元素均只有一個直接前驅

4）除最后一個元素外，序列中的每個元素均只有一個直接后驅

線性表的存儲結構

1）線性表的順序存儲

2）線性表的鏈式存儲

（1）單鏈表

（2）雙向鏈表

（3）循環鏈表

（4）靜態鏈表

棧

1）棧的定義及基本運算

（1）棧的定義

? 先進后出的線性表，只允許在表的一端插入和刪除元素

（2）棧的基本運算

? ①初始化棧InitialStack

? ②判斷空棧isEmpty

? ③入棧Push

? ④出棧Pop

棧的存儲結構

1）順序存儲

2）鏈式存儲

3）棧的應用

隊列

1）隊列的定義及基本運算

（1）隊列的定義

? 先進先出的線性表，只允許在表的一端插入元素，另一端刪除元素

（2）隊列的基本運算

? ①初始化隊列InitQueue

? ②判隊空isEmpty

? ③入隊EnQueue

? ④出隊DelQuene

? ⑤讀隊頭元素FrontQue

2）隊列的存儲結構

（1）隊列的順序存儲

（2）隊列的鏈式存儲

3）隊列的應用

串的定義及基本運算

1）串的定義

? 僅由字符構成的有限序列，是一種線性表

2）串的幾個基本概念

（1）空串

（2）空格串

（3）子串

（4）串相等

（5）串比較

3）串的基本操作

（1）賦值操作

（2）連接操作

（3）求串長

（4）串比較

（5）求子串

串的存儲結構

（1）串的順序存儲結構

（2）串的鏈式存儲

串的模式匹配

1）樸素的模式匹配算法（布魯特—福斯算法）

2）KMP算法

數組的定義及基本運算

1）數組的定義

2）數組的兩個基本運算

數組的順序存儲

廣義表的基本操作

1）取表頭

2）取表尾

廣義表的特點

1）廣義表可以是多層次的結構

2）廣義表中的元素可以是已經定義的廣義表的名字

3）廣義表可以是一個遞歸的表

廣義表的存儲結構

采用鏈式存儲結構

樹的定義

樹的基本概念

1）雙親，孩子和兄弟

2）結點的度

3）葉子結點

4）內部結點

5）結點的層次

6）樹的高度

7）有序（無序）樹

二叉樹的定義

二叉樹的性質

二叉樹的存儲結構

1）二叉樹的順序存儲結構

2）二叉樹的鏈式存儲結構