計算機科學技術導論復習材料

計算機科學技術導論復習材料

計算機科學技術的基礎知識

1.計算機的定義：

計算機是一種能按照事先存儲的程序，自動、高速地進行大量數(shù)

值計算和各種信息處理的現(xiàn)代化智能電子設備。

1.1計算機系統(tǒng)的組成

計算機系統(tǒng)由計算機硬件和計算機軟件組成。

計算機軟件：應用軟件-一辦公自動化軟件、財務管理軟件等

系統(tǒng)軟件一-操作系統(tǒng)、編譯系統(tǒng)、解釋系統(tǒng)、數(shù)

據(jù)庫管理系統(tǒng)等

計算機硬件：CPU、存儲器、各種輸入輸出設備

1.2計算機的發(fā)展

1946年美國賓西法尼亞大學研制世界上第一臺電子數(shù)字計算機

ENIACo

第一代計算機-電子管

第二代計算機-晶體管

第三代計算機-集成電路

第四代計算機-大規(guī)模與超大規(guī)模集成電路

1.3計算機的分類

1.按計算機處理數(shù)據(jù)的方式分類-數(shù)字計算機、模擬計算機

2.按計算機的用途分類-通用計算機和專用計算機

3.按計算機的規(guī)模和處理能力分類-巨型計算機、大/中型計算機、

小型計算機、微型計算機、工作站、服務器以及網(wǎng)絡計算機

1.4計算機的用途

1.科學計算-數(shù)值計算

2.數(shù)據(jù)處理-對數(shù)據(jù)輸入、分類、加工、統(tǒng)計、排序、傳輸、檢索、

存儲、制表等操作

3.過程控制-計算機及時采集數(shù)據(jù)，將數(shù)據(jù)檢測、處理后，按最佳值

迅速對控制對象進行自動控制或自動調(diào)節(jié)

4.計算機輔助系統(tǒng)-計算機輔助設計（CAD）、計算機輔助制造（CAM）、

計算機輔助教育（CAI）

5.人工智能-計算機模擬或部分模擬人類的智能,進行演繹推理和采

取決策的思維過程

6.電子商務-計算機和網(wǎng)絡進行商務活動

2.計算機的運算基礎：

2.1常用的數(shù)制

十進制（數(shù)字后加D表示）、二進制（數(shù)字后加B表示）、八進制（數(shù)

字后加Q表示）和十六進制（數(shù)字后加11表示）

任何一個R進制數(shù)N：

N=anatl-i???..aia,a-ia-m

均可表示為按權展開式形式；

N—a”a，n-i***..a，ia。,a-】...a.-m

n,rl1

二ariXR+an-!XR+???+a】XR+a0XR°

+aiXR1++a』XR"

二進制數(shù)，向右移一位（最高位補個零），數(shù)值就縮小1倍，反之,

向左移一位（最低位補個零），數(shù)值就擴大1倍。如

00000100（4）——》右移一位：00000010（2）

八進制數(shù)，用0,1,2,3,4,5,6,7八個數(shù)碼表示數(shù)值，采

用“逢八進一”計數(shù)原則。

十六進制數(shù)，用0,1,2,3,4,5,6,7,8,9,A,B,C,D,

E,F十六個數(shù)碼表示數(shù)值，采用“逢十六進一”計數(shù)原則。

2.2各種數(shù)制間相互轉(zhuǎn)換

一、非十進制轉(zhuǎn)換為十進制--“位權展開法”

1）二進制數(shù)1011101.1001轉(zhuǎn)換成十進制數(shù)

（1011101.1001）2=1X26+0X25+1X24+1X23+1X22+0

義241X2°+1X2-1+0X2/0X2-3+1X2-4

=64+16+8+4+1+0.5+0.0625

二（93.5625）10

2）八進制數(shù)763.24轉(zhuǎn)換成十進制數(shù)

(763.24)2=7X82+6X81+3X8°+2X8-1+4X8-2

二448+48+3+0.25+0.0625

二(499.3125)10

3)十六進制數(shù)B2F轉(zhuǎn)換成十進制數(shù)

(B2F)16=BX162+2X161+FX160

21C

二11X16+2X16+15X16

二2816+32+15=(2863)10

二、十進制轉(zhuǎn)換為非十進制--“求余法”（整數(shù)）或“得整數(shù)法”（小

數(shù)）

（A）整數(shù)

1）十進制整數(shù)125轉(zhuǎn)換成對應的二進制整數(shù)

2125余數(shù)

2-621

21310

2151

271

2|31

2|21

01

則得：（125）10=（1111101）2

2）十進制整數(shù)125轉(zhuǎn)換成對應的八進制整數(shù)

8125余數(shù)

8155八

817

""o-1

則得：(125)10=(175)8

3）十進制整數(shù)125轉(zhuǎn)換成對應的十六進制整數(shù)

余數(shù)

13A(D)

7

則得：(125)10=(7D)16

(5FD4.A3)16=0101111111010100.10100011

則得：(5FD4.A3)16=(101111111010100.10100011)2

2.3碼制

1)數(shù)據(jù)分類:數(shù)值型和非數(shù)值型

☆數(shù)值型

A.正、負號的計算機內(nèi)部表示

符號位：數(shù)值型數(shù)據(jù)的最高位用來表示數(shù)值的正負，用“0”表示

“十”號，用“1”表示“-”號

B.碼制表示

計算機中機器數(shù)可用不同碼制表示，常用碼制有原碼、反碼和補

碼表示法

原碼表示法：

最高位：真值符號(正為3負為1)

其余n-1位：為數(shù)值位且與真值的數(shù)值位相同

數(shù)X的原碼記為［X］原、原碼表示數(shù)的范圍與機器字長有關

