軟件工程—復(fù)試總結(jié)分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上軟件工程復(fù)試總結(jié)1、 數(shù)據(jù)庫(kù)部分?jǐn)?shù)據(jù)庫(kù)緒論1、 簡(jiǎn)述三層模式、兩級(jí)映射，分別有什么作用？模式（邏輯模式）：是數(shù)據(jù)庫(kù)中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述，是數(shù)據(jù)庫(kù)系統(tǒng)模式結(jié)構(gòu)的中間層，即不涉及數(shù)據(jù)的物理存儲(chǔ)細(xì)節(jié)，也與具體應(yīng)用程序開發(fā)工具語(yǔ)言無關(guān)。外模式（用戶模式）：是用戶能看見和使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征描述，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的邏輯表示，是模式的子集，一個(gè)數(shù)據(jù)庫(kù)可以有多個(gè)外模式。內(nèi)模式（存儲(chǔ)模式）：數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述，是數(shù)據(jù)在數(shù)據(jù)庫(kù)內(nèi)部的表示方式，如存儲(chǔ)方式是按照某個(gè)屬性升序存儲(chǔ)，什么索引等。外模式模式映像：當(dāng)模式發(fā)生改變，數(shù)據(jù)庫(kù)管理員對(duì)外模式模式映像作

2、相應(yīng)改變，可使外模式不變，從而應(yīng)用程序不用修改。保證數(shù)據(jù)與程序的邏輯獨(dú)立性。模式內(nèi)模式映像：當(dāng)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)改變了，由數(shù)據(jù)庫(kù)管理員對(duì)模式內(nèi)模式映像作相應(yīng)改變，可以保持模式不變，從而應(yīng)用程序也不必改變，保證了數(shù)據(jù)與程序的物理獨(dú)立性。三級(jí)模式使用戶能邏輯地抽象地處理數(shù)據(jù)而不關(guān)心數(shù)據(jù)在計(jì)算機(jī)內(nèi)具體表示方式與存儲(chǔ)方式，兩級(jí)映像保證了數(shù)據(jù)庫(kù)系統(tǒng)中的數(shù)據(jù)有較高的邏輯獨(dú)立性和物理獨(dú)立性。2、 說出至少三種數(shù)據(jù)庫(kù)類型（層次，網(wǎng)狀，關(guān)系）并簡(jiǎn)要解釋了一下層次模型：用樹形結(jié)構(gòu)來表示各類實(shí)體以及實(shí)體間的聯(lián)系，有且只有一個(gè)節(jié)點(diǎn)沒有雙親節(jié)點(diǎn)（根節(jié)點(diǎn)），其他的都有且只有一個(gè)雙親節(jié)點(diǎn)。只能能直接表示的是一對(duì)多聯(lián)系。優(yōu)點(diǎn)：

3、效率高結(jié)構(gòu)清晰，性能優(yōu)于關(guān)系數(shù)據(jù)庫(kù)，不低于網(wǎng)狀。缺點(diǎn)：現(xiàn)實(shí)世界很多聯(lián)系都不是層次的，如節(jié)點(diǎn)間多對(duì)多聯(lián)系，還有一個(gè)節(jié)點(diǎn)具有多個(gè)雙親的情況都不好表示。網(wǎng)狀模型：對(duì)于非層次關(guān)系的聯(lián)系，用層次表示非樹形結(jié)構(gòu)是很不直接的，網(wǎng)狀模型可以很好的表示，它允許有一個(gè)以上的節(jié)點(diǎn)沒有雙親，一個(gè)節(jié)點(diǎn)也可以有多個(gè)雙親，可以更直接地描述現(xiàn)實(shí)世界。優(yōu)點(diǎn)：更直接描述現(xiàn)實(shí)世界，性能也較好，存取效率也較高。缺點(diǎn)：結(jié)構(gòu)比較復(fù)雜不利于掌握，用戶編程還得了解系統(tǒng)結(jié)構(gòu)細(xì)節(jié)，加重了編程的負(fù)擔(dān)。關(guān)系模型：通常來看關(guān)系就是一張規(guī)范二維表，實(shí)體還是實(shí)體間的聯(lián)系都用關(guān)系來表示，對(duì)數(shù)據(jù)的檢索和更新結(jié)果也是關(guān)系。優(yōu)點(diǎn)：概念單一，用戶易懂易用，而且存取

4、路徑是對(duì)用戶透明的，從而有更高的數(shù)據(jù)獨(dú)立性和安全性，也簡(jiǎn)化程序員的工作。缺點(diǎn)：查詢效率往往不如格式化數(shù)據(jù)模型，為了提高性能，增加開發(fā)DBMS難度。關(guān)系數(shù)據(jù)庫(kù)3、 簡(jiǎn)述關(guān)系與關(guān)系模式的區(qū)別。關(guān)系實(shí)質(zhì)是一張二維表，關(guān)系模式是對(duì)關(guān)系的描述，關(guān)系是關(guān)系模式在某一時(shí)刻的狀態(tài)或內(nèi)容。關(guān)系模式是靜態(tài)的、穩(wěn)定的，而關(guān)系是動(dòng)態(tài)的，隨時(shí)間不斷變化的，因?yàn)殛P(guān)系操作不斷更新數(shù)據(jù)庫(kù)中的數(shù)據(jù)。通俗的說：關(guān)系是一張二維表，關(guān)系模式是表格的描述（表頭），關(guān)系名是表名，元祖是一行，屬性是列，分量一條記錄中的一個(gè)列值。4、 什么是關(guān)系數(shù)據(jù)庫(kù)？關(guān)系和二維表有什么區(qū)別？關(guān)系，是建立在關(guān)系數(shù)據(jù)庫(kù)模型基礎(chǔ)上的數(shù)據(jù)庫(kù)，借助于集合代數(shù)等概念

5、和方法來處理數(shù)據(jù)庫(kù)中的數(shù)據(jù)。在中，表示為一個(gè)二維表，一個(gè)關(guān)系就是一個(gè)二維表（但不是任意一個(gè)二維表都能表示一個(gè)關(guān)系。表中的第一行通常稱為屬性名，表中的每一個(gè)元組和屬性都是不可再分的，且元組的次序是無關(guān)緊要的。5、 關(guān)系的完整性（實(shí)體完整性、參照完整性、用戶自定義）和數(shù)據(jù)庫(kù)主鍵的約束性實(shí)體完整性：關(guān)系的主碼不能取空值，如果主碼由若干屬性組成都不能為空。實(shí)體以主碼作為唯一性標(biāo)識(shí)。參照完整性：一個(gè)關(guān)系中的外碼，或者取空值（若屬性組全為空），或者等于它參照的那個(gè)關(guān)系的主碼值。用戶自定義完整性：針對(duì)具體關(guān)系數(shù)據(jù)庫(kù)的約束。數(shù)據(jù)庫(kù)語(yǔ)言SQL6、 什么是DDL、DML、DCL？（數(shù)據(jù)庫(kù)語(yǔ)言有哪幾種？）數(shù)據(jù)定義語(yǔ)

6、言（DDL）：Create、Drop、Alter數(shù)據(jù)操縱語(yǔ)言（DML）：Insert、Update、Delete數(shù)據(jù)控制語(yǔ)言（DCL）：Grant、Revoke數(shù)據(jù)查詢語(yǔ)言：Select7、 什么是視圖，有什么作用？在數(shù)據(jù)庫(kù)哪層？視圖：是從一個(gè)或幾個(gè)基本表導(dǎo)出的表，是一個(gè)虛表，數(shù)據(jù)庫(kù)只存放視圖的定義，不存放視圖對(duì)應(yīng)的數(shù)據(jù)，數(shù)據(jù)仍放在原來的基本表，基本表數(shù)據(jù)改變，通過視圖查詢也改變了，作用：1、能夠簡(jiǎn)化用戶操作，使數(shù)據(jù)庫(kù)看起來更簡(jiǎn)單，清晰，簡(jiǎn)化查詢操作。2、更安全，機(jī)密數(shù)據(jù)不出現(xiàn)在不應(yīng)該看到這些數(shù)據(jù)的用戶視圖上。3、重構(gòu)數(shù)據(jù)庫(kù)時(shí)候，改變視圖不用修改程序，使數(shù)據(jù)具有邏輯獨(dú)立性。數(shù)據(jù)庫(kù)設(shè)計(jì)8、 簡(jiǎn)述

