Wu201451082127_矩阵连乘问题中,a1矩阵大小是100*5,a2矩阵大小为5*30,a3矩阵大小为30*10,则乘法次

1、【单选题】调度问题:n个任务按某一调度依次在一台机器上加工的算法设计策略是（）
A、加工时间短的优先安排
B、加工时间长的优先安排
C、等待时间短的优先安排
D、以上都不对（）
正确答案： A  
2、【单选题】【单选题】n个元素的集合有多少个不同的子集?
A、2^n
B、n!
C、n^2
D、n
正确答案： A  
3、【单选题】描述算法不能用
A、鸟语
B、计算机算法语言
C、人类自然语言
D、接近计算机语言的伪语言
正确答案： A  
4、【单选题】算法的常见描述方式不包括(  )
A、代码
B、甘特图
C、伪代码
D、流程图
正确答案： B 
6、【单选题】子程序（包括函数和方法）是用来被调用的，递归指的是
A、不同子程序之间直接或间接调用的程序设计方法
B、同一个子程序直接或间接调用自己的程序设计方法
C、子程序向调用它的程序段返回结果的程序设计方法
D、子程序不向调用它的程序段返回结果的程序设计方法
正确答案： B  
7、【单选题】渐进复杂性的含义是（）情况下的复杂性。
A、在最佳输入情况下
B、问题规模趋向于无穷大
C、在最坏输入情况下
D、平均各种输入之后
正确答案： B  
8、【单选题】分析算法的空间复杂性，应该分析
A、算法在执行过程中存储空间的总占用量
B、算法运行代码占用的存储量
C、算法在执行过程中数据空间的占用量
D、算法中定义的变量的数量
正确答案： C  
10、【单选题】用一重循环累乘求阶乘问题。n!算法的时间复杂度为()。(单选题)
A、2n
B、n!
C、n
D、n^2
正确答案： C  
11、【单选题】“时间复杂度”通常指的是算法在哪种情况下的时间复杂度
A、最好
B、最坏
C、平均
D、各种情况的加权平均
正确答案： B  
12、【单选题】算法的基本特性不包括()(单选题)
A、先进性
B、有穷性
C、有输入输出
D、无二义性
正确答案： A  
14、【单选题】算法分析主要分析的是
A、算法运行时的时间效率
B、算法的设计难度
C、算法中遗留的缺陷
D、算法设计的巧妙程度
正确答案： A  
15、【单选题】下述描述算法的方式采用的是算法的哪种描述方式（）？
 算法：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、程序设计语言
