




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)第七次作業(yè)選擇題1堆排序的時(shí)間復(fù)雜度是(D)。A)O(1)B)O(n)C)O(n2)D)O(nlogn)2. 若一個(gè)具有N個(gè)頂點(diǎn),K條邊的無向圖是一個(gè)森林(NK),則該森林中必有(C)棵樹。A)KB)NC)N-KD)13每一趟都能選出一個(gè)元素放在其最終位置上,并且不穩(wěn)定的排序算法是(B)。A)冒泡排序B)簡單選擇排序 C)希爾排序 D)直接插入排序4快速排序執(zhí)行一遍之后,已經(jīng)到位的元素個(gè)數(shù)是(A)。A)1B)3C)n/4D)n/25數(shù)據(jù)表中有10000個(gè)元素,如果僅需求出其中最大的10個(gè)元素,則采用(C)排序算法最節(jié)省時(shí)間。A)快速排序B)希爾排序C)堆排序D)直接選擇排序1如果一棵樹
2、有n1個(gè)度為1的結(jié)點(diǎn), 有n2個(gè)度為2的結(jié)點(diǎn), , nm個(gè)度為m的結(jié)點(diǎn), 試問有多少個(gè)度為0的結(jié)點(diǎn)? 試推導(dǎo)之。(8)綜合題2請(qǐng)畫出右圖所示的樹所對(duì)應(yīng)的二叉樹。(8)3. 判別序列(12,70,33,65,24,56,48,92,86,33)是否為堆,如果不是,則將它調(diào)整為大根堆。4給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。(1)希爾排序(第一趟排序的增量為6)(2)快速排序(選第一個(gè)記錄為樞軸)答案:因?yàn)槎褳橥耆鏄洌虼酥恍枰袛嗍遣皇撬泄?jié)點(diǎn),都大于或小于子節(jié)點(diǎn),即節(jié)點(diǎn)n需要大于或小于2n節(jié)點(diǎn)和2n+
3、1節(jié)點(diǎn);序列不是堆如調(diào)整為大根堆為:(92,86,56,70,33,33,48,65,12,24)若調(diào)整為小根堆為:(12,24,33,65,33,56,48,92,86,70) 答案:(1) (4,2,16,6,8,28,12,10,20,30,18)(2) (6,2,10,4,8,12,28,30,20,16,18)5. 利用比較的方法進(jìn)行排序,在最壞情況下,能達(dá)到的最好的時(shí)間復(fù)雜度是什么?答案:假定待排序的記錄有n個(gè)。由于含n個(gè)記錄的序列可能出現(xiàn)的狀態(tài)有n!個(gè),則描述n個(gè)記錄排序過程的判定樹必須有n!個(gè)葉子結(jié)點(diǎn)。若二叉樹高度是h,則葉子結(jié)點(diǎn)個(gè)數(shù)最多為2h-1;反之,若有u個(gè)葉子結(jié)點(diǎn),則二
4、叉樹的高度至少為log2u+1。這就是說,描述n個(gè)記錄排序的判定樹必定存在一條長度為log2n!+1的路徑。即任何一個(gè)籍助比較進(jìn)行排序的算法,在最壞情況下所需進(jìn)行的比較次數(shù)至少是log2(n!)。根據(jù)斯特林公式,有l(wèi)og2(n!) =O(nlog2n)。即籍助于“比較”進(jìn)行排序的算法在最壞情況下能達(dá)到的最好時(shí)間復(fù)雜度為O(nlog2n)。證畢。 6.19 Draw the general tree represented by the following sequential representation forgeneral trees illustrated by Example 6.8:
5、 XPC)Q)RV)M)(8)翻譯:對(duì)下列用6.8編碼方法寫出的樹的順序表示,畫出樹的形狀。 X | P - | | | C Q R - | | V M void StackSort(Stack& IN) Stack Temp1, Temp2; while (!IN.isEmpty() / Transfer to another stack Temp1.push(IN.pop(); IN.push(Temp1.pop(); / Put back one element while (!Temp1.isEmpty() / Process rest of elems while (IN.t
6、op() Temp1.top() / Find elems place Temp2.push(IN.pop(); IN.push(Temp1.pop(); / Put the element in while (!Temp2.isEmpty() / Put the rest back IN.push(Temp2.pop(); 7.2 編寫一個(gè)處理整數(shù)關(guān)鍵碼的插入排序。條件如下:輸入的是一個(gè)棧(不是數(shù)組),并且程序中只允許使用一定的整數(shù)以及棧。結(jié)束時(shí)排序結(jié)果放在棧中,棧頂元素最小,在最差的情況下,算法的執(zhí)行時(shí)間是(n2) 。初始序列為:(18,12,56,9,55,8) 插入排序基本思想是將第一
7、個(gè)數(shù)據(jù)元素看成一個(gè)有序子序列,再依次從第二個(gè)記錄起逐個(gè)插入到這個(gè)有序子序列中。 855 956121818第一個(gè)元素181256 955 8Temp1ININ181256 955 8Temp11218IN56 955 8Temp11812IN 955 8Temp1121856Temp2E=18E=12E=56ININ55 8Temp1 9121856IN 955 8Temp1121856Temp2Temp2IN 8Temp155561812 9Temp2IN Temp1 8 912185556E=19E=55E=8最終結(jié)果7.3 冒泡排序的實(shí)現(xiàn)過程中有如下循環(huán):for(int j=n-1;ji;j-);考慮將它換成以下語句的影響for(int j=n-1;j0;j-);請(qǐng)問新的實(shí)現(xiàn)方式還能正常執(zhí)行嗎?這種改變會(huì)影響到程序的漸近復(fù)雜度嗎?
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 電視直銷協(xié)議書
- 董事內(nèi)部協(xié)議書
- 電桿質(zhì)保協(xié)議書
- 繼父建房協(xié)議書
- 糞肥還田協(xié)議書
- 線路租用協(xié)議書
- 簽訂戀愛協(xié)議書
- 松江區(qū)婚姻糾紛協(xié)議書
- 暑假生勤工儉學(xué)協(xié)議書
- 父親和兒女簽字協(xié)議書
- 中醫(yī)各家學(xué)說(湖南中醫(yī)藥大學(xué))知到課后答案智慧樹章節(jié)測(cè)試答案2025年春湖南中醫(yī)藥大學(xué)
- 大學(xué)辦學(xué)模式改革創(chuàng)新的策略及實(shí)施方案
- 物業(yè)客服服務(wù)溝通技巧培訓(xùn)課件
- 監(jiān)獄消防安全生產(chǎn)課件
- 電力市場(chǎng)發(fā)展與人才培養(yǎng)戰(zhàn)略規(guī)劃
- 人力資源培訓(xùn):RACI表培訓(xùn)課件
- DBJ33T 1020-2022 建設(shè)工程地質(zhì)鉆探安全技術(shù)規(guī)程
- 高中家長會(huì) 共筑夢(mèng)想,攜手未來課件-高二下學(xué)期期末家長會(huì)
- 人文關(guān)懷在臨床護(hù)理中的應(yīng)用
- 醫(yī)院營養(yǎng)科建設(shè)方案
- 幼兒園伙食費(fèi)管理制度
評(píng)論
0/150
提交評(píng)論