研究生入學(xué)考試北航計算機軟件技術(shù)基礎(chǔ)復(fù)習(xí)課2010

2010軟件技術(shù)基礎(chǔ)復(fù)習(xí)課1/1001/100程序與軟件程序是計算機指令的序列，是一個用計算機語言描述的某一問題的解決步驟。這些指令非常簡單（簡單的四則運算、邏輯運算、數(shù)據(jù)傳送和跳轉(zhuǎn)指令）但它們的組合卻能完成非常復(fù)雜的任務(wù)。程序還有一個更為廣義的性質(zhì),它是信息。我們知道信息只有大小而無形狀,信息可用多種媒體(聲、文、圖)表示,信息的傳遞總要借助某種介質(zhì)(媒體)。信息作為商品要以有形的介質(zhì)作為載體進行交易,故稱軟件(Software)。軟件是計算機程序，方法，規(guī)則，相關(guān)的文檔以及在計算機上運行它時所必需的數(shù)據(jù)。1/100程序的特性程序的靜態(tài)與動態(tài)屬性–程序的表示是靜態(tài)的，但程序必須能夠運行，否則毫無用處。程序由程序語言抽象的符號表達–二進制機器碼，它是機器可以直接“讀懂”的語言。但書寫時人們常用八進制或十六進制表示。–匯編語言，用一些特殊描述符表示操作符和操作數(shù)，它與具體的硬件相關(guān)，不可移植。–高級語言，類似人類語言，易懂，可移植。*程序設(shè)計的發(fā)展過程------語言愈高級，愈自動，翻譯程序的任務(wù)愈重1/100高級程序設(shè)計語言實現(xiàn)計算的方式計算機只認(rèn)識機器語言，高級語言程序必須經(jīng)過翻譯才能被機器接收。把一種語言翻譯成另一種語言的程序叫翻譯器。直接翻成目標(biāo)（機器）語言的有兩種做法：–編譯器–解釋器1/100高級語言程序的編譯執(zhí)行–高級語言源程序經(jīng)編譯后得到目標(biāo)碼程序，但它還不能立即裝入

機器執(zhí)行，因為它一般不夠完整。有些函數(shù)是標(biāo)準(zhǔn)化了的，事先

已作為目標(biāo)碼存放在機器中，無需編寫，當(dāng)接到用戶的連接指示，機器將把連接程序（或連接器Linker）裝入內(nèi)存并開始工作，找出要調(diào)用哪些標(biāo)準(zhǔn)程序，到庫中找出被調(diào)用的模塊，輸入到內(nèi)存

并連接上，形成可執(zhí)行程序。然后是加載（Loading，裝入到內(nèi)存中合適的位置，此時得到的是內(nèi)存中的絕對地址），最后執(zhí)行（Running）得出結(jié)果。–例如：C語言中直接調(diào)用

sin（）函數(shù)–特點：編譯型語言可進行優(yōu)化（或多次優(yōu)化），目標(biāo)碼效率很高，是目前軟件開發(fā)的最主要編程語言。用這些語言編寫的原程序，都要進行編譯，連接，才能生成可執(zhí)行程序。C/C++,Pascal,Ada,FORTRAN等都是編譯型語言。源程序.C目標(biāo)程序.obj可執(zhí)行程序.exe結(jié)果編譯1/100連接執(zhí)行1/100高級語言程序的解釋執(zhí)行：–解釋執(zhí)行需要有一個解釋器(Interpreter)，它將源代碼逐句讀入：作詞法分析，建立內(nèi)部符號表；作語法和語義分析，即以中間碼建立語法樹，并作類型檢查把每一語句壓入執(zhí)行堆棧，壓入后立即解釋執(zhí)行。–特點：解釋執(zhí)行只看到一個語句，無法作整個程序優(yōu)化。例如，BASIC、VB等。解釋器不大，工作空間也不大、能根據(jù)程序執(zhí)行情況決定下一步做什么（人工智能經(jīng)常是這樣的）是它的優(yōu)點解釋執(zhí)行難于優(yōu)化、效率較低，這是這類語言的致命缺點。1/100Object-Oriented

language面向?qū)ο蟮恼Z言A

programming

language

that

reflects

theconcepts

of

object-oriented

programming.Example:SMALLTALK

and

C++.一種反映面向?qū)ο缶幊谈拍畹某绦蛟O(shè)計語言。例如SMALLTALK和C++對象、類、封裝、繼承面向?qū)ο螅綄ο螅悾^承＋通信（消息）1/100對象的概念：程序?qū)ο鬄槲覀兲峁┝酥苯用枋隹陀^世界對象的有力手段。每個對象可以用其一組屬性和它可以執(zhí)行的一組操作來定義。對象中的數(shù)據(jù)改稱為對象的屬性(Attribute)，操作改稱為對象的方法(Method)，即改變屬性的方法。對象間相互只有通信，叫發(fā)消息（Message)。因?qū)ο笫亲灾鞯某绦驅(qū)嶓w，發(fā)消息者可等可不等。接受消息的對象可以立即響應(yīng)，也可以稍晚些時間響應(yīng)，松弛了對象間的引用耦合，為并發(fā)程序，事件驅(qū)動程序提供了程序?qū)崿F(xiàn)的技術(shù)基礎(chǔ)。使用者就不必關(guān)心對象內(nèi)部情況，只按接口規(guī)定的形式向它發(fā)消息就可以了，如對象的設(shè)計者發(fā)現(xiàn)某個操作的算法（過程體）不好，重新改寫一個換了，使用者也不用知道，只要接口形式不變就行。1/100類與對象類是一組具有相同數(shù)據(jù)結(jié)構(gòu)和相同操作的對象的集合。沿用程序中表達數(shù)據(jù)的抽象辦法：定義一個類型、聲明該類型的變量，我們定義一類對象然后聲明它的不同實例（Instance):Dim

