三級數(shù)據(jù)庫高頻考點手冊

第一章計算機基礎(chǔ)知識

1、計算機的發(fā)展階段：經(jīng)歷了以下5個階段（它們是并行關(guān)系）：大型

機階段（經(jīng)歷四小階段它們是取代關(guān)系）、小型機階段、微型機階段、客戶

機/服務(wù)器階段（對等網(wǎng)絡(luò)與非對等網(wǎng)絡(luò)的概念）和互聯(lián)網(wǎng)階段（Arpanet

是在1983年第一個使用TCP/IP協(xié)議的。在1991年6月我國第一條與國

際互聯(lián)網(wǎng)連接的專線建成它從中國科學(xué)院高能物理研究所接到美國斯坦福

大學(xué)的直線加速器中心。在1994年實現(xiàn)4大主干網(wǎng)互連（中國公用計算機

互聯(lián)網(wǎng)Chinanet、中國科學(xué)技術(shù)網(wǎng)Cstnet,中國教育和科研計算機網(wǎng)

Cernet.中國金橋信息網(wǎng)ChinaGBN））

2、計算機種類：

按照傳統(tǒng)的分類方法：計算機可以分為6大類：大型主機、小型計算

機、個人計算機、工作站、巨型計算機、小巨型機。按照現(xiàn)實的分類

方法：計算機可以分為5大類：服務(wù)器、工作站、臺式機、筆記本、手持

設(shè)備。

3、計算機的公共配置：CPU、內(nèi)存（RAM）、高速緩存（Cache）、硬

盤、光驅(qū)、顯示器（CRT、LCD）、操作系統(tǒng)（OS）

4、計算機的指標(biāo)：位數(shù)指CPU寄存器中能夠保存數(shù)據(jù)的位數(shù)、速度

（MIPS、MFLOPS）指CPU每秒鐘處理的指令數(shù)通常用主頻來表示CPU的處理

速度、容量（B、KB、MB、GB、TB）、數(shù)據(jù)傳輸率（Bps）、版本和可靠性

(MTBF、MTTR)。

5、計算機的應(yīng)用領(lǐng)域：科學(xué)計算、事務(wù)處理、過程控制、輔助工程、

人工智能、網(wǎng)絡(luò)應(yīng)用。（補充實例）

6、計算機系統(tǒng)的組成:硬件系統(tǒng)具有原子特性（芯片、板卡、設(shè)備、網(wǎng)

絡(luò)）與軟件系統(tǒng)具有比特特性。且它們具有同步性。

7、奔騰芯片的技術(shù)特點：奔騰32位芯片，主要用于臺式機和筆記本,

奔騰采用了RISC和CISC技術(shù)（技術(shù)特點10個請看書P8）

8、安騰芯片的技術(shù)特點：安騰是64位芯片，主要用于服務(wù)器和工作

站。安騰采用簡明并行指令計算（EPIC）技術(shù)

9、主機板與插卡的組成：

（1）主機板簡稱主板（mainboard）或母板（motherboard）。由5部分組

成（CPU、存儲器、總線、插槽和電源）與主板的分類

（2）網(wǎng)絡(luò)卡又稱為適配器卡代號NIC,其功能為：（見書P11）

10、軟件的基本概念：軟件由程序（功能實現(xiàn)部分）與文檔（功能說明部

分）組成。軟件是用戶與計算機硬件系統(tǒng)之間的橋梁。

11、應(yīng)用軟件包括：桌面應(yīng)用軟件、演示出版軟件、瀏覽工具軟件、

管理效率軟件、通信協(xié)作軟件和系統(tǒng)維護軟件。

12、程序與文檔：程序是由指令序列組成的，告訴計算計如何完成一

個具體的任務(wù)。

文檔是軟件開發(fā)、使用和維護中的必備資料。

13、軟件開發(fā)：軟件的生命周期中，通常分為三大階段，每個階段又

分若干子階段:

(1)計劃階段：分為問題定義、可行性研究(是決定軟件項目是否開發(fā)

的關(guān)鍵)。

(2)開發(fā)階段：在開發(fā)前期分為需求分析、總體設(shè)計、詳細設(shè)計三個子

階段，在開發(fā)后期分為編碼、測試兩個子階段。前期必須形成的文檔有：

軟件需求說明書，軟件設(shè)計規(guī)格說明書。

(3)運行階段：主要任務(wù)是軟件維護。為了排除軟件系統(tǒng)中仍然可能隱

含的錯誤，擴充軟件功能。

14、編程語言：(機器語言與匯編語言都依賴于具體的機器，匯編語

言與高級語言都需要編譯)

(1)機器語言：能被計算機直接理解和執(zhí)行，速度快，但該種語言難記、

難學(xué)、難懂。

(2)匯編語言：用英文助記符和十進制數(shù)代替二進制碼，使機器語言變

成了匯編語言。匯編語言屬于低級語言。匯編語言要通過匯編程序把匯編

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

(3)高級語言：高級語言是一種面向問題或過程的語言。它是近似于日

常會話的語言。它不但直觀、易學(xué)，而且通用性強。高級語言要通過編譯

(或解釋)翻譯成機器語言才能執(zhí)行。

15、媒體的概念與分類：

(1)媒體的概念:信息的載體

(2)媒體的分類：傳輸媒體、表現(xiàn)媒體、表示媒體、感覺媒體

16、多媒體的基本概念：指有聲有色的信息處理與利用技術(shù)。多媒體

技術(shù)可劃分為偏硬件技術(shù)和偏軟件技術(shù)兩部分。

17、MPC的組成：具有CD-ROM、具有A/D和D/A轉(zhuǎn)換功能、具有高清

晰的彩色顯示器、具有數(shù)據(jù)壓縮與解壓縮的硬件支持

18、多媒體的關(guān)鍵技術(shù)：數(shù)據(jù)壓縮與解壓縮技術(shù)、芯片與插卡技術(shù)、

多媒體操作系統(tǒng)技術(shù)、多媒體數(shù)據(jù)管理技術(shù)。

19、超文本與超媒體的概念：

(1)超文本是非線性非順序的而傳統(tǒng)文本是線性的順序的。

(2)超文本概念：超文本是收集、存儲和瀏覽離散信息以及建立和表現(xiàn)

信息之間關(guān)系的技術(shù)。

(3)超媒體的組成：當(dāng)信息載體不限于文本時，稱之為超媒體。超媒體

技術(shù)是一種典型的數(shù)據(jù)管理技術(shù)，它是由稱之為結(jié)點(node)和表示結(jié)點之

間聯(lián)系的鏈(link)組成的有向圖(網(wǎng)絡(luò))，用戶可以對其進行瀏覽、查詢

和修改等操作。

(4)超媒體系統(tǒng)的組成：編輯器、導(dǎo)航工具、超媒體語言

第二章數(shù)據(jù)結(jié)構(gòu)算法

2.1基本概率

考點、1數(shù)據(jù)結(jié)構(gòu)的基本概念

1.數(shù)據(jù)

在計算機系統(tǒng)中，數(shù)據(jù)不僅包含了通常的數(shù)值概念，還有更廣泛的含義我

們把采用計算機對客觀事物進行識別、存儲和加工所做的描述，統(tǒng)稱為數(shù)據(jù)。

簡言之，數(shù)據(jù)就是計算機化的信息

數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。數(shù)據(jù)

項是數(shù)據(jù)的不可分割的最小單位，又稱為關(guān)鍵碼，其值能夠唯一確定一個數(shù)據(jù)

元素的數(shù)據(jù)項。

2.數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)包括3個方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機中的

存儲方式，以及在這些數(shù)據(jù)上定義的運算的集合。

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)在計算機中的存儲方式無關(guān)，

它用來抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線

性結(jié)構(gòu)。最常見的線性結(jié)構(gòu)是線性表，最典型的非線性結(jié)構(gòu)是樹型結(jié)構(gòu)。

⑵數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)實現(xiàn)了數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)的

存儲問題，存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)。存儲結(jié)構(gòu)分為順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯?/p>

結(jié)構(gòu)。

(3)數(shù)據(jù)的運算。數(shù)據(jù)的各種邏輯結(jié)構(gòu)都有相對應(yīng)的運算，每一種邏輯結(jié)構(gòu)

都有一個運算的集合。數(shù)據(jù)運算主要包括查找(檢索)、排序、插入、更新及刪