機器字長八位:范圍為-127?+127。即最小數(shù)是11111111,

最大數(shù)是01111111

機器字長十六位：范圍為-32767?+32767

反碼表示法：

正數(shù)：反碼和原碼相同

負數(shù)：反碼是對該數(shù)的原碼除符號位外各位取反，即“0”變“1”，

“1”變“0"。數(shù)X的反碼記為反］反

如:機器字長8位，二進制數(shù)+1011011和-1011011的反碼分別

表示為01011011和10100100

補碼表示法：

正數(shù)：補碼和原碼相同

負數(shù)：補碼是對該數(shù)的原碼除符號位外各位取反，最末位加1。即:

反碼加I。數(shù)X的補碼記為［X］補

如：機器字長8位，二進制數(shù)字011011和-1011011的補碼分別表示

為01011011和10100101

表示數(shù)范圍：

與二進制數(shù)的位數(shù)(即機器字長)有關，用八位二進制數(shù)表示時,

最高位為符號位，整數(shù)補碼表示的范圍為-128?+127。用十六位

二進制數(shù)表示整數(shù)補碼時，范圍為-32768?+32767

C.溢出判斷

無符號數(shù)的溢出判斷：無符號數(shù)是指定義的數(shù)沒有負數(shù)，即全部是正

數(shù)，最高位是數(shù)值位，不是符號位。當字長為8位時，若兩個無符號

數(shù)運算，結果超過了字長，稱為無符號數(shù)溢出。

如：mi1100(>0)

+0010oooo(>0)

=1OOPIHOO(超過8位字長)

有符號數(shù)的判斷:有符號數(shù)是指最高位為符號位,即可能是正數(shù)或負

數(shù)，當兩個有符號數(shù)運算時，結果不正確(超過了規(guī)定字長所表示的

有符號數(shù)范圍)，稱為有符號數(shù)溢出。

如：01111100(>0)

+01000000(>0)

=10111100?0,錯誤)

解決辦法：(如,采用雙符號位)

如：001111100(>0)

+001000000(>0)

=010111100(>0,正確)

D.定點數(shù)與浮點數(shù)

(1)定點數(shù)表示法

小數(shù)點位置：隱含表示

定點整數(shù)：小數(shù)點隱含固定在整個數(shù)值的最右端，符號位右邊所有

的位數(shù)表示的是一個純整數(shù)。計算機中格式表示如下：

數(shù)值位

符號位隱含小數(shù)點位置

定點小數(shù)：小數(shù)點隱含固定在最高數(shù)值位的左邊，符號位右邊，參

與運算的數(shù)是純小數(shù)。計算機中格式表示如下：

數(shù)值位

隱含小數(shù)點位置

符號位

(2)浮點數(shù)表示法

浮點數(shù)分成階碼和尾數(shù)兩部分來表示,.其中階碼一般用補碼定點

整數(shù)表示，階碼用了表示該數(shù)的小數(shù)點位置，尾數(shù)一般用補碼或原碼

定點小數(shù)表示。

字長給定的情況下：

階碼的位數(shù)越多：表示數(shù)范圍變大，但尾數(shù)的位數(shù)減少，數(shù)的精度

降低。

階碼的位數(shù)減少：數(shù)的表示范圍變小，但尾數(shù)的位數(shù)增加，數(shù)的精

度提高。

階符階碼尾符尾數(shù)

<_______指數(shù)部分__________>._尾數(shù)部分__________>1

☆非數(shù)值型

1.ASCII碼

字符是計算機使用最多的非數(shù)值型數(shù)據(jù)。ASCII碼常用7位二進

制進行編碼，共可表示27=128個字符。ASCII碼的最高位b7（最

低位為bO）常作為奇偶校驗位。所謂奇偶校驗，是指代碼傳送過程

中用來檢驗是否出現(xiàn)錯誤的一種方法，分奇校驗和偶校驗兩種。

常見字符Ascn碼:'A'=41H,'B',…等依次加一即得。

'a'=61H,'b',…等依次加一即得。

'O'=30H,T',…等依次加一即得。

根據(jù)漢字使用頻率的高低、構詞能力強弱、實際用途的大小劃分

為兩級漢字，一級漢字3755個，一級漢字3008個。

漢字輸入碼：方便人工通過輸入設備輸入漢字而設計。如：區(qū)位碼、

智能ABC碼、五筆字型碼。

國標碼：用于漢字信息處理系統(tǒng)之間或通信系統(tǒng)之間進行信息交

換，國標GB2312-80制定了漢字交換碼的標準。國標碼任何一個漢字

或圖形符號都用兩個7位的二進制數(shù)表示，計算機中用兩個字節(jié)表

示，每個字節(jié)的最高位為0,剩余7位為GB2312-80二進制編碼c

機內(nèi)碼：供計算機系統(tǒng)內(nèi)部進行漢字存儲、加工處理、傳輸統(tǒng)一

使用的代碼。俗稱變形國標碼。

其中：機內(nèi)碼二國標碼+8080H國標碼二區(qū)位碼+2020H

3.邏輯代數(shù)與邏輯電路基礎：

1847英國數(shù)學家喬治?布爾創(chuàng)立邏輯代數(shù)，所以又叫布爾代數(shù)

邏輯代數(shù)與普通代數(shù)有本質(zhì)的區(qū)別，邏輯代數(shù)表示的不是數(shù)量大小之

間的關系，而且邏輯關系，邏輯代數(shù)中的。和1,不是數(shù)量的0和1,

它只代表所要研究問題的兩種可能性或兩種穩(wěn)定的物理狀態(tài)。

1.邏輯變量和邏輯函數(shù)

邏輯電路具有輸入和輸出間的邏輯關系，為了對輸入和輸出間的

