第10章內部排序
一、選擇題
1. 下列排序方法中，穩定的排序方法是（ ）
a. 簡單選擇排序 b. 氣泡排序 c. 希爾排序 d. 快速排序
2. 在下列排序演算法中,哪乙個演算法的時間複雜度與初始排序無關（ ）。
a. 直接插入排序 b. 氣泡排序 c. 快速排序 d. 簡單選擇排序
3. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ ）
a. 希爾排序 b. 氣泡排序 c. 插入排序 d. 選擇排序
4. 從未排序序列中挑選元素，並將其依次插入已排序序列（初始時為空）的一端的方法，稱為（ ）。
a. 希爾排序 b. 歸併排序 c. 插入排序 d. 選擇排序
5. 對ｎ個不同的元素進行氣泡排序，在下列哪種情況下比較的次數最多（ ）。
a. 元素正序 b. 元素逆序 c. 元素無序 d. 元素基本有序
6. 對ｎ個不同的排序碼進行氣泡排序，在元素無序的情況下比較的次數為（ ）。
a. n+1b. nc. n-1d. n(n-1)/2
7. 快速排序在下列哪種情況下最易發揮其長處（ ）。
a. 被排序的資料中含有多個相同排序碼（即主關鍵字） b. 被排序的資料已基本有序
c. 被排序的資料中的最大值和最小值相差懸殊d. 被排序的資料完全無序
8. 對n個記錄的進行快速排序，在最壞情況下，演算法的時間複雜度是（ ）。
a. o(n) b. o(n2) c. o(nlog2n) d. o(n3)
9. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第乙個記錄為基準得到的一次劃分結果為（ ）。
a. 38, 40, 46, 56, 79, 84b. 40, 38, 46 , 79, 56, 84
c. 40, 38，46, 56, 79, 84d. 40, 38, 46, 84, 56, 79
10. 下列關鍵字序列中，（ ）是堆。
a. 16, 72, 31, 23, 94, 53 b. 94, 23, 31, 72, 16, 53
c. 16, 53, 23, 94，31, 72 d. 16, 23, 53, 31, 94, 72
11. 堆是一種（ ）排序。
a. 插入b. 選擇 c. 交換 d. 歸併
12. 堆的形狀是一棵（ ）。
a. 二叉排序樹 b. 滿二叉樹 c. 完全二叉樹 d. 平衡二叉樹
13. 若一組記錄為（46, 79, 56, 38, 40, 84），則利用堆排序建立的初始堆為（ ）。
a. 79, 46, 56, 38, 40, 84 b. 84, 79, 56, 38, 40, 46
c. 84, 79, 56, 46, 40, 38 d. 84, 56, 79, 40, 46, 38
14. 下述幾種排序方法中，要求記憶體最大的是（ ）
a. 插入排序 b.快速排序 c. 歸併排序 d. 選擇排序
二、填空題
1. 大多數排序演算法都有兩個基本的操作： 和 。
2. 在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。
3. 在插入和選擇排序中，若初始資料基本正序，則選用 ；若初始資料基本反序，則選用
4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 ；若初始記錄基本無序，則最好選用 。
5. 對於n個記錄的集合進行氣泡排序，在最壞的情況下所需要的時間是 。若對其進行快速排序，在最壞的情況下所需要的時間是
6. 對於n個記錄的集合進行歸併排序，所需要的平均時間是 ，所需要的附加空間是 。
7． 對於n個記錄的表進行2路歸併排序，整個歸併排序需進行趟（遍）。
8. 設要將序列（q, h, c, y, p, a, m, s, r, d, f, x）中的關鍵碼按字母公升序重新排列，則：
氣泡排序第一趟的排序結果是
初始步長為4的希爾（shell）排序第一趟的排序結果是
二路歸併排序第一趟的排序結果是
快速排序第一趟的排序結果是
堆排序初始建堆的結果是
9. 在堆排序、快速排序和歸併排序這3種排序方法中，若只從儲存空間考慮，則應首先選取方法，其次選取方法，最後選取方法；若只從排序結果的穩定性考慮，則應選取方法；若只考慮最壞情況下最快並且要節省記憶體考慮，則應選取方法。
三、判斷題
1. 內部排序要求待排序資料一定要以順序方式儲存。（ ）
2. 排序演算法中的比較次數與初始元素序列的排列無關。（ ）
3. 快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。（ ）
4. 堆排序是穩定的排序方法。（ ）
5. 歸併排序的輔助儲存為o(1)。（ ）
四、計算題
1. 對關鍵字序列 (12, 23, 56, 30, 78, 28, 37, 10, 42, 65 ) 從小到大排序，請寫出希爾排序的第一趟和第二趟排序結果（d=5，3，1），要求必須寫出過程。
2. 已知待排序序列為，寫出直接插入排序的前3趟排序結果。
資料結構第2章習題
一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n 時，需向前移動個元...
資料結構習題 第1章
第一章概論自測題姓名班級 一 填空題 每空1分，共33分 1.乙個計算機系統包括和兩大部分。2.一台計算機中全部程式的集合，稱為這台計算機的 3.計算機軟體可以分為軟體和軟體兩大類。科學計算程式包屬於診斷程式屬於 4.一種用助憶符號來表示機器指令的操作符和運算元的語言是 5.資料結構是一門研究非數值...
資料結構第1 2章習題
第一章一 選擇題 1.下面屬於邏輯結構的是 c 備註 其他都是儲存結構，包括迴圈佇列 a 順序表 b雜湊表 c 有序表d 單鏈表 2.下面關於演算法說法錯誤的是 d a 演算法最終必須由電腦程式實現 不見得，有些演算法是np完全問題，電腦程式只能實現低數量的值，對於高數量的是實現不了的 b.為解決某...