算法设计分析重庆大学练习题库及答案.docx

1、算法设计分析重庆大学练习题库及答案1、算法分析中，记号O表示（ ） A、渐进上界 B、非紧上界 C、非紧下界 D、非紧下界正确答案是A2、 在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是 （ ）。 A、总是选择面值最高的硬币 B、总是选择不超过剩余应找钱数的最大面值的硬币 C、总是选择面值是10，5的倍数的硬币 D、总是选择面值最小的硬币正确答案是B3、 由边界条件出发,通过递推式求f(n)的值,从边界到求解的全过程十分清楚的是（ ） A、贪心 B、递推 C、递归 D、概率正确答案是B4、考虑最长公共子序列问题的下述递归表达式，如果全部子问题组织在一个ci,j的二维表格中，则ci,

2、j不依赖于下述哪个子问题 ：（ ）。 A、同一行的上一列 B、同一列的上一行 C、上一行的上一列 D、同一行的下一列正确答案是D5、 算法的时间复杂度是指（） A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数正确答案是C6、 活动选择问题就是在所给的活动集合中，选出（ ）的相容活动子集。 A、当前可选活动中结束时间最早的活动 B、当前可选活动中开始时间最早的活动 C、当前可选活动中冲突数量最少的活动 D、当前可选活动中持续时间最长的活动正确答案是A7、一个长度为n英寸的钢管的最优切割问题，总共有( )个不同的子问题。 A、n+1

3、 B、n2 C、nlogn D、logn正确答案是A8、 最优二叉搜索树的时间复杂度为（ ）。 A、O(n) B、O(n!) C、O(n2) D、O(nlogn)正确答案是D9、 算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是（ ） A、5/0 B、将6或7与x相加 C、未赋值变量参与运算 D、f(n)=f(n-1)+2,f(1)=10,n为自然数正确答案是D10、 对于三个物体的背包问题，问题相关的数据为n=3, M=20,P=(25,24,15),W(18,15,10)。 下面给出的四个可行解中，最好的是（ ） A、(1/2，1/3，1/4) B、(1，2/15

4、，0) C、(0，2/3，1) D、(0，1，1/2)正确答案是D11、 递归函数f(n)=f(n-1)+n(n1)的递归出口是( )。 A、f(0)=0 B、f(1)=1 C、f(0)=1 D、f(n)=n正确答案是B12、下面关于快速排序的说法，正确的是（ ） A、快速排序的速度和数据无关，是一个固定的值 B、快速排序的速度在分解的均匀的时候效果最好，速度最快 C、快速排序主要的时间花在合并上面 D、快速排序在分解均匀的适合速度最慢正确答案是B13、 下面关于货郎担问题的描述，正确的是（ ） A、货郎担问题是求取具有最大成本的周游路线问题 B、货郎担问题适合使用贪心算法求问题的最优解 C、

5、货郎担问题存在多项式时间算法 D、货郎担问题可以通过动态规划算法实现正确答案是D14、 实现快速排序算法如下： QuickSort (A, p, r)IF p Max MaxAi;else if AiMin MinAi;return Max,Min其时间复杂度是（ ）。 A、2n B、2(n-1) C、3n D、3(n-1)正确答案是B31、 快速排序法的基本思想是对输入的数组按以下三个步骤进行排序（ ）。 A、分解，合并，递归求解 B、合并，递归求解，分解 C、递归求解，分解，合并 D、分解，递归求解, 合并正确答案是D32、 合并排序法的基本思想是：将待排序元素分成大小大致相同的（ ）个子

6、集合，分别对每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 A、4 B、3 C、2 D、5正确答案是C33、 在最优二叉搜索树问题中，我们的优化目标是（ ）。 A、只经过最少次数的比较就可以找到概率最大的元素 B、经过最多次数的比较就可以找到概率最小的元素 C、找到每个元素所需要的平均比较次数为最小 D、元素搜索代价的数学期望为最小正确答案是D34、 下面是贪心算法的基本要素的是（ ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解正确答案是C35、 分治法所能解决的问题应具有的关键特征是（ ）。 A、该问题的规模缩小到一定的程度就可以容易地解决 B