邏輯關系進行數(shù)學表達和演算，所以提出了邏輯變量和邏輯函數(shù)兩個

術語。

一個邏輯電路如下圖所示，A,B為輸入，F(xiàn)為輸出，輸入和輸出

之間的邏輯關系為F=f(A,B)o

A[

BF=f(A,B)F

A,B,F為邏輯變量

F二(A,B)為邏輯函數(shù)

邏輯變量和邏輯函數(shù)的邏輯取值，只取兩個值0和1,通常稱

為邏輯0和邏輯1。

2.邏輯運算

基本運算:邏輯與、邏輯或、邏輯非和異或運算。

邏輯與：

oooo與

=0

o-oo與

-1等于0

oo與

-0等于0

-與

-1等于1

邏輯或：

0+0=00或0等于0

0+1=1?；?等于1

1+0=11或0等于1

1+1=11或1等于1

邏輯非運算

0二1非0等于1；1=0非1等于0

異或運算

0十0=00同0異或，結果為0

0十1=10同1異或，結果為1

1?0=11同0異或，結果為1

1?1=01同1異或，結果為0

3.邏輯電路基礎

能實現(xiàn)邏輯運算的電路稱為邏輯門電路(簡稱門電路)，常用的

門電路有“與”門、“或”門、“非”門、“與非”門、“或非”門、

“異或”門等。由基本門電路按邏輯設計可以組合成計算機硬件的基

本功能電路。

(A)門電路符號

“與”門

A

______&F二AB

B

“或”門

A

B

也可表示為:

A

B

“非”門

“異或”門

A

B

也可表示為:

A

B

其他的“與非”門、“或非”門等、只要和非門一樣，方框后面

加圓圈即可。

(B)邏輯組合電路的分析與設計

邏輯組合電路設計的步驟如下：

①描述邏輯電路應具備的邏輯功能

②構造真值表

③寫邏輯函數(shù)表達式

④根據(jù)簡化的邏輯函數(shù)表達式畫邏輯圖

例：設計三人表決電路（A、B、C）。每人一個按鍵，如果同意則按下,

不同意則不按。結果用指示燈表示，多數(shù)同意時指示燈亮，否則不亮。

1.首先指明邏輯符號取“0”、“1”的含義

三個按鍵A、B、C按下時為“1”，不按時為“0”。輸出是F,多

數(shù)贊成時是數(shù)”,否則是數(shù)”。

2.根據(jù)題意列出真值表真值表

3.應用邏輯代數(shù)法則化簡ABCF

Y=ABC+ABC+ABC+ABC0000

0010

=(ABC+ABC)+(ABC+ABC)-}-(ABC+ABC)0100

=AB+AC+BC0111

1000

(這里Y=F,C+C^l)

1011

1101

4.根據(jù)邏輯表達式畫出邏輯圖1111

⑴若用與或門實現(xiàn)

EFF

若用與非門實現(xiàn)

F=AB+BC+CA

=AB+BC+CA=ABBCCA

4.計算機的基本結構和工作原理

4.1計算機硬件的基本結構

美國數(shù)學家馮?諾依曼提出：計算機由五個基本部分組成：運算

器、控制器、存儲器、輸入設備、輸出設備。描述了：五大部分的

功能及其相互關系。提出了：“采用二進制”和“存儲程序”兩個

重要基本思想。

(a)“采用二進制”一一計算機中的數(shù)據(jù)和指令均以二進制形式存

儲和處理；

(b)“存儲程序”將程序事先存入存儲器，計算機工作時自

動從存儲器讀取指令、分析后執(zhí)行。

1.運算器

在控制器控制下執(zhí)行程序中指令，完成各種算術和邏輯運算，

包括:算術邏輯單元(ALU)和寄存器。

(a)ALU:力口、減、乘、除等四則運算

與、或、非、移位等邏輯運算

(b)寄存器：暫存參加運算的操作數(shù)或運算結果。

2.控制器

指揮整個計算機的各個部件按照指令的功能要求協(xié)調(diào)工作。

組成：

(a)程序計數(shù)器(PC):存放將執(zhí)行指令在內(nèi)存儲器中的存儲地址

(b)指令寄存器(IR):暫時保存正在執(zhí)行的指令

(c)指令譯碼器(ID):譯碼指令操作碼，識別指令進行的操作

(d)時序電路：生成時序信號，協(xié)調(diào)指令執(zhí)行周期部件工作

(e)微操作控制電路：產(chǎn)生各種控制操作命令

控制器和運算器合在一起，即CPU。

3.存儲器

計算機記憶和存儲部件，存儲數(shù)據(jù)和程序。

?按功能分為內(nèi)存儲器和外存儲器

(1)內(nèi)存儲器(簡稱內(nèi)存)

作用：也稱主存儲器(簡稱主存)，存放運行程序的指令和數(shù)據(jù)。

組成：半導體存儲器組成。

特點：直接與CPU交換信息，存取速度快，容量較小，價格相對

外存高等。

內(nèi)存分類：

存取方式分：隨機訪問存儲器(RAM)和只讀存儲器(ROM)

(a)RAM：讀寫存儲器，存放正在執(zhí)行的程序及所需數(shù)據(jù)。存取

速度快，但只臨時存儲信息，即：加電，記憶信息;斷電，RAM中信息

丟失。

(b)ROM：只能讀出而不能重新寫入，信息是制作時專門儀器寫

入。斷電，信息不丟失。ROM常用來存放一些專用程序、數(shù)據(jù)和系

統(tǒng)配置。如磁盤引導程序、自檢程序、1/（）驅(qū)動程序等。

（2）外存儲器（簡稱外存）

又稱輔助存儲器，是內(nèi)存擴充。

特點：存儲容量大、價格低、但存取速度較慢，不能與CPU直

