快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：分解：选择一个枢轴

admin2015-06-03 44

问题快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：
分解：选择一个枢轴递归求解：通过递归的调用快速排序，对子数组A[p．．q-1]和A[q+1．．r]分别排序。
合并：快速排序在原地排序，故不需合并操作。
(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况?(7)。(最佳、平均、最坏)

选项

答案(4)O(nlgn)或O(nlog₂n)。 (5)O(nlgn)或O(nlog₂n)。 (6)O(n²)。 (7)最坏。

解析

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

本试题收录于：软件设计师下午应用技术考试题库软考中级分类

软件设计师下午应用技术考试

软考中级

相关试题推荐

随机试题

最新回复(0)

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：分解：选择一个枢轴

软件设计师下午应用技术考试

软考中级

由图1-1可见，网络中心与图书馆相距700米，而且两者之间采用千兆连接，那么两个楼之间的通信介质应选择(1)，理由是(2)。备选答案：(1)A．单模光纤B．多模光纤C．同轴电缆D．双绞线校园网在进行IP地址部署

【说明】某公司采用100M宽带接入Internet，公司内部有15台PC机，要求都能够上网。另外有2台服务器对外分别提供Web和E-mail服务，采用防火墙接入公网，拓扑结构如下图所示。

在Windows2003中，(1)不能实现NAT功能。A．终端服务管理器B．Internet连接共享C．路由和远程访问部门B中主机PCI的默认网关地址应配置为(4)才能访问Internet。

为了使DNS_Server1能正确解析本地Web站点的域名，需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中，新建的区域名称是(1)；在图2所示的对话框中，添加的新建主机名称为(2)，IP地址栏应填入(3)。DNS系统中反向查询

请在(1)～(4)空白处填写恰当的内容。DHCP的工作过程是：1)IP租用请求。DHCP客户机启动后，发出一个DHCPDISCOVER消息，其封包的源地址为(1)，目标地址为(2)。2)IP租用提供。当DHCP服务器收到DHCPDI

与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中，路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。以下是在路由器Router1上的部分配置信息，结

解释图10-2中的PVC和SVC。以下是LANE工作过程，其顺序已乱，请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④

如果ping127.0.0.1(本地循环地址)，如果该地址无法Ping通，则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后，经过一段时间等待，系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么

在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示，请将(1)～(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式，根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使

脾胃湿热的舌象是

某散养鸡群，生长发育不良，精神委顿，食欲减退，便秘或下痢，有时见血便。镜检见有大量虫卵，虫卵呈长椭圆形．卵壳厚、光滑，内含一个胚细胞。对该鸡群应用的药物是()

危重病人，突然头额冷汗大出，四肢厥冷，属于

某项目的工程费用为250000万元，按项目进度计划，项目建设期为5年，工程费用比例为第1年10％，第2年20％，第3年30％，第4年30％，第5年10％，建设期内年平均价格上涨指数为6％，则该项目的第3年涨价预备费为()万元。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是()。

《中华人民共和国义务教育法》第三十八条规定，不得参与或变相参与编写教科书的人员是()。①科研人员②中小学教师③国家机关工作人员④教科书审查人员

关于法的起源，下列表述不正确的有()。

十进制数75等于二进制数(　　)。

【B1】【B9】

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下： 分解：选择一个枢轴

软件设计师下午应用技术考试

软考中级

由图1-1可见，网络中心与图书馆相距700米，而且两者之间采用千兆连接，那么两个楼之间的通信介质应选择(1)，理由是(2)。备选答案：(1)A．单模光纤B．多模光纤C．同轴电缆D．双绞线校园网在进行IP地址部署

【说明】某公司采用100M宽带接入Internet，公司内部有15台PC机，要求都能够上网。另外有2台服务器对外分别提供Web和E-mail服务，采用防火墙接入公网，拓扑结构如下图所示。

在Windows2003中，(1)不能实现NAT功能。A．终端服务管理器B．Internet连接共享C．路由和远程访问部门B中主机PCI的默认网关地址应配置为(4)才能访问Internet。

为了使DNS_Server1能正确解析本地Web站点的域名，需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中，新建的区域名称是(1)；在图2所示的对话框中，添加的新建主机名称为(2)，IP地址栏应填入(3)。DNS系统中反向查询

请在(1)～(4)空白处填写恰当的内容。DHCP的工作过程是：1)IP租用请求。DHCP客户机启动后，发出一个DHCPDISCOVER消息，其封包的源地址为(1)，目标地址为(2)。2)IP租用提供。当DHCP服务器收到DHCPDI

与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中，路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。以下是在路由器Router1上的部分配置信息，结

解释图10-2中的PVC和SVC。以下是LANE工作过程，其顺序已乱，请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④

如果ping127.0.0.1(本地循环地址)，如果该地址无法Ping通，则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后，经过一段时间等待，系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么

在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示，请将(1)～(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式，根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使

脾胃湿热的舌象是

某散养鸡群，生长发育不良，精神委顿，食欲减退，便秘或下痢，有时见血便。镜检见有大量虫卵，虫卵呈长椭圆形．卵壳厚、光滑，内含一个胚细胞。对该鸡群应用的药物是()

危重病人，突然头额冷汗大出，四肢厥冷，属于

某项目的工程费用为250000万元，按项目进度计划，项目建设期为5年，工程费用比例为第1年10％，第2年20％，第3年30％，第4年30％，第5年10％，建设期内年平均价格上涨指数为6％，则该项目的第3年涨价预备费为()万元。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是()。

《中华人民共和国义务教育法》第三十八条规定，不得参与或变相参与编写教科书的人员是()。①科研人员②中小学教师③国家机关工作人员④教科书审查人员

关于法的起源，下列表述不正确的有()。

十进制数75等于二进制数( )。

【B1】【B9】

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：分解：选择一个枢轴

十进制数75等于二进制数(　　)。