7、、该问题可以分解为若干个规模较小的相同问题 C、利用该问题分解出的子问题的解可以合并为该问题的解 D、该问题所分解出的各个子问题是相互独立的正确答案是C36、 T(n)=2n3+10n2log(n)+30n的渐近时间复杂度为（ ）。 A、O(n2log(n) B、O(n4) C、O(n3)正确答案是C37、 在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的最大收益，且已知rn所代表的最优解里，第一刀切下了3英寸，则下述公式正确的是（ ）。 A、rn = p3 + rn-3 B、rn = rn 3 C、rn = rn-3 + 3 D、rn = r3 + p3正确答案是A3

8、8、 （ ）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质正确答案是D39、下列关于选择排序和冒泡排序的稳定性的说法，正确的是（ ）。 A、选择排序是稳定的，冒泡排序是稳定的。 B、选择排序是不稳定的，冒泡排序是不稳定的。 C、选择排序是稳定的，冒泡排序是不稳定的。 D、选择排序是稳定的，冒泡排序是不稳定的。正确答案是B40、 Edmonds-Karp算法中寻找增广路径的方法是（ ）。 A、深度优先算法 B、广度优先算法 C、Prim算法 D、Dijkstra算法正确答案是B41、使用分治法求解不需要满足的条件是（ ）。 A、子问题必须

9、是一样的 B、子问题不能够重复 C、子问题的解可以合并 D、原问题和子问题使用相同的方法解正确答案是A42、 在流网络中，对于源节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 A、在流网络中，对于任何节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 B、在流网络中，对于汇节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 C、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 D、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。正确答案是C43、 在矩阵连乘问题的动态规划

10、解决方案里，我们的所做的顶层决策是（ ）。 A、第一次矩阵乘法发生的位置 B、最后一次矩阵乘法发生的位置 C、结果矩阵维数最小的位置 D、结果矩阵列数最小的位置正确答案是B44、 关于0-1背包问题的下述形式化公式描述：下述说法不正确的是（ ）。 A、i 表示物品的重量 B、C表示背包容量 C、xi=0表示编号为i的物品不被选择 D、求解目标是最大化装入背包内的物品的总价值正确答案是A45、 在活动安排问题中，如果把全部活动按照结束时间递增序排序后，按贪心算法，我们总是安排 （ ）。 A、当前可选活动中结束时间最早的活动 B、当前可选活动中开始时间最早的活动 C、当前可选活动中冲突数量最少的活

11、动 D、当前可选活动中持续时间最长的活动正确答案是A46、找零钱问题中，定义 Cj为兑换j 所需要的硬币的最少数量，考虑下述递归表达式，下列关于对i的寻优的最恰当描述是（ ）。 A、考虑找出的第一个硬币面值的各种可能性 B、考虑先找给客户几分钱 C、考虑最多可以用几个硬币 D、考虑最少可以用几个硬币正确答案是A47、 Huffman编码问题中，我们的优化目标是（ ）。 A、所有字符编码长度的数学期望为最小 B、给频度高的字符以最短的编码 C、给频度最低的字符以最长的编码 D、给每个字符相同长度的编码正确答案是A48、 一个有n个结点的带权无向图，其生成树应有（ ）条边。 A、n B、n-1 C

12、、nlogn D、n/2正确答案是B49、 算法必须具备输入、输出和（ ）等5个特性。 A、可执行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性正确答案是B50、 当问题的规模n趋向无穷大时，（ ）的数量级(阶)称为算法的渐进时间复杂度。 A、时间复杂度 B、空间复杂度 C、冗余度 D、迭代次数正确答案是A51、 对于n个元素的排序问题，n2时,只要作（ ）次比较即可排好序。 A、3 B、2 C、1 D、4正确答案是C52、 递归算法不能适用以下场合（ ）。 A、数据的定义形式按递归定义 B、数据之间的关系(即数据结构)按递归定义 C

13、、问题解法按递归算法实现 D、概率问题正确答案是D53、 在最优二叉搜索树问题中，定义ei, j 为 ki,.,kj的最优二叉查找树的期望搜索成本，而我们需要通过寻优来确定最优二叉查找树的根结点的下标r,则r的取值范围为（ ）。 A、irj B、 irj C、irj D、ian/2 D、x=an/2正确答案是A56、 下列算法中通常以自底向上的方式求解最优解的是（ ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法正确答案是B57、备忘录方法的递归方式是 （ ） A、自顶向下 B、自右向左 C、忽上忽下 D、自底向上正确答案是A58、 算法指的是（ ）。 A、计算方法 B、排序方法 C

14、、解决问题的方法和过程 D、调度方法正确答案是C59、应用Johnson法则的流水作业调度采用的算法是（ ） A、贪心算法 B、分治法 C、动态规划算法 D、动态规划算法正确答案是D60、 贪心算法与动态规划算法的主要区别是（ ）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解正确答案是B61、对于矩阵链连乘的子问题mi,j，当i=j时表明该矩阵链有两个矩阵。（ ） 正确 错误正确答案是错误62、算法就是一组无穷的规则( ) 正确 错误正确答案是错误63、问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。( ) 正确 错误正确答案是正确64、动态规划和分治法在

15、分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的( )。 正确 错误正确答案是正确65、每一个递归定义都有其边界条件。( ) 正确 错误正确答案是正确66、 贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。( ) 正确 错误正确答案是正确67、用浮点数来表示大型整数，只能近似地表示它的大小( ) 正确 错误正确答案是正确68、多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。( ) 正确 错误正确答案是正确69、 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。(

16、) 正确 错误正确答案是正确70、裴波那契数列的定义：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其数据的定义形式不是按递归定义。( ) 正确 错误正确答案是错误71、程序性能是指运行一个程序所需的内存大小和时间多少。( ) 正确 错误正确答案是正确72、一个操作所需的时间和操作数的类型无关( ) 正确 错误正确答案是错误73、 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。( ) 正确 错误正确答案是正确74、 在JAVA语言中,执行特定认为的任务的函数或过程统称为方法。( ) 正确 错误正确答案是正确75、与分治法不同的是，适合于用动态规划求解的

17、问题经分解得到子问题往往是互相不独立的( )。 正确 错误正确答案是正确76、归并排序是指将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 （ ） 正确 错误正确答案是正确77、与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相独立的( )。 正确 错误正确答案是错误78、对所有问题,贪心算法不能都得到整体最优解 ( )。 正确 错误正确答案是正确79、算法重要特性是确定性、可实现性、输入、输出、有穷性( )。 正确 错误正确答案是正确80、 0-1背包问题，无论物件的顺序如

18、何排列，动态规划总能获得最优解。( ) 正确 错误正确答案是正确81、指数时间算法只有在n取值非常小时才实用。( ) 正确 错误正确答案是正确82、 动态规划法其具体形式是多种多样的，但都具有相同的填表格式。（ ） 正确 错误正确答案是正确83、 一般来说，对一个有序序列二分法(即把任意大小的问题尽可能地等分为两个子问题)较为有效。( ) 正确 错误正确答案是正确84、 如果各子问题是不独立的，一般用动态规划法比分治法较差。( ) 正确 错误正确答案是错误85、动态规划对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。( ) 正确 错误正确答案是正确86、 当一个问题具有最

19、优子结构性质时只能用动态规划方法求解。( ) 正确 错误正确答案是错误87、Huffmann编码树所对应的编码并不一定是前缀码。（ ） 正确 错误正确答案是错误88、 通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理。( ) 正确 错误正确答案是正确89、 问题的计算复杂性一般是随着问题规模的增加而减小。( ) 正确 错误正确答案是错误90、 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。( ) 正确 错误正确答案是正确91、Prim算法是一种动态规划算法。（ ） 正确 错误正确答案是错误92、 标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。( ) 正确 错误正确答案是正确93、 问题解法按递归算法实现的问题适用于递归求解。( ) 正确 错误正确答案是正确94、一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。( ) 正确 错误正确答案是正确95、 如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。（ ） 正确 错误正确答案是正确96、对于矩阵链连乘的子问题mi,j，其对应的si,j用于记录该矩阵链最后一次乘法发生的位置。（ ） 正确 错误