2016年山東科技大學(xué)__831數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)_考研專業(yè)課真題／研究生入學(xué)考試試題

1、數(shù)據(jù)結(jié)構(gòu)部分 一、簡答題（共30 分，每題 5 分） 1、試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的實(shí)例，說明其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次的含義及其相互關(guān)系。 2、簡述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、表頭結(jié)點(diǎn)。 3、在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么 ?4、設(shè)輸入序列為a,b,c,d,試寫出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。 5、什么是遞歸程序？遞歸程序的優(yōu)、缺點(diǎn)是什么？遞歸程序在執(zhí)行時(shí)，應(yīng)借助于何種數(shù)據(jù)結(jié)構(gòu)來完成？ 6、簡要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、 隊(duì)列空、隊(duì)列滿時(shí)的隊(duì)首指針與隊(duì)尾指針的值。二、應(yīng)用題（共40 分，每題 10 分） 1、設(shè)一棵二叉樹的先序、中

2、序遍歷序列分別為： abdfcegh及bfdage，hc完成以下問題： （1） 畫出這棵二叉樹； （2） 畫出這棵二叉樹的后序線索樹；（3） 將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。 2、已知待排序的序列為（ 503，87，512，61，908，170，897，275，653，462），試完成下列各題： （1） 根據(jù)以上序列建立一個(gè)堆，畫出第一步和最后堆的結(jié)果圖，要求先輸出最小值。 （2） 輸出最小值后，如何得到次小值，并畫出相應(yīng)結(jié)果圖。3、設(shè)哈希(hash)表的地址范圍為017，哈希函數(shù)為：h(k)=k mod16,k為關(guān)鍵字，用線性探測再散列法處理沖突，輸入關(guān)鍵字序列(10,24,32,17

3、,31,30,46,47,40,63,49)構(gòu)造哈希表，試回答下列問題：（1） 畫出哈希表示意圖； （2） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字比較?（3） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較?（4） 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。 4、已知一個(gè)圖的頂點(diǎn)集 v=1,2,3,4,5,6,7 ，共有 10 條邊，該1 2 2 5 5 2 2 6 1 36 4 5 4 7 6 7 7 7 51 1 2 2 2 3 3 4 5 7圖用如下邊集數(shù)組存儲(chǔ)： 起點(diǎn)終點(diǎn)權(quán)試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。 三、算法設(shè)計(jì)題（共 20 分，每題

4、 10 分） 1、已知指針 ha和 hb 指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)單鏈表的長度分別為 m和 n，試設(shè)計(jì)一個(gè)算法, 將這個(gè)兩個(gè)鏈表連接在一起，假設(shè)指針 hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。 2、設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為 (lchild, data,rchild)，設(shè)計(jì)一個(gè)算法將二叉樹中所有結(jié)點(diǎn)的左，右子樹相互交換。 操作系統(tǒng)部分 一： 簡答題 （每小題5分，共30分） 1：什么是微內(nèi)核結(jié)構(gòu)？該結(jié)構(gòu)有何優(yōu)點(diǎn)和缺點(diǎn)？ 2：什么是進(jìn)程控制塊？為什么說進(jìn)程控制塊是進(jìn)程生存的唯一標(biāo) 志 ？ 3：請分別說明進(jìn)程和線程的概念，并說明二者的差異。

5、 4：請說明內(nèi)存管理中內(nèi)碎片和外碎片的概念。 5：請說明操作系統(tǒng)中文件系統(tǒng)經(jīng)常使用的分配方式，并簡要說明它們的優(yōu)缺點(diǎn)。 6：操作系統(tǒng)的io 子系統(tǒng)一般需要具備什么功能？ 請列舉至少四個(gè)功能。 二：算法和計(jì)算題（共30分） 1：桌子上有一只盤子，每次只能放一個(gè)水果。爸爸專向盤子中 放蘋果，媽媽專向盤子中放橘子，一個(gè)兒子專等著吃盤子中的橘 子，一個(gè)女兒專等著吃盤子中的蘋果。 父、母的動(dòng)作可以分解為： 準(zhǔn)備水果；放水果兩步；兒女的動(dòng)作可以分解為：拿水果，吃水 果兩步。把父、母、兒、女看作是4 個(gè)進(jìn)程，請用 wait,signal操作寫出他們之間的同步機(jī)制。 （注意：對于用到的各個(gè)信號(hào)量需要說明初值）

6、 （12分） 2：假設(shè)磁盤有200 個(gè)磁道，磁盤請求隊(duì)列中都是隨機(jī)請求，它們按照到達(dá)的次序分別處于55、58、39、18、90、160、150、38、184 號(hào)磁道上，當(dāng)前磁頭在100 號(hào)磁道上，并向磁道號(hào)增加的方向移動(dòng)。請給出按著fcfs、sstf 和 scan算法進(jìn)行磁盤調(diào)度時(shí)的次序，并計(jì)算平均尋道長度。請列出計(jì)算過程。（本題 8 分） 3：某虛擬存儲(chǔ)器的用戶空間共有 32 個(gè)頁面，每頁 1kb，而主存為 16kb。假定某時(shí)刻系統(tǒng)為用戶的第 0、1、2、3 頁分配的物理塊號(hào)為 5、10、4、7，而該用戶作業(yè)的長度為 6 頁。請問：（本題總計(jì) 10 分）（提示：請注意邏輯地址是由哪兩部分組成的） 1) 十六進(jìn)制的邏輯地址（也稱為虛擬地址） 0a5c對應(yīng)的物理地址是