搜索
1华南农业大学期末考试试卷（A卷）2007学年第二学期考试科目：算法分析与设计考试类型：（闭卷）考试时间：120分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n作不同的处理，其中函数odd(n)当n是奇数时返回true，否则返回false，while(n1)if(odd(n))n=3*n+1;elsen=n/2;请问该算法所需计算时间的下界是D。A．Ω（2n）B．Ω（nlogn）C．Ω（n！）D．Ω（logn）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻，i12345678910s（i）0315352886f（i）65498713121110同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足B位客户的需求。P104A．3B．4C．5D．63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有2较大差别时，可以使用B来消除或减少问题的好坏实例间的这种差别。A．数值概率算法B．舍伍德算法C．拉斯维加斯算法D．蒙特卡罗算法4、将一个正整数n表示成一系列正整数之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）=C。A．q（8，8）B．1+q（9，9）P12C．2+q（10，8）D．A，B，C都正确5、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为B。A．n!B．2nC．2n+1-1D．niin1!/!P1406、在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是A。A．（4k–1）/3B．2k/3C．4kD．2k7、T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是C。A．T（n）=T（n–1）+1，T（1）＝1B．T（n）=2n2C．T（n）=T（n/2）+1，T（1）=1D．T（n）=3nlog2n8、给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1i≤n）为A。A．m[i]=1+max{0，m[k]（A[k]A[i]，1≤ki）}B．m[i]=1+m[k]（k=i-1&&i1）C．m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤ki）}D．m[i]=max{0，m[k]（A[k]A[i]，1≤ki）}设()fi表示：从左向右扫描过来直到以[]ai元素结尾的序列，获得的最长上升子序列的长度，且子序列包含[]ai元素（1in）。311()max{()1:[][];1}111;(1)[][]ififjaiajjiiijjiaiaj当,都有即，()fi是从(1)f，(2)f……到(1)fi中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。最后，所要求的整个序列的最长公共子序列长度为max{f(i):1=i=n}例如，对于序列：4263152i1234567array4263152f(i)11221329、有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．分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略11、一个算法应该包含如下几条性质，除了A。A．二义性B．有限性C．正确性D．可终止性12、在寻找n个元素中第k小元素问题中，如使用快速排序算法思想，运用分治算4法对n个元素进行划分，应如何选择划分基准？下面D答案解释最合理。A．随机选择一个元素作为划分基准B．取子序列的第一个元素作为划分基准C．用中位数的中位数方法寻找划分基准D．以上皆可行。但不同方法，算法复杂度上界可能不同13、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，请问他们怎样排队，才能使得总的排队时间最短C。A．水桶大的人先打水B．水桶小的人先打水C．按照什么顺序都一样D．先到的人先打水14、对布线问题，以下C是不正确描述。A．布线问题的解空间是一个图B．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的D．采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件15、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题C。A．问题规模相同，问题性质相同B．问题规模相同，问题性质不同C．问题规模不同，问题性质相同D．问题规模不同，问题性质不同二、简答题（40分，每题8分）1、现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n–1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。52、对于矩阵连乘所需最少数乘次数问题，其递归关系式为其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，ip为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A4501010404030305请根据以上的递归关系，计算出求矩阵连乘积A1A2A3A4所需要的最少数乘次数。3、对于4皇后问题，请画出用回溯法求解该问题时的搜索情况。jipppjkmkimjijimjki}],1[],[{min0],[1jki213132214142314134322432113231214241314432342432142143431324x2=2x3=3x4=4x1=1113834691114165710121517229241920222527303221232628313318454035363841434648373942444749346156515254575962645355586063655064、请解释什么是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，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.由于85，所以不能再放进背包。结果是把重量为2，3，4，5的物品装进背包，总价值最大为33.三、算法设计题（30分，每题10分）71、【硬币找零】设有n（1≤n≤10）种不同面值的硬币，各种硬币的面值存于数组T[1…n]中。现要用这些面值的硬币来找零钱。可以使用的各种面值的硬币个数存于数组Coins[1…n]中。请设计一个算法计算找出钱数L（0≤L≤20000）的最少硬币个数。•(1)状态表示：不妨设0T[1]T[2]…T[n]。当只用面值为T[1]，T[2]，…，T[i]的硬币时，可找出钱数j的最少硬币个数记为C[i,j]；当只用这些面值的硬币找不出钱数j时，记C[i,j]=∞。问题的解即为C[n,L]。•(2)最优子结构性质•设S[k]，k=1,2,…,i是只用面值为T[1]，T[2]，…，T[i]的硬币找钱j的一个最优找钱序列,即j=,而且则容易看出：S[k]，k=1,2,…,i-1是只用面值为T[1],T[2],…,T[i-1]的硬币找钱j-S[i]T[i]的一个最优找钱序列。•(2)根据最优子结构性质,可以建立递归关系：•初始条件为：C[i,0]＝0，i＝l，…，n;2、【钓鱼问题】在一条水平路边，有n（2≤n≤25）个钓鱼湖，从左到右编号为1、2、3、…、n。佳佳有H（1≤H≤16）个小时的空余时间，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。佳佳测出从第i个湖到第i+1个湖需要走5×Ti分钟的路，还测出在第i个湖边停留，第一个5分钟可以钓到鱼Fi，以后再每钓5分钟鱼，鱼量减少Di。为了简化问题，佳佳假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请设计一个算法求出佳佳能钓到最多鱼的方案。3、【罗密欧与朱丽叶的迷宫问题】8罗密欧与朱丽叶身处一个m×n的迷宫中，如下图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。【分支限界法】