数据结构(C语言版)习题及答案第九章

数据结构(C语言版)习题及答案

习 题

一、选择题

1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始

堆为( B )。

A、79，46，56，38，40，80 B、84，79，56，38，40，46

C、84，79，56，46，40，38 D、84，56，79，40，46，38

2、排序趟数与序列原始状态(原始排列)有关的排序方法是（ ACD ）方法。

A、插入排序 B、选择排序 C、冒泡排序 D、快速排序

3 、下列排序方法中，（ B ）是稳定的排序方法。

A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序

4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟

排序后的结果。

A、选择排序 B、冒泡排序 C、插入排序 D、堆排序

5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，

9，-1，8，20，7，15），则采用的是（ C ）排序。

A、选择 B、快速 C、希尔 D、冒泡

6 、一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第

一个记录为基准元素得到的一次划分结果为（ C ）。

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)

7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是

（ C ）。

A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80

C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40

8、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行

的关键字比较总次数是（ B ）。

A、10 B、15 C、21 D、34

9、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（ A ）。

A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序

C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序

E、以上答案都不对

10、采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（ ）。

A、有关 B、无关

9.2 填空题

1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用（直接插入排序），

若初始数据基本反序，则选用（直接选择排序）。

2、在归并排序中，若待排序记录的个数为20，则共需要进行（5）趟归并，在第三趟

归并中，是把长度为（4）的有序表归并为长度为（8）的有序表。

3、在内排序中，平均比较次数最多的是（快速排序），要求附加的内存空间最大的是（归

并排序），排序时不稳定的有（希尔排序）、（选择排序）、（快速排序）和（堆排序）等几种

方法。

4、对n个元素的序列进行冒泡排序，最少的比较次数是（n-1），此时元素的排列情况

数据结构(C语言版)习题及答案

（从小到大排列），在（从大到小排列）情况下比较次数最多，其比较次数为（n(n-1)/2）。

5、对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把

第7条记录60插入到有序表中时，为寻找插入位置需比较（3）次。

9.3 应用题

1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方

法举出一个不稳定的实例。

答：稳定的排序算法有直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序。

不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。

例子：讲课是的例子。

2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使

前七个记录有序，中间结果如下： 6 13 28 39 41 72 85 20 试在此基础上，沿用上述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答

以下问题：

(1) 使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？

