第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個不同的資料進行排序，至多需要比較次。
ａ. 891025
（ ）2． 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為
ａ. 希爾排序 ｂ. 氣泡排序插入排序選擇排序
（ ）3．從未排序序列中挑選元素，並將其依次插入已排序序列（初始時為空）的一端的方法，稱為
ａ. 希爾排序 ｂ. 歸併排序插入排序選擇排序
（ ）4．對ｎ個不同的排序碼進行氣泡排序，在下列哪種情況下比較的次數最多。
ａ. 從小到大排列好的 ｂ. 從大到小排列好的 ｃ. 元素無序 ｄ. 元素基本有序
（ ）5．對ｎ個不同的排序碼進行氣泡排序，在元素無序的情況下比較的次數為
ａ. n+1nn-1n(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, 8440, 38, 46 , 79, 56, 84
ｃ. 40, 38，46, 56, 79, 8440, 38, 46, 84, 56, 79
（ ）9． 在最好情況下，下列排序演算法中排序演算法所需比較關鍵字次數最少。
a．冒泡b．歸併c．快速d．直接插入
（ ）10． 置換選擇排序的功能是
a．選出最大的元素 b．產生初始歸併段 c．產生有序檔案 d．置換某個記錄
（ ）11．將5個不同的資料進行排序，至少需要比較次。
ａ. 4567
（ ）12．下列關鍵字序列中， 是堆。
ａ. 16, 72, 31, 23, 94, 5394, 23, 31, 72, 16, 53
ｃ. 16, 53, 23, 94，31, 7216, 23, 53, 31, 94, 72
（ ）13．堆是一種排序。
ａ. 插入選擇交換歸併
（ ）14．堆的形狀是一棵
ａ. 二叉排序樹 ｂ.滿二叉樹完全二叉樹平衡二叉樹
（ ）15．若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為
ａ. 79, 46, 56, 38, 40, 8484, 79, 56, 38, 40, 46
ｃ. 84, 79, 56, 46, 40, 3884, 56, 79, 40, 46, 38
（ ）16． 下述幾種排序方法中，平均查詢長度（asl）最小的是
ａ. 插入排序 ｂ.快速排序歸併排序選擇排序
（ ）17． 下述幾種排序方法中，要求記憶體最大的是
ａ. 插入排序 ｂ.快速排序歸併排序選擇排序
（ ）18．目前以比較為基礎的內部排序方法中，其比較次數與待排序的記錄的初始排列狀態無關的是
ａ. 插入排序 ｂ. 二分插入排序 ｃ. 快速排序氣泡排序
三、簡答題（每小題4分，共36分）
1. 已知序列基本有序，問對此序列最快的排序方法是多少，此時平均複雜度是多少？
2. 設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好採用哪種排序方法？
3. 用某種排序方法對線性表（25, 84，21,47,15,27,68,35,20）進行排序時，元素序列的變化情況如下：
25, 84，21,47,15,27,68,35,20 → 20, 15, 21, 25，47, 27,68,35, 84 → 15, 20, 21, 25，35, 27, 47, 68, 84→
15, 20, 21, 25，27, 35, 47, 68, 84， 問採用的是什麼排序方法？
4. 對於整數序列100，99，98，…3，2，1，如果將它完全倒過來，分別用氣泡排序和快速排序法，它們的比較次數和交換次數各是多少？
5.【嚴題集10.15④】設有n個值不同的元素存於順序結構中，試問能否用比2n-3少的比較次數選出這n個元素中的最大值和最小值？
若能請說明如何實現（不需寫演算法）。在最壞情況下至少需進行多少次比較。
6. 將兩個長度為n的有序表歸併為乙個長度為2n的有序表，最小需要比較n次，最多需要比較2n-1次，請說明這兩種情況發生時，兩個被歸併的表有何特徵?
7. 【嚴題集10.11②】試問：按錦標賽排序的思想，決出8名運動員之間的名次排列，至少需編排多少場次的比賽（應考慮最壞的情況）？
8. 【嚴題集10.19④】假設某大旅店共有5000個床位，每天需要根據住宿旅客的檔案製造乙份花名冊，該名冊要求按省（市）的次序排列，每一省（市）按縣（區）排列，又同一縣（區）的旅客按姓氏排列。
請你為旅店的管理人員設計乙個製作這份花名冊的方法。
9.【嚴題集10.6④】奇偶交換排序如下所述：
第一趟對所有奇數i，將a[i]和a[i+1]進行比較；第二趟對所有的偶數i,將a[i]和a[i+1]進行比較，若a[i]>a[i+1]，則兩者交換；第三趟對奇數i,第四趟對偶數i；……依次類推直至整個序列有序為止。
（1）試問這種排序方法的結束條件是什麼？是否為穩定排序？
（2）分析當初始序列為正序或逆序兩種情況下，奇偶交換排序過程中所需進行的關鍵字比較的次數。
（3）分析此種排序方法的平均複雜度及最壞複雜度。
四、以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執行以下演算法的各趟排序結束時，關鍵字序列的狀態，並說明這些排序方法中，哪些易於在鍊錶（包括各種單、雙、迴圈鍊錶）上實現？
資料結構第三章自測題答案
第3章棧和佇列自測卷答案姓名班級 一 填空題 每空1分，共15分 1.向量 棧和佇列都是線性結構，可以在向量的任何位置插入和刪除元素 對於棧只能在棧頂插入和刪除元素 對於佇列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 不允許插入和刪除運算的一端稱為棧底 ...
資料結構1800題第三章
第3章棧和佇列 一選擇題 1.對於棧運算元據的原則是 青島大學 2001 五 2 2分 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.在作進棧運算時,應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為 為了增加記憶體空間的利用率...
資料結構 C語言 第10章排序自測題
第9章排序 一 填空題 每空1分，共24分 1.大多數排序演算法都有兩個基本的操作 和 2.在對一組記錄 54，38，96，23，15，72，60，45，83 進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。3.在插入和選擇排序中，若初始資料基本正序，則選用 若初始...