参考教材：算法设计与分析（Python版） 作者：王秋芬
1 . 容易 （4分）2 n=O(100n ^2)
错误
2 . 容易 （3分）10=θ(log10)
正确
3 . 容易 （3分）2^n=O(3 n)
正确
4 . 容易 （3分）logn^ 2=θ(logn+5)
正确
5 . 容易 （3分）针对顺序查找算法，影响它时间复杂度的因素只有算法的输入序列()
错误
因素有：输入序列、问题规模
6 . 容易 （3分）n!的时间复杂度为O(n)
正确
7 . 容易 （3分）递归是指自己间接或直接调用自身
正确
8 . 普通 （3分）算法的基本特征有（）
A. 输入
B. 输出
C. 有限性
D. 确定性
E. 可行性
9 . 普通 （3分）渐进复杂性的含义是（）情况下的复杂性。
A. 在最佳输入情况下
B. 问题规模趋向于无穷
C. 在最坏输入情况下
D. 平均各种输入之后
10 . 普通 （3分）n个连续自然数a1...an连加和问题算法（利用等差数列求和公式）的输入可以是什么（）。
A. a1，n
B. an,n
C. a1,an
D. a1,an,n
11 . 普通 （3分）平均时间复杂度是指（）
A. 各种情况时间复杂度按概率的加权平均
B. 最好情况和最坏情况的时间复杂度的算术平均
C. 各种情况时间复杂度按概率的算术平均
D. 出现可能性最高的情况下的时间复杂度
平均时间复杂度是指各种情况时间复杂度按概率的加权平均
12 . 容易 （3分）算法的常见描述方式不包括（）
A. 代码
B. 甘特图
C. 伪代码
D. 流程图
13 . 容易 （3分）算法的基本特性不包括（）
A. 先进性
B. 有穷性
C. 有输入输出
D. 无二义性
算法的特性包括有输入输出，确定性（无二义性），有限性（有穷性），可行性（能行性）。
14 . 普通 （3分）阶乘问题求n!算法的时间复杂度为（）。
A. n
B. n!
C. 2n
D. n^2
15 . 容易 （3分）二分搜索（二分查找）算法的时间复杂度是（）。
A. n
B. logn
C. n^2
D. 2n
16 . 普通 （3分）汉诺塔问题的时间复杂度是（）。
A. n!
B. 2^n
C. 2n
D. logn
17 . 容易 （3分）下述描述算法的方式采用的是算法的哪种描述方式（）？ 算法：gcd(m,n) 输入：非负整数m,n，其中m,n不全为0 输出：m与n的最大公约数 1.while m>0 do 2. r←n mod m 3. n ←m 4. m ←r 5.return n
A. 自然语言
B. 程序流程图
C. 伪码
D. 程序设计语言
18 . 普通 （3分）背包问题的算法设计策略是（）
A. 重量小的优先装
B. 价值大的优先装
C. 单位重量价值大的优先装
D. 以上都不对
19 . 容易 （3分）调度问题的算法设计策略是（）
A. 加工时间短的优先安排
B. 加工时间长的优先安排
C. 等待时间短的优先安排
D. 以上都不对
20 . 普通 （3分）n个元素的冒泡排序代码如下：
def bubble_sort(arr): for i in range(len(arr) - 1): for j in range(len(arr) - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr
请分析算法的时间复杂度，用O表示（）
A. O(1)
B. O(n)
C.
D. O(nlogn)
n-1次冒泡 第一次比较n-1次 第二次比较n-2次 ......... 最后一次比较1次 共1+2+3+......+(n-1)
学生答案
21 . 普通 （3分）百元买白鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？设计一算法，则该算法的输入是（）
A. 100元
B. 100只鸡
C. 各种鸡的单价
D. 无需任何输入
22 . 普通 （3分）下面算法最好情况下的时间复杂度___，最坏情况下的时间复杂度为___
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)、O(n^2)
23 . 普通 （3分）以下递归程序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
24 . 普通 （3分）斐波那契数列的第1项为1，第2项为2，以后每一项等于前面两项之和，则第6项为___
13
25 . 普通 （3分）冒泡排序时间复杂度是___，堆排序时间复杂度是___。
O(n^2) 、nlogn
26 . 容易 （3分）递归算法必须具备的两个条件是___和___
边界条件或停止条件、递推方程或递归方程
27 . 普通 （3分）用O表示21+1/n的阶(O(1))
O(1)
28 . 普通 （3分）用O表示10log3 n的阶()
O(n)
29 . 普通 （3分）用O表示logn 3的阶()
O(logn)
30 . 容易 （3分）用O表示
的阶___
O(2^n)
31 . 容易 （3分）用O表示3n2+10n的阶___
O(n^2)
32 . 普通 （3分）请分析选择排序算法的时间复杂度，用O表示为:___
def selection_sort(arr):
# 第一层for表示循环选择的遍数
for i in range(len(arr) - 1):
# 将起始元素设为最小元素
min_index = i
# 第二层for表示最小元素和后面的元素逐个比较
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标
min_index = j
# 查找一遍后将最小元素与起始元素互换
arr[min_index] , arr[i] = arr[i] , arr[min_index]
return arr
O(n^2)
33 . 普通 （3分）请分析下面算法的时间复杂度：
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
最好情况下，比较n-1次，时间复杂度为O(n) 最坏情况下，比较n(n-1)/2次,时间复杂度为O(n^2)