7、數(shù)據(jù)庫(kù)設(shè)計(jì)的幾個(gè)階段需求分析：詳細(xì)調(diào)查現(xiàn)實(shí)世界要處理的對(duì)象，充分了解各種需求，在此基礎(chǔ)確定新系統(tǒng)的功能。概念結(jié)構(gòu)設(shè)計(jì)：經(jīng)常采用自頂向下需求分析，自底向上概念結(jié)構(gòu)設(shè)計(jì)。對(duì)需求分析收集到的數(shù)據(jù)進(jìn)行分類組織形成實(shí)體、實(shí)體的屬性，確定實(shí)體之間聯(lián)系，設(shè)計(jì)分E-R圖。逐一設(shè)計(jì)分E-R圖，最后將所有分E-R圖綜合成一個(gè)系統(tǒng)的E-R圖。邏輯結(jié)構(gòu)設(shè)計(jì)：一般來講把E-R圖向關(guān)系模型轉(zhuǎn)換，一個(gè)實(shí)體型轉(zhuǎn)換為一個(gè)關(guān)系模式。一個(gè)一對(duì)一聯(lián)系可以獨(dú)立也可以和任意一端合并，一個(gè)一對(duì)多聯(lián)系可以獨(dú)立也可以和N端對(duì)應(yīng)的關(guān)系模式合并，一個(gè)多對(duì)多聯(lián)系獨(dú)立轉(zhuǎn)換為一個(gè)關(guān)系模式。對(duì)數(shù)據(jù)模型規(guī)范化，還根據(jù)具體需求設(shè)計(jì)相應(yīng)的視圖。數(shù)據(jù)庫(kù)物理設(shè)計(jì)：

8、關(guān)系模式存取方法的選擇，比如索引、聚簇、哈希等存儲(chǔ)方式。還應(yīng)該確定數(shù)據(jù)庫(kù)的存取結(jié)構(gòu)，目前許多計(jì)算機(jī)有多個(gè)磁盤或磁盤陣列，因此可以將表和索引放在不同的磁盤上，在查詢時(shí)磁盤驅(qū)動(dòng)器并行工作，可以提高物理IO讀寫效率，也可以將比較大的表放在兩個(gè)磁盤上，以加快存取速度。數(shù)據(jù)庫(kù)的實(shí)施與維護(hù)：比如備份與恢復(fù)等待。9、 什么是E-R圖E-R圖：實(shí)體-聯(lián)系圖，在概念結(jié)構(gòu)設(shè)計(jì)中，對(duì)需求分析收集到的數(shù)據(jù)進(jìn)行分類組織形成實(shí)體、實(shí)體的屬性，確定實(shí)體之間聯(lián)系，設(shè)計(jì)E-R圖。10、 分別解釋1NF、2NF、3NF、BCNF、4NF范式：關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系是要滿足一定要求的，滿足不同程度的要求的為不同范式。規(guī)范化：一個(gè)低一級(jí)

9、范式關(guān)系模式通過模式分解可以轉(zhuǎn)化為若干個(gè)高一級(jí)范式的關(guān)系模式的集合。1NF：滿足最低要求的叫第一范式，每一個(gè)分量必須是一個(gè)不可分的數(shù)據(jù)項(xiàng)。2NF：消除關(guān)系中的部分函數(shù)依賴就稱為第二范式，部分函數(shù)依賴就是非主屬性不完全依賴于碼。3NF：每一個(gè)非主屬性既不部分依賴于碼，也不傳遞依賴于碼。 BCND：所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴，沒有任何屬性完全依賴于非碼的任何屬性，就是除了碼外一定不能有決定因素。數(shù)據(jù)庫(kù)并發(fā)控制11、 什么是事務(wù)，并發(fā)控制是保證事務(wù)的？事務(wù)：是一系列的數(shù)據(jù)操作，這些操作要么全不做，要么全做，不可分割。運(yùn)行過程中發(fā)生某種故障不能繼續(xù)執(zhí)行，全部回滾到開始狀態(tài)。并發(fā)控制中多個(gè)用

10、戶存取數(shù)據(jù)庫(kù)時(shí)候可能會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一個(gè)數(shù)據(jù)的情況，不加控制就會(huì)破壞事務(wù)的一致性，為了保證事物的一致性所以進(jìn)行并發(fā)控制。12、 ACID（事物的四個(gè)性質(zhì)）A原子性：要么都做，要么都不做。C一致性：如果運(yùn)行中發(fā)生故障，必須回滾。不能讓數(shù)據(jù)不一致。比如兩人轉(zhuǎn)錢，一半壞了，不一致倆人都沒有錢。I隔離性：一個(gè)事物不能被其他事物干擾。D持續(xù)性：事物一旦提交，他對(duì)數(shù)據(jù)庫(kù)的改變就應(yīng)該是永久的。接下來的操作和故障不應(yīng)該對(duì)剛才結(jié)果有任何影響。13、 數(shù)據(jù)庫(kù)中鎖有什么作用？什么是只讀鎖、什么是只寫鎖？一個(gè)事物對(duì)數(shù)據(jù)加鎖可以保證事物的四個(gè)特性，加鎖后其他事物不能更新此數(shù)據(jù)對(duì)象，不會(huì)產(chǎn)生數(shù)據(jù)不一致性。寫鎖（排

11、他鎖/ X鎖）：加寫鎖其他事物不能在對(duì)這個(gè)數(shù)據(jù)加任何類型鎖，釋放之前不能讀取和修改。讀鎖（共享鎖/ S鎖）：事物對(duì)數(shù)據(jù)加讀鎖，其他事物可以讀但不可以修改，可以加讀鎖不能加寫鎖。14、 什么是觸發(fā)器，有什么作用？用戶定義在關(guān)系表上的一類由事件驅(qū)動(dòng)的特殊過程，一旦定義了，用戶對(duì)表的增、刪、改操作均有數(shù)據(jù)庫(kù)系統(tǒng)自動(dòng)激活相應(yīng)觸發(fā)器觸發(fā)器可以分為語(yǔ)句觸發(fā)器和行級(jí)觸發(fā)器，觸發(fā)器動(dòng)作體是一個(gè)匿名PL/SQL過程塊，語(yǔ)句級(jí)觸發(fā)器可以在語(yǔ)句執(zhí)行前或后執(zhí)行，而行級(jí)觸發(fā)在觸發(fā)器所影響的每一行觸發(fā)一次。行觸發(fā)器用戶可以用new和old引用數(shù)據(jù)，語(yǔ)句級(jí)不能。2、 數(shù)據(jù)結(jié)構(gòu)部分線性表15、 單鏈表的就地逆置將頭結(jié)點(diǎn)摘下，

12、然后從第一節(jié)點(diǎn)開始，頭插法建立單鏈表，直到最后一個(gè)節(jié)點(diǎn)為止。16、 單鏈表可以用什么實(shí)現(xiàn)？指向結(jié)構(gòu)體的指針實(shí)現(xiàn)，結(jié)構(gòu)體中有兩個(gè)成員，每個(gè)節(jié)點(diǎn)分為數(shù)據(jù)域和指針域，除了最后一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)指針域都指向下一個(gè)節(jié)點(diǎn)的地址，最后一個(gè)節(jié)點(diǎn)指針域指向NULL。也可以用結(jié)構(gòu)體數(shù)組模擬這種操作，數(shù)組中每個(gè)下標(biāo)都對(duì)應(yīng)一個(gè)數(shù)據(jù)元素和游標(biāo)，游標(biāo)是下一個(gè)元素在數(shù)組中的下標(biāo)，把未被使用的數(shù)組元素作為備用鏈表，下標(biāo)為0的元素游標(biāo)存放備用鏈表第一個(gè)節(jié)點(diǎn)的下標(biāo)。數(shù)組最后一個(gè)元素游標(biāo)存放第一個(gè)有效數(shù)值元素的下標(biāo)，相當(dāng)于頭結(jié)點(diǎn)作用，游標(biāo)為0表示指向?yàn)榭?。棧和?duì)列17、 實(shí)現(xiàn)一個(gè)隊(duì)列的方法？為什么隊(duì)列的順序存儲(chǔ)需要留一個(gè)空位？循環(huán)

13、有什么好處？鏈?zhǔn)酱鎯?chǔ)：把鏈表改裝一下，加尾指針作為隊(duì)列的尾部可以插入節(jié)點(diǎn)，頭指針可以刪除節(jié)點(diǎn)，相當(dāng)于出隊(duì)。順序存儲(chǔ)：正常的順序存儲(chǔ)想要利用空出的空間就必須移動(dòng)元素，不移動(dòng)還會(huì)浪費(fèi)空間，循環(huán)隊(duì)列可以解決這個(gè)問題，把這段連續(xù)的地址空間，想象成邏輯上的環(huán)，所以只要有空閑空間就能使用。但是當(dāng)front和rear指針相等的時(shí)候有兩種情況，一種是滿，一種是空，為了區(qū)分這種情況，保留一個(gè)元素空間，我們假定當(dāng)rear+1與front相等隊(duì)列就滿了。而空的時(shí)候是rear等于front。又因?yàn)槭黔h(huán)也可能存在rear>front的情況，所以取模操作。另外計(jì)算隊(duì)列長(zhǎng)度的時(shí)候，rear>front隊(duì)長(zhǎng)為re

