《計算機導論》復習

?考試范圍：1?8章

?考試題型：

-選擇、填空、判斷、問答、計算

?考試時帶鋼筆或珠筆，不準使用計算

o

1

第1章概述

?1936年，英國科學家阿蘭?圖靈提出圖靈機模

型：把人在計算時所做的工作分解成簡單的機

械化動作交給機器去執(zhí)行，經過足夠的時間和

有限次機械步驟求得解答。理論上可以計算任

何可計算函數(shù)。

?1946年2月由賓夕法尼亞大學研制成功的ENIAC

是第一臺電子數(shù)字計算機。

2

?美籍匈牙利數(shù)學家馮?諾依曼提出現(xiàn)代計

算機基本結構——“馮?諾依曼計算機”：

-計算機應由運算器、控制器、存儲器、

輸入設備和輸出設備五大部件組成；

-應采用二進制簡化機器的電路設計；

-采用“存儲程序”以便計算機能保存指令

和數(shù)據以及能夠自動依次執(zhí)行指令。

3

?第一代計算機：電子管；

?第二代計算機：晶體管；

?第三代計算機：集成電路；

?第四代計算機：大規(guī)模/超大集成電路

計算硬件發(fā)展的新趨勢——并行計算、連網

4

?第一代軟件：機器語言，匯編語言；

?第二代軟件：高級語言；

?第三代軟件：操作系統(tǒng)；

?第四代軟件：結構化程序設計方法，UNIX,C,

DOS,鼠標+圖形界面；

?第五代軟件：面向對象程序設計，Windows,

Java,WWW;

5

第2章計算機基礎知識

?數(shù)制：按進位原則進行計數(shù)）逢R進一。

基數(shù)：數(shù)制中所需的數(shù)字字符個數(shù)。R進制的基數(shù)=R

位權：是一個與數(shù)字位置有關的常數(shù)，位權=即

其中n取值：以小數(shù)點為界，向左0,1,2,3……,

向右T,-2,-3……

例：（275.8）I。=2x102+7xlO^Sx100+8x

6

二進制的算術運算

加：減：乘：除：

0+0=00-0=00X0=00+0=0

0+1=10-1=10X1=004^1=0

1+0=11-0=11X0=01+0（無意義）

1+1=01-1=01X1=11+1=1

二進制的邏輯運算

與AND：或OR：非（取反）:

0A0=00V0=0

0Al=0OV1=10=1

1AO=O1VO=1

1A1=11V1=11=0

十進制整數(shù)一二進制整數(shù)］I+進制小數(shù)=二進制小數(shù)

除2取余數(shù)直到商為0；乘2取整直到小數(shù)部分為0或

由下而上排列。達到精度；由上而下排列。

0.6875

2I751k

TX2

23711........1.3750

2|180X2

2I910........0.7500

2I40X2

2L201.........1.5000

X2

2

0........1.0000

結果為：1001011結果為：0.1011

二進制數(shù)口十進制數(shù)

\____________________________________________________________________________________7

位權相加法?,各位數(shù)碼乘位權，再相加。

321

例：(1011-1)2=1X2+OX2+1X2+1X2°+1X2-1

=8+0+2+1+0.5=(11,5)10

「一…出門整數(shù)部分從右向左，小數(shù)部分從左向右，

二進制數(shù)每3位二進制一組，變?yōu)?位八進制。

、1米不足3位時分別在最左端和最右端補。湊夠3位。

［八進制效J例:(1100101001011.1101)2=(14513.64)8

?整數(shù)部分從右向左，小數(shù)部分從左向右，

每4位二進制一組，變?yōu)?位十六進制。

不足4位時分別在最左端和最右端補0湊夠4位。

例:(11010111101.1010001)2=(6BD.A2)16

位(bit)：計算機存儲數(shù)據的最小單位(0、1)

字節(jié)(Byte)：處理數(shù)據的基本單位(8bit/Byte)

一個字(Word)由2、4或8個字節(jié)組成。

