题海让大学四年没有难题
白天模式登陆

题目详情

单选题 快速排序算法在最好情况下和最坏情况下的时间复杂度分别为 ( )

A. O(logn)和O(n2)

B. O(n)和O(n2)

C. O(nlogn)和O(n)

D. O(nlogn)和O(n2)

算法分析与设计（22级）课程封面

学科：算法分析与设计（22级）

时间：2024-03-31 13:37:18

相关题目

相关作业

题目1
单选题
分治法解选择问题的最好效率属于( )
A. O(n2)B. O(nlogn)C. O(logn)D. O(n)
题目2
单选题
使用分治法求解不需要满足的条件是()
A. 子问题的解可以合并B. 子问题不能够重复C. 子问题必须是一样的D. 原问题和子问题使用相同的方法解
题目3
单选题
对于下列二分查找算法,以下正确的是( )
A. int binarySearch(int a[], int n, int x){ if(n > 0 && x >= a[0]){ int low = 0, high = n-1;while(low < high){ int mid=(low+high+1)/2;if(x < a[mid])high=mid-1;else low=mid;}if(x==a[low]) return low;}return –1;}B. int binarySearch (int a[], int n, int x){ int low=0, high=n-1;while(low<high-1){ int mid=(low+high)/2;if(x<a[mid])high=mid;else low=mid;}if(x==a[low]) return low;else return –1;}C. int binarySearch(int a[], int n, int x){ int low=0, high=n-1;while(low+1!=high){ int mid=(low+high)/2;if(x>=a[mid]) low=mid;else high=mid;}if(x==a[low]) return low;else return –1;}D. int binarySearch(int a[], int n, int x){ int low=0, high=n-1;while(low<=high){ int mid=(low+high)/2;if(x==a[mid]) return mid;if(x>a[mid]) low=mid;else high=mid;}return –1;}
题目4
单选题
以下不可以使用分治法求解的是( )
A. 棋盘覆盖问题B. 选择问题C. 0/1背包问题D. 归并问题
题目5
单选题
快速排序算法在最好情况下和最坏情况下的时间复杂度分别为 ( )
A. O(logn)和O(n2)B. O(n)和O(n2)C. O(nlogn)和O(n)D. O(nlogn)和O(n2)
题目6
单选题
分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分别解决子问题,最后将子问题的解组合起来形成原问题的解.这要求原问题和子问题( )
A. 问题规模相同,问题性质相同B. 问题规模相同,问题性质不同C. 问题规模不同,问题性质相同D. 问题规模不同,问题性质不同
题目7
单选题
在寻找n个元素中第k小元素问题中,如快速排序算法思想,运用分治算法对n个元素进行划分,如何选择划分基准?下面( )答案解释最合理
A. 用中位数的中位数方法寻找划分基准B. 取子序列的第一个元素作为划分基准C. 随机选择一个元素作为划分基准D. 以上皆可行.但不同方法,算法复杂度上界可能不同
题目8
单选题
T(n)表示当输入规模为n时的算法效率,以下算法效率最优的是( )
A. T(n)=3nlog2nB. T(n)= T(n-1)+1,T(1)=1C. T(n)= 2n2D. T(n)= T(n/2)+1, T(1)=1
题目9
单选题
在任何一个2k*2k的棋盘覆盖中,用到的L型骨牌个数恰好为( )
A. (4K-1)/2B. (2K-1)/3C. (2K-1)/2D. (4K-1)/3
题目10
单选题
快速排序时,如果所有元素都相等,这时取得的效率属于( )
A. 无法判断B. 最差效率C. 最优效率D. 两者都不是
Copyright © 2022 津ICP备2021001502号