计算机科学_算法设计与分析_算法考试题库及答案.pdf

《计算机科学_算法设计与分析_算法考试题库及答案.pdf》由会员分享，可在线阅读，更多相关《计算机科学_算法设计与分析_算法考试题库及答案.pdf（176页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法分析与设计 试卷自测一、单 选 题(题 数：1 3 6,考试抽取20道，分值20分)1折半查找长度为n 的线性表，平均查找长度为()n log n nlogn(n+l)/2正确答案：B2中印战争西山口战役刘伯承提出的 打头、截尾、剖腹、击背”是()思想.贪心 分治递推 枚举正 确 答 案：B3确 定 第i阶段的收益函数和从第i阶段出发到第n阶段所获得收益的最优值,建立动态规划基本方程。这种方法是()正推反推 自顶向下 自底向上正 确 答 案：B4通常我们讲的时间复杂度是()情况下的时间复杂度。平均最好 最坏 任意正确答案：C5logn2=()(n1/2)e o J c o正确答案：D60-

2、1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估 计 是？40 60 30 50正 确 答 案：A7下面不是影响回溯算法效率的主要因素的是（）满足约束函数的Xk值的个数xk的搜索顺序 优先级 上界函数约束的所有xk的个数正 确 答 案：C8使用分治法求解不需要满足的条件是（）。子问题不能够重复子问题的解可以合并 原问题和子问题使用相同的方法求解 子问题必须是一样的正 确 答 案：D9以下不可以使用分治法求解的是()。循环赛日程表 最接近点对问题 最大子段和问题 0/1背包问题正 确 答 案：D10Floyd算 法 的 时 间 复 杂 度 为0()mnm+nlgn

3、mlognnA3正确答案：D11堆排序的时间复杂度是0()。0(n)2n2 n nlogn正确答案：D12随机快速排序的时间复杂度是（）。0（n）0(2n)0(n2)O(nlogn)正 确 答 案：D13下面关于贪心算法错误的是（）贪心算法总能找到可行解，并且是最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征.贪心算法T S预处理后再进彳强优化选择。贪心选择中每一步的局部最优解都构成全局最优解的一部分.正 确 答 案：A14下面有关递归与循环的说法错误的是（）递归是比循环更灵活的重复操作的机制。递归是一种比循环更强、更好用的实现 重复操作 的机制。当问题需要 后进先

