上海海事大學數據結構試題及答案

Ⅰ 求下面數據結構試題的答案。。。

全國2008年10月高等教育自學考試

數據結構試題

課程代碼：02331

一、單項選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個備選項中只有一個是最符合題目要求的，請將其代碼填寫在題後的括弧內。錯選、多選或未選均無分。

1.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接後繼，則該結構是（ ）

A. 棧 B. 隊列

C. 樹 D. 圖

2.下面程序段的時間復雜度為（ ）

for (i=0; i<m; i++)

for (j=0; j<n; j++)

A[i][j]=i*j;

A. O (m2) B. O (n2)

C. O (m*n) D. O (m+n)

3.在頭指針為head的非空單循環鏈表中，指針p指向尾結點，下列關系成立的是（ ）

A. p->next==head B. p->next->next==head

C. p->next==NULL D. p==head

4.若以S和X分別表示進棧和退棧操作，則對初始狀態為空的棧可以進行的棧操作系列是（ ）

A. SXSSXXXX B. SXXSXSSX

C. SXSXXSSX D. SSSXXSXX

5.兩個字元串相等的條件是（ ）

A. 串的長度相等 B. 含有相同的字元集

C. 都是非空串 D. 串的長度相等且對應的字元相同

6.如果將矩陣An×n的每一列看成一個子表，整個矩陣看成是一個廣義表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),並且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（ ）

A. head (tail (head (L))) B. head (head(head(L)))

C. tail (head (tail (L))) D. head (head (tail (L)))

7.已知一棵含50個結點的二叉樹中只有一個葉子結點，則該樹中度為1的結點個數為（ ）

A. 0 B. 1

C. 48 D. 49

8.在一個具有n個頂點的有向圖中，所有頂點的出度之和為Dout ，則所有頂點的入度之和為（ ）

A. Dout B. Dout-1

C. Dout+1 D. n

9.如圖所示的有向無環圖可以得到的拓撲序列的個數是（ ）

A. 3 B. 4

C. 5 D. 6

10.如圖所示的帶權無向圖的最小生成樹的權為（ ）

A. 51 B. 52

C. 54 D. 56

11.對長度為n的關鍵字序列進行堆排序的空間復雜度為（ ）

A. O（log2n） B. O（1）

C. O（n） D. O（n*log2n）

12.已知用某種排序方法對關鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結果為

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）

所採用的排序方法是（ ）

A. 插入排序 B. 冒泡排序

C. 快速排序 D. 歸並排序

13.已知散列表的存儲空間為T[0..18]，散列函數H（key）=key%17,並用二次探測法處理沖突。散列表中已插入下列關鍵字：T[5]=39，T[6]=57和T[7]=7，則下一個關鍵字23插入的位置是（ ）

A. T[2] B. T[4]

C. T[8] D. T[10]

14.適宜進行批量處理的文件類型是（ ）

A. 順序文件 B. 索引順序文件

C. 散列文件 D. 多關鍵字文件

15.VSAM文件的索引結構為（ ）

A. B+樹 B. 二叉排序樹

C. B-樹 D. 最優二叉樹

二、填空題(本大題共10小題，每小題2分，共20分)

請在每小題的空格中填上正確答案。錯填、不填均無分。

16.如果某演算法對於規模為n的問題的時間耗費為T（n）=3n3，在一台計算機上運行時間為t秒，則在另一台運行速度是其64倍的機器上，用同樣的時間能解決的問題規模是原問題規模的 倍。

17.將兩個長度分別為m和n的遞增有序單鏈表，歸並成一個按元素遞減有序的單鏈表，可能達到的最好的時間復雜度是 。

18.已知循環隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下一個位置，則在隊列不滿的情況下，隊列的長度是 。

19.字元串「sgabacbadfgbacst」 中存在有 個與字元串「ba」相同的子串。

20.假設以列優先順序存儲二維數組A[5][8]，其中元素A[0][0]的存儲地址為LOC（a00）,且每個元素佔4個存儲單元，則數組元素A[i][j]的存儲地址為 。

21.假設用<x,y>表示樹的邊（其中x是y的雙親），已知一棵樹的邊集為

，該樹的度是 。

