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

admin2010-01-23 90

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

选项 A、O(nlog₂n)
B、O(n²)
C、O(log₂n)2
D、O(n²log₂n)

答案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(n²)。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序。因此，快速排序的复杂是O(nlog₂n)。

转载请注明原文地址:https://kaotiyun.com/show/gYxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

VLANtag在OSI参考模型的(50)实现。

在LAN拓扑机构中，(22)结构是具有中心节点的拓扑；(23)可以用令牌传递或用CSMA/CD控制媒体访问的拓扑；(24)仅使用象令牌传递这样的确定性的媒体空转法。

公钥密码是(39)。常用的公钥加密算法有(40)，它可以实现加密和数字签名，它的一个比较知名的应用是(41)，这种应用的协商层用公钥方式进行身份认证，记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。

下面关于VTP协议的描述中，错误的是()。

关于在I／O设备与主机间交换数据的叙述，__________是错误的。

若某计算机采用8位整数补码表示数据，则运算()将产生溢出。

某逻辑电路有两个输入分别为X和Y，其输出端为Z。当且仅当两个输入端X和Y同时为0时，输出Z才为0，则该电路输出Z的逻辑表达式为()。

只要物质蒸气的温度低于其临界温度，就可采取加压的方式将其液化

下列属于显性知识的是

关于辨脓的方法，错误的是()

集体土地上的房屋转为国有土地上的房屋,申请人应当自事实发生起()日内,向登记机关提交用地证明等有关文件,申请房屋所有权初始登记。

当量子能量达到12eV以上时，对物体有电离作用，能导致机体的严重损伤，这类辐射称为()。

协定存款账户视同()使用，不得透支。

下面哪些是国务院组成机构?（）

隋朝统一的条件主要有______。①人民渴望实现全国的统一②全国的交通比过去发达③北方民族的大融合④江南经济的发展

()是中国现存最大的一处坛庙建筑，原来是明、清两代皇帝祭天、祈祷丰收的地方。