算法导论中文课件练习.pptxVIP

西电软件学院算法分析与设计

练习

西电软件学院练习试描述分治策略求解问题的一般方法分治策略按照分而治之再合并的过程求解问题：分：将问题P分解为规模更小的子问题P1,P2,…,Pk。治：递归求解这些子问题。合并：将子问题P1,P2,…,Pk的解合并为问题P的解。

西电软件学院练习利用插入排序算法完成下面6个数的排序，给出每一趟插入完成后的数组状态。插入排序最坏情况下的计算时间量级是多少？51082274解：5105810581022578102245781022最坏情况下的计算时间为：O(n2)

西电软件学院练习利用归并排序算法完成下面8个数的排序，给出每一趟归并完成后的数组状态。归并排序的计算时间量级是多少？51082274616解：最坏情况下的计算时间为：O(nlgn)

西电软件学院练习快速排序算法最坏情况是什么？最坏情况下的计算时间是多少？其最好情况是什么？最好情况下的计算时间是多少？最坏情况：每次选取的划分元素均是集合中的最大或最小元素。O(n2)最好情况每次选取的元素是集合中中值元素。O(nlgn)

西电软件学院练习在下图所示的树中，结点2（值为4）处不满足大顶堆的性质，请调整该树，使其满足大顶堆的性质。如果将结点6（值为9）的值修改为20，堆该如何调整？请给出堆调整的详细过程。

西电软件学院练习基于比较的排序算法在最坏情况下的时间下界是多少？基数排序算法的基本思想如何？计数排序算法对输入数据有什么要求？这两个排序算法的计算时间是多少？nlgn基数排序的基本思想：从最低位开始，使用稳定的辅助排序算法依次按照每一位对输入数据排序。计数排序要求输入数据是1~k范围内的整数O(n)

西电软件学院练习试描述动态规划策略求解问题的一般方法1.确定最优解的结构。2.递归定义最优解的值。3.自底向上计算解的值。4.利用计算得到的信息构造最优解。利用动态规划策略求解问题时，通常要求问题需要具备什么特征？最优子结构：问题的最优解包含其子问题的最优解重复子问题：递归求解过程中只涉及相对较少的子问题，而这些子问题重复出现多次。

西电软件学院练习采用动态规划算法计算以下装配线调度问题（每条流水线上3个站，相应时间如图所示）的最少装配时间，并给出相应的最优装配路径。493756323312327161891319最少装配时间：21

西电软件学院练习0-1背包问题与分数背包问题有何区别？哪个问题可以使用贪心策略求解？贪心求解过程中正确的贪心准则是什么？哪个问题需要用动态规划策略求解？0-1背包要求每件物品要么全部拿走，要么不拿，而分数背包则允许带走物品的一部分。分数背包可用贪心策略求解；正确的贪心准则是按照“单位重量的价值”由高到低的顺序依次选取物品。0-1背包问题需要用动态规划求解

西电软件学院练习假设要设计一套用于编码a到f六个字符的编码方案，每个字符出现的频率如下所示。请设计相应的霍夫曼编码，给出构造霍夫曼编码树的过程及最后得到的编码方案。a:18b:32c:4d:8e:12f:26

西电软件学院练习利用Dijkstra算法求解下图中从源点A到图中所有结点的最短路径。该算法使用的哪种算法设计策略？该算法对图中边的权值有什么要求？该算法使用的是贪心策略；要求图中所有边的权值均非负。ABCDE582361731ABCDE0∞∞∞∞58∞∞711121089

西电软件学院练习插入排序算法在最坏情况下的计算时间为（）A)O(n)B)O(n2)C)O(nlgn)D)O(n3)快速排序算法在最坏情况下的计算时间为（）A)O(n)B)O(n2)C)O(nlgn)D)O(n3)归并排序算法在最坏情况下的计算时间为（）A)O(n)B)O(n2)C)O(nlgn)D)O(n3)基于比较的排序最坏情况下的计算时间下界为（）A)O(n)B)O(n2)C)O(nlgn)D)O(n3)大顶堆要求父结点的值()孩子结点的值。A)等于B)大于等于C)小于等于D)