自己做图片的网站链接,加强残联网站建设,数码产品网站建设计划书,东营建设信息网最新消息算法分析与设计 第六次理论作业 文章目录 算法分析与设计 第六次理论作业一. 单选题#xff08;共4题#xff0c;50分#xff09;二. 填空题#xff08;共3题#xff0c;37.5分#xff09;三. 简答题#xff08;共1题#xff0c;12.5分#xff09; 一. 单选题#xf…算法分析与设计 第六次理论作业 文章目录 算法分析与设计 第六次理论作业一. 单选题共4题50分二. 填空题共3题37.5分三. 简答题共1题12.5分 一. 单选题共4题50分 (单选题) 关于哈夫曼算法的正确性以下叙述中正确的是 。 A.最优前缀码问题只满足贪心选择性质不满足最优子结构性质。 B.最优前缀码问题不满足贪心选择性质但满足最优子结构性质。 C.最优前缀码问题既不满足贪心选择性质也不满足最优子结构性质。 D.最优前缀码问题既满足贪心选择性质也满足最优子结构性质。 正确答案: D:最优前缀码问题既满足贪心选择性质也满足最优子结构性质。 ; 12.5分 (单选题) 含有n个顶点的连通图的生成树含有 条边。 A. n n n B. n − 1 n-1 n−1 C. n 2 n^2 n2 D. n ! n! n! 正确答案: B:n-1; 12.5分 (单选题) 以下问题中除了 其余问题都可以利用贪心算法得到全局最优解。 A.哈夫曼编码 B.单源最短路径 C.活动安排问题 D.多机调度问题 正确答案: D:多机调度问题 ; 12.5分 (单选题) 有9个村庄其坐标位置如下表所示 i123456789x(i)123456789Y(i)123456789现在要盖一所邮局为这9个村庄服务请问邮局应该盖在哪里才能使得邮局到这9个村庄的总距离和最短 A. (4.50) B.(4.54.5) C.(55) D.(50) 正确答案: C:(55) ;
二. 填空题共3题37.5分 (填空题) ____算法是求解单源最短路径问题的贪心算法。 正确答案 (1) Dijkstra (填空题) 求解最小生成树的____算法和____算法都属于贪心算法。 正确答案 (1) Prim(2) Kruskal (填空题) ____编码是求解最优前缀码的贪心算法。 正确答案 (1) 哈夫曼
三. 简答题共1题12.5分 (简答题) 【最优服务次序问题】设有n个文档需要在同一打印机上打印。假定第i个文档需要的打印时间为 t i t_i ti 1 ≤ i ≤ n 1\leq i \leq n 1≤i≤n。应该如何安排这n个文档的打印次序才能使每个文档的平均等待时间达到最小平均等待时间指的是所有n个文档等待时间的总和除以n。 正确答案 贪心策略最短服务时间优先 将 n 个顾客的服务时间 t i t_i ti 按照由小到大排序n 个顾客的服务调度方案即为排序后的顺序即可使得平均等待时间最小。
