算法分析与设计 第六次理论作业
一. 单选题（共4题，50分）
-
(单选题) 关于哈夫曼算法的正确性，以下叙述中正确的是（ ）。
A.最优前缀码问题只满足贪心选择性质，不满足最优子结构性质。
B.最优前缀码问题不满足贪心选择性质，但满足最优子结构性质。
C.最优前缀码问题既不满足贪心选择性质，也不满足最优子结构性质。
D.最优前缀码问题既满足贪心选择性质，也满足最优子结构性质。
正确答案: D:最优前缀码问题既满足贪心选择性质，也满足最优子结构性质。 ;
12.5分
-
(单选题) 含有n个顶点的连通图的生成树含有（ ）条边。
A. \(n\)
B. \(n-1\)
C. \(n^2\)
D. \(n!\)
正确答案: B:n-1;
12.5分
-
(单选题) 以下问题中，除了（ ），其余问题都可以利用贪心算法得到全局最优解。
A.哈夫曼编码
B.单源最短路径
C.活动安排问题
D.多机调度问题
正确答案: D:多机调度问题 ;
12.5分
-
(单选题) 有9个村庄，其坐标位置如下表所示：
i 1 2 3 4 5 6 7 8 9 x(i) 1 2 3 4 5 6 7 8 9 Y(i) 1 2 3 4 5 6 7 8 9 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在哪里才能使得邮局到这9个村庄的总距离和最短？（ ）
A. (4.5，0)
B.(4.5，4.5)
C.(5，5)
D.(5，0)
正确答案: C:(5，5) ;
二. 填空题（共3题，37.5分）
-
(填空题) ____算法是求解单源最短路径问题的贪心算法。
正确答案： (1) Dijkstra
-
(填空题) 求解最小生成树的____算法和____算法都属于贪心算法。
正确答案： (1) Prim(2) Kruskal
-
(填空题) ____编码是求解最优前缀码的贪心算法。
正确答案： (1) 哈夫曼
三. 简答题（共1题，12.5分）
-
(简答题) 【最优服务次序问题】设有n个文档需要在同一打印机上打印。假定第i个文档需要的打印时间为\(t_i\)，\(1\leq i \leq n\)。应该如何安排这n个文档的打印次序才能使每个文档的平均等待时间达到最小？（平均等待时间指的是所有n个文档等待时间的总和除以n）。
正确答案：
贪心策略：最短服务时间优先
将 n 个顾客的服务时间 \(t_i\) 按照由小到大排序，n 个顾客的服务调度方案即为排序后的顺序，即可使得平均等待时间最小。