燕山大學(xué)操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)歷年考研真題答案附后

1、燕山大學(xué)操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)歷年考研真題答案附后最新資料， WORD 格式，可編輯修改！目錄說明： 精選了 16 套名校操作系統(tǒng)歷年考研真題1燕山大學(xué)操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)歷年考研真題2015 年燕山大學(xué)810 操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)考研真題2014 年燕山大學(xué)811 操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)考研真題2013 年燕山大學(xué)810 操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)考研真題2012 年燕山大學(xué)810 操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)考研真題2中國計(jì)量學(xué)院數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)歷年考研真題2015 年中國計(jì)量學(xué)院806 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題2014 年中國計(jì)量學(xué)院818 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題2013 年中國計(jì)量學(xué)院818 數(shù)據(jù)結(jié)構(gòu)與操作

2、系統(tǒng)考研真題3廣東工業(yè)大學(xué)操作系統(tǒng)歷年考研真題2014 年廣東工業(yè)大學(xué)830 操作系統(tǒng)考研真題2013 年廣東工業(yè)大學(xué)830 操作系統(tǒng)考研真題4沈陽航空航天大學(xué)操作系統(tǒng)歷年考研真題2014 年沈陽航空航天大學(xué)811 操作系統(tǒng)考研真題2013 年沈陽航空航天大學(xué)811 操作系統(tǒng)考研真題5沈陽工業(yè)大學(xué)計(jì)算機(jī)操作系統(tǒng)歷年考研真題2014 年沈陽工業(yè)大學(xué)837 計(jì)算機(jī)操作系統(tǒng)考研真題6山東科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)歷年考研真題2014 年山東科技大學(xué)830 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題2012 年山東科技大學(xué)838 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題數(shù)據(jù)結(jié)構(gòu)部分一、簡答題（ 15 分，每題 5 分）1什么是原地

3、工作？2什么是完全二叉樹？3什么是穩(wěn)定的排序方法？二、應(yīng)用題（ 45 分）1設(shè)有一個順序棧S，元素 s1, s2, s3, s4, s5, s6依次進(jìn)棧，如果 6 個元素的出棧順序?yàn)閟2, s3, s4, s6, s5, s1，則順序棧的容量至少應(yīng)為多少？畫出具體進(jìn)棧、出棧過程。（10 分）2給定一棵二叉樹如右圖所示（ 1）寫出該樹的前序、中序、后序遍歷結(jié)果；（ 2）畫出該二叉樹的中序線索樹；（ 3）將它轉(zhuǎn)換成等價的樹或森林。（ 15 分）3已知一個無向圖如下圖所示，要求用Kruskal算法生成最小樹，試畫出構(gòu)造過程。（10 分）4某整形數(shù)組 A 的數(shù)組元素分別是6，2，9，7，3，8，4，5

4、，0，試用下例各排序方法將A 中元素由小到大排序。（10 分）(1) 用第一元素中的值 6 作為樞軸，試寫出快速排序第一次分割后 A 中的結(jié)果。(2)A 中的元素是否為堆，如果不是，請將其調(diào)整為堆，寫出將 A 調(diào)整成堆后 A 中的結(jié)果。三、算法設(shè)計(jì)題（30 分 )答題要求：用自然語言說明所采用算法的思想；給出每個算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必要說明；用 C 語言寫出對應(yīng)的算法程序，并做必要的注釋。1將 n(n>1) 個整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個盡可能高效（時間、空間）的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即將 R 中的數(shù)據(jù)（ x0, x1, x2, x

5、n-1），變換為 (xp ， xp 1, , xn-1 ,x0 , x1, xp-1)。(15 分)2給出折半查找的遞歸算法，并給出算法時間復(fù)雜度性分析。（ 15 分）操作系統(tǒng)部分一、簡單題（每小題5 分，共 30 分）1操作系統(tǒng)設(shè)計(jì)的最重要的兩個目標(biāo)是什么？并簡述原因。2進(jìn)程有哪五種基本狀態(tài)？發(fā)生狀態(tài)間轉(zhuǎn)移的原因是什么？3在請求分頁機(jī)制中會發(fā)生缺頁中斷。請概述缺頁中斷的處理流程。4I/O控制方式有哪幾種實(shí)現(xiàn)方式？并比較這幾種I/O控制方式的優(yōu)缺點(diǎn)。5索引分配是外存管理中常用的分配方式。請問，索引分配有哪三種常見的方式？這些方式的優(yōu)點(diǎn)和缺點(diǎn)是什么？6產(chǎn)生死鎖的四個必要條件是什么？預(yù)防死鎖有幾種

6、實(shí)現(xiàn)方法？二、算法和計(jì)算題（共30 分）1桌子上有一只盤子，每次只能放一個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等著吃盤子中的橘子，一個女兒專等著吃盤子中的蘋果。父、母的動作可以分解為：準(zhǔn)備水果；放水果兩步；兒女的動作可以分解為：拿水果，吃水果兩步。把父、母、兒、女看作是4 個進(jìn)程，請用wait, signal操作寫出他們之間的同步機(jī)制。（注意：對于用到的各個信號量需要說明初值） （ 12 分）2在請求頁式系統(tǒng)中，一程序的頁面走向（訪問串或引用串）為 2，3，4，5，2，3，6，2，3，4，5，6, 設(shè)分配給該程序的存儲塊數(shù)為 m。試分別計(jì)算 m=3和 m=4時，F(xiàn)IFO 和 LRU兩種替換算法的缺頁（頁故障）數(shù)。結(jié)果說明了什么？。（10 分）3在 64