數(shù)據(jù)結(jié)構(gòu)作業(yè)7

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條邊的無(wú)向圖是一個(gè)森林（NK），則該森林中必有（C）棵樹(shù)。A）KB）NC）N-KD）13每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是（B）。A）冒泡排序B）簡(jiǎn)單選擇排序 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如果一棵樹(shù)

2、有n1個(gè)度為1的結(jié)點(diǎn), 有n2個(gè)度為2的結(jié)點(diǎn), , nm個(gè)度為m的結(jié)點(diǎn), 試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)? 試推導(dǎo)之。（8）綜合題2請(qǐng)畫(huà)出右圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù)。（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)。寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（1）希爾排序（第一趟排序的增量為6）（2）快速排序（選第一個(gè)記錄為樞軸）答案：因?yàn)槎褳橥耆鏄?shù)，因此只需要判斷是不是所有節(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è)記錄排序過(guò)程的判定樹(shù)必須有n!個(gè)葉子結(jié)點(diǎn)。若二叉樹(shù)高度是h，則葉子結(jié)點(diǎn)個(gè)數(shù)最多為2h-1；反之，若有u個(gè)葉子結(jié)點(diǎn)，則二

4、叉樹(shù)的高度至少為log2u+1。這就是說(shuō)，描述n個(gè)記錄排序的判定樹(shù)必定存在一條長(zhǎng)度為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編碼方法寫(xiě)出的樹(shù)的順序表示，畫(huà)出樹(shù)的形狀。 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 編寫(xiě)一個(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)過(guò)程中有如下循環(huán)：for(int j=n-1;ji;j-)；考慮將它換成以下語(yǔ)句的影響for(int j=n-1;j0;j-)；請(qǐng)問(wèn)新的實(shí)現(xiàn)方式還能正常執(zhí)行嗎？這種改變會(huì)影響到程序的漸近復(fù)雜度嗎？