算法分析作业
- 格式：doc
- 大小：556.50 KB
- 文档页数：11
算法分析练习题（一）
一、选择题
1、二分搜索算法就是利用（ A ）实现得算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不就是动态规划算法基本步骤得就是（ A ）。
A、找出最优解得性质 B、构造最优解 C、算出最优解 D、定义最优解
3．下列算法中通常以自底向上得方式求解最优解得就是（ B ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
4、衡量一个算法好坏得标准就是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
5、以下不可以使用分治法求解得就是（D ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题
6、 实现循环赛日程表利用得算法就是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
7、备忘录方法就是那种算法得变形。（ B ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法
8．最长公共子序列算法利用得算法就是（ B ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
9．实现棋盘覆盖算法利用得算法就是（ A ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
10、 矩阵连乘问题得算法可由（ B）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
11、Strassen矩阵乘法就是利用（ A ）实现得算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
12、使用分治法求解不需要满足得条件就是（A ）。
A 子问题必须就是一样得
B 子问题不能够重复 C 子问题得解可以合并
D 原问题与子问题使用相同得方法解
13、下列算法中不能解决0/1背包问题得就是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
14．实现合并排序利用得算法就是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
15．下列就是动态规划算法基本要素得就是（ D ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
16．下列算法中通常以自底向下得方式求解最优解得就是（ B ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
17、合并排序算法就是利用（ A ）实现得算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
18．实现大整数得乘法就是利用得算法（ C ）。
A、贪心法 B、动态规划法 C、分治策略 D、回溯法
19、 实现最大子段与利用得算法就是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
20、 一个问题可用动态规划算法或贪心算法求解得关键特征就是问题得（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
21、 实现最长公共子序列利用得算法就是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
二、填空题
1、算法得复杂性有 时间 复杂性与 空间 复杂性之分。
2、程序就是 算法 用某种程序设计语言得具体实现。
3、算法得“确定性”指得就是组成算法得每条 指令 就是清晰得，无歧义得。
4、矩阵连乘问题得算法可由 动态规划 设计实现。
5、算法就是指解决问题得 一种方法 或 一个过程 。 6、从分治法得一般设计模式可以瞧出，用它设计出得程序一般就是 递归算法 。
7、矩阵连乘问题得算法可由 动态规划 设计实现。
8、 动态规划算法得基本思想就是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 得解得到原问题得解。
9、算法就是由若干条指令组成得有穷序列，且要满足输入、 输出
、确定性与 有限性 四条性质。
10、大整数乘积算法就是用 分治法 来设计得。
11、快速排序算法就是基于 分治策略 得一种排序算法。
12、动态规划算法得两个基本要素就是、 性质与 性质 。
13、任何可用计算机求解得问题所需得时间都与其 规模 有关。
14、快速排序算法得性能取决于 划分得对称性 。
15、出自于“平衡子问题”得思想，通常分治法在分割原问题，形成若干子问题时，这些子问题得规模都大致 相同 。
16、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索得时间复杂性为O（），在最坏情况下，搜索得时间复杂性为O（ logn ）。
17、已知一个分治算法耗费得计算时间T(n)，T(n)满足如下递归方程：
22221nnOnTnOnT)()/()()(
解得此递归方可得T(n)= O（ nlogn ）。
18、动态规划算法有一个变形方法 备忘录方法 。这种方法不同于动态规划算法“自底向上”得填充方向，而就是“自顶向下”得递归方向，为每个解过得子问题建立了备忘录以备需要时查瞧，同样也可避免相同子问题得重复求解。
19、递归得二分查找算法在divide阶段所花得时间就是 O(1) ，conquer阶段所花得时间就是 T(n/2) ，算法得时间复杂度就是 O( log n) 。
20、用动态规划算法计算矩阵连乘问题得最优值所花得时间就是 O(n3) ，
子问题空间大小就是 O(n2) 。
21、一个算法得优劣可以用（时间复杂度）与（空间复杂度）与来衡量。
22、直接或间接地调用自身得算法称为（递归算法）。
23、 记号在算法复杂性得表示法中表示（渐进确界或紧致界）。 24、在分治法中，使子问题规模大致相等得做法就是出自一种（平衡子问题）得思想。
25、动态规划算法适用于解（具有某种最优性质）问题。
26、最优子结构性质得含义就是（问题得最优解包含其子问题得最优解）。
27、按照符号O得定义O(f)+O(g)等于O(max{f(n),g(n)})。
28、二分搜索技术就是运用（分治）策略得典型例子。
29、动态规划算法中，通常不同子问题得个数随问题规模呈（多项式）级增长。
30、（最优子结构性质）与（子问题重叠性质）就是采用动态规划算法得两个基本要素。
三、算法填空
1、最大子段与: 动态规划算法
int MaxSum(int n, int a[])
{
int sum=0, b=0； //sum存储当前最大得b[j], b存储b[j]
for(int j=1； j<=n； j++) {
if（b>0） b+=a[j] ；
else b=a[i] ； //一旦某个区段与为负，则从下一个位置累与
if (b>sum) sum=b ；
}
return sum；
}
2、快速排序
template
void QuickSort (Type a[], int p, int r)
{
if (p
int q=Partition(a,p,r);
QuickSort（a，p，q-1） ; //对左半段排序
QuickSort(a,q+1,r) ; //对右半段排序
}
}
四、简答题
1、写出下列复杂性函数得偏序关系（即按照渐进阶从低到高排序）：
2323log!log10nnnnnnnnn
2、将所给定序列a[1:n]分为长度相等得两段a[1:n/2]与a[n/2+1:n]，分别求出这两段得最大子段与，则a[1:n]得最大子段与有哪三种情形？
3、请说明动态规划方法为什么需要最优子结构性质。
最优子结构性质就是指大问题得最优解包含子问题得最优解。 动态规划方法就是自底向上计算各个子问题得最优解，即先计算子问题得最优解，然后再利用子问题得最优解构造大问题得最优解，因此需要最优子结构
4、设计动态规划算法得主要步骤就是怎么得？请简述。
参考解答：（1）找出最优解得性质，并刻划其结构特征。(6分) （2）递归地定义最优值。
（3）以自底向上得方式计算出最优值。
（4）根据计算最优值时得到得信息，构造最优解。
5、分治法所能解决得问题一般具有哪几个特征？请简述。
参考解答：（1）该问题得规模缩小到一定得程度就可以容易地解决；(6分) （2）该问题可以分解为若干个规模较小得相同问题，即该问题具有最
优子结构性质;
（3） 利用该问题分解出得子问题得解可以合并为该问题得解；
（4）原问题所分解出得各个子问题就是相互独立得，即子问题之间不包
含公共得子问题。
6、算法得要特性就是什么？
参考解答：确定性、可实现性、输入、输出、有穷性
7、 算法分析得目得就是什么？
参考解答：分析算法占用计算机资源得情况，对算法做出比较与评价，设计出额更好得算法。
8、算法得时间复杂性与问题得什么因素相关？
参考解答：算法得时间复杂性与问题得规模相关，就是问题大小n得函数。
9、算法得渐进时间复杂性得含义？
参考解答：当问题得规模n趋向无穷大时，影响算法效率得重要因素就是T(n)得数量级，而其她因素仅就是使时间复杂度相差常数倍，因此可以用T(n)得数量级(阶)评价算法。时间复杂度T(n)得数量级(阶)称为渐进时间复杂性。
10简述渐进时间复杂性上界得定义。
参考解答：T(n)就是某算法得时间复杂性函数，f(n)就是一简单函数，存在正整数No与C，n〉No，有T(n)
11快速排序算法最坏情况下需要多少次比较运算？ 参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。
12 阐述归并排序得分治思路。
参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序得两个序列归并成一个含n个元素得分好类得序列。如果分割后子问题还很大，则继续分治，直到一个元素。
13 快速排序得基本思想就是什么。
参考解答：快速排序得基本思想就是在待排序得N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小得放在前一部分，所有比它大得放置在后一部分，并把该记录排在这两部分得中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。
