《计算机算法设计与分析》试卷 考试时间120分钟2002年-2003年第二学期学号 姓名 成绩一、阐述题1． 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下：① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。
② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。
③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。
④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。
⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。
这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。
凡是算法，都必须满足以上五条特性。
只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。
2． 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。
(10分) 答：森林是由m(m ≥0)棵互不相交的树构成的集合。
对树中的每一个结点而言，其子树的集合即为森林。
所以，森林和树是可以相互递归定义的。
对于一个非空的森林F=(T 1，T 2，…，T m )，因为至少存在一棵树，不妨假设为T 1，则森林F 可以分解成T 1和由T 2，…，T m 构成的森林。
于是，可得到森林的两种遍历算法。
① 先序遍历森林若森林非空，则可按下述规则遍历这个森林： （1） 访问树中第一棵树的根结点；（2） 先序遍历第一棵中根结点的所有子树构成的森林； （3） 先序遍历除去第一棵树外剩下的树构成的森林。
② 中序遍历森林若森林非空，则可按下述规则遍历这个森林：（1） 中序遍历第一棵中根结点的所有子树构成的森林； （2） 访问树中第一棵树的根结点；（3） 中序遍历除去第一棵树外剩下的树构成的森林。
第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。
若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。
由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。
必要性。
同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。
2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。
由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。
3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。
4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。
∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。
当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。
精品课程 课后习题答案第 1 章 算 法 概 述习蹬 1- 1函数的渐近表达式求下列函数的渐近表达式：3, f + 10 n ; 1l 匀10·+·2'' ; 分析与解答： 3矿＋10n 二. ( ) ( 4 ) ;,l / 10+ 2 擒 ＝ 0 （ 2” ) ; 2.1-t- l 过 一( ){ 1 ) ；lo 耟. ; t = ( ） ( l (1g1.1) ； I O l og 守 ＝（＇i ？！), 21 + 1;, 1; l o g n ' ; 10lv g3飞习题 1- 21（) . l ）和() ( 2 )的区别试论 ( )( l ) 和 () ( 2 )的区别． 分析与觞答：根据符号（）的定义易知0 (1 ) = 0( 2)。
用()(1) 或 0 ( 2 ) 表示同一个函数时 ，差别仅在于 其中的祜数因子。
习题 1- 4 按渐近阶排列表达式按照渐近阶从低到高的顺序排列以下表达式，4n \排在哪一位？分析与解答：l (）g n , 3入 20:ri, 2 . n 2／又 义叫 应该3飞 n!。
， 函 数 排列 顺 序 如 下 ： 2 ．l og t , n23 、20n, 4,i-, 按 浙 近 阶从 低到尚 习题 1- 5箕法效宇( l ) 假设某符法在椋人栽模为”时的计算时间为 T (,t) = 3 X 2又 在某 台计算机上实现井 完成该算 法的时间为1 秒．现有另一台计算机，其运行速度为第一台的 64 倍，那么在这台新 机器 十用 同 一 符 法在 t 秒 内 能 招 轮人规模为多大的间题？( 2) 若上述芬法的计算时间改进为 T ( n )＝r/'能解轴入规枑为多大的问烦？( 3) 若 上述算法的计算时间进一步改进为 T (11) = 8 ,f 秒和可能解输人规筷 为多 大的问 题？分析与解答 ：其余 条 件不 变 ，则 在新 机 器上用i 秒时间其 余 条 件 不 变 ，那么在新机器上用＂赁法 在 t · 秒1引能 解输人规模 为 n l 的问题。
《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是（D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为（B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。
A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是（A ）。
A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是（C ）。
A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A．递归函数 B.剪枝函数 C。
