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