平顶山算法考试题 平顶山算法考试题

院（系） 专业 姓名 学号 班级

密封线内不要答题

…………………………………… 密……………………………………封………………………………………线………………………………………

平顶山学院 2007 ~ 2008 学年第二学期期终考试

《 算法分析与设计 》 A 卷

适用年级 2006 适用专业 软件个工程（本科）

考试形式 闭卷 考试时间 110 (分钟)

n

3. 用回溯法和分支限界法解题时常遇到的两类典型的解空间树是___________

和___________。

4. 分支限界法在解空间树 T 上的搜索方式是_________________。

5.用贪心算法求解的问题中它们一般具有_______________________和_______

_____________两个重要的性质。

6. 对于含有 n 个元素的排列树问题，最坏情况下其解空间的叶结点数目为____

_________ 。

二．简答题 （每小题 5 分，共 20 分）

1. 动态规划算法的基本思想是什么？

3. 数值随机化算法、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法四类随机化

1. 设某算法在输入规模为 n 时的计算时间为 T(n)=10*2

n

。若在甲台计算机上

实现并完成该算法的时间为 t 秒，现有一台运行速度是甲的 64 倍的另一台计

算机乙，问在乙计算机上用同一算法在 t 秒内能解决的问题的规模是多大？

（5 分）

2. 快速排序算法最坏情况下的复杂度为多少？如何修改快速排序算法，使它在

最坏情况下的计算时间为 O(nlogn)。（ 5 分）

3. 已知一棵二叉树 T 的中序和后序遍历序列分别为 DEBAFC 和 EDBFCA，问

《 算法分析与设计 》试卷 第7页（共 8 页） 《 算法分析与设计 》试卷 第8页（共 8 页）