第一周 基础知识(1):算法的基本概念及伪码描述,函数的渐近的界

作业测验

1、考虑下述选择排序算法: 最坏情况下该算法做次交换运算,这种情况在下列哪种输入条件下发生?
    A、数列元素各不相等且递增有序
    B、数列元素各不相等且递减有序
    C、数列元素各不相等且无序
    D、数列所有元素均相等
    E、数列中有相同元素且递增(不减)有序
    F、数列中有相同元素且递增(不减)有序

2、 上述算法所执行的加法次数是:
    A、
    B、
    C、
    D、
    E、
    F、

3、已知是含有个元素并且从小到大排好序的数组,中。如果出现在中第位置的概率是在前一个位置概率的一半,当充分大时,下述查找算法平均情况下的时间复杂度( )。(只需给出近似值)
    A、2
    B、3
    C、4
    D、1
    E、
    F、
    G、

4、下列哪个排序算法在最坏情况下的时间复杂度最低?
    A、插入排序
    B、堆排序
    C、冒泡排序
    D、快速排序

5、下列有关阶乘函数的表述错误的是?
    A、
    B、
    C、
    D、
    E、

6、之间的渐近关系是?
    A、
    B、
    C、
    D、无法确定

7、以下关于函数阶的关系中,哪几项是正确的?
    A、
    B、
    C、
    D、
    E、
    F、

8、下表给出函数, 使得成立的组号(从小到大排列)是:(请直接填写数字序号,例如顺序为,则填写"")

9、下表给出函数, 使得成立的组号(从小到大排列)是:(请直接填写数字序号,例如顺序为,则填写"")

10、下表给出函数, 使得成立的组号(从小到大排列)是:(请直接填写数字序号,例如顺序为,则填写"")

第二周 基础知识(2):序列求和方法,递推方程求解

作业测验

1、递归方程的解的精确值是:
    A、
    B、
    C、
    D、
    E、
    F、

2、的阶是:
    A、
    B、
    C、
    D、
    E、
    F、

3、请用主定理确定递归式的渐近的界:
    A、
    B、
    C、
    D、
    E、

4、给定个数的数组,其中为非负整数,求中的最大数. 考虑下述算法A,先把数组从中间划分成两个个数的数组,在中用同样的算法通过数之间的比较运算找最大数,如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组,在最坏情况下算法A的比较次数是,该算法在最坏情况下的递推方程是:
    A、
    B、
    C、
    D、
    E、
    F、

5、给定个数的数组,其中为非负整数,求中的最大数. 考虑下述算法A,先把数组从中间划分成两个个数的数组,在中用同样的算法通过数之间的比较运算找最大数,如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组,在最坏情况下算法A的比较次数是,则的精确值是?
    A、
    B、
    C、
    D、
    E、
    F、

6、把插入排序算法加以改进,可以得到二分插入排序算法。设输入数组是,插入排序算法的基本操作是:假定的前个数已经排好,将插入。插入时从开始,顺序检查,直到找到插入的合适的位置,将它插入。改进插入排序算法的步骤是:插入的操作不是在中从后向前顺序检索,而是采用二分检索方法找到插入的正确位置。 如果输入规模是,该算法在最坏情况下的比较次数是,那么该算法在最坏情况下的递推方程是
    A、
    B、
    C、
    D、
    E、

7、把插入排序算法加以改进,可以得到二分插入排序算法。设输入数组是,插入排序算法的基本操作是:假定的前个数已经排好,将插入。插入时从开始,顺序检查,直到找到插入的合适的位置,将它插入。改进插入排序算法的步骤是:插入的操作不是在中从后向前顺序检索,而是采用二分检索方法找到插入的正确位置。 如果输入规模是,该算法在最坏情况下的比较次数是,那么该算法在最坏情况下的递推方程的解是?
    A、
    B、
    C、
    D、
    E、
    F、

8、设递推方程给出了算法A在最坏情况下的时间复杂度函数,算法B在最坏情况下的时间复杂度函数满足递推方程,那么要使算法B比算法A具有更高的效率,即时间复杂度的阶低于的阶的最大正整数的值为:

9、给定个数的数组,其中为非负整数,求中的最大数. 考虑下述算法A,先把数组从中间划分成两个个数的数组,在中用同样的算法通过数之间的比较运算找最大数,如果的最大数是,的最大数是,那么就是问题的解。 假设对于个数的数组,在最坏情况下算法A的比较次数是,则的初值是( )?

10、把插入排序算法加以改进,可以得到二分插入排序算法。设输入数组是,插入排序算法的基本操作是:假定的前个数已经排好,将插入。插入时从开始,顺序检查,直到找到插入的合适的位置,将它插入。改进插入排序算法的步骤是:插入的操作不是在中从后向前顺序检索,而是采用二分检索方法找到插入的正确位置。 如果输入规模是,该算法在最坏情况下的比较次数是,那么该算法在最坏情况下的递推方程的初值是( )?

第三周 分治策略(1)

作业测验

1、双Hanoi塔问题是Hanoi塔问题的一种推广,与Hanoi塔的不同点在于:2n个圆盘,分成大小不同的n对,每对圆盘完全相同。初始,这些圆盘按照从大到小的次序从下到上放在A柱上,最终要把它们全部移到C柱,移动的规则与Hanoi塔相同。BiHanoi(A, C, n)的功能是从A移动2n个盘子到C,其中BiMove(A, C)表示从A移动两个盘子到C。下列哪一段代码是利用分治策略给出的正确的移动策略:
    A、
    B、
    C、
    D、

