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

admin2015-06-03 64

问题快速排序是一种典型的分治算法。采用快速排序对数组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．路由和远程访问在服务器2的eth1上启用基本防火墙，如果希望将202.117.12.38固定分配给IP地址为192.1

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

解释图10-2中的PVC和SVC。支持可变比特率(VBR)业务；支持面向连接的业务，其比特率是可变的。常见业务为压缩的分组语音通信和压缩的视频传输。请问根据其业务描述是属子图10-3中高层中的哪一级?

阅读以下有关网络设备安装与调试的叙述，分析设备配置文件，回答问题1至问题3。现以一台远程访问服务器(RemoteAccessServer，RAS)Cisco2509、RJ45为例来说明。第一步，准备安装与调试所需的设备，主要包括RAS

阅读以下应用L2TPv2协议实现VPN安全接入的技术说明，根据要求回答问题1至问题5。【说明】某企业应用L2TPv2协议部署企业的虚拟专用网(VPN)，以方便企业的VIP用户及出差员工通过公共Internet安全地访问企业内部LAN资源，其网络拓

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

丹毒的致病菌是()

建设项目内部控制主要有管理控制、运作控制、()、行为控制四种类型。

目前我国采取复合计税方法的消费品有()。

成交价和成交量是市场行为最基本的表现。()

能在金融市场上简便地转让变现而不招致损失是金融工具的()特性。

()是全面教育法规的“母法”。

AlfredNobel,aSwedishinventorcontributedmostofhisvastfortuneinatrustasafundfromwhichannualprizescouldbeawa

据统计，去年某校参加高考的385名文、理科考生中，女生189人，文科男生41人，非应届男生28人，应届理科考生256人。

Manyresidentsofapartmentcomplexesobjecttonoisyneighbors.

快速排序是一种典型的分治算法。采用快速排序对数组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．路由和远程访问在服务器2的eth1上启用基本防火墙，如果希望将202.117.12.38固定分配给IP地址为192.1

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

解释图10-2中的PVC和SVC。支持可变比特率(VBR)业务；支持面向连接的业务，其比特率是可变的。常见业务为压缩的分组语音通信和压缩的视频传输。请问根据其业务描述是属子图10-3中高层中的哪一级?

阅读以下有关网络设备安装与调试的叙述，分析设备配置文件，回答问题1至问题3。现以一台远程访问服务器(RemoteAccessServer，RAS)Cisco2509、RJ45为例来说明。第一步，准备安装与调试所需的设备，主要包括RAS

阅读以下应用L2TPv2协议实现VPN安全接入的技术说明，根据要求回答问题1至问题5。【说明】某企业应用L2TPv2协议部署企业的虚拟专用网(VPN)，以方便企业的VIP用户及出差员工通过公共Internet安全地访问企业内部LAN资源，其网络拓

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

丹毒的致病菌是()

建设项目内部控制主要有管理控制、运作控制、()、行为控制四种类型。

目前我国采取复合计税方法的消费品有()。

成交价和成交量是市场行为最基本的表现。()

能在金融市场上简便地转让变现而不招致损失是金融工具的()特性。

()是全面教育法规的“母法”。

AlfredNobel,aSwedishinventorcontributedmostofhisvastfortuneinatrustasafundfromwhichannualprizescouldbeawa

据统计，去年某校参加高考的385名文、理科考生中，女生189人，文科男生41人，非应届男生28人，应届理科考生256人。

Manyresidentsofapartmentcomplexesobjecttonoisyneighbors.

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