v

As

Double ‘v是雙精型的數(shù)據(jù)變量Dim OK

As

Command

Button ‘OK是按鈕類的對象變量這個類Command

Button是系統(tǒng)事先定義好的，OK是它的實例對象。ＯＫ有著和Command

Button一樣的屬性和方法，只是要給出各屬性的值。類是生成實例的樣板，是實例加工廠（給出一組屬性值就是一實例）。正是因為變量－－類型和實例－－類的相似性，許多語言（如：Ｃ＋＋）

都把類看作是類型，類的定義如同以簡單的類型構(gòu)造復(fù)雜的數(shù)據(jù)類型一樣。只不過類定義時還要定義類的方法（操作復(fù)雜類型的過程（或函數(shù)）在復(fù)

雜（抽象）類型之外定義）。1/100類繼承類的封裝保證了程序的模塊獨立性，調(diào)試程序比較方便。但相同的數(shù)據(jù)，相同的操作，每個類封裝一套就太繁雜了。繼承能解決這個問題。每個類都可以派生許多子類，子類（subclass）繼承父類（parentclass）的屬性和方法。子類可以派生它的子類……，老祖宗的屬性和方法可以一代一代傳到最新派生的(子)類?；悾╞aseclass）中的屬性和方法定義在派生類就不用寫了，只定義派生類’自己的’屬性和方法，這就構(gòu)成樹狀的繼承體系，我們把這個類繼承體系叫類庫。類的多重繼承讀C＋＋程序1/100四常用算法枚舉法–枚舉法亦稱窮舉法，它的基本思想是：首先依據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完。若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則本題無答案。–枚舉法的實質(zhì)是枚舉所有可能的解，用檢驗條件判斷定哪些是有用的，哪些是無用的，而題目往往就是檢驗條件。枚舉法的特點是算法簡單，但有時運算量大，對于可確定解的取值范圍且又一時找不到其他更好的算法時，就可以用它。例題：百雞問題(28_17)*(1_6)=4401852迭代法重復(fù)同樣步驟，可以逐次求得更精確的值。這一過程即為迭代過程.使用迭代法構(gòu)造算法的基本方法是：首先確定一個合適的迭代公式，選取一個初始近似值以及解的誤差，然后用循環(huán)處理實現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差。并認(rèn)為最后一次迭代得到的近似值為問題的解。這種迭代方法稱為逼近迭代。1/1001/100遞歸法–遞歸是構(gòu)造計算機算法的一種基本方法。如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的，遞歸過程必須有一個遞歸終止條件，即存在“遞歸出口”。無條件的遞歸是毫無意義的。–

f(n)=n!=n*(n-1)!=n*f(n-1)遞推法–

所謂遞推法，它的數(shù)學(xué)公式也是遞歸的（如：f(n)=n!=n*(n-1)!=n*f(n-1)

）。只是在實現(xiàn)計算時迭代方向相反。從給定邊界出發(fā)逐步迭代到達指定計算參數(shù)。它不需反復(fù)調(diào)用自己（節(jié)省了很多調(diào)用參數(shù)匹配開銷）。效率較高。–遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計算中最常見。1/100–遞歸與遞推是既有區(qū)別又有聯(lián)系的兩個概念。遞推是從已知的初始條件出發(fā)，逐次遞推出最后所求的值。遞歸則是從需求的函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值。一般說來，一個遞推算法總可以轉(zhuǎn)換為一個遞歸算法。遞歸算法往往比非遞歸算法要付出更多的執(zhí)行時間，盡管如此，由于遞歸算法編程序非常容易，各程序設(shè)計語言隨計算機速度提高都設(shè)有遞歸語言機制。此外，用遞歸過程來描述算法不僅非常自然，而且證明算法的正確性也比相應(yīng)的非遞歸形式容易很多，因此，遞歸是算法設(shè)計的基本技術(shù)。1/100鏈表–用一組任意單元表示數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系。它包含兩個域，一個表示數(shù)據(jù)本身，一個表示數(shù)據(jù)元素間的關(guān)聯(lián)。這樣一個整體成為一個結(jié)點。結(jié)點中表示關(guān)聯(lián)的部分成為指針域，內(nèi)部存放指針或鏈。–鏈表一般有單鏈表、雙向鏈表和循環(huán)鏈表等。a1La2a3a4a5

^Head單鏈表(線性鏈表)單鏈表就是鏈?zhǔn)酱鎯Φ木€性表，其結(jié)點除信息域外還含有一個指針域，用來指出其后繼結(jié)點的位置。單鏈表的最后一個結(jié)點沒有后繼結(jié)點，

它的指針域為空(記為NULL或∧)。另外還需要設(shè)置一個指針head，指向單鏈表的第一個結(jié)點。鏈表的一個重要特點是插入、刪除運算靈活方便，不需移動∧結(jié)點，只要改變結(jié)點中指針域的值即可。infonext1/100信息域指針域單鏈表節(jié)點結(jié)構(gòu)單鏈表邏輯示意圖abpabpc單鏈表單鏈表插入結(jié)點時的情況單鏈表刪除結(jié)點時的情況abxsp1/100單鏈表結(jié)點插入和刪除棧–除了前面講的線性表外，棧(STACK)也是一種特殊的線性表，是一種“后進先出”的結(jié)構(gòu)，也是使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)之一。它的運算規(guī)則受到一些約束和限定，故又稱限定性數(shù)據(jù)結(jié)構(gòu)。棧的結(jié)構(gòu)特點貨棧穿衣服的順序子彈壓入子彈夾摞盤子a

n┆a

3a

2a

1進棧出棧棧頂

