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




 
 
相关试题     计算机软件知识 

  第56题    2012年下半年  
已知关系模式：图书（图书编号，图书类型，图书名称，作者，出版社，出版日期，ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Computer..

  第65题    2011年上半年  
用插入排序和归并排序算法对数组<3，1，4，1，5，9，6，5>进行从小到大排序，则分别需要 进行（65)次数组元素之间的比较。

  第23题    2019年上半年  
在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4 (假设进程按此顺序到达)，其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3..

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



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

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