2008.7算法设计与分析课程期末试卷

1、华南农业大学期末考试试卷（a卷）2007学年第二学期 考试科目：算法分析与设计考试类型：（闭卷）考试时间：120分钟学号 姓名 年级专业 题号一二三总分得分评阅人一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n作不同的处理，其中函数odd (n) 当n是奇数时返回true，否则返回false，while ( n > 1)if ( odd (n) )n = 3 * n + 1;elsen = n / 2;请问该算法所需计算时间的下界是 d 。a（2n）b（nlog n）c（n！）d（logn）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租

2、用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻，i12345678910s（i）0315352886f（i）65498713121110同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足 b 位客户的需求。 p104a3b4c5d63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 b 来消除或减少问题的好坏实例间的这种差别。a数值概率算法b舍伍德算法c拉斯维加斯算法d蒙特卡罗算法4、将一个正整数n表示成一系列正整数之和，n = n1 + n2 + +nk（其中，n1n2 nk1，k1）正整数

3、n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）= c 。aq（8，8）b1 + q（9，9） p12c2 + q（10，8）da，b，c都正确5、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 b 。an!b2n c2n+1-1d p1406、在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的l型骨牌的个数是 a 。a（4k 1）/3b2k /3 c4k d2k7、t（n）表示当输入规模

4、为n时的算法效率，以下算法效率最优的是 c 。at（n）= t（n 1）+1，t（1）1 bt（n）= 2n2ct（n）= t（n/2）+1，t（1）=1 dt（n）= 3nlog2n8、给出一个由n个数组成的序列a1n，要求找出它的最长单调上升子序列，设mi（1in），表示以ai结尾的最长单调上升子序列的长度，则m1 = 1，mi（1 < i n）为 a 。ami = 1 + max0，mk（ak < ai，1k < i ）bmi = 1 + mk （k = i - 1 && i > 1）cmi = 1 + max0，mk （ak ai，1k <

5、 i ） dmi = max0，mk（ak < ai，1k < i ） 设表示：从左向右扫描过来直到以元素结尾的序列，获得的最长上升子序列的长度，且子序列包含元素（）。即，是从，到中找最大的一个值，再加1。或者就是1。主要是看ai这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。最后，所要求的整个序列的最长公共子序列长度为maxf(i): 1<=i<=n例如，对于序列：4 2 6 3 1 5 2i1234567array4263152f(i)11221329、有

6、9个村庄，其坐标位置如下表所示：i123456789x（i）123456789y（i）123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 c 才能使到邮局到这9个村庄的总距离和最短。a（4.5，0）b（4.5，4.5）c（5，5）d（5，0）10、关于回溯算法和分支限界法，以下 a 是不正确描述。a回溯法中【应为分支限界法】，每个活结点只有一次机会成为扩展结点b分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中c回溯法采用深度优先的结点生成策略d分支限界法采用广度优先或最小

7、耗费优先（最大效益优先）的结点生成策略11、一个算法应该包含如下几条性质，除了 a 。a二义性b有限性c正确性d可终止性12、在寻找n个元素中第k小元素问题中，如使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面 d 答案解释最合理。a随机选择一个元素作为划分基准b取子序列的第一个元素作为划分基准c用中位数的中位数方法寻找划分基准d以上皆可行。但不同方法，算法复杂度上界可能不同13、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，请问他们怎样排队，才能使得总的排队时间最短 c 。a水桶大的人先打水b水桶小的人先打水c按照什么顺序都一样d先到的人先打水14、对布

8、线问题，以下 c 是不正确描述。a布线问题的解空间是一个图b可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定c采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的d采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件15、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 c 。a问题规模相同，问题性质相同b问题规模相同，问题性质不同c问题规模不同，问题性质相同d问题规模不同，问题性质不同二、简答题（40分

9、，每题8分）1、 现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：（1） 每个选手必须与其他选手各赛一次；（2） 每个选手一天只能赛一次；（3） 循环赛一共进行n 1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。2、 对于矩阵连乘所需最少数乘次数问题，其递归关系式为其中mi，j为计算矩阵连乘aiaj所需的最少数乘次数，pi-1为矩阵ai的行，为矩阵ai的列。现有四个矩阵，其中各矩阵维数分别为：a1a2a3a450´1010´4040´3030´5请根据以上的递归关系，计算出求矩阵连乘积a1a2a3a4所需要的最少数乘

10、次数。3、 对于4皇后问题，请画出用回溯法求解该问题时的搜索情况。4、 请解释什么是p问题，np问题以及np完全问题并描述这三者之间的关系；最后，请列举几个常见的np完全问题。1）合取范式的可满足性问题；2）三元合取范式的可满足性问题；3）团问题；4）顶点覆盖问题；5）子集和问题；6）哈密顿回路问题；7）旅行售货员问题5、 有0-1背包问题如下：n=6，c=20，p=（4，8，15，1，6，3），w=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，p表示物品的价值，w表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。p=(15，

11、8，6，4，3，1) w=(2，3，4，5，8，10)，单位重量物品价值（7.5，2.67，1.5,0.8,0.375,0.1）解：可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。1.先把重量为2的物品放进背包，此时剩余载重量为17，p为15。2.把重量为3的物品放进背包，此时剩余载重量为14，p为23；3.把重量为4的物品放进背包，此时剩余载重量为10，p为29；4.把重量为5的物品放进背包，此时剩余载重量为5，p为33.由于8>5，所以不能再放进背包。结果是把重量为2，3，4，5的物品装进背包，总价值最大为33.三、算法设计题（3

12、0分，每题10分）1、【硬币找零】设有n（1n10）种不同面值的硬币，各种硬币的面值存于数组t1n中。现要用这些面值的硬币来找零钱。可以使用的各种面值的硬币个数存于数组coins1n中。请设计一个算法计算找出钱数 l（0l20000）的最少硬币个数。 (1)状态表示：不妨设0<t1<t2<<tn。当只用面值为t1，t2，ti的硬币时，可找出钱数j的最少硬币个数记为ci,j；当只用这些面值的硬币找不出钱数j时，记ci,j=。问题的解即为cn,l。 (2)最优子结构性质 设sk，k=1,2,i 是只用面值为t1，t2，ti的硬币找钱j的一个最优找钱序列,即 j = ,而且

13、则容易看出：sk，k=1,2,i-1是只用面值为t1,t2,ti-1的硬币找钱j-siti的一个最优找钱序列。 (2)根据最优子结构性质,可以建立递归关系： 初始条件为：ci,00，il，n;2、【钓鱼问题】在一条水平路边，有n（2n25）个钓鱼湖，从左到右编号为1、2、3、n。佳佳有h（1h16）个小时的空余时间，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。佳佳测出从第i个湖到第i+1个湖需要走5×ti分钟的路，还测出在第i个湖边停留，第一个5分钟可以钓到鱼fi，以后再每钓5分钟鱼，鱼量减少di。为了简化问题，佳佳假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请设计一个算法求出佳佳能钓到最多鱼的方案。3、【罗密欧与朱丽叶的迷宫问题】罗密欧与朱丽叶身处一个m×n的迷宫中，