top棧底1/100棧是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂(top)，表頭稱為棧底(bottom)。表中無元素時稱為空棧。在右上圖所示的棧中，棧中的元素按a1,a2,a3,…an的順序進棧，a1稱為棧底元素。新元素進棧要置于an之上，刪除或退棧必須先對an進行，即棧的操作是按先進后出的原則進行。因此，棧又稱為LIFO表(LastInFirstOut的縮寫)表。棧的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)，如右圖所示。棧底1/100棧頂top樹的存儲結(jié)構(gòu)–直觀地看，樹的存儲結(jié)構(gòu)可以采用具有多個指針域的多重鏈表，結(jié)點中指針域的個數(shù)應(yīng)由樹的度來決定。例如，下圖中樹的度為3，可以采用含有3個指針域的結(jié)點的多重鏈表作存儲結(jié)構(gòu)。但在實際應(yīng)用中，這種存儲結(jié)構(gòu)并不方便，一般將樹轉(zhuǎn)化為二叉樹表示，再進行處理。1/1001/100二叉樹的存儲結(jié)構(gòu)–通常使用具有兩個指針域的二叉鏈表作二叉樹的存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)如圖(a)所示，圖中LC為左指針域，指向結(jié)點的左子樹；RC為右指針域，指向結(jié)點的右子樹。1/100二叉樹的存儲結(jié)構(gòu)–圖(b)所示為一個二叉樹的二叉鏈表。有時亦可用

數(shù)組的下標(biāo)來模擬指針，即開辟三個一維數(shù)組DATA，

LC和RC分別存放結(jié)點的元素及其左、右指針，如圖

(c)所示。用一個結(jié)構(gòu)數(shù)組也可以。1/1001/100樹和二叉樹的遍歷(周游)–對于樹形結(jié)構(gòu)的運算很多，但最重要、使用最為廣泛的是遍歷。遍歷一個樹形結(jié)構(gòu)就是按一定的次序，系統(tǒng)地訪問該結(jié)構(gòu)中的所有結(jié)點，使每個結(jié)點恰被訪問一次。我們將重點討論二叉樹的遍歷。樹的遍歷–根據(jù)樹的遞歸定義，有兩種遍歷樹的方法：–先根(次序)遍歷：若樹中只有一個根結(jié)點，則訪問樹的根結(jié)點；否則，首先訪問樹的根結(jié)點，然后依次先根遍歷每棵子樹。–后根(次序)遍歷：若樹中只有一個根結(jié)點，則訪問樹的根結(jié)點；否則，首先依次后根遍歷每一棵子樹，然后訪問樹的根結(jié)點。1/100二叉樹的遍歷–分析二叉樹的結(jié)構(gòu)特性可知，一棵非空的二叉樹是由根結(jié)點、左子樹、右子樹三個基本部分組成，則遍歷二叉樹只要依次遍歷這三部分即可。使用自然語言描述的遍歷二叉樹的算法如下：–前序遍歷二叉樹算法（DLR）：若二叉樹不空，則依次進行下列操作：訪問根結(jié)點；前序遍歷左子樹；前序遍歷右子樹。1/100–中序遍歷二叉樹的算法（LDR）為：若二叉樹不空，則依次進行下列操作：中序遍歷左子樹；訪問根結(jié)點；中序遍歷右子樹。–后序遍歷二叉樹的算法（LRD）為：若二叉樹不空，則依次進行下列操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點。對于右圖，使用前序遍歷，則處理順序為：ABEFCGDHIJ對于右圖，使用中序遍歷，則處理順序為：EFBGCHIJDA對于右圖，使用后序遍歷，則處理順序為：FEGJIHDCBA1/100圖的存儲–圖的結(jié)構(gòu)復(fù)雜，應(yīng)用廣泛，因此其存儲表示方法也多種多樣。下面給出兩種最常用的存儲表示方法。圖的相鄰矩陣表示法–相鄰矩陣是表示結(jié)點間的相鄰關(guān)系的矩陣，若G是一個具有n個結(jié)點的圖，則G的相鄰矩陣是如下定義的n×n矩陣。1，若（Vi，Vj）是圖G的邊

A[i,j]＝0，若（Vi，Vj）不是圖G的邊1/1001/1001/100用相鄰矩陣表示圖，占用的存儲單元個數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。一個n個結(jié)點的圖，若其邊數(shù)比n少得多，那么它的相鄰矩陣中就會有很多零元素，占用很多空間來存儲零元素當(dāng)然是個浪費。如果用鄰接表表示法來表示圖，則占用的存儲單元個數(shù)不但與圖中結(jié)點個數(shù)有關(guān)，而且與邊數(shù)有關(guān)。同是n個結(jié)點的圖，如果邊數(shù)少，則占用的存儲單元也少。1/100圖的鄰接表表示法–結(jié)點表、邊表–一個順序存儲的結(jié)點表。結(jié)點表有n個表目，每個表目對應(yīng)于圖的一個結(jié)點。每個表目包括兩個字段：一個是結(jié)點的數(shù)據(jù)或指向結(jié)點數(shù)據(jù)的指針；另一個是指向此結(jié)點的邊表的指針。圖的每個結(jié)點都有一個邊表，一個結(jié)點的邊表的每個表目對應(yīng)于該結(jié)點相關(guān)聯(lián)的一條邊。–n個鏈接存儲的邊表。每個表目包括兩個字段：一個是與此邊相關(guān)聯(lián)的另一個結(jié)點在結(jié)點表中的序號；另一個是指向邊表的下一個表目的指針。1/100分塊查找分塊查找又稱索引順序查找，它是一種性能介于順序查找和二分查找之間的查找方法，其特點是要求文件中記錄關(guān)鍵字“分塊有序”。所謂“分塊有序”指的是文件可按關(guān)鍵字分成若干塊，且前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字，而各塊內(nèi)部的關(guān)鍵字不一定有序。1R(1:20)

171/1002

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

2008

21

19

31

33

22

25

42

37

40

52

61

73

78

55

94

88

79

