算法理论知识考核试题及答案.docx

《算法理论知识考核试题及答案.docx》由会员分享，可在线阅读，更多相关《算法理论知识考核试题及答案.docx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法理论知识考核试题一.选择题1.2 n=0(100n 2)单 *A.正确B.错误V2.10=B(logl0)单选题*A.正确VB.错误3.2 n=0(3 n)。()单选题*A.正确，B.错误4.logn 2=0(logn+5)单选题*A.正确VB.错误5 .针对JII页序查找算法，影响它时间复杂度的因素只有算法的输入序列()单选题*A.正确B.错误V6 .n!的时间复杂度为0(n)单选题*A.正确VB.错误41.背包问题:n个物品和1个背包。对物品i,其价值为vi,重量为wi,背包的容量为W。如何选取物品装 入背包，使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是()。()

2、单选题*A.重量小的优先装入背包B.体积小的优先装入背包C,价值大的优先装入背包D.单位重量的价值大的优先装入背包V42调度问题有n个客户带来n项任务每项加工时间已知，设为tij = l,2，,n。从0时刻开始，陆续安排 到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满 意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是()。()单选题*A.加工时间长的优先安排B.加工时间短的优先安排VC.完成时间早的优先安排D.等待时间长的优先安排43 .找零钱问题的贪心策略是()。()单选题*A.面值大的钱币优先找出B.面值小的钱币优先找出C,面值