4、出 的操作时,用递归算法更有效。递归方法相比循环方法大大地减少了算法的计算量。正 确 答 案：D15下面不是备忘录算法特点的是（）递推关系自顶向下计算 最优子结构子问题独立正 确 答 案：D16含 负 权 的 最 短 路 问 题 一 般 使 用（）求解。动态规划贪心算法 分治算法 网络流算法正 确 答 案：A17未来与过去无关,指的是（）性质。贪心选择 无后效性最优子结构重叠子问题正 确 答 案：B18设f C O、g (N)是定义在正数集上的正函数,如果存在正的常数C和自然数工，使得当、时有f(N)W Cg (N),则称函数f(N)当N充分大时有上界g (N),记作f(N)=0 (g(N)，

5、即 f(N)的 阶()g (N)的阶。A不高于不低于 等价于 逼近正 确 答 案：A19减少子问题合并的时间，就是减少时间复杂度函数T(n)=aT(n/b)+f(n)中的()值。ab f(n)n正确答案：C20动态规划方法使用()计算方式。自顶向下自高到低 自低到高 自底向上正确答案：D21下列算法中，通常以深度优先方式系统搜索问题解的是（）备忘录法 动态规划法 贪心法 回溯法正确答案：D22把任意一个最优解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是（）领先 反证 交换论证D界正确答案：C23快速排序的时间复杂度是0 ()A、nn2D n l o g n正确答案：c24Dinic算

6、法的时间复杂度为()A 2m nmnn/nD m2l o g C正确答案：A25便于实现集合操作的子集生成算法是()位向量法 二进制法 增量构造法正确答案：B26设 有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()法.冒泡排序 快速排序合并排序基数排序正确答 案：A27从所有候选答案中去搜索正确的解，这 是（）算法。嵯 递推正确答案：B28在下列算法中有时找不到问题解的是（）。蒙特卡罗算法拉斯维加斯算法 舍伍德算法 数值随机算法正确答案：B29从大规模问题逐步化为小规模问题的算法是（）递归正推 倒推 迭代正确答案：A30下面不是证明贪心算法证明方法的有（）。的

7、 幽 交换论证 界正确答案：B31p类 问 题 可 以（）多项式时间计算指数时间计算 指数时间验证正确答案：A32下面描述错误的是（）有多项式时间算法的问题是易解问题NP c EXP如果X问 题 pY且Y不能多项式时间解决，那么X也不能多项式时间解决。如果问题X&Y且Y KpX,那么X三p.Y.正确答案：c33下面关于算法的说法错误的是（）。同一数学模型使用不同的数据结构会有不同的算法,有效性有很大差别。证明算法不正确，只需给出一个反例，算法不能正确处理即可。算法是一个语句集合，按照顺序执行语句，处理实例彳导到正确答案.同一算法只有一种形式描述。正确答案：D34最大独立集问题,如果在10亿次每

8、秒的计算机上运行，当 n=50时，需要计算的时间估计是?1小时 24小时1年 100年正确答案：D35如 果 怪 需)”则 f(n)=(g(n)oQ 3O正确答案：c36分块查找256个元素的数组，每块的最佳长度是8 16 32 64正确答案：C37此题重复Floyd算法的时间复杂度为0()*mn m+nlgn mlogn正确答案：D38o-i背包问题的枚举算法，如果在万亿次每秒的计算机上运行年可以计算的问题规模估计是？4060 3050正确答案：B39算法复杂度分析的两种基本方法为（）和（）.结构化方法面向对象方法 事后统计事前分析 几何复杂度平均复杂度 平摊复杂度平滑复杂度正确答案：B40

9、下面哪种函数不是回溯法中为避免无效搜索采取的策略 递归函数 剪枝函数 限界函数约束函数正确答案：A41使目标函数最大（小）的解是问题的（）最优解可行解正确答案：A42Iogl0=()(10)eo wo正确答案：A43对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（）。n!2An2A(n+l)-l 2A(n-l)正确答案：B44有点重复下面说法关于算法与问题的说法错误的是（）.如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。算法是一种计算方法，对问题的每个实例计算都能得到正确答案。同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。证明算

10、法不正确，需要证明对任意实例算法者坏能正确处理.正确答案：D45(6n+5)=()(n2-n)/2o0o正确答案：D46重复快速排序的时间复杂度是。（）。2 nlogn正确答案：c47回溯算法和分支限界法的问题的解空间树不会是()0有序树子集树 排列树 无序树正确答案：D48重复对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为()。n!c、2A(n-l)正 确 答 案：B49下面有关递归与迭代的说法错误的是（）递归与迭代都是解决 重复操作 的机制。递归算法的实现往往要比迭代算法耗费更多的时间.每个迭代算法原则上总可以转换成与它等价的递归算法。每个递归算法原则上总可以转换成与它等价

11、的迭代算法正 确 答 案：D50在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用）对输入进行预处理。蒙特卡罗算法拉斯维加斯算法舍伍德算法数值随机化算法正 确 答 案：C51动态规划和分治算法的共同点是（）最优子结构性质重叠子问题性质加速原理贪婪准则正 确 答 案：A52贪心算法基本要素有（）和最优子结构性质。分解合并,腿独立子问题性质贪心选择性质 叠子问题性质正确答案：c53下面哪种函数是回溯法中为避免无效搜索采取的策略（）递归函数剪枝函数 随机数函数搜索函数正确答案：B54在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。回溯法 分

12、支限界法 回溯法和分支限界法 回溯法求解子集树问题正确答 案：B55T(n)=2T(n/2)+M,T(l)=l,则 T(n)=()A(n3)O(nlogn)0(n)0(n2)正确答案：D56下面有关说法错误的是（）倒推法是从后向前推解问题的方法.有些问题采用倒推法，容易理解和解决。循环用于重复性的工作。循环体的特点是：以不变应万变”高阶递推方程需要使用换元迭代化简为一阶方程求解。正确答案：D57给定n个元素的数组A,使用折半查找比使用顺序查找快（）倍。A 500050000 500 10000正 确 答 案：B58下列算法中通常以自底向上的方式求解最优解的是（）。分治法动态规划法 贪心法 回溯

13、正 确 答 案：B59下面关于N P问题说法正确的是（）NP问题都是不可能解决的问题P类问题包含在NP类问题中NP完全问题是P类问题的子集NP类问题包含在P类问题中正 确 答 案：B60如果每条边的最大容量为1,则时间复杂度是。（n m ）的网络流算法有（）FF算法 容量缩放算法 EK算法 Dinic算法正 确 答 案：A61下面关于程序和算法的说法错误的是（）算法必须在有穷时间终止程序是算法用某种程序设计语言的具体实现 程序总是在有穷步的运算后终止 算法可以使用自然语言描述，但要保证无歧义正 确 答 案：C62重复把任意一个最优解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是（）领先

14、 反证 交换论证 界正 确 答 案：c63未来与过去无关指的是（）的性质 贪心选择 无后效性 最优子结构 重叠子问题正确答案：B64最大独立集问题,如果在10亿次每秒的计算机上运行,100年可以计算的图的规模估计是?10 50 100D 150正确答案：B65下列说法错误的是I f X PY an d Y PZ,th en X YlH正确答案：A73剪枝函数包括（）和约束函数。启发式函数限界函数估计函数 最优函数正 确 答 案：B74改进分治算法的方法有（）和改进划分的对称性。减少子问题数备忘录拟阵原理 加速原理正 确 答 案：A75待排序文件基本有序时，下面哪种排序方法，效率最差?堆排序快速

15、排序冒泡排序 归并排序正 确 答 案：B76原问题的最优解包含其子问题的最优解，这是（）性质A贪心选择无后效性 最优子结构 重叠子问题正 确 答 案：B77下面描述错误的是（）求解问题的输入量，称为问题的规模.时间复杂度是输入规模n的函数。时间复杂度衡量算法的效率，空间复杂度是算法执行所需所有空间的资源量。正 确 答 案：D78两 个n/2长度的有序数组合并为新的有序数组的时间为()A n:nlogn n n/2正 确 答 案：c79分治算法与动态规划算法的不同点是()递推关系子问题独立 最优子结构 小问题易求解正 确 答 案：B80回溯法和分支限界法的主要区别在于，回溯法求取（）.一个解 极

16、大解 极小解 T解或所有解正 确 答 案：D81下列算法中不能解决0/1背包问题的是（）贪心法动态规划 回溯法 分支限界法正确答案：A82S P F A算法的时间复杂度为。（）mn m+nlgn mlogn正确答案：A83下面关于贪心算法的说法错误的是0 贪心算法的思想是寻求局部最优解，逐步达到全局最优解贪心算法总能找到可行解，但未必是最优解。贪心算法的思想是依据贪婪准则作出决策，逐步构造解值。未来不影响过去指的是无后效性的性质0正确答案：D84下面不是动态规划算法的基本要素的是（）O无后效性独立子问题性质 最优子结构性质 重叠子问题性质正确答案：B85给 定n个元素，使用分块查找一般设分块的

17、长度()n/3 n/2正确答案：C86解决问题的基本步骤是()。(1)算法设计(2)算法实现(3)数学建模(4)算法分析(5)正确性证明 Q)(4)(5)(4)(1)(4)Q）正确答案：C87（）生成子集，便于实现集合的操作。增量构造法二进制法 位向量法 法向量法正确答案：B88对于稠密图，使 用（）算法计算MST更适合 Kruskal Prim正确答案：B89获得解不一定是正确解的算法是（）。蒙特卡罗算法 拉斯维加斯算法 舍伍德算法 数值随机算法正 确 答 案：A90下面不是以空间换时间的方法有（）预处理 预构造 动态规划数据压缩正确答案：D91A公司处理器速度是B 公司的1000倍。对于复

