2. 计算机
  3. 在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用冒泡排序的第一趟扫描结果是(6

在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用冒泡排序的第一趟扫描结果是(6

admin2010-01-23  73
问题 在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用冒泡排序的第一趟扫描结果是(61)。设被排序数据序列有n个元素，冒泡排序算法的复杂性是(62)。
选项 A、O(nlog2n)
B、O(n2)
C、O(log2n)2
D、O(n2log2n)
答案B
解析 冒泡排序的过程是先将第1个数与第2个数相比较，若为逆序则交换两数，然后比较每两个数与第三个数，依次类推，直到第n-1个数与第几个数进行过比较为止。上述过程称为一趟冒泡排序，结果是最大的数被排在了最后。然后进行第二趟，对前面n-1个数进行冒泡排序，结果是次大的数被移到了n-1的位置上。一般来说，第i趟冒泡排序是从第一个数到第n-i+1的位置上，整个排序过程需进行k(1≤k≤n)趟。对于题中给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大排序，若先选出较大的元素，则对于冒泡排序，第一趟操作为541←→132，984←→746，984←→518，984←→181，984←→ 946，984←→314，984←→205，984←→827，其结果得到的序列为 (132,541,746,518,181,946,314,205,827,984)；对于直接选择排序，第一趟操作为984←→827，其结果得到的序列为(541,132,827,746,518,181,946,314,205,984)。请注意，如果采用快速排序(以中间元素518为基准)的第一趟扫描结果是(205,132,314,181,518,746,946,984,827)。分析冒泡排序的效率，若初始序列为正序，则只进行一次排序。在排序过程中只进行n-1次比较，不交换数据。若为逆序，则需进行n-1趟排序，需进行n(n-1)/2次比较，交换数据的数量组也相同。因此，冒泡排序的复杂性是O(n2)。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序。因此，快速排序的复杂是O(nlog2n)。
转载请注明原文地址:https://www.kaotiyun.com/show/gYxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)