上海海事大学数据结构试题及答案

Ⅰ 求下面数据结构试题的答案。。。

全国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;}