接交換信息等。

作言:一般存放需要長期保存、暫時不用的程序、數(shù)據(jù)和結果,

需要時可成批和內(nèi)存信息交換。

常用外存：磁盤（軟盤、硬盤）、光盤、磁帶等。

外存容量：KB、MB、GB、TB表示。

4.2程序設計基礎

☆計算機程序：有序指令的集合或具有一定結構的語句集合。

☆程序設計大致需三步：

①確定算法與數(shù)據(jù)結構；

②用流程圖表示程序思想；

③用程序設計語言編制計算機程序。

☆程序設計方法：

結構化程序設計和面向?qū)ο蟪绦蛟O計

（1）結構化程序設計

特點：

荷蘭學者Dijkstra70年代提出，主要思想是自頂向下、逐步求

精、模塊編程。結構化程序設計采用單入口單出口控制結構，即：順

序、選擇、循環(huán)。任何算法都可用這三種基本結構實現(xiàn)，任何復雜的

程序都可分解為由三種基木結構組成。

（2）面向?qū)ο蟮某绦蛟O計

特點:

對費數(shù)據(jù)和處理數(shù)據(jù)的過程（函數(shù)或方法）形成整體。

對象的重復使用程序建立了對象，其他程序員可在其他程序使

用這個對象，不必重新編制。節(jié)省開發(fā)時間，提高軟件開發(fā)效率。

三個特性封裝性、繼承性和多態(tài)性

封裝性：把數(shù)據(jù)結構同操作數(shù)據(jù)的過程組合在一起，封裝在一個

類中。封裝性能保護類中的數(shù)據(jù)與過程的安全，防止外

界干擾和誤用。

繼承性：符合人的思維，通過繼承，一個對象可獲得另一個對象

的屬性，并可加入一些屬于自己的特性。

多態(tài)性：就是一個接口，多種方式。優(yōu)點在于通過提供一個相同

的接口，可通過不同的動作來訪問，降低了問題的復雜

度。

ClassHuman{〃父類

Inicurl;（屬性：身份證號）

Intsex;（屬性：性別）

sleepO{（函數(shù)或方法，睡眠）

…}

}

ClassStudentextendsHuman{〃子類，父類是Human

PrivateIntsno;（屬性：學號）

PrivateInteno;（屬性：課程編號）

PrivateIntscore;（屬性：課程分數(shù)）

PrivateGetscoreO{（函數(shù)或方法，得到課程分數(shù)）

…}

PrivateDispscoreO{（函數(shù)或方法，顯示課程分數(shù)）

…}

PrivateSetscore（）{（函數(shù)或方法，設置課程分數(shù)）

…}

run（inti）{（函數(shù)或方法，跑步，i表示圈數(shù)）

…}

run（datad）{（函數(shù)或方法，跑步，d表示日期）

…}

）

//上面的屬性和方法封裝的很好，只在Student中使用，當然，程

序設計中，可給予更多的靈活性設置，如是否允許外面訪問等。

//子類繼承了父類中的屬性和方法，即Student有身份證號、性

別等屬性，也繼承了父類的方法sleep。

//Student有兩個方法run,但具體實施的動作不同，得到的結果

也不同，即具有多態(tài)性。

//對象定義：

Studentsi,s2,s3,???;〃基于類，定義多個對象si,s2,s3,???

☆程序設計語言

分機器語言、晟語言、高級語言、面向?qū)ο笳Z言等

1.機器語言

(a)計算機第一代語言，由0、1構成的機器指令(構成:操作碼，地

址碼)集合。

(b)最底層、能直接被機器接受。

(c)計算機硬件可宜接識別，執(zhí)行速度快。

(d)不同CPU,機器語言也不同。

(e)不易記憶，編寫難度大，不易移植，是面向機器的程序設計語言。

2.匯編語言

(a)第二代程序設il?語言。

(b)機器語言“符號化”，助記符代替操作碼，地址符代替地址碼。

(c)面向機器的語言。程序執(zhí)行效率較高，通用性與可移植性較差。

(d)計算機不能直接識別用匯編語言編寫的程序，須由專門翻譯程序

將匯編語言程序翻譯成機器語言，計算機才能執(zhí)行。

3高級語言

(a)面向問題的程序設計語言。

(b)與計算機硬件無關，表達方式接近于被描述問題，接近自然語言

和數(shù)學語言，易接受和掌握。通用性和可移植性好。

(c)編寫的源程序不能直接執(zhí)行，執(zhí)行前，須由編譯程序或解釋程序

翻譯成機器能接受的目標代碼。編寫的程序,執(zhí)行時間和空間效率差。

☆算法與數(shù)據(jù)結構

A)軟件系統(tǒng)開發(fā)，遵循幾個步驟：

1.分析問題，確定算法

分析解決的問題，提取操作對象，找出操作對象間關系。

確定具體解決問題方法和步驟，設計出優(yōu)化算法。

2.選擇程序設計語言進行程序設計

算法轉(zhuǎn)換成程序代碼。程序常定義：

程序二算法+數(shù)據(jù)結構+程序設計語言+工具和環(huán)境

3.程序測試

設計一組測試數(shù)據(jù)，使用這組測試數(shù)據(jù)運行程序。

B)算法

算法的定義：是解題的步驟，是一組有窮的規(guī)則，規(guī)定了解決某一特

定問題的一系列運算，是對解題方案的準確與完整的描述。

具有的特性：

早確定性(給定輸入，輸出確定。同一輸入，兩次運行，結果相同)

早有窮性(算法的執(zhí)行過程總是要結束的)

孕可行性(算法總是可以實現(xiàn)的)

早輸入和輸出。

0數(shù)據(jù)結構

