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

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

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

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

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

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