3、小于待找钱数且面值最大的优先找出VD.以上都不对44 .物品不可拆开的最优装载问题的贪心策略是()。()单选题*A.体积大的集装箱优先装B.体积小的集装箱优先装C.重量大的集装箱优先装D.重量小的集装箱优先装V45 .会场安排问题的最好的贪匕策略是()。()单选题*A.在不冲突的情况下，开始时间早的优先安排46 在不冲突的情况下，使用时间短的优先安排C.在不冲突的情况下，使用时间长的优先安排D.在不冲突的情况下，结束时间早的优先安排V46.调度问题的算法设计策略是(工()单选题*A.加工时间短的优先安排VB.加工时间长的优先安排C.等待时间短的优先安排D.以上都不对47.以下问题中，哪些问题的

4、分治算法消耗的时间与输入序列无关。()单选题*A.二分查找B.合并排序VC.快速排序D.最小值问题48.有关2个n位大整数乘法问题说法正确的是(1()多选题*A.将两个n位大整数分解为4个规模大致相等的n/2位整数的整数乘法问题VB.递归解决4个子问题VC.子问题的解需要归并成原问题的解VD.子问题的解本身就是原问题的解49.分治算法的步骤有(1()多选题*A.分解VB.治理VC.递归D.合并50 .分治算法的思想是()多选题*A,将规模较大的问题划分为规模较小的相同子问题VB.子问题之间相互独立VC.子问题之间不相互独立D.递归解决划分得到的子问题VE.将子问题的解归并得至嫄问题的解V51

5、.大整数A和B的乘法，将A分成位数大致相等的两部分A1和A2，将B分成位数大致相等的两部 分B1和B2,以下描述正确的是()。()多选题*A.子问题的解归并为原问题解的方法为:AxB=10nAlBl+10n/2(AlB2+A2Bl)+A2B2VB.子问题的解归并为原问题解的方法为：AxB = 10nAlBl + 10n/2(Al-A2)(B2- B1)+A1B1+A2B2)+A2B2VC.子问题的解归并为原问题解的方法为:AxB=10nAlBl + 10n/2(Al+A2)(Bl+B2)-AlBl- A2B2)+A2B2VD.以上方法都不对。52 .关于快速排序分治算法时间复杂度描述正确的是(

6、)。()多选题*A.快速排序分治算法最好情况下的时间复杂度为O(nlogn)”B.快谢E序分治算法最坏情况下的时间复杂度为O(n 2)7C.快速排序分治算法平均情况下的时间复杂度为O(n 2).D.二快速排序分治算法平均情况下的时间复杂度为O(nlogn).V53 .有关快速排序的分治算法描述正确的是()。()多选题*A.快速排序Aleft,right,选取基准元素的方法，将待排序元素分解为两个子问题。VB.快速排序基准元素的选取可以是待排序元素中的任何一个元素。VC.快速排序划分的两个子问题规模大致相等。D.快速排序Aleft,right,递归算法的边界条件是leftrightV54 .关于

7、二分查找时间复杂度描述正确的是()。()多选题*A.二分查找算法最好情况下的时间复杂度为O(1).VB.二分查找算法最坏情况下的时间复杂度为0(n).C.二分查找算法最坏情况下的时间复杂度为O(logn).VD.二分查找算法平均情况下的时间复杂度为O(logn).V55 .有关合并排序的分治算法描述正确的是()。()多选题*A.合并排序Aleft,right的元素，采用的分解方法是(left+right)/2。VB.合并排序Aleft,right的元素，采用的分解方法是(right-left)/20C.合并排序Aleft,right的元素，需要治理规模大致等于(right-left+l)/2的

8、两个子问题。VD.合并排序需要将两个有序的子序列归并成一个有序的子序列。V56 .有关循环赛日程表分治算法描述正确的是()。()多选题*A.循环赛日程表给定2 k个运动员，采用2 k/2的方法将运动员分成两组。VB.循环赛日程表算法先安排组内的赛程，再安排两组对打。VC.循环赛日程表算法的边界条件是两个运动员,一天的比赛。VD.循环赛日程表算法为2 k个运动员安排了 2 k-1天的比赛。57 .下述关于二分查找(折半查找)算法描述正确的是()。()多选题A.二分查找是在任意给定的n个元素序列中查找指定元素。B.二分查找的序列为Aleft,right,分解操作为:(right-left)/2C.

9、二分查找根据比较的结果，好的情况是相等，算法结束。坏的情况是进入其中一个子问题继续查找。VD.若二分查找的序列为Aleft,right,用递归来解决子问题，则边界条件是leftright。V58.分治算法核心就是分而治之,其中的“治”描述正确的是()。()多选题*A.分治法通过治理小问题来治理大问题。VB.分治法递归治理小问题。VC.分治法需要将子问题的解归并成大问题的解。VD.治理子问题时，会有重复性治理子问题的现象。59.分治算法的基本思想描述正确的是()。()多选题*A.分治法将规模大的问题分解成规模较小的问题解决。VB.分治法划分的小问题相互重叠。C.分治法一般采用递归的方法解决子问题

10、。VD.分治法划分的小问题规模小到一定程度时容易解决。V60.根据下面斐波那契数列的递归算法，可知斐波那契数列的第n项的递归式为( def Fibonacci(int num): if(num = 0 | num = 1):return num return Fibonacci(num-+ Fibonacci(num - 2)。()单选题*A. Fibonacci(n)=0 当 n=0 时B. Fibonacci(n)=l 当 n=l 时C. Fibonacci(n)=Fibonacci(n-l) + Fibonacci(n-2)当 n1 时VD. Fibonacci(n)=Fibonacci

11、(n-2)+Fibonacci(n-3)当 n1 时61.下面代码为求n !的递归算法，该代码反应的n!问题递归实现的停止条件(边界条件)为(I ()def fun(n):if (n = 1):return 1else:return fun(n -1) * n单选题*A. n!=l 当 n=0 时B. n!=l 当 n=l 时。C. n!=l 当 n1 时D. n!=l 当 n = 1 时62 .以下哪个问题的时间复杂度与输入序列有关()单选题*A.二分查找VB.最小值问题C.合并排序D.以上都不对63 .以下函数的功能是()def Q(R, low , high):if(lowhigh):#

12、仅当区间长度大于1时才须排序pivotpos=Partition(R,low,high) #划分后的基准元素所对应的位置Q(R,low,pivotposl)#对左区间递归排序Q(R,pivotpos+l,high)#对右区间递归排序单选题*A.二分查找B.二分求最值C.合并排序D.快速排序V64 .以下代码功能为合并排序，请根据注释按照数顺序选择合适的语句填入对应的括号。def MergeSort(A , low , high):if (low high):()#分解()#递归序列左半部分()#递归序列右半部分Merge(A, low, middle, high)#子问题的解合并成原问题的解单

13、选题*A. middle=(high-low)/2; MergeSort(A,low,middle); MergeSort(A,middle+l/high);B. middle=(low+high)/2; MergeSort(A,low,middle); MergeSort(A,middle+l,high);VC. middle=(low+high)/2; MergeSort(A,middle+l,high); MergeSort(A,low,middle);D. middle=(high-low)/2; MergeSort(A,middle+l,high); MergeSort(A,low,

14、middle);65.棋盘覆盖问题的分解方法为(工()单选题*A.B.C.VD.以上分解的方法都不对66.合并排序的分治算法时间复杂度的是()。()单选题*A. O(logn)B. O(nlogn)VC.D.67.解决给定的5个矩阵连乘问题：矩阵A1 ( 3x2 1 A2 ( 2x5 A3 ( 5x10 A4 (10x2 )和A5 (2x3 )，设表示Ai.Aj的最优计算次序对应的乘法计算次数(最优值)，P为存储矩阵行列的数组， 其中Pi是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：，根据该递归关系式，求解过程 中得到下面最优决策的二维表：由此，可得上述5个矩阵连乘的最优计算次

15、序为()单选题*A. ( Al ( A2 ( A3 ( A4A5 )B. ( A1A2 )( A3 ( A4A5 )C. (A1A2)( A3A4) A5)D. (A1(A2(A3A4)A5) V68 .关于动态规划和回溯法的区别，以下表述不正确的是。()单选题*A.动态规划和回溯法都可以用来求解最优化问题，但回溯法是基于枚举解的思想，动态规划则是基于 构造子问题最优值关系的方式B.在遇到重叠子问题的时候，动态规划思想会使用存储最优值的方式直接排除，而回溯法一般做法是 设法避环和剪枝，降氐其影响C.在求解相同问题时，动态规划必然比回溯法浪费空间，但是更节约时间V69 .关于动态规划与分治法的区

16、别，表述不正确的是。(”单选题*A.动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交B.动态规划建立在描述子问题最优值关系的状态转移方程基础上，分治法一般不需要建立类似的最优 值之间的数量关系C.分治法能写成递归形式，动态规划不能写成递归形式，D.动态规划一般用来求解最优化问题，分治法多不用于求解最优化问题，70.矩阵连乘问题中，A1矩阵大小是100*5,A2矩阵大小为5*30 , A3矩阵大小为30*10，则乘法次序(A1*A2)*A3需要的乘法次数是。()单选题*A.15000B. 30000C. 45000VD. 45000000071 .规模为5矩阵连乘问题，计算次序有()

17、种。()单选题*A. 10B. 12C. 14VD. 1672 .根据下面斐波那契数列的递归算法，可知斐波那契数列的第n项的递归式为(工defFibonacci(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)=l 当 n=l 时C. Fibonacci(n)=Fibonacci(n-l) + Fibonacci(n-2)当 n1 时VD. Fibonacci(n)=Fibonac

18、ci(n-2)+Fibonacci(n-3)当 n1 时.下面代码为求n !的递归算法，该代码反应的n!问题递归实现的停止条件(边界条件)为(1 () def fun(n):if (n = 1):return 1else:return fun(n -1) * n单选题*A. n! = l 当 n=0 时B. n! = l 当 n=l 时VC.n!=l 当 n1 时D. n!=l 当 n=l 时74 .合并排序的空间复杂度为()。()单选题*A. 0(logn)B. 9(n)VC. 0(nlogn)D. 0(n*n)75 .以下哪个问题的时间复杂度与输入序列有关(工()单选题*A.二分查找VB.

19、最小值问题C.合并排序D.以上都不对76 .以下函数的功能是()def Q(R, low , high):if(lowhigh):#仅当区间长度大于1时才须排序pivotpos=Partition(R,low,high) #划分后的基准元素所对应的位置Q(R,low,pivotpos-l)#对左区间递归排序Q(R,pivotpos+l,high)#对右区间递归排序单选题*A,二分查找7 .递归是指自己间接或直接调用自身单选题*A.正确V8 .错误8.算法的基本特征有（）多选题*A.输入。B.输出。C.有限性VD.确定性VE.可行性V9.渐进复杂性的含义是（）情况下的复杂性。单选题*A.在最佳输

20、入情况下B.问题规模趋向于无穷，C.在最喻入情况下D.平均各种输入之后lO.n个连续自然数al.an连加和问题算法（利用等差数列求和公式）的输入可以是什么（ 多选 题*A. al, nVB.an,nVC. al,anVD. al,an,nV11.平均时间复杂度是指（）单选题*A.各种情况时间复杂度按概率的加权平均VB.二分求最值C.合并排序D.快速排序V77.以下代码功能为合并排序，请根据注释按照数顺序选择合适的语句填入对应的括号。def MergeSort(A , low , high):if (low n):output(x) else:for i in range(l,m+l):if(c

21、onstraint and bound(t):xt=i做其他相关标识Backtrack(t+1)做其他相关标识的反操作B. def Backtrack (t):if (tn):output(x) else:for i in range(t,n + l):xt, xi*-xiz xtif (constraint(t) and bound(t):Backtrack(t+1)xt, xi-xi, xtVC. def Backtrack (int t):if (t = n):output(x)else:for i inrange(s(n,t),e(n,t):range(s(n,t),e(n,t):xt

22、=d(i)if (constraint(t) and bound(t):Backtrack(t+1)D. def Backtrack (int t): if (tn):output(x) if(constraint(t):做相关标识Backtrack(t+1) 做相关标识的反操作 if(bound(t):做相关标识 Backtrack(t+1)做相关标识的反操作87.最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支 X ,均可求出目标函数值的两个上界Ibl(X)和lb2(X),且总有Ibl(X) =lb2(X),则如果想用于剪枝,从减 少搜索节点的角度，哪

23、个界限更优？()单选题*A. IblB. lb2VC.二者等价D.依赖于具体输入88.0-1背包问题的解空间结构属于(I ()单选题*A.排列树B.子集树VC.满n叉树D.隐式图89.以下关于回溯法的说法，错误的是()单选题*A.回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历B.回溯法可以适用于求所有解、某个解、最优解等各种问题C.回溯法能够保证生成时间复杂度较低的算法VD.回溯法的编程中，有当前搜索路径的概念，需要保存当前路径上节点的状态90 .现有一个用于求解最优化问题的回溯算法,在搜索过程中涉及的函数的描述，错误的是()单选题A.违反约束函数的分支不属于问题的定义域B.违反限

24、界函数的分支不需要访问，不能够得到更优解C.目标函数是衡量解的优劣程度的函数D.在目标函数最小化问题中，限界函数应当使用上界V91 .关于旅行商问题的说法，错误的是()单选题*A.旅行商问题的解空间与最短路径问题相同V92 旅行商问题的优化目标是回路长度最短C.有4个点的旅行商问题的两个回路，ABCDA和BCDAB ,实际上是两个相同的回路D.旅行商问题无法用穷举求解，因为回路数目太多92.以下有关旅行商问题的递归代码，根据注释判断空缺部分填写正确的是(1 def Traveling(t): ()# 到达叶子结点#g存储图的邻接矩阵，x是存储解向量，初始化为xl:n=l,2，,n,cl是当前已

25、走的路经长 度，bestl 是当前已找到的最短路径长度。if(gxn 1 !=qo and (cl+gxnl bestl ) ): for j in range(l,n+l): bestxj=xj bestl=cl+gxnl else:#没有到达叶子结点 ()#控制当前节点的分 支数目，即对目的所有可能的取值。if( gxt-lxj !=oo and(cl+gxt-lxj bestl): #保存第t 个要去的城市编号到x用中，进入到第t+1层 xt,xj =xj,xt #交换两个元素的值cl+=gxt-lxj Traveling(t+1)#从第t+1层的扩展结点继续搜索 #第t+l层搜索完毕回

26、溯到第t层cl-=gxt-lxj xt,xj=xj,xto ( C )单选题*A.空 1 : if(t=n)空 2 : for(j=t;jn-l)空 2 : for(j=l;jn)空 2 : for(j=t;j=n-l)空 2 : for(j = l;j1,2，,nVB.该问题的解空间的组织结构是排列树。VC.该问题需要设置约束条件，不需要限界条件。D.该问题不需要设置约束条件，只需要限界条件。VE.该问题既需要设置约束条件，也需要限界条件。V102 .有关旅行售货员问题说法正确的是（1（）单选题*A.该问题的解形式为（xLx2,.,xn）, xi 取值范围为:令 S=Q2.,n,则 xiSx

27、Lx2,.,xi-lB.该问题的解空间的组织结构是排列树。VC.该问题需要设置约束条件，不需要限界条件。D.该问题不需要设置约束条件，只需要限界条件。E.该问题既需要设置约束条件，也可以设置限界条件。103 .有关回溯法说法正确的是（工（）多选题*A.回溯法是一种深度优先搜索的搜索算法VB.回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法VC.回溯法是一种宽（广）度优先搜索的搜索算法D.回溯法是一种最大效益或最小费用优先搜索的方法104有关n皇后问题说法正确的是（工（）多选题*A.该问题的解的形式为（xl, x2，xn） , xi表示第i个皇后位于第i行、第xi列（i=L23

28、.n）VB.该问题的初始状态为：（0,0，,0）7C.该问题的解空间的组织结构可以是排列树，也可以是满n叉树。VD.该问题只需要设置约束条件，不需要限界条件。VE.该问题解向量中的任意两个分量xi,xj满足：xirxj且|i-j|H|xi-xj|V105.以下描述中,影响回溯法的搜索效率的是（工（）多选题*A.问题的解空间，即搜索范围VB.设定的约束函数和限界函数。C.搜索方法D.满足约束条件和限界条件的节点数目V106.有关随机化算法错误的是（ （）单选题*A.随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效 果,这两次求解问题所需的时间甚至所得到的结果可

29、能会有相当大的差别。B.数值随机化算法常用于数值问题的求解，所得到的解都是精确解。VC.蒙特卡罗算法用于求问题的准确解，但解不一定正确。D.舍伍德算法引入随机性来降低最坏情况出现的概率，从而消除或减少问题好坏实例之间的时间消耗 的差异。107.有关估算n值的随机化算法说法错误的是（工（）单选题*A.估算n值的随机化算法估算的近似值的精度随算法消耗的时间的增加而提高B.估算TI值的随机化算法随机实验次数越多，估算的TT值精度越高C.估算TI值的随机化算法是数值随机化算法。D.估算TI值的随机化算法估算的近似值的精度与算法消耗的时间无关V108.有关主元素问题的蒙特卡罗算法说法错误的是。（）单选题

30、*A.主元素问题的蒙特卡罗算法每次执行都返回True或False ,True表示有主元素,False表示没有主 兀素。B.主元素问题的蒙特卡罗算法返回True的解是正确解，False的解不一定是正确解。C.主元素问题的蒙特卡罗算法得到正确解的概率随算法消耗的时间的增加而降低。VD.主元素问题的蒙特卡罗算法得到的解为正确解的概率大于0.5。109.有关素数测试问题算法说法正确的是。（）单选题*A.根据Wilson定理,可以设计素数测试的随机化算法。B.可以采用试除法，设计素数测试的随机化算法。C.根据二次探测定理设计的素数测试蒙特卡罗算法得到的解为正确解的概率大于0.5VD.根据二次探测定理，可

31、以设计素数测试的蒙特卡罗算法,当算法返回True时，解一定正确；当返回 False时，解不一定正确。110有关n皇后问题的拉斯维加斯算法说法正确的是。（）单选题*A. n皇后问题的拉斯维加斯算法可以采用对不冲突的多个列位置进行随机。VB. n皇后问题的拉斯维加斯算法得到接的概率小于0。C. n皇后问题的拉斯维加斯算法每次运行都能得到一种n个皇后的放置方案。D.多次运行n皇后问题的拉斯维加斯算法并不能提高算法得到解的概率。111.有关随机快速排序算法说法错误的是。（）单选题*A.随机快速排序与快速排序的区别是随机快速排序随机选择基准元素，而快速排序的确定性算法选择B.最好情况和最坏情况的时间复杂

32、度的算术平均C.各种情况时间复杂度按概率的算术平均D.出现可能性最高的情况下的时间复杂度12 .算法的常见描述方式不包括（）单选题*A.代码B.甘特图VC.伪代码D.渐呈图13 .算法的基本特性不包括（）单选题*A.先进性VB.有穷性C.有输入输出D.无二义性14 .阶乘问题求n!算法的时间复杂度为（1 单选题*A. nVB. n!C. 2nD. nA215 .二分搜索（二分查找）算法的时间复杂度是（ 单选题*A. nB. lognVC. nA2 固定位置的元素作为基准元素。B.随机快速排序通过对快速排序引入随机性，降低了快速排序最好和最坏情况出现的概率。C.随机快速排序的时间复杂度趋于O（n

33、logn）。D.随机快速排序每次运行都能够得至懈，但是得到的解不一定正确。V112.有关整数n的因子分解问题说法正确的是。（）单选题*A.整数的因子分解就是将整数n分解多个因子的乘积，并不要求因子的素数性。B.整数的因子分解问题不可以转化为因子分割问题。C.因子分割不可以采用试除法找出整数n的因子。D. Pollard算法，只要给足够的时间，肯定能找到整数n的因子。V113.以下有关随机数产生的线性同余法说法正确的是。（）单选题*A.线性同余法产生的随机数是伪随机数。VB.线性同余法的系数是模数的倍数时，随机数的随机性能好。C,线性同余法的系数、增量、模数越大，随机数的随机性能越差。D.线性同

34、余法的系数与模数互质，随机数的随机性能差。114.以下有关随机选择第k小算法正确的是。（）单选题*A.随机选择第k小算法中的随机性和随机快速排序的随机性一样,都是随机选择基准元素。VB.随机选择第k小算法是对线性时间选择算法中划分过程进行了随机其他和线性时间选择算法一样。C.随机选择第k小算法划分过程结束后，要在比基准元素小的子问题中查找第k小。D.随机选择第k小算法中的随机性和随机快速排序的随机性不同随机快速排序是随机选择基准元素, 随机选择第k小算法随机划分、比较。115.通过多次执行的方式提高随机算法得到正确解的概率的算法是。（）单选题*A.数值随机化算法B.蒙特卡罗算法VC.拉斯维加斯

35、算法D.舍伍德算法116.以下算法中，通过多次执行能够提高算法得到解的概率的算法是。（）单选题*A.拉斯维加斯算法VB.舍伍德算法C.蒙特卡罗算法D.数值随机化算法117.以下算法中，哪个算法用于求问题的近似解，求得近似解的精确程度与算法消耗的时间相关。（） 单选题*A.蒙特卡罗算法B.拉斯维加斯算法C,数值随机化算法VD.舍伍德算法118.有关随机化算法正确的是。（）多选题*A.随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效 果,这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。VB.数值随机化算法常用于数值问题的求解，所得到的解往往都是近似解，而且近似解的精度随计算时 间的增加不断提高。VC.蒙特卡罗算法用于求问题的准确解，但解不一定正确。VD.拉斯维加斯算法绝不返回错误的解，但有时得不到问题的解。可以通过多次执行提高算法得到解的概率。VE.舍伍德算法用于当一个确定性算法在最坏情况下的计算时间复杂性与