全部科目 > 软件设计师 >
2022年上半年 上午试卷 综合知识
第 62 题
知识点 分治法  
关键词 快速排序   时间复杂度   数组   算法   排序  
章/节 计算机软件知识  
 
 
快速排序算法在排序过程中，以待排序数组的第一个元素作为基准元素，将待排序数组划分为前后两个子数组，前面的子数组中的元素均小于或等于基准元素，后面的子数组中的元素均大于基准元素，划分过程的时间复杂度为(n);继续分别对两个子数组采用快速排序算法进行排序。根据上述摧述，央速排序算法采用了(62)算法设计策略。快返排序算法在最好和最坏情况下的时间复杂度分别为(63
 
  A.  分治
 
  B.  动态规划
 
  C.  贪心
 
  D.  回溯




 
 
相关试题     计算机软件知识 

  第60题    2012年下半年  
拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点vi到vj有一条路径，则顶点vi必然在..

  第27题    2021年下半年  
在磁盘上存储数据的排列方式会影响10服务的总时间。假设每个磁道被划分成10个物理块，每个物理块存放1个逻辑记录。逻辑记录R1,R2....R10存放在同一个磁道上，记录..

  第23题    2023年上半年  
某文件管理系统采用位示图(bitmap)来记录磁盘的使用情况，若计算机系统的字长为64位，磁盘容量为512GB，物理块的大小为4MB，那么位示图的大小为（）个字.

 
知识点讲解
· 分治法
 
        分治法
               递归的概念
               递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。
               递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体。
               分治法的基本思想
               分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破、分而治之。如果规模为n的问题可分解成k个子问题，1<k≤n，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。
               一般来说，分治算法在每一层递归上都有3个步骤。
               （1）分解。将原问题分解成一系列子问题。
               （2）求解。递归地求解各子问题。若子问题足够小，则直接求解。
               （3）合并。将子问题的解合并成原问题的解。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2026 All Rights Reserved
软考在线版权所有