算法设计与分析章节练习(2020.02.10)

单项选择题
判断完数的算法，需要求因子之和，若累加器为sum，则sum应该赋初值为（）
A.sum=0；
B.sum=i；
C.sum=1；
D.sum=sum；
单项选择题
备忘录方法是哪种算法的变形。（）
A.分治法
B.动态规划法
C.贪心法
D.回溯法
判断题
汉诺塔的时间复杂度从阶梯来讲，属于指数阶。
答案：正确
问答题
对于输入30，20，56，75，31，19和散列函数h（K）=Kmod11a.构造它们的开散列表b.求在本表中成功查找的最大键值比较次数c.求在本表中成功查找的平均比较次数
答案：
填空题
一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有（）复杂性和空间复杂性之分。
答案：时间
填空题
贪心算法的基本要素是（）质和（）性质。
答案：贪心选择；最优子结构
问答题
对下列各组函数f（n）和g（n），确定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并简要说明理由。（1）f（n）=2n；g（n）=n!（2）f（n）=√n；g（n）=logn2（3）f（n）=100；g（n）=log100（4）f（n）=n3；g（n）=3n（5）f（n）=3n；g（n）=2n
答案：（1）f（n）=O（g（n）），因为g（n）的阶比f（n）的阶高。
（2）f（n）=Ω（g（n））...
判断题
设T（n）=n，根据T（n）=O（f（n））的定义，O（n2）=T（n）。
答案：错误
填空题
计算机的资源最重要的是（）和（）资源。因而，算法的复杂性有（）和（）之分。
答案：时间；空间；时间复杂度；空间复杂度
填空题
递归算法设计的关键在于找出（）和（）。
答案：递归关系（递归方程）；递归终止（边界）条件