2、给定n个不同数的数组S和正整数i,,求S中最大的i个数,并且按照从大到小的次序输出,现有如下算法, 算法:调用i次找最大算法Findmax,每次从S中删除一个最大的数。该算法在最坏情况下的时间复杂度是:
    A、
    B、
    C、
    D、
    E、

3、给定n个不同数的数组S和正整数i,,求S中最大的i个数,并且按照从大到小的次序输出,现有如下算法, 算法:对S排序,并输出S中最大的i个数。该算法在最坏情况下的时间复杂度是:
    A、
    B、
    C、
    D、
    E、
    F、

4、有n个砝码(其中n为2的幂,即),每个重g克,其中一个不合格(重量可能大于或小于g克). 有一个秤可以称出重物的准确重量. 假设所有的砝码可以同时放到秤上,设计一个算法找出这个不合格的砝码,且秤重的次数达到最少. 采用分治算法,每次取一半砝码(比如t个)称重,如果恰好重tg克,那么不合格的砝码在剩下的砝码中;否则不合格的砝码就在被称重的砝码中. 设n枚砝码的称重次数是T(n),关于T(n)的递推方程是: 括号里应该填:
    A、
    B、
    C、
    D、
    E、

5、在之前n个砝码的题目中(其顺序可能出现在该题之后),在初值T(2)=1条件下,确定:对于给定的n个砝码,找到其中不合格砝码最多需要称重多少次,并选择一个函数填入括号内. 1.png.
    A、
    B、
    C、
    D、
    E、

6、设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. 算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. 算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解. 算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用1.png时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法,需要选择哪个算法?
    A、1
    B、2
    C、3
    D、都不对

7、设问题P的输入规模是n,下述三个算法是求解P的不同的分治算法. 算法1:在常数时间将原问题划分为规模减半的5个子问题,递归求解每个子问题,最多用线性时间将子问题的解综合而得到原问题的解. 算法2:先递归求解2个规模为n-1的子问题,最多用常量时间将子问题的解综合得到原问题的解. 算法3:在常数时间将原问题划分为规模n/3的9个子问题,递归求解每个子问题,最多用1.png时间将子问题的解综合得到原问题的解. 设最坏情况下时间复杂度最低的算法为A,A在最坏情况下的时间复杂度是 1.png
    A、
    B、
    C、
    D、
    E、

第四周 分治策略(2)

作业测验

1、给定含有n个不同的数的数组1.png。如果L中存在2.png,则称L是单峰的,并称3.png是L的“峰顶”。假设L是单峰的,请把a-d四行代码补全到算法中使得算法正确找到L的峰顶。 。 aaaa.png
    A、d, c, a, b
    B、d, c, b, a
    C、c, d, b, a
    D、d, b, c, a
    E、d, a, b, c

2、设信号向量是 ,1.png ,用于平滑处理的权向量是2.png,根据卷积计算公式,处理后的信号向量是3.png,那么4.png的值分别为( ),从下面的项中选择合适的答案:
    A、4.1,5.8,5.5
    B、2.2,8.4,3.2
    C、4.7,4.3,7.7
    D、0.4,3.2,0.6

3、在1.png枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是一个算法找出这枚不合格的硬币,每称1次作为1次基本运算。请把a,b,c三行代码填到算法中正确的位置中。 aaaa.png
    A、c, a, b
    B、c, b, a
    C、a, b, c
    D、b, a, c
    E、b, c, a

4、设 T是n个不等的数构成的数组,现在用分治算法找T的最大数. 先把T从中间划分成两个大小差不多的子数组1.png2.png,递归地求1.png2.png的最大数,分别记作4.png5.png. 比较4.png5.png,那么输出就是3.png. 以元素比较做基本运算,该算法在最坏情况下的时间复杂度的的递推方程是:
    A、1.png
    B、2.png
    C、3.png
    D、4.png

5、找第k小问题的分治算法. 算法开始将n个数分成5个1组,共1.png个组,然后取每组的中位数构成集合M,递归利用找第k小算法,计算M的中位数2.png,用2.png作为标准划分数组,得到子问题3.png4.png. 递归求解其中一个子问题即可. 如果开始分组时是3个元素一组,算法在最坏情况下的时间复杂度将达到5.png,如果开始分组时取7个元素一组,那么用2.png划分数组后产生的子问题最大规模将达到( ),算法在最坏情况下的时间复杂度是( ),两个括号里分别应该填:
    A、11.png
    B、22.png
    C、33.png
    D、44.png

6、1.png 针对表1给定的六个算法的时间复杂度T(n),从表2中选择关于T(n)的正确的递推方程,并将方程所对应的标号a,b,c,d,e,f按照算法一、二、三、四、五、六的顺序填入括号内(填写时6个字母之间不要加任何符号)。

7、1.png1.png 针对表1给定的六个算法的时间复杂度T(n),从表2中选择关于T(n)的正确的递推方程,从表3中选择正确的解,并将解所对应的标号1,2,3,4,5按照算法一、二、三、四、五、六的顺序填入括号内(填写时6个数字之间不要加任何符号).