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

1、《數(shù)據(jù)結(jié)構(gòu)》部分一、簡答題（30分，每題5分）1、串、數(shù)組、廣義表從元素間關(guān)系上可以看成線性結(jié)構(gòu)，它們與一般意義上的線性表相比有何特殊性？2、借助棧可以實現(xiàn)更復雜的操作，請簡述如何利用棧實現(xiàn)對表達式中括號是否匹配的檢驗。3、基于關(guān)鍵字比較的查找算法所能達到最優(yōu)時間復雜度是？能否設(shè)計一種與問題規(guī)模無關(guān)的查找算法？請給出基本思路。4、圖的廣度優(yōu)先遍歷與樹的何種遍歷策略相似？請給出簡單解釋。5、《數(shù)據(jù)結(jié)構(gòu)》中經(jīng)常采用“樹形化組織”的方式來整理

2、數(shù)據(jù)，比如折半查找表、二叉排序樹、大頂堆小頂堆等，請簡述這樣做的優(yōu)點。6、何為穩(wěn)定的排序方法？何為不穩(wěn)定的排序方法？哪些排序算法是不穩(wěn)定的？二、綜合應(yīng)用題（40分，每題10分）1、假設(shè)用于通信的電文共有8個字母ABCDEFGH組成，字母在電文中出現(xiàn)的頻率分別是0.2，0.04，0.06，0.02，0.12，0.24，0.25，0.07。①試為這8個字符設(shè)計哈夫曼編碼；②試設(shè)計另一種由二進制表示的等長編碼方案；節(jié)點所在的層數(shù)。操作系統(tǒng)部分

3、四、基礎(chǔ)題（每小題5分，共30分）1、單處理器操作系統(tǒng)的多個進程無法實現(xiàn)并行操作，如果要提高處理器利用率，主要采用什么技術(shù)？并對這一技術(shù)進行說明。2、某操作系統(tǒng)的一個進程從移動存儲設(shè)備讀入一個文件到內(nèi)存中，該操作系統(tǒng)所在的計算機系統(tǒng)采用DMA控制器實現(xiàn)字節(jié)傳輸。請簡述DMA傳輸文件到內(nèi)存的主要過程。3、操作系統(tǒng)中采用虛擬機結(jié)構(gòu)的主要優(yōu)點是什么？舉出一種常用的虛擬機規(guī)范，并簡要說明其工作過程。4、進程死鎖發(fā)生的必要條件是什么？對每個條件進

4、行說明。5、操作系統(tǒng)的目錄結(jié)構(gòu)的主要作用是什么？目錄中主要包含哪些信息？6、列舉三種主要的操作系統(tǒng)類型，并簡要說明每種類型的特點。五、應(yīng)用題（共30分）1、在虛擬存儲管理中，操作系統(tǒng)需要為多個進程分配一定數(shù)量的物理內(nèi)存塊（幀），分配方法有很多種，例如固定分配、優(yōu)先級分配等，但如果分配方法不當，容易引起頁面在內(nèi)外存之間頻繁的換入換出，使得系統(tǒng)性能（主要是處理器利用率）下降。為減少這一問題出現(xiàn)的可能性，除了經(jīng)常采用的工作集機制以外，還可以通