算法设计与分析(python版)-作业一

参考教材：算法设计与分析（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)