85分塊查找分塊查找的基本思想是：先抽取各塊中的最大關(guān)鍵字構(gòu)成一個索引表，由于文件中的記錄按關(guān)鍵字分塊有序，則索引表呈遞增有序狀態(tài)。查找分兩步進行，第一步先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊，第二步在已限定的那一塊中進行順序查找。下圖：其記錄符合分塊有序約定，每塊包含4個記錄，第一塊記錄的最大關(guān)鍵字21小于第二塊記錄中的最小關(guān)鍵字22等。1/1001/100插入排序插入排序的基本思想是：每步將一個待排序的記錄，按其關(guān)鍵碼值的大小插入到前面已排序的文件的適當(dāng)位置上，直到全部插完為止。直接插入排序–在已排好的序列中用順序法查找插入位置，找到后將該位置原來的記錄及其后面所有記錄順序后移一個位置，空出該位置來插入新記錄。用直接插入法排序n個記錄的文件，關(guān)鍵碼比較次數(shù)為n2量級，記錄移動個數(shù)也為

n2

量級。1/100初始關(guān)鍵字序列：[64]

57

89

6

2464]

7

89

6

242424第一次排序：

[5第二次排序：

[5第三次排序：

[5第四次排序：

[5第五次排序：

[57

64]

89

67

64 89]

66

7

64

89]

246

7

24

64

89]1/100選擇排序選擇排序的基本思想是：每次從待排序的記錄中選出關(guān)鍵字最小(或最大)的記錄，順序放在已排序的記錄序列的最后，直到全部排完為止。直接選擇排序是從待排序的所有記錄中，選取關(guān)鍵字最小的記錄并將他與原始序列中的第一個記錄交換位置；然后從去掉了關(guān)鍵字最小的記錄的剩余記錄中選擇關(guān)鍵字最小的記錄并將他與原始序列中第二個記錄交換位置，…，如此重復(fù)，直到序列中全部記錄排序完畢。1/100選擇排序（續(xù)）初始關(guān)鍵字序列：[64]5789624第一次排序：[5]64789624第二次排序：[56]7896424第三次排序：[567]896424第四次排序：[56724]6489第五次排序：[5672464]89最后結(jié)果序列：

[5

6

7

24

64

89]1/100操作系統(tǒng)的功能四大管理處理機（CPU）管理存儲器管理設(shè)備管理文件管理作業(yè)管理1/100處理機（CPU）管理處理機管理的主要功能就是對處理機的分配、調(diào)度實施最有效的管理，以最大限度地提高處理機的處理能力。

在多任務(wù)環(huán)境中，處理機的分配、調(diào)度都是以進程為單位的。所以處理機的管理可以歸結(jié)為進程管理。

進程管理的主要任務(wù)是為運行程序創(chuàng)建進程，進程調(diào)度，進程間通訊和最后程序運行完成后撤消進程。

需要注意的是，進程管理是由操作系統(tǒng)來完成的，用戶并不會感覺到它的存在。1/100存儲器管理

為每個進程分配內(nèi)存，當(dāng)進程被撤消時回收分配出去的內(nèi)存是內(nèi)存管理的主要內(nèi)容。

內(nèi)存保護，每個進程只能在自己的內(nèi)存空間中運行，否則會相互干擾甚至于破壞整個系統(tǒng)。

內(nèi)存映射，把應(yīng)用程序的邏輯地址正確地映射到物理地址。

操作系統(tǒng)最好能提供一種“虛擬”的內(nèi)存也就是比實際內(nèi)存大得多的“內(nèi)存”供應(yīng)用程序使用。1/100設(shè)備管理

計算機系統(tǒng)中的設(shè)備主要是指諸如鍵盤、鼠標(biāo)、顯示器、打印機、掃描儀、數(shù)碼相機、磁盤、

磁帶、光盤驅(qū)動器等輸入、輸出設(shè)備。

計算機系統(tǒng)的輸入、輸出設(shè)備千差萬別種類繁多，所以，設(shè)備管理除了對設(shè)備進行分配、調(diào)度，提高整個計算機系統(tǒng)的運行效率之外，還必須屏蔽各種設(shè)備的物理特性，向用戶提供一個方便、易用、高效的操作界面。1/100文件管理

計算機中的所有信息都是以文件的形式保存在外部存儲介質(zhì)上，供授權(quán)用戶使用的。

操作系統(tǒng)必須提供一套高效、方便、易用的信息管理機制，我們把它稱作文件系統(tǒng)。

文件系統(tǒng)應(yīng)當(dāng)具有這樣一些功能：數(shù)據(jù)存儲空間的分配、回收；文件的讀寫和查找機制和安全機制。

最后，操作系統(tǒng)還應(yīng)當(dāng)屏蔽掉各種存儲設(shè)備的物理特性，向用戶提供一套簡單、方便、易用的服務(wù)接口。1/100進程管理進程：進程是一個可并發(fā)執(zhí)行的程序在其數(shù)據(jù)集上的一次運行，是操作系統(tǒng)進行系統(tǒng)資源分配的單位和獨立運行的基本單位。操作系統(tǒng)用于組織它必須完成的多項任務(wù)、實現(xiàn)并發(fā)執(zhí)行的一種手段。進程擁有4個特性。進程的狀態(tài)

進程之間的狀態(tài)轉(zhuǎn)換并非都是可逆的。事實上，進程既不能從阻塞變?yōu)檫\行，也不能從就緒變?yōu)樽枞?/p>

進程之間的狀態(tài)轉(zhuǎn)換并非都是主動的，在很多情況下是“被動的”。事實上，只有“運行阻塞”的轉(zhuǎn)換是進程的主動行為，其它都是被動的。一個進程在任一指定時刻必須且只能處于上述諸狀態(tài)中的某一種狀態(tài)。當(dāng)進程處于運行態(tài)時，它是微觀意義下的運行。從宏觀來說，不管進程處于何1/100種狀態(tài)，它都是“正在運行”，用戶無從知道進程到底處于哪個狀態(tài)。線程－thread