22.n個頂點且含有環路的無向連通圖中，至少含有 條邊。

23.在一般情況下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數最少的是 。

24.和二分查找相比，順序查找的優點是除了不要求表中數據元素有序之外，對 結構也無特殊要求。

25.順序文件中記錄存放的物理順序和 順序一致。

三、解答題(本大題共4小題，每小題5分，共20分)

26.由森林轉換得到的對應二叉樹如圖所示，寫出原森林中第三棵樹的前序序列和後序序列。

前序序列：

後序序列：

27.圖的鄰接表的類型定義如下所示：

#define MaxVertexNum 50

typedef struct node {

int adjvex;

struct node *next;

}EdgeNode;

typedef struct {

VertexType vertex;

EdgeNode *firstedge;

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct {

AdjList adjlist;

int n, e;

}ALGraph;

為便於刪除和插入圖的頂點的操作，可將鄰接表的表頭向量定義為鏈式結構，兩種定義的存儲表示實例如下圖所示，請寫出重新定義的類型說明。

題27圖

28.某類物品的編號由一個大寫英文字母及2位數字（0..9）組成，形如E32。運用基數排序

對下列物品編號序列進行按字典序的排序，寫出每一趟（分配和收集）後的結果。

E13，A37，F43，B32，B47，E12，F37，B12

第一趟：

第二趟：

第三趟：

29.（1）畫出對表長為13的有序順序表進行二分查找的判定樹；

（2）已知關鍵字序列為（12，14，16，21，24，28，35，43，52，67，71，84，99），寫出在該序列中二分查找37時所需進行的比較次數。

（1）

（2）

四、演算法閱讀題（本大題共4小題，每小題5分，共20分）

30.已知線性表的存儲結構為順序表，閱讀下列演算法，並回答問題：

（1）設線性表L=（21，-7，-8，19，0，-11，34，30，-10），寫出執行f30(&L)後的L狀態；

（2）簡述演算法f30的功能。

void f30 (SeqList *L) {

int i,j;

for (i=j=0;i<L->length; i++)

if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i];

j++；

}

L->length=j;

}

(1)

(2)

31.閱讀下列演算法，並回答問題：

（1）Q、Q1和Q2都是隊列結構，設隊列Q=（1，0，-5，2，-4，-6，9），其中1為隊頭元素，寫出執行f31 (&Q,&Q1,&Q2)之後隊列Q、Q1和Q2的狀態；

（2）簡述演算法f31的功能。

（註：lnitQueue、EnQueue、DeQueue和QueueEmpty分別是隊列初始化、入列、出隊和判隊空的操作）

void f31 (Queue*Q, Queue*Q1, Queue*Q2) {

int e;

lnitQueue (Q1);

lnitQueue (Q2);

while (!QueueEmpty (Q)) {

e=DeQueue (Q);

if (e>=0) EnQueue (Q1,e);

else EnQueue (Q2,e)

}

}

（1）

（2）

32.閱讀下列演算法，並回答問題：

（1）假設串由合法的英文字母和空格組成，並以』\0』作結束符。設串s=」⊔⊔|⊔am⊔a⊔⊔⊔student」(⊔表示空格符)，寫出f32（s）的返回值；

（2）簡述演算法f32的功能。

int f32 (char*s){

int i, n, inword;

n=inword=0;

for (i=0;s[i]!=』\0』;i++)

if (s[i]!=』⊔』&& inword==0){

inword=1;

n++;

}

else if (s[i]==』⊔』&& inword==1)

inword=0;

return n;

}

（1）

（2）

33.閱讀下列對正整數關鍵字序列L操作的演算法，並回答問題：

（1）設L=(28,19,27,49,56,12,10,25,20,50),寫出f33 (L,4)的返回值；

（2）簡述函數f33的功能。

int Partition (SeqList*L, int low, int high);

‖對L[low..high]做劃分，返回基準記錄的位置，並使左部的關鍵字

‖都小於或等於基準記錄的關鍵字，右部的關鍵字都大於基準記錄的關鍵字

