天津商业大学-计算机科学与技术专业-高职升本-课件7

1、综合练习七,一.单选题,1. 就平均时间复杂度而言，下列排序方法中，性能最好的排 序方法是 【1】 ，它的平均时间复杂度为 【2】 。 【1】A) 快速排序 B) 选择排序 P276 C) 插入排序 D) 冒泡排序 【2】A) O(n) B) O(n2) P276 C) O(nlog2n) D) O(log2n!) 参考答案：A C,一.单选题,2. 在堆排序过程中，对n个记录建立初始堆需要进行 【1】 次筛选运算，而由初始堆到排序结束，需要对树根结点进行 【2】次筛选运算。P280 【1】A) n/2 B) n/2 C) n-1 D) n 【2】A) n/2 B) n/2 C) n-1 D)

2、 n 参考答案：A C,一.单选题,3. 以下四种排序方法中，关键字比较的次数与记录的初始排 列次序无关的是_ 。 A) 希而排序 B) 选择排序 C) 插入排序 D) 冒泡排序 B 4. 以下排序方法中，要求内存量最大的是_ 。 A) 快速排序 B) 选择排序 C) 插入排序 D) 归并排序 P289 D,一.单选题,5. 快速排序方法中，在_情况下不利于发挥其特长 。 A) 要排序的数据中含有多个相同的值 P276 B) 要排序的数据量太大 C) 要排序的数据基本有序 D) 要排序的个数为奇数 C,一.单选题,6. 在二路归并排序过程中，每趟归并的时间复杂度为【1】 整个排序过程的时间复杂

3、度为【2】。P283 P284 【1】A) O(n) B) O(n2) C) O(nlog2n) D) O(1) 【2】A) O(n) B) O(n2) C) O(nlog2n) D) O(1) A C 7. 在折半排序方法中，每次将待插入的关键字与它前面一组 _位置的关键字比较，从而确定待插入关键字的插入位 置。 A) 所有 B) 中间 C) 第一个 D) 最后一个 B,一.单选题,8. 若用堆排序方法建立一个非递减序列，则需要建立一个 _，而该堆是一棵_ 。P281 【1】A) 大顶堆 B) 完全二叉树 C) 小顶堆 D) 二叉树 【2】A) 大顶堆 B) 完全二叉树 C) 小顶堆 D)

4、二叉树 A B 9. 下列四种内排序方法中，不稳定的方法是_。 P289 A）直接插入排序 B）冒泡排序 C）快速排序 D）直接选择排序 C,一.单选题,10. 用某种方法对线性表(25，84，21，47，15，27，68，35 ，20)进行排序时，元素序列变化如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法_。 P272 A）归并排序 B）希而排序 C）快速排序 D）选择排序 C,二.多选题,1. 下列排序方法中，时间性能较好且不稳定的排序方法 是_。

5、A) 快速排序 B) 归并排序 C) 希而排序 D) 堆排序 A C D 2.下面给出的排序方法中，平均时间为O(nlog2n)的方法有 _。 P289 A）选择排序 B）插入排序 C）快速排序 D）堆排序 C D,二.多选题,3.下面的排序方法中，稳定的是_。 A）直接插入排序 B）堆排序 C）二分插入排序 D）归并排序 A C D,二.多选题,4内部排序过程中，按所需工作量分类，则可分为 。 A）简单排序方法 B）先进的排序方法 P264 C）复杂排序方法 D）基数排序方法 ABD 5.在排序过程中，待排序记录序列的存储方式有。 A）关键字排序 B）存储位置排序 P264 C）链表排序 D

6、）地址排序 BCD,三、判断题,1在n个记录的起泡排序过程中，若初始序列为有序序列， 则只需要进行一趟排序，在排序过程中需要进行n次比较，且 不移动记录。 P273 2. 基数排序是和其它类排序方法完全不同的排序方法，实现 基数排序只需要进行记录关键字的比较。 P284 ,四、填空题,1. 对n个记录采用直接插入排序，当待排序记录按关键字非 递减有序排列时，进行关键字间的比较次数为最小_ ，记录不需要移动。 n-1 2. 每次从无序表中挑出一个最大或最小的元素，把它交换到 有序表的一端，此种排序方法叫做_排序。 P277 选择,四、填空题,3. 通过一趟排序将待排记录分割成独立的两部分，其中一