數(shù)據(jù)元素：數(shù)據(jù)集合中的一個個體，是數(shù)據(jù)的基本單位。

數(shù)據(jù)結構：相互間存在某種關系的數(shù)據(jù)元素集合。

幾種典型的數(shù)據(jù)結構：

多線性表

定義：由n(n20)個數(shù)據(jù)元素(結點)a1,a2,……an組成的

有限序列。不同線性表中的數(shù)據(jù)元素可是各種各樣，但同一線性表中

的元素必是同一類型的數(shù)據(jù)對象。

存儲結構：順序存儲和鏈式存儲結構

順序存儲：數(shù)據(jù)元素按次序依次存放在一組地址連續(xù)的存儲單元里。

設：線性表的每個元素占用C個存儲單元

設：表中開始第一個元素al的存儲地址是Loc(al)

那么：線性表的第i個數(shù)據(jù)元素ai的存儲地址

Loc(ai)=Loc(al)+(i-l)*C1WiWn

確定起始位置，任一數(shù)據(jù)元素都可隨機存取，所以線性表的順序

存儲是一種隨機存取的存儲結構。

優(yōu)點:可隨機存取表中任一結點，實現(xiàn)對線性表的某些操作比較簡單,

如：計算線性表的長度、存取線性表中的任意一個結點、查找線性表

中某一元素等等。

缺點:實現(xiàn)線性表線性表的插入和刪除操作時，需要移動大量數(shù)據(jù)元

素而花費較多的時間。

鏈式存儲：每個數(shù)據(jù)元素的存儲表示包括兩個域：

數(shù)據(jù)域——存儲數(shù)據(jù)元素信息的域；

指針域——存儲直接后繼存儲位置的域

存儲單元可連續(xù)，也可不連續(xù)，甚至是零散分布在內(nèi)存，線性表

的鏈式存儲又稱鏈表。

優(yōu)點：插入、刪除操作簡單，只須修改相應的指針域。

缺點：不能隨機存取數(shù)據(jù)元素，只能順序存取，實現(xiàn)查找繁瑣。

特殊的線性表：棧一一插入和刪除數(shù)據(jù)的操作僅限制在表的一端(即

表尾)進行，通常稱插入、刪除一端為棧頂，另一端稱為棧底。

早樹

客觀世界大量存在樹結構，如族譜、行政組織機構都可用樹形象

表示。

①樹的基本概念

樹：n（n'O）個結點的有限集T,T為空稱為空樹，T非空，有

且僅有一個特定結點稱為根結點，其余結點可被分成m（mNO）個互

不相交子集Tl、T2、……Tm,其中每個子集本身又是一棵樹，并稱

①二叉樹的基本概念

二叉樹：n（n20）個結點有限集，它或是空集（n=0）,或是由一

個根結點及兩棵互不相交的，分別稱為根的左子樹和右子樹組成。

兩個不同的二叉樹

二叉樹不是樹的特殊情況，樹和二叉樹主要區(qū)別是：二叉樹有序。

遍歷一一二叉樹的基本操作

前序遍歷：ABDHTEJKCFLMGNO（先根結點，后左子樹，再右子樹）

中序遍歷：HDIBJEKALFMCNGO（先左子樹，后根結點，再右子樹）

后序遍歷：HIDJKEBLMFNOGCA（先左子樹，后右子樹，再根結點）

計算機硬件系統(tǒng)

☆總線

微型計算機的結構采用總線來實現(xiàn)相互間信息傳送。是微處理

器、內(nèi)存儲器和I/O接口間相互交換信息的公共通路。

組成：數(shù)據(jù)總線、地址總線和控制總線

數(shù)據(jù)總線一從微處理器向內(nèi)存儲器、［/0接口傳送數(shù)據(jù)的通路，

同時也是從內(nèi)存儲器、I/O接口向微處理器傳送數(shù)據(jù)的通路，因為它

可在兩個方向往返傳送數(shù)據(jù)，稱為雙向總線。

地址總線一微處理器向內(nèi)存儲器和I/O接口傳送地址信息的通

路，是單向總線，只能從微處理器向外傳送。

控制總線一微處理向內(nèi)存儲器和I/O接口傳送的命令信號及外

界向微處理器傳送狀態(tài)信號等信息的通路。

☆主板

有BIOS芯片、I/O控制芯片、鍵盤和面板控制開關接口、CPU插

座、內(nèi)存插槽、擴充插槽等元件。CMOS參數(shù)：通過設置CMOS參數(shù)（啟

動計算機時，按DEL鍵進入），可修改CPU工作頻率，屏蔽掉某個硬

盤（即使線纜連接了該硬盤，操彳E系統(tǒng)下也看不見）等一些系統(tǒng)設置

的操作。

南橋芯片

CPU風扇

電源7座、/（；MOS電池

9六*412、^BIOS芯片

若

內(nèi)存7A哪歌

并行打印機接口

CPU插槽

電源插座

北橋芯片

☆微處理器（MPU）性能指標

1）字長--CPU一次能處理的數(shù)據(jù)位數(shù)。

2）主頻、外頻和倍頻

主頻--CPU的時鐘頻率，單位是MHz。主頻越高，CPU的速度越快。

外頻--主板系統(tǒng)總線的工作頻率。外頻決定整塊主板的運行速度。

倍頻--CPU外頻與主頻相差的倍數(shù)。公式表示：主頻二外頻X倍頻。

3）高速緩存——基于程序執(zhí)行的局部性原理

LICache（一級緩存）是CPU第一層高速緩存（CPU內(nèi)部），分數(shù)據(jù)

緩存和指令緩存。

L2Cache（二級緩存）是CPU第二層高速緩存，分內(nèi)部和外部兩種

芯片。

4）流水線技術