為了描述進程狀態(tài)的變化和對進程進行資源分配和運行調(diào)度，加大了系統(tǒng)在空間方面和時間方面的開銷。－－>線程

線程是進程內(nèi)的一個可調(diào)度實體、是一個執(zhí)行單元、輕量進程。

引入進程是為了實現(xiàn)并發(fā)執(zhí)行，提高系統(tǒng)資源的利用率和吞吐量。1/1001/100線程具有進程的四大特征，線程包含于進程中并使用進程的地址空間。線程是可以獨立地被調(diào)度和執(zhí)行的，因此可以方便、快捷地實現(xiàn)并發(fā)操作。屬于同一個進程的若干線程共享進程的地址空間和其他資源，所以，線程之間的切換比進程之間的切換要快得多。1/100存儲管理

存儲管理研究的問題：如何更好地管理和合理地使用計算機的存儲器。存儲器資源是計算機系統(tǒng)中最為重要的資源，也

是系統(tǒng)進程和用戶進程爭奪最激烈的資源。存儲管理的好壞，往往直接影響到整個計算機系統(tǒng)的效率。

存儲管理的管理對象：內(nèi)存儲器以及作為內(nèi)存的擴展和延伸的外存儲器。內(nèi)存儲器用來臨時存放系統(tǒng)運行時所需的信息，它具有存取速度快和隨機存取的特點，但容量一般較小，價

格也較昂貴。磁帶、磁盤、光盤等稱為外存儲器(簡稱外存)，外存儲器用來存放永久信息，它具有容量大和非隨機存取的

特點，但存取速度較慢。1/100存儲管理要解決的問題：一是存儲空間的分配和回收；二是地址映射，就是把程序使用的地址映射成內(nèi)存空間地址；三是內(nèi)存的保護，就是系統(tǒng)要保證內(nèi)存中的進程不會相互干擾，影響整個系統(tǒng)的穩(wěn)定性、可靠性。1/100存儲管理方式分區(qū)管理

分區(qū)管理的基本思想是，把內(nèi)存空間靜態(tài)地或動態(tài)地分割成若干大小不等的區(qū)域，每個作業(yè)分配一片連續(xù)的存儲空間，程序一次整體裝入。分區(qū)管理分為：固定式分區(qū)管理可變式分區(qū)管理可重定位分區(qū)管理1/100分頁管理分頁存儲管理的基本思想

將每個進程的虛擬地址空間按固定大小(如2KB或4KB)分成若干個相等的頁面，并用0、1、2…等序號表示，叫做虛頁面；

把內(nèi)存空間也按同樣大小分為若干個相等的頁面，也用0、1、2…等序號表示，叫做實頁面。

在對進程進行存儲分配時，將進程的虛頁面映射到內(nèi)存中的實頁面上，這些實頁面可以是不連續(xù)的。1/100分段存儲管理

一個用戶程序通常由一個主程序、若干個子程序和數(shù)據(jù)區(qū)組成，我們把每一個像這樣的邏輯信息組稱做“段”，這時用戶程序的邏輯地址空間變成了二維地址空間（把整個邏輯地址空間分為若干段，每一個段段內(nèi)又從0開始記數(shù)）。我們可以以“段”為單位進行內(nèi)存管理。這就是“分段式”內(nèi)存管理的思想。

“段”是信息的邏輯單位，是由程序設(shè)計人員規(guī)定的，其長度隨程序的不同而變化的；1/100段頁結(jié)合存儲管理段內(nèi)再進行分頁

段頁結(jié)合是指在分段的基礎(chǔ)上，對各個段又進行分頁。把段調(diào)入內(nèi)存時，虛頁面與對實頁面相對應(yīng)，一頁一頁地存放。

同一信息段的各頁可以不連續(xù)地存放于內(nèi)存中，減少了移動的開銷。

不需要把一個段整段地調(diào)進內(nèi)存，而是在程序執(zhí)行過程中根據(jù)需要按該段的分頁逐頁請調(diào)，分段的最大長度不受內(nèi)存大小的限制。1/100設(shè)備驅(qū)動程序一種低級的系統(tǒng)過程，它直接控制硬件設(shè)備的操作。因為設(shè)備驅(qū)動程序直接與設(shè)備控制、設(shè)備提供的寄

存器打交道，所以一般使用匯編語言來編寫。設(shè)備驅(qū)動程序是和具體的硬件設(shè)備以及所處的系統(tǒng)緊密相關(guān)的。驅(qū)動程序可以負責(zé)數(shù)據(jù)的傳輸，在數(shù)據(jù)傳送完成之后，驅(qū)動程序把操作情況報告給“輸入輸出控制系統(tǒng)”。

當(dāng)某一進程需要使用某種輸入輸出設(shè)備時，首先向“輸入輸出控制系

統(tǒng)”發(fā)出請求，該子系統(tǒng)阻塞進程、分析進程發(fā)出的請求，并根據(jù)進程

的請求調(diào)用適當(dāng)?shù)脑O(shè)備驅(qū)動程序。

設(shè)備驅(qū)動程序接到“輸入輸出控制

系統(tǒng)”發(fā)出的調(diào)用請求后，寫設(shè)備

控制器的寄存器，完成設(shè)備的初始

化，操作設(shè)備完成具體的輸入輸出

工作，完成數(shù)據(jù)傳輸之后，把設(shè)備

的狀態(tài)信息反饋給“輸入輸出控制

系統(tǒng)”?！拜斎胼敵隹刂葡到y(tǒng)”檢驗設(shè)備狀態(tài)，喚醒請求進程，并把

操作狀態(tài)信息返回給請求進程。1/1001/100–關(guān)系型數(shù)據(jù)庫管理系統(tǒng)（RDBMS），主流的產(chǎn)品有Microsoft公司的SQL

