如果一个数组A[1…n]中某个元素的数量超过其元素数量的一半，称其包含主元素，假设比较两个元素大小的时间不是常数但判定两个元素是否相等的时间是常数，要求对于给定数组A，设计算法判定其是否有主元素，如果有，找到该元素。 （1) 设计时间复杂性为O（nlogn)的算法完成该任务。 （2) 设计时间复杂性为O（n)的算法完成该任务。
题目
如果一个数组A[1…n]中某个元素的数量超过其元素数量的一半，称其包含主元素，假设比较两个元素大小的时间不是常数但判定两个元素是否相等的时间是常数，要求对于给定数组A，设计算法判定其是否有主元素，如果有，找到该元素。 （1) 设计时间复杂性为O（nlogn)的算法完成该任务。 （2) 设计时间复杂性为O（n)的算法完成该任务。
相似考题
更多“如果一个数组A[1…n]中某个元素的数量超过其元素数量的一半，称其包含主元素，假设比较两个元素大小的时间不是常数但判定两个元素是否相等的时间是常数，要求对于给定数组A，设计算法判定其是否有主元素，如果有，找到该元素。 （1) 设计时间复杂性为O（nlogn)的算法完成该任务。 （2) 设计时间复杂性为O（n)的算法完成该任务。”相关问题
-
第1题：
在下列对单链表进行的操作中,算法时间复杂度为O(n)的是()。A、访问第i个元素的前驱(1
B、在第i个元素之后插入一个新元素(1≤i≤n)
C、删除第i个元素(1≤i≤n)
D、对表中元素进行排序
参考答案：A
-
第2题：
给定一组长度为n的无序序列，将其存储在一维数组a[O．．n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较a[O]和a[n-1]，若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值；然后依次比较a[2]和a[n-3]、 a[3]和a[n-4]、…，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小元素，在后n/2个元素查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。
A．动态规划法
B．贪心法
C．分治法
D．回溯法
正确答案：C
解析：本题考查算法设计基础知识。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。分治法的设计思想是：将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题(1k≤n)，且这些子问题互相独立且与原问题相同。递归地求解这些问题，然后将各子问题的解合并得到原问题的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数级时间。动态规划算法，通常可按以下几个步骤进行：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造一个最优解。回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。 -
第3题：
类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为(58)。
A．O(logn)
B．O(nlogn)
C．O(logkn)
D．O(nlogkn)
正确答案：C
-
第4题：
快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （ ） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （请作答此空） 。A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)答案：D解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。
理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O(n)，次操作的总复杂度为O(n2)。 -
第5题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（请作答此空）。
答案：D解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第6题：
给定包含n个正整数的数组A和正整数x，要判断数组A中是否存在两个元素之和等于x，先用插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。low=1;high=n;while（high>low）if A[low]+A[high]=x return true;else if A[low]+A[high]>x low++;else high--;return false;则过程P的时间复杂度为（ ），整个算法的时间复杂度为（请作答此空）。A.O（n）
B.O（nlgn）
C.O（n2）
D.O（n2lgn）答案：C解析：本题考查时间复杂度的基本知识。第一空有一层循环while，遍历判断，所以时间复杂度为n；第二空如图所示：插入排序的时间复杂为O(n2) ;故第一空正确答案为A；第二空正确答案为C；
-
第7题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。 -
第8题：
要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂度为（）
正确答案:O(n) -
第9题：
使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂性为O（）。
正确答案:1；logn -
第10题：
从n个数中选取最大元素（）。
- A、基本操作是数据元素间的交换
- B、算法的时间复杂度是O（n）
- C、算法的时间复杂度是O（n2）
- D、需要进行（n+1）次数据元素间的比较
正确答案:B -
第11题：
填空题要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂度为（）正确答案： O(n)解析： 暂无解析 -
第12题：
问答题给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。正确答案： 我们把这种算法叫做快速选择（quickselect）。令〡Si〡为Si中元素的个数，快速选择的步骤如下：
1）如果〡S〡=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF，则将S排序并返回第k个最小元。
2）选取一个枢纽元v∈S。
3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
4）如果k≤〡S1〡，那么第K个最小元必然在S1中。在这种情况下，返回quickselect（S1，k），如果k=1+〡S1〡
，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第（k-〡S1〡-1）个最小元。我们进行一次递归调用并返回quickselect（S2，k-〡S1〡-1）。
与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O（N=2）。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O（N）。具体分析类似快速排序的分析。
快速排序的实现甚至比抽象描述还要简单，当算法终止时，第k个最小元就在位置k-1上（因为数组开始于下标0）。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。解析： 暂无解析 -
第13题：
对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。
A．O(n)
B． O(n2)
C． O(1)
D． O(log2n)
正确答案：D
解析： 参见有序表采用二分查找时，算法的时间复杂性定义。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等) 。当有序线性表为顺序存储时才能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。 -
第14题：
阅读下列说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数X相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素的下标i和j（注意数组元素的下标从1开始）。 例如，在如下矩阵中查找整数8，则输出伟：True,4,1 2 4 6 9 4 5 9 10 6 7 10 12 8 9 11 13 流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。
【流程图】
【问题】该算法的时间复杂数是（） 供选择答案：A.O（1） B.O（m+n） C.O（m*n） D,O（m²+n²）正确答案：（1）n
（2）j-1→j
（3）i+1→I
（4）j
（5）C
-
第15题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为
，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。A.分治
B.动态规划
C.贪心
D.回溯
正确答案：A
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n/2)+解该递归式，可得时间复杂度为。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-l个元素，此时T(n)=T(n/1)+解该递归式，可得时间复杂度为。 -
第16题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（请作答此空）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（ ）。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第17题：
快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （请作答此空） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （ ） 。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。
理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O(n)，次操作的总复杂度为O(n2)。 -
第18题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.O（n）和O（nlgn）
B.O（n）和O（n2）
C.O（nlgn）和O（nlgn）
D.O（nlgn）和O（n2）答案：D解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。 -
第19题：
对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）
- A、O（n）
- B、O（n2）
- C、O（1）
- D、O（log2n）
正确答案:D -
第20题：
设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O（n）。
正确答案:操作步骤为：
①将所有元素出栈并入队；
②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③将奇数结点出栈并入队；
④将偶数结点出队并入栈；
⑤将所有元素出栈并入队；
⑥将所有元素出队并入栈即为所求。 -
第21题：
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。
正确答案: 我们把这种算法叫做快速选择（quickselect）。令〡Si〡为Si中元素的个数，快速选择的步骤如下：
1）如果〡S〡=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF，则将S排序并返回第k个最小元。
2）选取一个枢纽元v∈S。
3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
4）如果k≤〡S1〡，那么第K个最小元必然在S1中。在这种情况下，返回quickselect（S1，k），如果k=1+〡S1〡
，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第（k-〡S1〡-1）个最小元。我们进行一次递归调用并返回quickselect（S2，k-〡S1〡-1）。
与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O（N=2）。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O（N）。具体分析类似快速排序的分析。
快速排序的实现甚至比抽象描述还要简单，当算法终止时，第k个最小元就在位置k-1上（因为数组开始于下标0）。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。 -
第22题：
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
- A、O（n）
- B、O（nlog2n）
- C、O（1）
- D、O（n2）
正确答案:C -
第23题：
填空题使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂性为O（）。正确答案： 1,logn解析： 暂无解析 -
第24题：
单选题从n个数中选取最大元素（）。A基本操作是数据元素间的交换
B算法的时间复杂度是O（n）
C算法的时间复杂度是O（n2）
D需要进行（n+1）次数据元素间的比较
正确答案： B解析： 暂无解析