14、ar-front，但當(dāng)rear<front隊(duì)長(zhǎng)為兩段相加，所以通用公式為（rear-front+隊(duì)列的總長(zhǎng)度）%隊(duì)列總長(zhǎng)度樹與二叉樹18、 什么是完全二叉樹？完全二叉樹是由而引出來的。對(duì)于深度為K的，有N個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。19、 什么是二叉排序樹，簡(jiǎn)述它的查找過程，二叉排序樹的時(shí)間復(fù)雜度，遍歷后得到什么樣的序列？二叉排序樹是一種二叉樹，具有了一些獨(dú)特性質(zhì)，若左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值，右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值，而且它的左右子樹也是二叉排序樹。構(gòu)造一

15、個(gè)二叉排序樹是為了提高動(dòng)態(tài)查找中插入和刪除的速度。查找過程：遞歸查找二叉排序樹中是否存在要查關(guān)鍵字，若成功則指針指向該數(shù)據(jù)元素的節(jié)點(diǎn)，返回成功，如果關(guān)鍵字小于樹中這個(gè)節(jié)點(diǎn)，則去它左子樹中繼續(xù)查找，大于則去右子樹中查找。如果樹中沒有要查的關(guān)鍵字，則指針指向訪問的上一個(gè)節(jié)點(diǎn)，以便于插入。插入過程：如果當(dāng)查找失敗且指針p為空，則新建根節(jié)點(diǎn)，如果要插入的關(guān)鍵字小于p指向節(jié)點(diǎn)的數(shù)據(jù)，則插入到左孩子，否則右孩子。刪除過程：1葉節(jié)點(diǎn)直接刪除2只有左或右子樹刪了接下面3左右子樹都有的，找到要?jiǎng)h除的節(jié)點(diǎn)的直接前驅(qū)或后繼，用這個(gè)節(jié)點(diǎn)替換要?jiǎng)h除的節(jié)點(diǎn)，然后在刪除這個(gè)節(jié)點(diǎn)。二叉排序樹，以鏈接的方式存儲(chǔ)，有在執(zhí)行插入或

16、刪除操作時(shí)候不用移動(dòng)元素的優(yōu)點(diǎn)，插入刪除性能較好，而查找的時(shí)間復(fù)雜度取決與二叉排序樹的形狀。中序遍歷后得到升序系列，所以也稱為二叉排序樹。20、 什么是平衡二叉樹？為了解決二叉查找樹，查找時(shí)間依賴于形狀的問題，平衡二叉樹就是在建立二叉排序樹的時(shí)候，對(duì)它做了一定的限制，使它保持平衡，使每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多為1。具體做法：找出距離插入節(jié)點(diǎn)最近且平衡因子絕對(duì)值大于一的節(jié)點(diǎn)，把它當(dāng)為根的子樹叫做最小不平衡子樹，進(jìn)行相應(yīng)旋轉(zhuǎn)，使之平衡。插入節(jié)點(diǎn)：LL型，向右旋轉(zhuǎn)。RR型，向左旋轉(zhuǎn)。RL型，先右轉(zhuǎn)，再左轉(zhuǎn)。LR型，先左轉(zhuǎn)，再右轉(zhuǎn)。21、 什么是哈夫曼樹？哈夫曼樹的作用是什么？哈夫曼樹：帶

17、權(quán)路徑長(zhǎng)度為從該節(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與節(jié)點(diǎn)上權(quán)的乘積，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱作哈夫曼樹。構(gòu)造過程：把帶有權(quán)值的葉子節(jié)點(diǎn)按照從小到大的順序排列成一個(gè)有序序列，取出前兩個(gè)最小權(quán)值的節(jié)點(diǎn)作為一個(gè)新節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)，左孩子一般比右孩子小，新節(jié)點(diǎn)權(quán)值為兩個(gè)葉子的和，將新節(jié)點(diǎn)插入剛才有序序列適當(dāng)位置，重新選出頭兩個(gè)最小的，重復(fù)上面過程。哈夫曼編碼：為了解決當(dāng)年遠(yuǎn)距離電報(bào)的數(shù)據(jù)傳輸?shù)淖顑?yōu)化問題，發(fā)明了哈夫曼編碼，比如多英文文章傳輸，假設(shè)每個(gè)字母固定用一個(gè)二進(jìn)制串表示，文章很長(zhǎng)那傳送的串會(huì)非常長(zhǎng)。但英文字母每個(gè)字母出現(xiàn)的頻率是不一樣的，所以可以根據(jù)字母頻率設(shè)定權(quán)值，用哈夫曼樹來規(guī)劃它們，構(gòu)造哈夫

18、曼樹以后，把左分支用0表示，右分支用1表示，然后從根到葉子所經(jīng)過的路徑的數(shù)字用來編碼，當(dāng)雙方約定好同樣的哈夫曼樹后，發(fā)送信息的時(shí)候能明顯減少串長(zhǎng)度。圖的應(yīng)用22、 什么是有環(huán)圖，連通圖，強(qiáng)連通圖？連通圖：無向圖任意兩點(diǎn)都是連通的，圖中極大連通子圖（極大子圖還是連通的）成為連通分量。強(qiáng)連通圖：有向圖從vi到vj和從vj到vi都存在路徑稱為強(qiáng)連通圖，有向圖中極大連通子圖稱作強(qiáng)連通分量。連通圖的生成樹：是一個(gè)極小連通子圖，含有圖中全部n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊，少于是非連通圖，多余必定構(gòu)成環(huán)。有向樹：有向圖中一頂點(diǎn)入度為0，其余入度為1第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為環(huán)或回路。

19、序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑，除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡(jiǎn)單環(huán)。23、 圖的存儲(chǔ)方式有哪些簡(jiǎn)要敘述（鄰接矩陣和鄰接表）？鄰接矩陣：將頂點(diǎn)和邊分別存儲(chǔ)，頂點(diǎn)用一維數(shù)組存儲(chǔ)，邊用二維數(shù)組。可以根據(jù)這個(gè)二維數(shù)組獲取圖中的信息。比如判定兩頂點(diǎn)是否有邊，只需讀取二維數(shù)組值。想知道某個(gè)頂點(diǎn)的度就是將這一行的值相加。求他的臨界點(diǎn)也只需遍歷一行，值為1的就是。無向圖的邊數(shù)組是對(duì)稱的，有向圖入度看列，出度看行。鄰接表：對(duì)于邊數(shù)較少，頂點(diǎn)較多的圖，如果還用鄰接矩陣那是對(duì)空間的極大浪費(fèi)，所以用鄰接表，頂點(diǎn)還是一維數(shù)組存儲(chǔ)，此外數(shù)組每一個(gè)數(shù)據(jù)元素還存儲(chǔ)指向第一個(gè)鄰接點(diǎn)的

20、指針，以便于查找邊的信息，圖中每個(gè)頂點(diǎn)的所有鄰接點(diǎn)構(gòu)成一個(gè)鏈表。邊表每個(gè)節(jié)點(diǎn)存儲(chǔ)這個(gè)頂點(diǎn)在頂點(diǎn)表中的下標(biāo)，和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。想知道某頂點(diǎn)的度，就查找這個(gè)頂點(diǎn)的邊中節(jié)點(diǎn)的個(gè)數(shù)，要判斷是否存在邊也只需遍歷相應(yīng)邊表。但是對(duì)于有向圖能得到每個(gè)頂點(diǎn)出度，為了便于確定入度可以再建立一個(gè)逆鄰接表。24、 什么是DFS，遍歷后形成什么？時(shí)間和空間復(fù)雜度多少？遍歷節(jié)點(diǎn)順序是否唯一？DFS：圖的深度優(yōu)先遍歷，是一種遞歸過程，是對(duì)樹的先序遍歷的推廣，從某個(gè)頂點(diǎn)開始訪問，然后對(duì)尚未訪問的鄰接點(diǎn)出發(fā)，繼續(xù)深度優(yōu)先遍歷，直到所有和初始頂點(diǎn)路徑相通的頂點(diǎn)都被訪問到。對(duì)于非連通圖，只需對(duì)它的連通分量分別進(jìn)行DFS。

