2012年山東科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)-真題及參考答案

2012年山東科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)--真題及參考答案數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)Z試卷《數(shù)據(jù)結(jié)構(gòu)》部分（90分）一、簡(jiǎn)答題（20分，每題5分）1、請(qǐng)給出四種數(shù)據(jù)結(jié)構(gòu)基本類(lèi)型。答：根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列4類(lèi)的基本結(jié)構(gòu)：（1）集合。。。（2）線性結(jié)構(gòu)。。。（3）樹(shù)形結(jié)構(gòu)。。。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。。。2、簡(jiǎn)述棧和隊(duì)列的區(qū)別。（P44;P58）區(qū)別和聯(lián)系：從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線性表，不過(guò)是兩種特殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。因而，棧和隊(duì)列也可以被稱(chēng)作為操作受限的線性表。3、什么是關(guān)鍵路徑？(P183)在AOE網(wǎng)中，有些活動(dòng)可以并行地運(yùn)行，最短完成時(shí)間應(yīng)是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度（指路徑上所有權(quán)值之和），稱(chēng)這樣的路徑為關(guān)鍵路徑。4、插入類(lèi)排序有哪幾種？其中，哪些是不穩(wěn)定的排序算法？(P265)二、應(yīng)用題（40分）1、如果進(jìn)棧的序列是12345，請(qǐng)給出所有3、4先出棧的序列（3在4之前出棧）。（5分）(P)【解答】34215，34251，34521(可以參考下面這個(gè)題：【￥】鐵路進(jìn)行列車(chē)調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)，若進(jìn)站的六輛列車(chē)順序?yàn)椋?，2，3，4，5，6，那么是否能夠得到435612，325641，154623和135426的出站序列，如果不能，說(shuō)明為什么不能；如果能，說(shuō)明如何得到(即寫(xiě)出"進(jìn)棧"或"出棧"的序列)?！窘獯稹枯斎胄蛄袨?23456，不能得出435612和154623。不能得到435612的理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能讓棧底元素1在棧頂元素2之前出棧。不能得到154623的理由類(lèi)似，當(dāng)棧中元素只剩23，且3在棧頂，2不可能先于3出棧。得到325641的過(guò)程如下：123順序入棧，32出棧，得到部分輸出序列32；然后45入棧，5出棧，部分輸出序列變?yōu)?25；接著6入棧并退棧，部分輸出序列變?yōu)?256；最后41退棧，得最終結(jié)果325641。得到135426的過(guò)程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。)2、給出先綴表達(dá)式“-+a*b–cd/ef”對(duì)應(yīng)的后綴式，畫(huà)出其相應(yīng)的二叉樹(shù)，并畫(huà)出該二叉樹(shù)的中序線索樹(shù)。（10分）（P129）3、某帶權(quán)有向圖及它的鄰接表如下圖所示，試寫(xiě)出它的廣度優(yōu)先搜索序列，并根據(jù)克魯斯卡爾算法，求它的最小生成樹(shù)。（10分）廣度優(yōu)先搜索序列:(P167)A-->B-->C-->D-->E-->F-->G-->H克魯斯卡爾算法，求最小生成樹(shù):(P173)4、請(qǐng)寫(xiě)出應(yīng)填入下列敘述中（）內(nèi)的正確答案。排序有各種方法，如插入排序、快速排序、堆排序、冒泡排序等。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組由不同排序方法進(jìn)行一遍排序后的結(jié)果。（15分）(必須對(duì)算法的具體步驟有詳細(xì)的了解，認(rèn)真看看書(shū)吧P263)（①）排序的結(jié)果為：12，13，15，18，20，60（②）排序的結(jié)果為：13，15，18，12，20，60（③）排序的結(jié)果為：13，15，20，18，12，60【參考答案】①快速排序②冒泡排序③直接插入排序三、算法設(shè)計(jì)題（30分）答題要求：①用自然語(yǔ)言說(shuō)明所采用算法的思想；②給出每個(gè)算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必要說(shuō)明；③用C語(yǔ)言寫(xiě)出對(duì)應(yīng)的算法程序，并做必要的注釋。1、已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：prior,data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，prior也為指針域，但它的值為空（NULL），試編寫(xiě)算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使prior成為指向前驅(qū)結(jié)點(diǎn)的指針域。（15分）2、編寫(xiě)算法，在二叉樹(shù)中求位于中序序列中第k個(gè)位置的結(jié)點(diǎn)的值。（15分）(P129)分析：實(shí)際上是在考察中序遍歷，然后在中序遍歷中加上一個(gè)count變量，用來(lái)計(jì)數(shù)以確定是第幾個(gè)位置。（一下代碼參見(jiàn)P131）TElemTypeInOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){InitStack(S);p=T;Count=0;While(p||!StackEmpty(S)){If(p){Push(S,p);p=p->lchild;}Else{Pop(S,p);If(!visit(p->data))Returnerror;//出棧一個(gè)數(shù)，統(tǒng)計(jì)count加1；Count++;If(Count>=k){//當(dāng)統(tǒng)計(jì)個(gè)數(shù)到了k個(gè)時(shí)，返回所對(duì)應(yīng)的數(shù)。Returnp->data;}p=p->rchild;}}}《操作系統(tǒng)》部分（60分）四、簡(jiǎn)答題（每小題6分，共30分）1、什么是操作系統(tǒng)？操作系統(tǒng)的主要功能有哪些？操作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟件，是對(duì)硬件系統(tǒng)的首次擴(kuò)充。主要功能:處理機(jī)的管理、存儲(chǔ)器的管理、設(shè)備的管理、文件的管理、接口的管理（參考題目：什么是操作系統(tǒng)？它有什么基本特征？答：操作系統(tǒng)是為了達(dá)到方便用戶(hù)和提高資源利用率的目的而設(shè)計(jì)的，控制和管理計(jì)算機(jī)硬件和軟件資源，合理的組織計(jì)算機(jī)工作流程的程序的集合，它具有并發(fā)、共享、虛擬、異步性四個(gè)基本特征。）2、何謂進(jìn)程？進(jìn)程控制塊的作用和包含的信息是什么？（P41）進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位；進(jìn)程控制塊的作用：使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序（含數(shù)據(jù)），成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。包含的信息：進(jìn)程標(biāo)識(shí)符，處理機(jī)狀態(tài)，進(jìn)程調(diào)度信息，進(jìn)程控制信息3、產(chǎn)生死鎖的必要條件是什么？處理死鎖的基本方法有哪些？必要條件：(1）互斥條件（2）請(qǐng)求和保持條件（3）不剝奪條件（4）環(huán)路等待條件基本方法:（1）預(yù)防死鎖（2）避免死鎖（3）檢測(cè)死鎖（4）解除死鎖4、何謂虛擬存儲(chǔ)器？它有哪些特征？（P143）虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)器系統(tǒng)。具體的說(shuō)，是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器的基本特征是：(P144)多次性，對(duì)換性，虛擬性。（補(bǔ)充：①離散分配，即不必占用連續(xù)的內(nèi)存空間；②部分裝入，即每個(gè)作業(yè)不是全部一次性地裝入內(nèi)存，而是只裝入一部分；③多次對(duì)換，即所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存④虛擬擴(kuò)充，即不是物理上而是邏輯上擴(kuò)充了內(nèi)存容量；另外：虛擬存儲(chǔ)器的容量主要受到指令中表示地址的字長(zhǎng)和外存的容量的限制。）5、Spooling系統(tǒng)由幾部分組成？它有哪些特征？（P190）答：Spooling系統(tǒng)由輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進(jìn)程和輸出進(jìn)程共3部分組成。Spooling系統(tǒng)的特點(diǎn)有：(P191)（1）提高了I/O速度。I/O操作時(shí)針對(duì)輸入井和輸出井，避免了操作低速I(mǎi)/O設(shè)備的速度不匹配。（2）將獨(dú)占設(shè)備改造為共享設(shè)備。Spooling系統(tǒng)沒(méi)有為任何進(jìn)程實(shí)際分配設(shè)備，只是在輸入井或輸出井中為進(jìn)程分配一個(gè)存儲(chǔ)區(qū)和建立一張I/O請(qǐng)求表。（3）實(shí)現(xiàn)了虛擬設(shè)備功能。宏觀上有多個(gè)進(jìn)程在同時(shí)使用一臺(tái)獨(dú)占設(shè)備，但對(duì)于每一個(gè)進(jìn)程而言，他們認(rèn)為自己獨(dú)占了一個(gè)設(shè)備。五、算法和計(jì)算題（每小題10分，共30分）1.使用P、V操作描述讀者-寫(xiě)者問(wèn)題。要求允許幾個(gè)閱讀者可以同時(shí)讀該數(shù)據(jù)集，而一個(gè)寫(xiě)著不能與其他進(jìn)程（不管是寫(xiě)者還是讀者）同時(shí)訪問(wèn)該數(shù)據(jù)集。（P63）答：【分析】讀者-寫(xiě)者問(wèn)題是經(jīng)常出現(xiàn)的一種同步問(wèn)題。計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)（文件、記錄）常被多個(gè)進(jìn)程共享，但其中某些進(jìn)程可能只要求讀數(shù)據(jù)（稱(chēng)為Reader），另一些進(jìn)程則要求修改數(shù)據(jù)（稱(chēng)為Writer）。就共享數(shù)據(jù)而言，Reader和Writer是兩種不同類(lèi)型的進(jìn)程。一般地，兩個(gè)或兩個(gè)以上的Reader進(jìn)程同時(shí)訪問(wèn)共享數(shù)據(jù)時(shí)不會(huì)產(chǎn)生副作用，但若某個(gè)Writer和其他進(jìn)程（Reader或Writer）同時(shí)訪問(wèn)共享數(shù)據(jù)時(shí)，則可能產(chǎn)生錯(cuò)誤。為了避免錯(cuò)誤，同時(shí)盡可能地讓讀者進(jìn)程和寫(xiě)者進(jìn)程并發(fā)運(yùn)行，只要保證任何一個(gè)寫(xiě)者進(jìn)程能與其他進(jìn)程互斥訪問(wèn)共享數(shù)據(jù)即可。這個(gè)問(wèn)題稱(chēng)為讀者-寫(xiě)者問(wèn)題?！窘獯稹縋、V操作是定義在信號(hào)量s上的兩條原語(yǔ)，它是解決進(jìn)程同步與互斥的有效手段。定義下列信號(hào)量：互斥信號(hào)量rmutex，初值為1，用于使讀者互斥地訪問(wèn)讀者計(jì)數(shù)器，共享變量rcount；互斥信號(hào)量wmutex，初值為1，用于實(shí)現(xiàn)寫(xiě)者之間以及寫(xiě)者與讀者之間互斥地訪問(wèn)共享數(shù)據(jù)集。用信號(hào)量和P、V操作描述讀者-寫(xiě)者問(wèn)題如下：Beginrmutexwmutex:semaphore;rcount:Integer;rmutex=wmutex=1;rcount=0;CobeginProcessprocedureReaderbeginP(rmutex);//保護(hù)rcountrcount:=rcount+1ifrcount=lthenP(wmutex);//保證沒(méi)有writer在寫(xiě)V(rmutex);Performreadoperations;P(rmutex);rcount:=rcount-1;ifrcount=OthenV(wmutex);//沒(méi)有reader時(shí)，允許writer寫(xiě)操作V(rmutex);endProcessprocedureWriterbeginP(wmutex);performwriteoperations;V(wmutex);endCoendEnd2.假定在某移動(dòng)臂磁盤(pán)上，剛剛訪問(wèn)了75號(hào)柱面的請(qǐng)求，目前正在80號(hào)柱面讀信息，并且有下述請(qǐng)求序列等待訪問(wèn)磁盤(pán)：試用：（1）電梯調(diào)度算法；（2）最短尋找時(shí)間優(yōu)先算法，分別列出實(shí)際處理上述請(qǐng)求的次序。（1）36412587(2)12587364(參考題目及解析：假定在某移動(dòng)臂磁盤(pán)上，剛剛處理了訪問(wèn)75號(hào)柱面的請(qǐng)求，目前正在80號(hào)柱面上讀信息，并有下列請(qǐng)求序列等待訪問(wèn)磁盤(pán)：請(qǐng)求序列：l2345678欲訪問(wèn)的柱面號(hào)：16040190188905832102試用(1)電梯調(diào)度算法；(2)最短查找時(shí)間優(yōu)先算法，分別排出實(shí)際處理上述請(qǐng)求的次序。答：(1)電梯調(diào)度算法是從移動(dòng)臂當(dāng)前位置開(kāi)始，沿臂的移動(dòng)方向取選擇離當(dāng)前移動(dòng)臂最近的柱面訪問(wèn)，如果該方向上沒(méi)有訪問(wèn)請(qǐng)求，則改變臂的方向再選擇。從題中可以看出，先訪問(wèn)的是75柱面，正在訪問(wèn)80柱面。顯然移動(dòng)臂當(dāng)前的移動(dòng)方向是從小柱面號(hào)到大柱面號(hào)。所以采用電梯調(diào)度算法，先依次訪問(wèn)的應(yīng)該是90、102、160、188、190號(hào)柱面，之后掉轉(zhuǎn)方向去依次訪問(wèn)58、40、32號(hào)柱面。(2)最短查找時(shí)間優(yōu)先算法每次總是讓查找時(shí)間最短的請(qǐng)求先執(zhí)行，不管它是不是先訪問(wèn)的，也不管它在什么方向上。所謂查找時(shí)間最短的是指移動(dòng)臂從當(dāng)前位置移動(dòng)要訪問(wèn)的若干個(gè)位置中移動(dòng)距離最短的位置上所花的時(shí)間。針對(duì)本題，依次先處理的是90、102號(hào)柱面后，磁頭當(dāng)前離58號(hào)柱面有44個(gè)柱面的距離，而離160號(hào)柱面有58個(gè)柱面的距離，顯然要先訪問(wèn)58號(hào)柱面，依次下去訪問(wèn)的應(yīng)該是40、32、160、188、190號(hào)柱面。(1)用電梯調(diào)度算法處理次序是5、8、1、4、3、6、2、7。(2)用最短查找時(shí)間優(yōu)先算法處理的次序5、8、6、2、7、l、4、3。)3.在一個(gè)單道批處理系統(tǒng)中，一組作業(yè)的提交時(shí)刻和