对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。 (63)

admin2019-07-12 34

问题对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。
(63)

选项 A、O(n²)和O(n)
B、O(nlgn)和0(n)
C、O(n²)和O(1)
D、O(nlgn)和O(1)

答案C

解析本题考查算法分析的基础知识。排序和查找是基本的计算问题，存在很多相关的算法，不同的算法适用于不同的场合。不同的数据输入特点相同的算法也有不同的计算时间。若数据基本有序，对插入排序算法而言，则可以在近似线性时间内完成排序，即O(n)；而对于快速排序而已，则是其最坏情况，需要二次时间才能完成排序，即O(nz)。两个算法在排序时仅需要一个额外的存储空间，即空间复杂度均为常数时间复杂度O(1)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。 (63)

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

软考中级

阅读以下说明和C++代码，将应填入(n)处。[说明]在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时，关注此OfficeDoc类对象的相应的DocExplor

根据以上说明设计的实体联系图如下图所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。

下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r:数组元素下标，从p到rq:划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]问题1中伪代码的时间复杂度为(6)(用O符号表示)。

阅读以下说明，回答问题1～2，将解答填入对应的解答栏内。[说明]某程序的功能是输入三个正整数作为边长，判断三条边构成的三角形是否等边、等腰或是一般三角形。

该程序的控制流图中A～E分别是什么?为各测试路径设计测试用例。

请根据标准书号校验码的技术说明，将图5-13和图5-14程序流程图中(1)～(4)空缺处的内容填补完整。假设《应试捷径——典型考题解析与考点贯通_系统分析师考试》书籍标准书号前9个数字为7-121-04715，请写出其对应的校验码。

新旧民主主义革命的分水岭是【】

A．温肺化痰，利气散结B．降气化痰，止咳平喘C．消食导滞，下气祛痰D．滋阴潜阳，理气散结在三子养亲汤中莱菔子配伍的意义是

A．间使B．劳宫C．大陵D．内关手厥阴心包经的原穴是

患者，男，30岁。出现急性发作的畏寒、高热并咳大量脓臭痰，叩诊呈浊音，听诊呼吸音减低，经诊断考虑为血源性肺脓肿。该病最常见的致病菌是

J.C.Raven曾同()工作，并受到其的影响。

absolutetranslation

在标准ASCII码表中，英文字母a和A的码值之差的十进制值是()。

Shynessisthecauseofmuchunhappinessforagreatmanypeople.Shypeopleareanxiousand【B1】______;thatis,theyareexces