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

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