算法设计分析D卷 85分

1、.算法设计分析答案一 、 单项选择题1-10 CCCCA ABDAA二 、 判断题 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三 、 填空题1.时间 2.方法 过程 3.插入 交换 4.数据元素 5.*n = temp 6.动态规划算法 7.高级语言编写 8.增大 9.让后面的决策安心地使用前面的局部最优解的一种性质 10. 贪心选择性质四 、 简答题 1. O(n2)2.100n2=2n，解出来n=1/50五 、 问答题1.先设置一个变量 min，用于存放最小数。当输入 a、b、c 三个不相同的数后，先将 a 与 b 进行比较，把小者送给变量 min，再把 c 与 min

2、 进行比较，若 cmin，则 min=c。2.算法中的每一条指令必须有确切的含义题目一 、 单项选择题 (共 10 题、0 / 20 分 )1、设 mi, j 为计算矩阵链Aij 所需的乘法运算次数的最小值，则矩阵链A1n所需的乘法运算次数的最小值为（ ）。A、m1,n+1B、m1,n-1C、m1,nD、m0,n收藏该题2、二分搜索算法是基于（ ）设计的算法。A、穷尽法B、分治法C、动态规划法D、贪心法收藏该题3、直接或间接的调用自身的算法称为（ ）。A、迭代算法B、贪心算法C、递归算法D、动态规划算法收藏该题4、算法分析的两个主要方面是（ ）。A、可读性和文档性B、正确性和简单性C、空间复杂

3、度和时间复杂度收藏该题5、下述关于最优子结构的说法，不正确的是（ ）。A、原问题的最优解通过子问题的非最优解合并而得B、原问题的最优解建立在子问题的最优解基础之上C、原问题的最优解依赖于子问题的最优解D、原问题的最优解包含子问题的最优解收藏该题6、衡量一个算法好坏的标准是( ）。A、时间复杂度低B、运行速度快C、代码短D、占用空间少收藏该题7、阶乘函数用递归定义 Public static int factorial(int n) if(n=0) return 1; return ( ) ; A、n*factorial(n)B、n*factorial(n-1)C、n*factorial(n-2

4、)D、n*factorial(n+1)收藏该题8、实现归并排序利用的算法是（）。A、回溯法B、动态规划法 C、贪心法D、分治策略收藏该题9、衡量一个算法好坏的标准是（ ）。A、时间复杂度低B、占用空间少C、运行速度快D、代码短收藏该题10、如图所示的Huffmann树，字符s的编码是（ ）。A、1110B、010C、1111D、1010收藏该题二 、 判断题 (共 10 题、0 / 20 分 )1、应用Huffmann编码的目的是用更少的比特流表达更多的信息。（ ）正确错误收藏该题2、两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ）正确错误收藏该题3、算法就是一组有穷的规则。( )

5、正确错误收藏该题4、要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。( )正确错误收藏该题5、归并排序算法是渐近最优算法？( )正确错误收藏该题6、最小代价生成树是贪心法的一个经典例子。( )正确错误收藏该题7、当n取值较大时，指数时间算法和多项式时间算法在计算时间上差别不大( )正确错误收藏该题8、基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法要好( )正确错误收藏该题9、T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数n0和c，nn0，有T(n)cf(n)，这种关系记作T(n)=O(f(n)。 （ ）正确错误收藏该题10、任何一个可

6、以用计算机求解的问题所需的计算时间都与其规模有关。( )正确错误收藏该题三 、 填空题 (共 10 题、0 / 10 分 )1、程序的性能一般指程序的空间复杂性和 _ 复杂性。收藏该题2、计算机算法指的是解决问题的 _ 和 _。收藏该题3、写出两种典型的排序法： _ 、 _ 。（其中任意两种即可）收藏该题4、数据的基本单位称为 _ 。收藏该题5、交换两个参数的函数，用c语言实现：Public static void swap (int *m, int *n ) int *temp= m;m=n; _ ;收藏该题6、矩阵连乘问题的算法可由（ ）设计实现。收藏该题7、程序是_用某种程序设计语言的具

7、体实现。收藏该题8、算法的时间复杂度随着问题规模n的增大而 _ 。收藏该题9、最优子结构性质的含义是_。收藏该题10、贪心算法与动态规划算法的主要区别是_。收藏该题四 、 简答题 (共 2 题、0 / 20 分 )1、下面程序段的所需要的计算时间为_ int MaxSum(int n, int *a, int &besti, int &bestj) int sum=0; for(int i=1;i=n;i+) int thissum=0; for(int j=i;jsum) sum=thissum; besti=i; bestj=j; return sum; 收藏该题2、设有两个算法在同一机器上运行，