21、BFS：圖的廣度優(yōu)先遍歷，類似于樹的層序遍歷，先初始化一輔助隊(duì)列，從某個(gè)頂點(diǎn)開始訪問，訪問節(jié)點(diǎn)后入隊(duì)，隊(duì)列不為空則隊(duì)列元素出隊(duì)列，然后判斷當(dāng)前出隊(duì)列頂點(diǎn)鄰接點(diǎn)是否訪問過，沒有則訪問入隊(duì)，重復(fù)這一過程。25、 什么是算法？用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。并不是一下子就求出最短路徑，而是一步步求他們之間頂點(diǎn)的最短路徑，在這個(gè)過程中都基于已經(jīng)求出的最短路徑的基礎(chǔ)上。26、 什么是拓?fù)渑判颍渴裁磮D可以拓?fù)渑判?？這種用頂點(diǎn)表示活動(dòng)，用弧來表示活動(dòng)間的優(yōu)先關(guān)系的有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)簡(jiǎn)稱為AOV網(wǎng)。通常，在AOV網(wǎng)中，將所有活動(dòng)排列

22、成一個(gè)拓?fù)湫蛄械倪^程叫做拓?fù)渑判颍颐總€(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次，若頂點(diǎn)a在序列中排在頂點(diǎn)b前面，則在圖中不存在從頂點(diǎn)b到頂點(diǎn)a的路徑。(1)從有向圖中選擇一個(gè)沒有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它.(2)從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊.(3)重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒有前趨的頂點(diǎn)為止.判定網(wǎng)中是否存在環(huán)的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都出現(xiàn)在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)中一定不存在環(huán)。27、 什么是普里姆算法？什么是算法？最小生成樹：權(quán)值之和最小的那顆生成樹稱為最小生成樹。普里姆算法：在所有“其一個(gè)頂點(diǎn)已經(jīng)落在生成樹上，而另一個(gè)頂點(diǎn)尚

23、未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止克魯斯卡爾：新建一個(gè)圖G，G中擁有原圖中相同的節(jié)點(diǎn)，但沒有邊，將原圖中所有的邊按權(quán)值從小到大排序，從權(quán)值最小的邊開始，如果這條邊連接的兩個(gè)節(jié)點(diǎn)于圖G中不在同一個(gè)連通分量中，則添加這條邊到圖G中，重復(fù)，直至圖G中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中。28、 什么是關(guān)鍵路徑？用頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間的有向圖叫AOE網(wǎng)。在項(xiàng)目管理中，關(guān)鍵路徑最長(zhǎng)的那個(gè)路徑，決定了整個(gè)項(xiàng)目的最短完成時(shí)間。把關(guān)鍵路徑上的活動(dòng)成為關(guān)鍵活動(dòng)，關(guān)鍵活動(dòng)影響了整個(gè)工程的時(shí)間，即如果關(guān)鍵活動(dòng)不能按時(shí)完成的話，整

24、個(gè)工程完成時(shí)間就會(huì)受到影響。事件最早發(fā)生時(shí)間：從開始頂點(diǎn)到下一個(gè)頂點(diǎn)最長(zhǎng)路徑長(zhǎng)度。它決定了它后面的活動(dòng)的最早發(fā)生時(shí)間。事件最遲發(fā)生時(shí)間：工程不推遲的前提，該事件最遲必須發(fā)生的時(shí)間，從后往前計(jì)算，邊值最小的。活動(dòng)的最遲發(fā)生時(shí)間：活動(dòng)終點(diǎn)所表示事件最遲發(fā)生時(shí)間與該活動(dòng)所需時(shí)間之差。 查找與排序29、 什么是折半查找？時(shí)間復(fù)雜度多少？前提條件是什么？過程如何？1.必須采用 2.必須按關(guān)鍵字大小有序排列。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一

25、子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。時(shí)間復(fù)雜度：其算法復(fù)雜度為O（log n）30、 什么是哈希表?什么是沖突？普通的查找方法，查找關(guān)鍵字都需要比較，時(shí)間較長(zhǎng)，而哈希表的方法是欲查找關(guān)鍵字的存儲(chǔ)位置是由某個(gè)函數(shù)計(jì)算出來的，它把記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)存儲(chǔ)位置。這種關(guān)系稱為散列函數(shù)。查找步驟：存儲(chǔ)數(shù)據(jù)時(shí)候存儲(chǔ)在通過散列函數(shù)計(jì)算的地址，當(dāng)查找記錄時(shí)通過同樣的散列函數(shù)計(jì)算地址。適用情況：一個(gè)關(guān)鍵字對(duì)應(yīng)很多不適合，范圍查找不適合，排序也不可能。沖突：兩個(gè)不同的關(guān)鍵字用散

26、列函數(shù)計(jì)算出了相同的存儲(chǔ)地址稱為沖突。處理沖突的方法： 開放定址法：空閑地址，同義詞表項(xiàng)可以存，非同義詞也可以。 1.線性探測(cè)法：有沖突就順序查看下一個(gè)單元，可能造成堆積。平方探測(cè)法：1方，-1方，2方，-2方。這個(gè)不堆積但是只能探測(cè)一半。再散列：用別的函數(shù)再試試。偽隨機(jī)數(shù)法： 拉鏈法：把所有同義詞存在一個(gè)線性鏈表中。31、 什么是折半插入排序？時(shí)間空間復(fù)雜度多少？正常插入排序插入時(shí)候，從后往前查找待插入位置，而折半插入是用折半的方法找到插入的位置，然后插入。僅僅是減少了比較元素的次數(shù)，時(shí)間復(fù)雜度仍為O（N方）32、 什么是快速排序？時(shí)間空間復(fù)雜度多少？簡(jiǎn)述基本過程一般用第一個(gè)元素用作基準(zhǔn)數(shù)，

27、但如果是有序花費(fèi)時(shí)間將是二次。一般可以使用三數(shù)取中值分割法?？焖倥判蚴菍?duì)冒泡排序的改進(jìn)，屬于交換排序，基本思想基于分治法，在待排序表中取一個(gè)元素作為基準(zhǔn)，通過一趟排序?qū)⒋判虮韯澐譃楠?dú)立的兩部分。左邊部分小于基準(zhǔn)，右邊大于，這個(gè)過程稱為一趟排序，而后分別遞歸地對(duì)兩個(gè)子表重復(fù)上述過程，直到每部分內(nèi)只有一個(gè)元素或?yàn)榭?，即所有元素放在最終位置上。當(dāng)i<j 時(shí)且 j對(duì)應(yīng)的值大于基準(zhǔn)跳過，碰到小于基準(zhǔn)停下來，i小于j且i從前向后跳過小于基準(zhǔn)的值。如果i小于j，交換然后縮小區(qū)間（i+，j- -) 繼續(xù) 回到開始但前提i小于j33、 什么是堆？有什么用？什么是堆排序？堆可以看成是一棵，如果任意一節(jié)點(diǎn)都

28、小于它的子孫，稱為小項(xiàng)堆，任意節(jié)點(diǎn)大于它子孫稱為大頂堆。作用：可以對(duì)一組數(shù)據(jù)進(jìn)行排序。大數(shù)據(jù)中找出最大的幾個(gè)值，用堆比較快。堆排序：構(gòu)造堆先自下往上調(diào)整，如果建立大根堆，從下往上，從右往左，每個(gè)有孩子的節(jié)點(diǎn)（如果從數(shù)組角度是n/2處向前到1）的關(guān)鍵字小于左右子樹中關(guān)鍵字大者，則交換。反復(fù)利用上述調(diào)整堆的方法建堆，直到根節(jié)點(diǎn)。這樣將R1.n構(gòu)造為初始堆，將當(dāng)前初始堆頂記錄R1和該區(qū)間的最后一個(gè)記錄交換，然后將新的無序區(qū)調(diào)整為堆（亦稱重建堆）。與直接選擇區(qū)別：直接中，為了從R1.n中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R2.n中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面

29、的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。堆排序可通過保存部分比較結(jié)果，可減少比較次數(shù)。34、 你認(rèn)為哪種排序算法最優(yōu)？沒有最好，只有最適合，若n較小，用簡(jiǎn)單的排序算法較好比如簡(jiǎn)單選擇，直接插入，如果數(shù)據(jù)初始狀態(tài)已經(jīng)按關(guān)鍵字基本有序，則選用直接插入或冒泡較好。如果n較大應(yīng)該考慮用那幾個(gè)時(shí)間復(fù)雜度較好的算法，快速排序是被認(rèn)為是目前基于比較的內(nèi)部排序算法中最好的方法，當(dāng)待排序關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短。如果對(duì)負(fù)輔助空間有限制則可以考慮堆排序，另外求大數(shù)據(jù)的最大的幾個(gè)數(shù)，堆排序最適合