一個字的每一位由右至左編號。如32位字長:

31302524232270

0100011001001；-00110111

10

第三章數(shù)據表示法

?模擬信號和數(shù)字信號

?無符號數(shù)和有符號數(shù)

?符號位:二進制數(shù)的最高位表示“正”、

0為正，1為負。

11

為了運算方便，機器數(shù)采用原碼、補碼表示。

原碼:正號為0,負號為1,數(shù)值部分為二進制絕

對值。

補碼正數(shù)的補碼和原碼相同；負數(shù)的補碼是將

其原碼除符號位外各位取反，末位加1。

+5的原碼、未卜碼者口是00000101

-5

12

小數(shù)點位置固定的數(shù)稱為定點數(shù)。

定點整數(shù)：小數(shù)點固定在數(shù)值部分最右端。

定點小數(shù)：小數(shù)點固定在數(shù)值部分最左端。

小數(shù)點位置不固定的數(shù)稱為浮點數(shù)，分為階碼

(指數(shù))和尾數(shù)兩部分。

例：將十進制數(shù)+55以浮點數(shù)格式存放。

6

(55)10二(110111)2=0.110111*2

31302524232250

000001100

階碼階碼部分尾數(shù)尾數(shù)部分

符號位符號位

西文字符的編碼:

ASCII4馬(AmericanStandardCodeforInformationInterchange)

?128個常用字符，用7位二進制編碼，占一個字節(jié)，最高位0。

?其中，控制字符：。?32,127；普通字符：94個。

例如：“a”字符的編碼為1100001,對應的十進制數(shù)是97；

字符對應的十六進制對應的十進制

換行OAH10

回車ODH13

空格20H32

O?，9'30H-39H48?57

*?Z41H?5AH65?90

'a'?卬61H?7AH97?122

14

和漢字有關的編碼：

(1)漢字輸入碼：操作人員通過鍵盤輸入的漢字編碼。

(2)漢字國標碼(GB2312—80)

每個漢字占兩個字節(jié)的編碼。所有漢字分區(qū)，每個

區(qū)94個漢字。區(qū)號和位號各加32構成國標碼。

(3)機內碼

計算機內部存儲和加工漢字所用的編碼。

每個漢字的國標碼的每個字節(jié)最高位改為1,即成機內碼。

漢字國標碼漢字機內碼

中8680(0101011001010000)2010101100010000)2

華5942(0011101100101010)20)111011^101010)2

(4)漢字字形碼：點陣(漢字字形點陣的代碼)

15

差錯校驗碼一奇偶校驗碼

?為一個字節(jié)補充1bit（校驗位），設置校驗位的值

為。或1，使字節(jié)中的8bit和該校驗位含有1值的個數(shù)

為奇數(shù)（奇校驗）或偶數(shù)（偶校驗）。

數(shù)據前校驗編碼乂禺校驗編碼

00000000100000000o'00000000

01010100901010100101010100

可

16

文本壓縮方法:

關鍵字編碼，

關鍵字編碼是用單個字符代替常用單詞或前后綴。

如：the—~and->+that->$

行程長度編碼

在一些數(shù)據流中，某個字符可能連續(xù)地反復出現(xiàn)。

因此，重復字符序列被替換為：

標志字符+該字符+出現(xiàn)次數(shù)

17

文本壓縮方法:

哈夫曼編碼

1■計算信源符號出現(xiàn)的概率。p-0.125,a-0.25,

s-0.375,g-0,125,e-0,125

2.概率最小的兩個符號概率相加合成一個概率。

3,將合成概率看成一個新組合符號概率，重復上述

做法，直到最后只剩下兩個符號概率為止。

4.反過來逐步向前編碼，每一步有兩個分支各賦予

一個二進制碼，可以對概率大的編碼為1、,一,

18

■音頻信息的數(shù)字化：

■捕捉聲音時用固定的時間間隔對聲波進行采樣

（離散化處理），例如44.1kHz;（采樣）

