1、數據結構第七次作業選擇題1堆排序的時間復雜度是（D）。A）O(1)B）O(n)C）O(n2)D）O(nlogn)2. 若一個具有N個頂點，K條邊的無向圖是一個森林（NK），則該森林中必有（C）棵樹。A）KB）NC）N-KD）13每一趟都能選出一個元素放在其最終位置上，并且不穩定的排序算法是（B）。A）冒泡排序B）簡單選擇排序 C）希爾排序 D）直接插入排序4快速排序執行一遍之后，已經到位的元素個數是（A）。A）1B）3C）n/4D）n/25數據表中有10000個元素，如果僅需求出其中最大的10個元素，則采用（C）排序算法最節省時間。A）快速排序B）希爾排序C）堆排序D）直接選擇排序1如果一棵樹

2、有n1個度為1的結點, 有n2個度為2的結點, , nm個度為m的結點, 試問有多少個度為0的結點? 試推導之。（8）綜合題2請畫出右圖所示的樹所對應的二叉樹。（8）3. 判別序列（12，70，33，65，24，56，48，92，86，33）是否為堆，如果不是，則將它調整為大根堆。4給出一組關鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結束時的序列。（1）希爾排序（第一趟排序的增量為6）（2）快速排序（選第一個記錄為樞軸）答案：因為堆為完全二叉樹，因此只需要判斷是不是所有節點，都大于或小于子節點，即節點n需要大于或小于2n節點和2n+

3、1節點；序列不是堆如調整為大根堆為：(92，86，56，70，33，33，48，65，12，24)若調整為小根堆為：(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. 利用比較的方法進行排序，在最壞情況下，能達到的最好的時間復雜度是什么？答案：假定待排序的記錄有n個。由于含n個記錄的序列可能出現的狀態有n!個，則描述n個記錄排序過程的判定樹必須有n!個葉子結點。若二叉樹高度是h，則葉子結點個數最多為2h-1；反之，若有u個葉子結點，則二

4、叉樹的高度至少為log2u+1。這就是說，描述n個記錄排序的判定樹必定存在一條長度為log2n!+1的路徑。即任何一個籍助比較進行排序的算法，在最壞情況下所需進行的比較次數至少是log2(n!)。根據斯特林公式，有log2(n!) =O(nlog2n)。即籍助于“比較”進行排序的算法在最壞情況下能達到的最好時間復雜度為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）翻譯：對下列用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 編寫一個處理整數關鍵碼的插入排序。條件如下：輸入的是一個棧（不是數組），并且程序中只允許使用一定的整數以及棧。結束時排序結果放在棧中，棧頂元素最小，在最差的情況下，算法的執行時間是(n2) 。初始序列為：(18,12,56,9,55,8) 插入排序基本思想是將第一

7、個數據元素看成一個有序子序列，再依次從第二個記錄起逐個插入到這個有序子序列中。 855 956121818第一個元素181256 955 8Temp1ININ181256 955 8Temp11218IN56 955 8Temp11812IN 955 8Temp1121856Temp2E=18E=12E=56ININ55 8Temp1 9121856IN 955 8Temp1121856Temp2Temp2IN 8Temp155561812 9Temp2IN Temp1 8 912185556E=19E=55E=8最終結果7.3 冒泡排序的實現過程中有如下循環：for(int j=n-1;ji;j-)；考慮將它換成以下語句的影響for(int j=n-1;j0;j-)；請問新的實現方式還能正常執行嗎？這種改變會影響到程序的漸近復雜度嗎？