1、南京航空航天大學(xué)計算機考研試卷操作系統(tǒng)部分2000年操作系統(tǒng)考研試卷一、名詞術(shù)語解釋 每小題 4分，共 20分）1、系統(tǒng)調(diào)用與操作系統(tǒng)內(nèi)核2、進(jìn)程與線程3、頁表與快表4、設(shè)備獨立性5、文件控制塊與索引節(jié)點二、填空 每小題 2分，共 10分）1如果在設(shè)備處理時設(shè)置 I/O進(jìn)程，則不需要I/O進(jìn)程工作時，I/O進(jìn)程處于 狀態(tài)。2、系統(tǒng)中有 3個進(jìn)程，每個進(jìn)程需 2臺打印機，如果系統(tǒng)配有 4臺打印機，則系統(tǒng) _出現(xiàn)死鎖的情況 本題要判斷出現(xiàn)死鎖的可能性）。3、 設(shè)磁盤的I/O請求隊列中的磁道號為：98, 183, 37, 122, 14, 124, 65, 67,磁頭初始 位置為50,若采用FCFS

2、先來先服務(wù)）和SSTF最短尋道時間優(yōu)先）的磁盤調(diào)度算法，磁 頭分別移動 、 磁道。4、 可以被多個進(jìn)程在任何時刻共享的代碼必須是 。5、 為了實現(xiàn)CPU與外部設(shè)備的并行工作，系統(tǒng)引入了 硬件機制。三、回答下列問題 每小題 8分,共 48分）1、在操作系統(tǒng)中,何為虛擬存儲器、虛擬設(shè)備、虛擬處理機？2、 進(jìn)程具有哪幾種基本狀態(tài)：對于每一種可能有的狀態(tài)轉(zhuǎn)換。給出一種狀態(tài)轉(zhuǎn)換的原因。需圖示說明）3、 何為磁盤高速緩存：說明它為什么會提高磁盤的I/O速度。4、說明裝入時動態(tài)鏈接 Load-time Dynamic Linking ）與運行時動態(tài)鏈接 Run-time Dynamic Linking ）這

3、兩種程序鏈接方法之間差別。5、 試從物理概念上來說明記錄型信號量和wait 與 signal 操作？6、 簡述 Intel80386 實方式尋址和保護(hù)方式尋址時,內(nèi)存地址的形成過程,最大尋址空間各為多少？四、10分）在測量控制系統(tǒng)中的數(shù)據(jù)采集任務(wù),把所采集的數(shù)據(jù)送一單緩沖區(qū)：計算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計算。試寫出利用信號量機制實現(xiàn)兩者共享單緩沖的同步操 作算法。五、12分）某數(shù)據(jù)處理任務(wù)，要在 PC機上對40M字節(jié)的數(shù)據(jù)文件 集中放在硬盤上）進(jìn)行 排序，文件中每記錄的長度為 50個字節(jié)了。某學(xué)生編艘桓黿鍪褂 ？40K常規(guī)內(nèi)存的排序程序 ,速度很慢。問 ：1、該排序程序運行時,時間主要花

4、費在什么操作上？2、若將 40M 擴展內(nèi)存 ExtendedMemory ）設(shè)置為虛擬盤,運行速度會有多大提高？為什么？請給出使用虛擬盤后的排序算法,僅需用簡練的語言或粗框圖描述該算法。2001 年操作系統(tǒng)考研試卷測試科目 ：操作系統(tǒng)說明 ：答案一律寫在答題紙上一、名詞術(shù)語解釋 每小題 3分共 24分）1 、臨界資源和臨界區(qū)2、進(jìn)程控制塊 PCB3、多道程序設(shè)計4、計算機操作系統(tǒng)5、用戶態(tài)與核心態(tài)6、SPOOLing 系統(tǒng)7、邏輯文件和物理文件8、進(jìn)程映像二、填空 每小題2分，共 10分）1在具有兩級頁表的分頁存儲管理系統(tǒng)中，CPU每次要存取一個數(shù)據(jù)時，須訪問 _次內(nèi)存。2、產(chǎn)生死鎖的必要條件