■將每個采樣點的振幅值轉換為二進制數(shù)值，例

如用8位或16位二進制表示。（量化）

■把量化后的信號數(shù)據編成一個二進制碼組輸出。

（編碼）

?采樣頻率：每秒鐘的采樣次數(shù)。

?量化位數(shù)（采樣精度）：存放采樣點振幅值的二

進制位數(shù)。通常量化位數(shù)有8位、16位等。

19

■圖像信息的數(shù)字化：

■用“m行xn列”個像素點來離散化一幅圖像,

例如1024x768分辨率；（采樣）

■將每個像素點的三基色強度轉換為二進制值,

例如用8位、16位、24位、32位二進制表示。

（量化）

■數(shù)字化圖像的數(shù)據量很大，所以需要采用編

碼技術來壓縮信息，減少數(shù)據量。（編碼）

?分辨率：圖像中的行數(shù)和列數(shù)，每個行與列的

交點就是一個像素。例如1024X768、。

?顏色深度：每個像素點顏色值的存儲位數(shù)。

20

■視頻信息的數(shù)字化：

■連續(xù)動態(tài)的視頻由多幀靜態(tài)圖像組成。

■采樣頻率：每秒捕捉的畫面幀數(shù)。

■采樣精度：經采樣后每幀所包含的顏色位

（色彩值）。如8位,32位。

■必須對海量的視頻數(shù)據及其伴音進行壓縮

和編碼。

21

音頻文件常用格式

wma,wav,mp3mid

圖像文件常用格式

bmp,gif,jpgwmf

視頻文件常用格式

avi,mov,mpg,dat

22

第3章計算機體系結構

?門電路：接受一個或多個輸入信號，生

成一個輸出信號。每種類型的門執(zhí)行一

個特殊的邏輯函數(shù)。

?非門，與門，或門，異或門，與非門，

或非門等。

23

非門:

BooleanExpression邏輯框圖符號真值表

與門:

BooleanExpression邏輯框圖符號真值表

ABX=A*B

000

X=A*B010

100

111

24

或門:

BooleanExpression邏輯框圖符號真值表

A__ABX=A+B

v0|

X=A+B__A00

011

101

111

異或門：兩個輸入相同時，輸出是0,否則輸出1。

BooleanExpression邏輯框圖符號真值表

ABX=A十B

X=A十B000

011

101

110

25

與非門：讓與門的結果再經過一個非門。

BooleanExpressionLogicDiagramSymbolTruthTable

ABX

AA

X=(A-B)?001

B011

101

110

或非門：讓或門的結果再經過一個非門。

BooleanExpressionLogicDiagramSymbolTruthTable

AABX

X=(A+B)'001

B010

100

110

26

用晶體管構造門

否則Vout=1o極才不被接地，Vout=1o

27

“異或”邏輯表達式：X=A十B三A?B+A^

-28

半力口器halfadder：

計算兩個數(shù)位的和并生成正確進位的電路。

A和

B十和二A十B

進位二

進位AB

&

29

全力口器fulladder：

計算兩個數(shù)位的和并考慮進位輸入的電路。

和二A十B十C

進位輸出=AB+5人十田

進位輸出、

30

加法器adder：8bit相加需要復制8次全加器電路。

一個bit位的進位輸出將作為下一個bit位的進位輸入o

最右邊bit的進位輸入是0,最左邊bit的進位輸出被

舍棄（溢出）。

Co

S3S2S1So

位加法器例子

S=A+B4

S3s2&S。=WH/i/o+8332g8o

31

5飛鎖存器6飛latch)

S=0,R=1時，X=1o

R=0,S=1時，X=0o

S=1,R=1時，X保持不變。

和不能同時為。

清。端SR0

32

內存單元：存儲信息的單位（字節(jié)）。內存中有大量的

內存單元。

內存單元的地址：每個內存單元都有唯一的地址。

33

?CPU的主要性能指標：

主頻：CPU內核運算電路的運行頻率。