正确答案： C  
1、【单选题】允许使用递归程序设计方法的算法语言必须
A、将局部变量和形式参数都分配在系统栈里
B、将局部变量分配在系统栈里，将形式参数分配在系统堆里
C、将局部变量分配在系统堆里，将形式参数分配在系统栈里
D、将局部变量和形式参数都分配在系统堆里
正确答案： A  
3【单选题】算法的空间复杂性分析，通常只考虑
A、算法代码占用的存储空间
B、算法中定义的变量的数量
C、算法在执行过程中所需的辅助变量占用的存储空间
D、算法在执行过程中输入输出数据占用的存储空间
正确答案： C  
4、【单选题】算法分析主要分析的是
A、算法运行时的时间效率
B、算法的设计难度
C、算法中遗留的缺陷
D、算法设计的巧妙程度
正确答案： A  
5、【单选题】子程序（包括函数和方法）是用来被调用的，递归指的是
A、子程序向调用它的程序段返回结果的程序设计方法
B、子程序不向调用它的程序段返回结果的程序设计方法
C、同一个子程序直接或间接调用自己的程序设计方法
D、不同子程序之间直接或间接调用的程序设计方法
正确答案： C 
8、【单选题】平均时间复杂度是指( )
A、各种情况时间复杂度按概率的加权平均
B、最好情况和最坏情况的时间复杂度的算术平均
C、各种情况时间复杂度按概率的算术平均
D、出现可能性最高的情况下的时间复杂度
正确答案： A  
10、【单选题】若某算法各语句执行频度之和为，则该算法的时间复杂度为
A、O()
B、O(3)
C、O(3+5n)
D、O(3+5n+9)
正确答案： A 
12【单选题】背包问题: n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装入背包,使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是(  )
A、重量小的优先装入背包
B、体积小的优先装入背包
C、价值大的优先装入背包
D、单位重量的价值大的优先装入背包
正确答案： D 
16、【单选题】根据下面斐波那契数列的递归算法,可知斐波那契数列的第n项的递归式为()。
def Fibonacci(int num):
if(num == 0 || num == 1):
return num
return Fibonacci(num-1)+Fibonacci(num - 2)(单选题)
A、Fibonacci(n)=0 当n=0时
B、Fibonacci(n)=1 当n=1时
C、Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2) 当n〉1时
D、Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3) 当n〉1时
正确答案： C  
1、【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,kruskal算法的时间复杂度为()
A、O(n 2)
B、O(n 3)
C、O(eloge)
D、O(nlogn)
正确答案： C 
2、【单选题】给定一个无向连通带权图G=(V,E),n个顶点,e条边,Prim算法的时间复杂度为()
A、O(n 2)
B、O(n 3)
C、O(eloge)
D、O(nlogn)
正确答案： A 
3关于Prim算法和Kruskal算法的比较，正确的是
A、两个算法的时间复杂度相同
B、Prim算法适用于稠密图，Kruskal算法适用于稀疏图
C、Kruskal算法的时间复杂度是用顶点个数决定的
D、Prim为了提高贪心选择时查找最短边的效率，首先将图中的所有边按权值排序。
正确答案： B 
4、【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
这是经过多少次贪心选择之后得到的结果。（C）
A、1
B、2
C、3、
D、4
正确答案： C 
5、【单选题】单源最短路径问题算法中,采用了前驱pre数组,用于记录（）
A、当前最短路径长度
B、图中每个顶点的前驱
C、特殊路径
D、以上都不对
正确答案： B 
6、【单选题】调度问题:有n个客户带来n项任务,每项加工时间已知,设为ti,i=1,2,…,n。从0时刻开始,陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是( )
A、加工时间长的优先安排
B、加工时间短的优先安排
C、完成时间早的优先安排
D、等待时间长的优先安排
正确答案： B 
7【单选题】会场安排问题的最好的贪心策略是()
A、在不冲突的情况下，开始时间早的优先安排
B、在不冲突的情况下，使用时间短的优先安排
C、在不冲突的情况下，使用时间长的优先安排
D、在不冲突的情况下，结束时间早的优先安排
正确答案： D 
9、【单选题】哈夫曼编码是一种最优前缀码方案，给出待编码的8个字符及出现的频率，若干步贪心选择之后，树的集合为：
接下来的贪心选择选出的两个树的权分别为（）和（），让它们作为左右子树构造一课新树，新树的根权值是（C）。
A、15、14、23、
B、B、15、19、14
C、14、15、29
D、15、19、29
正确答案： C
2、【单选题】给定字符集及其出现的频率:{a:90%,b:5%,c:3%,d:2%},下述哪种编码是最优前缀码()?
A、a:1,b:01,c:000,d:001
B、a:0,b:01,c:000,d:001
C、a:1,b:10,c:000,d:001
D、a:0,b:10,c:000,d:001
正确答案： A 
6、【单选题】给定一个有向连通带权图G=(V,E),n个顶点,e条边,Dijsktra算法的时间复杂度为()
A、O(n 2)
B、O(n 3)
C、O(eloge)
D、O(nlogn)
正确答案： A 
8、【单选题】给定字符集{a,b,c,d,e,f},若用定长码编码,至少需要几位二进制位()
A、1位
B、2位
C、3位
D、4位
正确答案： C 
9、【单选题】找零钱问题的贪心策略是()
A、面值大的钱币优先找出
B、面值小的钱币优先找出
C、面值小于待找钱数且面值最大的优先找出
D、以上都不对
正确答案： C 
10、【单选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法不正确的是( )。
A、prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B、prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。
C、prim算法停止的条件是S=V
D、 prim算法的时间复杂度O(n3),n为图的顶点个数。
正确答案：D
1、【单选题】棋盘覆盖问题的分解方法为（）。
A、将2^k*2^k的棋盘分解为2个2^(k-1)*2^k
B、将2^k*2^k的棋盘分解为2个2^k*2^(k-1)
C、将2^k*2^k的棋盘分解为4个2^(k-1)*2^(k-1)
D、以上分解的方法都不对
正确答案： C 
2、【单选题】分治算法的基本思想描述错误的是( )
A、分治法将规模大的问题分解成规模较小的问题解决。
B、分治法划分的小问题相互重叠。
C、分治法一般采用递归的方法解决子问题。
D、分治法划分的小问题规模小到一定程度时可以直接解决。
正确答案： B
3、【单选题】二分合并排序算法时间复杂度的是()
A、O(logn)
B、O(nlogn)
C、0(logn^2)
D、0(n^2)
正确答案： B
4、【单选题】大整数A和B的乘法,将A分成位数大致相等的两部分A1和A2 ,将B分成位数大致相等的两部分B1和B2,以下描述错误的是()。
A、4个子问题的解归并为原问题解的方法为:A×B=10^nA1B1+10^n/2(A1B2+A2B1)+A2B2
B、3个子问题的解归并为原问题解的方法为:A×B=10^nA1B1+10^n/2((A1-A2)(B2-B1)+A1B1+A2B2)+A2B2
C、3个子问题的解归并为原问题解的方法为:A×B=10^nA1B1+10^n/2((A1+A2)(B1+B2)+A1B1+A2B2)+A2B2
D、划分3个子问题比划分4个子问题时间复杂度低
正确答案： C 
6、【单选题】有关2个n位大整数乘法问题说法错误的是()。
A、将两个n位大整数分解为4个规模大致相等的n/2位整数的整数乘法问题。
B、递归解决4个子问题。
C、子问题的解需要归并成原问题的解。
D、子问题的解本身就是原问题的解。
正确答案： D
7、【单选题】关于二分查找时间复杂度描述错误的是( )
A、二分查找算法最好情况下的时间复杂度为O(1).
B、二分查找算法平均情况下的时间复杂度为O(n).
C、二分查找算法最坏情况下的时间复杂度为O(logn).
D、二分查找算法平均情况下的时间复杂度为O(logn).
正确答案： B
8、【单选题】以下代码功能为合并排序,请根据注释按照数顺序选择合适的语句填入对应的括号。
{def MergeSort(A, low, high):
if (low < high):
()#分解
()# 递归序列左半部分
()# 递归序列右半部分
Merge(A, low, middle, high)# 子问题的解合并成原问题的解}
A、middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);
B、middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);
C、middle=(low+high)/2;MergeSort(A,middle+1,high); MergeSort(A,low,middle);
D、middle=(high-low)/2;MergeSort(A,middle+1,high); MergeSort(A,low,middle);
正确答案： B 
9、【单选题】有关循环赛日程表分治算法描述错误的是( )
A、循环赛日程表给定2^k个运动员,采用2^k/2的方法将运动员分成两组。
B、循环赛日程表算法先安排组内的赛程,再安排两组对打。
C、循环赛日程表算法的边界条件是两个运动员,一天的比赛。
D、循环赛日程表算法为2^k个运动员安排了2^k天的比赛。
正确答案： D
10、【单选题】分治算法核心就是分而治之,其中的“治”描述错误的是( )。
A、分治法通过治理小问题来治理大问题。
B、分治法递归治理小问题。
C、分治法需要将子问题的解归并成大问题的解。
D、治理子问题时,会有重复性治理子问题的现象。
正确答案： D 
11、【单选题】下述关于二分查找(折半查找)算法描述正确的是( )
A、二分查找是在任意给定的无序的数列中查找指定的数。
B、二分查找的序列为A[left,right]，其中left<right，分解操作为:(right-left)/2
C、二分查找根据比较二分位置的元素与待查找的是否相等。若相等，则算法结束。若不相等，进入其中一个子问题继续查找。
D、若二分查找的序列为A[left,right]，其中left<right，用递归来解决子问题，则left<right时递归结束。
正确答案： C
1、【单选题】有关合并排序的分治算法描述正确的是( )
A、合并排序A[left,right]的元素,采用的分解方法是(left+right)/2。
B、合并排序A[left,right]的元素,采用的分解方法是(right-left)/2。
C、合并排序A[left,right]的元素,需要治理规模大致等于(right-left+1)/2的两个子问题。
D、合并排序需要将两个有序的子序列归并成一个有序的子序列。
正确答案： B
3、【单选题】n个元素最小值问题的分治算法分解方法错误的是()。
A、划分为2个规模大致相等的子问题
B、从中间将n个元素划分为两部分
C、n个元素的位置下界left、上界right,分解操作为(left+right)/2
D、将n个元素分解为多个子问题,子问题之间不独立
正确答案： D 
4、【单选题】下述关于二分查找(折半查找)算法描述错误的是( )
A、二分查找是在任意给定的n个元素序列中查找指定元素。
B、二分查找的序列为A[left,right],分解操作为:(right-left)/2
C、二分查找根据比较的结果,好的情况是相等,算法结束。坏的情况是进入其中一个子问题继续查找。
D、若二分查找的序列为A[left,right],用递归来解决子问题,则边界条件是left>right。
正确答案： D
7、【单选题】以下函数的功能是（）
def Q(R, low，high):
if(low<high):#仅当区间长度大于1时才须排序
pivotpos=Partition(R,low,high) #划分后的基准元素所对应的位置
Q(R,low,pivotpos-1)#对左区间递归排序
Q(R,pivotpos+1,high)#对右区间递归排序
A、二分查找
B、二分求最值
C、合并排序
D、快速排序
正确答案： D
12、【单选题】关于快速排序分治算法时间复杂度描述错误的是()
A、快速排序分治算法最好情况下的时间复杂度为O(nlogn).
B、快速排序分治算法最坏情况下的时间复杂度为O(n 2).
C、快速排序分治算法平均情况下的时间复杂度为O(n 2).
D、快速排序分治算法平均情况下的时间复杂度为O(nlogn).
正确答案： C 
2、【单选题】有关快速排序的分治算法描述错误的是()。
A、快速排序A[left,right],选取基准元素的方法,将待排序元素分解为两个子问题。
B、快速排序基准元素的选取可以是待排序元素中的任何一个元素。
C、快速排序划分的两个子问题规模大致相等。
D、快速排序A[left,right],递归算法的边界条件是left<right
正确答案： C 我的答案：C 
8、【单选题】关于快速排序分治算法时间复杂度描述错误的是()
A、快速排序分治算法最好情况下的时间复杂度为O(nlogn).
B、快速排序分治算法最坏情况下的时间复杂度为O(n 2).
C、快速排序分治算法平均情况下的时间复杂度为O(n 2).
D、快速排序分治算法平均情况下的时间复杂度为O(nlogn).
正确答案： C
12、【单选题】有关2个n位大整数乘法问题说法错误的是()。
A、将两个n位大整数分解为4个规模大致相等的n/2位整数的整数乘法问题。
B、递归解决4个子问题。
C、子问题的解需要归并成原问题的解。
D、子问题的解本身就是原问题的解。
正确答案： D
1、【单选题】0-1背包问题的跳跃点算法的时间复杂度为( )
A、O(2^n)
B、O(nW)
C、O(n^2)
D、O(min(nW,2^n))
正确答案： D 
2、【单选题】给定序列X={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}，它们的最长公共子序列是（）。
A、BCBA
B、BCDA
C、ADAB
D、BCAA
正确答案： A
3、解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：
根据该递归关系式，求解得到下面二维表：
行A1和列A5确定的方格中的元素是（）。
A、132
B、130
C、264
D、150
正确答案： D
4、【单选题】n个工件2台机器的加工顺序问题(调度问题),依据贝尔曼法则设计的动态规划算法的时间复杂度为( )
A、O(logn)
B、O(nlogn)
C、O(logn^2)
D、O(n^2)
正确答案： B 
5、【单选题】关于动态规划与分治法的区别,表述不正确的是()
A、动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交
B、动态规划建立在描述子问题最优值关系的状态转移方程基础上,分治法一般不需要建立类似的最优值之间的数量关系
C、分治法能写成递归形式,动态规划不能写成递归形式
D、动态规划一般用来求解最优化问题,分治法多不用于求解最优化问题
正确答案： C 
6、【单选题】n个物品,背包容量为W的0-1背包问题的动态规划算法的时间复杂度为( )
A、O(logn)
B、O(nW)
C、O(n^2)
D、O(W^2)
正确答案： B 
7、【单选题】设c[i][j]表示序列Xi和Yj的最长公共子序列的长度。则它的递推关系式为：
则，根据给定的X=={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}从上到下填写缺失值
A、2 3、3
B、2 2 2
C、3、4 4
D、3、3、3
正确答案： C
9、【单选题】按照顺序排列动态规划的求解步骤,正确的是( ) (1)递归定义最优值。 (2)以自底向上的方式计算出最优值,并记录相关信息。 (3)分析最优解子结构性质。 (4)构造出最优解。
A、(1),(2),(3),(4)
B、(1),(3),(2),(4)
C、(3),(1),(2),(4)
D、(1),(2),(4),(3)
正确答案： C 
10、【单选题】关于动态规划和回溯法的区别,以下表述不正确的是()
A、动态规划和回溯法都可以用来求解最优化问题,但回溯法是基于枚举解的思想,动态规划则是基于构造子问题最优值关系的方式
B、在遇到重叠子问题的时候,动态规划思想会使用存储最优值的方式直接排除,而回溯法一般做法是设法避环和剪枝,降低其影响
C、在求解相同问题时,动态规划必然比回溯法浪费空间,但是更节约时间
正确答案： C 
11、【单选题】有7个工件，它们在第一台机器和第二台机器上的处理时间分别为：[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15]，[t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4]，这7个工件的最优加工顺序为（）。
A、1，2，3，4，5，6，7
B、1，4，6，3，2，7，5
C、1，6，4，3，7，5，2
D、1，4，2，6，5，7，3
正确答案： C
3、【单选题】矩阵连乘问题中,A1矩阵大小是100*5,A2矩阵大小为5*30,A3矩阵大小为30*10,则乘法次序 (A1*A2)*A3需要的元素乘法次数是( )。
A、15000
B、30000
C、45000
D、4500000
正确答案： C
4、【单选题】X序列有m个元素,Y序列有n个元素,X和Y的最长公共子序列问题的动态规划算法,时间复杂度为( )
A、O(nm)
B、O(nm^2)
C、O(mn^2)
D、O(lognm)
正确答案： A
5、【单选题】关于动态规划与分治法的区别,表述不正确的是()
A、动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交
B、动态规划建立在描述子问题最优值关系的状态转移方程基础上,分治法一般不需要建立类似的最优值之间的数量关系
C、分治法能写成递归形式,动态规划不能写成递归形式
D、动态规划一般用来求解最优化问题,分治法多不用于求解最优化问题
正确答案： C 
8、【单选题】规模为5矩阵连乘问题,计算次序有( )种。
A、10
B、12
C、14
D、16
正确答案： C
11、【单选题】解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：根据该递归关系式，求解过程中得到下面最优决策的二维表：由此，可得上述5个矩阵连乘的最优计算次序为（）
A、（A1（A2（A3（A4A5））））
B、（（A1A2）（A3（A4A5）））
C、（（A1A2）（（A3A4）A5））
D、（A1（（A2（A3A4））A5））
正确答案： D
3、【单选题】解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：根据该递归关系式，求解得到下面二维表：行A1和列A5确定的方格中的元素是（）。
A、132
B、130
C、264
D、150
正确答案： D 
1、【单选题】比较分支限界法和回溯法，说法错误的是（）
A、分支限界法保留下来的活结点是有可能导最优解的结点，回溯法则不是。
B、分支限界法与回溯法的搜索方式不同
C、分支限界法需要借助活结点表数据结构，而回溯法则不需要。
D、回溯法和分支限界法搜索之前都需要先确定搜索范围。
正确答案： A
2、【单选题】针对0-1背包问题，采用优先队列式分支限界法，以下说法中正确的是（）。
A、0-1背包问题的优先队列式分支限界法可以不用事先确定节点的优先级
B、 0-1背包问题的优先队列式分支限界法必须事先确定节点的优先级，优先级由用户根据问题目标来确定，并不唯一。
C、0-1背包问题的优先队列式分支限界法可以选用FIFO的队列数据结构来实现
D、0-1背包问题的优先队列式分支限界法需要用递归来实现。
正确答案： B 
3、【单选题】以下有关回溯法和分支限界法的描述中，错误的是（）
A、在分支限界法中，当前扩展结点一次生成一个孩子结点
B、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
C、分支限界法中，每一个活结点最多只有一次机会成为扩展结点。
D、回溯法中，每一个活结点有可能多次成为扩展结点
正确答案： A 
4、【单选题】以下关于回溯法的说法，错误的是（）
A、回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历
B、回溯法可以适用于求所有解、某个解、最优解等各种问题
C、回溯法能够保证生成时间复杂度较低的算法
D、回溯法的编程中，有“当前搜索路径”的概念，需要保存当前路径上节点的状态
正确答案： C 
5、【单选题】最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A、lb1
B、lb2
C、二者等价
D、依赖于具体输入
正确答案： B
6、【单选题】0-1背包问题的解空间结构属于（）
A、排列树
B、子集树
C、满n叉树
D、隐式图
正确答案： B
7、【单选题】有关n皇后问题说法错误的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用队列式分支限界法，也能用优先队列式分支限界法。
正确答案： D 
2、【单选题】关于分支限界法的说法，错误的是（）
A、分支限界法一般比回溯法使用更多内存空间
B、分支限界法分为队列式分支限界法和优先队列式分支限界法
C、分支限界法不能求解n皇后问题
D、分支限界法一般更适合求解最优化问题
正确答案： C 
3、【单选题】有关0-1背包问题的分支限界法说法错误的是（）
A、0-1背包问题可以用队列式分支限界法求解
B、 0-1背包问题可以用优先队列式分支限界法求解。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： D
4、【单选题】有关分支限界法说法错误的是（）
A、分支限界法和回溯法一样，都是搜索算法。
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、 分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： B
6、【单选题】以下有关回溯法和分支限界法的描述中，错误的是（）
A、在分支限界法中，当前扩展结点一次生成一个孩子结点
B、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
C、分支限界法中，每一个活结点最多只有一次机会成为扩展结点。
D、回溯法中，每一个活结点有可能多次成为扩展结点
正确答案： A
1、【单选题】以下关于回溯法的说法，错误的是（）
A、回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历
B、回溯法可以适用于求所有解、某个解、最优解等各种问题
C、回溯法能够保证生成时间复杂度较低的算法
D、回溯法的编程中，有“当前搜索路径”的概念，需要保存当前路径上节点的状态
正确答案： C  
2、【单选题】以下有关回溯法和分支限界法的描述中，错误的是（）
A、在分支限界法中，当前扩展结点一次生成一个孩子结点
B、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
C、分支限界法中，每一个活结点最多只有一次机会成为扩展结点。
D、回溯法中，每一个活结点有可能多次成为扩展结点
正确答案： A 、
3、【单选题】有关n皇后问题说法错误的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用队列式分支限界法，也能用优先队列式分支限界法。
正确答案： D 
4、【单选题】最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A、lb1
B、lb2
C、二者等价
D、依赖于具体输入
正确答案： B
1、最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A、lb1
B、lb2
C、二者等价
D、依赖于具体输入
正确答案： B  
2、有关0-1背包问题的分支限界法说法错误的是（）
A、0-1背包问题可以用队列式分支限界法求解
B、 0-1背包问题可以用优先队列式分支限界法求解。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： D  
3、有关分支限界法说法错误的是（）
A、分支限界法和回溯法一样，都是搜索算法。
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、 分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： B  
4、下述有关分支限界法搜索过程描述错误的是（）
A、分支限界法一次性生成所有的孩子结点
B、只有当活结点表为空时，算法才能结束。
C、分支限界法舍弃导致不可行解和非最优解的结点
D、分支限界法把活结点插入活结点表中
正确答案： B  
5、以下关于回溯法的说法，错误的是（）
A、回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历
B、回溯法可以适用于求所有解、某个解、最优解等各种问题
C、回溯法能够保证生成时间复杂度较低的算法
D、回溯法的编程中，有“当前搜索路径”的概念，需要保存当前路径上节点的状态
正确答案： C  
6、以下有关回溯法和分支限界法的描述中，错误的是（）
A、在分支限界法中，当前扩展结点一次生成一个孩子结点
B、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
C、分支限界法中，每一个活结点最多只有一次机会成为扩展结点。
D、回溯法中，每一个活结点有可能多次成为扩展结点
正确答案： A  
7、有关n皇后问题说法错误的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用队列式分支限界法，也能用优先队列式分支限界法。
正确答案： D
1、以下有关回溯法和分支限界法的描述中，错误的是（）
A、在分支限界法中，当前扩展结点一次生成一个孩子结点
B、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
C、分支限界法中，每一个活结点最多只有一次机会成为扩展结点。
D、回溯法中，每一个活结点有可能多次成为扩展结点
正确答案： A 
2、针对0-1背包问题，采用优先队列式分支限界法，以下说法中正确的是（）。
A、0-1背包问题的优先队列式分支限界法可以不用事先确定节点的优先级
B、 0-1背包问题的优先队列式分支限界法必须事先确定节点的优先级，优先级由用户根据问题目标来确定，并不唯一。
C、0-1背包问题的优先队列式分支限界法可以选用FIFO的队列数据结构来实现
D、0-1背包问题的优先队列式分支限界法需要用递归来实现。
正确答案： B 
3、下述有关分支限界法搜索过程描述错误的是（）
A、分支限界法一次性生成所有的孩子结点
B、只有当活结点表为空时，算法才能结束。
C、分支限界法舍弃导致不可行解和非最优解的结点
D、分支限界法把活结点插入活结点表中
正确答案： B 
4、最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A、lb1
B、lb2
C、二者等价
D、依赖于具体输入
正确答案： B 
5、有关n皇后问题说法错误的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用队列式分支限界法，也能用优先队列式分支限界法。
正确答案： D  
6、比较分支限界法和回溯法，说法错误的是（）
A、分支限界法保留下来的活结点是有可能导最优解的结点，回溯法则不是。
B、分支限界法与回溯法的搜索方式不同
C、分支限界法需要借助活结点表数据结构，而回溯法则不需要。
D、回溯法和分支限界法搜索之前都需要先确定搜索范围。
正确答案： A
1、有关0-1背包问题的分支限界法说法错误的是（）
A、0-1背包问题可以用队列式分支限界法求解
B、 0-1背包问题可以用优先队列式分支限界法求解。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： D  
2、针对0-1背包问题，采用优先队列式分支限界法，以下说法中正确的是（）。
A、0-1背包问题的优先队列式分支限界法可以不用事先确定节点的优先级
B、 0-1背包问题的优先队列式分支限界法必须事先确定节点的优先级，优先级由用户根据问题目标来确定，并不唯一。
C、0-1背包问题的优先队列式分支限界法可以选用FIFO的队列数据结构来实现
D、0-1背包问题的优先队列式分支限界法需要用递归来实现。
正确答案： B  
3、下述有关分支限界法搜索过程描述错误的是（）
A、分支限界法一次性生成所有的孩子结点
B、只有当活结点表为空时，算法才能结束。
C、分支限界法舍弃导致不可行解和非最优解的结点
D、分支限界法把活结点插入活结点表中
正确答案： B  
4、以下关于回溯法的说法，错误的是（）
A、回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历
B、回溯法可以适用于求所有解、某个解、最优解等各种问题
C、回溯法能够保证生成时间复杂度较低的算法
D、回溯法的编程中，有“当前搜索路径”的概念，需要保存当前路径上节点的状态
正确答案： C  
5、最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A、lb1、B、lb2
C、二者等价
D、依赖于具体输入
正确答案： B  
6、0-1背包问题的解空间结构属于（）
A、排列树
B、子集树
C、满n叉树
D、隐式图
正确答案： B  
7、关于分支限界法的说法，错误的是（）
A、分支限界法一般比回溯法使用更多内存空间
B、分支限界法分为队列式分支限界法和优先队列式分支限界法
C、分支限界法不能求解n皇后问题
D、分支限界法一般更适合求解最优化问题
正确答案： C
8、【单选题】算法的定义是
A、 算法是计算⽅法
B、 算法是计算机程序
C、 算法是解题的步骤
D、 算法不依赖数据结构
正确答案： C
3、【单选题】关于Prim算法和Kruskal算法的比较，正确的是
A、 两个算法的时间复杂度相同
B、 Prim算法适用于稠密图，Kruskal算法适用于稀疏图
C、 Kruskal算法的时间复杂度是用顶点个数决定的
D、 Prim为了提高贪心选择时查找最短边的效率，首先将图中的所有边按权值排序。
正确答案： B
4、【单选题】单源最短路径问题算法中,采用了前驱pre数组,用于记录（）
A、 当前最短路径长度
B、 图中每个顶点的前驱
C、 特殊路径
D、 以上都不对
正确答案： B 
1、【单选题】单源最短路径问题算法中,把出发点定为源点,根据该算法思想,与源点在同一集合中的点是（） 5
A、B 确定了最短路径的点 尚未确定最短路径的点
C、 不明确是哪些点
D、 以上都不对（）
正确答案： A
7、【单选题】单源最短路径问题算法中,V是图的顶点集,S记录已确定最短路径长度的点,算法的贪心策略是()
A、 选择特殊路径长度最短的,把相连的V-S中的点加入到S中,检查新增加的特殊路径,若比原来的短,则优化。
B、 选择特殊路径长度最短的,把相连的S中的点加入到V-S中,检查新增加的特殊路径,若比原来的短,则优化。
C、 选择路径长度最短的,把相连的点加入到S中,检查新增加的路径,若比原来的短,则优化。
D、 以上都不对
正确答案： A
4、【单选题】单源最短路径问题算法中,把出发点定为源点,根据该算法思想,与源点在同一集合中的点是（）
A、 确定了最短路径的点
B、 尚未确定最短路径的点
C、 不明确是哪些点
D、 以上都不对（）
正确答案： A 
1、【单选题】用Prim算法求解上图的最小生成树，初始时，集合S={a}，集合V-S={b,c,d,e,f,g}，第一步贪心选择的边是（）。
A、 （a,b）
B、 （b,c）
C、 （c,d）
D、 （c,f）
正确答案： A 
9、【单选题】单源最短路径问题算法中,V是图的顶点集,S记录已确定最短路径长度的点,算法的贪心策略是()
A、 选择特殊路径长度最短的,把相连的V-S中的点加入到S中,检查新增加的特殊路径,若比原来的短,则优化。
B、 选择特殊路径长度最短的,把相连的S中的点加入到V-S中,检查新增加的特殊路径,若比原来的短,则优化。
C、 选择路径长度最短的,把相连的点加入到S中,检查新增加的路径,若比原来的短,则优化。
D、 以上都不对
正确答案： A
9、【单选题】单源最短路径问题算法中,V是图的顶点集,S记录已确定最短路径长度的点,算法的贪心策略是()
A、 选择特殊路径长度最短的,把相连的V-S中的点加入到S中,检查新增加的特殊路径,若比原来的短,则优化。
B、 选择特殊路径长度最短的,把相连的S中的点加入到V-S中,检查新增加的特殊路径,若比原来的短,则优化。
C、 选择路径长度最短的,把相连的点加入到S中,检查新增加的路径,若比原来的短,则优化。
D、 以上都不对
正确答案： A
1、【单选题】下述关于二分查找(折半查找)算法描述正确的是( )
A、 二分查找是在任意给定的无序的数列中查找指定的数。
B、 二分查找的序列为A[left,right]，其中left<right，分解操作为:(right-left)/2
C、 二分查找根据比较二分位置的元素与待查找的是否相等。若相等，则算法结束。若不相等，进入其中一个子问题继续查找。
D、 若二分查找的序列为A[left,right]，其中left<right，用递归来解决子问题，则left<right时递归结束。
正确答案： C 
1、【单选题】有关合并排序的分治算法描述错误的是( )
A、 合并排序A[left,right]的元素,采用的分解方法是(left+right)/2。
B、 合并排序A[left,right]的元素,采用的分解方法是(right-left)/2。
C、 合并排序A[left,right]的元素,需要治理规模大致等于(right-left+1)/2的两个子问题。
D、 合并排序需要将两个有序的子序列归并成一个有序的子序列。
正确答案： B
6、有关分⽀限界法说法错误的是（）
A、 分⽀限界法和回溯法⼀样，都是搜索算法。
B、 分⽀限界法是⼀种“能进则进、进不了则换、换不了则退（回溯）”的搜索⽅法
C、 分⽀限界法是⼀种宽（⼴）度优先搜索的搜索算法
D、 分⽀限界法是⼀种最⼤效益或最⼩费⽤优先搜索的搜索算法
正确答案： B 
5、 针对0-1背包问题，采⽤优先队列式分⽀限界法，以下说法中正确的是（）。
A、 0-1背包问题的优先队列式分⽀限界法可以不⽤事先确定节点的优先级
B、 0-1背包问题的优先队列式分⽀限界法必须事先确定节点的优先级，优先级由⽤户根据问题⽬标来确定，并不唯⼀。
C、 0-1背包问题的优先队列式分⽀限界法可以选⽤FIFO的队列数据结构来实现
D、 0-1背包问题的优先队列式分⽀限界法需要⽤递归来实现。
正确答案： B
4、下述有关分⽀限界法搜索过程描述错误的是（）
A、分⽀限界法⼀次性⽣成所有的孩⼦结点
B、 只有当活结点表为空时，算法才能结束。
C、 分⽀限界法舍弃导致不可⾏解和⾮最优解的结点
D、 分⽀限界法把活结点插⼊活结点表中
正确答案： B 
1、⽐较分⽀限界法和回溯法，说法错误的是（）
A、 分⽀限界法保留下来的活结点是有可能导最优解的结点，回溯法则不是。
B、 分⽀限界法与回溯法的搜索⽅式不同
C、 分⽀限界法需要借助活结点表数据结构，⽽回溯法则不需要。
D、 回溯法和分⽀限界法搜索之前都需要先确定搜索范围。
正确答案： A 
10. (单选题)【单选题】通常，算法设计里说的“时间复杂度”指的是算法在那种情况下的时间复杂度
A. 最好
B. 最坏
C. 平均
D. 各种情况加权平均
正确答案: B