(2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？

答：

插入20的过程：

① 39>20：r=m-1=3;i<=r;m=(i+r)/2=4/2=2

② 13<20: i=m+1=3;i>r;查找过程结束，插入位置为i。

最终结果为：6 13 20 28 39 41 72 85

（1）插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，

每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序

表中的插入位置靠中间，则查找次数最少。

（2）在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对

的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元

素才找到插入位置。直接插入排序则每次只比较一次就找到合适位置。

3、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写

完整下示各步骤结果。

建立初始堆：_97 87 26 61 70 12 3 45

堆排序过程：

（1）87 70 26 61 45 12 3 97;（2） 70 61 26 3 45 12 87 97;

（3）61 45 26 3 12 70 87 97;（4） 45 12 26 3 61 70 87 97;

（5）26 12 3 45 61 70 87 97;（6） 12 3 26 45 61 70 87 97;

（7）3 12 26 45 61 70 87 97;

4、全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分

输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为

什么？

答：因排序的元素个数很大，所以需要采用排序速度较快的排序方法。排序速度比较

快的排序方法有快速排序、堆排序、归并排序和基数排序等。其中快速排序、归并排序和

基数排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连

续位置上的最终元素。但堆排序则每次输出一个堆顶元素（即最大或最小元素），然后对堆

数据结构(C语言版)习题及答案

进行再调整，保证堆顶元素总是剩下元素的最大或最小的，从而可知，若在大量数据的文件中，只选取排序后的前几名，采用堆排序最合适。

5、判断下列序列是否为堆，若不是堆，则把它们调整为堆。

（1）100，85，95，75，80，60，82，40，20，10，65;

（2）100，95，85，82，80，75，65，60，40，20，10;

（3）100，85，40，75，80，60，65，95，82，10，20;

（4）10，20，40，60，65，75，80，82，85，95，100;

答：（1）100，85，95，75，80，60，82，40，20，10，65; 是堆。

（2）100，95，85，82，80，75，65，60，40，20，10; 是堆。

（3）100，85，40，75，80，60，65，95，82，10，20; 不是堆

调整以后的堆为：

100，95，65，85，80，60，40，75，82，10，20

（4）10，20，40，60，65，75，80，82，85，95，100; 是堆。

9.4 算法题

1、假设待排序序列以单链表的形式存储，头指针为head，编写选择排序算法。（作为上机实践题目）

#include <stdio.h>

struct Rtype

{

KeyType key; //关键字域

};

struct Lnode

{

Elemtype data ;

struct Lnode * next ;

} ;

void selectsort( Lnode *L)

{

Lnode *p,*q,*r;

Rtype temp;

for (p=L->next;p->next!=NULL;p=p->next)

{

q=p;

for (r=p->next;r!=NULL;r=r->next)

if (q->data>r->data) q=r ;

if (p!=q)

{ temp=p->data; p-.data=q->data; q->data=temp; }

}

}

2、试以L.e[L.len+1]这监视哨，改写直接插入排序算法。

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

数据结构(C语言版)习题及答案

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void insertsort(ListSq r, int n) //待排序元素r[1]～r[n]

{

int i, j;

for (i=n;i<=2;i--)

{

r.e[n+1]=r.e[i];

j=i+1;

while (r.e[n+1].key>r.e[j].key)

{

r.e[j-1]=r.e[j];

j++;

}

r.e[j+1]=r.e[n+1];

}

}

3、奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则将两者交换；第三趟对奇数i；第四趟对偶数i，依次类推，直到整个序列有序为止。试问：这种排序方法的结束条件是什么？编写相应的实现算法。（作为上机实践题目）

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void qiousort (ListSq r, int n)

{

int flag=1;

while(flag)

{

flag=0;

int i=1;

while(i<n)

{

if (r.e[i].key> r.e[i+1].key)

{

Rtype temp=r.e[i];

r.e[i]=r.e[i+1];

r.e[i+1]=temp;

flag=1;

数据结构(C语言版)习题及答案

}

i+=2;

}

i=2;

while(i<n)

{

if (r.e[i].key> r.e[i+1].key)

{

Rtype temp=r.e[i];

r.e[i]=r.e[i+1];

r.e[i+1]=temp;

flag=1;

}

i+=2;

}

}

}

4 、设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。（作为上机实践题目）

算法为：

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void dbubblesort(ListSq r, int n)

{

int i,j,flag;

Rtype temp;

flag=1;

i=0;

while(flag)

{

flag=0;

for(j=n-i;j<i;j--)

{

if (r.e[j].key<r.e[j-1].key)

{

flag=a; temp=r.e[j];

r.e[j]= r.e[j-1];

数据结构(C语言版)习题及答案

r.e[j-1]=temp;

}

}

for(j=i;j<n-1;j++)

{

if (r.e[j].key>r.e[j+1].key)

{

flag=a; temp=r.e[j];

r.e[j]= r.e[j+1];

r.e[j+1]=temp;

}

}

i++;

}

}

5、写出快速排序的非递归算法。

Struct Elemtype

{

int low;

int high;

};

struct Stack

{

Elemtype stack [StackMaxSize] ; //StackMaxSize 确定顺序栈的最大深度 int top ; // 栈顶指针

}；

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void quicksort(ListSq *r, int s,int t)

{

Stack x;

Elemtype y,z,q;

Rtype temp;

Initstack(x);

y.low=s;

y.high=t;

push(x,y);

while(!Empty(x))

{

pop(s,y);

数据结构(C语言版)习题及答案

i=y.low; j=y.high;

temp=r.e[i];

do

{

while (j>i && r.e[j].key>=temp.key) j--;

if (i<j) //条件成立时交换r[i]和r[j]的值

{

r.e[i]=r.e[j];

i++;

}

while (i<j && r.e[i].key<=temp.key) i++;

if (i<j)

{

r[j]=r[i];

j--;

}

} while(i==j);//条件成立时继续进行一次划分中的比较和交换 r[i]=temp;

if ((i+1)<y.high)

{

z.low=i+1;

z.high=y.high;

push(x,z);

}

if (y.low<(i-1))

{

q.low=y.low;

q.high=i-1;

push(x,q);

}

}

}

本文来源：https://www.bwwdw.com/article/7nli.html