【正文】 時(shí)，小心地避免。 ? 檢測(cè)和恢復(fù)： 允許死鎖的產(chǎn)生，每隔一段時(shí)間進(jìn)行檢測(cè)，若存在死鎖，則即決之。 – 撤銷(xiāo)進(jìn)程。 – 掛起進(jìn)程。 存儲(chǔ)管理 ? 存儲(chǔ)管理任務(wù) 主存空間分配、地址映射、內(nèi)存保護(hù)、內(nèi)存“擴(kuò)充” ? 實(shí)存儲(chǔ)管理 1. 固定分區(qū)、動(dòng)態(tài)分區(qū)（空閑分區(qū)分配算法、動(dòng)態(tài)重定位） ? 虛擬存儲(chǔ)管理 請(qǐng)求分頁(yè)（概念、特點(diǎn)、地址轉(zhuǎn)換、頁(yè)面置換算法） 請(qǐng)求分段 設(shè)備管理 ? 有關(guān)概念 設(shè)備管理的功能、任務(wù) ? I/O請(qǐng)求的檢測(cè)與控制 ? 循環(huán)測(cè)試、中斷、 DMA、通道 ? 緩沖技術(shù) 概念、目的 ? 設(shè)備管理程序 邏輯設(shè)備與物理設(shè)備 ? 虛擬設(shè)備技術(shù) 虛擬設(shè)備、 SPOOLing技術(shù) 文件管理 ? 基本概念與術(shù)語(yǔ) 文件、文件系統(tǒng) 文件分類(lèi) ? 文件的結(jié)構(gòu) ? 邏輯結(jié)構(gòu)（記錄式文件、流式文件） 、物理結(jié)構(gòu)（連續(xù)分配、鏈接分配、索引分配） ? 文件目錄 ? FCB、文件目錄、目錄項(xiàng)、目錄文件、目錄結(jié)構(gòu)（單級(jí)、目錄、目錄）、路徑 ? 文件存儲(chǔ)空間的管理 數(shù)據(jù)庫(kù)系統(tǒng)概述 ? 數(shù)據(jù)庫(kù)基本概念 DB、 DBMS、 DBS、 DBA ? 數(shù)據(jù)模型 – 數(shù)據(jù)模型（ ER圖） 、結(jié)構(gòu)模型（層次、網(wǎng)狀、關(guān)系）、 ER圖轉(zhuǎn)換為關(guān)系模型 ? 數(shù)據(jù)庫(kù)系統(tǒng)結(jié)構(gòu)（三級(jí)模式結(jié)構(gòu)） – 外模式、模式、內(nèi)模式、外模式 /模式映象、模式 /內(nèi)模式映象 、邏輯獨(dú)立性、物理獨(dú)立性 ? 關(guān)系數(shù)據(jù)庫(kù)的基本概念 – 關(guān)系、元組、屬性、候選碼、主碼 – 關(guān)系模式、關(guān)系模型、關(guān)系特點(diǎn) 關(guān)系數(shù)據(jù)操作語(yǔ)言 ? 關(guān)系代數(shù) – 傳統(tǒng)的集合運(yùn)算（并、交、差、廣義笛卡爾積） – 專(zhuān)門(mén)的關(guān)系運(yùn)算（選擇、投影、連接（條件連接、自然連接）） ? 結(jié)構(gòu)化查詢語(yǔ)言 SQL – SQL： DDL、 DML、 DCL – SELECT語(yǔ)句的使用 軟件工程 ? 軟件工程基本概念 – 軟件、軟件危機(jī) – 軟件生命周期 – 軟件開(kāi)發(fā)過(guò)程 – 過(guò)程模型 – 軟件開(kāi)發(fā)方法 – 結(jié)構(gòu)化、面向?qū)ο? – 軟件開(kāi)發(fā)工具 結(jié)構(gòu)化軟件開(kāi)發(fā)方法 – 可行性研究 市場(chǎng)、經(jīng)濟(jì) 、技術(shù) 、法律、可行性研究報(bào)告 – 需求分析 任務(wù)、步驟、數(shù)據(jù)流圖、數(shù)據(jù)字典、需求規(guī)格說(shuō)明書(shū) – 概要設(shè)計(jì) 體系結(jié)構(gòu)設(shè)計(jì)、模塊設(shè)計(jì)、用戶界面設(shè)計(jì)、數(shù)據(jù)庫(kù)設(shè)計(jì)、概要設(shè)計(jì)說(shuō)明書(shū) 模塊獨(dú)立性、耦合、內(nèi)聚 詳細(xì)設(shè)計(jì)（圖形工具） 編碼 測(cè)試 目的、任務(wù)、白盒測(cè)試、黑盒測(cè)試、測(cè)試用例、測(cè)試計(jì)劃、測(cè)試報(bào)告 – 軟件維護(hù) 改正性維護(hù)、適應(yīng)性維護(hù)、 擴(kuò)充與完善性維護(hù)、預(yù)防性維護(hù) 線性鏈表的基本操作 ? 指針賦值 ? 指針移動(dòng) ? 后插 ? 前插 p s s = p p = p next p p s p ① ② ① snext= pnext ② pnext=s s ① ② p q head q=head While (qnext!=p) {q=qnext} ① qnext=s ② snext=p 棧的定義 ? 限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表 ? 棧頂 （ top)：允許插入和刪除的一端； ? 棧底 （ bottom):不允許插入和刪除的一端。 ? 棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱(chēng)棧為 LIFO表(Last In First Out). an … a3 a2 a1 棧底 進(jìn)棧 出棧 棧頂 棧底 練習(xí) 設(shè)一數(shù)列的順序?yàn)?,2,3,4,5 通過(guò)棧操作 ,不可能得到的序列是 ( ) A. 23451 B. 54123 C. 23145 D. 15432 1 2 2 33 4 4 5 5 1 練習(xí) 設(shè)一數(shù)列的順序?yàn)?,2,3,4,5 通過(guò)棧操作 ,不可能得到的序列是 ( ) A. 23451 B. 54123 C. 23145 D. 15432 1 2 3 4 4 5 5 答案 B 隊(duì)的定義 ? 一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 ? 隊(duì)尾 (rear):允許插入的一端 ? 隊(duì)頭 (Front):允許刪除的一端 ? 隊(duì)列的操作原則是先進(jìn)先出的，所以隊(duì)列又稱(chēng)作 FIFO表 (First In First Out) a1 a2 a3 a4 a5 an front隊(duì)頭 rear隊(duì)尾 出隊(duì) 入隊(duì) 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) ? 計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此將數(shù)組元素排成線性序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中 ? 行優(yōu)先順序：把數(shù)組按一行一行的順序依次排列。 地址的計(jì)算方法 —— 二維按行優(yōu)先順序存放 a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45 存放在計(jì)算機(jī)內(nèi)： m j1 aij i1 n a11 a12 a13 a14 a15 a21 a22 … a43 a44 a45 Loc（ aij） =Loc(a11)+(i1) * n +(j1) (1=i=m,1=j=n) 第一個(gè)元素是從 a11開(kāi)始，注意從 a00開(kāi)始的情況 Loc（ aij） =Loc(a00)+ i* n +j aij前的元素個(gè)數(shù) 地址的計(jì)算方法 —— 二維按列優(yōu)先順序存放 a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45 存放在計(jì)算機(jī)內(nèi)： m j1 aij i1 n a11 a21 a31 a41 a12 a22 a32 … a25 a35 a45 Loc（ aij） =Loc(a11)+(j1) * m +(i1) (1=i=m,1=j=n) 第一個(gè)元素是從 a11開(kāi)始，注意從 a00開(kāi)始的情況 Loc（ aij） =Loc(a00)+(j* m +i)*d 稀疏矩陣的壓縮存儲(chǔ)方式 三元組表示 ? 把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表 (三元組表 )來(lái)表示這個(gè)稀疏矩陣。 一個(gè)矩陣中若其非零元素的個(gè)數(shù) 遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱(chēng)為稀疏矩陣。 ? 但是這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。 結(jié)點(diǎn)的度 （ Degree） ：結(jié)點(diǎn)擁有的子樹(shù)數(shù) 。 結(jié)點(diǎn)的層次 ：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層。 孩子 （ Child） ：除根結(jié)點(diǎn)外 ,每個(gè)結(jié)點(diǎn)都是其前趨結(jié)點(diǎn)的孩子 雙親 （ Parent） ：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn) ， 稱(chēng)為這些結(jié)點(diǎn)的雙親 兄弟 （ Sibling） ： 同一雙親的孩子 。 有序樹(shù) :每個(gè)結(jié)點(diǎn)的各子樹(shù)從左到右的次序不能互換的樹(shù)稱(chēng)為有序樹(shù) 二叉 樹(shù) 4 2 3 1 6 7 8 9 10 11 12 5 非完全二叉樹(shù) ?完全二叉樹(shù) 4 2 3 1 6 7 8 9 10 11 12 5 完全二叉樹(shù) 特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)， 最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。 4. 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)高度為 |_ log2n_| +1 5. 設(shè)完全二叉樹(shù)中階段數(shù) n，按層編號(hào)，對(duì)樹(shù)中第 i個(gè)結(jié)點(diǎn)有： 1. 若 i=1， i的雙親節(jié)點(diǎn)編號(hào)為 |_ i/2_| 2. i的左子位于第 2*i號(hào)節(jié)點(diǎn) 3. i的右子位于第 2*i+1號(hào)節(jié)點(diǎn) 二叉樹(shù)的遍歷 ? 先序 ABCDEFG ? 中序 CBDAEGF ? 后序 CDBGFEA A B G C E D F 若二叉樹(shù)中各結(jié)點(diǎn)的值均不相同，則由二叉樹(shù)的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹(shù)，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹(shù)。 二叉排序樹(shù) 二叉排序樹(shù)或是空樹(shù) ,或具有下列性質(zhì) ? 其左子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)值均 小于 根結(jié)點(diǎn)的數(shù)據(jù)值 。 ? 左子樹(shù)和右子樹(shù)又各是一棵 二叉排序樹(shù) 10 3 21 2 18 4 13 15 9 9 8 中序遍歷 : 2,3,4,8,9,9,10,13,15,18,21 得到由小到大的有序序列 哈夫曼樹(shù) ? 樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱(chēng)為最優(yōu)二叉樹(shù)（即哈夫曼樹(shù)）。 ? 無(wú)向圖 :圖中頂點(diǎn)關(guān)系為無(wú)序?qū)Α?(弧 ) ? 網(wǎng) ：圖中每一條邊附有一個(gè)對(duì)應(yīng)的數(shù)（權(quán)） ? 有向網(wǎng) ：弧上帶權(quán)的有向圖 ? 子圖 :簡(jiǎn)單地說(shuō)，子圖就是原圖的一部分 ? 度 :無(wú)向圖中頂點(diǎn)的度就是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目 ? 入度 :頂點(diǎn) v的入度即是以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目 ? 出度 :頂點(diǎn) v的出度即是以該頂點(diǎn)為始點(diǎn)的邊的數(shù)目 圖的存儲(chǔ)結(jié)構(gòu) —— 鄰接矩陣表示法 1 2 3 5 4 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 2 3 4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 有向圖 無(wú)向圖，矩陣對(duì)稱(chēng) 圖的存儲(chǔ)結(jié)構(gòu) —— 鄰接表 1 2 3 5 4 1 2 3 4 1 2 3 4 ^ 2 1 3 ^ 3 2 1 5 ^ 4 1 ^ 5 3 ^ 1 2 3 ^ 2 3 4 ^ 4 1 ^ ^ 鄰接矩陣與鄰接表 ? 從存儲(chǔ)空間角度看，鄰接表更適合于表示稀疏圖而鄰接矩陣適合于表示稠密圖。 2 3 ^ 4 ^ 1 2 3 4 1 ^ ^ 0 0 0 0 0 0 0 1 1 0 0 0 V1 V2 V3 V4 V1 V2 V3 V4 0 1 1 0 圖的遍歷 ? 從某一個(gè)頂點(diǎn)出發(fā)，沿著某條路經(jīng)對(duì)途中其余頂點(diǎn)進(jìn)行訪問(wèn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次 – 深度優(yōu)先遍歷（ DFS depthfirst search） – 廣度優(yōu)先遍歷（ BFS breadthfirst search） 深度優(yōu)先遍歷算法 (dfs) 1 2 3 4 7 8 5 6 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Dfs(1) Dfs(2) Dfs(4) Dfs(8) Dfs(5) Dfs(6) Dfs(3) Dfs(7) 1 0 0 0 0 0 0 0 Visited[1:8] 11 2 3 4 5 6 7 8 1111 11深度優(yōu)先遍歷算法 鄰接表 存儲(chǔ) 1 2 4 5 ^ 2 1 3 ^ 3 1 6 7 ^ 4 8 ^ 5 8 ^ 2 2 6 8 ^ 8 5 3 4 6 7 ^ Dfs(7) Dfs(3) Dfs(1) Dfs(2) Dfs(4) Dfs(8) Dfs(5) Dfs(6) 7 8 ^ 3 0 0 0 0 0 0 1 0 Visited[1:8] 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 廣度優(yōu)先遍歷算法 (鄰接表 存儲(chǔ) ) 1 2 4 5 ^ 2 1 3 ^ 3 1 6 7 ^ 4 8 ^ 5 8 ^ 2 2 6 8 ^ 8 5 3 4 6 7 ^ Visited[1:8] 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7