CPU外頻：CPU總線頻率，外頻提高則與內存交

換數(shù)據的速度越快。主頻=外頻X倍頻系數(shù)。

數(shù)據總線寬度：即字長，如32位、64位。

CPU：算術和邏輯運算單元ALU、

控制器和寄存器組。

CPU可執(zhí)行的一組指令稱為指令集。

精簡指令集和復雜指令集。一

34

、一口口

運舁肅

ALU:執(zhí)行算術、邏輯運算

寄存器組：存源、中間數(shù)據

標志寄存器：保存標志信息

控制器

Be：口存放下一條指令的地址

IR：存放正執(zhí)行指令的內容

譯碼器：區(qū)分指令執(zhí)行的步驟

產生控制信號：向其它各部件發(fā)出控制信號，

保證各部件協(xié)調一致地工作

35

總線按所傳輸?shù)膬热莘郑校?/p>

數(shù)據總線：傳送數(shù)據。如：“奔騰”CPU有32條數(shù)

據線，表示每次可和內存并行交換32位二進制數(shù)。

地址總線：用于傳送CPU發(fā)出的地址信息,即指明

數(shù)據總線上的數(shù)據的源地址或目的地址。地址總線的

寬度決定了CPU的最大尋址能力（即所允許的最大內

存容量）。

控制在線＞傳送控制信號。

36

操作碼：要完成的操作類型

操作數(shù)：操作數(shù)所在的地址或操作數(shù)本身

例：JMPM1;ADDREG1REG2

37

內存：直接與CPU交換信息的存儲設備。用來存放計

算機運行期間所需的信息，如：指令、程序、文檔。

外存：內存的延伸，長期存放暫時不用的數(shù)據。如

系統(tǒng)文件、應用程序、用戶文檔等。

I-----鄢態(tài)RAM

隨機存儲器(RAM)-

1----動態(tài)RAM(DRAM)

內存儲器

住存）I-掩膜ROM

只讀存信器(ROM)——PROM

?——EPROM

存儲器

順序存取存儲器磁帶

外存儲器

（輔存）

直接存取存儲器軟盤、硬盤、光盤

高速緩沖存儲器（Cache）

38

非vonNeumann結構：

不采用“線性的讀取一執(zhí)行周期”。

并行（分布式）處理

?陣列計算機：多個處理機對不同數(shù)據同時運行

相同指令。

?多指令流多數(shù)據流MIMD系統(tǒng)：多個處理機對不

同數(shù)據執(zhí)行不同指令。

39

流水線技術(Pipeline)

?將每條指令分解成多個階段，幾條指令的不同階段

重疊運行，使控制器、運算器、存儲器等同時工作。

?如Pentium的6級流水線結構：

指令1取指譯碼地址生成取數(shù)執(zhí)行寫回

指令2取指譯碼地址生成取數(shù)執(zhí)行寫回

指令3取指譯碼地址生成取數(shù)執(zhí)行寫回

指令4取指譯碼地址生成取數(shù)執(zhí)行寫回

40

第4章操作系統(tǒng)

用戶1用戶2用戶3……用戶n

編譯程序匯編程序文本編輯器…數(shù)據庫系統(tǒng)

系統(tǒng)程序和應用程序

——操作系統(tǒng)-----

計算機硬件

操作系統(tǒng)：計算機硬件和軟件資源的管理者。

41

操作系統(tǒng)構成：進程管理、內存管理、文件管理、

輸入輸出系統(tǒng)管理，作業(yè)管理。

操作系統(tǒng)主要類別：

11批處理系統(tǒng)

31實時系統(tǒng)

42

分時操作系統(tǒng)：

?“分時”的含義：時間片輪轉，輪流占用CPU

?人機交互性好：程序的運行由用戶自己操作。

?共享主機：多個用戶同時使用同一臺計算機。

?對每個用戶而言好象獨占主機。

實時操作系統(tǒng)：

?及時響應外部事件的請求，在規(guī)定的嚴格時間內完

成對該事件的處理。