除等。

考點2主要的數(shù)據(jù)存儲方式

實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計算機存儲器的映像有多種不同的方式。順序存儲

結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)是兩種最主要的存儲方式。

1.順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元

里，節(jié)點之間的關(guān)系由存儲單元的相鄰關(guān)系來決定，它主要用于存儲線性結(jié)構(gòu)

的數(shù)據(jù)。順序存儲結(jié)構(gòu)的主要特點如下。

(1)由于節(jié)點之間的關(guān)系由物理上的相鄰關(guān)系決定，所以節(jié)點中沒有鏈接信

息域，只有自身的信息域，存儲密度大，空間利用率高。

(2)數(shù)據(jù)結(jié)構(gòu)中第i個節(jié)點的存儲地址乙可由下述公式計算求得：

Li=L0+(i-1)xK

L0為第一個節(jié)點存儲地址，左為每個節(jié)點所占的存儲單元數(shù)。

(3)插人、刪除運算會引起相應(yīng)節(jié)點的大量移動各節(jié)點的物理地址是相鄰

的，每一次插入、刪除運算會引起相應(yīng)節(jié)點物理地址的重新排列。

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)打破了計算機存儲單元的連續(xù)性，可以將邏輯上相鄰的兩個

數(shù)據(jù)元素存放在物理上不相鄰的存儲單元中鏈?zhǔn)酱鎯Y(jié)構(gòu)的每個節(jié)點中至少有

一個節(jié)點域，來體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。

鏈?zhǔn)酱鎯Y(jié)構(gòu)的主要特點包括以下幾個方面。

(1)節(jié)點中除自身信自、夕卜，還有表示鏈接信息的指針域，因此比順序存儲

結(jié)構(gòu)的存儲密度小，存儲空間利用率低。

(2)：羅輯上相鄰的節(jié)點物理上不一定相鄰，可用于線性表、樹、圖等多種

邏輯結(jié)構(gòu)的存儲表示。

⑶插入、刪除等操作靈活方便，不需要大量移動節(jié)點，只需將節(jié)點的指針

值修改即可。

考點3算法設(shè)計與分析

在計算機領(lǐng)域，一個算法實質(zhì)上是針對所處理問題的需要，在數(shù)據(jù)的邏輯

結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上施加的一種運算，它是解決特定問題的方法。一個算

法所占用的計算機資源包括時間代價和空間代價兩個方面

時間代價的含義是：當(dāng)問題的規(guī)模以某種單位由1增至n時，解決該問題

的算法運行時所耗費的時間也以某種單位由f(1)增至f(n),則稱該算法的時

間代價為f(n)o

空間代價的含義是：當(dāng)問題的規(guī)模以某種單位由1增至n時，解決該問題

的算法實現(xiàn)時所占用的空間也以某種單位由到8(1)增至8(11),則稱該算法的空

間代價為g(n)。

2.2線性表

線性表的邏輯結(jié)構(gòu)是由n個數(shù)據(jù)元素組成的一個有限序列。線性表中所包

含元素的個數(shù)叫線性表的長度.它是可變的.可同線性表中增加或刪除元素。

線性表包括順序表、鏈表、散列表和串等。

線性表的基本運算有：置表空、求表長、讀表元素、插入、刪除及檢索等

操作。

考點4順序表和一維數(shù)組

線性表的順序存儲是線性表的一種最簡單的存儲結(jié)構(gòu)。其存儲方法是：在

內(nèi)存中為線性表開辟一塊連續(xù)的存儲空間，該存儲空間所包含的存儲單元數(shù)要

大于或等于線性表的長度，讓線性表的第一個元素存儲在這個存儲空間的第一

個單元中，第二個元素存儲在第二個單元中，其他元素依次類推。一般情況下，

若長度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動的平均

次數(shù)均為n/2。

考點5鏈表

鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈?zhǔn)酱鎯Ρ硎?，?/p>

線性鏈表是非線性數(shù)據(jù)結(jié)構(gòu)樹和圖的鏈?zhǔn)酱鎯Ρ硎尽?/p>

1.線性鏈表

線性鏈表也稱為單鏈表，其每個一節(jié)點中只包含一個指針域。對鏈表進行

插入、刪除運算時只需改變節(jié)點中指針域的值。

(1)在指針一P后插入指針9的關(guān)鍵運算步驟：

qt.1ink:=Pt.1ink:

pt.1ink:=q;

(2)刪除指針P后繼節(jié)點q的關(guān)鍵運算步驟：

q：=pt.1ink;

pt.1ink:=qt.link;

(3)在第一個節(jié)點(或稱頭節(jié)點)前插入一個指針P的關(guān)鍵運算步驟：

pt.1ink:=head;

head:二P;

(4)刪除表中頭節(jié)點的關(guān)鍵運算步驟：

head:=headt.link:

2.雙鏈表

在雙鏈表中，每個節(jié)點中設(shè)置有兩個指針域，分別用以指向其前驅(qū)節(jié)點和

后繼節(jié)點。rlink指向節(jié)點的后繼，llink指向節(jié)點的前驅(qū)，這樣的結(jié)構(gòu)方便向

后和向前查找。

(1)若要在雙鏈表中刪除指針P所指的節(jié)點時，只需修改其前驅(qū)的rlink字

段和后繼的Mink字段，步驟如下：

pt.llink?.r1ink:=pt.r1ink;

PtT.rlinkT.llink:=Pt.llink;

⑵如果要在指針P后面插入指針q所指的新節(jié)點，只需修改P指針?biāo)腹?jié)

點的rlink字段和原來后繼均Kink字段，并重新設(shè)置q所指節(jié)點的Mink和

rlink值,步驟如下：

qt.Mink:=P:

qt.rlink:=Pt.rlink;

Pt.rlinkr.Rink:=q;

pt.rlink:=q;

3.可利用空間表

可利用空間表的作用是管理可用于鏈表插入和刪除的節(jié)點，當(dāng)鏈表插人需

要一個新節(jié)點時，就從可利用空間表中刪除第一個節(jié)點，用這個節(jié)點去做鏈表

插入；當(dāng)從鏈表中刪除一個節(jié)點時，就把這個節(jié)點插入到可利用空間表的第一

個節(jié)點前面。

考點6棧

棧又稱為堆棧，它是一種運算受限的特殊的線性表，僅允許在表的一端進

行插入和刪除運算，可進行運算的一端為棧頂(top),另一端為棧底(bottom)。

表中無任何元素的棧稱為空棧。由于棧的插入和刪除運算僅在棧頂進行，后進

棧的元素必定先被刪除，所以又把棧稱為“后進先出"(LIFO)表。

棧的基本操作有：

(1)push(S,X)o往棧S中插人(或稱推人)一個新的棧頂元素x,即進棧。

(2)pop(S)0從棧S中刪除(或稱彈出)棧頂元素，即出棧。

(3)lop(S,X):把棧S的棧頂元素讀到變量x中，棧保持不變。

(4)empty(S)o判斷棧S是否為空棧，是則返回值為真。

(5)makempty,(S)將棧S設(shè)置為空。

棧既然是一種線性表，所以線性表的存儲結(jié)構(gòu)同樣也適用于棧。棧通常用

順序存儲方式來存儲，分配一塊連續(xù)的存儲區(qū)域存放棧中元素，用一個變量來

指向當(dāng)前棧頂。

考點、7隊列

隊列簡稱為隊，它也是一種運算受限的線性表，隊列的限定是僅允許在表

的一端進行插入，而在另一端進行刪除。進行刪除操作的一端稱做隊列的頭，

進行插入操作的一端稱為隊列的尾.

隊列的基本操作有：

(1)enq(Q,X)。往隊列口中插入一個新的隊尾元素x,即人隊。

(2)deq(口)從隊列Q中刪除隊頭元素，即出隊。

(3)front口，x)將隊列口的隊頭元素值讀到變量x中，隊列保持不變。

(4)empty(Q).判斷隊歹，1口是否為空，是則返回值為真。

(5)makempty(口)將隊列口置為空隊列。

和線性表一樣、隊列的存儲方式也有順序存儲和鏈?zhǔn)酱鎯煞N。順序隊列

在進行人隊操作時，會產(chǎn)生假溢出現(xiàn)象解決的辦法是讓隊列首尾相連，構(gòu)成一

個循環(huán)隊列。

考點8串

