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

算法理论知识考核试题一.选择题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。如何选取物品装 入背包，使背包中所装入的物品的总价值最大?物品可以分割。该问题的贪心策略是()。()单选题*A.重量小的优先装入背包B.体积小的优先装入背包C,价值大的优先装入背包D.单位重量的价值大的优先装入背包V42调度问题有n个客户带来n项任务每项加工时间已知，设为tij = l,2，,n。从0时刻开始，陆续安排 到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满 意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是()。()单选题*A.加工时间长的优先安排B.加工时间短的优先安排VC.完成时间早的优先安排D.等待时间长的优先安排43 .找零钱问题的贪心策略是()。()单选题*A.面值大的钱币优先找出B.面值小的钱币优先找出C,面值小于待找钱数且面值最大的优先找出VD.以上都不对44 .物品不可拆开的最优装载问题的贪心策略是()。()单选题*A.体积大的集装箱优先装B.体积小的集装箱优先装C.重量大的集装箱优先装D.重量小的集装箱优先装V45 .会场安排问题的最好的贪匕策略是()。()单选题*A.在不冲突的情况下，开始时间早的优先安排46 在不冲突的情况下，使用时间短的优先安排C.在不冲突的情况下，使用时间长的优先安排D.在不冲突的情况下，结束时间早的优先安排V46.调度问题的算法设计策略是(工()单选题*A.加工时间短的优先安排VB.加工时间长的优先安排C.等待时间短的优先安排D.以上都不对47.以下问题中，哪些问题的分治算法消耗的时间与输入序列无关。()单选题*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 .大整数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 .关于快速排序分治算法时间复杂度描述正确的是()。()多选题*A.快速排序分治算法最好情况下的时间复杂度为O(nlogn)”B.快谢E序分治算法最坏情况下的时间复杂度为O(n 2)7C.快速排序分治算法平均情况下的时间复杂度为O(n 2).D.二快速排序分治算法平均情况下的时间复杂度为O(nlogn).V53 .有关快速排序的分治算法描述正确的是()。()多选题*A.快速排序Aleft,right,选取基准元素的方法，将待排序元素分解为两个子问题。VB.快速排序基准元素的选取可以是待排序元素中的任何一个元素。VC.快速排序划分的两个子问题规模大致相等。D.快速排序Aleft,right,递归算法的边界条件是left>rightV54 .关于二分查找时间复杂度描述正确的是()。()多选题*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的两个子问题。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.二分查找根据比较的结果，好的情况是相等，算法结束。坏的情况是进入其中一个子问题继续查找。VD.若二分查找的序列为Aleft,right,用递归来解决子问题，则边界条件是leftright。V58.分治算法核心就是分而治之,其中的“治”描述正确的是()。()多选题*A.分治法通过治理小问题来治理大问题。VB.分治法递归治理小问题。VC.分治法需要将子问题的解归并成大问题的解。VD.治理子问题时，会有重复性治理子问题的现象。59.分治算法的基本思想描述正确的是()。()多选题*A.分治法将规模大的问题分解成规模较小的问题解决。VB.分治法划分的小问题相互重叠。C.分治法一般采用递归的方法解决子问题。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(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(low<high):#仅当区间长度大于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)#子问题的解合并成原问题的解单选题*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,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个矩阵连乘的最优计算次序为()单选题*A. ( Al ( A2 ( A3 ( A4A5 )B. ( A1A2 )( A3 ( A4A5 )C. (A1A2)( A3A4) A5)D. (A1(A2(A3A4)A5) V68 .关于动态规划和回溯法的区别，以下表述不正确的是。()单选题*A.动态规划和回溯法都可以用来求解最优化问题，但回溯法是基于枚举解的思想，动态规划则是基于 构造子问题最优值关系的方式B.在遇到重叠子问题的时候，动态规划思想会使用存储最优值的方式直接排除，而回溯法一般做法是 设法避环和剪枝，降氐其影响C.在求解相同问题时，动态规划必然比回溯法浪费空间，但是更节约时间V69 .关于动态规划与分治法的区别，表述不正确的是。(”单选题*A.动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交B.动态规划建立在描述子问题最优值关系的状态转移方程基础上，分治法一般不需要建立类似的最优 值之间的数量关系C.分治法能写成递归形式，动态规划不能写成递归形式，D.动态规划一般用来求解最优化问题，分治法多不用于求解最优化问题，70.矩阵连乘问题中，A1矩阵大小是100*5,A2矩阵大小为5*30 , A3矩阵大小为30*10，则乘法次序(A1*A2)*A3需要的乘法次数是。()单选题*A.15000B. 30000C. 45000VD. 45000000071 .规模为5矩阵连乘问题，计算次序有()种。()单选题*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)=Fibonacci(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.最小值问题C.合并排序D.以上都不对76 .以下函数的功能是()def Q(R, low , high):if(low<high):#仅当区间长度大于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.在最佳输入情况下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 < high):()#分解()#递归序列左半部分()#递归序列右半部分Merge(A, low, middle, high)#子问题的解合并成原问题的解。()单选题*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+Lhigh);VC. middle=(low+high)/2; MergeSort(A,middle+l,high); MergeSort(A,low,middle);D. middle=(high-low)/2; MergeSort(A,middle+Lhigh); MergeSort(A,low,middle);78 .矩阵连乘问题中有多个矩阵相乘，问题是安排矩阵相乘的先后顺序，使总乘法次数最少，例如有ABC三个矩阵，则可行的顺序有ABCACBCABCBABACBCA六个。()单选题*正确错误V79 .以动态规划求解0-1背包问题，背包容量可以是任意实数。()单选题*正确错误V80 .有关矩阵连乘问题说法正确的是()。()多选题A.矩阵A L.Aj连乘，其中A k的行列为(p kxq。1旬+ 1,力,其结果矩阵的行列为9 ixq j)0 VB. n个矩阵连乘A 1.A n,其子问题为A i.A j连乘,lwiwjwn,其中i=j表示规模为1的子问题,其需要 的乘法次数为0。VC.设矩阵A i.A j连乘最少的乘法次数为矩阵A i.A j连乘的子问题为矩阵A i.A k连乘和矩 阵A k+l.A j连乘厕最优值的递归关系式表示为cij=cik+ck+lj+p iqjq kD.矩阵连乘问题的时间复杂度为O(n 2)81.动态规划的基本要素是()。()多选题*A.重叠子问题VB.最优子结构性质VC.自底向上的求解方式VD.自顶向下的递归求解方式82.有关动态规划描述正确的是()。()多选题*A.动态规划将多阶段决策问题转化为单阶段决策问题。VB.动态规划往往用于求解某种最优性质的问题。VC.适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。VD.动态规划求解时往往采用填表的方法记录问题最优值。VE.动态规划划分的各子问题与原问题相同，一般递归求解子问题。VF.动态规划求解某种最优性质的问题时，整体的最优值和子问题的最优值之间存在递归关系。V83.设ci皿表示序列Xi和Yj的最长公共子序列的长度。则它的递推关系式为：则根据给定的X二二A, B, C, B, D, A, B和Y=B, D, C, A, B, A从上到下填写缺失值。()单选题*A.2 3 3B. 222C. 3 4 4VD. 33384.给定序歹J X=A, B, C, B, D, A, B和Y=B, D, C, A, B, A,它们的最长公共子序列是(工()单选 题*A. BCBAVB. BCDAC. BDABD. BCAA85.按照III酹排列动态规划的求解步骤，正确的是()(1)递归定义最优值。(2)以自底向上的方式计算出最优值，并记录相关信息。(3)分析最优解子结构性质。(4)构造出最优解。()单选题*A. (1),(2),(3)X4)B. (1)X3),(2)X4)C.,(1),(2),。D. (1),(2),(4),86.以下算法框架中，哪个剧非列树模型的算法设计模式(1()单选题*A. def Backtrack (t): if (t>n):output(x) else:for i in range(l,m+l):if(constraint and bound(t):xt=i做其他相关标识Backtrack(t+1)做其他相关标识的反操作B. def Backtrack (t):if (t>n):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=d(i)if (constraint(t) and bound(t):Backtrack(t+1)D. def Backtrack (int t): if (t>n):output(x) if(constraint(t):做相关标识Backtrack(t+1) 做相关标识的反操作 if(bound(t):做相关标识 Backtrack(t+1)做相关标识的反操作87.最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支 X ,均可求出目标函数值的两个上界Ibl(X)和lb2(X),且总有Ibl(X) >=lb2(X),则如果想用于剪枝,从减 少搜索节点的角度，哪个界限更优？()单选题*A. IblB. lb2VC.二者等价D.依赖于具体输入88.0-1背包问题的解空间结构属于(I ()单选题*A.排列树B.子集树VC.满n叉树D.隐式图89.以下关于回溯法的说法，错误的是()单选题*A.回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历B.回溯法可以适用于求所有解、某个解、最优解等各种问题C.回溯法能够保证生成时间复杂度较低的算法VD.回溯法的编程中，有"当前搜索路径"的概念，需要保存当前路径上节点的状态90 .现有一个用于求解最优化问题的回溯算法,在搜索过程中涉及的函数的描述，错误的是()单选题A.违反约束函数的分支不属于问题的定义域B.违反限界函数的分支不需要访问，不能够得到更优解C.目标函数是衡量解的优劣程度的函数D.在目标函数最小化问题中，限界函数应当使用上界V91 .关于旅行商问题的说法，错误的是()单选题*A.旅行商问题的解空间与最短路径问题相同V92 旅行商问题的优化目标是回路长度最短C.有4个点的旅行商问题的两个回路，ABCDA和BCDAB ,实际上是两个相同的回路D.旅行商问题无法用穷举求解，因为回路数目太多92.以下有关旅行商问题的递归代码，根据注释判断空缺部分填写正确的是(1 def Traveling(t): ()# 到达叶子结点#g存储图的邻接矩阵，x是存储解向量，初始化为xl:n=l,2，,n,cl是当前已走的路经长 度，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层搜索完毕回溯到第t层cl-=gxt-lxj xt,xj=xj,xto ( C )单选题*A.空 1 : if(t=n)空 2 : for(j=t;j<=n;j+)B.空1 : if(t>n-l)空 2 : for(j=l;j<=n;j+)C.空1 : if(t>n)空 2 : for(j=t;j<=n;j +)VD.空 1 : if(t>=n-l)空 2 : for(j = l;j<=n;j+)93.有关回溯法说法正确的是（工（）多选题*A.回溯法是一种深度优先搜索的搜索算法VB.回溯法是一种"能进则进、进不了则换、换不了则退（回溯）”的搜索方法VC.回溯法是一种宽（广）度优先搜索的搜索算法D.回溯法是一种最大效益或最小费用优先搜索的方法94有关n皇后问题说法正确的是（工（）侈选题*A.该问题的解的形式为（xL x2，xn）, xi表示第i个皇后位于第i行、第xi列（i=l,23解VB.该问题的初始状态为：（0,00）7C.该问题的解空间的组织结构可以是排列树，也可以是满n叉树。VD.该问题只需要设置约束条件，不需要限界条件。VE、该问题解向量中的任意两个分量xi,xj满足：xi/xj且|ij|H|xi-xj|V95.两个分量 xi,xj 满足:xi'xj 且|i-j|r|xi-xj|下述有关搜索过程描述错误的是（1（）多选题*A.当解空间结构是一棵树时,搜索从根开始B.搜索过程中,正在生成孩子的节点称为扩展节点C.搜索过程中，所有孩子节点均已生成的节点称为扩展节点VD.搜索过程中，所有孩子节点均已生成的节点称为活结点节点VE.搜索过程中所有孩子节点均已生成的节点称为死节点VF.搜索过程动态生成的树称为搜索树V96.以下描述中，影响回溯法的搜索效率的是（1（）多选题*A.问题的解空间，即搜索范围，B.设定的约束函数和限界函数，C.搜索方法D.满足约束条件和限界条件的节点数目V97.以下有关子集树的描述中说法正确的是（工（）多选题*A.当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为 子集树。VB.子集树模型解的形式为n元组（xltx2，,xn ）,分量xi（i=l,2，,n）表示第i个元素是否在子集中。VC.子集树模型的解向量中,分量xi的取值为0或1, xi=O表示第i个元素不在子集中;xi=l表示第i 个元素在子集中。VD.旅行售货员问题可以开用子集树模型求解E.最优装载问题可以采用子集树模型求解F. 0-1背包问题可以采用子集树模型求解98 .有关子集树描述中，说法错误的是（工（）多选题*A.子集树的根结点为问题的初始状态VB.子集树的中间结点为搜索过程中形成的某中间状态VC.子集树的叶子结点为问题结束状态，D.子集树的分支表示从一个状态过渡到另一个状态的行为VE.子集树中从根结点到叶子结点的路径是一个可行解（一个子集）VF.子集树的深度等于问题的规模加IV99 .有关0-1背包问题说法正确的是（工（）多选题*A.该问题的解的形式为（xi, x2, xn）, xi（i=L2,3,.n）的取值为0或IVB.该问题的解空间的组织结构可以是排列树。C.该问题需要设置约束条件，也可以设置限界条件。VD.该问题只需要设置约束条件，不需要限界条件。100 .有关下图说法正确的是（）。（）多选题*A.该树表示的问题的规模为3VB.该树为一棵排列树VC.该树表示的问题规模为4。D.该树为一棵子集树101 .有关批处理作业调度问题说法正确的是（1（）多选题*A.该问题的解形式为（xLx2,.,xn） A取值范围为令S=12._n则xiwS-xl,x2，,xi-1 >1,2，,nVB.该问题的解空间的组织结构是排列树。VC.该问题需要设置约束条件，不需要限界条件。D.该问题不需要设置约束条件，只需要限界条件。VE.该问题既需要设置约束条件，也需要限界条件。V102 .有关旅行售货员问题说法正确的是（1（）单选题*A.该问题的解形式为（xLx2,.,xn）, xi 取值范围为:令 S=Q2.,n,则 xi£SxLx2,.,xi-lB.该问题的解空间的组织结构是排列树。VC.该问题需要设置约束条件，不需要限界条件。D.该问题不需要设置约束条件，只需要限界条件。E.该问题既需要设置约束条件，也可以设置限界条件。103 .有关回溯法说法正确的是（工（）多选题*A.回溯法是一种深度优先搜索的搜索算法VB.回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法VC.回溯法是一种宽（广）度优先搜索的搜索算法D.回溯法是一种最大效益或最小费用优先搜索的方法104有关n皇后问题说法正确的是（工（）多选题*A.该问题的解的形式为（xl, x2，xn） , xi表示第i个皇后位于第i行、第xi列（i=L23.n）VB.该问题的初始状态为：（0,0，,0）7C.该问题的解空间的组织结构可以是排列树，也可以是满n叉树。VD.该问题只需要设置约束条件，不需要限界条件。VE.该问题解向量中的任意两个分量xi,xj满足：xirxj且|i-j|H|xi-xj|V105.以下描述中,影响回溯法的搜索效率的是（工（）多选题*A.问题的解空间，即搜索范围VB.设定的约束函数和限界函数。C.搜索方法D.满足约束条件和限界条件的节点数目V106.有关随机化算法错误的是（ （）单选题*A.随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效 果,这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。B.数值随机化算法常用于数值问题的求解，所得到的解都是精确解。VC.蒙特卡罗算法用于求问题的准确解，但解不一定正确。D.舍伍德算法引入随机性来降低最坏情况出现的概率，从而消除或减少问题好坏实例之间的时间消耗 的差异。107.有关估算n值的随机化算法说法错误的是（工（）单选题*A.估算n值的随机化算法估算的近似值的精度随算法消耗的时间的增加而提高B.估算TI值的随机化算法随机实验次数越多，估算的TT值精度越高C.估算TI值的随机化算法是数值随机化算法。D.估算TI值的随机化算法估算的近似值的精度与算法消耗的时间无关V108.有关主元素问题的蒙特卡罗算法说法错误的是。（）单选题*A.主元素问题的蒙特卡罗算法每次执行都返回True或False ,True表示有主元素,False表示没有主 兀素。B.主元素问题的蒙特卡罗算法返回True的解是正确解，False的解不一定是正确解。C.主元素问题的蒙特卡罗算法得到正确解的概率随算法消耗的时间的增加而降低。VD.主元素问题的蒙特卡罗算法得到的解为正确解的概率大于0.5。109.有关素数测试问题算法说法正确的是。（）单选题*A.根据Wilson定理,可以设计素数测试的随机化算法。B.可以采用试除法，设计素数测试的随机化算法。C.根据二次探测定理设计的素数测试蒙特卡罗算法得到的解为正确解的概率大于0.5VD.根据二次探测定理，可以设计素数测试的蒙特卡罗算法,当算法返回True时，解一定正确；当返回 False时，解不一定正确。110有关n皇后问题的拉斯维加斯算法说法正确的是。（）单选题*A. n皇后问题的拉斯维加斯算法可以采用对不冲突的多个列位置进行随机。VB. n皇后问题的拉斯维加斯算法得到接的概率小于0。C. n皇后问题的拉斯维加斯算法每次运行都能得到一种n个皇后的放置方案。D.多次运行n皇后问题的拉斯维加斯算法并不能提高算法得到解的概率。111.有关随机快速排序算法说法错误的是。（）单选题*A.随机快速排序与快速排序的区别是随机快速排序随机选择基准元素，而快速排序的确定性算法选择B.最好情况和最坏情况的时间复杂度的算术平均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（nlogn）。D.随机快速排序每次运行都能够得至懈，但是得到的解不一定正确。V112.有关整数n的因子分解问题说法正确的是。（）单选题*A.整数的因子分解就是将整数n分解多个因子的乘积，并不要求因子的素数性。B.整数的因子分解问题不可以转化为因子分割问题。C.因子分割不可以采用试除法找出整数n的因子。D. Pollard算法，只要给足够的时间，肯定能找到整数n的因子。V113.以下有关随机数产生的线性同余法说法正确的是。（）单选题*A.线性同余法产生的随机数是伪随机数。VB.线性同余法的系数是模数的倍数时，随机数的随机性能好。C,线性同余法的系数、增量、模数越大，随机数的随机性能越差。D.线性同余法的系数与模数互质，随机数的随机性能差。114.以下有关随机选择第k小算法正确的是。（）单选题*A.随机选择第k小算法中的随机性和随机快速排序的随机性一样,都是随机选择基准元素。VB.随机选择第k小算法是对线性时间选择算法中划分过程进行了随机其他和线性时间选择算法一样。C.随机选择第k小算法划分过程结束后，要在比基准元素小的子问题中查找第k小。D.随机选择第k小算法中的随机性和随机快速排序的随机性不同随机快速排序是随机选择基准元素, 随机选择第k小算法随机划分、比较。115.通过多次执行的方式提高随机算法得到正确解的概率的算法是。（）单选题*A.数值随机化算法B.蒙特卡罗算法VC.拉斯维加斯算法D.舍伍德算法116.以下算法中，通过多次执行能够提高算法得到解的概率的算法是。（）单选题*A.拉斯维加斯算法VB.舍伍德算法C.蒙特卡罗算法D.数值随机化算法117.以下算法中，哪个算法用于求问题的近似解，求得近似解的精确程度与算法消耗的时间相关。（） 单选题*A.蒙特卡罗算法B.拉斯维加斯算法C,数值随机化算法VD.舍伍德算法118.有关随机化算法正确的是。（）多选题*A.随机化算法的特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效 果,这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。VB.数值随机化算法常用于数值问题的求解，所得到的解往往都是近似解，而且近似解的精度随计算时 间的增加不断提高。VC.蒙特卡罗算法用于求问题的准确解，但解不一定正确。VD.拉斯维加斯算法绝不返回错误的解，但有时得不到问题的解。可以通过多次执行提高算法得到解的概率。VE.舍伍德算法用于当一个确定性算法在最坏情况下的计算时间复杂性与