算法设计与分析2014试题B卷

诚信保证

本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号：

西北工业大学考试试题（卷）

2013－2014学年第2 学期

成绩 开课学院 计算机学院 课程 算法设计与分析 学时 48 开A考试日期 2014.6.30 考试时间 2 小时 考试形式（）（）卷 闭B考生班级 学 号 姓 名 一、简答题，共5题，每题8分（40分） 1. 简述分治法的基本思想。 2. 简述回溯算法的基本思想及其一般模式。 3. 简述分支限界法的基本思想。 4. 简述贪心算法的基本思想。 5. 简述分治法与动态规划的区别与联系。 二、应用题，共5题，每题12分（60分） 1、设有8个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他7个选手各赛一次； (2)每个选手一天只能参赛一次； (3)循环赛在7天内结束。 2、设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为t i ， 1 ≤i ≤n 。应如何安排 n 个顾客的服务次序才能使平均等待时间达到最小 ? 平均等待时间是 n 个顾客等待服务时间的总和除以 n 。 注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。 2. 命题教师和审题教师姓名应在试卷存档时填写。 共 2 页 第 1 页

西北工业大学命题专用纸 3、0-1背包问题：n=6, c=20, p=(4,8,15,1,6,3), w=(5,3,2,10,4,8)，其中n为物品个数，c为背包重量，p表示物品价值，w代表物品重量。请问应如何放进物品才能使放进背包的物品总价值最大，能获得的最大价值是多少？ 4、哈夫曼编码问题：文件中共有6个不同的字符出现，且各字母出现的次数分别为：a为30次，b为20次，c为15次，d为10次，e为5次，f为5次，求出哈夫曼编码。（要求：画出哈夫曼树）。 5、请写出斐波那契查序列的输出算法。 教务处印制 共 2 页 第 2 页

本文来源：https://www.bwwdw.com/article/ohhd.html