Server、SYBASE公司的Sybase、ORACLE公司的

Oracle、INFORMIX公司的Informix和IBM公司的DB2。–微軟公司的ODBC（Open

DataBaseConnectivity，即：開放數(shù)據(jù)庫互連）。1/100ODBC是Microsoft公司開發(fā)的一套開放數(shù)據(jù)庫系統(tǒng)應(yīng)用程序接口規(guī)范，目前它已成為一種工業(yè)標(biāo)準(zhǔn)，它提供了統(tǒng)一的數(shù)據(jù)庫應(yīng)用編程接口（API），為應(yīng)用程序提供了一套高層調(diào)用接口規(guī)范和基于動態(tài)連接庫的運行支持環(huán)境。使用ODBC開發(fā)數(shù)據(jù)庫應(yīng)用程序時，應(yīng)用程序調(diào)用的是標(biāo)準(zhǔn)的ODBC函數(shù)和SQL語句，數(shù)據(jù)庫底層操作由各個數(shù)據(jù)庫的驅(qū)動程序完成。因此使應(yīng)用程序有很好的適應(yīng)性和可移植性，并且具備了同時訪問多種數(shù)據(jù)庫管理系統(tǒng)的能力，從而徹

底克服了傳統(tǒng)數(shù)據(jù)庫應(yīng)用程序的缺陷。1/100關(guān)系型數(shù)據(jù)庫組成關(guān)系運算傳統(tǒng)的集合運算：–并（Union）、差（Difference）、交（Intersection選擇運算投影運算聯(lián)接運算1/100SQL：Structured

Query

Language（結(jié)構(gòu)化查詢語言）關(guān)系數(shù)據(jù)庫操作語言，標(biāo)準(zhǔn)的計算機數(shù)據(jù)庫語言

SQL語言基本上獨立于數(shù)據(jù)庫本身，獨立于所使用的機器、網(wǎng)絡(luò)、操縱系統(tǒng)，具有良好的可移植性

一種交互式查詢語言，允許用戶直接查詢存儲的數(shù)據(jù)，也可以把SQL語句嵌入到某種高級語言，如：C語言、COBOL等中。SQL語言不是一個完整的程序設(shè)計語言SQL的主要功能是數(shù)據(jù)定義、操縱和控制功能SQL語言1/100SQL中的數(shù)據(jù)操縱語句有：SELECT：檢索、INSERT：插入UPDATE：更新二SQL中的數(shù)據(jù)操縱1/100數(shù)據(jù)檢索語句SELECT：◆SELECT語句的一般形式為：SELECT

[DISTINCT]

列表[，列表]◆◆FROM

基本表（或視圖）[WHERE

條件表達式][GROUP

BY列名[HAVING條件表達式]]

[ORDER

BY列名[ASC/DESC]]；◆◆◆其中：‘DISTINCT’為去掉查詢結(jié)果中的重復(fù)的行；

‘GROUP

BY’是分組依據(jù)；‘HAVING’是分組提取條件；

‘ORDERBY’是查詢結(jié)果的排序方式，ASC為升序；DESC為降序。1/100例1：select

*

from卷面select

Max(總評)from卷面select

Min(總評)from卷面select

Avg(總評)from卷面這里，*代表全部列，這是一種簡化的寫法。

例2：查詢學(xué)生成績在80分到90分之間的學(xué)生的姓名和總評成績：SELECT姓名,總評FROM卷面WHERE總評

BETWEEN

80

AND

90

Order

By總評ASC此語句等價于：SELECT姓名,總評FROM卷面WHERE總評>=80

AND總評<=901/100例3：查詢姓張的同學(xué)的成績：SELECT

*

FROM卷面WHERE姓名LIKE"張%"這里，“%”代表任意個字符。例4：SELECT產(chǎn)品.產(chǎn)品名稱,供應(yīng)商.公司名稱FROM供應(yīng)商,產(chǎn)品WHERE供應(yīng)商.供應(yīng)商ID=產(chǎn)品.供應(yīng)商ID;–在這個查詢中，使用到2個表。在訪問多個表的列時，采用這種形式：表名.列名。1/100

SQL還提供了“聚集函數(shù)”，用戶可以使用它們來完成簡單的統(tǒng)計。這些函數(shù)有：計數(shù)函數(shù)

COUNT，求和函數(shù)SUM，求平均函數(shù)AVG等。請參看下面的例子。例6：統(tǒng)計“供應(yīng)商”表中的供應(yīng)商數(shù)目SELECT

COUNT(*)FROM供應(yīng)商例7：統(tǒng)計“供應(yīng)商”表中的美國供應(yīng)商數(shù)目SELECT

COUNT(*)FROM供應(yīng)商WHERE國家="美國"1/100數(shù)據(jù)更新語句SQL的數(shù)據(jù)更新語句包括修改、插入和刪除三類語句，即

UPDATE語句，INSERT語句和DELETE語句?？梢允褂肬PDATE語句來更新表中的數(shù)據(jù)，UPDATE語句的格式為：UPDATE表名SET列名＝表達式[，列名＝表達式]…

[WHERE條件]

“SET”后緊跟的是需要更新的列及其值，“WHERE”是需要更新的條件。例8：將300211同學(xué)的“總評”成績加5分。UPDATE卷面SET總評=總評+5

WHERE班號="300211"1/100

錄入數(shù)據(jù)是很自然的要求，此時應(yīng)當(dāng)使用數(shù)據(jù)插入語句

INSERT，插入語句的格式如下：INSERT

INTO表名[（列名[，列名]…）]VALUES（常量[，常量]…）例9：向課程表中增加一個新的課程記錄：INSERT

INTO

test

values

(12,"zhxj","100")

利用插入語句插入數(shù)據(jù)時，要注意數(shù)據(jù)的一致性，新增加的記錄的各個域值的類型和長度應(yīng)該與表中的定義完全一致。比如：主鍵不能空，且與表中已有記錄的主關(guān)鍵字不重。1/100