11、【单选题】用Prim算法求解上图的最小生成树，初始时，集合S={a}，集合V-S={b,c,d,e,f,g}，第一步贪心选择的边是（）。
A. （a,b）
B. （b,c）
C. （c,d）
D. （c,f）
正确答案: A
3. (单选题)规模为5凸多边形三角剖分方法有()种。
A. 2
B. 5
C. 14
D. 15
正确答案: B
5. (单选题)有关规模为n+1的凸多边形(v0,v1,...,vn)最优三角剖分问题,设凸多边形vi-1...vj最优三角剖分的权函数之和为c[i][j],凸多边形vi-1...vj的子问题为:矩阵凸多边形vi-1...vk的最优三角剖分、矩阵凸多边形vk...vj的最优三角剖分和三角形vi-1vkvj,设vi-1vkvj是最优决策，则计算最优值的递推方程表示为()。
A. c[i][j]=c[i][k]+c[k][j]+w(vi-1vkvj)
B. c[i][j]=c[i-1][k]+c[k][j]+w(vi-1vkvj)
C. c[i][j]=c[i][k]+c[k+1][j]+w(vi-1vkvj)
D. 以上都不对
正确答案: C
6. (单选题)n个工件加工顺序问题依据贝尔曼法则设计的动态规划算法的时间复杂度为()
A. O(n)
B. O(n2)
C. O(nlogn)
D. O(logn)
正确答案: C
9. (单选题)规模为5的有序序列,二叉搜索树共有()棵。
A. 14棵
B. 5棵
C. 40棵
D. 42棵
正确答案: D
13. (单选题)解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：

