南京航空航天大學(xué)2002年操作系統(tǒng)考研試題
來源：
時間：2007-06-06 14:33:44
一、填空（每小題5分，共20分）
（注意：答題時先給出填空內(nèi)容，再作必要的說明）
1、設(shè)系統(tǒng)中僅有一個資源類，其中共有3個資源實例，使用此類資源的進(jìn)程共有3個，每個進(jìn)程至少請求一個資源，它們所需資源最大量的總和為X，則發(fā)生死鎖的必要條件是：_________。
2、在一個請求分頁系統(tǒng)中，采用先進(jìn)先出頁面置換算時，假如一個作業(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 y
S2： b:=z 1
S3： c:=a-b
S4： w:=c 1
S1和S2兩條語句_________并發(fā)執(zhí)行，S3和S4兩條語句_________并發(fā)執(zhí)行。（本小題填空時考慮：是否可以并發(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、Intel 80386在保模式下工作時，為什么對內(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ū)一樣大，同一時刻只能由一個進(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)用的處理過程。你可以按照一個你熟悉的操作系統(tǒng)（如UNIX、WINDOWS、LINUX）來說明，也可以介紹你自己根據(jù)某個硬件環(huán)境設(shè)計的系統(tǒng)調(diào)用的處理過程。
六、（15分）
頁表設(shè)計。某系統(tǒng)采用了兩級頁表機(jī)制，可使頁表所占用內(nèi)存盡量少，分頁地址變換機(jī)構(gòu)如下圖：
頁目錄表共1024項，每個頁表1024項。地址轉(zhuǎn)換時，先由分段部件生成線性地址，再由上面所述的分頁部件，根據(jù)線性地址中的頁目錄索引在頁目錄表中找相應(yīng)的項，該項中為所需頁表在內(nèi)存的塊號，找到該頁表后，然后按第21－12位的頁表索引找到所需頁的內(nèi)存塊號，把它與12位偏移相加得到32位的物理地址。
設(shè)系統(tǒng)有如表6.1中所示的10個段，已知：1－8段從內(nèi)存的200000H處開始由低地址到高地址連續(xù)存放，映射到3G＋4M開始的線性地址空間；9段（緩沖區(qū)）放在400000H開始的內(nèi)存，映射的線性地址同物理地址；顯存從B8000H開始，映射到3G開始的線性地址空間。本題用的頁目錄表和頁表如表6.2中所示，所有頁表連續(xù)存放。
表6.1
1、請按下面的格式設(shè)計頁目錄表和頁表
表6.2
2、線性地址為：C0401010H、C0404010H、C0414010H，則物理地址是多少，所在段的段名是什么？
南京航空航天大學(xué)2002年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計試題
一、將下列稀疏矩陣的非零元素表示成三元組的形式和十字鏈表的形式。
二、設(shè)一棵二叉樹的層次遍歷序列為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,并采用開放定址法處理沖突，隨機(jī)探測再散列的下一地址公式為：
d1=H (key )
di=( di-1 7 * key ) % 11 （I=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，并要求利用原表結(jié)點。
七、已知一棵二叉樹用二叉鏈表存儲，root 指向根結(jié)點，p指向樹中任一結(jié)點。編程，輸出從root 到p 之間路徑上的結(jié)點。
八、已知一棵樹用孩子－兄弟鏈表存儲。編程，計算該樹的葉子數(shù)。
九、設(shè)有n 個整數(shù)組成的序列，每個整數(shù)為－1，0，1之一。編寫一個時間復(fù)雜度為O（n）的算法，使該序列按負(fù)數(shù)、零、正數(shù)的次序排好。
十、已知n個頂點的帶權(quán)圖用鄰接矩陣表示，編寫函數(shù)，實現(xiàn)用Kruskal算法構(gòu)造最小生成樹，要求對函數(shù)中所使用的變量和內(nèi)容做詳細(xì)的注釋說明。
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。
閱讀全文
招生服務(wù)平臺始創(chuàng)于1999年
打開微信掃一掃，關(guān)注育路教育官方微信
