南京航空航天大學(xué)2002年操作系統(tǒng)考研試題
來(lái)源：
時(shí)間：2007-06-06 14:33:44
一、填空（每小題5分，共20分）
（注意：答題時(shí)先給出填空內(nèi)容，再作必要的說(shuō)明）
1、設(shè)系統(tǒng)中僅有一個(gè)資源類，其中共有3個(gè)資源實(shí)例，使用此類資源的進(jìn)程共有3個(gè)，每個(gè)進(jìn)程至少請(qǐng)求一個(gè)資源，它們所需資源最大量的總和為X，則發(fā)生死鎖的必要條件是：_________。
2、在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，采用先進(jìn)先出頁(yè)面置換算時(shí)，假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時(shí)，訪問(wèn)過(guò)程中發(fā)生的缺頁(yè)次數(shù)為_(kāi)________和_________。（假定開(kāi)始時(shí)，物理塊中為空）
3、設(shè)系統(tǒng)中有三種類型的資源（A、B、C）和五個(gè)進(jìn)程（P0，P1，P2，P3，P4），某時(shí)刻的狀態(tài)如下：
根據(jù)銀行家算法可知，該時(shí)刻存在著一個(gè)安全序列：____________________________________。
4、根據(jù)Bernstein 條件（程序能并發(fā)執(zhí)行，且具有可再現(xiàn)性的條件），則如下4條語(yǔ)句中：
S1： a:=x y
S2： b:=z 1
S3： c:=a-b
S4： w:=c 1
S1和S2兩條語(yǔ)句_________并發(fā)執(zhí)行，S3和S4兩條語(yǔ)句_________并發(fā)執(zhí)行。（本小題填空時(shí)考慮：是否可以并發(fā)執(zhí)行）
二、回答下列問(wèn)題（每小題6分，共30分）
1、什么要引入設(shè)備獨(dú)立性？如何實(shí)現(xiàn)設(shè)備獨(dú)立性？
2、舉例說(shuō)明在分頁(yè)系統(tǒng)中，如何實(shí)現(xiàn)內(nèi)存共享？要求圖示說(shuō)明。
3、從用戶角度看，引入線程后有何好處？
4、生產(chǎn)者－消費(fèi)者問(wèn)題的同步算法中，為什么顛倒生產(chǎn)者進(jìn)程中的兩個(gè)P操作的次序，將導(dǎo)致進(jìn)程死鎖？
5、Intel 80386在保模式下工作時(shí)，為什么對(duì)內(nèi)存有保護(hù)作用？
三（10分）
進(jìn)程P1和P2通過(guò)兩個(gè)緩沖區(qū)給進(jìn)程P11、P12、P21、P22傳遞信息，進(jìn)程P11、P12取進(jìn)程P1的信息，進(jìn)程P21、P22取進(jìn)程P2的信息。假定這兩個(gè)緩沖區(qū)一樣大小，所要傳遞的信息也與緩沖區(qū)一樣大，同一時(shí)刻只能由一個(gè)進(jìn)程往緩沖區(qū)中送信息或取信息。試用PV操作來(lái)實(shí)現(xiàn)這6個(gè)進(jìn)程之間的同步與互斥關(guān)系，只要求寫(xiě)出進(jìn)程P1與P11的同步算法。
四、（10分）
在DOS、WINDOWS操作系統(tǒng)中使用的FAT文件系統(tǒng)中，一個(gè)文件使用的磁盤(pán)空間以簇為單位進(jìn)行分配，并且將一個(gè)文件使用的全部簇組成一個(gè)鏈表放在FAT表（文件分配表）中；在UNIX中，一個(gè)文件使用的磁盤(pán)塊號(hào)放在I結(jié)點(diǎn)（索引結(jié)點(diǎn)）中。試分析比較這兩種典型的文件物理結(jié)構(gòu)，在分析時(shí)要考慮到文件大小不同時(shí)對(duì)性能的影響。
五、（15分）
用戶程序在需要OS提供某種服務(wù)時(shí)，是通過(guò)系統(tǒng)調(diào)用來(lái)完成的。請(qǐng)以一個(gè)具體例子（如讀寫(xiě)磁盤(pán)、在顯示屏幕上顯示字符等）說(shuō)明系統(tǒng)調(diào)用的處理過(guò)程。你可以按照一個(gè)你熟悉的操作系統(tǒng)（如UNIX、WINDOWS、LINUX）來(lái)說(shuō)明，也可以介紹你自己根據(jù)某個(gè)硬件環(huán)境設(shè)計(jì)的系統(tǒng)調(diào)用的處理過(guò)程。
六、（15分）
頁(yè)表設(shè)計(jì)。某系統(tǒng)采用了兩級(jí)頁(yè)表機(jī)制，可使頁(yè)表所占用內(nèi)存盡量少，分頁(yè)地址變換機(jī)構(gòu)如下圖：
頁(yè)目錄表共1024項(xiàng)，每個(gè)頁(yè)表1024項(xiàng)。地址轉(zhuǎn)換時(shí)，先由分段部件生成線性地址，再由上面所述的分頁(yè)部件，根據(jù)線性地址中的頁(yè)目錄索引在頁(yè)目錄表中找相應(yīng)的項(xiàng)，該項(xiàng)中為所需頁(yè)表在內(nèi)存的塊號(hào)，找到該頁(yè)表后，然后按第21－12位的頁(yè)表索引找到所需頁(yè)的內(nèi)存塊號(hào)，把它與12位偏移相加得到32位的物理地址。
設(shè)系統(tǒng)有如表6.1中所示的10個(gè)段，已知：1－8段從內(nèi)存的200000H處開(kāi)始由低地址到高地址連續(xù)存放，映射到3G＋4M開(kāi)始的線性地址空間；9段（緩沖區(qū)）放在400000H開(kāi)始的內(nèi)存，映射的線性地址同物理地址；顯存從B8000H開(kāi)始，映射到3G開(kāi)始的線性地址空間。本題用的頁(yè)目錄表和頁(yè)表如表6.2中所示，所有頁(yè)表連續(xù)存放。
表6.1
1、請(qǐng)按下面的格式設(shè)計(jì)頁(yè)目錄表和頁(yè)表
表6.2
2、線性地址為：C0401010H、C0404010H、C0414010H，則物理地址是多少，所在段的段名是什么？
南京航空航天大學(xué)2002年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)試題
一、將下列稀疏矩陣的非零元素表示成三元組的形式和十字鏈表的形式。
二、設(shè)一棵二叉樹(shù)的層次遍歷序列為ABDEGHJK，中序遍歷序列為GDJHKBEA。
（1）畫(huà)出這棵二叉樹(shù)示意圖
（2）說(shuō)明建立這棵二叉樹(shù)的原理
三、回答下列B樹(shù)（有些教材中稱為B-樹(shù)）問(wèn)題：
（1）一棵4階4層（根為第一層，葉子為第二層）的B樹(shù)，至少有多少關(guān)鍵字，至多有多少關(guān)鍵字
（2）在含有n個(gè)關(guān)鍵字的m階B樹(shù)中進(jìn)行查找時(shí)，最多訪問(wèn)多少個(gè)結(jié)點(diǎn)。
四、哈希表中使用哈希函數(shù)H（key）=3 * key % 11,并采用開(kāi)放定址法處理沖突，隨機(jī)探測(cè)再散列的下一地址公式為：
d1=H (key )
di=( di-1 7 * key ) % 11 （I=2,3…..）
試在0到10的散列地址空間中對(duì)關(guān)鍵字序列（22，41，53，46，30，13，01，67）畫(huà)出Hash表示意圖，并求在等概率情況下查找成功的平均查找長(zhǎng)度。
五、求出一棵滿k叉樹(shù)的葉子結(jié)點(diǎn)數(shù)n和所有非葉子結(jié)點(diǎn)數(shù)m之間的關(guān)系，給出求解過(guò)程。
六、已知兩個(gè)鏈表A和B，其元素值遞增排列。編程，將A和B合并成一個(gè)遞減有序（相同值只保留一個(gè)）的鏈表C，并要求利用原表結(jié)點(diǎn)。
七、已知一棵二叉樹(shù)用二叉鏈表存儲(chǔ)，root 指向根結(jié)點(diǎn)，p指向樹(shù)中任一結(jié)點(diǎn)。編程，輸出從root 到p 之間路徑上的結(jié)點(diǎn)。
八、已知一棵樹(shù)用孩子－兄弟鏈表存儲(chǔ)。編程，計(jì)算該樹(shù)的葉子數(shù)。
九、設(shè)有n 個(gè)整數(shù)組成的序列，每個(gè)整數(shù)為－1，0，1之一。編寫(xiě)一個(gè)時(shí)間復(fù)雜度為O（n）的算法，使該序列按負(fù)數(shù)、零、正數(shù)的次序排好。
十、已知n個(gè)頂點(diǎn)的帶權(quán)圖用鄰接矩陣表示，編寫(xiě)函數(shù)，實(shí)現(xiàn)用Kruskal算法構(gòu)造最小生成樹(shù)，要求對(duì)函數(shù)中所使用的變量和內(nèi)容做詳細(xì)的注釋說(shuō)明。
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來(lái)源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來(lái)源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來(lái)源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。
閱讀全文
招生服務(wù)平臺(tái)始創(chuàng)于1999年
打開(kāi)微信掃一掃，關(guān)注育路教育官方微信