串(或字符串)是由零個或多個字符組成的有限序列。零個字符的串是空串。

串中字符的個數(shù)就是串的長度串中的字符可以是字母、數(shù)字或其他字符。

串的存儲同樣也有順序存儲和鏈?zhǔn)酱鎯煞N。順序存儲時，既可以采用非

緊縮方式，也可以采用緊縮方式。

串的基本運算有連接、賦值、求長度、全等比較、求子串、找子串位置及

替換等，其中找子串位置(或稱模式匹配)比較重要。

2.3多維數(shù)組、稀疏矩陣和廣義表

考點9多維數(shù)組的順序存儲

多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的所有元素并未排在一個線性序列

里，要順序存儲多維數(shù)組就需要按一定次序把所有的元素排在一個線性序列里。

常用的排列次序有行優(yōu)先順序和列優(yōu)先順序兩種。

考點、10稀疏矩陣的存儲

稀疏矩陣是指矩陣中含有大量的0元素。對稀疏矩陣可進行壓縮存儲，即

只存儲其中的非0元素。若非0元素分布是有規(guī)律的，可用順序方法存儲非0

元素。對于一般的稀疏矩陣，常見的存儲方法還有不元組法和十字鏈表法，這

里就不再介紹了。

考點11廣義表的定義和存儲

廣義表(又稱列表)是線性表的另一種推廣，是由零個或多個單元素或子表

所組成的有限序列。它與線性表的區(qū)別在于：線性表中的元素都是結(jié)構(gòu)上不可

分的單元素，而廣義表中的元素既可以是單元素，又可以是有結(jié)構(gòu)的表廣義表

與線性表相比，具有如下3個方面的特征。

(1)廣義表的元素可以是子表，而子表的元素還可以是子表。

(2)廣義表可被其他廣義表引用二

(3)廣義表可以是遞歸的表，即廣義表也可以是自身的一個子表。

2.4樹型結(jié)構(gòu)

樹型結(jié)構(gòu)是節(jié)點之間有分支的、層次關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹,

是一類重要的非線性結(jié)構(gòu)常用的樹型結(jié)構(gòu)有樹和二叉樹。

考點、12樹的定義

樹是樹型結(jié)構(gòu)的一個重要類型。一棵樹或者是沒有任何節(jié)點的空樹，或者

是由一個或多個節(jié)點組成的有限集合T,其中：

(1)有且僅有一個稱為該樹根的節(jié)點。

(2)除根節(jié)點外的其余節(jié)點可分為。M(m>0)個互不相交的有限集71,,

兀，…，T,其中每一個集合本身又是一棵樹，并且稱為根的子樹。

這是一個遞歸的定義，即在樹的定義中又用到了樹的概念。這恰好顯示了

樹的固有特性。

考點13二叉樹定義

1.二叉樹的定義

二叉樹是一種最簡單而巨重要的樹型結(jié)構(gòu)它或者是一棵空樹，或者是一棵

由一個根節(jié)點和兩棵互不相交的、分別稱為這個根的左子樹和右子樹的二叉樹

組成。有兩種特殊形態(tài)的二_叉樹，它們是滿二叉樹一和完全二叉樹。

2.二叉樹與樹的區(qū)別

盡管樹和二叉樹的概念之間有許多關(guān)系，但它們是兩個概念二叉樹不是樹

的特殊情況，樹和二叉樹之間最主要的區(qū)別是：二叉樹的節(jié)點的子樹要區(qū)分左

子樹和了。子樹，即使在節(jié)點只有一棵子樹的情況下也要明確指出該子樹是左

子樹還是右子樹。

考點14樹與二叉樹之間的轉(zhuǎn)換

1.樹轉(zhuǎn)換成二叉樹

將一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹應(yīng)包括以下幾個步驟：

(1)在兄弟竹點之間加條連線

⑵對每一個節(jié)點，只保留它與第一個子節(jié)點的連線，與其他子節(jié)點連線全

部抹掉

(3)以樹根為軸心，順時針旋轉(zhuǎn)45。

2.森林轉(zhuǎn)換成二叉樹

如果F={T1,T2，…Tm}是森林，則可按如下規(guī)則將其轉(zhuǎn)換乘

一棵二叉樹B=(root,LB,RB,)：

⑴若F為空，即m=0,則B為樹。

(2)若F非空，即則B的跟root即為森林中的第一棵樹的跟

ROOT(T);B的左子樹LB是從T、中根節(jié)點的子樹森林Fl={Til,T,,

Tm}轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F，={T1,T2,...Tm}轉(zhuǎn)換而

成的二叉樹。

3.二叉樹轉(zhuǎn)換成森林

如果B二(root,LB,RB)是、棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F=

{T1,T2,...Tm)：

(1)若B為空，則F為空。

⑵若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root;T1

中根節(jié)點的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的；F中除T1之外其余樹

組成的森林F，={T1,T2,…Tm}是由B的右子樹RB轉(zhuǎn)換而成的。

考點、15二叉樹和樹的周游

周游(或稱遍歷)是樹型結(jié)構(gòu)的一種重要運算，是其他運算的基礎(chǔ)。周游一

棵樹就是按一定的次序訪問樹中聽有節(jié)點，并且每個節(jié)點僅被訪問一次的過程。

1.周游二叉樹

二又樹的周游主要有以下3種方式。

(1)前序法(NLR)。訪問根，按前序周游左子樹，按前序周游右子樹。

(2)后序法(LRN)。按后序周游左子樹，按后序周游右子樹，訪問根。

(3)對稱序法(LNR)。按對稱序周游左子樹，訪問根，按對稱序周游右子樹。

2.周游樹和樹林

對樹和樹林的周游分為按深度優(yōu)先和按廣度優(yōu)先兩種方式進行。

按深度優(yōu)先方式又可分為按先根次序和按后根次序周游兩種方式。

(1)先根次序周游訪問第一棵樹的根，按先根次序周游第一棵樹的根子樹，

按先根次序周游其他的樹。

(2)后根次序周游按后根次序周游第一棵樹的子樹，訪問第一棵樹的根，按

后根次序周游其他的樹。

比較一下樹與一又樹之間的對應(yīng)關(guān)系，可以看出，按先根次序周游樹正好

與按前序法周游樹對應(yīng)的二叉樹等同，后根次序周游樹正好與按對稱序法周游

對應(yīng)的二叉樹等同。

按廣度優(yōu)先方式可以做層次次序周游，首先依次訪問層數(shù)為0的節(jié)點，然

后依次訪問下一層的節(jié)點，直至訪問完最后一層的節(jié)點。

考點16二叉樹的存儲和線索

1二叉樹的11ink-r1ink法存儲表示

二叉樹的存儲通常采用鏈接方式，即每個節(jié)點除存儲節(jié)點自身的信息外再

設(shè)置兩個指針域11ink和r1ink,分別指向節(jié)點的左子女和右子女。當(dāng)節(jié)點的

某個子女為空時，則相應(yīng)的指針值為空。再加上一個指向

樹根的指針t,就構(gòu)成了二叉樹的存儲表示。這種存儲表示法被稱為11ink

-rlink表示法。

2.線索二叉樹

在有n個節(jié)點的二叉樹的且ink-rlink法存儲表示中，必定有n+1個空

指針域，將這些指針位置利用起來，存儲節(jié)點在指定周游次序F的前驅(qū)、后繼

節(jié)點指針，則得到線索二叉樹。

考點17哈夫曼樹

哈夫曼樹是樹型結(jié)構(gòu)的一種應(yīng)用二哈夫曼(Huffman)樹又稱最優(yōu)樹，是一類

帶權(quán)路徑長度最短的樹，這種樹在信息檢索中經(jīng)常用到。所謂路徑長度就是從

一個節(jié)點到另一個節(jié)點所經(jīng)過的分支總數(shù)。樹的路徑長度是從樹的根到每個節(jié)

點的路徑長度之和。完全二叉樹就是這種路徑長度最短的二叉樹。節(jié)點的帶權(quán)

路徑長度為從該節(jié)點到樹根之間的路徑長度與節(jié)點上權(quán)的乘積。樹的帶權(quán)路徑

長度為樹中所有葉子節(jié)點的帶權(quán)路徑長度之和，WPL最小的不是完全二叉樹，而

是權(quán)大的葉子離根最近的二叉樹。

2.5“查找