5、是 :3、 在一個請求分頁存儲管理系統(tǒng)中，某程序的頁面走向為:7， 0， 1， 2， 0， 3， 0， 4， 2，3， 0， 3， 2， 1， 2， 0， 1， 7， 0， 1。假設(shè)分得的頁框數(shù)是 3，并且開始時頁框中是空的， 則分別采用最佳轉(zhuǎn)換算法和LRU頁面轉(zhuǎn)換算法，在訪問過程中發(fā)生缺頁中斷的次數(shù)分別是-和 。4、 一臺計算機有10臺磁帶機被m個進(jìn)程競爭，每個進(jìn)程最多需要三臺磁帶機，那么m為_ 時，系統(tǒng)沒有死鎖的危險。5、磁盤請求以 10,22,20,2， 40,6， 38柱面的次序到達(dá)磁盤驅(qū)動器。尋道時每個柱面移動需要6ms,則采用先到先服務(wù)算法的尋道時間為 ;采用電梯算法 起始移動方向

6、向外）的尋道時間為 。假設(shè)磁頭開始位置在柱面 20）三、回答下列問題 每小題 7分,共 42分）1、何謂系統(tǒng)的安全狀態(tài),試說明銀行家算法避免死鎖的原理？2、 在實現(xiàn)文件系統(tǒng)時把文件目錄的目錄項分解成兩部分:索引結(jié)點和符號名目錄項,有什 么好處？ 需圖示說明）3、在存儲管理中分頁與分段的主要區(qū)別是什么？分頁與分段兩種方法中,哪個更易于實現(xiàn) 共享,為什么？4、 在設(shè)備管理中引入單緩沖，如果從磁盤把一塊數(shù)據(jù)輸入到緩沖區(qū)中花費的時間為B ;把 緩沖區(qū)中的數(shù)據(jù)送到用戶區(qū)，所花費的時間為 M ; CPU對數(shù)據(jù)進(jìn)行處理的時間為 C，則系統(tǒng) 對每一塊數(shù)據(jù)的處理時間是多少？要求寫出由 B，C，M組成的表達(dá)式，并

7、說明其中的道理5、提高磁盤I/O速度的方法有哪些？并分別加以簡單的說明。6、程序順序執(zhí)行和并發(fā)執(zhí)行分別有哪些牲？程序并發(fā)執(zhí)行的條件是什么？對于下列語句, 哪些能并發(fā)執(zhí)行,哪些不能,說明理由。S1:a=5-x; S2:b=a*x ; S3:c=4*x ; S4:d=b+c ; S5:e=d+3 ;四、14分）一個主修動物行為學(xué)、輔修計算機科學(xué)的學(xué)生參加了一個課題,調(diào)查花果山的猴子是否能被教會理解死鎖。他找到一處峽谷,橫跨峽谷拉了一根繩索假設(shè)為南北方向）,這樣猴子就可以攀著繩索越過峽谷人。只要它們朝著相同的方向,同一時刻可以有 多只猴子通過。但是如果在相反的方向上同時有猴子通過則會發(fā)生死鎖這些猴子

8、將被卡在繩索中間,假設(shè)這些猴子無法在繩索上從另一只猴子身上翻過去）。如果一只猴子相越 過峽谷,它必須看當(dāng)前是否有別的猴子在逆向通過。請使用信號量寫一個避免死鎖的程序 來解決該問題。五、10分）在分頁式存儲管理中,什么叫快表,說明其工作原理和過程,畫出具有快表 的地址變換機構(gòu)。2002年操作系統(tǒng)考研試卷一、填空 每小題5分，共 20分）注意:答題時先給出填空內(nèi)容，再作必要的說明）1、設(shè)系統(tǒng)中僅有一個資源類，其中共有3個資源實例，使用此類資源的進(jìn)程共有3個，每個進(jìn)程至少請求一個資源，它們所需資源最大量的總和為X ，則發(fā)生死鎖的必要條件是 :2、在一個請求分頁系統(tǒng)中，采用先進(jìn)先出頁面置換算時，假如一

