（第20讲）关于排序的各种算法的汇总的题目
1、排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
稳定的排序算法有：冒泡、插入、归并
不稳定的有：选择、希尔、快排、堆排
2、一个递归必须包含：终止条件和递归部分
3、快排在什么情况下最弱：排有序序列，降成N的平方
一、选择题
1．某内排序方法的稳定性是指( )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法D．以上都不对
2．下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 堆积
3．下列排序算法中，其中（ ）是稳定的。
A. 堆排序，冒泡排序 B. 快速排序，堆排序
C. 直接选择排序，归并排序 D. 归并排序，冒泡排序
4．稳定的排序方法是（ ）
A．直接插入排序和快速排序 B．折半插入排序和起泡排序
C．简单选择排序和四路归并排序 D．树形选择排序和shell排序
5．下列排序方法中，哪一个是稳定的排序方法？（ ）
A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。
7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。
A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速 E．基数
9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序
10．下面的排序算法中，不稳定的是（ ）
A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。
11．下列内部排序算法中：
A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序
（1）其比较次数与序列初态无关的算法是（ ）
（2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（ ）
（4）排序的平均时间复杂度为O(n•logn)的算法是（ ）为O(n•n)的算法是（ ）
12．排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B. 选择 C. 冒泡 D. 快速
13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( )
A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法
14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。
A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序
15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。
A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序
16．比较次数与排序的初始状态无关的排序方法是( )。
A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序
17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。
A．选择排序 B.冒泡排序 C.插入排序 D.堆排序
18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 2584 47 （4） 15 21 25 47 84
则采用的排序是 ( )。
A. 选择 B. 冒泡 C. 快速 D. 插入
20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择 B. 快速 C. 希尔 D. 冒泡
21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。
A．选择 B. 堆 C. 直接插入 D. 冒泡
22．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序
23．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择 B. 冒泡 C. 归并 D. 堆
24．下列序列中，（ ）是执行第一趟快速排序后所得的序列。
A. [68，11，18，69] [23，93，73] B. [68，11，69，23] [18，93，73]
C. [93，73] [68，11，69，23，18] D. [68，11，69，23，18] [93，73]
25．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。
A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
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)
27. 在下面的排序方法中，辅助空间为O（n）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序
28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
A．冒泡 B. 希尔 C. 快速 D. 堆
29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序
30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的是（ ）算法。
A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序
31. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡 B. 希尔插入 C. 交换 D. 快速
32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序
答案：
|
1.D |
2.D |
3.D |
4.B |
5.B |
6.B |
7.C,E |
8.A |
9.C |
10.C,D,F |
11.1D,C 11.2A,D,F |
|||
|
11.3B 11.4(A,C,F)(B,D,E) |
12.C,D |
13.A |
14.B,D |
15.D |
16.D |
17.C |
18.A |
19.A |
20.C |
21.C |
|||
|
22.B |
23.C |
24.C |
25.A |
26.C |
27.D |
28.C |
29.B |
30.C,B |
31.D |
32.D |
|||
部分答案解释如下：
18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。
20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。
49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。
64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。
二、判断题：
1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ）
2．内排序要求数据一定要以顺序方式存储。 （ ）
3．排序算法中的比较次数与初始元素序列的排列无关。（）
4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（）
7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）
8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ ）
9．在待排数据基本有序的情况下，快速排序效果最好。（ ）
10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ ）
11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ）
12．堆肯定是一棵平衡二叉树。（ ）
13．堆是满二叉树。（ ）【
14．（101，88，46，70，34，39，45，58，66，10）是堆。（）
15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
16．堆排序是稳定的排序方法。（ ）
17．归并排序辅助存储为O（1）。（ ）
18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）
19．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ ）
20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n），（ ）而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。
21．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ）
22．在任何情况下，归并排序都比简单插入排序快。（ ）
23．归并排序在任何情况下都比所有简单排序速度快。（ ）
24．快速排序总比简单排序快。（ ）
25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ ）
三、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。
2. 外排序的基本操作过程是_______和_______。
3. 属于不稳定排序的有__________。
4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。
5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。
6．直接插入排序用监视哨的作用是_______。
7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。
8. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。
selectsort(head)
p=head;
while(p(1)_______)
{q=p;r=(2)_______
while((3)______ )
{if ((4)_______) q=r;
r=(5)_______ ;
}
tmp=q->data; q->data=p->data; p->data=tmp;p= (6)_______ ;
}
9．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：
#include<stdio.h>
typedef structnode {char data; struct node *link; }node;
node*select(node *head)
{node*p,*q,*r,*s;
p=(node*)malloc(sizeof(node));
p->link=head; head=p;
while(p->link!=null)
{q=p->link; r=p;
while ((1)____)
{ if (q->link->data<r->link->data) r=q;
q=q->link;
}
if ((2)____) {s=r->link; r->link=s->link; s->link= ((3)_____);((4)_____);}
((5)____) ;
}
p=head;head=head->link; free(p); return(head);
}
10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。
void sort(SqList&r,int n) {
i=1;
while((1)__) {
min=max=1;
for(j=i+1;(2)____ ;++j)
{if((3)____)min=j; else if(r[j].key>r[max].key) max=j; }
if((4)_____)r[min] < ---- >r[j];
if(max!=n-i+1){if((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); }
i++;
}
}//sort
习题答案
二、判断题
|
1.√ |
2.× |
3.× |
4.× |
5.× |
6.× |
7.× |
8.× |
9.× |
10.× |
11.× |
12.× |
13.× |
|
14.√ |
15.√ |
16.× |
17.× |
18.× |
19.× |
20.× |
21.× |
22.× |
23.× |
24.× |
25.√ |
|
部分答案解释如下：
5. 错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。 12. 错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
22. 错误。待排序序列为正序时，简单插入排序比归并排序快。
三、填空题
1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速排序、堆排序等
4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时）
6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7.n(n-1)/2
8.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data<q->data(5)r->next (6)p->next
9. 题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。
(1)q->link!=NULL(2)r!=p (3)p->link(4)p->link=s (5)p=p->link
10.(1)i<n-i+1(2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i(6)r[max]<-->r[n-i+1]
1、以下关于运算符优先顺序的描述中正确的是______。（）D
A、关系运算符＜算术运算符＜赋值运算符＜逻辑与运算符
B、逻辑与运算符＜关系运算符＜算术运算符＜赋值运算符
C、算术运算符＜关系运算符＜赋值运算符＜逻辑与运算符
D、赋值运算符＜逻辑与运算符＜关系运算符＜算术运算符
2、C语言规定，简单变量做实参时，它和对应形参之间的数据传递方式是 B
C语言规定,数组名做实参时,它和对应形参之间的数据传递方式是 A
A. 地址传递B.单向的值传递C.由实参传给形参，再由形参传回给实参D.由用户指定传递方式
形参：函数定义中的参数
实参：函数调用时的参数
参数传送只有两种传递方式：
值传递，又称单向传递，只能把实参数值传给形参，形参最后的结果不影响实参（形参改变大小，实参大小不变）
地址传递，通过指针，把实参的地址给形参，形参的大小可以影响实参
3、2048游戏理想情况下最大值：131072 最小值：4
因为假设四格，第一个2，第二个4，第三个8，第四个16，这样最大是2的四次方，但如果第一个是4（因为游戏随机出现的可能会是4），这样最大的就是2的五次方，同理。
1、下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（）
A、插入排序 B、堆排序 C、冒泡排序 D、快速排序
2、以下关于Cache的叙述中，正确的是（）
A、CPU中的Cache容量应大于CPU之外的Cache容量
B、Cache的设计思想是在合理成本下提高命中率
C、Cache的设计目标是容量尽可能与主存容量相等
D、在容量确定的情况下，替换算法的时间复杂度是影响Cache命中率的关键因素
3、数据存储在磁盘上的排列方式会影响I/O服务的性能，一个圆环的磁道上有10个物理块，10个数据记录R1------R10存放在这个磁道上，记录的安排顺序如下表所示：
|
物理块 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
逻辑记录 |
R1 |
R2 |
R3 |
R4 |
R5 |
R6 |
R7 |
R8 |
R9 |
R10 |
假设磁盘的旋转速度为20ms/周，磁盘当前处在R1的开头处，若系统顺序扫描后将数据放入单缓冲区内，处理数据的时间为4ms（然后再读取下个记录），则处理这10个记录的最长时间为（）
A、180ms B、200ms C、204ms D、220ms
4、随着IP网络的发展，为了节省可分配的注册IP地址，有一些地址被拿出来用于私有IP地址，以下不属于私有IP地址范围的是（）
A、10.6.207.84 B、172.23.30.28 C、172.32.50.80 D、192.168.1.100
5、下列关于一个类的静态成员的描述中，不正确的是（）
A、该类的对象共享其静态成员变量的值 B、静态成员变量可被该类的所有方法访问
C、该类的静态方法只能访问该类的静态成员变量 D、该类的静态数据成员变量的值不可修改
6、已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）
A、1.5 B、1.7 C、2.0 D、2.3
7、表达式“X=A+B*（C--D）/E”的后缀表示形式可以为（）
A、XAB+CDE/-*= B、XA+BC-DE/*= C、XABCD-*E/+= D、XABCDE+*/=
8、（）设计模式将抽象部分与它的实现部分相分离。
A、Singleton（单例） B、 Bridge（桥接）
C、 Composite（组合） D、 Facade（外观）
9、下面程序的输出结果为多少？
void Func(charstr_arg[100])
{
printf("%d ",sizeof(str_arg));
}
intmain(void)
{
char str[]="Hello";
printf("%d ",sizeof(str));
printf("%d ",strlen(str));
char *p = str;
printf("%d ",sizeof(p));
Func(str);
}
10、C++将父类的析构函数定义为虚函数，下列正确的是哪个？
A、释放父类指针时能正确释放子类对象
B、释放子类指针时能正确释放父类对象
C、这样做是错误的
D、以上全错
11、下列哪一个不属于关系数据库的特点？
A、数据冗余度小
B、数据独立性高
C、数据共享性好
D、多用户访问
12、下面程序的输出结果为多少？
void Func(charstr_arg[2])
{
int m = sizeof(str_arg);
int n = strlen(str_arg);
printf("%d ",m);
printf("%d ",n);
}
intmain(void)
{
char str[]="Hello";
Func(str);
}
13、typedef char *String_t; 和 #define String_d char * 这两句在使用上有什么区别？
14、到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？
15、题目：已知rand7() 可以产生 1~7 的7个数（均匀概率），利用rand7() 产生rand10() 1~10（均匀概率）
16、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。
17、对一个正整数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到1时操作停止，求经过9次操作变为1的数有多少个？
算法编程题：
1、 给定一个字符串，求出其最长的重复子串。
参考答案
1. B。若序列事先已经基本有序，则插入法和冒泡法会明显减少比较次数，快速排序法与主元的选择有关，若一般选子序列左侧第一个元素比较，则第一个元素最好是大小居中的，以使得分成的两个子数组长度大致相等，性能才能最佳，所以快速排序也与初始输入集有关的。堆排序受数据集输入顺序影响最小。
2. B。Cache（高速缓冲器）容量小于主存，但速度快于主存，慢于CPU，相当于CPU和主存间的一个缓冲器，Cache中存放最近使用过的内存内容（基于最近使用过的内容很可能被再次使用的原理）。若CPU寻访的内容在Cache中存放，则优先从Cache中读取，称为命中，否则称为脱靶，脱靶只能从主存中读取内容了。当Cache存储满的时候，用替换算法清理掉不用的内容，保留下最新或最常使用的内容，称为替换。Cache设计目标是提高命中率。替换算法确实是影响Cache命中率，但还有Cache容量、存储单元大小、组数多少、地址比较方法、写操作方法等都会影响Cache命中率。
3. C。这道题终于会做了。是这样的原理，磁盘会一直朝某个方向旋转，不会因为处理数据而停止。本题要求顺序处理R1到R10，起始位置在R1，一周是20ms，共10个记录，所以每个记录的读取时间为2ms。首先读R1并处理R1，读R1花2ms，读好后磁盘处于R1的末尾或R2的开头，此时处理R1，需要4ms，因为磁盘一直旋转，所以R1处理好了后磁盘已经转到R4的开始了，这时花的时间为2+4=6ms。这时候要处理R2，需要等待磁盘从R5一直转到R2的开始才行，磁盘转动不可反向，所以要经过8*2ms才能转到R1的末尾，读取R2需要2ms，再处理R2需要4ms，处理结束后磁盘已经转到R5的开头了，这时花的时间为2*8+2+4=22ms。等待磁盘再转到R3又要8*2ms，加上R3自身2ms的读取时间和4ms的处理时间，花的时间也为22ms，此时磁盘已经转到R6的开头了，写到这里，大家已经可以看到规律了，读取并处理后序记录都为22ms，所以总时间为6+22*9=204ms。
4. C。见实习生笔试里的解释。
5. D。静态成员只要不是const的，每个对象都对其进行可以修改，但注意静态成员只有一份，修改后所有对象再访问的时候，都是最近修改后的数值了。
6. C。解释如下，先分别求这六个数的余7后的结果，分别为3,4,4,0,3,6。列出一个表格，如下所示：
|
位置 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
记录 |
63 |
48 |
|
38 |
25 |
74 |
52 |
|
查找次数 |
1 |
3 |
|
1 |
1 |
2 |
4 |
38的余数是3，所以放在3号位置对应的记录里，25放在位置4，74求余的结果也是4，这就出现冲突了，线性探测就是往后移一格再存，所以放在5号位置了，按照这个方法依次放置到相应的位置。查找时，比如此时查找52，余数是3，本应位于3号位置，但3号位置被38占了，所以继续向后查找，4号位置没有，5号位置也没有，6号位置才查到，所以查找次数就是4次了。平均查找长度就是各数查找次数之和/6。
7. C。后缀形式，复习一下，其实不难的，注意运算优先级，”＝”应是最后做的。
8. B。看看设计模式的书。
9. 6,5,4,4。第一个是求数组的大小，不要忘了’ ’，第二个是求字符串长度，注意strlen返回的长度是不包括’ ’的，指针的sizeof都是4字节（32位系统）。函数中形参虽是数组的形式，但实际传入的是指针（数组首地址），所以后面[100]其实没有用，还是4字节。
10. A。虚析构函数，C++多态。
11. D。
12. 4,5。同第9题解释，函数中的[2]其实是没有用的，因为只传数组首地址，就是指针，所以sizeof(指针)=4（32位系统），求strlen时是遇’ ’停止计数的，且不包括’ ’，所以是5。
13. 前者声明一个类型的别名，在编译时处理，有类型检查；后者是一个简单的替换，在预编译时处理，无类型检查。从使用上来说，String_t a,b; a和b都是char* 类型的，但String_d a,b; 只有a是char*类型的，b是char型的。
14. 需要自己去完善条件。比如优惠券本次消费是否就可以使用，还是要等到下次消费才可用，优惠券在消费多少时才可以使用等。举个简单的例子，比如只能下次消费使用，且满200才可以使用其中的50元优惠券，这样实际折扣为（200+200-50）/400＝8.9折，继续买下去，折扣可以在8折左右。
15.如下：
1int rand10()
2 {
3int temp;
4int temp2;
5do
6 {
7 temp = rand7();
8 } while (temp > 5);//temp 1到5
9do
10 {
11 temp2 = rand7();
12while (temp2 > 2);//temp2 1到2
13return temp + (temp2 - 1) * 5;
14 }
16. 解法同15。
17. 最后一个必是2/2＝1，前一个也必是4/2＝2，再往前可以自己推几个，可以发现从9th到5th间隔内的分叉数依次是0,1,1,2,3,5，每次分叉就会多出一个可能的数，找规律可以推测是Fabbonaci数列，所以结果应该1+1+2+3+5+8+13＝33，别忘了即使是0分叉也包含了自身一个数，所以最终结果是34。
|
排序法 |
最差时间分析 |
平均时间复杂度 |
稳定度 |
空间复杂度 |
|
冒泡排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
|
快速排序 |
O(n2) |
O(n*log2n) |
不稳定 |
O(log2n)~O(n) |
|
选择排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
|
二叉树排序 |
O(n2) |
O(n*log2n) |
不一顶 |
O(n) |
|
插入排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
|
堆排序 |
O(n*log2n) |
O(n*log2n) |
不稳定 |
O(1) |
|
希尔排序 |
O |
O |
不稳定 |
O(1) |
一、单选题
12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。
A．冒泡排序 B．快速排序 C．堆排序 D．归并排序
1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( )
A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k)
2．最好和最坏时间复杂度均为O( )且稳定的排序方法是( )。
A．快速排序 B．堆排序 C．归并排序 D．基数排序
3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。
A．起泡排序 B．希尔排序 C．堆排序 D．快速排序
4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（ ）
A．快速排序 B．堆排序 C．归并排序 D．直接插入排序
5．排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B．选择 C．希尔 D．快速
6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是( )。
A．堆排序 B．直接插入排序 C．快速排序 D．直接选择排序
7．关键字比较次数与数据的初始状态无关的排序算法是( )。
A．直接选择排序 B．冒泡排序 C．直接插入排序 D．希尔排序
8. 若一个元素序列基本有序，则选用（ ）方法较快。
A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序
9. 若要从1000个元素中得到4个最小值元素，最好采用（ ）方法。
A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序
10. 若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法。
A．直接插入排序 B．归并排序 C．堆排序 D．快速排序
11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（ ）方法。
A．直接插入排序 B．归并排序 C．堆排序 D．快速排序
12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（ ）。
A．直接选择排序 B．归并排序 C．堆排序 D．快速排序
13. 在平均情况下速度最快的排序方法为（ ）。
A．直接选择排序 B．归并排序 C．堆排序 D．快速排序
14、设有关键字初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，则用下列哪种排序方法进行第一趟扫描的结果为{F,H,C,D,P,A,M,Q,R,S,Y,X}？
A．直接插入排序 B．二路归并排序
C．以第一元素为基准的快速排序 D．基数排序
15．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A．插入 B．选择 C．希尔 D．二路归并
16．下面排序法中，( )排序法是不稳定的。
A．插入 B．冒泡 C．二路归并 D．堆
17.下列排序方法中，不稳定的是（ ）
A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序
18. 在直接插入排序的第i趟排序前，有序表中的元素个数为（ ）。
A．i B．i+1 C．i-1 D．1
19. 在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元素作监视哨。
A．i B．i-1 C．i+1 D．1
20. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）。
A．j-i B．i-j-1 C．i-j D．i-j+1
21. 对n个元素进行直接插入排序，则各趟排序中寻找插入位置的平均时间复杂性为（ ）。
A．O(1) B．O(n) C．O(n2) D．O(log2n)
22. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。
A．n B．n+1 C．n-1 D．2n
23. 对n个元素进行直接插入排序时间复杂性为（ ）。
A．O(1) B．O(n) C．O(n2) D．O(log2n)
24、n个记录直接插入排序时所需的记录最小比较次数是( )
A．n-1 B．n C．n(n-1)/2 D．n(n+1)/2
25. 对n个元素进行直接插入排序，空间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
26. 对n个元素进行冒泡排序，第一趟至多需要进行（ ）对相邻元素之间的交换。
A．n B．n-1 C．n+1 D．n/2
27. 对n个元素进行冒泡排序，最好情况下的时间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(n)
28. 对n个元素进行冒泡排序，至少需要（ ）趟完成。
A．1 B．n C．n-1 D．n/2
6．快速排序的记录移动次数（ ）比较次数，其总执行时间为0（nlog2n）。
A）大于 B）大于等于 C）小于等于 D）小于
29. 对n个元素进行快速排序，第一次划分最多需要移动（ ）次元素，假定包括基准和临时量之间的移动。
A．n/2 B．n-1 C．n D．n+1
30.对序列（3, 7, 5, 9, 1）进行快速排序，则第一次划分时需要移动元素的次数为（ ），假定不包括基准和临时量之间的移动。
A．1 B．2 C．3 D．4
31. 对n个元素进行快速排序，最好情况下需要进行（ ）趟。
A．n B．n/2 C．log2n D．2n
32. 对n个元素进行快速排序，最坏情况下需要进行（ ）趟。
A．n B．n-1 C．n/2 D．log2n
33. 对n个元素进行快速排序，平均情况下的时间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
34. 对n个元素进行快速排序，最坏情况下的时间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
35. 对n个元素进行快速排序，平均情况下的空间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
36. 对n个元素进行快速排序，最坏情况下的空间复杂性为（ ）。
A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)
37. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。
A．1, 3, 5, 7, 9 B． 9, 7, 5, 3,