查找是數(shù)據(jù)結(jié)構(gòu)中一種很常用的基本運算。

查找就是在數(shù)據(jù)結(jié)構(gòu)中找出滿足某種條件的節(jié)點。所給的條件可以是關(guān)鍵

碼字段的值，也可以是非關(guān)鍵碼字段的值，本節(jié)只考慮基于關(guān)鍵碼值的查找

考點18順序查找

順序查找是線性表的最簡單、最基本的查找方法順序查找的優(yōu)點是對線性

表節(jié)點的邏輯次序無要求，對線性表存儲結(jié)構(gòu)也無要求

順序查找的缺點是速度較慢，平均檢索長度與表中節(jié)點個數(shù)和n成正比，

查找成功最多需比較n次，平均查找長度為(n+1)/2次，約為表長的，半，查

找失敗需比較n+1次順序查找算法的時間復(fù)雜度為0(n)。

考點19二分法查找

二分法查找是一種效率比較高的查找方法，在進行二分法查找時，線性表

節(jié)點必須按關(guān)鍵碼值排序，且線性表是以順序存儲方式存儲的。

二分法查找的優(yōu)點是比較次數(shù)少，查找速度快，平均檢索長度小，經(jīng)過｛—

logen次比較就可以完成查找過程。缺點是在查找之前要為建立有序表付出代

價，同時對有序表的插入和刪除都需要平均比較和移動表中的一半元素。一般

情況下，二分查找適應(yīng)于數(shù)據(jù)相對固定的情況，且二分法查找只適用于線性表

的順序存儲。

考點20分塊查找

分塊查找又稱索引順序查找，是介于線性查找和二分法查找之間的一種查

找方法。它要求把線性表分成若干塊，每一塊中的節(jié)點不必有序，但塊與塊之

間必須排序，不妨設(shè)每一塊中各節(jié)點的關(guān)鍵碼都大于前一塊的最大關(guān)鍵碼值。

另外，還要求將各塊中的最大關(guān)鍵碼值組成一個有序的索引表。滿足上述條件

的線性表稱做分塊有序表。它的分塊檢索的過程分以下兩步進行。

⑴先查索引表(可以用線性檢索或二分法檢索)，確定要找的記錄在哪一

塊。

(2)在相應(yīng)的塊中線性檢索待查記錄。

考點21散列表的存儲和查找

散列存儲中使用的函數(shù)稱為散列(Hash)函數(shù)散列表(又稱哈希表)是線性表

的一種重要的存儲方式和檢索方法。實現(xiàn)散列技術(shù)檢索必須解決兩個問題：一

個是構(gòu)造一個好的散列函數(shù)，盡可能避免沖突現(xiàn)象的發(fā)生；另一個是設(shè)計有效

的解決沖突的方法。

1.散歹＞1函數(shù)

常用的散列函數(shù)有以下幾種。

⑴除余法。選擇一個適當(dāng)?shù)恼麛?shù)川通常選P為不大于散列表存儲區(qū)域大

刁、的最大素數(shù))，用p去除關(guān)鍵碼值，取其余數(shù)作為地址，即h(key)二keymod

P?

(2)數(shù)字分析法。當(dāng)關(guān)鍵碼的位數(shù)比存儲區(qū)域地址碼位數(shù)多時，可以對關(guān)鍵

碼的各位進行分析，去掉分布不均勻的位，留下分布均勻的位作為地址。

(3)折疊法。將關(guān)鍵碼值從某些地方斷開，分為幾段，折疊相加，作為地址。

(4)中平方法。對關(guān)鍵碼值求平方，取中間的幾位數(shù)作為地址。

2.處理沖突的方法

發(fā)生沖突是指由關(guān)鍵字求得的散列地址為1)的位置上已存有記

錄，處理沖突就是為該關(guān)健字找到另一個“空”的散列地址。常用的處理沖突

的方法有開地址法、拉鏈法等。

3.負載因子(裝填因子)和平均檢索長度

裝填因子表示散列表的裝滿程度，定義為散列表中節(jié)點的數(shù)目除以基本區(qū)

域能容納的節(jié)點數(shù)所得的商，用a表示a越小，沖突的可能性越小，a越大，沖

突的可能性越大，檢索時需要比較的次數(shù)就越多。平均檢索長度依賴于散列表

的裝填因子。

2.6排序

排序是數(shù)據(jù)處理領(lǐng)域經(jīng)常要使用的一種運算，就是將一組元素按照關(guān)鍵碼

的遞增或遞減的順序來排列為過程

按照排序過程中的存儲器不同，可將排序方法分為內(nèi)部排序和外部排序兩

類。一廠面將介紹插入排序、選擇排序、交換排序和歸并排序等幾種常用的內(nèi)

部排序方法。

考點22插入排序

插入排序的基本思想：每一步將一個待排序的記錄按其關(guān)鍵字值的大小插

人到一個有序的文件中，插入后該文件仍然是有序文件。

1.直接插入排序

直接插入排序是一種最簡單的排序方法它的基木思想是將一個記錄插入到

已排好序的有序表中，從而得到一個新的、記錄數(shù)增I的有序表整個排序過程

為：先將第一個記錄看成是一個有序的子序列，然后從第2個記錄起依次逐個

地插入到這個有序的子序列中去。

直接插入排序的時間復(fù)雜度為0(n)。

直接插人排序方法不僅適用于順序表，而且適用于單鏈表

2.二分法插入排序

在直接插入排序}},,若采用二分法查找而不是順序查找待插入元素的插入

位置，則稱為二分法插入排序這種插入排序可減少比較次數(shù)，使排序速度有所

提高，但提高不會太多，因為移動記錄的總次數(shù)不受改變，其時間復(fù)雜度仍為

0(n2)。

直接插入和二分法插入排序方法都是穩(wěn)定的，因為它們不會改變原序列中

具有相同關(guān)鍵字記錄的相對次序。

3.希爾排序

希爾排序又稱縮小增量排序，它是對直接插入排序的一種改進方法希爾排

序的基本思路：對相隔較大距離的記錄進行比較，就能使記錄在比較后移動較

大的距離這樣能使較小的記錄盡快往前移，較大的記錄盡快往后移，從而提高

排序的速度

希爾排序是一種不穩(wěn)定的排序過程

考點、23選擇排序

選擇排序的基木思想是每次從待排序的記錄中選出關(guān)鍵碼值最小或最大的

記錄放在已排好序的記錄序列后面，直至排序完畢。

1.直接選擇排序

直接選擇排序也是一種簡單的排序方法。選擇排序的基本方法是：每次從

待排序的區(qū)間中選擇出具有最小排序碼的元素。把該元素與該區(qū)間的第一個元

素交換位置。第一次待排序區(qū)間為A⑴~A[n],經(jīng)過選擇和交換后，A[l]為

最小排序碼的元素。第二次待排序區(qū)間為A[2]-A[n],經(jīng)過選擇和交換后，A[2]

為僅次于A[1]的具有最小排序碼的元素，依次類推，經(jīng)過nT次選擇和交換

后，排序完畢。

直接選擇排序方法的時間復(fù)雜度為0(n2),此方法是不穩(wěn)定的。

2.堆排序

堆的定義如下：n個元素序列｛kl,k2,kn),當(dāng)且僅當(dāng)滿足下列關(guān)系

時，稱之為堆。

人毛人Ki《K2i,Ki<K2i+1,i=1,2,…，n/2

堆排序的基本思想：對一組待排序的關(guān)鍵碼，首先把它們按堆的定義排列

成一個序列，找到其中最小的關(guān)鍵碼.接著將最小的關(guān)鍵碼取出，然后將剩下

的關(guān)鍵碼再建堆排序，依次進行，直到將全部關(guān)鍵碼排好為止。建堆的基本方

法是將大的元素下沉，小的元素上浮，即所謂的篩選法。

在最壞的情況下，堆排序時間復(fù)雜度為0(nlog2n)。堆排序僅需一個記錄

大小的輔助存儲空間。堆排序是不穩(wěn)定的。

考點、24交換排序

交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字值，并交換不滿足順

序要求的那些記錄，直到全部記錄滿足關(guān)鍵字值排序要求為止。

1.起泡排序

起泡排序又稱為冒泡排序，其基本思想是通過相鄰記錄之間關(guān)鍵字的比較

和交換，使關(guān)鍵字值較小的記錄逐漸從底部移向頂部，即從下標(biāo)較大的單元移

