问题题干答案解析相关问题热门问题最新问题

问题详情

在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于（）策略的算法。

A、分治

B、动态规划

C、贪心

D、回溯

时间：2021-09-01 12:07 关键词：算法设计和分析中级软件设计师

答案解析

A
分治算法的基本思想是将一个难以直接解决的大问题分解成一些规模较小的小问题以便各个击破，分而治之。分治算法的每一层都有3个步骤：分解、求解和合并。本题的查找算法，不断划分数组，缩小查找范围，可见该算法是基于分治策略的算法。

相关问题

在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于（）策略的算法。
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为（）。
下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（　　　）
论设计模式在软件开发中的应用设计模式描述了在特定场景下解决一般设计问题的类和相互通信的对象。一个设计模式命名、抽象并确定了一个通用设计结构的主要方面，这些设计结构能被用来构造可复用的面向对象设计。现在，设计模式已经广泛地应用在软件开发中。请围绕"设计模式在软件开发中的应用"论题，依次对以下3个方面进行论述： ①概要叙述你参与分析和开发的应用项目，以及你所担任的主要工作。 ②简要介绍设计模式的基本概念及分类，详细说明在你所参与分析和开发的应用项目中应用了哪些设计模式、方法，以及选用它们的原因。 ③分析并讨论使用设计模式的效果，并分析和评价设计模式对软件开发的影响。
通过程序设计活动求解问题时，通常可分为问题建模、算法设计、编写代码和编译调试4个阶段。（）阶段的工作与所选择的程序语言密切相关。