30、。如果要求排序穩(wěn)定可以考慮歸并排序。如果n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解，采用基數(shù)排序較好。當(dāng)記錄本身信息量很大，為了避免移動(dòng)，可以考慮鏈表。3、 操作系統(tǒng)部分操作系統(tǒng)概述35、 操作系統(tǒng)用到了那些數(shù)據(jù)結(jié)構(gòu)？舉例說明進(jìn)程調(diào)度后備隊(duì)列，先進(jìn)先出算法短進(jìn)程優(yōu)先算法用了堆動(dòng)態(tài)分區(qū)分配，首次適應(yīng)算法。在此算法中，空閑區(qū)鏈按起始地址遞增順序排列，在進(jìn)行內(nèi)存分配時(shí)，從鏈?zhǔn)组_始順序查找，直到找到一個(gè)能滿足其大小要求的空閑區(qū)為止。循環(huán)首次適應(yīng)算，循環(huán)鏈表。目前廣泛流行公用緩沖池，池中的緩沖區(qū)可供多個(gè)進(jìn)程共享。它把相同類型的緩沖區(qū)鏈成一個(gè)隊(duì)列索引順序文件：記錄分組，索引表中為每組中的第一個(gè)記錄建立一個(gè)索引

31、項(xiàng)，組與組之間關(guān)鍵字必須有序，組中關(guān)鍵字可以無序。通過索引表找到所在組。散列文件：沒有順序特征。文件分配磁盤塊方式：鏈接分配，索引分配。系統(tǒng)調(diào)用的過程？操作系統(tǒng)的組成？提供一系列具備預(yù)定功能的，通過一組稱為系統(tǒng)調(diào)用（system call)的接口呈現(xiàn)給用戶。系統(tǒng)調(diào)用把的請(qǐng)求傳給，調(diào)用相應(yīng)的的內(nèi)核完成所需的處理，將處理結(jié)果返回給應(yīng)用程序。系統(tǒng)調(diào)用通常包括：進(jìn)程控制、文件系統(tǒng)控制、內(nèi)存管理、網(wǎng)絡(luò)管理，進(jìn)程通信等?；竟δ埽禾幚頇C(jī)管理，處理器的分配和運(yùn)行實(shí)施有效的管理，如進(jìn)程控制，同步，通信，調(diào)度。存儲(chǔ)器管理，對(duì)內(nèi)存分配、保護(hù)、擴(kuò)充。設(shè)備管理，對(duì)計(jì)算機(jī)系統(tǒng)內(nèi)的所有設(shè)備實(shí)施有效管理，比如設(shè)備分配，緩沖

32、和虛擬，設(shè)備傳輸控制，設(shè)備獨(dú)立性。文件管理，有效的支持文件的存儲(chǔ)、檢索和修改等操作，解決文件的共享、保護(hù)問題，比如文件存儲(chǔ)空間管理、目錄管理、文件操作管理。用戶接口，方便用戶使用操作系統(tǒng)，通常有命令接口，程序接口，圖形接口。36、 什么是微內(nèi)核？ 什么是shell？操作系統(tǒng)：操作系統(tǒng)是控制和管理整個(gè)計(jì)算機(jī)系統(tǒng)硬件和軟件資源，并合理組織調(diào)度計(jì)算機(jī)的工作和資源分配。進(jìn)程管理 存儲(chǔ)管理 設(shè)備管理 文件管理微內(nèi)核：操作系統(tǒng)的一種體系結(jié)構(gòu)，將最基本的功能保留在內(nèi)核，基于客戶服務(wù)器模式的微內(nèi)核結(jié)構(gòu)，將操作系統(tǒng)劃分兩大部分，微內(nèi)核和服務(wù)器，把操作系統(tǒng)絕大部分功能都放在服務(wù)器中實(shí)現(xiàn)，交互借助于微內(nèi)核通信。優(yōu)點(diǎn)

33、：每個(gè)服務(wù)進(jìn)程允許在獨(dú)立用戶進(jìn)程中，即每個(gè)服務(wù)器失敗不會(huì)引起系統(tǒng)其他服務(wù)器崩潰，可靠性好。還具有良好的靈活性，可以方便增刪服務(wù)功能，便于維護(hù)修改服務(wù)器代碼不會(huì)影響其他部分，適合分布式處理的計(jì)算環(huán)境。缺點(diǎn)：效率不高，所有用戶進(jìn)程都要通過微內(nèi)核相互通信。Shell：編程人員通過系統(tǒng)調(diào)用，api接口來使用操作系統(tǒng)提供的功能，普通用戶不編程，所以操作系統(tǒng)給普通用戶提供一個(gè)shell與用戶交互，shell就是覆蓋在操作系統(tǒng)上的一個(gè)用戶界面，可以是圖形的比如window，也可以是文本，比如linux，用戶可以輸入命令操作系統(tǒng)，不是進(jìn)行直接系統(tǒng)調(diào)用。進(jìn)程管理37、 作業(yè)與進(jìn)程的區(qū)別一個(gè)進(jìn)程是一個(gè)程序?qū)δ硞€(gè)數(shù)

34、據(jù)集的執(zhí)行過程，是分配資源的基本單位。作業(yè)是用戶需要計(jì)算機(jī)完成的某項(xiàng)任務(wù)，是要求計(jì)算機(jī)所做工作的集合。38、 進(jìn)程和程序有什么區(qū)別？進(jìn)程是程序及其數(shù)據(jù)在計(jì)算機(jī)上的一次運(yùn)行活動(dòng)，是一個(gè)動(dòng)態(tài)概念，而程序是一組有序的指令集合，是一種靜態(tài)的概念進(jìn)程是程序的一次執(zhí)行過程它是動(dòng)態(tài)地創(chuàng)建和消亡的具有一定的生命周期是暫時(shí)存在的，程序則是一組代碼集合，是永久存在可長(zhǎng)期保存的。進(jìn)程可以創(chuàng)建進(jìn)程，程序不能創(chuàng)建新程序。39、 進(jìn)程和線程有什么區(qū)別？什么是進(jìn)程樹？進(jìn)程是資源擁有的基本單位，線程是獨(dú)立調(diào)度的基本單位，而不用有系統(tǒng)資源，當(dāng)可訪問其隸屬進(jìn)程的系統(tǒng)資源，不僅進(jìn)程之間可以并發(fā)，同一進(jìn)程內(nèi)的多個(gè)線程也能，進(jìn)一步提高

35、了并發(fā)度，由于創(chuàng)建和撤銷進(jìn)程系統(tǒng)都要為之分配或回收資源，保存當(dāng)前環(huán)境等開銷遠(yuǎn)大于創(chuàng)建或撤銷線程。進(jìn)程樹是一個(gè)形象化的比喻，比如一個(gè)進(jìn)程啟動(dòng)了一個(gè)程序，而啟動(dòng)的這個(gè)進(jìn)程就是原來那個(gè)進(jìn)程的子進(jìn)程，形成的一種樹形的結(jié)構(gòu)。40、 簡(jiǎn)述進(jìn)程的狀態(tài)與轉(zhuǎn)換新建完進(jìn)程分配了必要資源，進(jìn)入就緒狀態(tài)，這時(shí)只需要得到處理就進(jìn)程就能運(yùn)行，進(jìn)入運(yùn)行狀態(tài)后，需要等待某個(gè)資源進(jìn)入阻塞狀態(tài)，資源到位了進(jìn)入就緒隊(duì)列等待處理機(jī)。運(yùn)行完事進(jìn)入終止?fàn)顟B(tài)，資源回收。41、 進(jìn)程間的通信有幾種方式？共享存儲(chǔ)：在通信進(jìn)程之間存在一塊可直接訪問的共享空間，通過對(duì)這段空間的讀寫實(shí)現(xiàn)進(jìn)程之間的信息交換，在對(duì)共享空間進(jìn)行寫/讀操作時(shí)，需要使用同步

36、互斥工具。消息傳遞：數(shù)據(jù)交換是以格式化的消息為但單位，操作系統(tǒng)提供的消息傳遞方式，有直接通信方式和間接通信方式。管道通信：管道就是連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，向管道提供輸入的發(fā)送進(jìn)程以字符流形式將大量數(shù)據(jù)送入管道，接受管道輸出的進(jìn)程，則從管道中接受數(shù)據(jù)，為了協(xié)調(diào)雙方通信，管道機(jī)制需提供互斥、同步和確定對(duì)方的存在。42、 什么叫饑餓？段作業(yè)優(yōu)先算法時(shí)候，長(zhǎng)作業(yè)一直得不到處理機(jī)43、 進(jìn)程的調(diào)度算法有哪些?分別簡(jiǎn)述先來先服務(wù)，缺點(diǎn)短作業(yè)可能等待很長(zhǎng)時(shí)間，平均響應(yīng)時(shí)間很慢。短任務(wù)優(yōu)先算法：平均響應(yīng)時(shí)間最優(yōu)，分為搶占和非搶占，容易餓死長(zhǎng)任務(wù)。高響應(yīng)比：優(yōu)先權(quán)=等待時(shí)間+

