admin 管理员组文章数量: 887021
算法
目录
一.单选题
二.多选题
补充的题
知识点
一.单选题
1
【单选题】n个元素最小值问题的分治算法分解方法错误的是()。
- A、
划分为2个规模大致相等的子问题
- B、
从中间将n个元素划分为两部分
- C、
n个元素的位置下界left、上界right,分解操作为(left+right)/2
- D、
将n个元素分解为多个子问题,子问题之间不独立
正确答案： D
2
【单选题】有关2个n位大整数乘法问题说法错误的是()。
- A、
将两个n位大整数分解为4个规模大致相等的n/2位整数的整数乘法问题。
- B、
递归解决4个子问题。
- C、
子问题的解需要归并成原问题的解。
- D、
子问题的解本身就是原问题的解。
正确答案： D
【单选题】有关快速排序的分治算法描述错误的是()。
- A、
快速排序A[left,right],选取基准元素的方法,将待排序元素分解为两个子问题。
- B、
快速排序基准元素的选取可以是待排序元素中的任何一个元素。
- C、
快速排序划分的两个子问题规模大致相等。
- D、
快速排序A[left,right],递归算法的边界条件是left<right
正确答案： C
4
【单选题】下述关于二分查找(折半查找)算法描述错误的是( )
- A、
二分查找是在任意给定的n个元素序列中查找指定元素。
- B、
二分查找的序列为A[left,right],分解操作为:(right-left)/2
- C、
二分查找根据比较的结果,好的情况是相等,算法结束。坏的情况是进入其中一个子问题继续查找。
- D、
若二分查找的序列为A[left,right],用递归来解决子问题,则边界条件是left>right。
正C
5
【单选题】根据下面斐波那契数列的递归算法，可知斐波那契数列的第n项的递归式为（）。
def Fibonacci(int num):
if(num == 0 || num == 1):
return num
return Fibonacci(num-1)+Fibonacci(num - 2)
- A、
Fibonacci(n)=0 当n=0时
- B、
Fibonacci(n)=1 当n=1时
- C、
Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2) 当n〉1时
- D、
Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3) 当n〉1时
正确答案： C
6
【单选题】棋盘覆盖问题的分解方法为（）。
- A、
将2^k*2^k的棋盘分解为2个2^(k-1)*2^k
- B、
将2^k*2^k的棋盘分解为2个2^k*2^(k-1)
- C、
将2^k*2^k的棋盘分解为4个2^(k-1)*2^(k-1)
- D、
以上分解的方法都不对
正确答案： C
7
【单选题】关于快速排序分治算法时间复杂度描述错误的是()
- A、
快速排序分治算法最好情况下的时间复杂度为O(nlogn).
- B、
快速排序分治算法最坏情况下的时间复杂度为O(n 2).
- C、
快速排序分治算法平均情况下的时间复杂度为O(n 2).
- D、
快速排序分治算法平均情况下的时间复杂度为O(nlogn).
正确答案： C
【单选题】二分合并排序算法时间复杂度的是()
- A、
O(logn)
- B、
O(nlogn)
- C、
0(logn^2)
- D、
0(n^2)
正确答案： B
9
【单选题】分治算法核心就是分而治之,其中的“治”描述错误的是( )。
- A、
分治法通过治理小问题来治理大问题。
- B、
分治法递归治理小问题。
- C、
分治法需要将子问题的解归并成大问题的解。
- D、
治理子问题时,会有重复性治理子问题的现象。
正确答案： D
10
【单选题】
以下代码功能为合并排序,请根据注释按照数顺序选择合适的语句填入对应的括号。
{def MergeSort(A, low, high):
if (low < high):
()#分解
()# 递归序列左半部分
()# 递归序列右半部分
Merge(A, low, middle, high)# 子问题的解合并成原问题的解}
- A、middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);
- B、middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);
- C、middle=(low+high)/2;MergeSort(A,middle+1,high); MergeSort(A,low,middle);
- D、middle=(high-low)/2;MergeSort(A,middle+1,high); MergeSort(A,low,middle);
正确答案： B
答案解析：
11
【单选题】大整数A和B的乘法,将A分成位数大致相等的两部分A1和A2 ,将B分成位数大致相等的两部分B1和B2,以下描述错误的是()。
- A、
4个子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2(A1B2+A2B1)+A2B2
- B、
3个子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2((A1-A2)(B2-B1)+A1B1+A2B2)+A2B2
- C、
3个子问题的解归并为原问题解的方法为:A×B=10nA1B1+10n/2((A1+A2)(B1+B2)-A1B1-A2B2)+A2B2
- D、
划分3个子问题比划分4个子问题时间复杂度低
正确答案： C
【单选题】分治算法的基本思想描述错误的是( )
- A、分治法将规模大的问题分解成规模较小的问题解决。
- B、分治法划分的小问题相互重叠。
- C、分治法一般采用递归的方法解决子问题。
- D、分治法划分的小问题规模小到一定程度时可以直接解决。
正确答案： B
答案解析：
二.多选题（共3题,20.8分）
1
【多选题】分治算法的思想是()
- A、
将规模较大的问题划分为规模较小的相同子问题。
- B、
子问题之间相互独立。
- C、
子问题之间不相互独立。
- D、
递归解决划分得到的子问题
- E、
有些子问题的解需要归并得到原问题的解
正确答案： ABDE
2
【多选题】分治算法的步骤有()
- A、
分解。
- B、
治理。
- C、
递归。
- D、
贪心。
正确答案： AB
3
【多选题】n个元素最小值问题的分治算法分解方法为（）
- A、
划分为2个规模大致相等的子问题
- B、
从中间将n个元素划分为两部分
- C、
如果n个元素的位置下界left、上界right，那么每次分解操作为(left+right)/2
- D、
将n个元素分解为多个子问题，子问题之间不独立
正确答案： ABC
补充的题
知识点
-
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
-
二分查找的时间复杂度为O(logn)。
二分查找算法的算法思维:
1.首先查找数组必须是有序的(假设为升序)。
2.取查找数组中间的数作为基准,如果需要查找的数据大于基准说明该数存在于 数组的左边。反之存在于基准右边。
3 假设待查找的数小于基准,那么将基准换成左子数组的中间的数，重复步骤2，直到找到该数。
本文标签： 算法
版权声明：本文标题：算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686521868h5460.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论