下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。　　　　void　select_sort(int　a[]，int　n){　　　　//将a中整数序列重新排列成从小到大有序的整数序列　　　　for(i

admin2013-05-11 34

问题下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。　　　　void　select_sort(int　a[]，int　n){　　　　//将a中整数序列重新排列成从小到大有序的整数序列　　　　for(i=0；i＜n-1；++i){　　　　j=i；　　　　for(k=i+1；k＜n；++k)if(a[k]＜a[j])j=k；　　　　if(j!=i){w=a[j]；a[j]；a；a=w}　　　　)//select_sort

选项 A、O(n²)
B、O(n³)
C、O(n⁴)
D、O(n)

答案A

解析算法中的控制结构是两重循环，所以基本操作是在内层循环中的“比较”，它的重复执行次数是：

　　　对时间复杂度而言，只需要取最高项，并忽略常数系数。

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

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

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

相关试题推荐

随机试题

最新回复(0)

下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。　　　　void　select_sort(int　a[]，int　n){　　　　//将a中整数序列重新排列成从小到大有序的整数序列　　　　for(i

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

软考中级

下面关于曼彻斯特编码的叙述中，错误的是__________。(2010年下半年试题)

TCP协议使用(1)次握手机制建立连接，当请求方发出SYN连接请求后，等待对方回答(2)，这样可以防止建立错误的连接。(2012年上半年试题)(2)

某指令流水线由5段组成，第1、3、5段所需时间为△t，第2、4段所需时间分别为3πt、2△t，如下图所示，那么连续输入n条指令时的吞吐率(单位时间内执行的指令个数)TP为__________。(2009年上半年试题)

对文法G进行改写，然后对每个非终结符写出不带回溯的递归于程序。说明输入串(a，a)#是否为G的句子。

用波特率为56KB的MODEM从网上下载一个文件，这个文件的大小为1MB字节。约定每帧有1个起始位、8个数据位和1个停止位。问下载这个文件至少需要(7)分钟。

用迭代法求解方程x5-x-1=0，下列迭代公式不可能正确的是(6)。

“世界是处在不断的历史发展中的物质”，这是()

男，56岁。近1个月来始有左侧舌根、软腭及咽部阵发性剧烈疼痛，并向外耳道放射。吞咽、说话均可引起疼痛，甚至夜间有疼醒现象，临床检查以上部位未见明显肿胀。黏膜色正常无溃疡，治疗首选药为

关于胆碱酯酶复活药疗效正确的是

某女士，30岁，诊断为甲状腺功能亢进。清晨测得脉率96次／分，血压17．3／9．3kPa(130／70mmHg)。计算基础代谢率属于

按照法律规定，不得在公开开庭时出示的证据是()。

对于一手楼，建筑面积在90m2以下的普通住宅，按揭比例最高不超过购房总价的()。

找出工作绩效差距，制定并实施有针对性的改进计划来提高员工绩效水平的过程称为()。

杯子理论，旨在说明市场需要什么样的杯子厂家就可以生产什么样的杯子，同时不同的杯子只有在相应的市场里才最能发挥其最大价值。根据上述定义，下列选项体现了杯子理论的是()。

路由表包含的一个非常特殊的路由是【　　】。

IP地址块211．64．0．0／11的子网掩码可写为()。

下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[]，int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i