向下標(biāo)較小的單元，關(guān)鍵字較大的記錄從頂部移向底部。從起泡排序算法可以

看出，若初始序列為“正序”序列，則只需進行一趟排序；反之，若初始序列

為“逆序”序列，則需進行。一I趟排序。因此，總的時間復(fù)雜度為。(礦)。

起泡排序是一種穩(wěn)定的排序過程。

2.快速排序

快速排序是口前內(nèi)部排序中速度最快的一種排序算法，其實質(zhì)是對起泡排

序的改進在快速排序中，記錄的比較和交換是從兩端向中間進行的，排序碼較

大的記錄一次就能夠從前面交換到后面單元，排序碼較小的記錄一次就能夠從

后面交換到前面單元，記錄每次移動的距離較遠，總比較和移動次數(shù)較少。

快速排序是不穩(wěn)定的排序。排序速度最快時，其時間復(fù)雜度為0(nlog,n);

排序速度最慢時，其時間復(fù)雜度為。(n')快速排序的平均時間復(fù)雜度為0(nlog2

n)。快速排序除了需要一個記錄的輔助空間來存放每次選取的基準(zhǔn)記錄外，還

需要一個棧空間來實現(xiàn)遞歸。

考點25歸并排序

歸并是將兩個或者多個有序表合并成一個有序表歸并排序要求待排序文件

已經(jīng)部分排序。歸并排序的基本思想是將這些已排過序的文件進行合并，得到

完全排序的文件。

假設(shè)初始序列含有n個記錄，則可看成是n個有序的子序列，每個子序列

的長度為1,然后兩兩歸并，得到n/2個長度為2或I的有序子序列，再兩兩歸

并，如此重復(fù)，直到得到一個長度為n的有序序列為止。這種排序方法稱為二

路歸并排序。

歸并排序平均時間復(fù)雜度為0(nl092n),輔助空間為03)。

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

3.1操作系統(tǒng)

考點1操作系統(tǒng)概念

1.操作系統(tǒng)基本概念

操作系統(tǒng)是計算機系統(tǒng)中的一個系統(tǒng)軟件，是控制和管理計算機硬件和軟

件資源，合理組織計算機工作流程及方便用戶的程序集合。操作系統(tǒng)有兩個重

要的作用：一是管理系統(tǒng)中的各種資源；二是給用戶提供一個友好的界面，方

使用戶操作計算機。

2.操作系統(tǒng)的基本特征

操作系統(tǒng)包括以下3個基本特征：

(1)并發(fā)性。所謂并發(fā)性是指在計算機系統(tǒng)中同時存在多個程序，從宏觀上

看，這些程序是同時向前推生的。

(2)共享性。所謂資源共享性是指操作系統(tǒng)程序與多個用戶程序共享系統(tǒng)中

的各種資源。這種共享是在操作系統(tǒng)控制下實現(xiàn)的。

(3)隨機性。操作系統(tǒng)運行在一個隨機環(huán)境中。一個設(shè)備可能在任何時候向

處理機發(fā)出中斷請求，系統(tǒng)無法知道運行著的程序會在什么時候做什么事情。

考點2操作系統(tǒng)的功能

操作系統(tǒng)的主要功能包括以下幾個方面。

(1)進程管理。主要是對處理機進行管理。

(2)存儲管理。主要是對內(nèi)存的分配、保護和擴充。

(3)設(shè)備管理。對所有輸人、輸出設(shè)備的管理。

(4)文件管理。主要涉及文件的邏輯組織和物理組織，目錄的結(jié)構(gòu)和管理。

(5)作業(yè)管理。為用戶提供一個友好的環(huán)境，方便用戶組織自己的工作流程。

考點、3操作系統(tǒng)的類型

隨著計算機硬件技術(shù)的不斷發(fā)展，出現(xiàn)了多種類型的操作系統(tǒng)：手工操作

系統(tǒng)、批處理操作系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)及通用操作系統(tǒng)。隨著網(wǎng)絡(luò)技術(shù)

的發(fā)展，相應(yīng)地出現(xiàn)了網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)。下面將對主要的操作

系統(tǒng)進行簡單介紹。

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

批處理操作系統(tǒng)最大的特征就是用戶不直接操作計算機，而是將作業(yè)交給

系統(tǒng)操作員，由操作人員將作業(yè)成批地輸入計算機，然后按某種調(diào)度策略，順

序地執(zhí)行作業(yè)流中的每一個作業(yè)，以節(jié)省人工操作時間和提高機器的使用效

率。批處理操作系統(tǒng)又可分為單道批處理系統(tǒng)和多道批處理系統(tǒng)。

2.分時系統(tǒng)

分時系統(tǒng)中的分時指多個用戶通過終端可同時使用一臺計算機。操作系統(tǒng)

在接收用戶發(fā)出的請求后，按照時間片輪轉(zhuǎn)算法輪流分配給每個用戶一段CPU

時間，進行各自的處理。但對于每個單獨的用戶都仿佛自己獨占了整個計算機

系統(tǒng)分時系統(tǒng)主要有以下幾個方面的特點：

(1)多路性若干個用戶同時使用一臺計算機，從微觀上看是各用戶輪流使用

計算機；從宏觀上看是各用戶在并行工作。

(2)交互性二用戶可根據(jù)系統(tǒng)對清求的響應(yīng)結(jié)果，進一步向系統(tǒng)提出新的請

求。

(3)獨立性用戶之間可以相互獨立、互不十涉；系統(tǒng)保證各用戶程序運行的

完整性，不會發(fā)生相互混淆或破壞等現(xiàn)象。

(4)及時性系統(tǒng)對用戶的輸入及時做出啊應(yīng)。分時系統(tǒng)性能的主要性能指標(biāo)

之一是響應(yīng)時間，即從終端發(fā)出的命令到系統(tǒng)予以應(yīng)答聽需的時間。

3.實時系統(tǒng)

實時系統(tǒng)是指可對外部事件做出及時洞應(yīng)并在一定時間內(nèi)完成對事件的處

理的操作系統(tǒng)，其特點是及時響應(yīng)和高可靠性實時系統(tǒng)可分為實時控制系統(tǒng)和

實時信息處理系統(tǒng)兩大類。

4.個人計算機操作系統(tǒng)

個人計算機操作系統(tǒng)是指用于個人計算機上的操作系統(tǒng)，提供聯(lián)機交互功

能：這要求系統(tǒng)有友好的用戶接口和操作界面

5.網(wǎng)絡(luò)操作系統(tǒng)

網(wǎng)絡(luò)操作系統(tǒng)可通過通信設(shè)備將分散的具有獨立功能的多個計算機系統(tǒng)互

聯(lián)起來，用于實現(xiàn)信息交換、資源共享、互操作和協(xié)作處理的系統(tǒng)各用戶間都

要遵守一定的網(wǎng)絡(luò)協(xié)議來共享資源。

6.分布式操作系統(tǒng)

分布式操作系統(tǒng)可統(tǒng).管理和調(diào)度整個系統(tǒng)上的資源以實現(xiàn)各計算機之間

的資源共享和信息傳輸，對任務(wù)實行動態(tài)、合理的分配及并行的處理分布式系

統(tǒng)各個計算機之間無主次之分，為用戶提供一個標(biāo)準(zhǔn)的接口和統(tǒng)一的界面，使

用戶方便實現(xiàn)聽需要的操作。

考點、4研究操作系統(tǒng)的方法

研究操作系統(tǒng)可以從以下幾種不同的角度進行

1.資源管理觀點

從資源管理的觀點來看，操作系統(tǒng)的管理對象是計算機系統(tǒng)的資源，操作

系統(tǒng)則是管理系統(tǒng)資源的程序集合通常，把操作系統(tǒng)分為處理機管理、存儲管

理、設(shè)備管理、作業(yè)管理和文件管理等5個主要部分，由這幾部分程序的協(xié)調(diào)、

配合來完成用戶的作業(yè)要求。

2.進程觀點

這種觀點把操作系統(tǒng)看作由若干個可以同時獨立進行的程序和一個對這些

程序進行協(xié)調(diào)的核心所組成，這些同時運行的程序稱為進程，每個進程都可完

成某一特定的任務(wù)。

3.虛機器觀點

從服務(wù)用戶和機器功能擴充的觀點來看，操作系統(tǒng)為用戶使用計算機提供

