算法设计与分析期末考试B卷

大学期末考试试卷B卷算法设计与分析

一、选择题30分，每题2分

1、下面的算法段针对不同的自然数n作不同的处理，其中函数oddn当n是奇数时返回true否则返回falsewhilen1ifoddnn=3*n+1;elsen=n/2;请问该算法所需计算时间的下界是OA.2nB.QnlognC.Qn!D.Qlogn

2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，si表示开始租用时刻，fi表示结束租用时刻，同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足位客户的需求P104A.3B.4C.5D.

63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用来消除或减少问题的好坏实例间的这种差别A.数值概率算法B.舍伍德算法C.拉斯维加斯算法D.蒙特卡罗算法

4、将一个正整数n表示成一系列正整数之和，n=m+g+・・・+nk其中，川三112》2nk，lk21正整数n的一个这种表示称为正整数n的一个划分正整数n的不同的划分个数总和称为正整数n的划分数，记作pn；另外，在正整数n的所有不同划分中，将最大加数nl不大于m的划分个数记作qnm则当n=10时，pn=oA.q88B.1+q99P12C.2+q108D.ABC都正确

5、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为oA.n!B.2nC.2n+1-lD.£〃!!P140/=i

6、在棋盘覆盖问题中，对于2kx2k的特殊棋盘有一个特殊方块，所需的L型骨牌的个数是一AA.4k-1/3B.2k/3C.4kD.2k

7、Tn表示当输入规模为n时的算法效率，以下算法效率最优的是A.Tn=Tn-1+1T1=1B.Tn=2n2C.Tn=Tn/2+1T1=1D.Tn=3nlog2n

8、给出一个由n个数组成的序列A[1…n]要求找出它的最长单调上升子序列，设m[i]1WiWn表示以A[i]结尾的最长单调上升子序列的长度，则=m[i]lin为m[i]=1+max{0m[k]A[k]A[i]IWkvi}m[i]=1+m[k]k=i-1i1m[i]=1+max{0m[k]A[k]WA[i]lWki}m[i]=max{0m[k]A[k]A[i]lWki}

9、有9个村庄，其坐标位置如下表所示:现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短A.

4.50B.

4.

54.5C.55D.

5010、关于回溯算法和分支限界法，以下是不正确描述A.回溯法中，每个活结点只有一次机会成为扩展结点B.分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中C.回溯法采用深度优先的结点生成策略D.分支限界法采用广度优先或最小耗费优先最大效益优先的结点生成策略

11、一个算法应该包含如下几条性质，除了OA.二义性B.有限性C.正确性D.可终止性

12、在寻找n个元素中第k小元素问题中，如使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行但不同方法，算法复杂度上界可能不同

13、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，请问他们怎样排队，才能使得总的排队时间最短OA.水桶大的人先打水B.水桶小的人先打水C.按照什么顺序都一样D.先到的人先打水

14、对布线问题，以下是不正确描述A.布线问题的解空间是一个图B.可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C.采用广度优先的标号法找到从起点到终点的布线方案这个方案如果存在的话不•定是最短的D.采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件

15、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解这要求原问题和子问题A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同

二、简答题40分，每题8分

1、现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表:每个选手必须与其他选手各赛一次；每个选手一天只能赛一次；循环赛一共进行n-1天请利用分治法的思想，给这8位运动员设计一个合理的比赛日程

2、对于矩阵连乘所需最少数乘次数问题，其递归关系式为min+m[k+1J]+pkp｝ijikjJ其中m［ij］为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi」为矩阵Ai的行，p为矩阵Ai的列现有四个矩阵，其中各矩阵维数分别为请根据以上的递归关系，计算出求矩阵连乘积AiA2A3A4所需要的最少数乘次数

3、对于4皇后问题，请画出用回溯法求解该问题时的搜索情况

4、请解释什么是P问题，NP问题以及NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题

5、有-1背包问题如下n=6c=20P=4815163W=5321048其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大

三、算法设计题30分，每题10分

1、【硬币找零】设有niWnWlO种不同面值的硬币，各种硬币的面值存于数组T［1…n］中现要用这些面值的硬币来找零钱可以使用的各种面值的硬币个数存于数组Coins口…n］中请设计一个算法计算找出钱数L0WLW20000的最少硬币个数

2、【钓鱼问题】在一条水平路边，有n2WnW25个钓鱼湖，从左到右编号为

1、

2、

3、…、n佳佳有H1WHW16个小时的空余时间，他希望用这些时间钓到尽量多的鱼他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼佳佳测出从第i个湖到第i+1个湖需要走5XTi分钟的路还测出在第i个湖边停留，第一个5分钟可以钓到鱼Fi以后再每钓5分钟鱼，鱼量减少Di为了简化问题，佳佳假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼请设计一个算法求出佳佳能钓到最多鱼的方案

3、【罗密欧与朱丽叶的迷宫问题】罗密欧与朱丽叶身处一个mXn的迷宫中，如下图所示每一个方格表示迷宫中的一个房间这mXn个房间中有一些房间是封闭的，不允许任何人进入在迷宫中任何位置均可沿8个方向进入未封闭的房间罗密欧位于迷宫的pq方格中，他必须找出一条通向朱丽叶所在的rs方格的路在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少每改变一次前进方向算作转弯一次请设计一个算法帮助罗密欧找出这样一条道路■12345678910si0315352886fi65498713121110•123456789xi123456789yi123456789AiAiA350x1010x4040x3030x5■罗褶丘IIO朱E研。