9、個作業(yè)的頁面走向為1， 2,3, 4, 1, 2, 5, 1, 2, 3, 4, 5,當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，訪問過程中發(fā)生的缺頁次數(shù)為 和。假定開始時，物理塊中為空）3、 設(shè)系統(tǒng)中有三種類型的資源 A、B、C）和五個進(jìn)程P0, P1, P2, P3, P4）,某時刻 的狀態(tài)如下 :根據(jù)銀行家算法可知，該時刻存在著一個安全序列 :_。4、 根據(jù) Bernstein 條件 程序能并發(fā)執(zhí)行，且具有可再現(xiàn)性的條件），則如下4條語句中 :S1: a:=x+yS2:b:=z+1S3:c:=a-bS4:w:=c+1S1和S2兩條語句 并發(fā)執(zhí)行，S3和S4兩條語句 并發(fā)執(zhí)行。本小題填空時考

10、慮 :是否可以并發(fā)執(zhí)行）二、回答下列問題 每小題 6分,共 30分）1 、什么要引入設(shè)備獨立性？如何實現(xiàn)設(shè)備獨立性？2、舉例說明在分頁系統(tǒng)中,如何實現(xiàn)內(nèi)存共享？要求圖示說明。3、從用戶角度看,引入線程后有何好處？4、 生產(chǎn)者一消費者問題的同步算法中，為什么顛倒生產(chǎn)者進(jìn)程中的兩個P操作的次序，將 導(dǎo)致進(jìn)程死鎖？5、Intel80386在保模式下工作時，為什么對內(nèi)存有保護(hù)作用？三10分）進(jìn)程P1和P2通過兩個緩沖區(qū)給進(jìn)程 P11、P12、P21、P22傳遞信息，進(jìn)程 P11、P12取進(jìn)程P1 的信息，進(jìn)程P21、P22取進(jìn)程P2的信息。假定這兩個緩沖區(qū)一樣大小，所要傳遞的信息也 與緩沖區(qū)一樣大，同

11、一時刻只能由一個進(jìn)程往緩沖區(qū)中送信息或取信息。試用PV操作來實現(xiàn)這6個進(jìn)程之間的同步與互斥關(guān)系，只要求寫出進(jìn)程P1與P11的同步算法。四、10分）在DOS、WINDOWS操作系統(tǒng)中使用的FAT文件系統(tǒng)中，一個文件使用的磁盤空間以簇為 單位進(jìn)行分配，并且將一個文件使用的全部簇組成一個鏈表放在FAT表 文件分配表）中；在UNIX中，一個文件使用的磁盤塊號放在I結(jié)點 索引結(jié)點）中。試分析比較這兩種典型的文件物理結(jié)構(gòu),在分析時要考慮到文件大小不同時對性能的影響。五、15分）用戶程序在需要OS提供某種服務(wù)時，是通過系統(tǒng)調(diào)用來完成的。請以一個具體例子如讀寫磁盤、在顯示屏幕上顯示字符等）說明系統(tǒng)調(diào)用的處理過

12、程。你可以按照一個你熟悉的操作系統(tǒng) 如UNIX、WINDOWS、LINUX ）來說明，也可以介紹你自己根據(jù)某個硬件環(huán)境 設(shè)計的系統(tǒng)調(diào)用的處理過程。六、15分）頁表設(shè)計。某系統(tǒng)采用了兩級頁表機制,可使頁表所占用內(nèi)存盡量少,分頁地址變換機構(gòu)如下圖 :頁目錄表共 1024項，每個頁表 1024項。地址轉(zhuǎn)換時，先由分段部件生成線性地址，再由上 面所述的分頁部件，根據(jù)線性地址中的頁目錄索引在頁目錄表中找相應(yīng)的項，該項中為所 需頁表在內(nèi)存的塊號，找到該頁表后，然后按第2112位的頁表索引找到所需頁的內(nèi)存塊號，把它與 12位偏移相加得到 32位的物理地址。設(shè)系統(tǒng)有如表6.1中所示的10個段，已知:1 8段從