了許多服務(wù)功能和良好的工作環(huán)境。

考點5操作系統(tǒng)的硬件環(huán)境

硬件是構(gòu)造操作系統(tǒng)的基礎(chǔ)，硬件對操作系統(tǒng)的構(gòu)造提供必要的支持。通

常，操作系統(tǒng)所涉及的硬件環(huán)境主要包括以下幾個方面。

1.特權(quán)指今與處理機狀態(tài)

(1)特權(quán)指令。只允許操作系統(tǒng)使用，而不允許一般用戶使用的指令。

(2)非特權(quán)指令。特權(quán)指令之外的指令稱做非特權(quán)指令，非特權(quán)指令的執(zhí)行

不影響其他用戶及系統(tǒng)。

(3)CPU狀態(tài)。CPU交替執(zhí)行操作系統(tǒng)程序和用戶程序。在執(zhí)行不同程序時，

根據(jù)運行程序為機器指是，的使用權(quán)限而將CPU置為不同的狀態(tài)CPU的狀態(tài)屬

于程序狀態(tài)字PSW中的一位。

2.中斷機制

中斷機制是現(xiàn)代計算機系統(tǒng)中的基本設(shè)施之一，它在系統(tǒng)中起著通信聯(lián)絡(luò)

的作用，以協(xié)調(diào)系統(tǒng)對各種外部事件的響應(yīng)和處理。

3.定時裝置

為了實現(xiàn)系統(tǒng)管理和維護，硬件必須提供時鐘，即定時裝置硬件時鐘通常

分為兩類：即絕對時鐘和相討時鐘。

3.2進程管理

考點6多道程序設(shè)計

1.程序的順序執(zhí)行

程序的順序執(zhí)行具有以下幾個特點：

(1)順序性。程序所規(guī)定的動作在機器上嚴格地按順序執(zhí)行，每個動作的執(zhí)

行都以前一個動作的結(jié)束為前提條件。

(2)封閉性。程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因

素的影響，即只有程序本身的動作才能改變程序的運行環(huán)境。

(3)可再現(xiàn)性。順序執(zhí)行的最終結(jié)果與程序運行的速度無關(guān)。

2.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化

程序執(zhí)行環(huán)境具有以下3個特點：

(1)獨立性。在多道環(huán)境下執(zhí)行的每道程序都是邏輯上獨立的，且執(zhí)行速度

與其他程序無關(guān)，執(zhí)行的起止時間也是獨立的。

(2)隨機性。在多道程序環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行的開始時間都是

隨機的。

(3)資源共享性。一般來說，多道環(huán)境下執(zhí)行程序的道數(shù)總是多于計算機系

統(tǒng)中CPU的個數(shù)，單CPU也是如此。

3.程序的并發(fā)執(zhí)行

程序的并發(fā)執(zhí)行是指為了充分利用系統(tǒng)資源，提高計算機的處理能力，在

計算機系統(tǒng)中有兩個或兩個以上的程序同時執(zhí)行的狀態(tài)。參與并發(fā)執(zhí)行的程序

稱為并發(fā)程序，并發(fā)程序執(zhí)行時的特點如下：

(1)各并發(fā)程序在執(zhí)行期間相互制約。

(2)程序與計算不是---對應(yīng)的關(guān)系。

(3)不可再現(xiàn)性。

4.多道程序系統(tǒng)

一般情況下，計算機要同時處理多個具有獨立功能的程序來增強系統(tǒng)的處

理能力和提高機器的處理效率。常采用并行操作技術(shù)來使系統(tǒng)的各種硬件資源

做到并行工作，即在計算機中，所運行程序的道數(shù)(吞吐量)多。程序在運行時

有如下3個特點：獨立性、隨機性和資源共享性。

考點7進程

1.進程的概念

進程是操作系統(tǒng)中最基本、最重要的概念。通常是指內(nèi)存區(qū)域中的一組指

令序列的執(zhí)行過程，是程序中具有一定獨立功能的關(guān)于某個數(shù)據(jù)集合的一次運

行活動，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。

2.進程的特性

(1)并發(fā)性可以同其他進程一道向前推進，即一個進程的第一個動作可以在

另一個進程的最后一個動作結(jié)束之前開始

(2)動態(tài)性是指進程對應(yīng)用程序的執(zhí)行過程，體現(xiàn)在兩方面：其一，進程動

態(tài)產(chǎn)生，動態(tài)消亡；其二，在進程的生命周期內(nèi)，其狀態(tài)動態(tài)變化。

(3)獨立性。一個進程是一個相對完整的調(diào)度單位，它可以獲得處理機并參

與并發(fā)執(zhí)行。

(4)交往性。一個進程在運行過程中可能與其他進程發(fā)生直接的或間接的相

互作用。

(5)異步性。每個進程按照各自獨立的、不可預(yù)知的速度向前推進。

3.進程與程序的區(qū)別與聯(lián)系

(1)進程是程序的執(zhí)行，是動態(tài)的；而程序是指令的集合，是靜態(tài)的。

(2)進程的存在是有限的，從運行到結(jié)束，是暫時的；而程序則是永久存在

的。

⑶進程包括程序、數(shù)據(jù)和進程控制塊(PCB)。

(4)一個程序可以有多個進程，一個進程也可以包含多個程序。

4.進程的狀態(tài)

進程在其存在過程中，它們的狀態(tài)在不斷發(fā)生變化。系統(tǒng)中的不同事件均

可以引起進程狀態(tài)的變化。

一般情況下，一個進程可分為以下3種狀態(tài)：

(1)就緒狀態(tài)。是指一個進程已經(jīng)具備運行條件，但由于沒有獲得CPU而不

能運行所處的狀態(tài)。一旦把CPU分配給它，該進程就可運行二處于就緒狀態(tài)的

進程可以是多個。

(2)運行狀態(tài)。是指進程已獲得CP1,并且在CPU上執(zhí)行的狀態(tài)。

(3)等待狀態(tài)。也稱阻塞狀態(tài)或封鎖狀態(tài)，是指進程因為等待某種事件發(fā)生

而暫時不能運行的狀態(tài)。

在一定的條件下，進程的狀態(tài)是可以相互轉(zhuǎn)換的。

5.進程控制塊

進程控制塊(ProcessControlBlock,簡稱PCB)是用來記錄進程狀態(tài)及其

他相關(guān)信息的數(shù)據(jù)結(jié)構(gòu),PCB是進程存在的唯一標(biāo)志，PCB存在則進程存在。系

統(tǒng)創(chuàng)建進程時會產(chǎn)生一個PCB,撤銷進程時，PCB也自動消失。

考點8進程控制

進程控制也稱進程管理，對進程實施有效的管理，包括進程的建立、棉I銷、

進程阻塞及進程的喚醒等。

進程控制是通過原語來實現(xiàn)的，用于進程控制的原語一般有：創(chuàng)建進程、

撤銷進程、掛起進程、激活進程、阻塞進程、喚醒進程及改變進程優(yōu)先級等。

1.創(chuàng)建原語

創(chuàng)建原語用于建立一個新的進程，其主要操作過程是先向系統(tǒng)申請一個空

閑的PCB,然后根據(jù)父進程提供的參數(shù)，將相關(guān)信息填入，最后返回一個進程的

內(nèi)部名。

2.撤稍原語

撤銷原語是用于撤銷一個已完成任務(wù)的進程，以釋放它所占用的所有的內(nèi)

部和外部資源。實質(zhì)上是撤銷PCB,有兩種撤銷策略，一種是只撤銷1個具有特

定標(biāo)識符的進程，另一種是撤銷該進程及其所有子孫進程。

3.阻塞原語

阻塞原語的作用是將進程由運行狀態(tài)變回阻塞狀態(tài)。具體過程是先中斷

CPU,將CPU的當(dāng)前狀態(tài)保存在PCB現(xiàn)場信息中，將進程的當(dāng)前狀態(tài)置為等待，

插人到等待隊列中去。

4.喚酸原語

喚醒原語的作用是將進程由阻塞狀態(tài)變?yōu)榫途w狀態(tài)，其操作過程是在等待

隊列中找出某進程，將它的當(dāng)前狀態(tài)置為就緒，然后將其從等待隊列中撤出并

插入到就緒隊列中去。

考點9進程的同步與互斥

1.臨界資源和臨界區(qū)

