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

问答题
给出一个找零问题的实例，使得贪婪算法不能输出一个最优解，为找零问题写一个贪婪算法的伪代码，它以金额n和硬币的面额d1＞d2＞…＞dm作为输入，以n的函数形式给出该算法的效率类型.
答案：
问答题
设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数的十进制表示从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。例如，将562843748分割成5，62，84，37，48，然后判断（5+62+84+37+48）能否被11整除
答案：//将一个大整数看成一个数组
//数组的奇数位对应数的10倍加上数组偶数对应数的本身 <...
单项选择题
整数5和10的最大公约数是（）。
A.10
B.5
C.30
D.50
单项选择题
下列问题适合用解析法求解的是（）
A.输出1000以内所有的完全平方数
B.一个小球从100米高的楼顶做自由落体运动，求落地时的速度V
C.将全班同学根据身高从高到矮排队
D.在一组彩球中寻找出所有的红球
判断题
数据结构与算法里，字符串和字符数组是一回事。
答案：错误
问答题
由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？
答案：①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）
②策略容易发现（关键：提取清楚问题中的维度）...
问答题
解0/1背包问题：n=4，M=14，（W1，W2，W3，W4）=（3，6，8，4），（P1，P2，P3，P4）=（2，4，6，3）。
答案：
单项选择题
数据结构与算法中，计算某范围内的素数之和，应该使用的是（）
A.单层循环
B.循环嵌套
C.continue语句+switch语句
D.return语句+continue语句
多项选择题
数据结构与算法里，顺序表的查找有（）
A.顺序查找
B.折半查找
C.随机查找
D.索引查找
问答题
请说明动态规划方法为什么需要最优子结构性质？
答案：最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子...