刪除一些已經(jīng)過時的數(shù)據(jù)。使用刪除語句

DELETE來完成。刪除語句的一般格式為：DELETE

FROM

表名

[WHERE

條件]若WHERE子句缺省，則是無條件刪除表中的全部數(shù)據(jù)，但表仍然存在。例10：刪除學(xué)生選課表SC中的全部數(shù)據(jù)。DELETE

FROM

test例11：刪掉某一個記錄：delete

from

test

where

name="zhxj"1/100

SQL的數(shù)據(jù)定義包括三類對象的定義：基本表、視圖和索引。從用戶的觀點看，基本的數(shù)據(jù)定義語句有三類：定義、修改和刪除。表的定義、修改與刪除定義基本表的語句格式為：CREATE

TABLE表名（列定義[，列定義]…）；其中“列定義”為：列名列數(shù)據(jù)類型[NOT

NULL]CREATE

TABLE

test(ID

text(8),NAME

text(10),分?jǐn)?shù)

INT)三SQL中的數(shù)據(jù)定義1/100

如果我們需要修改表的結(jié)構(gòu)，就需用到表修改語句。修改表的結(jié)構(gòu)的語句格式為：ALTER

TABLE

表名ADD列名類型；

當(dāng)然，刪除表是可能的，在某些情況下也是需要的。

SQL中的表刪除語句很簡單：DELETE

TABLE

表名；ACCESS中：drop

table1/100索引的建立和刪除

索引是數(shù)據(jù)存取的路徑。為一個表創(chuàng)建索引，可以顯著地提高查詢效率。創(chuàng)建索引的語句為：CREATE[UNIQUE]INDEX索引名ON表名（列名[次序][，列名[次序]]…）索引順序有兩種，升序（ASC）和降序（DESC）其中，UNIQUE表示每一索引值只對應(yīng)唯一的數(shù)據(jù)記錄，一般在主鍵上建立這樣的索引。比如，我們在“學(xué)生信息

S的主鍵SNO上建立一個索引：CREATE

INDEX

t

ON

test

(ID)1/100

視圖（VIEW）是用戶看到的數(shù)據(jù)內(nèi)容，它是由基本表重構(gòu)的虛表。視圖對應(yīng)關(guān)系數(shù)據(jù)庫中的外模式。視圖具有這樣一些的特點：視圖是虛表，它只有定義的數(shù)據(jù)，沒有實際存儲的數(shù)據(jù)，它的數(shù)據(jù)散列在有關(guān)聯(lián)的基本表中。對視圖

內(nèi)容的操作最終都轉(zhuǎn)換為對與視圖相關(guān)的基本表的

操作。視圖向不同用戶提供各自需求的虛表結(jié)構(gòu)，

隔離用戶與其不相干的數(shù)據(jù)，是一種安全控制手段。視圖所包含的屬性還可來自于多個基本表，是多個基本表的部分屬性的綜合。用于定義視圖的表可以是基本表也可以是已定義好的視圖。需要注意的是，如果在視圖的基礎(chǔ)上再定義視圖，那會大大降低查詢效率。1/100完善的安全機制，一般采用基于角色的多級授權(quán)安全機制

任何級別的用戶在使用數(shù)據(jù)庫系統(tǒng)時，除了必須擁有的授權(quán)外，還必須提供正確的用戶名稱和用戶口令

數(shù)據(jù)庫系統(tǒng)管理員（即DBA）負責(zé)完成整個系統(tǒng)的管理工作，獲得DBA授權(quán)的用戶可以創(chuàng)建數(shù)據(jù)庫、表等而成為這些數(shù)據(jù)庫對象的擁有者。

擁有者對自己所擁有的對象有完全控制權(quán)，同時擁有者也可以授權(quán)其他用戶使用其所擁有的對象。數(shù)據(jù)控制功能1/100

SQL的數(shù)據(jù)控制功能是指控制用戶對數(shù)據(jù)的存取權(quán)力，語句有兩條：授權(quán)語句（GRANT）和收權(quán)語句（REVOKE）。例1：假設(shè)把對表LTemp的所有操作權(quán)限授權(quán)給用戶LUSER –

GRANT

ALL

ON

LTemP

TO

LUSER

例2：假設(shè)只把查看（即SELECT）的權(quán)限授權(quán)給用戶

JUSER–

GRANT

SELECT

ON

LTemp

TO

JUSER1/100在星型網(wǎng)絡(luò)中，每臺計算機由電纜連接到一個集中的站點上，可以是集線器(hub)或交換機（switch）。集線器能將所有計算機的報文轉(zhuǎn)發(fā)給其它所有計算機（在廣播式星型網(wǎng)絡(luò)中）或者只發(fā)給目標(biāo)計算機（交換式星型網(wǎng)絡(luò)中）。為了擴展星型網(wǎng)絡(luò)的規(guī)模，可以在適當(dāng)?shù)牡胤皆僭O(shè)置一個或幾個集線器，進行互連。星型網(wǎng)絡(luò)是目前最流行的一種網(wǎng)絡(luò)結(jié)構(gòu)。星型結(jié)構(gòu)1/100優(yōu)點–星型網(wǎng)絡(luò)可以提供集中的資源管理。易于擴展和維護。–故障易于隔離。如果某臺計算機發(fā)生故障，整個網(wǎng)絡(luò)不會受到影響。集線器可以檢測到網(wǎng)絡(luò)故障，并隔離有問題的計算機或網(wǎng)絡(luò)電纜，網(wǎng)絡(luò)的其余部分可正常運行。缺點–要求中央節(jié)點的可靠性較高。如果中央節(jié)點失敗，整個網(wǎng)絡(luò)就會癱瘓。星型網(wǎng)絡(luò)拓撲結(jié)構(gòu)的優(yōu)缺點1/100計算機網(wǎng)絡(luò)的基本功能就是進行數(shù)據(jù)通信，不同計算機交換信息時必須遵循一定規(guī)則。一般把計算機通信雙方在通信時必須遵循的一組規(guī)范稱之為網(wǎng)絡(luò)協(xié)議（Protocol）。從某種意義上來說，協(xié)議就是計算機網(wǎng)絡(luò)的核心。網(wǎng)絡(luò)協(xié)議與網(wǎng)絡(luò)操作系統(tǒng)1/100

