歷年碩士生入學考試初試科目試題庫_山東科技大學研究生教育學院

1、科目代碼：403 請在答題紙（本）上做題， 在此試卷及草入紙上做題無效！山東科技大學2005年招收碩士學位研究生入學考試數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)試題（共4頁）說明：1、本試卷為數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩部分。數(shù)據(jù)結(jié)構(gòu)部分共六題，滿分100分：操作系統(tǒng)部分共三題滿分50分。全試卷共十題，滿分150分。2、答案一律寫在答題紙上。3、答卷應(yīng)字跡清楚，語義確切。數(shù)據(jù)結(jié)構(gòu)部分注意事項：1、算法應(yīng)說明基本思路，應(yīng)對主要數(shù)據(jù)類型、變量給出說明，所寫算法應(yīng)結(jié)構(gòu)清晰、簡明易懂，應(yīng)加上必要的注釋。2、算法可用（類）PASCAL語言、（類）C語言等你所熟悉的高級語言編寫，但要注明語種。一、解答下列問題（共30分）；1、5分根據(jù)

2、數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)的邏輯結(jié)構(gòu)通常有哪些基本結(jié)構(gòu)？數(shù)據(jù)元素之間的關(guān)系在計算機中有哪幾種表示方式？第1頁p 2、5分將N*N的上三角矩陣A（ij時Aij=0,i 時 Aij0 ）的非零元存儲在一維數(shù)組 B （下標 k 從 0 開始），試給出 Bk 與 Aij 之間的元素對應(yīng)關(guān)系。 3、5分寫出后綴表達式abxcde/-fx+的運算順序。4、5分畫出廣義表（a,(x,y,(x）的存儲結(jié)構(gòu)。5、5分比較哈希表與其它查找表的不同之處。6、5分利用兩個棧S1和S2模擬一個隊列，寫出入隊算法和出隊算法的算法思想。二、10分已知樹T的先序訪問序列為：ABEFCDGHIK后序訪問序列為：EFBCH

3、IKGDA。1、畫出樹T。2、將樹T轉(zhuǎn)換為對應(yīng)的二叉樹BT。3、將二叉樹BT后序線索化。三、15分有一種簡單的排序算法，叫做計數(shù)排序（count sorting）。這種排序算法對一個待排序的表（用數(shù)組表示）進行排序，并將排序結(jié)果存放到另一個新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對某一個記錄，統(tǒng)計出的計數(shù)值為c，那么，這個記p 第2頁錄在新的有序表中的合適的存放位置即為c（如C=0則當前元素存放在新表的號單元）。編程實現(xiàn)計數(shù)排序算法四、15分編寫一遞歸屬算法，刪除單鏈表中所

4、有值為x的結(jié)點。五、15分試寫一算法，求二叉樹T中任意指定兩個結(jié)點最近的共同祖先結(jié)點。六、15分度寫一算法，判斷有向圖G中任意指定兩個結(jié)點之間是否存在路徑。操作系統(tǒng)部分一、判斷題（正確者打錯誤者，每小題1分，共10分）1進程控制塊是進程存在的唯一標識。2作業(yè)調(diào)度是高級調(diào)度，而進程調(diào)度是低級調(diào)度。3時間片越小，系統(tǒng)的響應(yīng)時間就越小，系統(tǒng)物效率就越高。4按首次適應(yīng)算法分配的分區(qū)，一定與作業(yè)要求的容量大小最接近。5在分頁存儲管理中，減少面百大小，可以減少內(nèi)存的浪費。所以，頁面越小越好。6進程A與進程B共享變量S1，需要互斥；進程B與進程C共享變量S2，需要互斥。從而，進程A與進程C也必須互斥。7虛擬

5、存儲器的基本思想是把作業(yè)地址空間和主存空間視為兩個不同的地址空間，前者稱為虛存，后者稱為實存。8虛擬設(shè)備技術(shù)是在一類物理設(shè)備上模擬另一類物理設(shè)備的技術(shù)，它可以將獨占設(shè)備改造為共享設(shè)備。9文件的物理結(jié)構(gòu)密切依賴于文件存儲器的特性和存取方法。10移臂調(diào)度的目標是使磁盤的旋轉(zhuǎn)周數(shù)最小。第3頁二、名詞角釋（每小題詞分，共15分）1操作系統(tǒng)2周轉(zhuǎn)時間3碎片4設(shè)備驅(qū)動程序5事務(wù)三、綜合題（25分）1（6分）設(shè)有兩個進程P1和P2的程序如下，其信號量的初始值S1=S2=0，試求P1，P2并發(fā)執(zhí)行結(jié)束后的x,y,z的值，并對結(jié)果加以解釋。進程1 進程2Y=1; x=1;Y=y+2; x=x+1;Signal(s1; wait(s1;Z=y+1; x=x+y;Wait(S2; signal(S2;Y=y+z; z=z+x;2（4分）簡述產(chǎn)生死鎖的原因和必要條件。3（6分）考慮下面的頁訪問串：1，2，3，4，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6假定有4，5個頁塊，應(yīng)用下面的頁面置換算法，計算會出現(xiàn)多少次缺頁中斷。注意，所給定的頁塊初始均為空，因此，首次訪問一頁時就會發(fā)生缺頁中斷。（1）Opti