把一個復雜的運算分解成多個簡單的基本運算，每個簡單運算由

一個專門設計的電路單元完成（都在CPU內(nèi)部），這些電路單元的運

作可并行同時進行。

取指令—分析指令號執(zhí)行指令一保存結果

重疊執(zhí)行

取指令~~L陰分析指令執(zhí)行指令廠可保存結果

時間T

☆網(wǎng)絡適配卡

也稱網(wǎng)卡，是計算機間互相通信的接口。目前，常用有10Mbps（兆

位/每秒），100Mbps和10Mbps/100Mbps自適應（根據(jù)實際網(wǎng)速自動調(diào)

整）網(wǎng)卡。

☆總線標準

1）ISA總線——16位總線標準，總線時鐘頻率為8MHZ,最大傳輸

率為16MB/S（兆字節(jié)/每秒），數(shù)據(jù)總線為16位，地址總線為24

位。

2）PCI總線——32位總線標準，可擴展到64位，與CPU時鐘頻率

無關，自身采用33MHz總線時鐘，數(shù)據(jù)總線為32位，數(shù)據(jù)傳輸

率為132MB/S~264MB/S。

3）AGP總線一一隨著三維圖形的應用而發(fā)展的一種總線標準。AGP

在顯卡與內(nèi)存間提供了一條直接訪問通道。

☆串行口和并行口

1）串行口一-用于連接鼠標、鍵盤和調(diào)制解調(diào)器等設備。串行口在

單一導線上以二進制形式一位一位傳輸，適合長距離的信息傳輸。

2）并行口-一并行口適合連接短距離和高速信息傳輸?shù)脑O備。在一

個多導線電纜上以字節(jié)為單位同時傳輸，常見是并行口連接打印機。

☆輸入設備

1)鍵盤

鍵盤主要分3個區(qū)：

(a)主鍵盤區(qū)：字母、數(shù)字、符號鍵、控制鍵等組成；

(b)功能鍵區(qū)：F1?F12共12個功能鍵；

(c)數(shù)字鍵/光標控制鍵區(qū)：位于鍵盤右邊。

2)鼠標器

依傳感技術分機械式、光電式和機械光電式。

機械式——底部有圓球。

光電式——光電傳感器，底部不設圓球，而是光電元件和光源組成。

☆輸出設備

1)打印機

擊打式打印機——靠機械動作實現(xiàn)印字，如點陣打印機、行式打印

機都是擊打式打印機，噪聲較大。

非擊打式打印機——激光打印機、噴墨打印機。印字過程無機械擊

打動作，噪聲較小。

☆輔助存儲設備

無論內(nèi)磁道扇區(qū)，還是外磁道扇區(qū)，一個扇區(qū)的空間大小(存儲

的字節(jié)數(shù))都一樣，因此，內(nèi)磁道扇區(qū)位密度大。

U盤--USB(通用串行接口)接口設備，采用串行傳輸。

計算機常用軟件介紹

?軟件計算機中的程序、數(shù)據(jù)及相關的文檔

。操作系統(tǒng)

?定義種系統(tǒng)軟件，統(tǒng)一管理和控制計算機系統(tǒng)軟、硬件

資源，合理組織計算機工作流程，控制程序執(zhí)行，并為用戶提供

良好、易于操作的工作環(huán)境。

?分類

1)批處理操作系統(tǒng)

①單道批處理操作系統(tǒng)

一批作業(yè)以脫機方式輸入磁帶（如同拿磁帶到別處去拷貝作業(yè),

且有多個作業(yè)放入磁帶--外存，拷貝完后，再到某處（配有執(zhí)行監(jiān)控

程序）執(zhí)行批改作業(yè)，作業(yè)處理是一個接一個連續(xù)進行，內(nèi)存中始終

只一道作業(yè)，故稱單道批處理操作系統(tǒng)（即指監(jiān)控程序）。

雖然單道處理（執(zhí)行時）減少了人工操作的干預時間，但CPU運行

一個作業(yè)時，若有I/O請求，則CPU須等待輸入/輸出完成，這意味

著很長時間CPU空閑。

②多道批處理操作系統(tǒng)

多個作業(yè)同時放在內(nèi)存，當某個作業(yè)需I/O時?，CPU處理完它的

請求后就轉(zhuǎn)向去做下一道作業(yè)。這樣，第二道作業(yè)的執(zhí)行將與第一道

作業(yè)的I/O并行工作，CPU得到充分利用。

2）分時操作系統(tǒng)

分時技術CPU的執(zhí)行時間被劃分成許多時間片，每個內(nèi)存中的

程序（進程）使用時間片規(guī)定的CPU時間。這樣，多個程序輪流使用

CPU時間。如某個程序規(guī)定時間片內(nèi)沒有完成工作，這時也要把CPU

讓給其他程序，等待下一輪再使用時間片，循環(huán)輪轉(zhuǎn)，直到結束C微

觀上程序執(zhí)行不連續(xù)。

3）網(wǎng)絡操作系統(tǒng)

五方面功能——即網(wǎng)絡通信管理、資源管理、網(wǎng)絡服務（遠程登錄、

文件傳輸、電子郵件、信息檢索等）、網(wǎng)絡管理和互操作。

4）分布式操作系統(tǒng)

基本特征：資源、功能、任務和控制都分布。

任務分布

（a）若干臺計算機協(xié)作完成任務。一個計算問題分成若干個可并行

執(zhí)行的子計算，每個子計算在各計算機上并行執(zhí)行。

（b）各臺計算機組成一個完整、功能強的計算機系統(tǒng)，用戶感覺不

到多臺計算機存在。

資源分布

a）多個計算機共享一個存儲器系統(tǒng)