18、杂度为n3的算法,B公司的计算机可以在1小时内处理规模为n 的问题，A公司的计算机 在 1 小时能处理的问题规模是（1.0 分）0.0分n10n 100n1000l/2n正确答案：B92下面关于时间复杂度的描述错误的是()时间复杂度是最复杂部分的运行时间 时间复杂度是关键操作的运行时间 时间复杂度是在最坏情况下运行时间 时间复杂度是在平均情况下的运行时间正确答案：D93给定n个元素的数组A,n=10；使用折半查找比使用顺序查找大约快一倍。100 10 1000D、10 0 0：正确答案：A94下面有关递归与递推的说法错误的是()递归是逆向的，从大规模的问题逐步到小规模间题。递推是正向的，从小规

19、模的问题推解出大规模问题。递归表现为自己调用自己递推则没有这样的形式。一般来说,递归的效率高于递推正确答案：D95f(n)=Q(g(n),则 g(n)为 f(n)的()上界 下界 同阶D低阶正确答案：B96设 有5000个无序的元素，希望用最快的速度挑选出其中前500个最大的元素，最好选用（）法。冒泡排序 快速排序 堆排序 基数排序正确答案：C97实现二分搜索利用的算法是（）.分治策略动态规划法贪心法 回溯法正确答案：A98从资源划分，算法的复杂度分为（）和（）。时间复杂度空间复杂度空间复杂度平均复杂度 最好复杂度最坏复杂度 时间复杂度平均复杂度间间复杂度平均复杂度正确答案：A99算 法 与

20、程 序 的 区 别 是（）A输入输出确定性有穷性正确答案：D100FIF。是（）的搜索方式。A回溯分支限界动态规划贪心正确答案：B101分支限界法解o r背包问题时的解空间树是()。子集树排列树 深度优先生成树 广度优先生成树正确答案：A102下面关于贪心算法错误的是()贪心算法总能找到可行解，并且是最优解。问题的最优子结构性质是该问题可用贪心或动态规划算法求解的关键特征。贪心算法T 殳预处理后再进彳谩优化选择。贪心选择中每一步的局部最优解都构成全局最优解的一部分正确答案：A103重复肯定获得可行解，但不一定是正确解的算法是（）。蒙特卡罗算法 拉斯维加斯算法舍伍德算法 舍伍德算法 数值随机算法

21、正 确 答 案：A104备忘录与动态规划算法的不同点是（）递推关系 自顶向下计算 子问题重叠最优子结构正 确 答 案：B105备忘录方法使用（）的递归方式。自顶向下自高到低自低到高 自底向上正确答 案：A106时 间 复 杂 度 为0（n”m）的 网 络 流 算 法 是（）一般预流推进算法先进先出预流推进算法最高标号预流推进算法最短增广路算法正确答案：C:107f(n)=100 n为奇数f(n)=5r?+3n n 为偶数则f(n)的下界为 n 2n 1正确答案：D108下面不是动态规划的基本方法有().多重选择 增加变量舍入 区间变量正确答案：C109装载问题的回溯算法所需的计算时间为（）A

22、2nlogn n2n正确答案：A110动态规划算法的基本要素有（）和最优子结构性质。分解合并崛独立子问题性质 贪心选择性质 重叠子问题性质正确答案：D111类似分块查找256个元素的数组，分成()块最好?816 32 64正确答案：B112以下不可以使用分治法求解的是()。线性选择问题归并排序 0/1背包问题 棋盘覆盖问题正确答案：c113对近似递增序列的线性表从小到大排序，使用哪种方法好？堆排序.快速排序.插入排序 归并排序正确答案：C114分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者()。求解目标不同，搜索方式相同 求解目标不同片叟索方式也不同 求解目标相同才叟索方式不同

23、求解目标相同方叟索方式也相同正确答案：B115I质序直找长度为n的线性表，平均查找长度为()n n/2(n+l)/2(n-l)/2正确答案：C116()是贪心算法与动态规划算法的共同点 重叠子问题 构造最优解 贪心选择性质 最优子结构性质正确答案：D117下 面 程 序 的 时 间 复 杂 度 为()X =1for i=l to n dofor j=l to i dofor k=l to j dox+0(n)B、0(n3)0 (n )O(n l o g n)正 确 答 案：B118插入排序的时间复杂度是（）。O（n）0(2n)0(n2)O(nlogn)正 确 答 案：C119重复算法复杂度分析

24、的两种方法是（）事前分析和事后统计最坏情况的复杂度和最好情况的复杂度 最坏情况的复杂度和平均复杂度 最好情况的复杂度和平均复杂度正 确 答 案：A120待排序文件基本有序时，下面哪种排序方法，效率最高?堆排序快速排序 冒泡排序 归并排序正 确 答 案：c121下面程序的时间复杂度为（）i=lwhile(iCg (N),则称函数f(N)当N充分大时有下界g (N),记作f(N)=Q (g(N),即 f(N)的 阶()g (N)的阶。不高于 不低于 等价于 逼近正确答案：B127优先队列式分支限界法选取扩展结点的原则是()先进先出 后进先出 结点的优先级随机正 确 答 案：c128可能获得解，且一

25、定是准确解的算法是()。蒙特卡罗算法 拉斯维加斯算法 舍伍德算法 数值随机算法正 确 答 案：B129从 长 度 为n的数组中多次查找数据，使 用()方法好。顺序查找随机查找 排序后折半查找无序查找正确答 案：C130下面不是动态规划算法特点的是（）自底向上计算无后效性 子问题独立 子问题重叠正确答案：c131求解高阶递推方程一般使用o迭代方法 差消迭代 换元迭代 直接迭代正确答案：A132假设算法A 的计算时间为T(n)=2An,在计算机A 上输入规模为n 时算法A 的运行时间为t 秒。计算机B的运行速度是A 的 64倍 在 t 秒时间计算机B运行算法A 的输入规模是().n+6 64n 6

26、n.2cn正确答案：A133以下是NP完全问题的()0-1背包顶点覆盖 最短路最大公因子正确答案：A134NP类问题可以().多项式时间计算指数时间验证 多项式时间验证 指数时间计算正确答案：C135主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方程，则下列关于方程中的约束中不准确的是？对于系数a,必须满足a=l对于系数b,必须满足bl 若对于常数 e0,f(n)=O(n V r),则 T(n)=(r?V)若 f(n)=0,则 T (n)=e(n bg bal o q n)正 确 答 案：D136一个问题可用动态规划算法或贪心算法求解的关键特征是问题的()。重叠子问题 最优子结

27、构性质 贪心选择性质 定义最优解正 确 答 案：B二、多 选 题(题 数：7 5,考试抽取5 道，分值10分)1通过降低子问题合并时间，降低分治算法时间复杂度的有()大整数乘法计数逆序 线性时间选择 最接近点对正 确 答 案：BD2子集生成方法有（）增量构造法二进制法 位向量法 法向量法正 确 答 案：ABC3下面时间复杂度的描述正确的是（）logn!=0（nlogn）log n _ ,J o ga b n 折半查找的时间复杂度为B(nbgn)从 n 个数中查找最小值的时间复杂度为O(n)正 确 答 案：ABD我 的 答 案：4求 解 递 推 方 程 的 迭 代 法 分 为()直接迭代差消迭代

28、 换元迭代 主定理正 确 答 案：ABC5贪心算法的基本要素是()贪心选择的性质无后效性性质 最优子结构性质 独立子问题的性质正确答案：ABC6给定网络N=(V,E)的一个流f,f需满足的条件是对于每条边 e e E:O W f(e)W c(e),c(e)为边 e 的容量 B、对于每个顶点v e V -s,t:净流量=0 源点s的流出量=|f|汇点t的流入量=lfl正确答案：ABCD7递归函数的要素是（）边界条件 递归方程 输入 迭代正确答案：AB8p类问题可以（）。多项式时间计算指数时间计算 指数时间验证多项式时间验证正确答案：AD9下面属于NP完全问题的是()SAT最大独立集 最小顶点覆盖

29、 旅行商问题正确答案：ABCD10关于带需求的流通下面说法正确的是()。f(e)为边e的流量,c(e)为边e的容量。对于任意边e e E:0f(e)c(e)对任意顶点v-s,t,顶点的净流量=0供给和=需求和对于任意边 e G E：(e)f(e)0,l o g n =o(E)l o g an =0(l o g b n)常数 a,b 0.对任意 r 1 和 d 0,nd=正确答案：ABC12下面那些算法的时间复杂度为0(n2)顺序查找 折半查找.插入排序 冒泡排序 折半插入排序正确答 案：CDE13回溯法的效率依赖于下列哪些因素()满足显约束的值的个数计算约束函数的时间计算限界函数的时间 确定解

30、空间的时间正 确 答 案：ABC14最短路算法中适用于负权图的是（）Floyd算法SPFA算法Bellman 算法 Dijkstra 算法正 确 答 案：ABC15动态规划算法的特点（）自底向上计算自顶向下计算子问题独立 子问题重叠正 确 答 案：AD16区间动态规划的计算次序是（）先小区间后大区间先大区间后小区间 自底向上 自顶向下正 确 答 案：AC17问题变换的方法有（）.实例简单化问题约简 左达变换 分支正确答案：ABC18下列哪个结点属于回溯法的结点类型？（）扩展结点活结点 根结点 死结点正确答案：ABD19T(n)=T(n-l)+n,T(l)=l,贝 U T(n)=()e(2n(n

31、+l)/2 0(n2)Q(n2)正 确 答 案：ABCD20最好情况下,时间复杂度为O(n)的排序算法有()冒泡排序 计数排序 插入排序 直接选择排序正 确 答 案：ABC21改进分治算法的方法有()减少问题的规模改进分治的均衡度 减少合并的时间 减少子问题的个数正确答案：BCD22从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，最常见的方式有（）.队列式分支限界法优先队列式分支限界法 栈式分支限界法 FIFO分支限界法正确答案：ABD23下面说法正确的是（）使用眼界函数作优先级,第一个加入队列的叶子就是最优解 用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最

32、优解的子树。回溯和分支眼界都是动态生成解空间树正确答案：BCD24以下关于判定问题难易处理的叙述中错误的是（）。可以由多项式时间算法求解的问题是难处理的 需要超过多项式时间算法求解的问题是易处理的 可以由多项式时间算法求解的问题是易处理的需要超过多项式时间算法求解的问题是不能处理的正确答案：ABD25最小生成树问题可以使用的算法有（）Kruskal Prim Solim Dijkstra正确答案：ABC26分治算法与动态规划算法的相同点是（）递推关系子问题独立 子问题重叠最优子结构正确答案：AD27N 后问题利用（）减少搜索。对称性约束函数 重排原理 加速原理正确答案：ABC28备忘录算法的特

33、点（）自底向上计算 自顶向下计算 从大到小计算从小到大计算正确答案：BC29下列算法中能解决0/1背包问题的是（）贪心法动态规划 回溯法 分支限界法正确答案：BCD30下面分治算法的说法正确的是（）处理随机排列的数组时，合并排序比快速排序快。三分法的判定树是三叉树最小堆中每个元素调整的次数不超过树高e（logn）.二分法子问题不独立的情况可以使用分治算法计算，但计算量大正确答案：BCD31最 大 独 立 集 问 题 和（）问题等价。A、最大团.最小顶点覆盖 区间调度问题.稳定匹配问题正确答案：AB32下面关于NP问题说法错误的是（）NP问题都是不可能解决的问题P类问题包含在NP类问题中NP完全

34、问题是P类问题的子集 NP类问题包含在P类问题中正 确 答 案：ACD33通过减少子问题个数，降低分治算法时间复杂度的有（）A大整数乘法Strassen矩阵乘法 线性时间选择 最接近点对正确答 案：AB34回溯算法的效率在很大程度上依赖的因素有（）产生xk的时间。满足显约束的Xk值的个数。计算可行性约束函数constraint和上界函数bound的时间.满足可行性约束函数和上界函数的所有xk的个数。正确答案：ABCD35给定两张喜欢列表，稳 定 匹 配 问 题 的 输 出 是（）。完美匹配没有不稳定配对 最大兀配 稳定匹配正确答 案：ABCD36分数拆分问题的枚举算法通过（）方法进行了优化。减

35、少枚举变量减少枚举变量的值域 优化数据结构 优化数学模型正 确 答 案：ABD37时 间 复 杂 度 为O(nlogn)的排序算法有()堆排序 快速排序 合并排序 计数排序正 确 答 案：AC38贪心算法的常用证明方法有()。领先反证 界 交换论证正确答案：ABCD39改 进 FF网络流算法，可以通过选择（）增广路，降低时间复杂度。最大容量 最短路径 最大瓶颈容量 边数最少正确答案：ABCD40区间问题包含()区间调度区间划分区间选点区间覆盖正确答案：ABCD41递归变为非递归的方法有()A模拟栈递推尾递归循环正确答案：ABC42回溯法解题步骤：针对所给问题，定义问题的解空间确定易于搜索的解空

36、间结构 确定最优子结构的性质 以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索正确答案：ABD我的答案：43分治算法的适用条件有（）问题可以分解为规模较小的子问题小规模子问题可解 子问题可合并为问题的解子问题相互独立正 确 答 案：ABCD44从资源划分算法的复杂度分为（）.时间复杂度空间复杂度平均复杂度平摊复杂度正 确 答 案：AB45提高事后统计方法准确度的有（）重复测试加大n典型实例测试。优化算法正确答案：ABC46下面关于程序和算法的说法正确的是（）。算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。程序是算法用某种程序设计语言的具体实现。程序总是在有穷步的运算后终

37、止。算法是一个过程，计算机每次求解是针对问题的一个实例求解。正确答案：ABD47递归一般用于解决问题有（）：数据的定义是按递归定义的.问题解法按递归实现。（回溯）数据的结构形式是按递归定义的。迭代问题正 确 答 案：ABC48备忘录与递归算法的相同点是（）递推关系自顶向下计算 从大到小计算 子问题重叠正 确 答 案：AD49备忘录算法的特点（）自底向上计算 自顶向下计算子问题独立子问题重叠正确答 案：BD50分治法在每一层递归上有三个步骤（）分解 解决 合并 选择正确答 案：ABC51最短路算法中适用于稀疏图的是（）Floyd算法SPFA算法Bellman 算法 Dijkstra 算法正 确

38、答 案：BCD52对 于NP完全问题,可采取的解题策略有()。用启日方法求解分支限界法求解小实例 用随机算法求解 只求近似解正 确 答 案：ABCD53()肯定获得最优解。分支眼界贪心算法 随机算法 动态规划算法正 确 答 案：AD54问 题 的 状 态 生 成 法 有（）子集树生成法深度优先生成法 宽度优先生成法 排列树生成法正 确 答 案：BC55（）肯定获得最优解。回溯算法贪心算法随机算法枚举算法正 确 答 案：AD56属于最短路增广路算法的有（）FF算法EK算法Dinic算法ISAP算法正 确 答 案：BCD57下 面 说 法 正 确 的 是（）现实计算机上无法产生真正的随机数求解同一

39、实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。正 确 答 案：ABCD58重复枚举算法的优化方法有（）减少枚举变量 减少枚举变量的值域 优化数据结构 优化数学模型正 确 答 案：ABCD59动态规划算法的特点()自底向上计算 自顶向下计算 从大到小计算 从小到大计算正确答 案：AD60给定二分图G=V,E巾无孤立点，|v|=n,其最大流算法求得最大流f,则G的()=n-f.最大独立数 最大匹配数 最小顶点覆盖最小边覆盖正 确 答 案：AD61问题变换

40、的目的和方式有（）。复杂变简单 未知变已知 难解变易解 隐式变显式正 确 答 案：ABCD62复杂度比较方法有（）对数积分 极限D放大正确答案：ABCD63类似给定二分图G=中无孤立点,|V|=n，其最大流算法求得最大流f,则G的()=f.最大独立数最大匹配数 最小顶点覆盖 最小边覆盖正确答案：BC64重复分治法在每一层递归上有三个步骤()分解 解决 合并D选择正确答案：ABC65顺序查找适合的数据结构是（）A散列存储顺序存储 链式存储 压缩存储正确答案：BC66下面说法正确的是（）随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法.当最坏和平均情况差别较大时,舍

41、伍德算法可以消除好坏实例的差别，达到平均实例的性能.线性同余法是产生伪随机数的最常用的方法 增加蒙特卡罗算法的求解次数,可使求解错误的概率任意小。正确答案：ABCD67下面分治算法的说法正确的是()分治法的设计思想是大事化小，各个击破，分而治之。每次都将问题分解为原问题规模的一半进行求解，称为二分法.分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。减治法是把一个问题转化成一个子问题来解决。正确答案：ABD68下面时间复杂度的描述正确的是()logn!=0(nlogn)aA(logn)=nA(loga)折半查找的时间复杂度为e（nlogn）从 n 个数中查找最小值的时间复杂度为0

42、（n）正确答案：ABD69分支限界法与回溯法的不同点是什么？求解目标不同 搜索方式不同 对扩展结点的扩展方式不同 存储空间的要求不同正确答案：ABCD70用分支限界法设计算法的步骤是：针对所给问题，定义问题的解空间（对解进行编码）；确定易于搜索的解空间结构（按树或图组织解）；定义最优子结构 以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索.正 确 答 案：ABD71算法的性质有（）输入输出 确定性 有穷性正 确 答 案：ABCD72求解递推方程的方法有（）迭代法递归树 归纳法 主定理正 确 答 案：ABCD73类似动态规划算法的基本要素有（）。贪心选

43、择性质 最优子结构性质 无后效性 重叠子问题性质正 确 答 案：BCD74下面说法正确的是()多源点和多汇点的网络流问题可以通过增加一个“超源点 和 超汇点”转化为单源点和单汇点的网络流问题无向图的每条边变为方向相反的两条边，容量是原边的容量，这样无向图的最大流问题变换为有向图的最大流问题。剩余网络中从源S到汇t的最小费用路是剩余网络中从S到t的以费用为权的最短路.最小费用最大流算法寻找从源点S到汇点t的最小费用路，然后沿最小费用路增流，直至找到最小费用工Z J IL o正确答案：ABCD75类似时间复杂度为。(门 人 2)的排序算法有()冒泡排序 快速排序 插入排序 直接选择排序正确答案：A

44、BCD三、填 空 题（题数：64,考试无填空，可作为选择判断的补充）1回答是与否的问题是_问题。正确答案第一空：判定2A公司处理器速度是B公司的100倍。对于复杂度为n：的算法，B公司的计算机可以在1时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是_ _ _ _ _ _ _ _正确答案第一空：10n3构造一个解使目标函数最大或最小的问题是问题。正确答案第一空：优化4使用回溯法进行状态空间树裁剪分支时一般有两个标准：可行性约束函数和限界函数，装载问题和旅行商问题正好是两种不同的类型，其中同时使用可行性约束函数和限界函数的进行裁剪的是 ,只 使 用 限 界 函 数 进 行 裁 剪

45、的 是 。正确答案第一空：装载问题第二空：旅行商问题5分析下列方程的上界0(_)和下界w(_).T(n)=T(n-l)+1,T(l)=l正确答案第一空：n第二空：n6分析下列程序的上界0(_)和下界Q(_).P=1for i=l to nA2 dofor j=l to i doP=P+i正确答案第一空：nA4第二空：nA47分析下列方程的时间复杂度为。(_).T(n)=4T 5/2)+n,T(l)=l正确答案第一空：nA2第二空：nA28按照霍纳法则，计算p(x)=axn+an-.x-+a,x+a。的数量级为一。正确答案第一空：n9背包问题，背包容量C=20,物品价值p,=4,8,15,1,6

46、,3,物品重量必=5,3,2,10,4,8.如果是部分背包问题，求装入背包的最大价值和相应装入物品。该问题最好使用(一)算法求解.装入背包的最大价值是(),对应的完整物品的编 号 是(_ _ _ _)、(_ _ _ _)、(_ _ _ _)、(_)O如果物品数为n,算法的时间复杂度为0()正确答案第一空：贪心第二空：35.25第三空：1第四空：2第五空：3第六空：5第七空：nlogn10给定一个数字三角形，从顶至底有多条路径,每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分。最小路径得 分 为(_),相应路径(从顶到底)对应的数字为(_)_)(_),(_)，(_)。73 88

47、 4 02 7 4 44 5 2 6 5正确答案第一空：20第二空：7第三空：3第四空：4第五空：4第六空：211回溯法搜索解空间树时，常 用 的 两 种 剪 枝 函 数 为、正确答案第一空：约束函数第二空：限界函数我的答案：12多选式时间可验证问题是问题。正确答案第一空：NP13矩 阵 c 中每一行选一个元素，使选择的元素不同列,并且元素之和最小。(_J o b 1 J o b 2J o b 3J o bP e r s o n a9568P e r s o n b6437P e r s o n c5818P e r s o n d7694问题的解空间是（一）树。最小元素和（_。，对应的安排是

48、a安排j o b（_ _ _ _ _）、b安排j o b(_)、C安排j o b(_）、d安 排 如 果 人 数 和 任 务 数 为n,时间复杂度是正确答案第一空：排列第二空：16第三空：2第四空：1第五空：3第六空：4第七空：n!14传教士和野人问题转换的图是。正确答案第一空：状态空间图15插入排序最好情况下的时间复杂度为0(_)，最坏情况下的复杂度为0(一 )正确答案第一空：n 第二空：n216某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示,s(i)表示开始租用时刻,f(i)表示结束租用时刻,10个客户的申请如下表所示.同一时刻，该羽毛

49、球场只能租借给T 立客户，请设计一个租用安排方案，在 这 10位客户里面,使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。i12345678910s(i)03153511886f(i)65498713121110(1)该问题可以使用(_)算法求解？(2)该问题在计算前，按照(_)从小到大排序进行预处理。(3)最多安排的客户编号顺序为(_)、(_)、(_)、(_).正确答案第一空：贪心第二空：f(i)第三空：3第四空：6第五空：9第六空：717有4种不同面值的硬币(每种无限多)。面值分别为Vl=3,V2=5,V3=7,V4=14O给定S=100,可

50、以选用多少个硬币，使得面值之和，恰好为S?输出硬币数目的最小值及组合。该问题最好使用(_)算法求解？输出硬币数目的最小值是(_).输出硬币数目的最小值的组合是第1种(_)枚、第2种(_)枚、，第3种(_)枚、第4种(_ _)枚.正确答案第一空：动态规划第二空：10第三空：2第四空：2第五空：0第六空：618任务安排问题:某公司有5个工作岗位,每个岗位需要1个人,现接到5位待业者申请。A申请岗位1、2、3,B申请1、4,C和D申请4、5,E申请5.最多一人就业，相应安排是:A安 排 岗 位 一 或 一B安排岗位。如 果n个 人m个岗位，最好使用算法。正确答案第一空：4第二空：2第三空：3第四空：