根据该递归关系式，求解得到下面二维表：

行A1和列A5确定的方格中的元素是（）。
A. 132
B. 130
C. 264
D. 150
正确答案: D
17. (单选题)设c[i][j]表示序列Xi和Yj的最长公共子序列的长度。则它的递推关系式为：

则，根据给定的X=={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}从上到下填写缺失值

A. 2 3 3
B. 2 2 2
C. 3 4 4
D. 3 3 3
正确答案: C
1. (单选题)设某拓朴图有n个顶点。用深度优先搜索算法搜索所有顶点，则时间复杂度为
A. O(n*n)
B. O(n*logn)
C. O(logn)
D. O(n)
正确答案: D
2. (单选题)n个结点的满二叉树，增加一层，结点总数最多增加
A. n
B. n-1
C. n+1
D. 2n
正确答案: C
4. (单选题)在有n个结点的满二叉树上，加一层结点，结点总数增加
A. n个
B. n-1个
C. n+1个
D. 2n个
正确答案: C
8. (单选题)现有一个用于求解最优化问题的回溯算法，在搜索过程中涉及的函数的描述，错误的是（）
A. 违反约束函数的分支不属于问题的定义域
B. 违反限界函数的分支不需要访问，不能够得到更优解
C. 目标函数是衡量解的优劣程度的函数
D. 在目标函数最小化问题中，限界函数应当使用上界
正确答案: D
9. (单选题)关于旅行商问题的说法，错误的是()
A. 旅行商问题的解空间与最短路径问题相同
B. 违反限界函数的分支不需要访问，不能够得到更优解
C. 目标函数是衡量解的优劣程度的函数
D. 在目标函数最小化问题中，限界函数应当使用上界
正确答案: D

1、【多选题】n个连续自然数a1...an连加和问题算法(利用等差数列求和公式)的输入可以是什么(  )。
A、a1,n
B、.an , n
C、a1, an
D、a1, an , n
正确答案： ABCD 
2、【多选题】关于算法特性的描述，正确的是
A、算法必须有输出
B、算法必须有输入
C、算法要产生确定的结果
D、算法的解题过程必须在有限步里结束
E、先有程序后有算法
正确答案： ACD  
3、【多选题】关于算法设计，正确的包括
A、算法设计首先要充分理解要解决的问题
B、详细设计算法之前要先设计算法的数学模型
C、设计算法时存储数据的形式（数据结构）很重要
D、算法不需要考虑通用性
E、算法不需要正确性验证
正确答案： ABC  
4、【多选题】关于算法设计，不正确的是
A、算法设计首先要充分理解要解决的问题
B、详细设计算法之前要先建立算法的数学模型
C、设计算法时存储数据的形式（数据结构）很重要
D、算法不需要考虑通用性
E、算法不需要正确性验证
正确答案： DE  
5、【多选题】关于算法的描述方法，正确的包括
A、算法的描述不应该使用复杂的逻辑运算
B、算法描述必须使用伪代码
C、算法描述可以使用程序设计语言
D、算法描述是对问题的解决方法和步骤的记录
E、描述算法的语句要注意不要有二义性
正确答案： CDE 
6、【多选题】对算法执行时间的描述，不正确的包括
A、问题规模增大，执行时间会增加
B、数据的排列形式有时也是影响影响算法执行时间
C、好的算法对不同规模的问题的处理时间是一样的
D、好算法在慢的计算机上的执行时间，一定比，差的算法在快的计算机上执行时间短
E、所谓好的算法的时间复杂度必须小于O(n)
正确答案： CDE  
7、【多选题】算法的基本特征有（）
A、输入
B、输出
C、有穷性
D、确定性
E、可行性
正确答案： ABCDE  
8、【多选题】关于递归算法设计，不正确的说法有
A、设计递归算法必须设计递归过程
B、设计递归算法必须设计递归终止条件和满足终止条件时的行为
C、如果一个问题是用递归方式描述的，应该优先考虑设计递归算法
D、如果一个问题是用递归方式描述的，应该优先考虑设计循环算法
E、如果一个问题是用递推方式描述的，应该优先考虑设计递归算法
正确答案： DE 
9、【多选题】关于算法分析的说法中，正确的包括
A、算法分析包括对算法的数据结构的复杂度的分析
B、算法分析包括对算法的输入效率进行分析
C、算法分析包括对算法的时间效率进行分析
D、算法分析包括对算法的空间效率进行分析
E、算法分析包括对算法的代码存储空间的分析
正确答案： CD  
10【多选题】关于算法特性的描述，不正确的是
A、算法必须有输出
B、算法必须有输入
C、算法要产生确定的结果
D、算法的解题过程必须在有限步里结束
E、先有程序后有算法
正确答案： BE  
1贪心算法的正确性证明包括证明
A、可行性
B、贪心选择性质
C、最优子结构性质
D、存在最优解
E、可分为独立子问题
正确答案： BC  
2【多选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法正确的是( )。
A、prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B、prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中
C、prim算法停止的条件是S=V
D、prim算法的时间复杂度O(n2),n为图的顶点个数
E、prim算法的时间复杂度和图的顶点数有关,也和图的边数也有关
F、prim算法的时间复杂度O(n3),n为图的顶点个数
正确答案： ABCD 
2【多选题】给定一个无向连通带权图G,下述有关生成树的说法正确的是()。
A、G的生成树可能有多棵
B、G的生成树唯一
C、G的最小生成树耗费最小
D、G的最小生成树唯一
正确答案： AC 
1、【多选题】分治算法的步骤有()
A、分解。
B、治理。
C、递归。
D、贪心。
正确答案： AB
2、【多选题】n个元素最小值问题的分治算法分解方法为（）
A、划分为2个规模大致相等的子问题
B、从中间将n个元素划分为两部分
C、如果n个元素的位置下界left、上界right，那么每次分解操作为(left+right)/2
D、将n个元素分解为多个子问题，子问题之间不独立
正确答案： ABC 
3、【多选题】{有关以下代码,说法正确的是()。
def BinarySearch(s, x, low, high):
 if (low > high):
   return -1、middle = (low + high) / 2
if (x == s[middle]):
 return middle
elif(x > s[middle]):
 return BinarySearch(s, x, middle + 1, high)
else :
 return BinarySearch(s, x, low, middle - 1)}