int f33 (SeqList L, int k){

int low, high, pivotpos;

low=1;

high=L.length;

if (k<low || k>high)

return-1;

do {

pivotpos=Partition (&L, low, high);‖調用快速排序的劃分演算法

if (pivotpos<k)

low=pivotpos+1;

else if (pivotpos>k)

high=pivotpos-1;

}while (pivotpos!=k);

return L.data [pivotpos];

}

（1）

（2）

五、演算法設計題（本題10分）

34.二叉排序樹的類型定義如下：

typedef struct BSTNode {‖ 二叉排序樹的結點結構

int data; ‖數據域

struct BSTNode *lchild, *rchild; ‖左、右孩子指針

}BSTNode,*BSTree;

設計遞歸演算法，統計一棵二叉排序樹T中值小於a的結點個數。

Ⅱ 數據結構考試試題

1~5:CBBDC
6:2的k次方減1
7：D
8：B
9：B
後面的自己看吧

Ⅲ 數據結構本科試題

6 、A （至多有2^(k-1)個節點。k為深度）
7、A（簡單排一下，就發現父節點就是編號/2）
8、B（隊列先進先出）
9、B（
結點的權：在一些應用中，賦予樹中結點的一個 有某種意義的實數。
結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度：為樹中所有葉結點的帶權路徑長度之和）
10、B（先訪問根節點、再訪問左子樹，最後右子樹）
11、C（首先肯定是線性結構，排除D，其次，隊列和棧，順序存儲、鏈式存儲皆可。A、B顯然不對）

Ⅳ 數據結構考試復習題1

太晚了今天 記下了 下次來回答你 放入收藏夾了 希望來得及

Ⅳ 數據結構試題

1.A）順序

3.可能的順序有14種
ABCD; ABDC; ACBD; ACDB; ADCB; BCDA; BDCA;
BADC; BACD; BCAD; CDBA; CBAD; CBDA; DCBA
4.隊尾
5大於等於一
6,8
7. 6

Ⅵ 數據結構 試題 求答案

首先，定義一個數組存放上表所有數據（共46個數據）。設這個數組為A(46)
然後按下列步驟進行排序計算
1）A(1)≤A(2)？是轉第2步，否則

A(1)<-->A(2)（即A(1)、A(2)值互換，實現A(1)≤A(2)）
2）A(2)≤A(3)？是（說明A(1)≤A(2)≤A(3)）轉第3步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(1)≤A(2)？是（說明A(1)≤A(2)≤A(3)）轉第3步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)）
3）A(3)≤A(4)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(3)<-->A(4)（實現A(3)≤A(4)）

A(3)≥A(2)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(2)≥A(1)？是（說明A(1)≤A(2)≤A(3)≤A(4)）轉第4步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)≤A(4)）
4）A(4)≤A(5)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(4)<-->A(5)（實現A(4)≤A(5)）

A(4)≥A(3)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(3)<-->A(4)（實現A(3)≤A(4)）

A(3)≥A(4)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(2)<-->A(3)（實現A(2)≤A(3)）

A(2)≥A(1)？是（說明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）轉第5步，否則

A(1)<-->A(2)（實現A(1)≤A(2)≤A(3)≤A(4)≤A(5)）
5）A(5)≤A(6)？是轉第6步，否則

A(5)<-->A(6)

A(5)≥A(4)？是轉第6步，否則

A(4)<-->A(5)

A(4)≥A(3)？是轉第6步，否則

A(3)<-->A(4)

A(3)≥A(2)？是轉第6步，否則

A(2)<-->A(3)

A(2)≥A(1)？是轉第6步，否則

A(1)<-->A(2)
6）......

按如上思路進行下去，即可實現A(46)數組按升序重排。

由上述1）~5）步的比較過程可以看出，每執行一步，就完成一次若干組數據從小到大的排序，且執行比較時，總是從已排好序的最大那個數開始，從大到小進行邊比較邊調整次序。另一個特點是，越到後面，每一步中需要比較與調整的數據越多。

Ⅶ 數據結構試題庫

網路文庫有好多呢，只要些積分就行了啊。
豆丁上面有更多，更專業的東西，但是需要掏錢，你自己選擇著看看吧。
豆瓣有討論組可以為你找到所有你想要的東西，但是得耐心的找相關的小組和人

