數(shù)據(jù)結(jié)構(gòu)第九章排序習(xí)題及答案(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上習(xí)題九 排序一、單項(xiàng)選擇題1下列內(nèi)部排序算法中： A快速排序 B.直接插入排序 C. 二路歸并排序 D. 簡單選擇排序 E. 起泡排序 F. 堆排序（1） 其比較次數(shù)與序列初態(tài)無關(guān)的算法是（ ） （2）不穩(wěn)定的排序算法是（ ）（3）在初始序列已基本有序（除去n個(gè)元素中的某k個(gè)元素后即呈有序，k<<n）的情況下，排序效率最高的算法是（ ）（4）排序的平均時(shí)間復(fù)雜度為O(nlogn)的算法是（ ）為O(nn)的算法是（ ）2比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是( )。A直接插入排序 B起泡排序 C快速排序 D簡單選擇排序3對一組數(shù)據(jù)（84，47，25，15

2、，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 則采用的排序是 ( )。 A. 選擇 B. 冒泡 C. 快速 D. 插入4下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A. 選擇 B. 冒泡 C. 歸并 D. 堆5一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。A(38,40,46,56,79,84) B. (40,38,46,79,56

3、,84)C(40,38,46,56,79,84) D. (40,38,46,84,56,79)6下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是( )排序。 A 冒泡 B. 希爾 C. 快速 D. 堆 7. 就平均性能而言，目前最好的內(nèi)排序方法是( )排序法。A. 冒泡 B. 希爾插入 C. 交換 D. 快速 8. 下列排序算法中，占用輔助空間最多的是：( ) A. 歸并排序 B. 快速排序 C. 希爾排序 D. 堆排序9. 若用冒泡排序方法對序列10,14,26,29,41,52從大到小排序，需進(jìn)行 （ ）次比較。 A. 3 B. 10 C. 15 D. 25 10. 快速排序方法

4、在（ ）情況下最不利于發(fā)揮其長處。 A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值C. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) D. 要排序的數(shù)據(jù)已基本有序11下列四個(gè)序列中，哪一個(gè)是堆（ ）。A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,1512. 有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為 （ ）A-1，4，8，9，20，7，15，7 B-1，7，15，7，4，8，20，9C-1，4，7，8

5、，20，15，7，9 DA，B，C均不對。二、填空題1.若待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是_的，否則稱為_的。2.按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為_排序和_排序。3直接插入排序用監(jiān)視哨的作用是_。4對n個(gè)記錄的表r1.n進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為_。5下面的c函數(shù)實(shí)現(xiàn)對鏈表head進(jìn)行選擇排序的算法,排序完畢,鏈表中的結(jié)點(diǎn)按結(jié)點(diǎn)值從小到大鏈接。請?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容,每個(gè)空框只填一個(gè)語句或一個(gè)表達(dá)式：#include <stdio.h>typedef struct node ch

6、ar data; struct node *link; node;node *select(node *head)node *p,*q,*r,*s; p=(node *)malloc(sizeof(node); p->link=head; head=p;while(p->link!=null) q=p->link; r=p; while (1)_) if (q->link->data<r->link->data) r=q; q=q->link; if (2)_) s=r->link; r->link=s->link; s-

7、>link= (3)_); (4)_); (5)_) ; p=head; head=head->link; free(p); return(head); 6下面的排序算法的思想是：第一趟比較將最小的元素放在r1中，最大的元素放在rn中，第二趟比較將次小的放在r2中，將次大的放在rn-1中，,依次下去，直到待排序列為遞增序。（注：<->）代表兩個(gè)變量的數(shù)據(jù)交換）。void sort(SqList &r,int n) i=1;while(1)_) min=max=1;for (j=i+1;(2)_ ;+j) if(3)_) min=j; else if(rj.key

8、>rmax.key) max=j; if(4)_) rmin < - >rj;if(max!=n-i+1)if (5)_) rmin < - > rn-i+1; else (6)_); i+;/sort 7下列算法為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將ai和ai+1進(jìn)行比較,第二趟對所有偶數(shù)的i,將ai和ai+1進(jìn)行比較,每次比較時(shí)若ai>ai+1,將二者交換;以后重復(fù)上述二趟過程,直至整個(gè)數(shù)組有序。void oesort (int an)int flag,i,t; do flag=0;for(i=1;i<n;i+,i+) if(ai>

9、;ai+1) flag=(1)_; t=ai+1; ai+1=ai; (2)_;for (3)_ if (ai>ai+1) flag=(4)_;t=ai+1; ai+1=ai; ai=t; while (5)_; 第九章 排序一、單項(xiàng)選擇題1（1） DC （2）ADF （3）B （4）ACF BDE 2D3A4C5C6C7. D8. A9. C10. D11C12. C二、填空題1.穩(wěn)定、不穩(wěn)定2.內(nèi)部、外部3免去查找過程中每一步都要檢測整個(gè)表是否查找完畢，提高了查找效率。4n(n-1)/25題中為操作方便，先增加頭結(jié)點(diǎn)（最后刪除），p指向無序區(qū)的前一記錄，r指向最小值結(jié)點(diǎn)的前驅(qū)，一趟排序結(jié)束，無序區(qū)第一個(gè)記錄與r所指結(jié)點(diǎn)的后繼交換指針。(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link6.(