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