7、部 分记录的关键字均比另一部分记录的关键字小，则可分别对 这两部分记录继续进行排序，以达到整个序列有序。这种排 序方法称为_排序。 P273 快速 4. 在插入排序和选择排序，若初始记录基本正序，则选用 _，若初始记录基本反序，则选用_。 插入排序(移动记录少) 选择排序(交换记录少),四、填空题,5. 假定一组待排序的关键字序列为（46，79，56，38，40， 84），对其进行二路归并排序的过程中，第二趟归并后的结 果为 。 38，46，56，79 40，84,初始状态,一趟归并： 46 79 38 56 40 84,二趟归并： 38 46 65 79 40 84,三趟归并： 38 40

8、46 65 79 84,四、填空题,6. 假定一组待排序的关键字序列为（46，79，56，38，40， 84），对其进行快速排序的过程中，第一次划分的结果为 。 40，38 46 56，79，84,一趟快速排序过程P275,初始状态,没有交换,一次交换,二次交换,三次交换,一趟排序,四、填空题,7. 假定一组待排序的关键字序列为（46，79，56，38，40， 84），则利用堆排序的方法建立的初始大顶堆为 。 84，79，56，38，40，46,四、填空题,8. 若待排序的记录中存在多个记录具有相同的键值，经过排 序，这些记录的相对次序仍然保持不变，则称这种排序方法 是 。 稳定的 9.对序列

9、(15，9，7，8，20，-1，4 )用希而排序方法排序， 经一趟排序后序列变为（15，-1，4，8，20，9，7），则该 次采用的增量是 。 4,六、应用题,1对于给定关键字序列45，65，23，84，34，75，41，12 ，写出按从小到大顺序进行冒泡排序的各趟结果。参考答案 初始状态：45 65 23 84 34 75 41 12 第一趟： (45 23 65 34 75 41 12) 84 第二趟： (23 45 34 65 41 12) 75 84 第三趟： (23 34 45 41 12) 65 75 84 第四趟： (23 34 41 12) 45 65 75 84 第五趟： (

10、23 34 12) 41 45 65 75 84 第六趟： (23 12) 34 41 45 65 75 84 第七趟： (12) 23 34 41 45 65 75 84,六、应用题,2有一组数据25，50，70，21，4，18，100，43，7，12。 请写出快速排序算法的基本思想，然后对该组数据写出每趟的 结果，并标明第一趟的数据移动情况。 参考答案： 基本思想：通过一趟排序将待排序记录分割成独立的两部 分，其中一部分记录的关键字均比另一部分记录的关键字小， 则可对这两部分继续排序，以达到整个记录有序。,六、应用题,每趟数据移动情况 初始关键字：(25 50 70 21 4 18 100

11、 43 7 12) 一次交换后： 12 50 70 21 4 18 100 43 7 25 二次交换后： 12 25 70 21 4 18 100 43 7 50 三次交换后： 12 7 70 21 4 18 100 43 25 50 四次交换后： 12 7 25 21 4 18 100 43 70 50 五趟交换后： 12 7 18 21 4 25 100 43 70 50 一趟排序后： (12 7 18 21 4) 25 (100 43 70 50),七、编程,1.请先叙述快速排序的基本思想，然后用C语言编写快速 排序的递归形式算法。 函数首部为 #define MAXSIZE 100 t

12、ypedef int KeyType； /*定义关键字类型*/ typedef struct /*定义记录类型*/ KeyType key； InfoType Otherinfo； RcdType；,七、编程,函数首部： typedef struct /*定义顺序表*/ RcdType rMAXSIZE+1； int length； SqList； void Partition(SqList L, int low, int high) /*一趟快速排序*/ 参考答案： 基本思想：通过一趟排序，将待排序的记录分割成独立 的两部分，其中一部分记录的关键字均比另一部分记录的关 键字小，则可对这两部分记录继续排序，以达到整个序列有 序。,七、编程,(1) 一趟快速排序 void Partition(SqList L, int low, int high) int pikey； L.r0=L.rlow； Pikey= L.rlow.key； While(low= pikey) high - -； L.rlow= L.rhigh； While(lowhigh & L.rlow.key= pikey) low + +； L.rhigh= L.rlow； L.rlow= L.r0； return low； ,七、编程,(2) 对L中子序列快速