第9章排序
一、填空題（每空1分，共24分）
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. 在堆排序、快速排序和歸併排序中，
若只從儲存空間考慮，則應首先選取方法，其次選取方法，最後選取方法；
若只從排序結果的穩定性考慮，則應選取方法；
若只從平均情況下最快考慮，則應選取方法；
若只從最壞情況下最快並且要節省記憶體考慮，則應選取方法。
二、單項選擇題（每小題1分，共18分）
1．將5個不同的資料進行排序，至多需要比較次。
ａ. 8 ｂ. 9 ｃ. 10 ｄ. 25
2． 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為
ａ. 希爾排序 ｂ. 氣泡排序ｃ. 插入排序 ｄ. 選擇排序
3．從未排序序列中挑選元素，並將其依次插入已排序序列（初始時為空）的一端的方法，稱為
ａ. 希爾排序ｂ. 歸併排序 ｃ. 插入排序ｄ. 選擇排序
4．對ｎ個不同的排序碼進行氣泡排序，在下列哪種情況下比較的次數最多。
ａ. 從小到大排列好的 ｂ. 從大到小排列好的
ｃ. 元素無序 ｄ. 元素基本有序
5．對ｎ個不同的排序碼進行氣泡排序，在元素無序的情況下比較的次數為
ａ. n+1 ｂ. n ｃ. n-1 ｄ. n(n-1)/2
6．快速排序在下列哪種情況下最易發揮其長處。
ａ. 被排序的資料中含有多個相同排序碼
ｂ. 被排序的資料已基本有序
ｃ. 被排序的資料完全無序
ｄ. 被排序的資料中的最大值和最小值相差懸殊
7． 對有n個記錄的表作快速排序，在最壞情況下，演算法的時間複雜度是
a．o(n) b．o(n2) c．o(nlog2n) d．o(n3)
8．若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第乙個記錄為基準得到的一次劃分結果為
ａ. 38, 40, 46, 56, 79, 84
ｂ. 40, 38, 46 , 79, 56, 84
ｃ. 40, 38，46, 56, 79, 84
ｄ. 40, 38, 46, 84, 56, 79
9．下列關鍵字序列中， 是堆。
ａ. 16, 72, 31, 23, 94, 53
ｂ. 94, 23, 31, 72, 16, 53
ｃ. 16, 53, 23, 94，31, 72
ｄ. 16, 23, 53, 31, 94, 72
10．堆是一種排序。
ａ. 插入 ｂ.選擇 ｃ. 交換 ｄ. 歸併
11．堆的形狀是一棵
ａ. 二叉排序樹 ｂ.滿二叉樹
ｃ. 完全二叉樹ｄ. 平衡二叉樹
12．若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為
ａ. 79, 46, 56, 38, 40, 84 ｂ. 84, 79, 56, 38, 40, 46
ｃ. 84, 79, 56, 46, 40, 38 ｄ. 84, 56, 79, 40, 46, 38
17． 下述幾種排序方法中，要求記憶體最大的是
ａ. 插入排序 ｂ.快速排序
ｃ. 歸併排序選擇排序
資料結構 C第3章自測卷
第3章棧和佇列自測卷 一 填空題 1.向量 線性表 棧和佇列都是結構，可以在向量的位置插入和刪除元素 對於棧只能在插入和刪除元素 對於佇列只能在插入和刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為不允許插入和刪除運算的一端稱為 3.是被限定為只能在表的一端進行插入運算，在表的另一端...
資料結構 C語言 第3章棧和佇列自測卷
第3章棧和佇列自測卷 一 填空題 1.向量 線性表 棧和佇列都是線性結構，可以在向量的任意位置插入和刪除元素 對於棧只能在棧頂插入和刪除元素 對於佇列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 不允許插入和刪除運算的一端稱為棧底 3.佇列是被限定為只能在...
資料結構第9章 排序
第9章排序 一 複習要點 排序是使用最頻繁的一類演算法。排序分內排序與外排序。內排序演算法主要分5大類，有12個演算法。在插入排序類中討論了直接插入排序 二分法插入排序 表插入排序和shell排序演算法 在交換排序類中討論了起泡排序和快速排序演算法 在選擇排序類中討論了簡單選擇排序 錦標賽排序和堆排...