13、內(nèi)存的200000H處開始由低地址到高地址連續(xù)存放，映射到3G+ 4M開始的線性地址空間；9段<緩沖區(qū)）放在400000H開始的內(nèi)存， 映射的線性地址同物理地址；顯存從 B8000H開始，映射到3G開始的線性地址空間。本題 用的頁目錄表和頁表如表 6.2中所示，所有頁表連續(xù)存放。表6.11、請按下面的格式設(shè)計頁目錄表和頁表表6.22、線性地址為:C0401010H、C0404010H、C0414010H，則物理地址是多少，所在段的段名是什么？數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研試卷2000年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研試卷測試科目 :數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計說明 :下列每道題 10分，編程題可用任何一種編程語言編

14、寫1、敘述基數(shù)排序算法，并對下列整數(shù)序列圖示其基數(shù)排序的全過程。179，208，93，306，55，859，984，9，271，332、 什么是哈夫曼樹？試證明有 n個葉子的哈夫曼樹共有2n-1個結(jié)點。3、推導(dǎo)并求解n階Hanoi塔問題至少執(zhí)行move操作次數(shù)。4、 設(shè)有三對角矩陣<Aij ） n呦，將其三對角線上元素逐行存于數(shù)組B : 1.m中，使Bk=A ij求:<1 ）用i,j表示k的下標(biāo)變換公式<2）用k表示i,j的下標(biāo)變換公式5、 輸入下列整數(shù)序列，畫出建立的二叉排序樹，最后分別圖示將其中50，86刪除后的二叉 排序樹86，50，78，59，90，64，55，23，

15、100，40，80，456、設(shè)整數(shù)序列a1, a2,，an,給出求解最大值的遞歸程序。7、編程求解無向圖G的所有連通分量。8、設(shè)有帶頭結(jié)點的單鏈表 L,編程對表中任一值只保留一個結(jié)點，刪除其余值相同的結(jié)點。9、 設(shè)T是一棵n元樹，Tb是T的孩子兄弟表示 < 二叉鏈表）的二叉樹，試編程由Tb計算T的 高度。 <要求用非遞歸方法實現(xiàn)）10、 設(shè)以整數(shù)序列a1, a2, a3, a4作為棧S的輸入，利用push, pop操作，寫出所有可能的 輸出,并編程實現(xiàn)算法。南京航空航天大學(xué) 2002年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計試卷一、將下列稀疏矩陣的非零元素表示成三元組的形式和十字鏈表的形式。二、設(shè)一棵二

16、叉樹的層次遍歷序列為ABDEGHJK ,中序遍歷序列為 GDJHKBEA 。<1）畫出這棵二叉樹示意圖<2）說明建立這棵二叉樹的原理三、回答下列B樹<有些教材中稱為B-樹）問題：<1） 一棵4階4層 <根為第一層，葉子為第二層）的B樹，至少有多少關(guān)鍵字，至多有多少關(guān)鍵字<2)在含有n個關(guān)鍵字的m階B樹中進(jìn)行查找時，最多訪問多少個結(jié)點。四、哈希表中使用哈希函數(shù) H<key ) =3*key%11, 并采用開放定址法處理沖突，隨機探測再散列的下一地址公式為:d1=H (key >di=( di-1 +7 * key > % 11 <1=2,3)試在0到10的散列地址空間中對關(guān)鍵字序列<22， 41， 53， 46， 30， 13， 01， 67)畫出 Hash表示意圖，并求在等概率情況下查找成功的平均查找長度。五、求出一棵滿k叉樹的葉子結(jié)點數(shù)n和所有非葉子結(jié)點數(shù) m之間的關(guān)系，給出求解過程。六、已知兩個鏈表 A和B，其元素值遞增排列。編程，將 A和B合并成一個遞減有序 < 相同值 只保留一個)的鏈表C,并要求