2011年山東科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)-真題及習(xí)題與講解

《數(shù)據(jù)結(jié)構(gòu)》部分一、簡答題（20分，每題5分）1、請給出4類常用的基本數(shù)據(jù)結(jié)構(gòu)類型。（課本p5第6行）答：根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列4類的基本結(jié)構(gòu)：（1）集合。。。（2）線性結(jié)構(gòu)。。。（3）樹形結(jié)構(gòu)。。。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。。。2、什么是哈希表？（課本P253第2行）答：根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法，將一組關(guān)鍵字映射到一個有限的、連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集上的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表。3、請比較簡單排序、快速排序、堆排序、歸并排序的算法效率和穩(wěn)定性。（課本P289）（算法效率的概念P14；穩(wěn)定性的概念P263;簡單排序也就是除希爾排序之外的所有插排入序P265;快速排序P272;堆排序P279;歸并排序P283）答：4、請比較普里姆算法與克魯斯卡爾算法解決圖最小生成樹問題的時間復(fù)雜度。(課本P175)(最小生成樹：P173;普里姆算法P173;克魯斯卡爾算法P175)答：普里姆算法的因此適用于求邊稠密的網(wǎng)的最小生成樹。而克魯斯卡爾算法恰恰相反，它的時間復(fù)雜度為O(eloge)(e為網(wǎng)時間復(fù)雜度為O(n2)（假設(shè)網(wǎng)中有n個頂點），與網(wǎng)中的邊數(shù)無關(guān)，中邊的數(shù)目)，因此它相對于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹。二、應(yīng)用題（50分）1、已知二叉樹的DBFEGAHCIJ，請畫出對（10分）前序遍歷、中序遍歷的結(jié)果分別是：ABDEFGCHIJ和應(yīng)的二叉樹，給出后序遍歷的結(jié)果，并將它轉(zhuǎn)換成等價的樹或森林。（二叉樹的前序遍歷、中序遍歷P128；樹P137；森林P138）答：2、某帶權(quán)有向圖及它的鄰接表如下：(1)試寫出它的答：A-->B-->D-->C-->F-->E-->G--H（提示：不要畫圖，(2)根據(jù)普里姆(Prim)算法，求它的從頂點A出發(fā)的最小生成樹。（10分）（普里姆算法P173;克魯斯卡爾算法P175）深度優(yōu)先搜索序列。(深度優(yōu)先搜索P167；鄰接表P163；廣度優(yōu)先搜素P169)直接根據(jù)鄰接表畫）答：（沒有有向圖，也就沒權(quán)重，沒法做，領(lǐng)會精神）3、畫出向小頂堆中加入數(shù)據(jù)4,2,5,8,3,6,10,1時，每加入一個數(shù)據(jù)后堆的變化。（15分）（堆P280;）4.一組關(guān)鍵字集合為(25，10，8，27，32，68)，設(shè)哈希函數(shù)H(k)=kmod7，分別用線性探測和鏈地址法兩種解決沖突的方法構(gòu)造長度為8的哈希表，要求畫出具體的哈希表并求查找成功且等概率情況下各自的平均查找長度。（15分）(線性探測和鏈地址法兩種解決沖突的方法P257和P258；平均查找長度P260)答：哈希表如下:線性探測平均查找長度：（1*4+2*1+3*1）/6=9/6鏈地址法平均查找長度：（1*5+2*1）/6=7/6三、算法設(shè)計題（30分)答題要求：①用自然語言說明所采用算法的思想；②給出每個算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必要說明；③用C語言寫出對應(yīng)的算法程序，并做必要的注釋。1、已知一個帶表頭結(jié)點的單鏈表，結(jié)點的結(jié)構(gòu)為假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)）。查找成功，輸出結(jié)點的data值，并返回1；否則，只返回0。(15分)（單鏈表P27；單鏈表c語言結(jié)構(gòu)義P28）該鏈表中定【解析】本題詳細解析如下：(1)算法的基本設(shè)計思想：問題的關(guān)鍵是設(shè)計一個盡可能高效的算法，通過鏈表的一趟遍歷，找到倒數(shù)第k個結(jié)點的位置。算法的基本設(shè)計思想是：定義兩個指針變量始時均指向頭結(jié)點的下一個結(jié)點（鏈表的第一個結(jié)點）。p指針沿鏈表移動；當p指針移k個結(jié)點時，q指針開始與p指針同步移動；當p指針移動到最后一個結(jié)點時，q指k個結(jié)點。以上過程對鏈表僅進行一遍掃描。p和q，初動到第針所指示結(jié)點為倒數(shù)第(2)算法的詳細實現(xiàn)步驟：①count=0，p和q指向鏈表表頭結(jié)點的下一個結(jié)點；②若p為空，③若count等于k，則q指向下一個結(jié)點；④p指向下一個結(jié)點，⑤若count等于k，則查找失敗，返回0；轉(zhuǎn)⑤；否則，count=count+1；轉(zhuǎn)②；成功，輸出該結(jié)點的data域的值，返回1；否則，說明k值超過了線性表的長度，查找⑥算法結(jié)束。(3)算法實現(xiàn)：typedefstructNode{ElemTypedata;structNode*next;}*Pointer;PointerLinkList;intSearch_k(Pointer&list,intk)//查找鏈表list倒數(shù)第k個結(jié)點，并輸出該結(jié)點data域的值{p=list->next;q=list->next;//指針p、q指示第一個結(jié)點intcount=0;while(p!=NULL){//遍歷鏈表直到最后一個結(jié)點if(count<k)count++;//計數(shù)，若count<k只移動pelseq=q->next;p=p->next;//后之讓p、q同步移動}//whileif(count<k)return0;//查找失敗返回0else{//否則打印并返回1printf("%d",q->data);return1;}}//Search_k提示：算法程上分數(shù)，如果能用偽代碼寫出自然更好，比較復(fù)雜的地方可以序題，如果能夠?qū)懗鰯?shù)據(jù)結(jié)構(gòu)類型定義、正確的算法思想都會至少給一半以直接用文字表達。2、請給出統(tǒng)計二叉樹中葉子結(jié)點個數(shù)的算法。（15分）（二叉樹P121;二叉樹鏈式存儲結(jié)構(gòu)P127;遍歷算法偽碼P129、P130）算法分析:首先要明白其本質(zhì)還是二叉樹的遍歷.只不過是帶額外有條件的輸出.即找出葉子結(jié)點并進行計數(shù).下面是比較好記的一個算法，簡單，但是一定不要記錯！intleaf(bitreet){if(!t)return0;//空樹，返回0elseif(!t->lch&&!t->rch)return1;elsereturn(leaf(t->lch)+leaf(t->rch));}/************************算法分析:首先要明白其本質(zhì)還是二叉樹的遍歷.只不過是帶額外有條件的輸出.即找出葉子結(jié)點并進行計數(shù).1.提到計數(shù)的話,一開始的反應(yīng)就是建立一個int型變量(如count),然后找到一個符合條件的就進行count++;但在這里就不是那么合適了.因為若是要遍歷,選擇遞歸遍歷,則每次調(diào)用一次遞歸函數(shù)都會創(chuàng)建一個count,各個count都不相同.而且都會被初始化為0,這樣就沒什么意義了.2.所以采取的方法就是利用函數(shù)返回值.把函數(shù)定義為返回值為int型的函數(shù).3.然后進行判斷:if(!t->lch&&!t->rch)如果左右結(jié)點都為NULL,則返回1(也就是計數(shù)+1).則否就調(diào)用遞歸函數(shù),先左子樹,后右子樹.這個算法真正精髓的一句就是:return(leaf(t->lch)+leaf(t->rch));在調(diào)用遞歸的同時把各個遞歸函數(shù)的返回值都加了起來.而最終返回到主函數(shù)的值就是葉子節(jié)點的個數(shù)!巧妙!:D**************************/《操作系統(tǒng)》部分四、簡答題（每小題6分，共30分）1、什么是操作系統(tǒng)？試列舉三種你所熟悉的操作系統(tǒng)名稱及類型？（P1;P13）操作系統(tǒng)是配置在計算機硬件上的第一層軟件，是對硬件系統(tǒng)的首次擴充。MS-DOS:單用戶單任務(wù)操作系統(tǒng)Windows95/98/xp:單用戶多任務(wù)操作系統(tǒng)LinuxOS：多用戶多任務(wù)操作系統(tǒng)2、何謂虛擬？OS中利用的虛擬技術(shù)有哪些？(P16;)操作系統(tǒng)中的所謂虛擬，是指通過某種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。在操作系統(tǒng)中利用了兩種方式實現(xiàn)虛擬技術(shù)，即時分復(fù)用技術(shù)和空分復(fù)用技術(shù)。利用時分復(fù)用技術(shù)實現(xiàn)了：虛擬處理機技術(shù)和虛擬設(shè)備技術(shù)利用空分復(fù)用技術(shù)實現(xiàn)了：虛擬磁盤技術(shù)和虛擬存儲器技術(shù)3、進程死鎖產(chǎn)生的原因是什么？處理死鎖的基本方法有哪些？(P103;P105)進程死鎖產(chǎn)生的原因可歸結(jié)為如下兩點：（1）競爭資源。當系統(tǒng)中供多個進程共享的資源如打印機等，其數(shù)目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產(chǎn)生死鎖。（2）進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，也同樣會導(dǎo)致產(chǎn)生進程死鎖。處理死鎖的基本方法可以歸結(jié)為以下四種：（1）預(yù)防死鎖（2）避免死鎖（3）檢測死鎖（4）解除死鎖4、在具有快表的段頁式存儲管理方式中，如何實現(xiàn)地址變換？（教材習(xí)題（P159--15題）；答案：P137）答：在段頁式系統(tǒng)中，為了便于實現(xiàn)地址變換，須配置一個段表寄存器，其中存放段表始址和段長TL。進行地址變換時，首先利用段號S，將它與段長TL進行比較。若S<TL，表示未越界，利用段表始址和段號來求出該段所對應(yīng)的段表項在段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)頁的頁表項位置，從中讀出該頁所在的物理塊號b，再利用塊號b和頁內(nèi)地址來構(gòu)成物理地址。在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，須三次訪問內(nèi)存。第一次訪問內(nèi)存中的段表，從中取得頁表始址；第二次訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或數(shù)據(jù)。顯然，這使訪問內(nèi)存的次數(shù)增加了近兩倍。為了提高執(zhí)行速度，在地址變換機構(gòu)中增設(shè)一個高速緩沖寄存器。每次訪問它時，都須同時利用段號和頁號去檢索高速緩存，若找到匹配的表項，便可從中得到相應(yīng)頁的物理塊號，用來與頁內(nèi)地址一起形成物理地址；若未找到匹配表項，則仍須再三次訪問內(nèi)存。5、文件控制塊的作用是什么？它通常包括哪三類信息？(P224;)為了能對一個文件進行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，稱之為“文件控制塊”。文件管理程序可借助于文件控制塊中的信息，對文件施以各種操作。施以有效管理，在文件控制塊中，通常應(yīng)含有三類信息，即為了能對系統(tǒng)中的大量文件基本信息、存取控制信息及使用信息。五、算法和計算題（每小題10分，共20分）1、從讀一致。這一工作由三個進程get,copy和put以及兩個緩沖程get的功能是把一張卡片上的信息從讀卡機上讀進buffer1；進程copy的功能是buffer1的信息復(fù)制到buffer2；進程put的功能是取出buffer2中的信息并從行式打印機上打印輸出。量機制完成三個進程間的盡可能并量的作用及初值。（生產(chǎn)者-消費者問題P58;信號量P53）解答：這3個進程間的關(guān)系可用下圖來表示：卡機上讀進N張卡片，然后復(fù)制一份，要求復(fù)制出來的卡片與讀進來的卡片完全區(qū)buffer1和buffer2完成。進把試用信號發(fā)正確運行的關(guān)系（用程序表示），并指明信號分析這3個進程之間的關(guān)系，可以得知，get和copy進程之間通過buffer1進行合作，這是一種生產(chǎn)者-消費者問題；同理，進程copy和put之間通過buffer2進行合作，兩者之間也是一種生產(chǎn)者-消費者問題。為此，設(shè)計互斥信號量mutex1，mutex2來實現(xiàn)對buffer1和buffer2的互斥訪問；為實現(xiàn)get和copy之間的同步，設(shè)置兩個信號量semptybuffer1和sfullbuffer1，分別表示緩沖區(qū)buffer1是空的還是滿的；為實現(xiàn)copy和put之間的同步，設(shè)置兩個信號量semptybuffer2、sfullbuffer2，分別表示緩沖區(qū)buffer2是空的還是滿的。Varmutex1,mutex2,semptybuffer1,sfullbuffer1,semptybuffer2，sfullbuffer2:semaphore:=1,1,1,0,1,0;Get:beginRepeat從讀卡機讀入一張卡片信息；P(semptybuffer1);P(mutex1);將信息放入buffer1;V(sfullbuffer1);V(mutex1);Untilfalse;EndCopy:beginRepeatP(sfullbuffer1);P(mutex1);從buffer1復(fù)制信息;V(semptybuffer1);V(mutex1);P(semptybuffer2);P(mutex2);將信息復(fù)制放入buffer2;V(sfullbuffer2);V(mutex2);Untilfalse;End;Put:beginRepeatP(sfullbuffer2);P(mutex2);從buffer2取出信息;V(semptybuffer2);V(mutex2);把信息從打印機輸出；Untilfalse;End;2、磁盤請求的柱面按10,22,20,2,40,6,38的次序到達磁盤的驅(qū)動器，尋道時每個柱面移動需要6ms。計算按以下算法調(diào)度時的（1）先來先服務(wù)；（2）最短尋道時間優(yōu)先；（3）電梯調(diào)度算法。