2017年山東科技大學(xué)研究生入學(xué)考試823數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題

1、《數(shù)據(jù)結(jié)構(gòu)》部分一、簡(jiǎn)答題（30分，每題5分）1、《數(shù)據(jù)結(jié)構(gòu)》這門課程重點(diǎn)研究“數(shù)據(jù)”還是“結(jié)構(gòu)”？請(qǐng)簡(jiǎn)單解釋你的理由。2、線性表的順序存儲(chǔ)結(jié)構(gòu)叫順序表，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)叫鏈表，請(qǐng)簡(jiǎn)述你對(duì)“順序表順序存儲(chǔ)、隨機(jī)讀?。绘湵黼S機(jī)存儲(chǔ)、順序讀取”這句話的理解。3、數(shù)據(jù)結(jié)構(gòu)中你熟悉的哪些數(shù)據(jù)類型是遞歸定義的？請(qǐng)給出一種遞歸數(shù)據(jù)類型的定義，并做簡(jiǎn)單解釋。4、棧和隊(duì)列與普通線性表相比有何異同？簡(jiǎn)述隊(duì)列順序存儲(chǔ)實(shí)現(xiàn)的技巧。5、基于關(guān)鍵字比較的排序

2、算法所能達(dá)到最優(yōu)時(shí)間復(fù)雜度是？能否設(shè)計(jì)一種不需要關(guān)鍵字間比較的排序算法？請(qǐng)給出基本思路。6、簡(jiǎn)述KMP算法是如何提高字符串的模式匹配效率的。二、綜合應(yīng)用題（40分，每題10分）1、已知二叉樹的中序遍歷序列為DBFEAGCH，后序遍歷序列為DFEBGHCA。①請(qǐng)畫出該二叉樹；②將其先序線索化；③將該二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹或森林。2、已知圖的鄰接矩陣為：1什么是進(jìn)程？一般情況下，進(jìn)程由哪三大部分組成？2在操作系統(tǒng)中，什么是系統(tǒng)抖動(dòng)（顛簸）？從

3、哪些方面可以處理系統(tǒng)抖動(dòng)問題？3緩沖技術(shù)是操作系統(tǒng)中的一種重要技術(shù)，說明緩沖技術(shù)的特點(diǎn)和常用的緩沖類型。4列舉三種磁盤調(diào)度算法，并簡(jiǎn)要說明每種算法的基本思想。5操作系統(tǒng)為文件分配外存空間時(shí)可以采用多種分配方法，簡(jiǎn)述索引分配和鏈接分配方法的思想和特點(diǎn)。6簡(jiǎn)述計(jì)算機(jī)操作系統(tǒng)的主要功能，并對(duì)每項(xiàng)功能進(jìn)行說明。五、應(yīng)用題（共五、應(yīng)用題（共30分）分）1有一個(gè)10頁(yè)的進(jìn)程P，操作系統(tǒng)根據(jù)其內(nèi)存塊（幀）分配策略，為該進(jìn)程分配了5個(gè)物理塊（幀），其頁(yè)

4、表如下所示，頁(yè)的大小為4KB，請(qǐng)計(jì)算邏輯地址為0x17C8和0x6E37的物理地址。（8分）頁(yè)號(hào)頁(yè)號(hào)塊號(hào)裝入內(nèi)存時(shí)刻塊號(hào)裝入內(nèi)存時(shí)刻上次引用（訪問）該頁(yè)面時(shí)刻上次引用（訪問）該頁(yè)面時(shí)刻R(讀)M(修改修改)0710:0511:3310349:3510:2010129:3610:4011599:5510:151181110:0110:50002假設(shè)一個(gè)系統(tǒng)中有3個(gè)進(jìn)程P1，P2，P3，它們的到達(dá)就緒隊(duì)列的時(shí)間和所需的CPU服務(wù)時(shí)間分別如下