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

admin2015-06-03 52

问题快速排序是一种典型的分治算法。采用快速排序对数组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]排序的三个步骤如下：分解：选择一个枢轴

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

软考中级

IPSec工作在TCP/IP协议栈的(1)，为TCP/IP通信提供访问控制、(2)、数据源验证、抗重放、(3)等多种安全服务。IPSec的两种工作模式分别是(4)和(5)。(1)～(5)备选答案：A．应用层B．网络层C．数据链

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

以下是使用E1线路实现多个64Kbit/s专线连接。当链路为T1时，channel-group编号为0～23，Timeslot范围为1～24；当链路为E1时，channel-group编号为0～30，Timeslot范围为1～31．路由器

阅读以下说明，回答【问题1】～【问题4】，将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中，A主机的IP地址是192．155．12．112，B主机的IP地址是192．155．12．120，C主机的IP地址是19

网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2)，根据传入客户端的(3)，以统计方式将其映射到群集主机。当发现到达的数据包时，所有主机同时执行这种映射，以快速

简述网络规划阶段需求分析的方法和解决的问题。(控制在100个字以内)在需求分析过程中应对已有网络的现状及运行情况作调研，如果要在已有的网络上作新的网络建设规划，如何保护用户已有投资?(控制在100个字以内)

L2TP协议是一种基于(1)协议的二层隧道协议，它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上，为了保证传输的可靠性，L2TP协议对控制报文采取了(3)机制，并要求tunne1对端设备在隧道(tunne

在计算机体系结构设计时，通常在CPU和内存之间设置小容量的Cache机制，以提高CPU数据输入输出速率。通常当Cache已存满数据后，新数据必须替换(淘汰)Cache中的某些旧数据。常用的数据替换算法包括________。

在自然环境现状调查中，地理位置调查内容包括()。

根据以下文字资料。回答下列小题。2011年，某省农民人均纯收入达4736．25元，比2005年增加1845．59元，增长63．9％。2012年上半年该省农村居民人均现金收入达到2834．59元，比上年同期增加482．79元，增速比去年同期快5．4

按岗位定员又分为工作岗位定员和()定员。

4，9，15，22，30，39，()

凡携带枪支饮酒的，一律予以开除。()

执行以下语句段后，xy的值是()。intpt，xy；xy=200；pt=&xy；xy=pt+30；

PassageTwo(1)Resultsdayhasatime-wornrhythm,fullofannualtropes:localnewspaperpicturesofenvelope-clutchinggi

Thenewmanagerhadmanydifficultiestoovercomebuthetookthemallinhis______.

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

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

软考中级

IPSec工作在TCP/IP协议栈的(1)，为TCP/IP通信提供访问控制、(2)、数据源验证、抗重放、(3)等多种安全服务。IPSec的两种工作模式分别是(4)和(5)。(1)～(5)备选答案：A．应用层B．网络层C．数据链

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

以下是使用E1线路实现多个64Kbit/s专线连接。当链路为T1时，channel-group编号为0～23，Timeslot范围为1～24；当链路为E1时，channel-group编号为0～30，Timeslot范围为1～31．路由器

阅读以下说明，回答【问题1】～【问题4】，将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中，A主机的IP地址是192．155．12．112，B主机的IP地址是192．155．12．120，C主机的IP地址是19

简述网络规划阶段需求分析的方法和解决的问题。(控制在100个字以内)在需求分析过程中应对已有网络的现状及运行情况作调研，如果要在已有的网络上作新的网络建设规划，如何保护用户已有投资?(控制在100个字以内)

L2TP协议是一种基于(1)协议的二层隧道协议，它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上，为了保证传输的可靠性，L2TP协议对控制报文采取了(3)机制，并要求tunne1对端设备在隧道(tunne

在计算机体系结构设计时，通常在CPU和内存之间设置小容量的Cache机制，以提高CPU数据输入输出速率。通常当Cache已存满数据后，新数据必须替换(淘汰)Cache中的某些旧数据。常用的数据替换算法包括________。

在自然环境现状调查中，地理位置调查内容包括()。

根据以下文字资料。回答下列小题。2011年，某省农民人均纯收入达4736．25元，比2005年增加1845．59元，增长63．9％。2012年上半年该省农村居民人均现金收入达到2834．59元，比上年同期增加482．79元，增速比去年同期快5．4

按岗位定员又分为工作岗位定员和()定员。

4，9，15，22，30，39，()

凡携带枪支饮酒的，一律予以开除。()

执行以下语句段后，xy的值是()。int*pt，xy；xy=200；pt=&xy；xy=*pt+30；

PassageTwo(1)Resultsdayhasatime-wornrhythm,fullofannualtropes:localnewspaperpicturesofenvelope-clutchinggi

Thenewmanagerhadmanydifficultiestoovercomebuthetookthemallinhis______.

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

执行以下语句段后，xy的值是()。intpt，xy；xy=200；pt=&xy；xy=pt+30；