國際標(biāo)準(zhǔn)化組織ISO在1979年提出開放

系統(tǒng)互連參考模型OSI/RM，根據(jù)“分層”的思想制訂計算機網(wǎng)絡(luò)互連的標(biāo)準(zhǔn)，建

立了網(wǎng)絡(luò)協(xié)議模型。

OSI/RM是一個網(wǎng)絡(luò)協(xié)議模型，并不是一個實際的網(wǎng)絡(luò)實現(xiàn)。OSI參考模型1/100OSI采用了分層的結(jié)構(gòu)化技術(shù)。在邏輯上把功能分為若干層，每一層實現(xiàn)一個定義明確的功能。分層時遵循這樣的原則：–層次間相對獨立，每一層使用下層提供的服務(wù)實現(xiàn)自己的功能；–每一層的目的都是向它的上一層提供服務(wù)并且向上層屏蔽掉實現(xiàn)細節(jié)–下層對上層來說是“透明的”，對下層的任何修改不會影響到上層OSI/RM的協(xié)議層次1/100應(yīng)用層會話層表示層應(yīng)用層應(yīng)用層協(xié)議表示層表示層協(xié)議會話層網(wǎng)絡(luò)層傳送層傳送層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層物理層

物理層協(xié)議

物理層表示層協(xié)議表示層協(xié)議網(wǎng)絡(luò)層協(xié)議數(shù)據(jù)鏈路層協(xié)議7654321接口接口接口接口接口接口OSI/RM開放系統(tǒng)互連參考模型1/100TCP/IP（Transmission

Control

Protocol/Internet

Protocol）協(xié)議是目前應(yīng)用最廣泛的網(wǎng)絡(luò)互連協(xié)議。全球最大的互連網(wǎng)Internet就采用了TCP/IP協(xié)議。TCP/IP不是國際標(biāo)準(zhǔn)，但它是眾多廠商和用戶支持的事實標(biāo)準(zhǔn)，OSI標(biāo)準(zhǔn)非常龐雜，產(chǎn)品比較少，無法取代

TCP/IP的市場主導(dǎo)地位。TCP/IP協(xié)議

TCP/IP協(xié)議采用分層的體系

結(jié)構(gòu)（如圖所

示），共分為

四層：網(wǎng)絡(luò)接

口層，網(wǎng)際層，傳輸層和應(yīng)用

層。TCP/IP協(xié)議層次1/100IPARP

ARP硬件協(xié)議（鏈路控制和介質(zhì)訪問）TCPUDPTELNETSMTPFTP

DNSTFTPSMTP1/100負責(zé)接受IP數(shù)據(jù)報，并通過網(wǎng)絡(luò)進行傳送。網(wǎng)絡(luò)的接口有兩種：1、設(shè)備驅(qū)動程序；2、使用專用數(shù)據(jù)鏈路協(xié)議的子系統(tǒng)。本層的協(xié)議標(biāo)準(zhǔn)很多，包括各種邏輯鏈路控制和介質(zhì)訪問協(xié)議。1/100IP協(xié)議提供主機間的數(shù)據(jù)傳送能力。地址解析協(xié)議ARP實現(xiàn)了物理地址和IP地址間的映射，起著屏蔽物理地址細節(jié)的作用?？刂茀f(xié)議ICMP。1/100提供端到端的通信。傳輸控制協(xié)議TCP，面向連接的協(xié)議。用戶數(shù)據(jù)報協(xié)議UDP，無連接協(xié)議。1/100為用戶提供一組高層協(xié)議，依賴于TCP或UDP。FTP、Telnet、HTTP等1/100在任何一個物理網(wǎng)絡(luò)中，各站點都有一個機器可識別的物理地址（如：MAC）。網(wǎng)際層的IP協(xié)議提供了一種全網(wǎng)通用的地址格式，即IP地址，在統(tǒng)一管理下進行地址分配。IP地址是一種層次型地址，由網(wǎng)絡(luò)號和主機號組成，如圖所示：網(wǎng)絡(luò)號+主機號1/100IP地址IP地址的長度為32比特，按網(wǎng)絡(luò)規(guī)模的大小，可分為三類IP地址的分類1/1001/100子網(wǎng)掩碼（Subnet

mask）是一個32位的位模式，若某位為“1”，表示該位對應(yīng)著IP地址中網(wǎng)絡(luò)號部分中的一位，若某位為“0”，則表示它對應(yīng)著IP地址中的主機號部分。–例如：一個C類地址：6，用前24

位標(biāo)識網(wǎng)絡(luò)號部分，最后8位標(biāo)識主機，則它的子網(wǎng)掩碼可以標(biāo)識為：（用點分十進制表示）。（4）子網(wǎng)掩碼1/100主機號部分可進一步劃分成子網(wǎng)號和主機號兩部分，這樣可以擴展地址中的網(wǎng)絡(luò)號部分，但節(jié)點的編號范圍會減少子網(wǎng)掩碼主要與路由選擇有關(guān)。示例：子網(wǎng)掩碼24（11111111

11111111

11111111

11100000）下面給出各種網(wǎng)絡(luò)類別的缺省子網(wǎng)掩碼。

A類地址：B類地址：C類地址：1/100傳統(tǒng)的軟件工程---生存周期模型瀑布(waterfall)式的生存周期模型，把軟件的生命周期分為七