西安电子科技大学网络与继续教育学院
2023 学年上学期
《算法分析与设计》期末考试试题
(综合大作业)
一、填空题(每小题 4 分，共计 40 分)
1. 抽象数据类型的英文简称是 ，它是算法的一个 ____________连同定义在该 模型上并作为算法构件的一组_________。
2. O(f)+O(g)= __ ，O(f)O(g)= 。
3. 与分治法类似，动态规划算法的基本思想是_____________________，
先求解_________________ ，然后从这些解得到原问题的解。与分治法不同 的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是
的。
4. 直接或间接调用自身的算法称为________________，用函数自身给出定义的函数是
。
___________________
5. 5n2 + 5n 的渐近表达式是 ________ ，
log(n5 ) 的渐近表达式是 ____ ________ 。
6. 对于表达式n3 、5n2 、log n ， 20n , 按照渐近阶从低到高的顺序排列, 顺序是
。
____
7. 贪心算法总是做出在当前看来_____________ 的选择，也就是说，贪心
算法并不从整体最优考虑，它所做出的选择只是在某种意义上的_______
。
___________
8. 表示最优前缀码的二叉树总是一颗 ，即树中任一个结点都有两个儿子 结点。
9. 动态规划算法的两个基本要素是________________________和____
。
____________________
10. 部 分 背 包 问 题 适 用 于 _________________算 法 求 解 、 而 0- 1 背 包 问 题 适 用 于 ________________算法求解。
二、简答题(每小题 10 分，共计 40 分)
1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还 需要加上什么步骤？
2. 请简述为什么部分背包问题可以用贪心算法求解，而0- 1 背包问题却不能用贪心算法求解。
3. 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写出 该方程的一般形式，并指出其中各参数的意义。
4. 请简述动态规划算法求解最优化问题的步骤。
三、算法设计题(共计 20 分)
什么是贪心算法，用实例分析贪心算法是如何解决实际问题的。