当前位置：首页 » 数据结构练习题 » 正文

数据结构-排序-练习题

3259 人参与 2018年09月10日 21:49 分类 : 数据结构练习题评论

1、选择题

(1)直接插入排序算法的时间复杂度为（）

A．O（N） B.O（1） C.O(N2) D.O(LOGN)

(2)下列排序方法中，从平均时间而言最佳的是（）

A．快速 B.希尔 C.基数 D.归并

(3)下列是稳定的排序方法的（）

A．快速 B.希尔 C.堆 D.基数

(4)所需辅助空间为O（N）的排序方法为（）

A．快速 B.希尔 C.基数 D.归并

(5)如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

A．起泡排序

B．快速排序

C．简单选择排序

D．堆排序

(6)下列选项中，（）需要的附加存储开销最大。

A．快速排序

B．堆排序

C．归并排序

D.插入排序

参考答案： (1） C (2） A (3） D (4）D (5）C (6)C

2、选择排序的基本思想是什么？给定初始关键字 [49 38 65 97 76 13 27 49]，请写出具体排序过程及程序实现。

基本思想：

①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
优点：稳定，比较次数与冒泡排序一样；
缺点：相对之下还是慢。

初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 76 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

参考代码如下：

#include <iostream>
using namespace std;
void main()
{
int i,j,k,t;
int R[8]={49,38,65,97,76,13,27,49};
for(i=0;i<7;i++)
{
k=i;
for(j=i+1;j<8;j++)
if(R[j]<R[k])
k=j;
if(k!=i)
{

t=R[j];R[j]=R[k];R[k]=t;

}
}
for(i=0;i<8;i++)
cout<<R<<endl;
}