在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。

admin2009-02-15 74

问题在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。

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

答案A

解析冒泡排序的过程是先将第1个数与第2个数相比较，若为逆序则交换两数，然后比较每两个数与第三个数，依此类推，直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序，结果是最大的数被排在了最后。然后进行第二趟排序，对前面n-1个数进行冒泡排序，结果是次大的数被排到了n-1的位置上。一般来说，第i趟冒泡排序是从第一个数到第n-i+1的位置上，整个排序过程需进行A(1≤k≤n)趟。分析冒泡排序的效率，若初始序列为正序，则只进行一次排序。在排序过程中只进行n-1次比较，不交换数据。若为逆序，则需进行n-1趟排序，需进行n(n-1)/2次比较，交换数据的数量组也相同。因此，冒泡排序的复杂性是O(n²)。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序。因此，快速排序的复杂是O(nlog₂n)。

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

本试题收录于：程序员上午基础知识考试题库软考初级分类

程序员上午基础知识考试

软考初级

相关试题推荐

随机试题

最新回复(0)

在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。

程序员上午基础知识考试

软考初级

IIS安装的硬盘分区最好选用NTFS格式，是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④

IIS安装的硬盘分区最好选用NTFS格式，是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④

阅读以下基于Windows2003操作系统配置Web服务器的技术说明，回答问题1～问题5。【说明】随着电子商务日益普及，某网络服务提供商基于WindowsServer2003操作系统建构了一台的虚拟服务器，并安装IIS6.0来配置各类客户网

请从以下供选择的答案中为index.asp文档程序中(1)～(5)处空缺部分选择正确答案。(1)A．CreateObjectB．ConnectC．ExecuteSQLD．Open()(2)A．＜body＞B．＜ht

阅读以下网络安全的技术说明，根据要求回答问题1～问题6。【说明】某电子商务公司在WindowsServer2003中安装IIS6.0来配置Web服务器，域名为www.abc.com。该商务网站在设计时充分考虑了安全问题，通过对安全性、可用性

安装Linux之前需要知道哪些必要的数据信息?Unux中的WWW服务器有哪几种?

/etc/dhcpd.conf文件中的配置语句：hostCIU_DHCP{hardwareethemet52.54.AB.3B.B6.45fixed-address192.168.1.15；}表示的是什么意思?DHCP客户机从DHCP

连接主机A与交换机的单根网线的最大长度为多少?100Base-TX局域网中交换机最多可以级连几级?两个交换机间的距离不能超过多少米?

大型机械设备和多班作业的机械必须建立()。

根据()，证券投资基金可分为成长型投资基金、收入型投资基金和平衡型投资基金。

税务机关按照一地一证得原则，核发《外管证》，《外管证》的有效期限一般为()。

对外贸易关系人及仲裁、司法等机关，对海运进口商品可向检验机构申请办理(　　)等残损鉴定工作。

下列我们日常生产生活所需的产品中，不属于发酵工程产品的是()。

下列事由，根据《国家行政机关公文处理办法》的规定，不可以使用“决定”的是()。

四元方程组Ax=b的三个解是α1，α2，α3，其中α1=(1，1，1，1)T，α2+α3=(2，3，4，5)T，如r(A)=3，则方程组Ax=b的通解是_________．

阅读以下说明，回答问题1至问题4，将解答填入答题纸对应的解答栏内。【说明】某企业采用WindowsServer2003配置了Web、FTP和邮件服务。【问题2】根据图3-1判断正误。(正确的答“对”，错误的答“错”)A．勾选“读取”是指禁止

不允许出现重复字段值的索引是

在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。

程序员上午基础知识考试

软考初级

IIS安装的硬盘分区最好选用NTFS格式，是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④

IIS安装的硬盘分区最好选用NTFS格式，是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④

阅读以下基于Windows2003操作系统配置Web服务器的技术说明，回答问题1～问题5。【说明】随着电子商务日益普及，某网络服务提供商基于WindowsServer2003操作系统建构了一台的虚拟服务器，并安装IIS6.0来配置各类客户网

请从以下供选择的答案中为index.asp文档程序中(1)～(5)处空缺部分选择正确答案。(1)A．CreateObjectB．ConnectC．ExecuteSQLD．Open()(2)A．＜body＞B．＜ht

阅读以下网络安全的技术说明，根据要求回答问题1～问题6。【说明】某电子商务公司在WindowsServer2003中安装IIS6.0来配置Web服务器，域名为www.abc.com。该商务网站在设计时充分考虑了安全问题，通过对安全性、可用性

安装Linux之前需要知道哪些必要的数据信息?Unux中的WWW服务器有哪几种?

/etc/dhcpd.conf文件中的配置语句：hostCIU_DHCP{hardwareethemet52.54.AB.3B.B6.45fixed-address192.168.1.15；}表示的是什么意思?DHCP客户机从DHCP

连接主机A与交换机的单根网线的最大长度为多少?100Base-TX局域网中交换机最多可以级连几级?两个交换机间的距离不能超过多少米?

大型机械设备和多班作业的机械必须建立()。

根据()，证券投资基金可分为成长型投资基金、收入型投资基金和平衡型投资基金。

税务机关按照一地一证得原则，核发《外管证》，《外管证》的有效期限一般为()。

对外贸易关系人及仲裁、司法等机关，对海运进口商品可向检验机构申请办理( )等残损鉴定工作。

下列我们日常生产生活所需的产品中，不属于发酵工程产品的是()。

下列事由，根据《国家行政机关公文处理办法》的规定，不可以使用“决定”的是()。

四元方程组Ax=b的三个解是α1，α2，α3，其中α1=(1，1，1，1)T，α2+α3=(2，3，4，5)T，如r(A)=3，则方程组Ax=b的通解是_________．

阅读以下说明，回答问题1至问题4，将解答填入答题纸对应的解答栏内。【说明】某企业采用WindowsServer2003配置了Web、FTP和邮件服务。【问题2】根据图3-1判断正误。(正确的答“对”，错误的答“错”)A．勾选“读取”是指禁止

不允许出现重复字段值的索引是

对外贸易关系人及仲裁、司法等机关，对海运进口商品可向检验机构申请办理(　　)等残损鉴定工作。