Ⅷ 尋一份《數據結構》試題及答案

《數據結構》試題一、選擇題（每小題2分，共30分）1． 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則採用（ ）存儲方式最節省時間。A、單鏈表 B、雙鏈表 C、單向循環 D、順序表2． 串是任意有限個（ ）A、符號構成的序列 B、符號構成的集合C、字元構成的序列 D、字元構成的集合3． 設矩陣A（aij ，l≤i,j≤ 10）的元素滿足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i<j, l≤i, j≤ 10)現將A的所有非0元素以行序為主序存放在首地址為2000的存儲區域中，每個元素佔有4個單元，則元素A[9][5]的首址為A、2340 B、2336 C、2164 D、21604． 如果以鏈表作為棧的存儲結構，則退棧操作時（ ）A、 必須判別棧是否滿 B、 對棧不作任何判別C、 必須判別棧是否空 D、 判別棧元素的類型5． 設數組Data[0..m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出隊操作的語句為（ ）A、front=front+1 B、front=(front+1)% mC、rear=(rear+1)%m D、front=(front+1)%(m+1)6． 深度為6（根的層次為1）的二叉樹至多有（ ）結點。A、 64 B、32 C、31 D、637． 將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親編號為（ ）A、24 B、25 C、23 D、無法確定8． 設有一個無向圖G=（V，E）和G』=（V』，E』）如果G』為G的生成樹，則下面不正確的說法是（ ）A、G』為G 的子圖 B、G』為G 的邊通分量C、G』為G的極小連通子圖且V』=V D、G』為G的一個無環子圖9． 用線性探測法查找閉散列表，可能要探測多個散列地址，這些位置上的鍵值（ ）A、 一定都是同義詞 B、一定都不是同義詞 C、都相同 D、不一定都是同義詞10． 二分查找要求被查找的表是（ ）A、 鍵值有序的鏈接表 B、鏈接表但鍵值不一定有序C、 鍵值有序的順序表 D、順序表但鍵值不一定有序11． 當初始序列已經按鍵值有序，用直接插入演算法對其進行排序，需要循環的次數為（ ）A、n2 B、nlog2n C、log2n D、n-1 12． 堆是一個鍵值序列{k1,k2,…, kn},對i=1,2,…,|_n/2_|,滿足( )A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2iC、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n) 13．一個具有n個頂點的無向完全圖的邊數為（ ）A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)14．在索引順序表中查找一個元素，可用的且最快的方法是（ ）A、用順序查找法確定元素所在塊，再用順序查找法在相應塊中查找B、用順序查找法確定元素所在塊，再用二分查找法在相應塊中查找C、用二分查找法確定元素所在塊，再用順序查找法在相應塊中查找D、用二分查找法確定元素所在塊，再用二分查找法在相應塊中查找15．若某線性表中最常用的操作是在最後一個元素之後插入一個元素和刪除最後一個元素，則採用（ ）存儲方式最節省運算時間。A、 單鏈表 B、雙鏈表C、帶頭結點的雙循環鏈表D、容量足夠大的順序表 二、判斷題（每小題1分，共10分）1．雙鏈表中至多隻有一個結點的後繼指針為空。（ ）2．在循環隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear。（ ）3．對鏈表進行插入和刪除操作時，不必移動結點。（ ）4．棧可以作為實現程序設計語言過程調用時的一種數據結構。（ ）5．在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。( )i6．對有向圖G，如果從任一頂點出發進行一次深度優先或廣度優先搜索就能訪問每個頂點，則該圖一定是完全圖。( )7．「順序查找法」是指在順序表上進行查找的方法。（ ）8．向二叉排序樹插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。（）9．鍵值序列{A，C，D，E，F，E，F}是一個堆。10．二路歸並時，被歸並的兩個子序列中的關鍵字個數一定要相等。（） 三、填空題（每小題2分，共20分）1．在帶有頭結點的單鏈表L中，若要刪除第一個結點，則需執行下列三條語句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一個長度為20的有序表採用二分查找方法進行查找，共有＿＿＿＿＿＿個元素的查找長度為3。3．採用冒泡排序對有n個記錄的表A按鍵值遞增排序，若L的初始狀態是按鍵值遞增，則排序過程中記錄的比較次數為＿＿＿＿＿。若A的初始狀態為遞減排列，則記錄的交換次數為＿＿＿＿＿＿＿。4．在無頭結點的雙鏈表中，指針P所指結點是第一個結點的條件是＿＿＿＿＿＿。5．G為無向圖，如果從G的某個頂點出發，進行一次廣度優先搜索，即可訪問圖的每個頂點，則該圖一定是＿＿＿＿＿圖。6．如果一個有向圖中沒有＿＿＿＿＿＿，則該圖的全部頂點可能排成一個拓撲序列。7．深度為8（根的層次號為1）的滿二叉樹有＿＿＿＿＿＿個葉子結點。 8．將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點X，其雙親PARENT（X）的編號為＿＿＿＿＿＿＿。9．設某閉散列表HT未滿，散列函數H（KEY）為鍵值第一字母在字母表中的序號，處理沖突方法為線性探測法，請在下列演算法劃線處填上適當內容，以實現按鍵值第一字母的順序輸出閉散列表中所有鍵值的演算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(「datatype」,HT[j]); j=(j+1)% m; } } }10．設有一個鏈隊，結點結構為data|next，front為隊頭指針，rear為隊尾指針，當執行入隊操作時需執行下列語句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、簡答題：（每小題4分，共20分）1. 對於一個有10000個結點的二叉樹，樹葉最多有多少個？最少有多少個？2. 已知一棵二叉樹的中序序列和後序序列分別為： DBGEACHF和DGEBHFCA，則該二叉樹的前序序列是什麼？3. 設有1000個無序的元素，需排出前10個最大（小）的元素，你認為採用哪種排序方法最快？為什麼？4. 在KMP演算法中，已知模式串為ADABCADADA ，請寫出模式串的next[j]函數值。5. 中序遍歷的遞歸演算法平均空間復雜度為多少？ 五、 演算法設計題（每小題10分，共20分）1. 試編寫一個演算法，判斷一給定的整型數組a[n]是不是一個堆。2. 一棵二叉樹的繁茂度定義為各層結點數的最大值與樹的高度的乘積。試寫一高效演算法，求二叉樹的繁茂度。參考答案一、選擇題1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判斷題 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空題1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．連通6．迴路或環7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不為空、H(HT[j])=I10．rear - > next = p、rear = p四、簡答題：1. 答： 最多是完全二叉樹的形態，即5000個葉子；最少是單支樹的形態，即1個葉子。2.答：是：ABDEGCFH3. 答：用錦標賽排序或堆排序很合適，因為不必等全部元素排完就能得到所需結果，時間效率為O(nlog2n)； 即O（1000log21000）=O(10000) 錦標賽排序的准確比較次數為：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准確比較次數為：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也較快，最多耗費比較次數為（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考慮遞歸時佔用了棧空間，但遞歸次數最多不超過樹的高度，所以空間復雜度為O(log2n) 五、 演算法設計題1.解：提示：堆的定義是：ki<k2i和K2i＋1 void SortA(sqlist &A, int n) { if(n==0) return(0); //空表if (a[1]<a[2]) { for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);return(「maxleap」)};}2. 要用層次遍歷以及隊列來處理，可以增設一個寬度計數器，在統計完每一層的結點個數之後,再從計數器中挑出最大值。typedef struct { BTNode node; int layer; //layer是結點所在層數 } BTNRecord, r ; int Width(Bitree T ){ //求樹寬 int count[ ]; //增開count向量，存放各層對應的結點數 InitQueue(Q); //隊列初始化，Q的元素為BTNRecord類型 EnQueue(Q,{T, 0}); //根結點入隊, 0 表示count[0]，下標值 while(!QueueEmpty(Q)) { DeQueue(Q, r); //結點出隊 count[r.layer]++; //出隊時再把結點對應層的計數器加if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按層序入隊時要隨時標注結點所在層號 h=r.layer; //最後一個隊列元素所在層就是樹的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一層結點數最多 return (h*maxn)} // Width

Ⅸ 數據結構的試題

原序列有十個數: 10 18 4 3 6 12 1 9 18 8 [ 以10為基準,處理全部十個數 ] 10與8 互換,得到: 8 18 4 3 6 12 1 9 18 10 10與18互換,得到: 8 10 4 3 6 12 1 9 18 18 10與9 互換,得到: 8 9 4 3 6 12 1 10 18 18 10與12互換,得到: 8 9 4 3 6 10 1 12 18 18 10與1 互換,得到: 8 9 4 3 6 1 10 12 18 18 第1趟排序的結果: 8 9 4 3 6 1 10 12 18 18 [ 以8為基準,處理 8 9 4 3 6 1 ] 8與1互換,得到: 1 9 4 3 6 8 10 12 18 18 8與9互換,得到: 1 8 4 3 6 9 10 12 18 18 8與6互換,得到: 1 6 4 3 8 9 10 12 18 18 第2趟排序的結果: 1 6 4 3 8 9 10 12 18 18 [ 以1為基準,處理 1 6 4 3 ] 1比右邊的數字都小,不用交換 第3趟排序的結果: 1 6 4 3 8 9 10 12 18 18 [ 以6為基準,處理 6 4 3 ] 6與3互換,得到: 1 3 4 6 8 9 10 12 18 18 第4趟排序的結果: 1 3 4 6 8 9 10 12 18 18 [ 以3為基準,處理 3 4 ] 3比4小,不用交換 第5趟排序的結果: 1 3 4 6 8 9 10 12 18 18 [ 以12為基準,處理 12 18 18 ] 12比右邊的數字都小,不用交換 第6趟排序的結果: 1 3 4 6 8 9 10 12 18 18 [ 以18為基準,處理 18 18 ] 18與18不用交換 第7趟排序的結果: 1 3 4 6 8 9 10 12 18 18 這就是最後的排序結果. // C語言測試程序 #include <stdio.h> #define MAXSIZE 10000 /* 用於要排序數組個數最大值，可根據需要修改 */ typedef struct{ int r[MAXSIZE+1];
/* 用於存儲要排序數組，r[0]用作哨兵或臨時變數 */ int length;
/* 用於記錄順序表的長度 */}SqList; int g_count; /* 交換L中數組r的下標為i和j的值 */void swapData(SqList *L,int i,int j){ int temp=L->r[i]; L->r[i]=L->r[j]; L->r[j]=temp;} void printData(SqList L){ int i; printf("(%d) ",g_count); for(i=1;i<L.length;i++) { printf("%d,",L.r[i]); } printf("%d",L.r[i]); printf("\n"); g_count++;} /* 快速排序******************************** *//* 交換順序表L中子表的記錄，使樞軸記錄到位，並返回其所在位置 *//* 此時在它之前(後)的記錄均不大(小)於它。 */int Partition(SqList *L,int low,int high){ int pivotkey; pivotkey=L->r[low]; /* 用子表的第一個記錄作樞軸記錄 */ while(low<high) /* 從表的兩端交替地向中間掃描 */ { while(low<high&&L->r[high]>=pivotkey) high--; swapData(L,low,high);/* 將比樞軸記錄小的記錄交換到低端 */ while(low<high&&L->r[low]<=pivotkey) low++; swapData(L,low,high);/* 將比樞軸記錄大的記錄交換到高端 */ } return low; /* 返回樞軸所在位置 */} /* 對順序表L中的子序列L->r[low..high]作快速排序 */void QSort(SqList *L,int low,int high){ int pivot; if(low<high) { pivot=Partition(L,low,high); /* 將L->r[low..high]一分為二，算出樞軸值pivot */ ////////測試 printData(*L); //////// QSort(L,low,pivot-1);
/* 對低子表遞歸排序 */ QSort(L,pivot+1,high);
/* 對高子表遞歸排序 */ }} /* 對順序表L作快速排序 */void QuickSort(SqList *L){ QSort(L,1,L->length);} int main(){ int d[]={10,18,4,3,6,12,1,9,18,8}; int N; int i; SqList LT; N=sizeof(d)/sizeof(int); for(i=0;i<N;i++) { LT.r[i+1]=d[i]; } LT.length=N; printf("快速排序:\n"); printData(LT); QuickSort(<); return 0;}