37、要求服務(wù)時(shí)間/要求服務(wù)時(shí)間既照顧了短作業(yè)，又不會(huì)使長(zhǎng)作業(yè)得不到服務(wù)。分時(shí)（時(shí)間片）：選擇適當(dāng)時(shí)間片，過大退化成FCFS過小切換所用時(shí)間多。優(yōu)先級(jí)：靜態(tài)優(yōu)先級(jí)不變，動(dòng)態(tài)優(yōu)先級(jí)，執(zhí)行了降低優(yōu)先級(jí)。多級(jí)反饋隊(duì)列調(diào)度算法：設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高，依次降低，各隊(duì)列中進(jìn)程內(nèi)時(shí)間片的大小也不相同，最高優(yōu)先級(jí)的時(shí)間片最小，依次升高。當(dāng)一個(gè)進(jìn)程進(jìn)入內(nèi)存后，先進(jìn)入優(yōu)先級(jí)最高隊(duì)尾，等待調(diào)度，當(dāng)運(yùn)行時(shí)候如果在該時(shí)間片結(jié)束，便可撤離了，沒完成就進(jìn)入第二個(gè)隊(duì)列末尾等待，依次進(jìn)行，如果在最后一個(gè)隊(duì)列執(zhí)行一次還沒完成，就在這隊(duì)列繼續(xù)排隊(duì)。僅當(dāng)?shù)谝魂?duì)列空閑時(shí)候，調(diào)度程序才會(huì)調(diào)度第二隊(duì)

38、中進(jìn)程運(yùn)行，優(yōu)先級(jí)高的隊(duì)列空閑，優(yōu)先級(jí)低才會(huì)被調(diào)度，如果優(yōu)先級(jí)低的隊(duì)列正在執(zhí)行，優(yōu)先級(jí)高隊(duì)列有進(jìn)程進(jìn)入，則調(diào)度程序把正在執(zhí)行的進(jìn)程放在這隊(duì)的末尾，優(yōu)先級(jí)高的先執(zhí)行。實(shí)時(shí)最早截止時(shí)間優(yōu)先（EDF）：開始截止時(shí)間確定優(yōu)先級(jí)。最低松弛度優(yōu)先（LLF）：根據(jù)任務(wù)緊急程度來確定優(yōu)先級(jí)。44、 什么是軟實(shí)時(shí)，什么是硬實(shí)時(shí)？硬實(shí)時(shí)系統(tǒng)有一個(gè)剛性的、不可改變的時(shí)間限制，它不允許任何超出時(shí)限的錯(cuò)誤。超時(shí)錯(cuò)誤會(huì)帶來?yè)p害甚至導(dǎo)致系統(tǒng)失敗、或者導(dǎo)致系統(tǒng)不能實(shí)現(xiàn)它的預(yù)期目標(biāo)。 軟實(shí)時(shí)系統(tǒng)的時(shí)限是一個(gè)柔性靈活的，它可以容忍偶然的超時(shí)錯(cuò)誤。失敗造成的后果并不嚴(yán)重，僅僅是輕微的降低了系統(tǒng)的吞吐量。45、 什么是PV操作？簡(jiǎn)述

39、PV操作要點(diǎn)及注意事項(xiàng)。信號(hào)量是最早出現(xiàn)的用來解決進(jìn)程同步與互斥問題的機(jī)制，包括一個(gè)稱為信號(hào)量的變量及對(duì)它進(jìn)行的兩個(gè)原語(yǔ)操作p操作和v操作，這兩個(gè)操作是不可中斷的程序段，稱為原語(yǔ)。P原語(yǔ)操作的動(dòng)作是：信號(hào)量減1；若減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；若減1后小于零，則該進(jìn)程被阻塞后進(jìn)入與該信號(hào)相對(duì)應(yīng)的隊(duì)列中V原語(yǔ)操作的動(dòng)作是：信號(hào)量加1；若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行；若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程。信號(hào)量必須成對(duì)使用。且在P,V愿語(yǔ)執(zhí)行期間不允許有中斷的發(fā)生。P,V原語(yǔ)不但可以解決進(jìn)程管理當(dāng)中的互斥問題，而且我們還可以利用此方法解決進(jìn)程同步與進(jìn)程通信的問題。

40、同步時(shí)候信號(hào)量初始為0，互斥時(shí)候?yàn)?。46、 什么是死鎖？有什么解決辦法？死鎖：多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將無法向前推進(jìn)。原因：是資源的爭(zhēng)奪，或進(jìn)程推進(jìn)順序非法。必要條件：資源為臨界資源、進(jìn)程所獲得資源在用完之前不可強(qiáng)行奪走，只能主動(dòng)釋放，進(jìn)程已經(jīng)保持了至少一個(gè)資源，但有提出了新的資源請(qǐng)求，但該資源以被占用了，循環(huán)等待條件，存在一種進(jìn)程資源的循環(huán)等待鏈。預(yù)防死鎖：這是一種較簡(jiǎn)單和直觀的事先預(yù)防的方法。方法是通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或者幾個(gè)，來預(yù)防發(fā)生死鎖。但是由于所施加的限制條件往往太嚴(yán)格，可能會(huì)導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量

41、降低。避免死鎖：該方法同樣是屬于事先預(yù)防的策略，但它并不須事先采取各種限制措施去破壞產(chǎn)生死鎖的的四個(gè)必要條件，而是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。檢測(cè)死鎖：這種方法并不須事先采取任何限制性措施，也不必檢查系統(tǒng)是否已經(jīng)進(jìn)入不安全區(qū)，此方法允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。但可通過系統(tǒng)所設(shè)置的檢測(cè)機(jī)構(gòu)，及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源，然后采取適當(dāng)措施，從系統(tǒng)中將已發(fā)生的死鎖清除掉。解除死鎖：這是與檢測(cè)死鎖相配套的一種措施。當(dāng)檢測(cè)到系統(tǒng)中已發(fā)生死鎖時(shí)，須將進(jìn)程從死鎖狀態(tài)中解脫出來。常用的實(shí)施方法是撤銷或掛起一些進(jìn)程，以便回收一些資

42、源，再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運(yùn)行。內(nèi)存管理47、 簡(jiǎn)述內(nèi)存的連續(xù)分配管理方式固定分區(qū)分配，劃分若干個(gè)固定大小區(qū)域，建立分區(qū)說明表，容易產(chǎn)生內(nèi)部碎片。動(dòng)態(tài)分區(qū)分配，又稱可變分區(qū)分配，是一種動(dòng)態(tài)劃分內(nèi)存的分區(qū)方法。不預(yù)先劃分，而是在進(jìn)程裝入內(nèi)存時(shí)候，根據(jù)進(jìn)程大小動(dòng)態(tài)的建立分區(qū)。并使分區(qū)大小正好適合進(jìn)程的需要。因此系統(tǒng)中分區(qū)的大小數(shù)目是可變的。會(huì)產(chǎn)生外部碎片?？捎镁o湊技術(shù)解決，不時(shí)的動(dòng)態(tài)整理。首次適應(yīng)，空閑分區(qū)以地址遞增次序鏈接，找到一個(gè)能滿足要求的分區(qū)。最佳適應(yīng)：分區(qū)按容量遞增形成分區(qū)鏈。最壞適應(yīng)：分區(qū)按容量遞減形式分區(qū)鏈。臨近適應(yīng)：循環(huán)首次適應(yīng)，從上次查找

43、結(jié)束位置開始繼續(xù)查找。48、 程序裝入和鏈接。編譯：將源代碼編譯成若干個(gè)目標(biāo)模塊鏈接：鏈接程序?qū)⒕幾g后形成的目標(biāo)模塊，以及所需庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。鏈接分為靜態(tài)，裝入時(shí)動(dòng)態(tài)，運(yùn)行時(shí)動(dòng)態(tài)裝入：由裝入程序裝入模塊裝入內(nèi)存中運(yùn)行。分為絕對(duì)裝入，可重定位，靜態(tài)重定位一次性完成，動(dòng)態(tài)重定位。49、 常用內(nèi)存保護(hù)方法有哪些？頁(yè)表機(jī)制里，頁(yè)表寄存器中有頁(yè)表起始地址，和頁(yè)表長(zhǎng)度，比較頁(yè)號(hào)和頁(yè)表長(zhǎng)度如果大于頁(yè)表長(zhǎng)度則產(chǎn)生越界中斷。50、 什么是交換技術(shù)？什么是覆蓋技術(shù)？及其區(qū)別覆蓋：把一個(gè)用戶空間分成一個(gè)固定分區(qū)和若干個(gè)覆蓋區(qū)，活躍部分放入固定區(qū)，其余部分先放即將訪問的進(jìn)覆蓋區(qū)，其他需要時(shí)候