A、BinarySearch的功能是针对有序序列s[] ,采用二分搜索技术查找指定元素x
B、if (low>high) return -1;该语句为递归的边界条件
C、将问题规模一份为二的语句是middle=(low+high)/2;
D、递归序列左半部分的语句是BinarySearch (s, x, middle+1, high);
E、递归序列左半部分的语句是BinarySearch (s, x, low, middle-1);
正确答案： ABCE
4、【多选题】分治算法的思想是()
A、将规模较大的问题划分为规模较小的相同子问题。
B、子问题之间相互独立。
C、子问题之间不相互独立。
D、递归解决划分得到的子问题
E、有些子问题的解需要归并得到原问题的解
正确答案： ABDE 
2、【多选题】n个元素最小值问题的分治算法分解方法为（）
A、划分为2个规模大致相等的子问题
B、从中间将n个元素划分为两部分
C、如果n个元素的位置下界left、上界right，那么每次分解操作为(left+right)/2
D、将n个元素分解为多个子问题，子问题之间不独立
正确答案： ABC
2、【多选题】分治算法的思想是()
A、将规模较大的问题划分为规模较小的相同子问题。
B、子问题之间相互独立。
C、子问题之间不相互独立。
D、递归解决划分得到的子问题
E、有些子问题的解需要归并得到原问题的解
正确答案： ABDE
1、【多选题】有关矩阵连乘问题说法正确的是( )
A、矩阵A i...A j连乘, A i的行列为(p(i-1)×p i),A j的行列为(p(j-1)×p j),最后一次划分在A k,它的行列为(p(k-1)×p k),k=i,i+1,...,j,其结果矩阵的行列为(p(i-1)×p j)。
B、n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0
C、设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p i-1* p j* p k
D、矩阵连乘问题的时间复杂度为O(n^2)
正确答案： AB 
2、【多选题】有关动态规划描述正确的是()
A、动态规划将多阶段决策问题转化为单阶段决策问题。
B、动态规划往往用于求解某种最优性质的问题。
C、适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
D、动态规划求解时往往采用填表的方法记录问题最优值。
E、动态规划划分的各子问题与原问题相同,一般递归求解子问题。
正确答案： ABCD
3、【多选题】有关0-1背包问题的跳跃点算法描述正确的是( )
A、跳跃点(x,c[i][x])表示装入重量为x时,装入最大价值为c[i][x]
B、初始跳跃点为(0,0)
C、用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i],其中i=1,2,...,n
D、用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i]去掉重量不减,价值反而减少的受控点。其中i=1,2,...,n
正确答案： ABD 
4、【多选题】有关动态规划描述正确的是( )
A、动态规划递归求解问题时,因为子问题的重复求解,时间复杂度较高。
B、动态规划往往用于求解某种最优性质的问题
C、适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的
D、动态规划求解时往往采用填表的方法记录子问题的解
正确答案： ABCD
5、【多选题】有关工件加工顺序问题算法描述正确的是()
A、该问题的子问题:M1开始处理S集合的工件时,M2需要t时间才能停下来情况下,加工S集合中的工件总加工时间最短,可以用T(S,t)表示最短的总加工时间。
B、该问题的最短加工时间用T(S,t),则递推方程为:T(S,t)=min i∈S{t 1i+T(S-{i},max{t-t 1i,0}+t 2i)}
C、该问题的动态规划算法依据Johnson Bellman’s Rule.
D、该算法将第一台机器处理时间大于等于第二台机器处理时间的工件后安排加工,并按照第二台机器处理时间非降序排列的顺序加工。
正确答案： ABC
6、【多选题】动态规划的基本要素是( )
A、重叠子问题
B、最优子结构性质
C、自底向上的求解方式
D、自顶向下的递归求解方式
正确答案： ABC
1、【多选题】有关矩阵连乘问题说法正确的是()
A、矩阵A i...A j连乘,其中A k的行列为(p k×q k),k=i,i+1,...,j,其结果矩阵的行列为(p i×q j)。
B、n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0。
C、设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p iq jq k
D、矩阵连乘问题的时间复杂度为O(n 2)
正确答案： AB
3、【多选题】有关0-1背包问题,用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),以下说法正确的是( )
A、当i=0时或j=0时,c[i][j]=0
B、当j<w i时,物品无法装入,则背包容量依旧为j,c]i][j]=c[i-1][j]
C、当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最小。故c]i][j]=min(c[i-1][j],c[i-1][j-w i]+v i)
D、当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最大。故c]i][j]=max(c[i-1][j],c[i-1][j-w i]+v i)
正确答案： ABD
4、【多选题】有关最长公共子序列问题的动态规划算法说法正确的是( )
A、X n和Y m的代表了两个长度为n和m的字符串,求X n和Y m的最长公共子序列的子问题是:求X i和Y j的最长公共子序列,i=0,1,...n,j=0,1,...,m。
B、X i和Y j的最长公共子序列当i=0时,最长公共子序列的长度为0;j=0时,最长公共子序列的长度也为0
C、设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]
D、设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]+1、正确答案： AB
6、【多选题】有关动态规划描述正确的是( )
A、动态规划递归求解问题时,因为子问题的重复求解,时间复杂度较高。
B、动态规划往往用于求解某种最优性质的问题
C、适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的
D、动态规划求解时往往采用填表的方法记录子问题的解
正确答案： ABCD 
1、【多选题】有关矩阵连乘问题说法正确的是( )
A、矩阵A i...A j连乘, A i的行列为(p(i-1)×p i),A j的行列为(p(j-1)×p j),最后一次划分在A k,它的行列为(p(k-1)×p k),k=i,i+1,...,j,其结果矩阵的行列为(p(i-1)×p j)。
B、n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0
C、设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p i-1* p j* p k
D、矩阵连乘问题的时间复杂度为O(n^2)
正确答案： AB
2、有关动态规划描述正确的是()
A、动态规划将多阶段决策问题转化为单阶段决策问题。
B、动态规划往往用于求解某种最优性质的问题。
C、适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
D、动态规划求解时往往采用填表的方法记录问题最优值。
E、动态规划划分的各子问题与原问题相同,一般递归求解子问题。
正确答案： ABCD 
2、【多选题】动态规划的基本要素是( )
A、重叠子问题
B、最优子结构性质
C、自底向上的求解方式
D、自顶向下的递归求解方式
正确答案： AC 
3、【多选题】有关矩阵连乘问题说法正确的是()
A、矩阵A i...A j连乘,其中A k的行列为(p k×q k),k=i,i+1,...,j,其结果矩阵的行列为(p i×q j)。
B、n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0。
C、设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p iq jq k
D、矩阵连乘问题的时间复杂度为O(n 2)
正确答案： AB
1、【多选题】比较分支限界法和回溯法，两者的不同是（）
A、在一般情况下，分支限界法与回溯法的求解目标不同
B、分支限界法与回溯法的搜索方式不同
C、分支限界法需要借助活结点表数据结构，而回溯法则不需要。
D、扩展结点的扩展方式不同。
E、回溯法需要确定搜索范围，分支限界法则不需要。
F、分支限界法保留下来的活结点是有可能导致可行解或最优解的结点，回溯法则不是。
正确答案： ABCD 
2、【多选题】有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用回溯法求解
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE
3、【多选题】有关分支限界法说法正确的是（）
A、分支限界法是一种深度优先搜索的搜索算法
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： CD 
4、【多选题】以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以开用子集树模型求解
正确答案： ABC
5、【多选题】下述有关搜索过程描述错误的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，正在生成孩子的节点称为扩展节点
C、搜索过程中，所有孩子节点均已生成的节点称为扩展节点
D、搜索过程中，所有孩子节点均已生成的节点称为活结点节点
E、搜索过程中，所有孩子节点均已生成的节点称为死节点
F、搜索过程动态生成的树称为搜索树
正确答案： CD
6、【多选题】有关批处理作业调度问题说法正确的是（）
A、该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n
B、该问题的解空间的组织结构是排列树。
C、该问题需要设置约束条件，不需要限界条件。
D、该问题不需要设置约束条件，只需要限界条件。
E、该问题既需要设置约束条件，也需要限界条件。
正确答案： ABD 
7、【多选题】下述有关分支限界法搜索过程描述正确的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，扩展结点一次性生成所有的孩子结点
C、搜索过程中，舍弃导致不可行解和非最优解的结点
D、搜索过程中，保留下来的孩子结点是可能导致可行解或最优解的结点
E、搜索过程中，保留下来的孩子结点是活结点，被插入活结点表中。
F、当活结点表为空时或找到所需要的解时，算法结束。
正确答案： ABCDEF   
8、【多选题】以下有关回溯法和分支限界法的描述中，正确的是（）
A、回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解。
B、回溯法以宽度优先或以最小耗费（最大效益）优先的方式搜索解空间树，而分支限界法则以深度优先的方式搜索解空间树。
C、在分支限界法中，当前扩展结点一次性生成所有的孩子结点。
D、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
E、回溯法中，每一个活结点最多只有一次机会成为扩展结点。
F、分支限界法中，每一个活结点有可能多次成为扩展结点
正确答案： ACD
1、【多选题】以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以开用子集树模型求解
正确答案： ABC
2、【多选题】有关0-1背包问题的分支限界法说法正确的是（）
A、0-1背包问题可以用队列式分支限界法
B、0-1背包问题可以用优先队列式分支限界法。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品的总价值大于当前找到的最大价值。
E、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品装入剩余空间装入的最大价值大于当前找到的最大价值。
F、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： ABCDE
3、【多选题】以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以用子集树模型求解
E、最优装载问题可以采用子集树模型求解
F、0-1背包问题可以采用子集树模型求解
正确答案： ABCEF
4【多选题】有关0-1背包问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1
B、该问题的解空间的组织结构可以是排列树。
C、该问题需要设置约束条件，也可以设置限界条件
D、该问题只需要设置约束条件，不需要限界条件
正确答案： AC 
5【多选题】有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题只需要设置约束条件，不需要限界条件。
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE
6、【多选题】以下描述中，影响回溯法的搜索效率的是（）
A、问题的解空间，即搜索范围
B、设定的约束函数和限界函数
C、搜索方法
D、满足约束条件和限界条件的节点数目
正确答案： ABD 
7、【多选题】有关回溯法说法正确的是（）
A、回溯法是一种深度优先搜索的搜索算法
B、回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、回溯法是一种宽（广）度优先搜索的搜索算法
D、回溯法是一种最大效益或最小费用优先搜索的方法
正确答案： AB
8、【多选题】有关批处理作业调度问题说法正确的是（）
A、该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n
B、该问题的解空间的组织结构是排列树。
C、该问题需要设置约束条件，不需要限界条件。
D、该问题不需要设置约束条件，只需要限界条件。
E、该问题既需要设置约束条件，也需要限界条件。
正确答案： ABD
9、【多选题】下述有关搜索过程描述错误的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，正在生成孩子的节点称为扩展节点
C、搜索过程中，所有孩子节点均已生成的节点称为扩展节点
D、搜索过程中，所有孩子节点均已生成的节点称为活结点节点
E、搜索过程中，所有孩子节点均已生成的节点称为死节点
F、搜索过程动态生成的树称为搜索树
正确答案： CD  
1、【多选题】下述有关搜索过程描述错误的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，正在生成孩子的节点称为扩展节点
C、搜索过程中，所有孩子节点均已生成的节点称为扩展节点
D、搜索过程中，所有孩子节点均已生成的节点称为活结点节点
E、搜索过程中，所有孩子节点均已生成的节点称为死节点
F、搜索过程动态生成的树称为搜索树
正确答案： CD  
2、【多选题】以下描述中，影响回溯法的搜索效率的是（）
A、问题的解空间，即搜索范围
B、设定的约束函数和限界函数
C、搜索方法
D、满足约束条件和限界条件的节点数目
正确答案： ABD  
3、【多选题】以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以开用子集树模型求解
正确答案： ABC  
4、【多选题】有关0-1背包问题的分支限界法说法正确的是（）
A、0-1背包问题可以用队列式分支限界法
B、0-1背包问题可以用优先队列式分支限界法。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品的总价值大于当前找到的最大价值。
E、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品装入剩余空间装入的最大价值大于当前找到的最大价值。
F、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： ABCDE  
5、【多选题】有关回溯法说法正确的是（）
A、回溯法是一种深度优先搜索的搜索算法
B、回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、回溯法是一种宽（广）度优先搜索的搜索算法
D、回溯法是一种最大效益或最小费用优先搜索的方法
正确答案： AB  
6、【多选题】有关0-1背包问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1、B、该问题的解空间的组织结构可以是排列树。
C、该问题需要设置约束条件，也可以设置限界条件
D、该问题只需要设置约束条件，不需要限界条件
正确答案： AC  
7、【多选题】有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用回溯法求解
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE  
8、【多选题】比较分支限界法和回溯法，两者的不同是（）
A、在一般情况下，分支限界法与回溯法的求解目标不同
B、分支限界法与回溯法的搜索方式不同
C、分支限界法需要借助活结点表数据结构，而回溯法则不需要。
D、扩展结点的扩展方式不同。
E、回溯法需要确定搜索范围，分支限界法则不需要。
F、分支限界法保留下来的活结点是有可能导致可行解或最优解的结点，回溯法则不是。
正确答案： ABCD 
9、【多选题】有关下图说法正确的是（）
A、该树表示的问题的规模为3、B、该树为一棵排列树
C、该树表示的问题规模为4
D、该树为一棵子集树
正确答案： AB 我的答案：ABD 
10、【多选题】有关分支限界法说法正确的是（）
A、分支限界法是一种深度优先搜索的搜索算法
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： CD 
11、【多选题】有关批处理作业调度问题说法正确的是（）
A、该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n
B、该问题的解空间的组织结构是排列树。
C、该问题需要设置约束条件，不需要限界条件。
D、该问题不需要设置约束条件，只需要限界条件。
E、该问题既需要设置约束条件，也需要限界条件。
正确答案： ABD
1、以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以用子集树模型求解
E、最优装载问题可以采用子集树模型求解
F、0-1背包问题可以采用子集树模型求解
正确答案： ABCEF  
2、以下描述中，影响回溯法的搜索效率的是（）
A、问题的解空间，即搜索范围
B、设定的约束函数和限界函数
C、搜索方法
D、满足约束条件和限界条件的节点数目
正确答案： ABD  
3、下述有关分支限界法搜索过程描述正确的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，扩展结点一次性生成所有的孩子结点
C、搜索过程中，舍弃导致不可行解和非最优解的结点
D、搜索过程中，保留下来的孩子结点是可能导致可行解或最优解的结点
E、搜索过程中，保留下来的孩子结点是活结点，被插入活结点表中。
F、当活结点表为空时或找到所需要的解时，算法结束。
正确答案： ABCDEF   
4
有关下图说法正确的是（）
A、该树表示的问题的规模为3、B、该树为一棵排列树
C、该树表示的问题规模为4
D、该树为一棵子集树
正确答案： AB   
5
下述有关搜索过程描述错误的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，正在生成孩子的节点称为扩展节点
C、搜索过程中，所有孩子节点均已生成的节点称为扩展节点
D、搜索过程中，所有孩子节点均已生成的节点称为活结点节点
E、搜索过程中，所有孩子节点均已生成的节点称为死节点
F、搜索过程动态生成的树称为搜索树
正确答案： CD  
6
有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题只需要设置约束条件，不需要限界条件。
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE   
7
有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用回溯法求解
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE  
8
以下有关回溯法和分支限界法的描述中，正确的是（）
A、回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解。
B、回溯法以宽度优先或以最小耗费（最大效益）优先的方式搜索解空间树，而分支限界法则以深度优先的方式搜索解空间树。
C、在分支限界法中，当前扩展结点一次性生成所有的孩子结点。
D、在回溯法中，当前扩展结点选择其中某一个孩子结点进行扩展。
E、回溯法中，每一个活结点最多只有一次机会成为扩展结点。
F、分支限界法中，每一个活结点有可能多次成为扩展结点
正确答案： ACD
1、以下描述中，影响回溯法的搜索效率的是（）
A、问题的解空间，即搜索范围
B、设定的约束函数和限界函数
C、搜索方法
D、满足约束条件和限界条件的节点数目
正确答案： ABD  
2、有关分支限界法说法正确的是（）
A、分支限界法是一种深度优先搜索的搜索算法
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： CD  
3、有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题能用回溯法求解
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE 
4、以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以开用子集树模型求解
正确答案： ABC  
5、有关回溯法说法正确的是（）
A、回溯法是一种深度优先搜索的搜索算法
B、回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、回溯法是一种宽（广）度优先搜索的搜索算法
D、回溯法是一种最大效益或最小费用优先搜索的方法
正确答案： AB  
6、以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以用子集树模型求解
E、最优装载问题可以采用子集树模型求解
F、0-1背包问题可以采用子集树模型求解
正确答案： ABCEF  
7、下述有关分支限界法搜索过程描述正确的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，扩展结点一次性生成所有的孩子结点
C、搜索过程中，舍弃导致不可行解和非最优解的结点
D、搜索过程中，保留下来的孩子结点是可能导致可行解或最优解的结点
E、搜索过程中，保留下来的孩子结点是活结点，被插入活结点表中。
F、当活结点表为空时或找到所需要的解时，算法结束。
正确答案： ABCDEF   
8、比较分支限界法和回溯法，两者的不同是（）
A、在一般情况下，分支限界法与回溯法的求解目标不同
B、分支限界法与回溯法的搜索方式不同
C、分支限界法需要借助活结点表数据结构，而回溯法则不需要。
D、扩展结点的扩展方式不同。
E、回溯法需要确定搜索范围，分支限界法则不需要。
F、分支限界法保留下来的活结点是有可能导致可行解或最优解的结点，回溯法则不是。
正确答案： ABCD  
9、有关0-1背包问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1、B、该问题的解空间的组织结构可以是排列树。
C、该问题需要设置约束条件，也可以设置限界条件
D、该问题只需要设置约束条件，不需要限界条件
正确答案： AC
1、有关0-1背包问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1、B、该问题的解空间的组织结构可以是排列树。
C、该问题需要设置约束条件，也可以设置限界条件
D、该问题只需要设置约束条件，不需要限界条件
正确答案： AC  
2、有关分支限界法说法正确的是（）
A、分支限界法是一种深度优先搜索的搜索算法
B、分支限界法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C、分支限界法是一种宽（广）度优先搜索的搜索算法
D、分支限界法是一种最大效益或最小费用优先搜索的搜索算法
正确答案： CD  
3、下述有关分支限界法搜索过程描述正确的是（）
A、当解空间结构是一棵树时，搜索从根开始
B、搜索过程中，扩展结点一次性生成所有的孩子结点
C、搜索过程中，舍弃导致不可行解和非最优解的结点
D、搜索过程中，保留下来的孩子结点是可能导致可行解或最优解的结点
E、搜索过程中，保留下来的孩子结点是活结点，被插入活结点表中。
F、当活结点表为空时或找到所需要的解时，算法结束。
正确答案： ABCDEF   
4、以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以用子集树模型求解
E、最优装载问题可以采用子集树模型求解
F、0-1背包问题可以采用子集树模型求解
正确答案： ABCEF  
5、有关n皇后问题说法正确的是（）
A、该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B、该问题的初始状态为：(0,0,...,0)
C、该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D、该问题只需要设置约束条件，不需要限界条件。
E、该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
正确答案： ABCDE  
6、以下描述中，影响回溯法的搜索效率的是（）
A、问题的解空间，即搜索范围
B、设定的约束函数和限界函数
C、搜索方法
D、满足约束条件和限界条件的节点数目
正确答案： ABD  
7、有关0-1背包问题的分支限界法说法正确的是（）
A、0-1背包问题可以用队列式分支限界法
B、0-1背包问题可以用优先队列式分支限界法。
C、0-1背包问题的约束条件是装入的背包重量小于等于背包容量
D、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品的总价值大于当前找到的最大价值。
E、0-1背包问题的限界条件可以是当前已装入背包的价值加上剩余物品装入剩余空间装入的最大价值大于当前找到的最大价值。
F、0-1背包问题的优先队列式分支限界法也可以不设置结点的优先级。
正确答案： ABCDE  
8、以下有关子集树的描述中说法正确的是（）
A、当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B、子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C、子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D、旅行售货员问题可以开用子集树模型求解
正确答案： ABC
3、【多选题】分治算法的思想是()
A、将规模较大的问题划分为规模较小的相同子问题。
B、子问题之间相互独立。
C、子问题之间不相互独立。
D、递归解决划分得到的子问题
E、有些子问题的解需要归并得到原问题的解
正确答案： ABDE
3、【多选题】有关动态规划描述正确的是()
A、 动态规划将多阶段决策问题转化为单阶段决策问题。
B、 动态规划往往⽤于求解某种最优性质的问题。
C、 适⽤动态规划求解的问题经分解得到的各个⼦问题往往不是相互独⽴的。
D、 动态规划求解时往往采⽤填表的⽅法记录问题最优值。
E、 动态规划划分的各⼦问题与原问题相同,⼀般递归求解⼦问题。
正确答案： ABCD
5、【多选题】有关矩阵连乘问题说法正确的是()
A、 矩阵A i...A j连乘,其中A k的⾏列为(p k×q k),k=i,i+1,...,j,其结果矩阵的⾏列为(p i×q j)。
B、 n个矩阵连乘A 1...A n,其⼦问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的⼦问题,其需要的乘法次数为0。
C、 设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的⼦问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p iq jq k
D、 矩阵连乘问题的时间复杂度为O(n 2)
正确答案： AB
5、【多选题】有关最⻓公共⼦序列问题的动态规划算法说法正确的是( )
A、 X n和Y m的代表了两个⻓度为n和m的字符串,求X n和Y m的最⻓公共⼦序列的⼦问题是:求X i和Y j的最⻓公共⼦序列,i=0,1,...n,j=0,1,...,m。
B、 X i和Y j的最⻓公共⼦序列当i=0时,最⻓公共⼦序列的⻓度为0;j=0时,最⻓公共⼦序列的⻓度也为0
C、 设X i和Y j的最⻓公共⼦序列的⻓度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]
D、 设X i和Y j的最⻓公共⼦序列的⻓度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]+1
正确答案： AB 
4、【多选题】有关工件加工顺序问题算法描述正确的是()
A、该问题的子问题:M1开始处理S集合的工件时,M2需要t时间才能停下来情况下,加工S集合中的工件总加工时间最短,可以用T(S,t)表示最短的总加工时间。
B、该问题的最短加工时间用T(S,t),则递推方程为:T(S,t)=min i∈S{t 1i+T(S-{i},max{t-t 1i,0}+t 2i)}
C、该问题的动态规划算法依据Johnson Bellman’s Rule.
D、该算法将第一台机器处理时间小于第二台机器处理时间的工件后安排加工,并按照第一台机器处理时间非降序排列的顺序加工。
E、该算法将第一台机器处理时间大于等于第二台机器处理时间的工件后安排加工,并按照第二台机器处理时间非降序排列的顺序加工。
正确答案： ABC 
8、【多选题】 ⽐较分⽀限界法和回溯法，两者的不同是（）
A、 在⼀般情况下，分⽀限界法与回溯法的求解⽬标不同
B、 分⽀限界法与回溯法的搜索⽅式不同
C、 分⽀限界法需要借助活结点表数据结构，⽽回溯法则不需要。
D、 扩展结点的扩展⽅式不同。
E、 回溯法需要确定搜索范围，分⽀限界法则不需要。
F、 分⽀限界法保留下来的活结点是有可能导致可⾏解或最优解的结点，回溯法则不是。
正确答案： ABCD 
6、【多选题】 以下有关⼦集树的描述中说法正确的是（）
A、 当所给的问题是从n个元素组成的集合S中找出满⾜某种性质的⼀个⼦集时，相应的解空间树称为⼦集树。
B、 ⼦集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在⼦集中。
C、 ⼦集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在⼦集中；xi=1表示第i个元素在⼦集中。
D、 旅⾏售货员问题可以开⽤⼦集树模型求解
正确答案： ABC
4、以下有关回溯法和分⽀限界法的描述中，正确的是（）
A、 回溯法的求解⽬标是找出解空间树中满⾜约束条件的所有解，⽽分⽀限界法的求解⽬标则是找出满⾜约束条件的⼀个解。
B、 回溯法以宽度优先或以最⼩耗费（最⼤效益）优先的⽅式搜索解空间树，⽽分⽀限界法则以深度优先的⽅式搜索解空间树。
C、 在分⽀限界法中，当前扩展结点⼀次性⽣成所有的孩⼦结点。
D、 在回溯法中，当前扩展结点选择其中某⼀个孩⼦结点进⾏扩展。
E、 回溯法中，每⼀个活结点最多只有⼀次机会成为扩展结点。
F、分⽀限界法中，每⼀个活结点有可能多次成为扩展结点
正确答案： ACD 
1、有关分⽀限界法说法正确的是（）
A、 分⽀限界法是⼀种深度优先搜索的搜索算法
B、 分⽀限界法是⼀种“能进则进、进不了则换、换不了则退（回溯）”的搜索⽅法
C、分⽀限界法是⼀种宽（⼴）度优先搜索的搜索算法
D、分⽀限界法是⼀种最⼤效益或最⼩费⽤优先搜索的搜索算法
正确答案： CD
38. (多选题)【多选题】关于算法对辅助空间占用的描述中，正确的有
A. 问题规模总是会影响算法的辅助空间占用量
B. 复杂的数据结构总是会占用较多辅助空间
C. 动态数据结构通常会有比较多的存储浪费
D. 循环算法常常会比递归算法占用更少的辅助空间
E. 递归算法通常会占用比较多的辅助数据空间
正确答案: DE
40. (多选题)【多选题】关于循环算法和递归算法的对比，正确的说法有
A. 循环一定比递归快
B. 通常递归算法不易调试
C. 递归和循环都是算法设计的重要手段
D. 应该尽量避免使用递归
E. 不是所有的算法语言都支持递归
正确答案: BCE
41. (多选题)【多选题】对算法设计的理解，正确的包括
A. 所有的算法都很难设计
B. 算法不是程序，可以适当的允许错误
C. 相对于有没有好算法，有没有算法更重要
D. 不是所有的算法都很难设计 
E. 程序流程图是最好的算法描述工具
正确答案: CD
48. (多选题)【多选题】关于算法对辅助空间占用的描述中，不正确的是
A. 问题规模总是会影响影响算法的辅助空间占用量
B. 复杂的数据结构总是会占用较多辅助空间
C. 动态数据结构通常会有比较多的存储浪费
D. 循环算法常常会比递归算法占用更少的辅助空间
E. 递归算法通常会占用比较多的辅助数据空间
正确答案: ABC
50. (多选题)【多选题】A关于循环算法和递归算法的对比，不正确的说法有
A. 循环一定比递归快
B. 通常递归算法会不易调试
C. 递归和循环都是算法设计的重要手段
D. 应该尽量避免使用递归
E. 不是所有的算法语言都支持递归
正确答案: AD
32. (多选题)有关凸多边形三角剖分问题说法正确的是()
A. n+1边形的凸多边形最优三角剖分问题与n个矩阵连乘问题。
B. n+1边形的凸多边形任意一种三角剖分方法可以用一棵二叉树唯一表示。
C. n+1边形的凸多边形V 0V 1...V n,其子问题为V i-1...V j连乘,0≤i≤j≤n,其中i=j表示一条直线,即退化的多边形,其三角形权函数为0。
D. 矩阵连乘问题的时间复杂度为O(n^3)
正确答案: ABCD
34. (多选题)规模为n的0-1背包问题,有关子问题描述正确的是()
A. 子问题可以描述为规模为i的0-1背包问题,即:1...i共i个物品,背包容量为j
B. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j-w i]。
C. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j-w ix i],其中x i等0或1。
D. 用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),则其子问题为:1...i-1共i-1个物品,背包容量为j-w ix i的最优值为c[i-1][j]。
正确答案: AC
37. (多选题)有关最优二叉搜索树说法正确的是()
A. 最优二叉搜索树的左孩子的节点都比根节点小,右孩子节点都比根节点大。
B. 最优二叉搜索树的平均比较次数最少。
C. 最优二叉搜索树的平均比较次数最多。
D. 最优二叉搜索树中有n个是节点,n+1个虚节点。
正确答案: ABD
38. (多选题){s1,s2,...,sn},虚节点{e0,e1,...,en}的最优二叉搜索树问题的子问题描述为有序序列{si,si+1,...,sj},虚节点{ei-1,ei,...,ej}的最优二叉搜索树,以下描述正确的是()。
A. i=1，j=n表示规模为n的原问题。
B. i=j+1，表示字符序列为空，对应的最优二叉搜索树为一棵空树。
C. 有序序列{si,si+1,...,sj},虚节点{ei-1,ei,...,ej}的最优二叉搜索树的子问题是：有序序列{si,si+1,...,sk-1},虚节点{ei-1,ei,...,ek-1}的最优二叉搜索树和有序序列{sk+1,sk+2,...,sj},虚节点{ek,ek+1,...,ej}的最优二叉搜索树。
正确答案: ABC
15. (多选题)有关子集树描述中，说法错误的是（）
A. 子集树的根结点为问题的初始状态
B. 子集树的中间结点为搜索过程中形成的某中间状态
C. 子集树的叶子结点为问题结束状态
D. 子集树的分支表示从一个状态过渡到另一个状态的行为
E. 子集树中从根结点到叶子结点的路径是一个可行解（一个子集）
F. 子集树的深度等于问题的规模加1
正确答案: ABCD
17. (多选题)有关下图说法正确的是（）

