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

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

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

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

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