算法设计与分析答案2023

第四章测试

1.在某通讯系统中用到了a，b，c，d，e，f 8个字符，字符频度（百分比）为 45， 13， 12，16，9，5则字符a的编码为( )：
A:0 B:1100
C:. 111
答案:A
2.活动安排问题利用贪心法求解，则其复杂度为（ ）
A:O(logn)
B:O(n2) C:O(n) D:O(nlogn) 3.在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。( )
A:对 B:错 4.背包问题与0-1背包问题求解方法类似，都能用贪心法或动态规划方法得到最优解（ ）
A:错 B:对 5.有关分治法、贪心算法和动态规划算法的描述，正确的是（ ）
A:适用三种方法所解的问题都是可分解成子问题的；
B:贪心算法和动态规划算法共同特征为最优子结构性质;
C:问题能用动态规划法解的不一定能用贪心算法解；
D:用贪心法一定能用动态规划法，但是，动态规划法的效率一般高于贪心算法。
6.下列哪些问题能适用贪心法高效求解？ （ ）
A:0-1背包问题 B:单源最短路径问题
C:最小生成树问题
D:哈夫曼编码问题