A. 该树表示的问题的规模为3
B. 该树为一棵排列树
C. 该树表示的问题规模为4
D. 该树为一棵子集树
正确答案: AB
9. (多选题)部落卫队问题。原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何2 个人都不是仇敌。给定byteland部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。以下有关部落卫队问题说法正确的是（）
A. 该问题的解的形式为(x1,x2,...,x3)，xi(i-1,2,3,...,n)=0或1，0表示居民未被选入部落卫队，1表示居民被选入部落卫队。
B. 该问题的解空间组织结构为一棵排列树，规模为n时，树的深度为n。
C. 该问题可以用分支限界法求解，也可以用回溯法求解。
D. 该问题需要设置约束条件，也需要设置限界条件。
E. 将给定的仇敌关系图转换成它的补图，则成为友好关系图，部落卫队问题实质就是最大团问题。
正确答案: ACDE
11. (多选题)有关旅行售货员问题的分支限界法说法正确的是（）
A. 旅行售货员问题可以用队列式分支限界法，也可以用优先队列式分支限界法。
B. 旅行售货员问题的约束条件是当前城市和要去的城市之间有路相连。
C. 旅行售货员问题的限界条件可以是当前已走过的路径长度小于当前找到的最优路径长度。
D. 旅行售货员问题的限界条件可以是当前已走过的路径长度加上未走过的城市最小出边权之和小于当前找到的最优路径长度。
E. 旅行售货员问题的优先队列式分支限界法优先级可以设置为当前已走过的路径长度加上未走过的城市最小出边权之和。
正确答案: ABCDE
12. (多选题)有关旅行售货员问题的分支限界解法，说法错误的是（）
A. 旅行售货员问题可以用队列式分支限界法
B. 旅行售货员问题可以用回溯法，也可以用分支限界法。
C. 旅行售货员问题的限界条件可以是当前已走过的路径长度。
D. 旅行售货员问题的限界条件可以是当前已走过的路径长度加上未走过的城市最小出边权之和
E. 旅行售货员问题的优先队列式分支限界法优先级可以设置为当前已经走过的路径长度。
F. 旅行售货员问题的约束条件是当前城市和要去的城市之间有边相连。
正确答案: CD

