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

问答题
由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？
答案：①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）
②策略容易发现（关键：提取清楚问题中的维度）...
问答题
编写一个Heap Sorting算法，并分析时间复杂性。
答案：
多项选择题
30个记录的序列进行冒泡排序，则有可能（）。
A.29次比较就完成排序
B.进行29趟排序才结束排序
C.不能完成排序
D.可能10趟就结束了排序
问答题
回溯法与分支限界法的区别是什么？
答案：两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条...
问答题
分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。
答案：
不一定导致递归。
如非递归的二叉树中序遍历。
这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。
单项选择题
关于循环嵌套描述不正确的是（）
A.循环嵌套就是一个循环结构体内还有另一个循环结构，也称为多重循环。
B.for循环只能嵌套for循环结构
C.for循环可以嵌套while，也可以嵌套do...while结构
D.continue只可以用于循环结构语句中
判断题
冒泡排序若在一趟排序中没有记录交换则停止。这样能加快排序的速度。
答案：正确
问答题
有0-1背包问题如下：n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）
答案：可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先...
多项选择题
数据结构与算法里，属于不稳定排序的是（）。
A.快速排序
B.冒泡排序
C.直接插入排序
D.希尔排序
问答题
使用prim算法构造出如下图的一棵最小生成树。
答案：