第一章测试1【判断题】(10分)一个问题的同一实例可以有不同的表示形式A.错B.对2【判断题】(10分)同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A.错B.对3【判断题】(10分)问题的两个要素是输入和实例。
A.对B.错4【单选题】(10分)算法与程序的区别是（）A.有穷性B.确定性C.输出D.输入5【单选题】(10分)解决问题的基本步骤是（）。
（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明A.(3)(1)(5)(4)(2)B.(3)(4)(1)(5)(2)C.(1)(2)(3)(4)(5)D.(3)(1)(4)(5)(2)6【单选题】(10分)下面说法关于算法与问题的说法的是（）。
A.算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
B.证明算法不正确，需要证明对任意实例算法都不能正确处理。
C.如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
D.同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
7【多选题】(10分)下面关于程序和算法的说法正确的是（）。
A.算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B.程序总是在有穷步的运算后终止。
C.程序是算法用某种程序设计语言的具体实现。
D.算法是一个过程，计算机每次求解是针对问题的一个实例求解。
8【多选题】(10分)最大独立集问题和（）问题等价。
A.最大团B.稳定匹配问题C.区间调度问题D.最小顶点覆盖9【多选题】(10分)给定两张喜欢列表，稳定匹配问题的输出是（）。
A.完美匹配B.最大匹配C.稳定匹配D.没有不稳定配对10【单选题】(10分)问题变换的目的有（）。
(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难解变易解（5）以上都是。
A.（5）B.（1）C.（2）D.（3）E.（4）11【单选题】(10分)按照霍纳法则，计算p(x)=a n x n+a n-1x n-1+…+a1x1+a0的数量级为____。
A.nB.n^2C.lognD.nlogn第二章测试1【判断题】(10分)时间复杂度是指算法最坏情况下的运行时间。
A.错B.对2【判断题】(10分)f(n)=3n3+7n2+4nlogn=O（n2）A.错B.对3【判断题】(10分)如果一个算法是多项式时间算法，该算法是有效的,是好算法。
A.错B.对4【单选题】(10分)算法复杂度分析的两种基本方法为（）和（）。
A.几何复杂度平均复杂度B.平摊复杂度平滑复杂度C.事后统计事前分析D.结构化方法面向对象方法5【单选题】(10分)下面程序的时间复杂度为（）x=1fori=1tondoforj=1toidofork=1tojdox++A.O(n)B.O(n^2)C.O(n^3)D.O(nlogn)6【单选题】(10分)对近似递增序列的线性表从小到大排序，使用哪种方法好？A.插入排序B.堆排序C.快速排序D.归并排序7【多选题】(10分)顺序查找适合的数据结构是（）A.压缩存储B.散列存储C.链式存储D.顺序存储8【单选题】(10分)给定n个元素的数组A，n=10^3,使用折半查找比使用顺序查找大约快___倍。
A.100B.10C.1000D.10^(3/2)9【单选题】(10分)则f(n)的渐进性态f(n)=Ω()A.nB.n^2C.1D.10010【判断题】(10分)f=O(g)当且仅当g=Ω(f)A.对B.错第三章测试•第1部分•总题数:121【判断题】(10分)0-1背包问题的枚举算法的时间复杂度为O（2n）A.对B.错2【判断题】(10分)增量构造法生成子集前需要对集合中元素从小到大排列。
A.错B.对3【判断题】(10分)分块查找一般设分块的长度是n/2.A.错B.对4【判断题】(10分)枚举法适用于问题的小规模实例。
A.错B.对5【单选题】(10分)便于实现集合操作的子集生成算法是（）A.增量构造法B.二进制法C.位向量法6【单选题】(10分)从所有候选答案中去搜索正确的解，这是（）算法。
A.递推B.枚举C.蛮力7【单选题】(10分)l o g n2=()(l o g n+5)A.OB.θC.oD.w8【单选题】(10分)0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？A.40B.60C.30D.509【多选题】(10分)分数拆分问题的枚举算法通过（）方法进行了优化。
A.减少枚举变量的值域B.优化数学模型C.优化数据结构D.减少枚举变量10【多选题】(10分)下面那些算法的时间复杂度为O（）?A.折半插入排序B.顺序查找C.冒泡排序D.插入排序E.折半查找11【单选题】(10分)A公司处理器速度是B公司的100倍。
对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是（）A.10nB.100nC.nD.n^212【判断题】(10分)冒泡排序的时间复杂度为Ω(n^2)A.错B.对第四章测试1【判断题】(10分)贪心算法总能找到可行解，但未必是最优解。
A.错B.对2【判断题】(10分)贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
A.对B.错3【判断题】(10分)问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
A.对B.错4【判断题】(10分)Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
A.错B.对5【单选题】(10分)贪心算法基本要素有（）和最优子结构性质。
A.分解合并性质B.重叠子问题性质C.独立子问题性质D.贪心选择性质6【单选题】(10分)下面不是证明贪心算法证明方法的有（）。
A.领先B.优化C.界D.交换论证7【多选题】(10分)最小生成树问题可以使用的算法有（）A.SolimB.KruskalC.DijkstraD.Prim8【多选题】(10分)区间问题包含()A.区间调度B.区间覆盖C.区间选点D.区间划分9【判断题】(10分)负权的单源最短路问题可以使用Dijkstra算法求解A.对B.错10【判断题】(10分)设C是一个环，f是C中的最大边，那么最小生成树中肯定包含f。
A.错B.对第五章测试1【判断题】(10分)正推是从小规模的问题推解出大规模间题的一种方法。
A.对B.错2【判断题】(10分)一般来说，递归的效率高于递推。
A.对B.错3【单选题】(10分)从大规模问题逐步化为小规模问题的算法是（）A.正推B.迭代C.递归D.倒推4【单选题】(10分)求解高阶递推方程一般使用（）迭代方法A.差消迭代B.换元迭代C.直接迭代5【多选题】(10分)递归函数的要素是（）A.迭代B.边界条件C.递归方程D.输入6【多选题】(10分)递归变为非递归的方法有（）A.循环B.递推C.模拟栈D.尾递归7【多选题】(10分)T(n)=T(n-1)+n，T(1)=1，则T(n)=（）A.n(n+1)/2B.O(n^2)C.Ω(n^2)D.θ(n^2)8【多选题】(10分)递归一般用于解决问题有（）A.问题解法按递归实现B.数据的结构形式是按递归定义的C.数据的定义是按递归定义的D.迭代问题9【单选题】(10分)主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方程，则下列关于方程中的约束中不准确的是？设A.对于系数a，必须满足a>=1B.对于系数b，必须满足b>1C.若f(n)=O(x)，则T(n)=Θ(xlogn)D.若对于常数e>0，f(n)=O(y)，则T(n)=Θ(x)10【单选题】(10分)，则T(n)=（）A.O(nlogn)B.O(n)C.Θ(n^2)D.Ω(n^3)11【判断题】(10分)循环用于重复性的工作。
循环体的特点是：“以不变应万变”。
A.对B.错第六章测试1【判断题】(10分)分治法分解的子问题与原问题形式相同。
A.错B.对2【判断题】(10分)N个元素排序的时间复杂度不可能是线性时间。
A.错B.对3【判断题】(10分)三分法的判定树是三叉树。
A.对B.错4【判断题】(10分)减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)A.对B.错5【单选题】(10分)设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()法。
A.冒泡排序B.快速排序C.基数排序D.合并排序6【单选题】(10分)堆排序的时间复杂度是O（）。
A.O（nlogn）B.O（2n）C.O（n2）D.O（n）7【单选题】(10分)改进分治算法的方法有（）和改进划分的对称性。
A.备忘录B.加速原理C.拟阵原理D.减少子问题数8【多选题】(10分)通过减少子问题个数，降低分治算法时间复杂度的有（）A.大整数乘法B.Strassen矩阵乘法C.最接近点对D.线性时间选择9【多选题】(10分)分治法在每一层递归上有三个步骤（）A.合并B.分解C.选择D.解决10【单选题】(10分)使用分治法求解不需要满足的条件是（）。
A.子问题不能够重复B.子问题的解可以合并C.原问题和子问题使用相同的方法求解D.子问题必须是一样的11【判断题】(10分)最小堆中每个元素调整的次数不超过树高。
A.对B.错12【判断题】(10分)分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。
A.错B.对13【判断题】(10分)任何排序算法至少需要O(nlogn)次比较。
A.对B.错14【单选题】(10分)找n个元素的中位数的分治算法的时间复杂度为O().A.nlognB.C.n^2D.logn第七章测试1【判断题】(10分)动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
A.错B.对2【判断题】(10分)0/1背包问题的动态规划算法是多项式时间算法。
A.B.对3【判断题】(10分)对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA 算法。
A.错B.对4【判断题】(10分)Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
A.错B.对5【单选题】(10分)含负权的最短路问题一般使用（）求解。
A.动态规划B.网络流算法C.贪心算法D.分治算法6【单选题】(10分)动态规划算法的基本要素有（）和最优子结构性质。
A.分解合并性质B.独立子问题性质C.重叠子问题性质D.贪心选择性质7【单选题】(10分)下面不是动态规划的基本方法有（）。
A.增加变量B.多重选择C.区间变量D.舍入8【多选题】(10分)最短路算法中适用于稀疏图的是（）A.Dijkstra算法B.Bellman算法C.Floyd算法D.SPFA算法9【多选题】(10分)分治算法与动态规划算法的相同点是（）A.最优子结构B.子问题重叠C.子问题独立D.递推关系10【判断题】(10分)DAG上最短路，固定起点和终点没有意义。