44、在調(diào)入覆蓋原有的段。交換：把處于等待狀態(tài)的程序從內(nèi)存移到外存，騰出空間這叫換出，然后把準(zhǔn)備好競(jìng)爭(zhēng)CPU運(yùn)行的程序從外存調(diào)入內(nèi)存，這叫換入。51、 什么是拼接技術(shù)？就是緊湊技術(shù)：動(dòng)態(tài)分區(qū)分配回收時(shí)候，將其余空閑分區(qū)合并為一個(gè)大的空閑分區(qū)。52、 簡(jiǎn)述內(nèi)存的非連續(xù)非配管理方式（段、頁(yè)）非連續(xù)分配根據(jù)分區(qū)大小是否固定分為，分頁(yè)存儲(chǔ)管理和分段存儲(chǔ)管理。分頁(yè)存儲(chǔ)管理方式又根據(jù)是否要把作業(yè)的所有頁(yè)面都裝入內(nèi)存分為基本分頁(yè)存儲(chǔ)方式，和請(qǐng)求分頁(yè)存儲(chǔ)方式基本分頁(yè)存儲(chǔ)管理方式：把主存空間分為大小相等且固定的塊，相對(duì)較小，作為主存的基本單位，每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時(shí)，以塊為單位逐個(gè)申請(qǐng)主存中的塊空

45、間。與固定分區(qū)技術(shù)的區(qū)別是塊的大小相對(duì)于分區(qū)較多，而且進(jìn)程也按照塊進(jìn)行劃分，進(jìn)程運(yùn)行時(shí)按塊申請(qǐng)主存可用空間并執(zhí)行，只會(huì)在最后一個(gè)不完整塊產(chǎn)生內(nèi)部碎片。進(jìn)程在執(zhí)行過程中需要申請(qǐng)主存空間，就是要為每個(gè)頁(yè)面分配主存中的可用葉框，這就產(chǎn)生了頁(yè)和葉匡的一一對(duì)應(yīng)。頁(yè)面大小要適中，太小頁(yè)表長(zhǎng)，頁(yè)內(nèi)碎片增大，降低內(nèi)存的利用率。一般每頁(yè)大小4KB，所以頁(yè)內(nèi)偏移量12位，頁(yè)號(hào)20位，地址最多2的20此方頁(yè)。頁(yè)表：為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程創(chuàng)建一張頁(yè)表，記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，頁(yè)表一般在內(nèi)存中。頁(yè)表作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的映射。頁(yè)表寄存器PTR存放頁(yè)表在內(nèi)存地址，和

46、頁(yè)表長(zhǎng)度。進(jìn)程未執(zhí)行放在進(jìn)程控制塊中，執(zhí)行存入。TLB快表：若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存，一次是訪問頁(yè)表，確定物理地址，一次是取數(shù)據(jù)和指令。這顯然比通常執(zhí)行指令慢一倍，所以增加一個(gè)具有并行查找能力的高速緩存存儲(chǔ)器-快表。又稱聯(lián)想寄存器，用來存放當(dāng)前訪問的若干表項(xiàng)，比較的時(shí)候是將頁(yè)與塊表中的所有頁(yè)號(hào)同時(shí)進(jìn)行比較，找到取出，如果沒有則訪問主存中頁(yè)表，讀出后同時(shí)放入快表中，以便后面可能再次訪問，但若塊表以滿則按著一定算法對(duì)舊頁(yè)表進(jìn)行替換。頁(yè)表占空間太大可以用兩級(jí)頁(yè)表，進(jìn)程執(zhí)行只需調(diào)入最高級(jí)頁(yè)表就可以，進(jìn)程的頁(yè)表和進(jìn)程本身的頁(yè)面，可以再后面的執(zhí)行中再調(diào)入。分段管理：

47、分頁(yè)是從計(jì)算機(jī)角度考慮設(shè)計(jì)，提高內(nèi)存利用率，而且通過硬件機(jī)制，對(duì)用戶完全透明，分段管理方式的提出考慮了用戶程序員以滿足編程方便，信息保護(hù)和共享等多方面需求。段內(nèi)要求連續(xù)，段間不要求連續(xù)，作業(yè)地址空間是二維的。最大段長(zhǎng)64KB，段號(hào)為16位，段內(nèi)偏移量為16位。段式系統(tǒng)中段號(hào)和段內(nèi)偏移量必須由用戶顯示提供。段表映射了邏輯空間和內(nèi)存空間。段表項(xiàng)記錄了起址和段長(zhǎng)。分段系統(tǒng)共享是通過兩個(gè)作業(yè)的段表中相應(yīng)表指向被共享的段的同一個(gè)物理副本實(shí)現(xiàn)的。不能修改的代碼稱為純代碼和可重入代碼這樣代碼不能修改數(shù)據(jù)是可以共享的。段頁(yè)式：將兩種存儲(chǔ)管理方法結(jié)合起來，形成了段頁(yè)式存儲(chǔ)管理方式。作業(yè)地址空間首先分成若干邏輯段

48、，每段都有自己段號(hào)，然后每一段分成若干大小固定的頁(yè)。對(duì)內(nèi)存空間管理仍然和分頁(yè)一樣。邏輯地址三部分，段號(hào)，頁(yè)號(hào)，偏移量。段表項(xiàng)報(bào)考段號(hào)，頁(yè)表長(zhǎng)度，頁(yè)表起始地址。頁(yè)表項(xiàng)包括頁(yè)號(hào)和塊號(hào)。53、 簡(jiǎn)述虛擬存儲(chǔ)器的原理傳統(tǒng)存儲(chǔ)管理方式一次性，駐留性不換出。局部性原理，空間局部性，一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元頁(yè)將被訪問，指令通常說順序存放，順序執(zhí)行的，數(shù)據(jù)也一般以數(shù)組等方式簇聚存儲(chǔ)的。時(shí)間局部性，某一指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行，數(shù)據(jù)被訪問過，不久以后數(shù)據(jù)有可能再次被訪問。原因是程序有循環(huán)。基于局部性原理，在程序裝入時(shí)候，可以將程序的一部分裝入內(nèi)存，其余部分留在外存

49、，就可以啟動(dòng)程序執(zhí)行，在程序執(zhí)行過程中，訪問的信息不存在內(nèi)存，由系統(tǒng)將所需的部分調(diào)入內(nèi)存然后繼續(xù)執(zhí)行程序，另一方面將暫時(shí)不使用的內(nèi)存換出道外存。從而騰出空間存放將要掉入內(nèi)存的信息，這樣系統(tǒng)好像為用戶提供了一個(gè)比實(shí)際內(nèi)存大的多的存儲(chǔ)器，稱為虛擬存儲(chǔ)器。實(shí)現(xiàn)：請(qǐng)求分頁(yè)，請(qǐng)求分段，請(qǐng)求段頁(yè)式存儲(chǔ)管理硬件支持：內(nèi)存外存，也表機(jī)制，中斷機(jī)構(gòu)，地址變換機(jī)構(gòu)。請(qǐng)求分頁(yè)管理方式：建立在基本分頁(yè)管理方式，為了支持虛擬存儲(chǔ)器功能，增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能。每當(dāng)要訪問的頁(yè)面不在內(nèi)存時(shí)候，便產(chǎn)生了一個(gè)缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺的頁(yè)面調(diào)入內(nèi)存，此時(shí)將缺頁(yè)進(jìn)程阻塞，調(diào)完喚醒，內(nèi)存有空閑塊則分配，將要掉入的頁(yè)裝入該塊

