《第3章排序答案.doc》由會員分享,可在線閱讀,更多相關(guān)《第3章排序答案.doc(10頁珍藏版)》請在裝配圖網(wǎng)上搜索。
第3章 排序 自測卷 答案 姓名 班級
題號
一
二
三
四
五
總分
題分
24
18
36
8
14
100
得分
一、填空題(每空1分,共24分)
1. 大多數(shù)排序算法都有兩個基本的操作: 比較(兩個關(guān)鍵字的大?。? 和 移動(記錄或改變指向記錄的指針) 。
2. 在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接插入排序時,當(dāng)把第7個記錄60插入到有序表時,為尋找插入位置至少需比較 3 次。(可約定為,從后向前比較)
3. 在插入和選擇排序中,若初始數(shù)據(jù)基本正序,則選用 插入排序(到尾部) ;若初始數(shù)據(jù)基本反序,則選用 選擇排序 。
4. 在堆排序和快速排序中,若初始記錄接近正序或反序,則選用 堆排序 ;若初始記錄基本無序,則最好選用 快速排序 。
5. 對于n個記錄的集合進行冒泡排序,在最壞的情況下所需要的時間是 O(n2) 。若對其進行快速排序,在最壞的情況下所需要的時間是 O(n2) 。
6. 對于n個記錄的集合進行歸并排序,所需要的平均時間是 O(nlog2n) ,所需要的附加空間是 O(n) 。
7.【計研題2000】對于n個記錄的表進行2路歸并排序,整個歸并排序需進行 log2n 趟(遍),共計移
動 n log2n 次記錄。
(即移動到新表中的總次數(shù)!共log2n趟,每趟都要移動n個元素)
8.設(shè)要將序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的關(guān)鍵碼按字母序的升序重新排列,則:
冒泡排序一趟掃描的結(jié)果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ;
初始步長為4的希爾(shell)排序一趟的結(jié)果是 P, A, C, S, Q, D, F, X , R, H,M, Y ;
二路歸并排序一趟掃描的結(jié)果是 H, Q, C, Y,A, P, M, S, D, R, F, X ;
快速排序一趟掃描的結(jié)果是 F, H, C, D, P, A, M, Q, R, S, Y,X ;
堆排序初始建堆的結(jié)果是 A, D, C, R, F, Q, M, S, Y,P, H, X 。
9. 在堆排序、快速排序和歸并排序中,
若只從存儲空間考慮,則應(yīng)首先選取 堆排序 方法,其次選取 快速排序 方法,最后選取 歸并排序 方法;
若只從排序結(jié)果的穩(wěn)定性考慮,則應(yīng) 選取歸并排序方法;
若只從平均情況下最快考慮,則應(yīng)選取快速排序方法;
若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮,則應(yīng)選取堆排序方法。
二、單項選擇題(每小題1分,共18分)
( C )1.將5個不同的數(shù)據(jù)進行排序,至多需要比較 次。
A. 8 B. 9 C. 10 D. 25
( C )2. 排序方法中,從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較,將其放入已排序序列的正確位置上的方法,稱為
A. 希爾排序 B. 冒泡排序 C. 插入排序 D. 選擇排序
( D )3. 排序方法中,從未排序序列中挑選元素,并將其依次插入已排序序列(初始時為空)的一端的方法,稱為
A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序
( C )4.對n個不同的排序碼進行冒泡排序,在下列哪種情況下比較的次數(shù)最多。
A. 從小到大排列好的 B. 從大到小排列好的 C. 元素?zé)o序 D. 元素基本有序
( D )5.對n個不同的排序碼進行冒泡排序,在元素?zé)o序的情況下比較的次數(shù)為
A. n+1 B. n C. n-1 D. n(n-1)/2
(前3個答案都太小了)
( C )6.快速排序在下列哪種情況下最易發(fā)揮其長處。
A. 被排序的數(shù)據(jù)中含有多個相同排序碼 B. 被排序的數(shù)據(jù)已基本有序
C. 被排序的數(shù)據(jù)完全無序 D. 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊
( B )7. 【計研題2001】對有n個記錄的表作快速排序,在最壞情況下,算法的時間復(fù)雜度是
A.O(n) B.O(n2) C.O(nlog2n) D.O(n3)
( C )8.若一組記錄的排序碼為(46, 79, 56, 38, 40, 84),則利用快速排序的方法,以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為
A. 38, 40, 46, 56, 79, 84 B. 40,38, 46 , 79, 56, 84
C. 40, 38,46, 56, 79, 84 D. 40, 38,46, 84, 56, 79
( A&D )9.【計研題2001】在最好情況下,下列排序算法中 排序算法所需比較關(guān)鍵字次數(shù)最少。
A.冒泡 B.歸并 C.快速 D.直接插入
(僅n—1次!)
( C )10. 【計研題2001】置換選擇排序的功能是 。 (置換選擇排序=簡單選擇排序?)
A.選出最大的元素 B.產(chǎn)生初始歸并段 C.產(chǎn)生有序文件 D.置換某個記錄
( A )11.將5個不同的數(shù)據(jù)進行排序,至少需要比較 次。
A. 4 B. 5 C. 6 D. 7
( D )12.下列關(guān)鍵字序列中, 是堆。
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
( B )13.堆是一種 排序。
A. 插入 B.選擇 C. 交換 D. 歸并
( C )14.堆的形狀是一棵
A. 二叉排序樹 B.滿二叉樹 C. 完全二叉樹 D. 平衡二叉樹
( B )15.若一組記錄的排序碼為(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
( B )16. 下述幾種排序方法中,平均查找長度(ASL)最小的是
A. 插入排序 B.快速排序 C. 歸并排序 D. 選擇排序
( C )17. 下述幾種排序方法中,要求內(nèi)存最大的是
A. 插入排序 B.快速排序 C. 歸并排序 D. 選擇排序
( B )18.目前以比較為基礎(chǔ)的內(nèi)部排序方法中,其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是
A. 插入排序 B. 二分插入排序 C. 快速排序 D. 冒泡排序
三、簡答題(每小題4分,共36分)
1. 【全國專升本題】已知序列基本有序,問對此序列最快的排序方法是多少,此時平均復(fù)雜度是多少?
答:插入排序和冒泡應(yīng)該是最快的。因為只有比較動作,無需移動元素。此時平均時間復(fù)雜度為O(n)
2. 設(shè)有1000個無序的元素,希望用最快的速度挑選出其中前10個最大的元素,最好采用哪種排序方法?
答:用堆排序或錦標(biāo)賽排序最合適,因為不必等全部元素排完就能得到所需結(jié)果,時間效率為O(nlog2n)
;若用冒泡排序則需時n!/(n-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, 問采用的是什么排序方法?
答:用的是快速排序方法。注意每一趟要振蕩完全部元素才算一個中間結(jié)果。
4. 對于整數(shù)序列100,99,98,…3,2,1,如果將它完全倒過來,分別用冒泡排序和快速排序法,它們的比較次數(shù)和交換次數(shù)各是多少?
答:冒泡排序的比較和交換次數(shù)將最大,都是1+2+…+n-1=n(n-1)/2=5099=4545次
快速排序則看按什么數(shù)據(jù)來分子表。
如果按100來分,則很慘,也會是n(n-1)/2!
若按中間數(shù)據(jù)50或51來分表,則:
第1輪能確定1個元素,即在1個子表中比較和交換了n-1個元素;n-(21-1)
第2輪能再確定2個元素,即在2個子表中比較和交換了n-3個元素;n-(22-1)
第3輪能再確定4個元素,即在4個子表中比較和交換了n-7個元素;n-(23-1)
第4輪能再確定8個元素,即在8個子表中比較和交換了n-15個元素;n-(24-1)
……
第6輪能再確定32個元素,即在32個子表中比較和交換了n-65個元素;n-(26-1)
第7輪則能全部確定,(因為27=128), 在100個子表中比較和交換了n-(100-1)個元素;
比較和交換總次數(shù)為:7n-(21-1+22-1+23-1……+26-1+100-1) =7n+7-(1+2+4+……+64+100)=7n-(8+16+32+164)=700-220=480次
若從中間選擇初始元素,則ASL=(n+1)log2n-(21+22+23+……+2m)= nlog2n+log2n-(21+22+23+……+n)≈O(nlog2n)
5.【全國專升本試題】【嚴(yán)題集10.15④】設(shè)有n個值不同的元素存于順序結(jié)構(gòu)中,試問能否用比2n-3少的比較次數(shù)選出這n個元素中的最大值和最小值?若能請說明如何實現(xiàn)(不需寫算法)。在最壞情況下至少需進行多少次比較。(或問:對含有n個互不相同元素的集合,同時找最大元和最小元至少需進行多少次比較?)
答:若用冒泡排序法,求最大值需n-1次比較;第二趟改為從n-1開始求最小值,需n-2次比較,合計2n-3次。
顯然本題意圖是放棄冒泡排序,尋找其他方法。
法1 :一個簡單的辦法是,在一趟比較時,將頭兩個元素分別作為最大和最小值的暫存內(nèi)容,將其余n-2個元素與其相比,具體可設(shè)計為:
第1步:a1
a2? YES則直接替換a2,NO則再比較a1, 1~2次;
第3步:a4>a2? YES則直接替換a2,NO則再比較a1, 1~2次;
……
第n-1步:an>a2? YES則直接替換a2,NO則再比較a1, 1~2次;
合計:(n-2)(1~2)+1=(n-1)~(2n-3 )≤2n-3 最好情況至少需要n-1次比較,最壞情況需2n-3次。
法2 :借用快速排序第一趟思想:以a1為支點,將序列分成兩個子表。這一趟需要n-1次比較;
然后,在左邊的子表中求最小值,冒泡一趟需要y-1次;
在右邊的子表中求最大值,冒泡一趟需要z-1次;
合計需要(n-1)+( y-1)+( z-1)=n+y+z-3 因為y+z+1=n, 所以總次數(shù)=2n-4≤2n-3!!!!!!!!!!!
但最壞情況下仍為為2n-3次,即一趟完畢后仍為單子表的情況。怎么辦?有無更好的辦法?
法3 :能否用錦標(biāo)賽排序思路?求最大值等于求冠軍,需要n—1次比較;但接著求最小值,等于在n/2個葉子中比較即可。
編程也不復(fù)雜:可設(shè)計為,
第一趟:n個數(shù)據(jù)兩兩比較(共n/2次),小者放偶數(shù)位,大者放奇數(shù)位;
第二趟:對奇數(shù)位元素繼續(xù)兩兩比較(n/4次);對偶數(shù)位元素也兩兩比較(n/4次);合計n/2次;
第三趟:對奇數(shù)位元素繼續(xù)兩兩比較(n/23次);對偶數(shù)位元素也兩兩比較(n/23次);合計n/22次;
第四趟:對奇數(shù)位元素繼續(xù)兩兩比較(n/24次);對偶數(shù)位元素也兩兩比較(n/24次);合計n/23次;
……
第log2n趟:對奇數(shù)位元素繼續(xù)兩兩比較(n/2log2n次=1);對偶數(shù)位元素也兩兩比較(1次);合計2次;
全部比較次數(shù)為:2+4+8+……+n/2次≤2n-3 (n>1)
用二進制性質(zhì)即可證明? 因為 20+21+…2k-2+2k-1<2k ,即21+…2k-2+2k-1<2k —1 < 2k —1 +2k —2
(n=2k, 當(dāng)k=1,即n=2時為極端情況,1=1; n=3時,1.5<3
k=2時,即n=4時,2<5
6. 【成教考題】將兩個長度為n的有序表歸并為一個長度為2n的有序表,最小需要比較n次,最多需要比較2n-1次,請說明這兩種情況發(fā)生時,兩個被歸并的表有何特征?
答:最少的比較次數(shù)是這樣一種情況:若A表所有元素都小于(或大于)B表元素,則A1比較完B1~Bn之后,直接拼接即可。
最多比較次數(shù)的情況應(yīng)該是A、B兩表互相交錯,此時需要穿插重排。則A表的每個元素都要與B表元素相比,A1與B1相比,能確定其中一個元素的位置;剩下一個還要與另一表中下一元素再比較一次,
即:在表A或表B的n個元素中,除了最后一個元素外,每個元素都要比較2次!最壞情況總共為2n—1次。
7. 【嚴(yán)題集10.11②】試問:按錦標(biāo)賽排序的思想,決出8名運動員之間的名次排列,至少需編排多少場次的比賽(應(yīng)考慮最壞的情況)?
劉答:不能簡單地用(n-1)+(n-2)log2n來計算比賽場次。要特別注意,隨著n/2的葉子結(jié)點被調(diào)整完畢之后,樹的深度會逐層減少!
分別n=8和n=7的情況推導(dǎo)并歸納,得到如下計算公式:
比賽場次=(n-1)+n/2(k-1)+ (n/22)(k-2)+…+ n/2(k-1) ,其中k=log2n
當(dāng)n=8時,k=3, 比賽場次=7+8/2(2)+8/4= 17場(這是最壞情況,即每次都先從葉子調(diào)整起)
8. 【嚴(yán)題集10.19④】假設(shè)某大旅店共有5000個床位,每天需要根據(jù)住宿旅客的文件制造一份花名冊,該名冊要求按?。ㄊ校┑拇涡蚺帕校恳皇。ㄊ校┌纯h(區(qū))排列,又同一縣(區(qū))的旅客按姓氏排列。請你為旅店的管理人員設(shè)計一個制作這份花名冊的方法。
(提示)這是一個多關(guān)鍵字的排序問題。請思考對這個文件進行排序用哪一種方法更合適,是MSD法還是LSD法?
答:采用哪種排序方法,關(guān)鍵要看記錄的結(jié)構(gòu)是如何定義的,如果旅客填表如下:
?。ㄊ校?
縣(區(qū))
姓名
床位號
則按題意要求,應(yīng)當(dāng)采用MSD法,否則無法滿足。
但若“姓名”項在前,則必須用LSD才符合題意要求。
9. 【全國專升本題】【嚴(yán)題集10.6④】奇偶交換排序如下所述:第一趟對所有奇數(shù)i,將a[i]和a[i+1]進行比較;第二趟對所有的偶數(shù)i,將a[i]和a[i+1]進行比較,若a[i]>a[i+1],則兩者交換;第三趟對奇數(shù)i,第四趟對偶數(shù)i;……依次類推直至整個序列有序為止。
(1)試問這種排序方法的結(jié)束條件是什么?是否為穩(wěn)定排序?
(2)分析當(dāng)初始序列為正序或逆序兩種情況下,奇偶交換排序過程中所需進行的關(guān)鍵字比較的次數(shù)。
(3)分析此種排序方法的平均復(fù)雜度及最壞復(fù)雜度。
答:(1) 這種算法其實是兩兩比較,第一趟很像錦標(biāo)賽的“初賽”,將勝者(大數(shù))置于偶數(shù)單元;
第二趟對偶數(shù)單元操作,即第一組大者與第二組小者戰(zhàn),大者后移。結(jié)果相當(dāng)于冒泡排序的一趟;
所以結(jié)束條件應(yīng)為偶數(shù)趟無交換。
結(jié)束條件是:若n為偶數(shù)時,奇數(shù)循環(huán)時i>n-1 ,偶數(shù)循環(huán)時i>n ,
若n為奇數(shù)時,奇數(shù)循環(huán)時i>n 偶數(shù)循環(huán)時i>n+1
似乎不穩(wěn)定?因為交換沒有依次進行。
四、【全國專升本類似題】【類嚴(yán)題集10.1①】以關(guān)鍵字序列(256,301,751,129,937,863,742,694,076,438)為例,分別寫出執(zhí)行以下算法的各趟排序結(jié)束時,關(guān)鍵字序列的狀態(tài),并說明這些排序方法中,哪些易于在鏈表(包括各種單、雙、循環(huán)鏈表)上實現(xiàn)?
① 直接插入排序 ② 希爾排序 ③冒泡排序 ④快速排序
⑤直接選擇排序 ⑥ 堆排序 ⑦ 歸并排序 ⑧ 基數(shù)排序 (8分)
解:先回答第2問: ① ⑤ ⑦ ⑧皆易于在鏈表上實現(xiàn)。
① 直接插入排序的中間過程如下: ② 希爾排序的中間過程如下:
③ 冒泡排序的中間過程如下: ④快速排序的中間過程如下:
⑤ 直接選擇排序的中間過程如下: ⑥堆排序(大根堆)的中間過程如下:
⑦ 歸并排序排序的中間過程如下:
⑧ 基數(shù)排序的中間過程如下:
五、算法設(shè)計題(4選2, 每題7分,共14分)
1. 【嚴(yán)題集10.25③】試編寫教科書10.2.2節(jié)中所述鏈表插入排序的算法。
10.25
void SLInsert_Sort(SLList &L)//靜態(tài)鏈表的插入排序算法
{
L.r[0].key=0;L.r[0].next=1;
L.r[1].next=0; //建初始循環(huán)鏈表
for(i=2;i<=L.length;i++) //逐個插入
{
p=0;x=L.r[i].key;
while(L.r[L.r[p].next].keyL.r[i];
L.r[i].next=p;
}
p=q;
}//for
}//SLInsert_Sort
2. 【嚴(yán)題集10.30④】按下述原則編寫快排的非遞歸算法:
(1) 一趟排序之后,先對長度較短的子序列進行排序,且將另一子序列的上、下界入棧保存;
(2) 若待排記錄數(shù)≤3,則不再進行分割,而是直接進行比較排序。
10.30
typedef struct {
int low;
int high;
} boundary; //子序列的上下界類型
void QSort_NotRecurve(int SQList &L)//快速排序的非遞歸算法
{
low=1;high=L.length;
InitStack(S); //S的元素為boundary類型
while(low2) //如果當(dāng)前子序列長度大于3且尚未排好序
{
pivot=Partition(L,low,high); //進行一趟劃分
if(high-pivot>pivot-low)
{
Push(S,{pivot+1,high}); //把長的子序列邊界入棧
high=pivot-1; //短的子序列留待下次排序
}
else
{
Push(S,{low,pivot-1});
low=pivot+1;
}
}//if
else if(low=pivotkey)
high--;
L.r[low]=L.r[high];
while(lowL.r[high].key) L.r[low]<->L.r[high];
else //子序列含有三個元素
{
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
}
}//Easy_Sort
3. 【嚴(yán)題集10.41④】假設(shè)有1000個關(guān)鍵字為小于10000的整數(shù)的記錄序列,請設(shè)計一種排序方法,要求以盡可能少的比較次數(shù)和移動次數(shù)實現(xiàn)排序,并按你的設(shè)計編出算法。
解:可以用基數(shù)排序來實現(xiàn),關(guān)鍵字位數(shù)d=4,數(shù)基radix=10(從0~9)
則基數(shù)排序的算法如下;
void Hash_Sort(int a[ ])//對1000個關(guān)鍵字為四位整數(shù)的記錄進行排序
{
int b[10000];
for(i=0;i<1000;i++) //直接按關(guān)鍵字散列 (即分配)
{
for(j=a[i];b[j];j=(j+1)%10000);
b[j]=a[i];
}
for(i=0,j=0;i<1000;j++) //將散列收回a中
if(b[j])
{
for(x=b[j],k=j;b[k];k=(k+1)%10000)
if(b[k]==x)
{
a[i++]=x;
b[k]=0;
}
}//if
}//Hash_Sort
4. 【嚴(yán)題集10.42④】序列的“中值記錄”指的是:如果將此序列排序后,它是第[n/2]個記錄。試寫一個求中值記錄的算法。
10.42
typedef struct {
int gt; //大于該記錄的個數(shù)
int lt; //小于該記錄的個數(shù)
} place; //整個序列中比某個關(guān)鍵字大或小的記錄個數(shù)
int Get_Mid(int a[ ],int n) //求一個序列的中值記錄的位置
{
place b[MAXSIZE];
for(i=0;ia[i]) b[i].gt++;
else if(a[j]
下載提示(請認(rèn)真閱讀)
- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都歸您。
文檔包含非法信息?點此舉報后獲取現(xiàn)金獎勵!
下載文檔到電腦,查找使用更方便
5
積分
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
-
排序
答案
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學(xué)習(xí)交流,未經(jīng)上傳用戶書面授權(quán),請勿作他用。
鏈接地址:http://www.820124.com/p-12786901.html