当前位置：文档库 › 排序习题

排序习题

8.13 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。

8.14 以单链表作为存储结构实现直接插入排序算法。

8.15 设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。

*8.16 写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。

8.17 下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。

void BubbleSort(int A[],int n)

//不妨设A[0..n-1]是整型向量

int lastExchange,j,i=n-1;

while (i>0)

lastExchange=0;

for(j=0;j

if(A[j+1]

交换A[j]和A[j+1];

lastExchange=j;

}

i=lastExchange;//将i置为最后交换的位置

}//endwhile

}//BubbleSort

8.18 改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。

8.19 对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。

8.20`以单链表为存储结构，写一个直接选择排序算法。

8.21 写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。

8.22 写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。

8.23 写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。

8.24 已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。

8.25 设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在0到n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B[0..n-1]中。

*8.26 写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。

例题1、

下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（B）

A、二分插入排序

B、堆排序

C、冒泡排序

D、快速排序

例题2、

写出下列算法的时间复杂度。

(1)冒泡排序；(2)选择排序；(3)插入排序；(4)二分插入排序；(5)快速排序；(6)堆排序；(7)归并排序

例题1、

写出希尔排序算法程序，并说明最坏的情况下需要进行多少次的比较和交换。

程序略，需要O(n^2)次的比较

例题2、

设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是H, C, Q, P, A, M, S, R, D, F, X ,Y；

初始步长为4的希尔（shell）排序一趟的结果是P, A, C, S, Q, D, F, X , R, H,M, Y ；

二路归并排序一趟扫描的结果是H, Q, C, Y，A, P, M, S, D, R, F, X；

快速排序一趟扫描的结果是F, H, C, D, P, A, M, Q, R, S, Y，X；

堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y，P, H, X。

例题1、

在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）；若初始数据基本反序，则选用选择排序。

例题2、

下述几种排序方法中，平均查找长度（ASL）最小的是

Ａ. 插入排序Ｂ.快速排序Ｃ. 归并排序Ｄ. 选择排序

例题1、

对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序，它们的比较次数和交换次数各是多少？

答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次。

例题2、

把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间。

事实上，这道题放到冒泡排序这里不知道是不是特别合适，只是有一种解法是类似冒泡的思想，如下解法一

解法一、

每次遇到大写字母就往后冒，最后结果即为所求

[cpp]view plaincopy

1.#include

2.#include

3.//题目以及要求：把一个字符串的大写字母放到字符串的后面，

4.//各个字符的相对位置不变，不能申请额外的空间。

5.//判断是不是大写字母

6.int isUpperAlpha(char c){

7.if(c >= 'A' && c <= 'Z'){

8.return 1;

9.}

10.return 0;

11.}

12.//交换两个字母

13.void swap(char *a, char *b){

14.char temp = *a;

15.*a = *b;

16.*b = temp;

17.}

18.char * mySort(char *arr, int len){

19.if(arr == NULL || len <= 0){

20.return NULL;

21.}

22.int i = 0, j = 0, k = 0;

23.for(i = 0; i < len; i++){

24.for(j = len - 1 - i; j >= 0; j--){

25.if(isUpperAlpha(arr[j])){

26.for(k = j; k < len - i - 1; k++){

27.swap(&arr[k], &arr[k + 1]);

28.}

29.break;

30.}

31.//遍历完了字符数组，但是没发现大写字母，所以没必要再遍历下去

32.if(j == 0 && !isUpperAlpha(arr[j])){

33.//结束;

34.return arr;

35.}

36.}

37.}

38.//over:

39.return arr;

40.}

41.int main(){

42.char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";

43.printf("%s\n", mySort(arr, strlen(arr)));

44.return 0;

45.}

解法二。

步骤如下

1、两个指针p1和p2，从后往前扫描

2、p1遇到一个小写字母时停下，p2遇到大写字母时停下，两者所指向的char交换

3、p1，p2同时往前一格

代码如下：

[cpp]view plaincopy

1.#include

2.#include

3.//判断是不是大写字母

4.int isUpperAlpha(char c){

5.if(c >= 'A' && c <= 'Z'){

6.return 1;

7.}

8.return 0;

9.}

10.//交换两个字母

11.void swap(char *a, char *b){

12.char temp = *a;

13.*a = *b;

14.*b = temp;

15.}

16.char * Reorder(char *arr, int len){

17.if(arr == NULL || len <= 0){

18.return NULL;

19.}

20.int *p1 = arr;

21.int *p2 = arr;

22.While(p1

23.While( isUpperAlpha(*p1) ){

24.P1++;

25.}

26.While( !isUpperAlpha(*p2) ){

27.P2++;

28.}

29.swap(p1, p2)

30.}

31.//结束

32.return arr;

33.}

34.int main(){

35.char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";

36.printf("%s\n", Reorder(arr, strlen(arr)));

37.return 0;

例题1、

最小的k个数，输入n个整数，找出其中最下的k个数，例如输入4、5、1、6、2、7、3、8、1、2，输出最下的4个数，则输出1、1、2、2。

当然，博主也知道这题可以建大小为k的大顶堆，然后用堆的方法解决。

但是这个题目可也以仿照快速排序，运用partition函数进行求解，不过我们完整的

快速排序分割后要递归地对前后两段继续进行分割，而这里我们需要做的是判定分割的位置，然后再确定对前段还是后段进行分割，所以只对单侧分割即可。代码如下：

[cpp]view plaincopy

1.void GetLeastNumbers_by_partition(int* input, int n, int* output, int k)

2.{

3.if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)

4.return;

5.int start = 0;

6.int end = n - 1;

7.int index = Partition(input, n, start, end);

8.while(index != k - 1)

9. {

10.if(index > k - 1)

11. {

12. end = index - 1;

13. index = Partition(input, n, start, end);

14. }

15.else

16. {

17. start = index + 1;

18. index = Partition(input, n, start, end);

19. }

20. }

21.for(int i = 0; i < k; ++i)

22. output[i] = input[i];

23.}

例题2、

判断数组中出现超过一半的数字

当然，这道题很多人都见过，而且最通用的一种解法是数对对消的思路。这里只是再给大家提供一种思路，快排partition的方法在很多地方都能使用，比如这题。我们也可以选择合适的判定条件进行递归。代码如下：

[cpp]view plaincopy

1.bool g_bInputInvalid = false;

2.bool CheckInvalidArray(int* numbers, int length)

3.{

4. g_bInputInvalid = false;

5.if(numbers == NULL && length <= 0)

6. g_bInputInvalid = true;

7.return g_bInputInvalid;

8.}

9.bool CheckMoreThanHalf(int* numbers, int length, int number)

10.{

11.int times = 0;

12.for(int i = 0; i < length; ++i)

13. {

14.if(numbers[i] == number)

15. times++;

16. }

17.bool isMoreThanHalf = true;

18.if(times * 2 <= length)

19. {

20. g_bInputInvalid = true;

21. isMoreThanHalf = false;

22. }

23.return isMoreThanHalf;

24.}

25.int MoreThanHalfNum_Solution1(int* numbers, int length)

26.{

27.if(CheckInvalidArray(numbers, length))

28.return 0;

29.int middle = length >> 1;

30.int start = 0;

31.int end = length - 1;

32.int index = Partition(numbers, length, start, end);

33.while(index != middle)

34. {

35.if(index > middle)

36. {

37. end = index - 1;

38. index = Partition(numbers, length, start, end);

39. }

40.else

41. {

42. start = index + 1;

43. index = Partition(numbers, length, start, end);

44. }

45. }

46.int result = numbers[middle];

47.if(!CheckMoreThanHalf(numbers, length, result))

48. result = 0;

49.return result;

50.}

例题3、

有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面(不要求保持原顺序)

这题可能大家都能想到的方法是：设置首尾两个指针，首指针向后移动寻找大写字母，尾指针向前移动需找小写字母，找到后都停下，交换。之后继续移动，直至相遇。这种方法在这里我就不做讨论写代码了。

但是这题也可以采用类似快排的partition。这里使用从左往后扫描的方式。字符串在调整的过程中可以分成两个部分：已排好的小写字母部分、待调整的剩余部分。用两个指针i和j，其中i指向待调整的剩余部分的第一个元素，用j指针遍历待调整的部分。当j指向一个小写字母时，交换i和j所指的元素。向前移动i、j，直到字符串末尾。代码如下：[cpp]view plaincopy

1.#include

https://www.wendangku.net/doc/9a9649368.html,ing namespace std;

3.void Proc( char *str )

4.{

5.int i = 0;

6.int j = 0;

7.//移动指针i, 使其指向第一个大写字母

8.while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;

9.if( str[i] != '\0' )

10.{

11.//指针j遍历未处理的部分，找到第一个小写字母

12.for( j=i; str[j] != '\0'; j++ )

13.{

14.if( str[j] >= 'a' && str[j] <= 'z' )

15.{

16.char tmp = str[i];

17.str[i] = str[j];

18.str[j] = tmp;

19.i++;

20.}

21.}

22.}

23.}

24.int main()

25.{

26.char data[] = "SONGjianGoodBest";

27.Proc( data );

28.return 0;

29.}

30.例题1、

31.编写算法，从10亿个浮点数当中，选出其中最大的10000个。

32.典型的Top K问题，用堆是最典型的思路。建10000个数的小顶堆，然后将10亿

个数依次读取，大于堆顶，则替换堆顶，做一次堆调整。结束之后，小顶堆中存放的数即为所求。代码如下(为了方便，这里直接使用了STL容器)：

33.例题1、

34.题目输入一个数组，数组元素的大小在0->999.999.999的范围内，元素个数为

0-500000范围。题目要求通过相邻的元素的交换，使得输入的数组变为有序，要求输出交换的次数

35.这题求解的其实就是一个逆序对。我们回想一下归并排序的过程：

36.归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

37.分解：将n个元素分成个含n/2个元素的子序列。

38.解决：用合并排序法对两个子序列递归的排序。

39.合并：合并两个已排序的子序列已得到排序结果。

40.在归并排序算法中稍作修改，就可以在n log n的时间内求逆序对。

41.将数组A[1...size]，划分为A[1...mid] 和A[mid+1...size].那么逆序对数的个数

为f(1, size) = f(1, mid) + f(mid+1, size) + s(1, mid, size)，这里s(1, mid, size)代表左值在[1---mid]中，右值在[mid+1, size]中的逆序对数。由于两个子序列本身都已经排序，所以查找起来非常方便。

42.代码如下：

例题2、

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query 都可能重复。要求你按照query的频度排序。

1、hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

2、hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。

3、堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序。将排序好的query 和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。对这10个文件进行归并排序（内排序与外排序相结合）。

例题3、

归并一个左右两边分别排好序的数组，空间复杂度要求O(1)。

使用原地归并，能够让归并排序的空间复杂度降为O(1)，但是速度上会有一定程度的下降。代码如下：

例题1、

一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。

对500W数据排序，如果基于比较的先进排序，平均比较次数为

O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条

件：100=

创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。

实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从

0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。

例题2、

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可（内存限制为2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。

分析：既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。

思想：将整型的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。按以下步骤实施：

1、把10G整数每2G读入一次内存，然后一次遍历这536,870,912即（1024*1024*1024）*2 /4个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可。

2、继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。

3、一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

例题3、

给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值M,要求设计线性的时间算法

典型的最大间隙问题。

要求线性时间算法。需要使用桶排序。桶排序的平均时间复发度是O(N).如果桶排序的数据分布不均匀，假设都分配到同一个桶中，最坏情况下的时间复杂度将变为O(N^2).

桶排序: 最关键的建桶，如果桶设计得不好的话桶排序是几乎没有作用的。通常情况下，上下界有两种取法，第一种是取一个10^n或者是2^n的数，方便实现。另一种是取数列的最大值和最小值然后均分作桶。

对于这个题，最关键的一步是：由抽屉原理知：最大差值

M>= (Max(V[n])-Min(V[n]))/(n-1)！所以，假如以(Max(V[n])-Min(V[n]))/(n-1)为桶宽的话，答案一定不是属于同一个桶的两元素之差。因此，这样建桶，每次只保留桶里面的最大值和最小值即可。

代码如下：

例题1、

某地区年龄排序问题

够典型的计数排序吧，年龄的区间也就那么大

总结

总结一下各种排序算法如下

行测事件排序题库

事件排序每道题给出五个事件，每个事件是以简短语句表述的，接着给出表示事件的四种假定发生顺序的四个数字序列，请你选择其中最合乎逻辑的一种事件顺序。【例题】（1）收集书籍（2）购买材料（3）打造书架（4）雇用木工（5）排列书籍 A.4—3—1—2—5 B.1—4—2—3—5 C.4—3—2—1—5 D.3—2—1—4—5 【解答】此题正确答案为B。收集书籍（1）——雇用木工（4）——购买材料（2）——打造书架（3）——排列书籍（5），这一顺序相对于其他顺序而言最为合理。 2005年国家一卷 71. （1）考古挖掘（2）绘制壁画（3）建造陵墓（4）拼接图案（5）盗墓取宝 A.3—5—1—2—4 B.3—2—5—1—4 C.2—3—4—5—1 D.2—3—5—1—4 72.（1）救治无效，家属告状（2）身患重病，借款购药（3）企业胜诉，报社致歉（4）药品鉴定，真伪不同（5）记者撰文，药厂蒙冤 A.2—4—1—5—3 B.5—2—4—1—3 C.2—1—5—4—3 D.5—4—2—1—3 73. （1）绿叶葱葱，森林茂密（2）厂房林立，马达轰鸣（3）钻机飞转，原油滚滚（4）燃气发电，远程送电（5）阳光明媚，百花齐放 A.3—4—5—1—2 B.5—4—1—2—3 C.1—2—3—4—5 D.5—1—3—4—2 74. （1）融入异族自谋出路（2）一支残部向西突围（3）跨过界河向北征战（4）战火熄灭回国通商（5）青年男子被征入伍 A.3—5—2—1—4 B.3—2—1—4—5 C.5—2—3—4—1 D.5—3—2—1—4 75. （1）嫌疑人聚焦在印刷厂一名职工身上（2）死者所穿衣服完好无损（3）工作服前襟上有一块补丁（4）检测碎布片中有油墨成分（5）现场拾到一块衣服碎片 A.2—5—1—4—3 B.2—5—4—3—1 C.5—2—4—1—3 D.5—2—3—4—1 76. （1）大量有机物积聚（2）形成石油（3）复杂的化学变化（4）剧烈地质变化（5）古浮游生物残骸沉积海底 A.1—5—3—4—2 B.5—4—1—2—3 C.3—1—2—5—4 D.5—1—4—3—2 77. （1）诸葛亮显示出卓越的军事才华（2）三顾茅庐（3）刘备拜诸葛亮为军师（4）赤壁之战大败曹军（5）提出三分天下战略 A.1—4—5—2—3 B.5—4—3—2—1 C.2—5—3—4—1 D.1—2—3—4—5 78. （1）商品经济出现（2）资本主义生产方式产生（3）生产力发展（4）资本原始积累（5）社会分工扩大 A.1—5—3—4—2 B.3—4—2—5—1 C.3—5—1—4—2 D.1—2—3—5—4 79. （1）生命单体（2）原始水生物（3）生物大分子（4）简单有机物（5）地球生物圈

小学句子排序方法及习题附答案

小学句子排序方法及习题怎样排列顺序错乱的句子？把排列错乱的句子整理成一段通顺连贯的话，能训练对句子的理解能力、有条理表达能力和构段能力。这样的练习一般可按五步进行。第一步，仔细阅读每句话或每组句子，理解它们的主要内容; 第二步，综合各句的意思，想想这些话主要说的是什么内容; 第三步，想想全段的内容按什么顺序排列好，即找出排列顺序的依据，如，是按事情发展顺序，还是时间顺序，或方位，还是“总分”等; 第四步，按确定的排列依据排列顺序; 第五步，按排好的顺序仔细读两遍，看排得对不对，如发现有的句子排得位置不对，就进行调整，直到这段话排得通顺连贯为止。把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。

那么，如何学会排列好句子呢?我们可以按下列方法进行。一、按事情发展的顺序排列。有些错乱的句子，我们在排列时，应仔细分析句与句之间的联系。常见的错乱句子，往往叙述了一件完整的事，或者活动的具体过程。那么，我们就可以按事情发展的顺序来排列。二、按时间先后顺序排列。对一些错乱的句子，我们可以找出表示时间概念的词语，如，早晨、上午、中午、下午等词，然后按时间先后顺序进行排列句子。三、按先总述后分述的顺序排列。根据这段话的特点，找出这句话是个中心句，其他句子都是围绕着这句话来说的。显而易见，我们可按先总后分的顺序来排列句子。四、按空间推移的顺序排列。所谓空间推移，就是由地点的转移，表达出不同的内容。排列时，要十分注意，不要与其他的方法相混淆。把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。

第十章：内部排序练习题

第十章：内部排序练习题一、选择题 1、下述几种排序方法中，平均查找长度最小的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（）。 A、6 B、7 C、8 D、20 3、下列排序算法中不稳定的有（）。 A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序 4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（），相应的时间复杂度为（），该算法是（）排序方法。 A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定J、不稳定 5、对初始状态为递增的表按递增顺序排序，最省时间的是（）算法，最费时间的算法是（）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 8、下列排序中，排序速度与数据的初始排列状态没有关系的是（）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序 9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序 10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序 12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 A、希尔排序 B、归并排序 C、插入排序 D、选择排序 13、n个记录的直接插入排序所需记录关键码的最大比较次数为（）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1 14、n个记录的直接插入排序所需的记录最小移动次数为（）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n 15、快速排序在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。

几种常见内部排序算法比较

常见内部排序算法比较排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.

详细设计 1、起泡排序算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key

排序习题参考标准答案

————————————————————————————————作者：————————————————————————————————日期：

习题七参考答案一、选择题 1．内部排序算法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序算法中，( B )是不稳定的排序。 A．插入排序B．堆排序C．二路归并排序D．冒泡排序 3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。 A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序 4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。 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．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。 A. 2 B. 4 C. 6 D. 8 8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序二、填空题 1.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。 2.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较 3 次。 3.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。 4.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 {50,70,60,95,80}。 5.n个记录的冒泡排序算法所需的最大移动次数为3n(n-1)/2 ，最小移动次数为0 。 6.对n个结点进行快速排序，最大的比较次数是n(n-1)/2 。 7.对于堆排序和快速排序，若待排序记录基本有序，则选用堆排序。 8.在归并排序中，若待排序记录的个数为20，则共需要进行5 趟归并。 9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素的移动。 10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。三、算法设计题 1．试设计算法，用插入排序方法对单链表进行排序。参考答案:

内部排序代码

#include #include #include #include #define OK 1 #define FALSE 0 #define MAX_NUM 100 typedef int Status; typedef int ElemType; typedef struct SqList { ElemType r[MAX_NUM]; int length; }SqList; typedef SqList HeapType; Status Exchange(ElemType &a,ElemType &b) { ElemType t; t=a;a=b;b=t; return OK; } //直接插入排序 Status InsertSort(SqList &L) { int i,j; for(i=2;i<=L.length;i++) if(L.r[i]

for(j=i-dk;j>0&&L.r[0]>t; for(j=1,i=t-1;i>=0;i--,j<<=1) dlta[i]=j+1; dlta[t-1]--; for(i=0;iL.r[j+1]) Exchange(L.r[j],L.r[j+1]); return OK; } //快速排序 int Partition(SqList &L,int low,int high) { int pivotkey=L.r[low]; L.r[0]=L.r[low]; while(low=pivotkey) high--; L.r[low]=L.r[high]; while(low

数据结构第九章排序习题及答案

习题九排序一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

行测事件排序题库

C.2—1—5—4—3 D.5—4—2—1—3

73. (1)绿叶葱葱，森林茂密 (2)厂房林立，马达轰鸣 (3)钻机飞转，原油滚滚(4)燃气发电，远程送电 (5)阳光明媚，百花齐放 A.3—4—5—1—2 B.5—4—1—2—3 C.1—2—3—4—5 D.5—1—3—4—2 (3)工作服前襟上有一块补丁(4)检测碎布片中有油墨成分 (5)现场拾到一块衣服 A.2—5—1—4—3 B.2—5— C.5—2—4—1—3 大量有机物积聚(2)形成石油 (3)跨过界河向北征战 (4)战火熄灭回国通商 (5)青年男子被征入伍 A.3—5—2—1—4 B.3—2—1—4—5 C.5—2—3—4—1 D.5—3—2—1—4 75. (1)嫌疑人聚焦在印刷厂一名职工身上(2)死者所穿衣服完好无损 (5)古浮游生物残骸沉积海底 A.1—5—3—4—2 B.5—4—1—2—3 C.3—1—2—5—4 77. (1)诸葛亮显示出卓越的军事才华(2)三顾 74. (1)融入异族自谋出路(3)复杂的化学变化(2) 一支残部向西突围(4) 剧烈地质变化 76. ( 1 )

数据结构查找排序经典试题

数据结构查找排序经典试题一、填空 1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度 ASL=_______。 2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有____________。 3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行 _________趟的插入才能完成排序。 4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_________趟的排序。 5、直接插入排序算法的时间复杂度为________________。 6、按（）遍历二叉排序树，可以得到按值递增的关键字序列，在下图所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（）。 50 95 20 55 70 10 30 85 二、判断

1、平衡二叉树中子树的深度不能大于1。（） 2、快速排序法是稳定的排序方法。（） 3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地方。（） 4、冒泡排序法是稳定的排序方法。（） 5、折半插入排序法是稳定的排序方法。（）三、选择 1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的插入才能完成排序。 A、n B、(n-1)/2 C、n+1 D、n-1 2、采用顺序查找法查找长度为n的线性表时，平均查找长度为（） A、n B、(n-1)/2 C、n/2 D、(n+1)/2 3、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行（）次比较。 A、1 B、2 C、3 D、4 4、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。 A、5 B、4 C、3 D、2 5、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，

第7章排序习题参考答案

内部排序算法的实现与比较

内部排序算法的实现与比较 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT

实验四：内部排序算法的实现与比较一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。（2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。（3)对结果作出简要分析。 3．测试数据：随机函数产生。二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作：数组赋值： for(i=1;i

公共部门人力资源管理练习题排序

公共部门人力资源管理练习题（）一、选择题（每题2分，30题共计60分，每题至少有一个答案，多选或者少选均不能得分） 74. 对于公共部门人才所要测评的要素来说，（A）是最基本的测评方式，具有重要的把关作用。 A. 笔试 B. 资质测试 C. 评价中心技术 D. 无领导小组讨论 83. 美国哈佛大学威廉·詹姆斯教授，在实地调查中发现一个人平常表现的能力水平，与经过激发可能达到的能力水平之间存在着大约（ A ）左右的差距。 A. 60％ B. 50％ C. 80％ D. 70％ 89. （ A）是绩效管理的重要环节，也是传统的绩效管理模式与现代模式的本质区别之一。 A. 持续沟通 B. 实施绩效评价 C. 提供绩效反馈 D. 绩效改进指导 53. 第一个被公认的现代人事管理部门是1902年在（B）现金出纳公司设立的劳工部门，它的工作内容包括工资行政、诉怨、雇用工作情况和工作改善等。 A. 英国 B. 美国 C. 德国 D. 比利时 57. 我国古代社会中按官职高低授予不同政治待遇以表明官员等级尊卑的制度是（B）。 A. 俸禄 B. 品秩 C. 致仕 D. 回避 58. 《中华人民共和国公务员法》于（B）开始施行。 A. 2006年10月1日 B. 2006年1月1日 C. 2007年10月1日 D. 2007年1月1日 62. 我国劳动力市场体系已初步形成，（B）在人力资源配置中的主导地位也已初步确立。 A. 政府部门 B. 市场机制 C. 第三部门 D. 三资企业 70. （ B）是一种以工作为中心的工作分析方法，是对管理工作进行定量化测试的方法，适用于不同组织内管理层次以上职位的分析。 A. 职位分析问卷 B. 管理职位描述问卷 C. 体能分析问卷 D. 心理分析问卷 77. 公共部门人力资源招募与选录工作只有在（ B ）分析的基础上，才能确定公共职位空缺的数量、结构、任职资格条件、具体的招募途径以及甄选方法等。 A. 劳动力市场的供需状况 B. 内部环境 C. 外部环境 D. 经济环境 80. ( B )是公职人员职业生涯开始时或任新职时所经历的第一种类型的培训。 A. 技能培训 B. 初任培训 C. 专业培训 D. 知识更新培训 85. 我国古代的"卧薪尝胆"、"破釜沉舟"的故事充分说明了( B )的重大作用。 A. 情感激励 B. 危机激励 C. 荣誉激励 D. 目标激励 86. 目前，大多数公共管理部门所采取的考评模式均属于（ B）。 A. 发展型评估 B. 判断型评估 C. 参与型评估 D. 专项型评估 88. 实践证明，采用（B）的考核方法，很难区分不同部门之间公务员业绩的差别和同一部门内工作性质差别不太大的公务员工作业绩的高下，也很难根据考核结果客观、完整地评价一个公务员。 A. 定量分析 B. 定性分析 C. 360度绩效分析 D. 平衡记分卡 106. 公共部门人力资源部内培训的最大优点在于( B)。 A.有助于增进部门之间的相互联系和信息交流，并有助于节省培训经费 B.针对性较强、容易实施，也比较容易取得实效 C.有助于人们开阔视野，增强应对所面对的现实问题的能力 D.有利于部门工作经验的传授和良好人际关系的维系，也有利于保持部门的优良传统和工作的连续性 67. ( C )是公务员交流最为常见的方式。 A. 调任 B. 聘任 C. 转任 D. 挂职锻炼 107. （C）是目前公职人员培训中普遍采用的方法。 A. 讲授式培训法 B. 研讨式培训法 C. 案例分析培训法 D. 合作研究培训法

内部排序算法的实现与比较

实验四：内部排序算法的实现与比较一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。（2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。（3)对结果作出简要分析。 3．测试数据：随机函数产生。二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作：数组赋值： for(i=1;i

行测事件排序专项练习

行测事件排序专项（考的简单且不多） 1．（1）某公司推出送奶服务（2）李大妈发现奶箱是空的（3）获得赔偿（4）给奶品公司打电话（5）发生车祸 A．1-2-5-3-4 B．1-5-2-4-3 C．1-5-4-2-3 D．1-5-3-4-2 2．（1）责令店主停业整顿（2）追查熟食加工点（3）举行婚礼（4）出现多人食物中毒（5）核查各种菜品 A．3-5-4-2-1 B．4-3-2-5-1 C．3-4-5-2-1 D．3-4-1-5-2 3．（1）119接到报警（2）消防队赶到封锁现场（3）道路堵塞（4）运化学试剂的汽车发生遗撒（5）路边树丛突然起火 A．4-5-1-2-3 B．3-4-5-1-2 C．4-3-2-1-5 D．4-5-2-3-1 4．（1）摔倒（2）遗留废料（3）提起诉讼（4）上班（5）道路施工 A．4-2-1-5-3 B．5-2-4-1-3 C．4-3-2-1-5 D．4-5-2-3-1 5．（1）晕倒（2）领导探望（3）步入社会（4）工作任劳任怨（5）成为劳模 A．4-2-1-3-5 B．1-3-2-4-5 C．5-4-1-3-2 D．3-4-1-2-5

答案及详细解析 1．【答案】B。解析：这是一则因奶品公司未如约履行送奶服务，最终给客户赔偿的整个过程。 2．【答案】C。解析：这是一则食物中毒，并予以严查的经过。要强调的是“停业整顿”一定是在情况调查清楚之后的措施。因此答案是C。 3．【答案】A。解析：本题要注意之处就是因为“起火”，所以消防队首先赶到现场。 4．【答案】B。解析：按照事件发生的时间顺序排列。 5．【答案】D。解析：按照事件发生的时间顺序排列。行测事件排序专项突破训练附答案事件排序题主要考查考生对事件发生先后顺序的理解与逻辑思维能力。这类考题的题型有2种。第一种：逻辑判断型这是一类考察考生对事物逻辑关系的分析能力的一种体型，试题中的五个环节往往有着某些必然的联系，但考生要注意这些联系的时间顺序，尤其是其中的某两项或三项，这类题型的考点也就在这些容易混淆时间顺序的事件的孰先孰后上；同时在做出选择后还要考虑一下自己所做的排序是否合乎事理。如下面的试题【例题】：(1)山洪暴发(2)紧急动员(3)战胜洪水(4)大堤决堤(5)抗灾抢险 A: 1-2-4-3-5 B: 1-4-2-5-3 C: 5-3-4-2-1 D: 4-1-2-3-5 答案应该选B

2018年浙江省选考信息技术查找与排序强化习题一答案

第二轮排序和查找算法综合1 行政班：教学班：姓名：学号：根据课本上的排序算法和查找算法回答1-6题： 1．【加试题】有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能．．．的是（） A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7 2.【加试题】对下列数据序列进行冒泡升序排序，排序效率最低的序列（） A.31，29，24，20，15，10 B.10，15，20，24，29，31 C.29，10，31，15，20，24 D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（） A．69 B．66、69 C．66、76、69 D．56、66、76、69 4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种方法都能访问到的数字是（） A.3 B.5 C.8 D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为（） A.feel, data, easy B.great, data, easy C.bike, cake, dada，easy D.feel,cake,data,easy 6.【加试题2】下列有关查找的说法，正确的是（） A．进行对分查找时，被查找的数据必须已按升序排列 B．进行对分查找时，如果查找的数据不存在，则无需输出结果 C．在新华字典中查找某个汉字，最适合使用顺序查找 D．对规模为n的数据进行顺序查找，平均查找次数是21 n 7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是（） For i = 1 To 1 For j = 5 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j) a(j) = a(j - 1) a(j - 1) = t End If Next j Next i 命题：杜宗飞 A.70，57，38，53，30 B.30, 38，70，53，57 C.70，38，57，53，30 D.30, 38，57，53，70 8.【加试题】有如下程序段： For i = 1 To 2

排序习题

行测事件排序题库

小学句子排序方法及习题附答案

第十章：内部排序练习题

几种常见内部排序算法比较

排序习题参考标准答案

内部排序代码

最新人教版小学四年级语文句子排序练习题附答案

数据结构第九章排序习题及答案

行测事件排序题库

数据结构查找排序经典试题

第7章 排序 习题参考答案

内部排序算法的实现与比较

公共部门人力资源管理练习题 排序

内部排序算法的实现与比较

行测事件排序专项练习

2018年浙江省选考信息技术查找与排序强化习题一答案

第7章排序习题参考答案

公共部门人力资源管理练习题排序