-要求：及時響應、快速處理，高可靠性和安全性

?應用領域：過程控制、事務處理。

43

內存分配方案-連續(xù)內存分配

在可用內存中找到足夠大的一塊連續(xù)內存（如100KB）,

切出要求長度的內存（如70KB）分配，剩余內存（如

30KB）作為新空閑區(qū)留待以后分配或合并。

?首次適應（First-fit）策略

?最佳適應（Best-fit）策略

?最差適應（Worstf。策略

內存分配方案-分頁式內存管理

為解決碎片問題和實現(xiàn)不連續(xù)分配，采用頁式管理。

44

虛擬內存：

當一個用戶程序要調入內存運行時，不是將該

程序的所有頁面都裝入內存，而是只裝入部分

的頁面，就可啟動程序運行；

在運行的過程中，如果發(fā)現(xiàn)要運行的程序或要

訪問數(shù)據不在內存，則向系統(tǒng)發(fā)出缺頁中斷請

求；

系統(tǒng)在處理這個中斷時，將磁盤上相應的頁面

調入內存，使得該程序能夠繼續(xù)運行。

45

進程是程序對某個數(shù)據集的一次執(zhí)行過程。

?:?程序是靜態(tài)概念（建立與刪除）；進程是動態(tài)概念。

一個進程由三部分組成：

?進程控制塊PCB,程序段，數(shù)據集

46

◎CPU調度：把CPU分配給某個就緒進程去運行。

◎不可搶占式：當前運行進程完成或阻塞或時間片

到時，才再分配處理機。

◎搶占式：將正運行進程強行撤下，處理機分配給

其它進程。例如當有一個優(yōu)先權更高的進程進入就緒

隊列時。

?先到先服務(FCFS,First-Come,First-Served)

?最短作業(yè)優(yōu)先(SJF,Shortest-Job-First)

?輪轉(RR,Round-Robin)：時間片輪轉

47

文件系統(tǒng)和目錄

文件：存儲在外存上具有標識名的一組相關字

符流或記錄的集合。透明存放和按名存取

文件的命名：文件名.擴展名

，布.:七

48

■OS將每個目錄看成一張表，表中是該目錄下所有

文件的信息。（其實目錄本身也是一個文件）

■創(chuàng)建文件時，先在磁盤上為新文件分配一個空閑

塊，然后在目錄表中添加一新條目。

文件名權限建立時間文件長度第一磁盤塊號盤塊數(shù)其它

myOl.c1101605092268B565722

abc.exe001230000220324B356364

q123.doc110322083156342B4585715

■■■■■■■■■■■■■■■■■■■■■■■■.....................■■■■■■

xyz.txt11192210012B243411

49

從開始位置順序讀取字

符/記錄，適合于磁帶

訪問方式

UNIX中的文件存取權限：

?:?用戶分三類：文件主、同組用戶、其他用戶。

?:?權限有三種：讀R、寫W、執(zhí)行X。

50

■磁盤調度：當多個進程都提出“磁盤訪問請求”

時，需要對訪盤請求的服務順序進行調整，以降

低平均磁盤訪問時間。

■FCFS先來先服務：按請求的次序服務。

■SSTF最短尋道時間優(yōu)先：優(yōu)先選擇距當前磁

頭位置最近的訪問請求進行服務。

■SCAN掃描算法（電梯算法）：選擇位于磁頭移動方

向前方且距磁頭位置最近的訪問請求進行服務。

51

第5章網絡計算

?計算機網絡是一種利用通信線路和通信

設備，把分布在不同地點的多個獨立的

計算機系統(tǒng)有機地連接起來，實現(xiàn)所連

接的計算機之間互相通信和資源共享的

計算機系統(tǒng)。

52

＞帶寬：網絡上數(shù)據傳輸?shù)乃俾剩瑔挝籦it/s。

，網絡分類：局域網，城域網，廣域網

＞拓撲結構：總線型，星型，環(huán)型

OSI網絡體系結構參考模型

