算法设计分析重庆大学练习题库及答案Word下载.docx
《算法设计分析重庆大学练习题库及答案Word下载.docx》由会员分享，可在线阅读，更多相关《算法设计分析重庆大学练习题库及答案Word下载.docx（54页珍藏版）》请在冰点文库上搜索。
6、活动选择问题就是在所给的活动集合中，选出（
）的相容活动子集。
∙A、当前可选活动中结束时间最早的活动
∙B、当前可选活动中开始时间最早的活动
∙C、当前可选活动中冲突数量最少的活动
∙D、当前可选活动中持续时间最长的活动
7、
一个长度为n英寸的钢管的最优切割问题，总共有（）个不同的子问题。
∙A、n+1
∙B、n2
∙C、nlogn
∙D、logn
8、最优二叉搜索树的时间复杂度为（）。
∙A、O（n）
∙B、O（n!
）
∙C、O（n2）
∙D、O（nlogn）
9、算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是（
）
∙A、5/0
∙B、将6或7与x相加
∙C、未赋值变量参与运算
∙D、f（n）=f（n-1）+2,f
（1）=10,n为自然数
10、对于三个物体的背包问题，问题相关的数据为n=3,M=20,P=（25,24,15）,W（18,15,10）。
下面给出的四个可行解中，最好的是（）
∙A、（1/2，1/3，1/4）
∙B、（1，2/15，0）
∙C、（0，2/3，1）
∙D、（0，1，1/2）
11、递归函数f（n）=f（n-1）+n（n>
1）的递归出口是（）。
∙A、f（0）=0
∙B、f
（1）=1
∙C、f（0）=1
∙D、f（n）=n
12、
下面关于快速排序的说法，正确的是（）
快速排序的速度和数据无关，是一个固定的值
快速排序的速度在分解的均匀的时候效果最好，速度最快
快速排序主要的时间花在合并上面
快速排序在分解均匀的适合速度最慢
13、下面关于货郎担问题的描述，正确的是（）
∙A、货郎担问题是求取具有最大成本的周游路线问题
∙B、货郎担问题适合使用贪心算法求问题的最优解
∙C、货郎担问题存在多项式时间算法
∙D、货郎担问题可以通过动态规划算法实现
14、实现快速排序算法如下：
QuickSort（A,p,r）
IFp<
rTHEN
q←Partition（A,p,r）
（）
QuickSort（A,q+1,r）
∙A、QuickSort（A,q-1,r）
∙B、QuickSort（A,q-1,r）
∙C、QuickSort（A,q+1,r）
∙D、QuickSort（A,q-2,r）
15、找零钱问题中，定义C[j]为兑换j所需要的硬币的最少数量，如果找出的第一个硬币为5分，则下述公式哪个是对的（
∙A、C[j]=1+C[j-5]
∙B、C[j]=5+C[j-1]
∙C、C[j]=5+C[j-5]
∙D、C[j]=1+C[j-1]
16、
在最优二叉搜索树问题中，定义e[i,j]为
ki,...,kj的最优二叉查找树的期望搜索成本，而我们确定根结点下标为r,则其左子树的下标范围是（
∙A、i..r
∙B、i..r-1
∙C、i..r+1
∙D、i+1..r
17、衡量一个算法好坏的标准是（）。
∙A、运行速度快
∙B、占用空间少
∙C、时间复杂度低
∙D、代码短
18、最长公共子序列算法利用的算法是（
∙A、分支界限法
∙B、动态规划法
∙C、贪心法
∙D、回溯法
19、Huffman编码的贪心算法所需的计算时间为（
∙A、O（n2）
∙B、O（nlogn）
∙C、O（2n）
∙D、O（n）
20、使用分治法求解不需要满足的条件是（
子问题必须是一样的
∙B、子问题不能够重复
∙C、子问题的解可以合并
∙D、原问题和子问题使用相同的方法解
21、在最长公共子序列问题中，如果定义c[i,j]为X1..Xi和Y1..Yj的最长公共子序列的长度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（）。
∙A、c[0,0]
∙B、c[1,1]
∙C、c[1,m]
∙D、c[m,n]
22、以下关于贪心算法，不正确的说法是（
∙A、用于解决优化问题
∙B、总是选择在当前看来最好的选择
∙C、期望通过局部最优达到全局最优
∙D、所需求解的问题可以不满足最优子结构性质
23、
下列关于算法速度的描述，正确的是（）
一般来说，测试算法速度的方法就是在计算机上运行，执行快的说明算法就快；
多项式时间算法在任何情况下都要比指数时间算法快
可以使用空间复杂度来描述算法的速度
对于问题规模比较大的时候，对数时间算法比指数时间算法快非常多
24、贪心算法与动态规划类似，用于解决最优化问题，下面关于它们的叙述正确的是（）
∙A、贪心算法比较动态规划易于编码
∙B、两种算法都要求问题存在最优子结构
∙C、贪心算法是期望通过所做的局部最优选择来产生全局最优解决方案
∙D、贪心算法是期望通过所做的局部最优选择来产生全局最优解决方案
25、
在使用伪代码进行算法描述时，不可以实现循环的是（）。
while
for
if
goto
26、
关于几种排序算法的速度描述，正确的是（）
插入排序速度快，适合大规模数据
选择排序速度快，适合大规模数据
冒泡排序速度快，适合大规模数据
快速排序速度快，适合大规模数据
27、
下面关于网络流的属性的描述，错误的是（）
对于所有
；
28、大型程序设计一般用（）数据类型来描述算法。
∙A、逻辑
∙B、抽象
∙C、简明
∙D、复杂
29、与分治法不同的是，适合于用动态规划求解的问题（）。
∙A、经分解得到子问题往往不是互相独立的
∙B、经分解得到子问题往往是互相独立的
∙C、经分解得到子问题往往是互相交叉的
∙D、经分解得到子问题往往是任意的
30、
算法simpleMaxMin（A[l..r]）如下，
Max=Min=A[l];
fori=l+1tordo
ifA[i]>
MaxMax←A[i];
elseifA[i]<
MinMin←A[i];
returnMax,Min
其时间复杂度是（）。
2n
2（n-1）
3n
3（n-1）
31、快速排序法的基本思想是对输入的数组按以下三个步骤进行排序（）。
∙A、分解，合并，递归求解
∙B、合并，递归求解，分解
∙C、递归求解，分解，合并
∙D、分解，递归求解,合并
32、合并排序法的基本思想是：
将待排序元素分成大小大致相同的（）个子集合，分别对每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
∙A、4
∙B、3
∙C、2
∙D、5
33、在最优二叉搜索树问题中，我们的优化目标是（
∙A、只经过最少次数的比较就可以找到概率最大的元素
∙B、经过最多次数的比较就可以找到概率最小的元素
∙C、找到每个元素所需要的平均比较次数为最小
∙D、元素搜索代价的数学期望为最小
34、下面是贪心算法的基本要素的是（
∙A、重叠子问题
∙B、构造最优解
∙C、贪心选择性质
∙D、定义最优解
35、分治法所能解决的问题应具有的关键特征是（）。
∙A、该问题的规模缩小到一定的程度就可以容易地解决
∙B、该问题可以分解为若干个规模较小的相同问题
∙C、利用该问题分解出的子问题的解可以合并为该问题的解
∙D、该问题所分解出的各个子问题是相互独立的
36、T（n）=2n3+10n2log（n）+30n的渐近时间复杂度为（）。
∙A、O（n2log（n））
∙B、O（n4）
∙C、O（n3）
37、在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的最大收益，且已知rn所代表的最优解里，第一刀切下了3英寸，则下述公式正确的是（）。
∙A、rn=p3+rn-3
∙B、rn=rn–3
∙C、rn=rn-3+3
∙D、rn=r3+p3
38、（
）是贪心算法与动态规划算法的共同点。
∙D、最优子结构性质
39、
下列关于选择排序和冒泡排序的稳定性的说法，正确的是（）。
选择排序是稳定的，冒泡排序是稳定的。
选择排序是不稳定的，冒泡排序是不稳定的。
选择排序是稳定的，冒泡排序是不稳定的。
40、Edmonds-Karp算法中寻找增广路径的方法是（
∙A、深度优先算法
∙B、广度优先算法
∙C、Prim算法
∙D、Dijkstra算法
41、
使用分治法求解不需要满足的条件是（）。
∙A、子问题必须是一样的
42、在流网络中，对于源节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
∙A、在流网络中，对于任何节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
在流网络中，对于汇节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
∙C、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
∙D、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
43、在矩阵连乘问题的动态规划解决方案里，我们的所做的顶层决策是（
∙A、第一次矩阵乘法发生的位置
∙B、最后一次矩阵乘法发生的位置
∙C、结果矩阵维数最小的位置
∙D、结果矩阵列数最小的位置
44、关于0-1背包问题的下述形式化公式描述：
下述说法不正确的是（）。
∙A、i表示物品的重量
∙B、C表示背包容量
∙C、xi=0表示编号为i的物品不被选择
∙D、求解目标是最大化装入背包内的物品的总价值
45、在活动安排问题中，如果把全部活动按照结束时间递增序排序后，按贪心算法，我们总是安排（
46、
找零钱问题中，定义C[j]为兑换j所需要的硬币的最少数量，考虑下述递归表达式，
下列关于对i的寻优的最恰当描述是（
∙A、考虑找出的第一个硬币面值的各种可能性
∙B、考虑先找给客户几分钱
∙C、考虑最多可以用几个硬币
∙D、考虑最少可以用几个硬币
47、Huffman编码问题中，我们的优化目标是（
∙A、所有字符编码长度的数学期望为最小
∙B、给频度高的字符以最短的编码
∙C、给频度最低的字符以最长的编码
∙D、给每个字符相同长度的编码
48、一个有n个结点的带权无向图，其生成树应有（）条边。
∙A、n
∙B、n-1
∙D、n/2
49、算法必须具备输入、输出和（）等5个特性。
∙A、可执行性、可移植性和可扩充性
∙B、可行性、确定性和有穷性
∙C、确定性、有穷性和稳定性
∙D、易读性、稳定性和安全性
50、当问题的规模n趋向无穷大时，（）的数量级（阶）称为算法的渐进时间复杂度。
∙A、时间复杂度
∙B、空间复杂度
∙C、冗余度
∙D、迭代次数
51、对于n个元素的排序问题，n＝2时,只要作（）次比较即可排好序。
∙A、3
∙B、2
∙C、1
∙D、4
52、递归算法不能适用以下场合（）。
∙A、数据的定义形式按递归定义
∙B、数据之间的关系（即数据结构）按递归定义
∙C、问题解法按递归算法实现
∙D、概率问题
53、在最优二叉搜索树问题中，定义e[i,j]为ki,...,kj的最优二叉查找树的期望搜索成本，而我们需要通过寻优来确定最优二叉查找树的根结点的下标r,则r的取值范围为（）。
∙A、i≤r≤j
∙B、i<
r<
j
∙C、i≤r<
∙D、i<
r≤j
54、程序可以不满足算法性质的（）。
∙A、输入
∙B、输出
∙C、确定性
∙D、有限性
55、二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较：
如果（），则只要在数组a的左半部继续搜索x。
x＜a[n/2]
∙B、x=a[n/2]
∙C、x>
a[n/2]
∙D、x>
=a[n/2]
56、下列算法中通常以自底向上的方式求解最优解的是（
∙A、备忘录法
57、
备忘录方法的递归方式是（
自顶向下
自右向左
忽上忽下
自底向上
58、算法指的是（）。
∙A、计算方法
∙B、排序方法
∙C、解决问题的方法和过程
∙D、调度方法
59、
应用Johnson法则的流水作业调度采用的算法是（）
∙A、贪心算法
分治法
动态规划算法
60、贪心算法与动态规划算法的主要区别是（
∙A、最优子结构
∙B、贪心选择性质
∙C、构造最优解
61、
对于矩阵链连乘的子问题m[i,j]，当i=j时表明该矩阵链有两个矩阵。
∙正确
∙错误
错误
62、
算法就是一组无穷的规则（）
63、
问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。
正确
64、
动态规划和分治法在分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的（）。
65、
每一个递归定义都有其边界条件。
66、贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。
67、
用浮点数来表示大型整数，只能近似地表示它的大小（）
68、
多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。
69、子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。
70、
裴波那契数列的定义：
f（n）=f（n-1）+f（n-2）,f（0）=1,f
（1）=2，其数据的定义形式不是按递归定义。
71、
程序性能是指运行一个程序所需的内存大小和时间多少。
72、
一个操作所需的时间和操作数的类型无关（）
73、要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。
74、在JAVA语言中,执行特定认为的任务的函数或过程统称为方法。
75、
与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相不独立的（）。
76、
归并排序是指将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。
如果分割后子问题还很大，则继续分治，直到一个元素。
（）
77、
与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相独立的（）。
78、
对所有问题,贪心算法不能都得到整体最优解（）。
79、
算法重要特性是确定性、可实现性、输入、输出、有穷性（）。
80、0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解。
81、
指数时间算法只有在n取值非常小时才实用。
82、动态规划法其具体形式是多种多样的，但都具有相同的填表格式。
83、一般来说，对一个有序序列二分法（即把任意大小的问题尽可能地等分为两个子问题）较为有效。
84、如果各子问题是不独立的，一般用动态规划法比分治法较差。
85、
动态规划对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
86、当一个问题具有最优子结构性质时只能用动态规划方法求解。
87、
Huffmann编码树所对应的编码并不一定是前缀码。
88、通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理。
89、问题的计算复杂性一般是随着问题规模的增加而减小。
90、子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。
91、
Prim算法是一种动态规划算法。
92、标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。
93、问题解法按递归算法实现的问题适用于递归求解。
94、
一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
）
95、如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。
96、
对于矩阵链连乘的子问题m[i,j]，其对应的s[i,j]用于记录该矩阵链最后一次乘法发生的位置。
升级会员 