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

admin2019-07-12 38

问题对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://www.kaotiyun.com/show/1hCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

阅读下列说明、图以及Java程序。[说明]某订单管理系统的部分UML类图如下图所示。上图中，Product表示产品，ProductList表示所销售产品的列表，Order表示产品订单，Orderltem表示产品订单中的一个条

阅读下列说明和C++代码，将应填入(n)处的字句写在对应栏内。【说明】已知某类库开发商提供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示。其中，Application类表示应用程序自身，而Docum

(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符号表示)。

阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲构造一文件／目录树，采用组合(Composite)设计模式来设计，得到的类图如6—7所示：【c++代码】#include#include#include

解放生产力和发展生产力的关系是()

透明质酸酶不适合用于

下列凝血因子中，哪一个不是蛋白质

某哮喘患者，伴有严重房室传导阻滞和眼内压升高，应当选用

患者眩晕，精神萎靡，健忘多梦，腰膝酸软，四肢不温，形寒怯冷，舌质淡，脉沉细无力。治疗应首选()

在建筑物区分所有权的内容中，具有主导性的权利是()。

根据《中华人民共和国海关法》规定，在海关监管区和海关附近沿海沿边地区，海关有权检查、扣留有走私嫌疑的运输工具、货物、物品以及走私嫌疑人员。（）

下列关于诉讼时效中止的表述，正确的有()。

公共管理是以政府为核心的各类公共组织为保障和促进公共利益而提供公共产品和公共服务、管理公共事务的所有活动。公共管理的主体不仅包括国家行政机关，而且包括()。