数据结构课后习题八选择题总结

习题八

1. 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种方法称为(C

A. 归并排序 B.冒泡排序 C.插入排序 D.选择排序

2. 从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)末端的方法,称为(D

A. 归并排序 B.冒泡排序 C. 插入排序 D. 选择排序

3. n个不同的关键字由小到大进行冒泡排序,在下列(B)情况下比较次数最多。

A. 从小到大排列好 B.从大到小排列好 C.元素无序 D.元素基本有序

4. n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为(D

A. n+1 B.n   C.n-1  D.n(n-1)/2

5. 快速排序在下列(C)情况下最易发挥其长处。

A. 被排序的数据中含有多个相同排序码

B. 被排序的数据已基本有序

C. .被排序的数据完全无序

D. 被排序的数据中的最大值与最小值相差悬殊

6. n个关键字做出快速排序,在最坏的情况下,算法的时间复杂度为(A

A. O(n) B.O(n^2)  C.O(nlog2n)  D.O(n^3)

7. 若一组记录的排序码为(467956384084),利用快速排序的方法,以第一个记录为准的到的第一次划分结果是(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

8. 下列关键字序列中,(D)是堆

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

9. 堆是一种(B)排序

A.插入 B.选择  C交换  D.归并

 

10. 堆的形状是一棵(C

A.二叉排序树 B.满二叉树  C.完全二叉树  D.平衡二叉树

 

11. 若一组记录的排序码为(467956384084),则利用堆排序的方法建立的初始堆为(B

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

 

12. 下列几种排序方法中,要求内存最大的是(C

A.希尔排序 B.快速排序  C.归并排序  D.堆排序

 

13. 下列几种方法中,(C)是最稳定的排序方法。

A.希尔排序 B.快速排序  C.归并排序  D.堆排序

 

14. 数据表中有10000个元素,如果仅要求求出其最大的10个元素,则采用()算法最节省时间(D

A.冒泡排序 B.快速排序 C.简单选择排序  D.堆排序

 

15. 下列排序算法中,不能保证每趟排序至少能将一个元素放到其最终位置上的排序方法是(A

A..希尔排序 B.快速排序  C冒泡排序  D.堆排序

 

 

排序分类:

1. 插入类:将无序子序列中记录插入到有序序列中

直接插入、折半插入、希尔排序

2. 交换类:通过交换无序子序列中记录,得到最大或最小,并将它插入到有序子序列

冒泡排序、快速排序

3. 选择类:从无序子序列中选择关键字最大或最小,加入有序子序列

简单选择排序,树形选择排序,堆排序

4. 归并类:归并两个以上记录的有序子序列

2路归并

 

插入排序:

1. 直接插入排序

将每一条记录插入到已排序的有序表中(顺序查找要插入的位置)

Void InsertSort(SqList  &L){

For(i=2;i<=L.length;++i)

If(L.r[i].key判断当前位是否比前一位小

L.r[0]=L.r[i]; 小于,则把小的值放入0

L.r[i]=L.[i-1]; 把较大值位后移

For(j=i-2;L.r[0].key判断0位值是否小于其他已经排序值,西

L.r[j+1]=L.r[j]; 插入

L.r[j+1]=L.r[0]; 将较大值的低位赋较小值

}

}

时间复杂度:O(n^2)    空间复杂度O1

稳定,简便,适用于链式和顺序,基本有序或N值小时

2. 折半插入:

将每一条记录插入到已排序的有序表中(折半查找要插入的位置)

Void BInsertSort(SqList &L){

For(i=2;i<=L.length;++i){

L.r[0]=L.r[i];

Low=1;

High=i-1;

While(low<=high){

m=(low+high)/2;

If(L.r[0].key

Else low=m+1;

}

For(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];

L.r[high+1]=L.r[0];

 

}

}

时间复杂度:O(n^2)    空间复杂度O1

稳定,只适用顺序,适合无序,N较大时

3. 希尔排序

缩小增量排序,类似于减少记录个数,序列基本有序的直接插入排序

分组插入1.选取增量(选取间隔为多少的为一组)2.比较大小(各个组中直接插入排序)

531

空间复杂度为O1

记录跳跃式移动,不稳定,增量必须没有除1以外的公因子,最后一个必为1

适用于无序,N较大

 

 

交换排序:

1. 冒泡排序:

两两比较相邻记录的关键字,如果逆序就交换

每次只有两个关键字比较一次,最先排出最大值

稳定,可用于顺序和链式,适用于有序,N较小

 

2. 快速排序

在待排序记录中任取一个作为枢纽,

将两个指针i,j分别指向表的起始和最后的位置。

反复操作以下两步:

1)j逐渐减小,并逐次比较j指向的元素和目标元素的大小,若p(j)

2)i逐渐增大,并逐次比较i指向的元素和目标元素的大小,若p(i)>T则交换位置。

时间复杂度为Onlog2n)空间复杂度 最好:O(log2n) 最坏:On

 

选择排序:

1. 简单选择排序

每趟遍历最小关键字,找最小

时间复杂度On^2)空间复杂度O(1)

稳定,可链式,

 

2. 堆排序:一种树形选择排序,将待排序的记录看成是一棵完全二叉树的顺序存储结构。

每一个非终端结点都大于或小于其左右孩子的结点值

最大堆:由小到大  最小堆:由大到小

 

建初堆:按照无序序列建立完全二叉树,从n/2处进行堆调整

筛选法:把较小的关键字逐层筛下去,将较大关键字逐层选上来

堆排序:先建初堆,然后在大根堆基础上,反复交换堆顶元素和最后一个元素,最后得到有序序列

 

时间复杂度O(nlog2n) 空间复杂度O(1)

 

归并排序

2路归并:将两个或两个以上有序表合并成一个有序表

n个记录看成n个长度为1的子序列,重复进行两两归并,每次归并前都进行排序。

 

时间复杂度 O(nlog2n) 空间复杂度O(n)

习题八

1. 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种方法称为(C

A. 归并排序 B.冒泡排序 C.插入排序 D.选择排序

2. 从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)末端的方法,称为(D

A. 归并排序 B.冒泡排序 C. 插入排序 D. 选择排序

3. n个不同的关键字由小到大进行冒泡排序,在下列(B)情况下比较次数最多。

A. 从小到大排列好 B.从大到小排列好 C.元素无序 D.元素基本有序

4. n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为(D

A. n+1 B.n   C.n-1  D.n(n-1)/2

5. 快速排序在下列(C)情况下最易发挥其长处。

A. 被排序的数据中含有多个相同排序码

B. 被排序的数据已基本有序

C. .被排序的数据完全无序

D. 被排序的数据中的最大值与最小值相差悬殊

6. n个关键字做出快速排序,在最坏的情况下,算法的时间复杂度为(A

A. O(n) B.O(n^2)  C.O(nlog2n)  D.O(n^3)

7. 若一组记录的排序码为(467956384084),利用快速排序的方法,以第一个记录为准的到的第一次划分结果是(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

8. 下列关键字序列中,(D)是堆

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

9. 堆是一种(B)排序

A.插入 B.选择  C交换  D.归并

 

10. 堆的形状是一棵(C

A.二叉排序树 B.满二叉树  C.完全二叉树  D.平衡二叉树

 

11. 若一组记录的排序码为(467956384084),则利用堆排序的方法建立的初始堆为(B

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

 

12. 下列几种排序方法中,要求内存最大的是(C

A.希尔排序 B.快速排序  C.归并排序  D.堆排序

 

13. 下列几种方法中,(C)是最稳定的排序方法。

A.希尔排序 B.快速排序  C.归并排序  D.堆排序

 

14. 数据表中有10000个元素,如果仅要求求出其最大的10个元素,则采用()算法最节省时间(D

A.冒泡排序 B.快速排序 C.简单选择排序  D.堆排序

 

15. 下列排序算法中,不能保证每趟排序至少能将一个元素放到其最终位置上的排序方法是(A

A..希尔排序 B.快速排序  C冒泡排序  D.堆排序

 

 

排序分类:

1. 插入类:将无序子序列中记录插入到有序序列中

直接插入、折半插入、希尔排序

2. 交换类:通过交换无序子序列中记录,得到最大或最小,并将它插入到有序子序列

冒泡排序、快速排序

3. 选择类:从无序子序列中选择关键字最大或最小,加入有序子序列

简单选择排序,树形选择排序,堆排序

4. 归并类:归并两个以上记录的有序子序列

2路归并

 

插入排序:

1. 直接插入排序

将每一条记录插入到已排序的有序表中(顺序查找要插入的位置)

Void InsertSort(SqList  &L){

For(i=2;i<=L.length;++i)

If(L.r[i].key判断当前位是否比前一位小

L.r[0]=L.r[i]; 小于,则把小的值放入0

L.r[i]=L.[i-1]; 把较大值位后移

For(j=i-2;L.r[0].key判断0位值是否小于其他已经排序值,西

L.r[j+1]=L.r[j]; 插入

L.r[j+1]=L.r[0]; 将较大值的低位赋较小值

}

}

时间复杂度:O(n^2)    空间复杂度O1

稳定,简便,适用于链式和顺序,基本有序或N值小时

2. 折半插入:

将每一条记录插入到已排序的有序表中(折半查找要插入的位置)

Void BInsertSort(SqList &L){

For(i=2;i<=L.length;++i){

L.r[0]=L.r[i];

Low=1;

High=i-1;

While(low<=high){

m=(low+high)/2;

If(L.r[0].key

Else low=m+1;

}

For(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];

L.r[high+1]=L.r[0];

 

}

}

时间复杂度:O(n^2)    空间复杂度O1

稳定,只适用顺序,适合无序,N较大时

3. 希尔排序

缩小增量排序,类似于减少记录个数,序列基本有序的直接插入排序

分组插入1.选取增量(选取间隔为多少的为一组)2.比较大小(各个组中直接插入排序)

531

空间复杂度为O1

记录跳跃式移动,不稳定,增量必须没有除1以外的公因子,最后一个必为1

适用于无序,N较大

 

 

交换排序:

1. 冒泡排序:

两两比较相邻记录的关键字,如果逆序就交换

每次只有两个关键字比较一次,最先排出最大值

稳定,可用于顺序和链式,适用于有序,N较小

 

2. 快速排序

在待排序记录中任取一个作为枢纽,

将两个指针i,j分别指向表的起始和最后的位置。

反复操作以下两步:

1)j逐渐减小,并逐次比较j指向的元素和目标元素的大小,若p(j)

2)i逐渐增大,并逐次比较i指向的元素和目标元素的大小,若p(i)>T则交换位置。

时间复杂度为Onlog2n)空间复杂度 最好:O(log2n) 最坏:On

 

选择排序:

1. 简单选择排序

每趟遍历最小关键字,找最小

时间复杂度On^2)空间复杂度O(1)

稳定,可链式,

 

2. 堆排序:一种树形选择排序,将待排序的记录看成是一棵完全二叉树的顺序存储结构。

每一个非终端结点都大于或小于其左右孩子的结点值

最大堆:由小到大  最小堆:由大到小

 

建初堆:按照无序序列建立完全二叉树,从n/2处进行堆调整

筛选法:把较小的关键字逐层筛下去,将较大关键字逐层选上来

堆排序:先建初堆,然后在大根堆基础上,反复交换堆顶元素和最后一个元素,最后得到有序序列

 

时间复杂度O(nlog2n) 空间复杂度O(1)

 

归并排序

2路归并:将两个或两个以上有序表合并成一个有序表

n个记录看成n个长度为1的子序列,重复进行两两归并,每次归并前都进行排序。

 

时间复杂度 O(nlog2n) 空间复杂度O(n)

你可能感兴趣的