第1章-算法概述 总分:100分 得分:30.0分
1 . 填空题 简单 10分
递归算法必须具备的两个条件是___和___
回答错误
答案
边界条件或停止条件、递推方程或递归方程
2 . 填空题 中等 10分
冒泡排序时间复杂度是___,堆排序时间复杂度是___。
学生答案
O(n^2)、O(nlogn)
回答错误
答案
、 nlogn
3 . 填空题 中等 10分
斐波那契数列的第1项为1,第2项为2,以后每一项等于前面两项之和,则第6项为___
学生答案
13
回答正确
答案
13
1 2 3 5 8 13……
4 . 填空题 简单 10分
算法分析主要是分析算法的性能,包括时间复杂度和___
学生答案
空间复杂度
5 . 填空题 简单 10分
请求解递归式:n>1时,T(n)=2T(n/2)+n,否则T(n)=1,则其θ形式,T(n)=___
学生答案
θ(nlogn)
回答正确
答案
θ(nlogn)
迭代法 比较麻烦,可以选择主定理方法计算;
6 . 填空题 中等 10分
以下递归程序fun(5,0)输出的第一个元素是___,求解过程中最大层次为___ def fun(i,d): if(i>1 and i%2!=0): fun(i-i//2,d+1) if(i>1): fun(i//2,d+1)
答案
1、4
7 . 填空题 中等 10分
求
递推方程的解是___
学生答案
T(n)=θ(n^2)
回答错误
答案
解析文章来源地址https://www.toymoban.com/news/detail-436600.html
8 . 填空题 中等 10分
求递推方程
得到的解是___
学生答案
T(n)=θ(logn)
回答错误
答案
O(logn)
9 . 填空题 中等 10分
求递推方程
得到的解是___
学生答案
T(n)=θ(nlogn)
回答错误
答案
O(nlogn)
10 . 填空题 中等 10分
下面算法最好情况下的时间复杂度___,最坏情况下的时间复杂度为___
def bubble_sort(nums):
for i in range(len(nums) - 1):
swap_flag = False #改进后的冒泡,设置一个交换标志位
for j in range(len(nums) - i - 1):
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
swap_flag = True
if not swap_flag:
return nums #若没有元素交换,则表示已经有序
return nums
学生答案
O(n^2)、O(n)
回答错误
答案
O(n)、<imgsrc="https://cdn1.qingline.net/d61861a5b2faa1ecb1522d77d786eb71.png"/>文章来源:https://www.toymoban.com/news/detail-436600.html
解析
到了这里,关于第一章 算法概述的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!