1、贪心算法在每个阶段面临选择时,都做出对眼前来讲是最有利的选择()
正确答案：√
2、针对同一个问题,贪心策略可能有多个,贪心算法的好坏取决于贪心策略的好坏。
正确答案：√
3、贪心法可以保证最终的解是最优解。
正确答案：×
4、采用贪心策略设计的算法，一定要对算法的正确性进行证明。
正确答案：√
5、会场安排的最佳贪心策略一定能保证安排最多的相容会议使用同一会议室。
正确答案：√
6、一个好的贪心策略,一定能得到问题的最优解。
正确答案：×
7、贪心法具有高效性,它可以非常迅速地获得一个解。
正确答案：√
2、贪心算法的贪心策略确定后可以更改( )
正确答案：×
3、贪心法可以保证最终的解是最优解。
正确答案：×
5、堆排序、冒泡排序、快速排序都采用了贪心策略进行排序。
正确答案：×
8、一个好的贪心策略,一定能得到问题的最优解。
正确答案：×
1、采用贪心策略设计的算法，一定要对算法的正确性进行证明。
正确答案：√
2、会场安排的最佳贪心策略一定能保证安排最多的相容会议使用同一会议室。
正确答案：√
3、针对同一个问题,贪心策略可能有多个,贪心算法的好坏取决于贪心策略的好坏。
正确答案：√
4、一个好的贪心策略,一定能得到问题的最优解。
正确答案：×
6、贪心法可以保证最终的解是最优解。
正确答案：×
7、哈夫曼编码属于可变长编码。
正确答案：√
1、0-1背包问题的动态规划解法不适合背包容量非常大()的情况。
正确答案：√
2、最长公共子序列问题的动态规划解法时间复杂度等于两个序列长度之积。
正确答案：√
3、最长公共子序列问题中，如果采取穷举法，可以在序列A中子序列可能的开头和结尾（因为子序列由其开头位置和结尾位置唯一确定），然后在序列B中查找它是否存在，如果按照子序列长度降序枚举，找到的第一个公共子序列就是最长公共子序列。
正确答案：×
4、以动态规划求解0-1背包问题，背包容量可以是任意实数。
正确答案：×

