给定n个整数构成的数组A={a1，a2，……，an}和整数x，判断A中是否存在两个元素ai和aj，使的ai+aj=x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在ai+aj=x，具体的方法如下列伪代码所示。则求解该问题时排序算

admin2019-07-12 51

问题给定n个整数构成的数组A={a₁，a₂，……，a_n}和整数x，判断A中是否存在两个元素ai和aj，使的ai+aj=x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在a_i+a_j=x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了(62)算法设计策略，整个算法的时间复杂度为(63)。
i=1;j=n
WhileiIfrdi+ai=xretumtree
Els
(63)

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

答案B

解析分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分支算法的时间复杂度为O(nlgn)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

下图为DARPA提供的公共入侵检测框架示意图，该系统由四个模块组成，其中模块①～④对应的正确名称为____________。

把IP网络划分成子网的好处是(55)________________。

ARP表用于缓存设备的IP地址与MAC地址的对应关系，采用ARP表的好处是__________。(2011年下半年试题)

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(3)

使用Telnet协议进行远程登陆时需要满足的条件不包括()。

默认情况下，Linux系统中用户登录密码信息存放在______文件中。

在距离矢量路由协议中，每一个路由器接收的路由信息来源于____________。

下图是一个软件项目的活动图，其中顶点表示项目里程碑，联结顶点的边表示包含的活动，则里程碑(1)在关键路径上，活动FG的松弛时间为(2)。(1)

软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分，与其最相适应的软件开发方法是(9)。

阅读下列说明、图和c++代码。[说明]某订单管理系统的部分UML类图如下图所示。上图中，Product表示产品，ProductList表示产品目录，Order表示产品订单，OrderItem表示产品订单中的一个条目，Or

下列关于代理的叙述中，不正确的是()。

关于工程分包的说法，正确的有()。

在所有网元功能测试完成后，进行的语音业务测试是()类业务。

常用的建设工程项目施工成本计划的编制依据包括()。

房地产市场的租金水平,类似于所开发房地产的地产未来月租金纯收益为200元/平方米,该房产总建筑面积7500平方米,该类房地产的还源率为7%,出租率为70%,则所开发房地产的总价可确定为()。

控制的最好方法是()。

将一个正方形分成9个小正方形，填上1到9这9个自然数，使得任意一个横行、一个纵列以及每一对角线上的3个数之和等于15，请问位于中间的小正方形应填哪个数?()

[2012年]设A为三阶矩阵，P为三阶可逆矩阵，且P-1AP=.若P=[α1，α2，α3]，Q=[α1+α2，α2，α3]，则Q-1AQ=()．

MarioDeLibertyhadbeenlivingasmallbusinessman’sdream.Twenty-oneyearsagoheopeneduptheWestgatePubinHavertown,Pe

A、Thematerialsforindoorplumbinghavebeenimproved.B、Thehousesrecentlybuiltaremuchmoresolid.C、Peoplewon’tgoanywh