微信小程序第一章 单元测试
1、判断题：
程序运行结果往往与输入相关，所以程序可以不满足确定性（ ）
选项：
A:错
B:对
答案: 【错】
2、多选题：
有关算法分析的事后统计法正确的是（ ）。
选项：
A:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一样的。
B:测试的结果与程序的编译和运行环境有关
C:结果是面向机器，面向程序员，面向语言的
D:结果与测试的样本数据有关
答案: 【测试的结果与程序的编译和运行环境有关
;结果是面向机器，面向程序员，面向语言的
;结果与测试的样本数据有关
】
3、多选题：
下面哪些内容是算法设计之前要完成的内容? ( )
选项：
A:证明算法的正确性。
B:确定合适的数据结构
C:使用何种计算机语言设计程序
D:是求精确解还是近似解
答案: 【确定合适的数据结构
;是求精确解还是近似解
】
4、单选题：
函数10logn3+5logn2的渐近表达式为（ ）：
选项：
A:O(nlogn)
B:O（logn2）
C:O(logn3)
D:O(logn)
答案: 【O(logn)
】
5、单选题：
下列函数根据渐近阶从低到高顺序是（ ）
选项：
A:n1/2 ＜ logn ＜2n ＜n3 ＜3n ＜n!
B:n1/2 ＜ logn ＜2n ＜n3 ＜ n! ＜ 3n
C:logn ＜n1/2＜2n ＜n3 ＜ n! ＜ 3n
D:logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!
答案: 【logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!】
6、判断题：
研究NPC 问题的意义: 一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。( )
选项：
A:对
B:错
答案: 【对】
第二章 单元测试
1、单选题：
直接或间接的调用自身的算法称为（ ）。
选项：
A:贪心算法
B:动态规划算法
C:递归算法
D:迭代算法
答案: 【递归算法
】
2、单选题：
Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（ ）
选项：
A:
B:
C:
D:
答案: 【
】
3、单选题：
分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。
选项：
A:问题规模不同，问题性质不同
B:问题规模相同，问题性质相同
C:问题规模相同，问题性质不同
D:问题规模不同，问题性质相同
答案: 【问题规模不同，问题性质相同
】
4、单选题：
利用二分搜索，最坏情况下的计算时间复杂性为（ ）。
选项：
A:O (n2)
B:O（n）
C:O (logn)
D:O (2n)
答案: 【O (logn)】
5、单选题：
二分搜索算法只适用（ ）存储结构。
选项：
A:堆
B:任意顺序
C:栈
D:顺序
答案: 【顺序】
6、单选题：
使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（ ）。
选项：
A:10
B:1000
C:500
D:11
答案: 【10】
7、单选题：
线性时间选择的时间复杂度为（ ）。
选项：
A:O(n)
B:O （nlogn）
C:O(n2)
D:O(logn)
答案: 【O(n)
】
8、单选题：
利用合并排序，其辅助空间为（ ）：
选项：
A:O(logn)
B:O(nlogn)
C:O（n）
D:O(n2)
答案: 【O（n）】
9、单选题：
利用快速排序，对数的序列{16, 27, 13, 2, 15,38}，选择基准16，进行一次划分，结果为（ ）：
选项：
A:{2, 13, 15} 16 {38, 27}
B:{13, 2, 15} 16 {27, 38}
C:{15, 13, 2} 16 {27, 38}
D:{13, 2, 15} 16 {38,27}
答案: 【{13, 2, 15} 16 {27, 38}
】
10、判断题：
分治策略解决棋盘覆盖问题是一个渐近意义下最优的算法.（ ）
选项：
A:对
B:错
答案: 【对】
第三章 单元测试
1、单选题：
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（ ）。
选项：
A:zk≠xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
B:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。
C:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
答案: 【zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
】
2、单选题：
当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).
选项：
A:7
B:10
C:6
D:9
答案: 【6】
3、单选题：
设有四个矩阵A,B,C,D,它们的维数分别是A=50*10, B=10*40, C=40*30, D=30*50,，则计算其乘积至少需要（ ）次乘法
选项：
A:87500
B:10500,
C:16000,
D:36000,
答案: 【10500,】
4、多选题：
下面关于动态规划解题的步骤内容描述正确的是哪些？（ ）
选项：
A:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。
B:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。
C:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。
D:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。
答案: 【分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。
;构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。
;建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。
】
5、单选题：
问题用动态规划算法求解效率较高的原因？( )
选项：
A:最优子结构性质
B:子问题重叠性质
C:贪心选择性质
D:递归性质.
答案: 【子问题重叠性质】
6、单选题：
对0-1背包问题，n=5，c=12，w={3,7,5,4，4}，v={6,3, 5,4，6 }，则其最优解为（ ）
选项：
A:（1，0，1，0，1）
B:（0，1，0，1，1）
C:（0，1，1，1，1）
D:（1，1，1，1，1）
答案: 【（1，0，1，0，1）
】
7、判断题：
一般来说解同一个问题，动态规划法的效率高于分治算法（ ）
选项：
A:错
B:对
答案: 【错】
8、判断题：
图象的变位压缩存储采用数据头和数据存储的编码式存储方式，节省存储空间，实现压缩。（ ）
选项：
A:对
B:错
答案: 【对】
第四章 单元测试
1、单选题：
在某通讯系统中用到了a，b，c，d，e，f 8个字符，字符频度（百分比）为 45， 13， 12，16，9，5则字符a的编码为( )：
选项：
A:1100
B:0
C:. 111
答案: 【0】
2、单选题：
活动安排问题利用贪心法求解，则其复杂度为（ ）
选项：
A:O(n2)
B:O(logn)
C:O(nlogn)
D:O(n)
答案: 【O(nlogn)】
3、判断题：
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。( )
选项：
A:错
B:对
答案: 【对】
4、判断题：
背包问题与0-1背包问题求解方法类似，都能用贪心法或动态规划方法得到最优解（ ）
选项：
A:错
B:对
答案: 【错】
5、多选题：
有关分治法、贪心算法和动态规划算法的描述，正确的是（ ）
选项：
A:问题能用动态规划法解的不一定能用贪心算法解；
B:贪心算法和动态规划算法共同特征为最优子结构性质;
C:适用三种方法所解的问题都是可分解成子问题的；
D:用贪心法一定能用动态规划法，但是，动态规划法的效率一般高于贪心算法。
答案: 【问题能用动态规划法解的不一定能用贪心算法解；
;贪心算法和动态规划算法共同特征为最优子结构性质;
;适用三种方法所解的问题都是可分解成子问题的；
】
6、多选题：
下列哪些问题能适用贪心法高效求解？ （ ）
选项：
A:0-1背包问题
B:最小生成树问题
C:单源最短路径问题
D:哈夫曼编码问题
答案: 【最小生成树问题
;单源最短路径问题
;哈夫曼编码问题】
第五章 单元测试
1、判断题：
使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界（ ）
选项：
A:对
B:错
答案: 【对】
2、判断题：
适用回溯法解旅行售货员问题，只有当搜索到最后一个城市时，才能判断当前路径是否是该问题的一个解。（ ）
选项：
A:对
B:错
答案: 【错】
3、多选题：
下面关于用回溯法解题说法，正确的是( ).
选项：
A:在搜索过程中动态产生问题的解空间；
B:这种方法适用于解一些组合数相当大的问题。
C:显式地存储整个解空间 ；
D:解空间树有子集树与排列树两种;
答案: 【在搜索过程中动态产生问题的解空间；
;这种方法适用于解一些组合数相当大的问题。
;解空间树有子集树与排列树两种;
】
4、多选题：
回溯法中的剪枝函数包括( )。
选项：
A:限界函数
B:约束函数
C:递归函数
D:随机数生成函数
答案: 【限界函数
;约束函数
】
5、多选题：
回溯法解题步骤,正确的是（ ）
选项：
A:确定最优子结构的性质;
B:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;
C:针对所给问题，定义问题的解空间;
D:确定易于搜索的解空间结构;
答案: 【以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;
;针对所给问题，定义问题的解空间;
;确定易于搜索的解空间结构;
】
6、判断题：
四色定理是第一个主要由计算机证明的理论（ ）
选项：
A:对
B:错
答案: 【对】
第六章 单元测试
1、单选题：
在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是( )。
选项：
A:回溯法和分支限界法
B:回溯法
C:回溯法求解子集树问题
D:分支限界法
答案: 【分支限界法】
2、单选题：
分支限界法与回溯法的相同点是：都是一种在问题的（ ）中搜索问题解的算法。
选项：
A:二叉搜索树T
B:排列树T
C:子集树T
D:解空间树T
答案: 【解空间树T
】
3、多选题：
优先队列式分支限界法解问题时，活结点表的组织形式可能是（ ）。
选项：
A:最小堆
B:数组
C:栈
D:最大堆
答案: 【最小堆;最大堆】
4、判断题：
具有限界函数的广度优先生成搜索解空间树法称为回溯法。（ ）
选项：
A:对
B:错
答案: 【错】
5、判断题：
旅行售货员问题的解空间树是一棵子集树。（ ）
选项：
A:错
B:对
答案: 【错】
请先 ！