50、，并修改頁(yè)表中相應(yīng)表項(xiàng)，若此時(shí)沒有空閑塊，則按著一定算法置換。修改過還寫回，與一般中斷比可以再指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。54、 簡(jiǎn)述各種頁(yè)面置換算法（LRU、CLOCK）LRU是如何實(shí)現(xiàn)的？最佳，以后不會(huì)使用的淘汰。不可能實(shí)現(xiàn)。先進(jìn)先出：優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁(yè)面。最近最久未使用LRU置換算法：淘汰最近最長(zhǎng)時(shí)間未訪問過的頁(yè)面，該算法未每個(gè)頁(yè)面設(shè)置一個(gè)訪問字段，來記錄頁(yè)面自上次被訪問以來所經(jīng)歷的時(shí)間，淘汰頁(yè)面時(shí)候選擇現(xiàn)有頁(yè)面中值最大的。需要棧支持?？衫靡粋€(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問某頁(yè)面時(shí)，便將頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁(yè)

51、面的編號(hào)民，而棧底則是最近最久未使用的頁(yè)面的頁(yè)面號(hào)。Clock算法：LRU接近最佳置換算法，性能好但是開銷大，F(xiàn)IFO簡(jiǎn)單但是性能差，CLOCK算法比較小的開銷接近LRU的性能，最近未用（NRU），給每一幀關(guān)聯(lián)一個(gè)附加位，稱為使用位，當(dāng)某一頁(yè)首次裝入主存，該幀使用位設(shè)置1，隨后再被訪問頁(yè)被置1，替換算法把候選幀集合看成一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之關(guān)聯(lián)， 當(dāng)某一頁(yè)被替換時(shí)該指針被設(shè)置成指向緩沖區(qū)的下一幀。當(dāng)需要替換一頁(yè)時(shí)候，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位為0的一幀，每當(dāng)遇到為1的改0，如果所有都為0則替換第一個(gè)，所有都為1則全改0一圈回來后替換第一個(gè)，由于循環(huán)檢查各頁(yè)情況，所以CLOCK

52、。優(yōu)化：加一個(gè)修改位，改了的為1， 系統(tǒng)先找沒訪問過頁(yè)沒修改過的，不對(duì)使用位修改，找不到的找沒訪問，改了的，這次過去使用位改0，找不到，回原點(diǎn)從新來，這回一定能找到了。由于修改的頁(yè)面需要寫回。這樣節(jié)省時(shí)間。55、 什么是TLB（快表）？有什么用？原理？TLB塊表：若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存，一次是訪問頁(yè)表，確定物理地址，一次是取數(shù)據(jù)和指令。這顯然比通常執(zhí)行指令慢一倍，所以增加一個(gè)具有并行查找能力的高速緩存存儲(chǔ)器-快表。又稱聯(lián)想寄存器，用來存放當(dāng)前訪問的若干表項(xiàng)，比較的時(shí)候是將頁(yè)與塊表中的所有頁(yè)號(hào)同時(shí)進(jìn)行比較，找到取出，如果沒有則訪問主存中頁(yè)表，讀出后同時(shí)放

53、入快表中，以便后面可能再次訪問，但若塊表以滿則按著一定算法對(duì)舊頁(yè)表進(jìn)行替換。IO管理和文件56、 什么是設(shè)備無關(guān)性？應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備。為了實(shí)現(xiàn)設(shè)備獨(dú)立性，在程序中使用邏輯設(shè)備名來請(qǐng)求，使用某類設(shè)備，在系統(tǒng)中設(shè)置邏輯設(shè)備表。用于將邏輯設(shè)備名映射為物理設(shè)備名。這樣多個(gè)進(jìn)程可以分時(shí)使用同一個(gè)設(shè)備了。57、 磁盤調(diào)度算法有哪些？先來先服務(wù)：僅適用于請(qǐng)求磁盤IO的進(jìn)程數(shù)目較少的場(chǎng)合最簡(jiǎn)單的一種磁盤調(diào)度算法，根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度。優(yōu)點(diǎn)：簡(jiǎn)單，公平，每一個(gè)請(qǐng)求的進(jìn)程都能夠得到處理，不會(huì)出現(xiàn)長(zhǎng)期得不到處理的進(jìn)程。缺點(diǎn)：未對(duì)尋道進(jìn)行優(yōu)化，致使平均尋道時(shí)間可能較長(zhǎng)。最短尋道時(shí)間優(yōu)

54、先：該算法選擇這樣的進(jìn)程，其要求訪問的磁道，與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，但這種算法不能保證平均尋道時(shí)間最短優(yōu)點(diǎn)：較FCFS有更好的尋道性能缺點(diǎn)：可能導(dǎo)致老進(jìn)程饑餓，可能會(huì)出現(xiàn)磁臂黏著掃描算法：也叫電梯調(diào)度算法在SSTF算法基礎(chǔ)上優(yōu)化而得到，可以防止老進(jìn)程饑餓。該算法不僅考慮到被訪問磁道和當(dāng)前磁頭之間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。(應(yīng)該選取同方向且距離最近的磁道訪問。)優(yōu)點(diǎn)：磁頭雙向移動(dòng)，不會(huì)產(chǎn)生饑餓，平均尋道時(shí)間短。缺點(diǎn)：可能會(huì)出現(xiàn)磁臂黏著循環(huán)掃描算法：為了減少延遲，CSCAN規(guī)定磁頭單向移動(dòng)，當(dāng)從里到最外后，磁頭立即返回到最里的欲訪問磁道，然后繼續(xù)向外。

55、優(yōu)點(diǎn)：磁頭單向移動(dòng)，不會(huì)產(chǎn)生饑餓，平均尋道時(shí)間短。58、 文件共享的方式又哪些？硬連接：基于索引節(jié)點(diǎn)的共享方式，諸如文件的物理地址以及其他的文件屬性等信息，不再是放在目錄項(xiàng)中，而是放在索引節(jié)點(diǎn)中。文件目錄只設(shè)置文件名以及指向相應(yīng)索引節(jié)點(diǎn)的指針，索引節(jié)點(diǎn)還應(yīng)有一個(gè)鏈接計(jì)數(shù)。軟連接：符號(hào)鏈為讓B共享用戶A的一個(gè)共享文件F，可以由系統(tǒng)創(chuàng)建一個(gè)LINK類型的新文件也取名為F，并將文件F寫入用戶B的目錄中，指向這個(gè)鏈接文件，其實(shí)就是快捷方式。59、 文件分配方式有哪些？連續(xù)分配：每個(gè)文件在磁盤上占一組連續(xù)塊，支持順序訪問和直接訪問，優(yōu)點(diǎn)是簡(jiǎn)單，存取速度快。缺點(diǎn)是文件長(zhǎng)度不宜動(dòng)態(tài)增加。增加需大量移動(dòng)。鏈接

56、分配：采取離散分配，消除外部碎片，提高了磁盤利用率，根據(jù)當(dāng)前需要分配必需的盤塊，當(dāng)文件動(dòng)態(tài)增長(zhǎng)時(shí)，可以動(dòng)態(tài)再為它分配盤塊。隱式鏈接：每個(gè)文件對(duì)應(yīng)一個(gè)磁盤塊的鏈表，磁盤塊分布在磁盤的任何地方，除最后一個(gè)盤塊外，每個(gè)盤塊都由指向下一個(gè)盤塊的指針。顯示連鏈接：把指針顯式存放在內(nèi)存中一張連接表中，該表在整個(gè)磁盤設(shè)置一張，每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號(hào)。顯著提高了檢索速度，大大減少了訪問磁盤的次數(shù)，由于分配給文件的所有盤塊號(hào)都放在該表中，故稱該表為文件分配表（FAT）索引分配：把每個(gè)文件的所有盤塊號(hào)都集中放在一起構(gòu)成索引塊表。為了處理大文件，可以鏈接多個(gè)索引塊，也可以多層索引?；旌纤饕喊讯喾N索

57、引分配方式相結(jié)合的分配方式。60、 文件存儲(chǔ)空間管理空閑表法：與內(nèi)存動(dòng)態(tài)分配相似空閑鏈表法：將所有空閑盤區(qū)拉成一條空閑鏈。位示圖：磁盤上每個(gè)盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)61、 簡(jiǎn)述緩沖池原理緩沖池：由多個(gè)系統(tǒng)公用的緩沖區(qū)組成，緩沖區(qū)按其使用情況可以形成三個(gè)隊(duì)列，空緩沖隊(duì)列、裝滿輸入數(shù)據(jù)的緩沖隊(duì)列（輸入隊(duì)列）和裝滿輸出數(shù)據(jù)的隊(duì)列（輸出隊(duì)列），還有四個(gè)緩沖區(qū)：用于收容輸入數(shù)據(jù)緩沖區(qū)、用于提取輸入數(shù)據(jù)的工作緩沖區(qū)、用于收容輸出數(shù)據(jù)的工作緩沖區(qū)以及用于提取輸出數(shù)據(jù)的工作緩沖區(qū)。當(dāng)輸入進(jìn)程需要輸入數(shù)據(jù)時(shí)，從空緩沖隊(duì)列隊(duì)首摘下一個(gè)空緩沖區(qū)，把它作為收容輸入工作緩沖區(qū)，然后把輸入數(shù)據(jù)輸入其中，裝滿后再掛到輸入隊(duì)列末尾。當(dāng)計(jì)算機(jī)進(jìn)程要輸入數(shù)據(jù)時(shí)，便從輸入隊(duì)列取得一個(gè)空緩沖區(qū)作為提取輸入工作緩沖區(qū)，計(jì)算進(jìn)程從中提取數(shù)據(jù)，數(shù)據(jù)用完后再將它掛到空緩沖隊(duì)列尾。當(dāng)計(jì)算機(jī)進(jìn)程需要輸入數(shù)據(jù)時(shí)，便從空緩沖隊(duì)列的隊(duì)首取得空緩沖區(qū)，作為收容輸出工作緩沖區(qū)，當(dāng)其中裝滿輸出數(shù)據(jù)后，再將它掛到輸出隊(duì)列隊(duì)尾。當(dāng)要輸出時(shí)，有輸出進(jìn)程從輸出隊(duì)列中取得一個(gè)裝滿輸出數(shù)據(jù)的緩沖區(qū)，作為提取輸出工