广州大学松田学院10数据结构复习题-排序-参考答案

数据结构复习题排序一判断题下列各题正确的请在前面的括号内打错误的打如果某种排序算法不稳定则该排序方法就没有实用价值希尔排序是不稳定的排序冒泡排序是不稳定的排序对个记录的进行快速排序所需要的平均时间是堆排序所需的时间与待排序的记录个数无关当待排序的元素个数很多时为了交换元素的位置要占用较多的时间这是影响时间复杂度的主要因素快速排序在任何情况下都比其它排序方法速度快对快速排序来说初始序列为正序或反序都是最坏情况采用归并排序可以实现外排序采用希尔方法排序时若关键字的排列杂乱无序则效率最高快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上冒泡排序的时间复杂度是二填空题大多数排序算法都有两个基本的操作比较和移动评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间根据被处理的数据在计算机中使用不同的存储设备排序可分为内排序和外排序外排序是指在排序过程中数据的主要部分存放在计算机的外存中对个关键字进行冒泡排序其可能的最小比较次数为次在最坏情况下在第趟直接插入排序中要进行次关键字的比较对个关键字进行冒泡排序时间复杂度为快速排序在最坏情况下的时间复杂度是对于个记录的集合进行归并排序所需要的平均时间为对于个记录的集合进行归并排序所需要的附加空间是若原始数据接近无序则选用快速排序最好在排序前关键字值相等的不同记录排序后相对位置保持不变的排序方法称为稳定排序方法在插入排序和选择排序中若初始数据基本正序则选用插入排序较好当增量为时该趟希尔排序与直接插入排序基本一致第一趟排序后序列中键值最大的记录交换到最后的排序算法是冒泡排序依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序在插入排序选择排序和归并排序中排序是不稳定的为选择排序在对一组记录进行直接插入排序时当把第个记录插入到有序表时为寻找插入位置需比较次两个序列分别为用冒泡排序法对和进行排序交换次数较少的是序列对一组记录进行直接选择排序时第四次选择和交换后未排序记录是三选择题排序是根据的大小重新安排各元素的顺序关键字数组元素件结点评价排序算法好坏的标准主要是执行时间辅助空间算法本身的复杂度执行时间和所需的辅助空间直接插入排序的方法是的排序方法不稳定稳定外部选择直接插入排序的方法要求被排序的数据存储必须链表必须顺序顺序或链表可以任意排序方法中从无序序列中选择关键字最小的记录将其与无序区初始为空的第一个记录交换的排序方法称为希尔排序归并排序插入排序选择排序每次把待排序方的区间划分为左右两个区间其中左区间中元素的值不大于基准元素的值右区间中元素的值不小于基准元素的值此种排序方法叫做冒泡排序堆排序快速排序归并排序快速排序在情况下最易发挥其长处待排序的数据中含有多个相同的关键字待排序的数据已基本有序待排序的数据完全无序待排序的数据中最大值与最小值相差悬殊下述几种排序方法中要求内存量最大的是插入排序选择排序快速排序归并排序直接插入排序的方法是从第个元素开始插入到前边适当位置的排序方法堆的形状是一棵二叉排序树满二叉树完全二叉树平衡二叉树内排序是指在排序的整个过程中全部数据都在计算机的中完成的排序内存外存内存和外存寄存器快速排序的方法是的排序方法不稳定稳定外部选择下列排序方法中关键字比较次数与记录的初始排列次序无关的是选择排序希尔排序插入排序冒泡排序下述几种排序方法中平均时间复杂度最小的是希尔排序插入排序冒泡排序选择排序对有个记录的表作快速排序在最坏情况下算法的时间复杂度是冒泡排序的方法对个数据进行排序第一趟排序共需要比较次对个不同的排序码进行冒泡递增排序在下列情况比较的次数最多从小到大排列好的从大到小排列好的元素无序元素基本有序用直接插入排序法对下面的四个序列进行由小到大的排序元素比较次数最少的是一组记录的排序码为其中含有个长度为的有序表按归并排序的方法对该序列进行一趟归并后的结果为一个数据序列的关键字为采用快速排序并以第一个数为基准得到第一次划分的结果为四排序过程分析已知数据序列写出采用直接插入算法排序时每一趟排序的结果解第一趟结束时结果第二趟结束时结果第三趟结束时结果第四趟结束时结果第五趟结束时结果已知数据序列写出采用直接插入算法排序时每一趟排序的结果解第一趟结束时结果第二趟结束时结果第三趟结束时结果第四趟结束时结果第五趟结束时结果第六趟结束时结果第七趟结束时结果已知数据序列请写出采用冒泡排序法对该序列作升序排序时每一趟的结果解第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果第五趟排序结果第五趟排序过程中已无记录交换排序结束已知数据序列请写出采用冒泡排序法对该序列作升序排序时每一趟的结果解第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果第五趟排序结果第六趟排序结果第六趟排序过程中已无记录交换排序结束已知数据序列写出希尔排序每一趟设排序的结果解已知数据序列写出希尔排序每一趟排序的结果设解已知数据序列写出二路归并排序的每一趟排序结果第一趟排序结果第二趟排序结果第三趟排序结果已知数据序列写出采用简单选择排序的每一趟排序结果解已知数据序列试画出采用快速排序法第一趟排序的结果解交换交换第一趟排序结果已知数据序列试写出采用快速排序法第一趟排序的结果解五二分插入排序程序填空按递增序对进行二分插入排序设定为监视哨元素后移插入六算法题以单链表为存储结构写一个直接选择排序算法解以单链表作为存储结构实现直接插入排序算法解查找插入位置最大无须插入插在表头插在中间某个位置上设计一个算法使得在尽可能少的时间内重排数组将所有取负值的关键字放在所有取非负值的关键字之前解初终下标自右向左找非负数自左向右找负数设已排序的文件用单链表表示再插入一个新记录仍然按关键字从小到大的次序排序试写出该算法排序过程分析已知数据序列试画出采用快速排序法第一趟排序的结果解已知数据序列写出二路归并排序的每一趟排序结果解第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果已知数据序列写出采用简单选择排序的每一趟排序结果解已知数据序列写出采用冒泡排序法每一趟排序的结果解第一趟结束时结果第二趟结束时结果第三趟结束时结果第四趟结束时结果第五趟结束时结果已无交换结束已知数据序列写出希尔排序每一趟排序的结果设解已知数据序列写出采用直接插入算法排序时每一趟排序的结果解第一趟结束时结果第二趟结束时结果第三趟结束时结果第四趟结束时结果第五趟结束时结果第六趟结束时结果第七趟结束时结果程序填空设表的长度为试填空完成直接插入排序程序按递增序对进行直接插入排序设定为监视哨插入第个记录直接选择排序按递增序对进行直接选择排序选择选择关键字最小的记录交换关键字二分插入排序按递增序对进行二分插入排序设定为监视哨元素后移插入算法设计题设计一个函数修改冒泡排序过程以实现双向冒泡排序每一趟排序通过相邻的关键字比较产生最小和最大的两个元素解由底向上由上向底以单链表为存储结构写一个直接选择排序算法解设待排序的文件用单链表做存储结构头指针为写出其选择排序算法