臨界資源是指一次只允許一個進程使用的資源：一個進程中訪問臨界資源

的那段程序代碼稱為臨界區(qū)。它們不允許兩個及以上的進程同時訪問或修改。

2.進程的同步

進程的同步運行是指進程之間的一種直接的協(xié)同工作關(guān)系，這些進程通過

相互合作來完成一項任務(wù)。

3.進程的互斤

進程間一種間接的相互作用構(gòu)成進程互斥。進程互斥的目的就是使某一進

程可以在某一時間內(nèi)獨占一些資源.

考點、10進程通信

1.信號量和P,V操作

解決進程的同步與互斥，既可用硬件實現(xiàn)，也可用軟件實現(xiàn)。

(1)在系統(tǒng)中信號量(S)是一個整數(shù)。當(dāng)S}-0時，表示可供并發(fā)進程使用

的資源實體數(shù)；當(dāng)S<0時，代表等待使用臨界區(qū)的進程數(shù)。

(2)只能通過P、V操作原語來改變P,V操作信號量的數(shù)值。P操作表示在當(dāng)

前進程申請的各種資源，V操作代表當(dāng)前進程釋放所占用的資源。P操作和V操

作都是低級進程通信原語。

(3)利用P、V操作可以解決并發(fā)進程間的互斥問題。

(4)利用P、V操作也可以解決并發(fā)進程間的同步問題。

2.高級通信機構(gòu)

對進程間大量信息的交換常采用消息通信的方法，高級通信原語不僅可保

證相互制約的進程的正確關(guān)系，同時還實現(xiàn)了進程之間的信息交換。該方法不

僅能實現(xiàn)進程間的通信，而且能實現(xiàn)進程間數(shù)據(jù)的傳送。下面分別介紹3種高

級進程通信。

(1)消息緩沖通信。消息緩沖通信的基本思想：系統(tǒng)管理一組消息緩沖區(qū)，

在每一個緩沖區(qū)可以存放一個信息。發(fā)送進程在發(fā)送消息前，在內(nèi)存中設(shè)置一

個發(fā)送區(qū)，裝人欲發(fā)送的消息，在申請到一個消息緩沖區(qū)以后，將發(fā)送區(qū)里的

消息發(fā)送到緩沖區(qū)中。

⑵管道通信。管道通信實質(zhì)上是利用外存來進行數(shù)據(jù)通信，傳輸數(shù)據(jù)量大,

但速度較慢。發(fā)送進程從管道的一端寫入數(shù)據(jù)，接收進程在需要的時候從管道

的另一端讀出數(shù)據(jù)。

⑶信箱通信。信箱通信指進程并不把消息直接發(fā)送給對方，而是將通信的

消息以信件的方式放在信箱內(nèi)。

考點、11進程典度

進程調(diào)度即處理機調(diào)度在多道程序系統(tǒng)中，進程數(shù)目往往大于處理機數(shù)目，

這會使進程相互爭奪處理機，必須按照一定的策略將crt分配給這些進程中

的某一進程

1.進程調(diào)度的功能

記錄系統(tǒng)中所有進程的狀態(tài)、優(yōu)先數(shù)及資源使用情況，CPU空閑時按一定算

法確定將CPU分配給哪個進程和分配多長時價。

2.進程調(diào)度方式

進程調(diào)度方式是指有優(yōu)先數(shù)更高的進程進入就緒隊列時，如何分配CPU,一

般包括剝奪方式和非剝奪方式兩種調(diào)度方式

3.進程調(diào)度算法

⑴先來先服務(wù)算法FCFS。該算法按照進程進入就緒隊列的先后順序來選擇

二即每當(dāng)進行進程調(diào)度時.總是把就緒隊列的隊首進程投入運行二

(2)時間片輪轉(zhuǎn)算法。這主要是分時系統(tǒng)中使用的一種調(diào)度算法。其基本思

想是：將CPU的處理時間劃分成一個個時間片，就緒隊列中的諸進程輪流運行

一個時間片。當(dāng)時間片結(jié)束時，就強迫運行進程讓出CPU,該進程進入就緒隊列，

等待下一次調(diào)度。同時，進程調(diào)度又去選擇就緒隊列中的另一個進程，分配給

它一個時間片，以投入運行。

影響時間片大小設(shè)置的主要因素有：系統(tǒng)響應(yīng)時間、就緒進程數(shù)目(終端數(shù)

目)和一計一算機處理能力。

(3)最高優(yōu)先級算法進程調(diào)度每次將處理機分配給具有最高優(yōu)先級的就緒

進程，進程的優(yōu)先級由進程優(yōu)先數(shù)決定

進程優(yōu)先數(shù)的設(shè)置可以是靜態(tài)的，也可以是動態(tài)的。

最高優(yōu)先數(shù)算法又可與不同的CPU方式結(jié)合起來，形成可剝奪式最高優(yōu)

先數(shù)算法和不可剝奪式最高優(yōu)先數(shù)算法。

考點12死鎖

1.死鎖的概念

死鎖是指在多道程序系統(tǒng)中，兩個或兩個以上的進程無限期地等待永遠不

會發(fā)生的事件，得不到所需資源因而不能運行的狀態(tài)處于死鎖狀態(tài)的進程稱為

死鎖進程。

死鎖產(chǎn)生的原因：一是系統(tǒng)資源不足；二是多道程序運行時，進程的推進

順序不合理。

2.產(chǎn)生死鎖的必要條件

(1)互斥條件。進程互斥使用資源，任一時刻一個資源只為一個進程獨占，

其他進程若請求一個已被占用的資源，只能等占用者釋放后才能使用

(2)不可剝奪條件(不可搶rtl-)。進程所獲得的資源在未使用完畢之前，不

能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放

⑶部分分配(占有等待)。進程每次申請它所需要的一部分資源，在申請新

的資源的同時，繼續(xù)占用已分配到的資源。

⑷循環(huán)等待：存在一個進程環(huán)路，環(huán)路中每一個進程已獲得的資源同時被

下一個進程所請求。

3.資源分配圖

死鎖問題可用一個有向圖來表示。資源分配圖就是描述進程、資源及它們

之間關(guān)系的有向圖。當(dāng)進程請求資源時，系統(tǒng)檢查并發(fā)進程組是否構(gòu)成資源的

請求環(huán)路。存在環(huán)路，可能存在死鎖；不存在環(huán)路，一定沒有死鎖。

4.死鎖預(yù)防

只要破壞死鎖產(chǎn)生的4個必要條件之一，就可有效避免死鎖的產(chǎn)生，主要

有以下幾種方法：

⑴破壞互斥條件

(2)破壞不可剝奪條件。

⑶破壞部分分配條件二

(4)破壞循環(huán)等待條件

5.死鎖解除

當(dāng)發(fā)現(xiàn)死鎖后，可采用以下兩種方法來解除死鎖：

(1)資源剝奪法。從一些進程那里強行剝奪足夠數(shù)量的資源分配給死鎖進

程，以解除死鎖狀態(tài)

⑵撤銷進程法。按照某種策略逐個地撤銷死鎖進程，直到獲得為解除死鎖

所需要的足夠使用的資源為按照什么原則撤銷進程，實用而又簡便的方法就是

撤銷那些代價最小的進程，或者撤銷進程的數(shù)量最少。

考點、13線程

1.線程的概念

線程是進程中的一個實體，是CPU調(diào)度和分派的基本單位

2.線程的屬性

(1)每個線程有一個唯一的標(biāo)識符和一張線程描述表。

(2)不同的線程可以執(zhí)行相同的程序。

(3)同一級的進程中的各個線程共享該進程的地址空間。

(4)線程是處理器的獨立調(diào)度單位，多個線程是可以并發(fā)執(zhí)行的。

(5)一個線程被創(chuàng)建以后便開始了它的生命周期，直到終止。

3.線程與進程的比較

線程與進程的主要區(qū)別表現(xiàn)在以下幾個方面：

(1)調(diào)度。在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和獨立調(diào)度、分派的

基本單位只有進程，而在引線程的操作系統(tǒng)中，則把線程作為調(diào)度和分派的基

本單位，把進程作為資源擁有的基本單位，使傳統(tǒng)進程兩個屬性分開，從而使

線程能輕裝運行，這樣可以顯著地提高系統(tǒng)的并發(fā)程度。在同一進程中，線程

