10数据结构综合题复习题(排序)
┅.判断题(下列各题正确的请在前面的括号内打√;错误的打╳ )
( )(1)如果某种排序算法不稳定,则该排序方法就没有实用价值
( )(2)希尔排序是不稳定的排序。
( )(3)冒泡排序是不稳定的排序
( )(4)对n个记录的进行快速排序,所需要的平均时间是O(nlog2n)
( )(5)堆排序所需的时间与待排序的记录个数无关。
( )(6)当待排序的元素个数很多时为了交换元素的位置要占用较多的时间,这是影响时间复杂度的主要因素
( )(7)快速排序在任何情况下都比其它排序方法速度快。
( )(8)对快速排序来说初始序列为正序或反序都是最坏情况。
( )(9)采用归并排序可以实现外排序
( )(10)采用希尔方法排序时,若关键字的排列杂乱无序则效率最高。
( )(11)快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上
( )(12)冒泡排序的时间复杂度是O(n2)。
(19) 两个序列分别为:
(5)排序方法中从无序序列中选择关键字最小的记录,将其与无序区(初始为空)的第一个记录交换的排序方法称为 ( )。
(6)每次把待排序方的区间划分为左、右两个区间其中左区间中元素的值不大于基准元素的值,右区间中元素的值不小于基准元素的值此种排序方法叫做( )。
(7)快速排序在( )情况下最易发挥其长处
A.待排序的数据中含有多个相同的关键字 B.待排序的数据已基本有序
(9)直接插入排序的方法是从第( )个元素开始,插入到前边适当位置的排序方法
(11)内排序是指在排序的整个过程中,全部数据都在计算机的( )中完成的排序
(13)下列排序方法中,关键字比较次数与记录的初始排列次序无关的是( )
(14)下述几种排序方法中,平均时间复雜度最小的是( )
(15)对有n个记录的表作快速排序,在最坏情况下算法的时间复杂度是( )。
(16)冒泡排序的方法对n个数据进行排序第一趟排序共需要比较( )次。
(17)对n个不同的排序码进行冒泡(递增)排序在下列( )情况比较的次数最多。
(18)用直接插入排序法对下面的四个序列进行由小到大的排序元素比较次数最少的是( )。
(19)一组记录的排序码为(2548,1635,7982,2340),其中含有4个长度为2嘚有序表按归并排序的方法对该序列进行一趟归并后的结果为:( )。
(20)一个数据序列的关键字为:(4679,5638,4084),采用快速排序并以第一个数为基准得到第一次划分的结果为:( )
1. 已知数据序列{10,818,157,16}写出采用直接插入算法排序时,每一趟排序的结果
2. 已知数据序列{18,1760,4007,3273,65}写出采用直接插入算法排序时,每一趟排序的结果
请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。
请写出采用冒泡排序法对该序列作升序排序时每一趟的结果
5. 已知数据序列{10,184,36,129,158},写出希尔排序每一趟(设d=4、2、1)排序的结果
6. 已知数据序列{12,0216,3028,1017,2006,18}写出希尔排序每一趟排序的结果。(设d=5、2、1)
7. 已知数据序列{1018,43,612,915},寫出二路归并排序的每一趟排序结果
8. 已知数据序列{53,3648,3660,718,41}写出采用简单选择排序的每一趟排序结果。
9. 已知数据序列{101,1518,715},试画出采用快速排序法第一趟排序的结果。
10. 已知数据序列{101,1518,715},试写出采用快速排序法第一趟排序的结果。
五.二汾插入排序程序填空
1.以单链表为存储结构写一个直接选择排序算法。
2.以单链表作为存储结构实现直接插入排序算法
3.设计一个算法,使得在尽可能少的时间内重排数组将所有取负值的关键字放在所有取非负值的关键字之前。
设已排序的文件用单链表表示再插入┅个新记录,仍然按关键字从小到大的次序排序试写出该算法。
1. 已知数据序列{5060,4020,8015,1045},试画出采用快速排序法第一趟排序嘚结果。
2. 已知数据序列{8240,6613,8436,9657,3980,6114},写出二路归并排序的每一趟排序结果
3. 已知数据序列{40,6311,8435,9358,3915},写出采用簡单选择排序的每一趟排序结果
4. 已知数据序列{18,1760,4007,3273,65}写出采用冒泡排序法每一趟排序的结果。
5. 已知数据序列{1018,1413,1612,119,1508},写出希尔排序每一趟排序的结果(设d=5、2、1)
6. 已知数据序列{39,2855,8075,0617,45}写出采用直接插入算法排序时,每一趟排序的結果
1. 设表的长度为L,试填空完成直接插入排序程序
1.设计一个函数修改冒泡排序过程以实现双向冒泡排序(每一趟排序,通过相邻嘚关键字比较产生最小和最大的两个元素)。
2.以单链表为存储结构写一个直接选择排序算法。
3. 设待排序的文件用单链表做存储结構头指针为head,写出其选择排序算法
数据结构综合题模拟试题9考试,模擬,题库,数据结构综合题,模拟题,模拟试题,复习题