算法分析与设计期末考试模拟试题一

本文格式为Word版，下载可任意编辑——算法分析与设计期末考试模拟试题一

第1页（共4页）算法分析与设计期末考试模拟试题一

课程名称：__算法分析与设计考试形式：闭卷

学习中心：_________考试时间：90分钟

姓名：_____________学号：

一、填空题（每题4分，共计40分）

1.寻常只考虑三种状况下的时间繁杂度，即状况、

状况和状况下的时间繁杂度，分别记为Tmax(N)、Tmin

(N)和Tavg(N)，实践说明可操作性最好且最有实际价值的是状况下的时间繁杂度。

2.nn1032的渐近表达式是，

)log(3n的渐近表达式是。

3.根据符号O的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法

时，区别仅在于其中的。

4.递归算法是指的算法，递归函数

是指的

函数。

5.贪心算法总是做出在当前看来_____________的选择，也就是说，贪

心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的

________________。

6.假使某问题具有________________________和

___________________________两个重要性质，该问题可以用贪心算

法求解。

7.单源最短路径问题适合用_______________算法来求解、0-1背包问

题适合用_____________算法来求解。

8.分治法是将一个规模为n的问题分解为k个规模________的子问题，

这些子问题___________且与原问题__________。递归地求解这些子

问题，然后将各个子问题的解_________得到原问题的解。

9.动态规划算法的两个基本要素是____________________和

____________________。

10.___算法可以有效地解凸多边形最优三角剖分问题，

而____________算法是求解最优装载问题的有效方法。

二、简答题（每题10分，共计40分）

1.假使只需要求解问题的最优值，动态规划算法步骤是什么？假使需要构造最优解，则还需要加上什么步骤？

2.请简述什么是贪心选择性质

3.请简述什么是最小生成树。

4.请简述贪心算法比动态规划算法效率高的原因。

三、算法分析和设计题（每题10分，共计20分）

1.请写出汉诺塔问题的简要递归算法。

2.请设计一个在有序数组a[1..n]中二分探寻元素x的递归算法，要求若x在数组中则返回其下标否则返回0.

算法分析与设计模拟试题一答案

一、填空题答案（每题4分，共计40分）

第2页（共4页）

第3页（共4页）1.最坏、最好、平均、最坏

2.

)(2nO、)(lognO3.常数因子

4.直接或间接地调用自身、用函数自身给出定义

5.最好、局部最优选择

6.贪心选择性质、最优子结构性质

7.贪心算法、动态规划算法

8.较小、相互独立、一致、合并

9.最优子结构（性质）、子问题重叠（性质）

10.动态规划算法、贪心算法。

二、简答题答案（每题10分，共计40分）

1.假使只需要求解问题的最优值，动态规划算法步骤如下：

（1）找出最优解的性质，并刻画其结构特征；

（2）递归地定义最优值；

（3）以自底向上的方式计算出最优值；

假使需要构造最优解，则还需要加上如下步骤：

（4）根据计算最优值时得到的信息，构造最优解。

2.所谓贪心选择性质是指，所求问题的全局最优解可以通过一系列局

部最优选择，即贪心选择来达到。

3.假使G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的花费。在G的所有生成树中，花费最小的生成树称为G的最小生成树。

4.动态规划算法需要知道所有子问题的解，而贪心算法不需要知道所有子问题的解，它只是在每一步迭代中选择看起来最好的解，并不从整体进行最优考虑，因此效率较高。

三、算法分析和设计题答案（每题10分，共计20分）

1.汉诺塔问题的递归算法如下:

publicstaticvoidHanoi(intn,inta,intb,intc)

第4页（共4页）

{if(n0)

{

Hanoi(n-1,a,c,b);

Move(a,b);

Hanoi(n-1,c,b,a)；

}

}2.算法如下：

输入：正整数n和存储n个元素的数组a[1..n],被探寻的元素x输出：若x在数组中则返回其下标否则返回0

i=binarysearch(1,n,a,x);

returnI;

endBINARYSEARCH1

过程binarysearch(low,high,a,x)

//在数组a的下标为low到high范围内寻觅x,//若找到x则返回其下标否则返回0

iflowhighthen

return0;

else

mid=[]2/)(highlow+;

ifa[mid]=xthen

returnmid;

elseifa[mid]xthen

retu