的切換不會引起進程切換，在由一個進程中的線程切換到另一進程中的線程時，

將會引起進程切換。

(2)并發(fā)性在引入線程的操作系統(tǒng)中，不僅進程之間可以并發(fā)執(zhí)行，而且在

一個進程中的多個線程之也可以并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性,

從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)的吞吐。在引入了線程的操作系統(tǒng)中，

可以在一個文件服務(wù)進程中設(shè)置多個服務(wù)線程。當(dāng)?shù)谝粋€線程等待時，件服務(wù)

進程中的第二個線程可以繼續(xù)運行；當(dāng)?shù)诙€線程封鎖時，第3個線程可以繼

續(xù)執(zhí)行，從而顯著地高了文件服務(wù)的質(zhì)量及系統(tǒng)的吞吐量C

(3)擁有資源不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)，進程都是

擁有資源的一個獨立單位。一般地說，線程自己不擁有系統(tǒng)資源(也有一點兒必

不可少的資源)，但它可以訪問其隸屬進程的資源，即一個進程的代碼段、數(shù)據(jù)

段及系統(tǒng)資源(如已打開的文件、1/0設(shè)備等)，可供同一個進程的其他所有線共

享

(4)系統(tǒng)開銷。由于在創(chuàng)建或撤銷進程時，系統(tǒng)都要為之分配或回收資源，

如內(nèi)存空間、1/0設(shè)備等。因此操作系統(tǒng)所付出的開銷將顯著地大于在創(chuàng)建或撤

銷線程時的開銷。類似地，在進行進程切換時，涉及到整個當(dāng)前進程CPU環(huán)境

的保存及新近被調(diào)度運行的進程的CPU環(huán)境的設(shè)置。而線程切換只需保存和設(shè)

置少量寄存器的內(nèi)容，并不涉及存儲器管理方面的操作?？梢?，進程切換的開

銷也遠大于線程切換的開銷。

3.3作業(yè)管理

考點14操作系統(tǒng)與用戶之間的接口

操作系統(tǒng)向用戶提供了兩類接口：一類是程序級接口，另一類是作業(yè)級接

口。

1.程序級接口

程序級接口是由一組系統(tǒng)調(diào)用命令組成的。系統(tǒng)調(diào)用命令可以看成是機器

指令的擴充，用戶通過在程序中使用這些系統(tǒng)調(diào)用命令來請求操作系統(tǒng)提供服

務(wù)。

2.作業(yè)級接口

作業(yè)級接日是為用戶在作業(yè)一級請求操作系統(tǒng)為其服務(wù)而設(shè)置的，用戶可

通過這類接口組織控制作業(yè)的工作流程。作業(yè)級接1-1可分為聯(lián)機接口和脫機

接口兩類。

考點15作業(yè)管理

作業(yè)就是用戶在一次事務(wù)處理過程中，要求計算機系統(tǒng)所做工作的總稱。

一個作業(yè)分為幾個步驟，每個步驟稱為作業(yè)步。在批處理系統(tǒng)中將作業(yè)安排在

輸人設(shè)備上，然后依次讀人系統(tǒng)進行處理，從而形成了作業(yè)流作業(yè)管理分為作

業(yè)調(diào)度和作業(yè)控制兩部分。

1.作業(yè)調(diào)度

作業(yè)調(diào)度的主要任務(wù)是：按照各種調(diào)度算法，從后備作業(yè)隊列中挑選一批

合理搭配的作業(yè)。進入運行狀態(tài)，同時，為選中的作業(yè)分配內(nèi)存和外部設(shè)備等

資源，為其建立有關(guān)的進程，當(dāng)作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，做好釋放資源

等善后處理工作。

⑴作業(yè)的狀態(tài)：一個作業(yè)進入系統(tǒng)到運行結(jié)束，要經(jīng)過4種狀態(tài)的變遷，

即提交狀態(tài)、后備狀態(tài)、執(zhí)行狀態(tài)和完成狀態(tài)

(2)作業(yè)調(diào)度算法：常用的作業(yè)調(diào)度算法有以下幾種

先來光服務(wù)算法

短作業(yè)優(yōu)先算法

最高響應(yīng)比作業(yè)優(yōu)先算法

優(yōu)光數(shù)算法

2.作業(yè)控制

作業(yè)控制是指用戶或系統(tǒng)操作員對作業(yè)運行的全過程控制。作業(yè)控制可以

分為聯(lián)機作業(yè)控制和脫機作業(yè)控制兩種方式。

3.4存儲管理

考點16基本概念

1.存儲器

存儲器是計算機系統(tǒng)中的重要資源，必須重點管理的資源。存儲器可分為3

類：主存儲器、外存儲器和高速緩存

2.存儲管理的主要目的和功能

(1)內(nèi)存空間的分配和回收。操作系統(tǒng)為每個進程分配一定的內(nèi)存空間，進

程結(jié)束時要收回內(nèi)存空間。

(2)內(nèi)存空間的共享。內(nèi)存共享是指兩個或多個進程共用內(nèi)存中相同的區(qū)

域，其目的是節(jié)省內(nèi)存空間，實現(xiàn)進程間通信，提高內(nèi)存空間的利用效率。存

儲共享的內(nèi)容可以是程序的代碼，也可以是數(shù)據(jù)。

(3)存儲保護。在多道程序并發(fā)運行的環(huán)境下，內(nèi)存中系統(tǒng)程序和數(shù)據(jù)段可

供不同的用戶進程共享。為了保護存儲區(qū)內(nèi)各類程序和信息不被破壞和干擾，

保證系統(tǒng)正常運行，需要對內(nèi)存中的程序和數(shù)據(jù)段采取保護措施。內(nèi)存保護一

般有防止地址越界和防止操作越權(quán)兩種方式。

(4)地址映射。地址映射又稱為地址的重定位。地址有物理地址和邏輯地址

(又稱相對地址)兩個概念。

程序被調(diào)入主存時，首先要將程序的邏輯地址變換為物理地址，包括相應(yīng)

地調(diào)整程序中有關(guān)地址的指令，這個過程稱為地址重定位。重定位的方法有兩

種：靜態(tài)地址重定位和動態(tài)地址重定位

(5)內(nèi)存擴充。系統(tǒng)中內(nèi)存容量是有限的，操作系統(tǒng)為了滿足用戶的作業(yè)對

內(nèi)存空間的需要，以某種方式將內(nèi)、外存聯(lián)合起來，向用戶提供一個虛擬存儲

器，其容量比實際內(nèi)存要大得多。

3.碎片管理

碎片是指內(nèi)存中出現(xiàn)的一些零散的小空閑區(qū)域—解決碎片的方法是緊湊

(拼接)技術(shù).

考點、17分區(qū)存儲管理

分區(qū)式存儲管理是滿足多道程序運行的一種存儲管理技術(shù)，其基本思想是

將內(nèi)存劃分為若十連續(xù)區(qū)域，稱為分區(qū)，每個分區(qū)裝入一個運行作業(yè)。按分區(qū)

的方式，又可分為同定分區(qū)和可變分區(qū)。

1.固定介區(qū)

固定分區(qū)是指在處理作業(yè)前將內(nèi)存劃分為若十個固定大小的存儲區(qū)，每個

分區(qū)裝入一個作業(yè)，到該作業(yè)完成后收回該區(qū)。固定分區(qū)會浪費一些存儲空間。

2.可變介區(qū)

可變分區(qū)是指在作業(yè)裝入內(nèi)存時進行分區(qū)，分區(qū)的大小正好與作業(yè)要求的

存儲空間相等，分區(qū)的個數(shù)與大小都是不確定的。這種分區(qū)方式的缺點就是會

引起碎片的產(chǎn)生。

系統(tǒng)利用空閑區(qū)表來管理內(nèi)存中的空閑分區(qū)，常用的分配策略有：最先適

應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法。系統(tǒng)為正在運行的進程提供一對硬件

寄存器，可采用兩種方式：

⑴基址寄存器和限長寄存器。

(2)上界寄存器和下界寄存器。

考點18頁式存儲管理

1.基本概念

⑴內(nèi)存分配。頁式存儲管理把內(nèi)存空間分為相同大小的存儲區(qū)稱為“塊”，

用戶的作業(yè)地址空間也分成與“塊”同樣大小的若干個片段，稱之為“頁頁

和塊從零開始按順序編號，分別稱