b）各計算機有獨立存儲器，并互聯(lián)成統(tǒng)一的存儲資源。用戶看來,

整個系統(tǒng)跟一臺計算機一樣。

控制分布

實現(xiàn)并行任務分配、并行進程通信、分布控制機構、分散資源的

管理，并逐漸向智能化（如負載均衡的考慮）方向發(fā)展。

5）分布式操作系統(tǒng)與網(wǎng)絡操作系統(tǒng)的比較

（A）分布性

分布式:處理和控制分布。

網(wǎng)絡操作系統(tǒng)：網(wǎng)絡控制，集中在某個(些)主機或網(wǎng)絡服務器，或

說控制方式集中。

(B)并行性

分布式:有多個處理單元，將多個任務分配到多個處理單元，任務并

行執(zhí)行。

網(wǎng)絡操作系統(tǒng):網(wǎng)絡操作系統(tǒng)通常無任務分配功能。

(C)透明性

分布式:面對多臺計算機就像一臺。

如，用戶要訪問某文件，只需提供文件名而無須知道所要訪問對象駐

留在哪個站點，即具有物理位置的透明性。

網(wǎng)絡操作系統(tǒng):主要指操作實現(xiàn)的透明。

如，用戶要訪問服務器文件，只需發(fā)出相應文件存取命令而無須了解

存取如何實現(xiàn)。

(D)共享性

分布式:系統(tǒng)所有用戶共享各個站點軟、硬件資源。

網(wǎng)絡操作系統(tǒng):共享資源在某個主機或網(wǎng)絡服務器。其他機器資源，

由該機用戶獨占。

(E)可靠性

分布式:處理和控制分布，任何站點故障，通過容錯技術實現(xiàn)系統(tǒng)重

構，系統(tǒng)仍能運行。

網(wǎng)絡操作系統(tǒng):控制集中在某個主機或服務器，系統(tǒng)重構較弱。

?操作系統(tǒng)功能

1.處理機管理--進程管理

進程程序的一次動態(tài)運行過程。注：一個程序的兩次運行對應

兩個進程。

幾方面管理——進程控制、進程同步、進程通信和調(diào)度。

分時系統(tǒng)中內(nèi)存進程的狀態(tài)變化情況

2,存儲器管理--內(nèi)存分配、地址映射、內(nèi)存保護和內(nèi)存擴充

早按一定策略為用戶作業(yè)和進程分配存儲空間和實現(xiàn)重定位。

程序空間

重定位

多記錄內(nèi)存使用情況，保護內(nèi)存程序和數(shù)據(jù)不被破壞。

早使用虛擬存儲技術，提供程序執(zhí)行所需的比實際容量大的多虛擬

存儲空間。

3.設備管理--緩沖管理、設備分配和設備處理

早完成多個用戶使用設備時，數(shù)據(jù)如何緩沖處理。

早為用戶分配所需I/O設備；

早完成用戶提出的I/O請求；

4.文件管理--文件存儲空間管理、目錄管理、文件讀寫管理及文件

共享與保護

5〕用戶接口一一提供用戶編程接口和提供用戶操作計算機的界面接口

?操作系統(tǒng)實例

1.MS-D最操作系統(tǒng)-一單用戶單任務操作系統(tǒng)

界面：命令式內(nèi)部命令和外部命令

內(nèi)部命令：當用戶敲入內(nèi)部命令時，實際是執(zhí)行COMMAND.COM文

件，這個文件是DOS的主要組成部分，由COMMAND.COM文件負責識別

和解釋用戶敲入的是何種內(nèi)部命令。

外部命令：當用戶敲入外部命令時，這個外部命令實際上對應的

是某個獨立的可執(zhí)行文件，因此，外部命令的執(zhí)行實際上是這個可執(zhí)

行文件被調(diào)入內(nèi)存執(zhí)行。

2.Windows操作系統(tǒng)一一單用戶/多用戶多任務操作系統(tǒng)

界面：圖形式——用戶操作計算機都在圖形化的界面下進行

版本:分單機版(如WINDOWS95,98,ME,XP等)和服務器版(如

WINDOWSNT,2000,2003等)

3.UNIX操作系統(tǒng)一-多用戶多任務操作系統(tǒng)

界面：命令式和圖形式都支持，圖形界面可個性化。（UNIX一般

把實現(xiàn)圖形界面的模塊部分不作為它的組成，只提供圖形界面的統(tǒng)一

外掛接口，因此，只要滿足這個統(tǒng)一接口，不同風格的界面都可外掛）

使用范圍：一般用于小型機和大型機。

4.Linux操作系統(tǒng)-一多用戶多任務操作系統(tǒng)

界面：類似于UNIX

版本:RedHatLinux>TurboLinux、紅旗Linux、藍點Linux

其他：源代碼完全免費,一般微機使用較多。

計算機網(wǎng)絡與通信

計算機網(wǎng)絡

1.定義

若干臺地理位置不同，且具有獨立功能的計算機，通過通信設備

和線路相互聯(lián)接，在網(wǎng)絡操作系統(tǒng)，網(wǎng)絡管理軟件及網(wǎng)絡通信協(xié)議的

管理和協(xié)調(diào)下，實現(xiàn)信息傳輸和資源共享的計算機系統(tǒng)

2.網(wǎng)絡系統(tǒng)組成

X網(wǎng)絡通信系統(tǒng)：提供節(jié)點間的數(shù)據(jù)通信功能。

X網(wǎng)絡操作系統(tǒng)：對網(wǎng)絡資源有效管理。

X網(wǎng)絡應用系統(tǒng)：基于網(wǎng)絡環(huán)境的應用系統(tǒng)。

3.網(wǎng)絡分類和拓撲結構

派覆蓋地域范圍劃分：局域網(wǎng)LAN、城域網(wǎng)MAN、廣域網(wǎng)WAN。