5、矩阵连乘问题中有多个矩阵相乘，问题是安排矩阵相乘的先后顺序，使总乘法次数最少，例如 有[A][B]C三个矩阵，则可行的顺序有ABC\ACB\CAB\CBA\BAC\BCA六个。
正确答案：×
6、0-1背包问题的贪心法解法和动态规划解法都能够生成最优解。
正确答案：×
2、最长公共子序列问题的动态规划解法时间复杂度等于两个序列长度之积。
正确答案：√
3、最长公共子序列问题中，如果采取穷举法，可以在序列A中子序列可能的开头和结尾（因为子序列由其开头位置和结尾位置唯一确定），然后在序列B中查找它是否存在，如果按照子序列长度降序枚举，找到的第一个公共子序列就是最长公共子序列。
正确答案：×
3、最⻓公共⼦序列问题的动态规划解法时间复杂度等于两个序列⻓度之积。
正确答案：√
简答题
1．简述算法的概念及特征。
答案：算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列，并且具有以下特性：（1）
输入（零个或多个）；（2）输出（一个或多个）；（3）确定性，组成算法的每条指令必须有确定的含义，
无歧义；（4）有限性，算法中指令的条数是有限的，每条指令的执行次数是有限的，执行每条指令的时
间也是有限的；（5）可行性。有待实现的运算都是基本运算。
2．简述算法设计的一般过程。
答案：（1）充分理解要解决的问题；（2）数学模型拟制；（3）算法详细设计；（4）算法描述；（5）
算法思路的正确性验证；（6）算法分析；（7）算法的计算机实现和测试；（8）文档资料的编制。
3．简述算法分析的概念，实际分析中考虑的侧重点是什么？
答案：算法分析就是对算法在运行过程中所需要的计算机资源的量的多少进行分析。
实际分析中，主要侧重时间复杂度分析和空间复杂度分析。
4．简述递归的概念和递归算法求解步骤。
答案：子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用
自身的算法称为递归算法 。
采用递归算法来求解问题的一般步骤：（1）分析问题，寻找递归关系；（2）找出停止条件；（3）构建
函数体。
5．简述分治法的基本思想和求解步骤。
答案：分治法的基本思想是将一个难以直接解决的大问题，分解成一些规模较小的相同问题，如果子问题
还不容易解决，继续分解为更小的子问题，直到容易解决为止。各个子问题相互独立，递归解决各子问题，
将子问题的解归并为原问题的解。
求解步骤：（1）分解：分解为规模较小、与原问题相同、相互独立的子问题；（2）治理：递归解决子问
题，将子问题的解归并为原问题的解。
6．简述分治法的特征。
答案：分治算法具有以下特征：（1）问题规模足够小时容易解决；（2）将规模大的问题分成规模较小的
子问题；（3）子问题相互独立；（4）子问题的解决方法与原问题相同；（5）递归解决子问题；（6）子
问题的解能够合并成原问题的解。
7．二分查找算法是根据分治策略来设计的，简述二分查找算法的思想。
答案：假定元素序列已经由小到大排好序，将有序序列分成规模大致相等的两部分，然后取中间元素与特
定查找元素 x 进行比较，如果 x 等于中间元素，则算法终止；如果 x 小于中间元素，则在序列的左半部继
续查找，即在序列的左半部重复分解和治理操作；否则，在序列的右半部继续查找，即在序列的右半部重
复分解和治理操作。可见，二分查找算法重复利用了元素间的次序关系。
8．合并排序算法是根据分治策略来设计的，简述合并排序算法的思想。
答案：（1）分解：将待排序元素分成大小大致相同的两个子序列；（2）求解子问题：用合并排序法分别
对两个子序列递归地进行排序；（3）合并：将排好序的有序子序列进行合并，得到符合要求的有序序列。
将待排序序列从中间一分为二（即下标 mid=（left + right）/2）,然后对左边递归，对右边递归。递归的结
果为左边是有序的序列，右边是有序序列，最后将两个有序的子序列合并得到一个有序的子序列。递归过
程直到子序列只包含一个元素为止。
9．快速排序算法是根据分治策略来设计的，简述快速排序算法的思想。
答案：选取待排序序列的第一个元素为基准元素，然后通过一趟扫描将待排序的元素分割成独立的两个序
列，第一个序列中所有元素均不大于基准元素、第二个序列中所有元素均不小于基准元素。再对第一个序
列和第二个序列分别进行递归排序，最终可使整个序列变成有序序列。
快速分类算法是根据分治策略设计出来的算法。其关键步骤就是“划分”：根据某个元素 v 为标准，将序
列中的元素重新整理，使得整理后的序列中 v 之前的元素都不大于 v，而 v 之后的元素都不小于 v。此时，
元素 v 即找到了其最终的位置。要得到序列的排序结果，再只需对 v 之前的元素和 v 之后的元素分别排
序即可，这可通过递归处理来完成。
10．简要叙述动态规划法的基本思想。
答案：（1）将待求解的问题分解得到的规模较小的子问题，子问题之间往往不是相互独立的。（2）在求
解过程中，采用自底向上的求解方法，将已解决的子问题的解保存到相应表格中，在需要时可以轻松找出。
11．简要叙述动态规划法与分治算法的异同。
答案：（1）将待求解问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最
优解。（2）分治法中子问题是相互独立的，采用自顶向下的递归求解子问题，动态规划中，子问题往往
不是相互独立的，采用自底向上的求解方法。
12．简述动态规划算法的基本要素。
答案：（1）最优子结构性质；（2）子问题重叠性质；（3）自底向上的求解方式。
13．简述动态规划求解最优化问题的步骤。
答案：动态规划求解最优化问题的步骤有如下四步：（1）找出最优解的性质，并刻划其结构特征。（2）
递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最
优解。
14．简述贪心算法的基本思想。
答案：从问题的某一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优的决策，逐步逼近给定
的目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止。
15．简述贪心算法的解题步骤。
答案：（1）分解：将原问题分解为若干个相互独立的阶段；（2）解决：对于每个阶段依据贪心策略进行
贪心选择，求出局部的最优解；（3）合并：将各个阶段的解合并为原问题的一个可行解。
16 ．简述贪心算法的基本要素。
答案：（1）最优子结构性质，一个问题的最优解一定包含其子问题的最优解；（2）贪心选择性质，所求
问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终的选
择方案是全局最优的。
17．简述哈夫曼编码算法的思想。
答案：将 n 个字符看做是 n 个孤立的树，组成一个结合。重复做如下操作：从集合中取出两棵出现频率最
低的树，让它们作为左右子树构成一棵新树，新树的频率为左右子树频率之和。然后将新树插入到树的集
合中；算法直到集合中只剩下一棵树为止。
该算法的基本思想是以字符的使用频率做权构建一棵哈夫曼树。首先将 n 的字符分别看作以其为根的树，
构成 n 棵树的一个集合；然后每次从树的集合中取出双亲为 0 且权值最小的两棵树作为左、右子树，构造
一棵新树；新树根结点的权值为其左右孩子结点权之和，将新树插入到树的集合中；算法直到树的集合中
只有一棵树为止。
18．简述 Prim 算法构造最小生成树的基本思想。
答案：首先，令 U={u0}，u0∈V，TE={}；然后，只要 U 是 V 的真子集，就做如下贪心选择：选取满足条件
i ∈U，j ∈ V-U，且边（i，j）是连接 U 和 V-U 的所有边中的最短边，即该边的权值最小；将顶点 j 加入
集合 U，边（i，j）加入集合 TE。继续上面的贪心选择一直进行到 U=V 为止。
19．简述最小生成树的 Kruskal 算法的基本思想。
答案：按照图中边权由大到小的次序依次考虑每条边是否加入最小生成树中。当考虑到某条边时，如果该
边与已经加入到最小生成树中的边不形成回路，则将该边加入进去。
20．简述回溯法的基本思想
答案：回溯法的基本思想是：深度优先搜索+剪枝。从根结点开始，以深度优先的方式进行搜索，搜索的
过程中，每搜索到一个结点，检查是否满足约束函数和限界函数，如果满足，则更深一层的搜索，如果不
满足，则剪枝，搜索过程直到找到问题的解或所有活结点变成死结点为止。回溯法用来求问题的多个解。
从根节点出发，以深度优先的方式进行搜索。判断当前是否到叶子节点，若到了叶子节点，则修正最优值，
若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）
21．简述回溯法的搜索思想。
答案：从根开始，以深度优先搜索的方式进行搜索。根结点是活结点并且是当前的扩展结点。在搜索的过
程中，当前的扩展结点向纵深方向移向一个新结点，判断该新结点是否满足隐约束，如果满足，则新结点
成为活结点，并且成为当前的扩展结点，继续深一层的搜索；如果不满足，则换该新结点的兄弟结点（扩
展结点的其它分支）继续搜索；如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成
为死结点，搜索回溯到其父结点处继续进行。搜索过程直到找到问题的解或根结点变成死结点为止。
22．试说明回溯法求解问题的算法框架。
答案：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间组织结构；（3）以深度优
先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
23． 什么是子集树，简述解的形式，分量的含义。
答案：当所给的问题是从 n 个元素组成的集合 S 中找出满足某种性质的一个子集时，相应的解空间树称为
子集树。
此类问题解的形式为 n 元组（x1,x2,…,xn），分量 xi（i=1,2,…,n）表示第 i 个元素是否在要找的子集中。xi
的取值为 0 或 1，xi=0 表示第 i 个元素不在要找的子集中；xi=1 表示第 i 个元素在要找的子集中。
24．什么是排列树，简述解的形式，分量的含义。
答案：当所给的问题是从 n 个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。
此类问题解的形式为 n 元组（x1,x2,…,xn），分量 xi（i=1,2,…,n）表示第 i 个位置的元素是 xi。n 个元素组
成的集合为 S={1,2,…,n}，xi∈S-{x1,x2,…,xi-1}，i=1,2,…,n
25．简述分支限界法的思想。
答案：是一种在问题的解空间树中搜索问题解的算法，它常以宽度优先或以最小耗费（最大效益）优先的
方式搜索问题的解空间树。分支限界法首先将根结点加入活结点表（用于存放活结点的数据结构），接着
从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还
是保留，舍弃那些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表
中取出一个活结点作为当前扩展结点，重复上述扩展过程，一直持续到找到所需的解或活结点表为空时为
止。
26．简述回溯法和分支限界法的相同点
答案：（1）均需要先定义问题的解空间，确定的解空间组织结构一般都是树或图。（2）在问题的解空间
树上搜索问题解。（3）搜索前均需确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。
（4）搜索过程中必须判断扩展生成的结点是否满足判断条件，如果满足，则保留该扩展生成的结点，否
则舍弃。
27．简述回溯法和分支限界法的不同点
答案：（1）搜索目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求
解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）
搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的
方式搜索解空间树（3）扩展方式不同：在回溯法搜索中，扩展结点一次生成一个孩子结点，而在分支限
界法搜索中，扩展结点一次生成它所有的孩子结点。