?應用層(AppIicationLayer)

?表示層(PresentationLayer)

?會話層(SessionLayer)

?傳輸層(TransportLayer)

?網絡層(NetworkLayer)

?數(shù)據鏈路層(DataLinkLayer)

?物理層(PhysicaILayer)

53

,每段占1個字節(jié)，取值0—255

IP地址格式nnn.nnn.nnn.nnn

如202.112.0.36

A類

B類

C類

54

IP地址

3

域名

WWW.

t-t-V

主機名機構域領域國家域

DNS（域名服務器）：完成域名向IP地址的轉換。

頂級域名分類：

類型名：如edu,gov,org,cn等。

區(qū)域名：如cn'uk/hk等。

55

Internet的典型應用

?電子郵件E-MaiL文件傳輸FTP,遠程登錄

Telnet,全球信息網WWW,電子公告板BBS,

實時聊天ICQ,網絡電話IPPhone

產茅—

56

第6章程序設計與算法分析

?:?計算機問題求解三階段：不斷反復的過程

?:?算法開發(fā)：得到問題的通用解決方案

?分析問題、提出并測試算法

?:?算法實現(xiàn)：得到計算機可運行的程序

?編碼和測試程序

?:?維護：在實踐中檢驗

?實際運轉、修改維護程序‘百

57

?:?兩種程序設計方法：

4?自頂向下方法(Top-downMethodology)

?程序設計模式：“數(shù)據結構+算法”

士在軟件功能說明書中，動詞是重點。

?:?面向對象程序設計(ObjectOriented

Programming)

?程序設計模式：“對象+消息”

+在軟件功能說明書中，名詞是重點。

58

自頂向下程序設計方法

①自頂向下、逐步求精：逐層分解復雜任務，把任務

細節(jié)推延到下層模塊中實現(xiàn)。

②模塊化：每個模塊完成特定的、相對簡單的功能。

③流程控制結構化：程序通過順序、分支、循環(huán)三種

基本控制結構來實現(xiàn)。

59

面向對象的程序設計方法

60

*繼承inheritance：子類得到父類的全部屬性和方法,

還可以擴充和覆蓋父類的成員。

*多態(tài)polymorphism：也稱重載。不同子類中同一方

法名可定義成不同代碼，所以它們在收到同一消息

時做出的響應行為也不同。

*封裝encapsulation：將屬性和行為隱藏起來，外部

通過特定的接口訪問對象成員。好處是保護成員，

修改程序時只涉及類的內部。

61

低級程序設計語言

機器語言：由二進制代碼組成。能被計算機直接

理解和執(zhí)行，但編程困難，可移植性差。

把機器指令中的操作碼和操作數(shù)用英文助記符和

符號地址來表示，稱為匯編語言。依賴于機器，

可移植性同樣較差。

62

高級程序設計語言

?編譯器對整個源程序經過編譯處理，產生一個與源

程序等價的目標程序；通過連接程序將目標程序和

有關的程序庫組合成一個完整的可執(zhí)行程序；

?執(zhí)行速度快，修改源程序后都必須重新編譯。同一

種高級語言在不同CPU平臺上需要不同的編譯器。

編譯器連接程序數(shù)據

源程序―L目標程序―L可執(zhí)行程序！—,運行

.C.obj.exe結巢

63

?解釋程序對源程序進行逐句分析，若沒有錯誤,

將該語句翻譯成一個或多個機器語言指令，然后

立即執(zhí)行這些指令；若解釋時發(fā)現(xiàn)錯誤，則立即

停止，報錯并提醒用戶更正代碼。

?解釋方式不生成目標程序，執(zhí)行速度慢。

解釋程序

高級語言

計算結果

源程序

據

64

?Java源程序先經過編譯生成Java字節(jié)碼，然后由

JVM(JavaVirtualMachine,Java虛擬機)解釋執(zhí)行。

?Java字節(jié)碼相當于是“標準的機器語言”，速度快,

唯一，只要有相應的JV