派交換技術劃分：電路交換網(wǎng)、分組交換網(wǎng)、信元交換網(wǎng)（ATM網(wǎng)）。

派網(wǎng)絡拓撲結構：總線型、環(huán)型、星型、網(wǎng)狀型、樹型等。

X網(wǎng)絡傳輸介質(zhì)：有線和無線。有線傳輸介質(zhì)有雙絞線、同軸電纜、

光纖，無線傳輸介質(zhì)有微波、紅外線。

4.計算機網(wǎng)絡協(xié)議

派協(xié)議

有關計算機網(wǎng)絡通信的整套規(guī)則，是為完成計算機網(wǎng)絡通信而制

訂的規(guī)則、約定和標準。網(wǎng)絡協(xié)議由語法、語義和時序三大要素組成。

X0SI參考模型

國際標準化組織ISO發(fā)布開放系統(tǒng)互連基本參考模型OST標準，

0SI各層功能：

物理層：利用物理傳輸介質(zhì)為數(shù)據(jù)鏈路層提供物理連接，實現(xiàn)透

明傳送比特流，對物理傳輸介質(zhì)的電氣、機械等特性進行規(guī)范。

數(shù)據(jù)鏈路層：物理層基礎上，建立通信實體間數(shù)據(jù)鏈路連接，傳

送幀為單位的數(shù)據(jù)，采用差錯控制、流量控制，使有差錯的物理線路

變成無差錯數(shù)據(jù)鏈路。

網(wǎng)絡層；實現(xiàn)路由選擇、擁塞控制與網(wǎng)絡互連等功能。

傳輸層：向用戶提供可靠的端到端服務，透明的傳送報文。向高

層屏蔽下層數(shù)據(jù)通信細節(jié)。

會話層：組織兩個會話進程間通信，并管理數(shù)據(jù)交換。

表示層：處理兩個通信系統(tǒng)交換信息的表示方式。包括數(shù)據(jù)格式

變換、數(shù)據(jù)加密與解密、數(shù)據(jù)壓縮與恢復等。

應用層：確定進程間通信性質(zhì)，滿足用戶需要。

應用層將特定的應用進行處理的協(xié)議

每一個應用都有一個協(xié)議

電子郵件圓^s件應用應）

遠程登陸一^⑤應通Q

文件傳輸^輸應用謔）

表示層計算機固有的數(shù)據(jù)格式，與計算機網(wǎng)絡公共的數(shù)據(jù)

格式的交換

?計算機網(wǎng)絡公共的數(shù)據(jù)格式

消除字符串、圖像和聲音等不同信息的表現(xiàn)形式

會話層通信的管理.建立/切斷連接（數(shù)據(jù)傳輸?shù)倪壿嬀€

路）。對傳輸層以下的各層進行管理

連接是什么時候建立的？什么時候切斷的？有幾個正在通信？

傳輸層一兩個節(jié)點間的數(shù)據(jù)傳輸?shù)墓芾?。提供?shù)據(jù)傳輸?shù)?/p>

可靠性（數(shù)據(jù)能夠確實地到達對方）

數(shù)據(jù)沒仃去失嗎?

□

息3n」~r—J一』

網(wǎng)絡層地址的管理和路由的選擇

經(jīng)過哪一條路由能夠到達目的地?

數(shù)據(jù)鏈路層直接連接的“算機之間數(shù)據(jù)幀的識別和傳輸

J__■-A0101—?一?

物理層“0”與“1”對應于電壓的高與低，或者光的

亮與滅。規(guī)定了連接器和電纜的形狀

0101->jinn—oioi

數(shù)字串與信號的變換

一連接器和電纜的形狀

派TCP/IP協(xié)議簇

TCP/IP：傳輸控制協(xié)議/網(wǎng)際協(xié)議

一組用于實現(xiàn)網(wǎng)絡互連的通信協(xié)議，是Internet使用的基礎協(xié)

議?；赥CP/IP的參考模型與0SI參考模型相比，結構更為簡單。

OSIRMTCP/IPRMTCP/IP僑議簇

t

Q.a.e段Q.

ln

LLeS1a

T

TCPUDP

IP屈P.RW?P.ICIP)

度

oW……

-K￡2

TCP協(xié)議傳送給IP的協(xié)議數(shù)據(jù)單元稱作TCP報文段或簡稱為TCP

段(segment),UDP協(xié)議傳送給IP的協(xié)議數(shù)據(jù)單元稱作UDP數(shù)據(jù)報

(datagram)；IP協(xié)議傳送給網(wǎng)絡接口層的協(xié)議數(shù)據(jù)單元稱作IP數(shù)

據(jù)報；通過以太網(wǎng)傳輸?shù)谋忍亓鞣Q作數(shù)據(jù)幀(frame)o

主枷A各對等層協(xié)議主枷B協(xié)議交換單元

報文

TCP報文段

UDP蚊梅報

IP數(shù)據(jù)報

數(shù)據(jù)幀

IP協(xié)議：“網(wǎng)際協(xié)議”

信息包頭部，包含TP協(xié)議要求的各種信息，其中最重要的是信

息包的源地址和目的地址。無論信息包需要從哪里傳送到哪里，因特

網(wǎng)上路由設備和交換設備都會根據(jù)信息包頭部地址信息幫助它選擇

合適路徑到達目的地。

TCP協(xié)議：“傳輸控制協(xié)議”

將完整消息流封裝成許多信息包；接收數(shù)據(jù)時，信息包重組Q同

時TCP協(xié)議還負擔流量控制。

UDP協(xié)議：“用戶數(shù)據(jù)協(xié)議”

用于需要快速傳送而不是可靠連接場合。UDP