算法设计与分析课程期末试卷A卷自测.docx

《算法设计与分析课程期末试卷A卷自测.docx》由会员分享，可在线阅读，更多相关《算法设计与分析课程期末试卷A卷自测.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析课程期末试卷A潮测The document was prepared on January 2, 2021华南农业大学期末考试试卷(A卷)2008学年第一学期考试科目：算法分析与设计考试类型：(闭卷)考试时间：120分钟学号 姓名 年级专业题号四总分得分评阅人一、选择题(20分，每题2分).下述表达不正确的是OA . 1?/2+ 211的渐进表达式上界函数是0(2，B . nZ/2 + 211的渐进表达式下界函数是。(2C . logi?的渐进表达式上界函数是O(logn)D . logrr3的渐进表达式下界函数是Q(n3)1 .当输入规模为n时，算法增长率最大的是。A . 5n

2、 B . 201og2nC . 2n2 D . 3nlog3n(n)表示当输入规模为n时的算法效率，以下算法效率最优的是oA . T (n) =T (n - 1) +1, T =1B . T (n) = 2n2C . T (n) =T (n/2) +1, T (1) =1 D . T (n) = 3nlog2n.在棋盘覆盖问题中，对于2kx2k的特殊棋盘(有一个特殊方块),所需的L型骨牌的 个数是一。A . (4k- 1) /3 B . 2k/34 .在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准下面答案解释最合理。A.随机选择一个

3、元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D ,以上皆可行。但不同方法，算法复杂度上界可能不同5 .有9个村庄，其坐标位置如下表所示：123456789X (1)123456789y123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村 庄的总距离和最短。A. (.0)B . (, ) C . (5, 5) D . (5, 0)个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒 定。如下说法不正确A,让水桶大的人先打水，可以使得每个人排队时间之和最小.让水桶小的人先打水，可以使得每个人排队

4、时间之和最小C.让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D.若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样8分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解 决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问 题OA .问题规模相同，问题性质相同B .问题规模相同，问题性质不同C .问题规模不同，问题性质相同D .问题规模不同，问题性质不同.对布线问题，以下是不正确描述。A.布线问题的解空间是一个图B .可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对 边界的判定C.采用广度优先的标号

5、法找到从起点到终点的布线方案(这个方案如果存在的话)不 一定是最短的D.采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算 法结束条件8 .对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为oA . n! B , 2n C . 2n+1-lD . !！Z=1答案：DACAD CACCB二、填空题(10分，每题2分)1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此 算法的复杂性有时间复杂性和空间复杂性之分。2、出自于平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这 些子问题的规模都大致相同。3、使用二分搜索算法在n个有

6、序元素表中搜索一个特定元素，在最佳情况下，搜索的 时间复杂性为O (_),在最坏情况下，搜索的时间复杂性为O ( logn )。4、已知一个分治算法耗费的计算时间T(n), T(n)满足如下递归方程：解得此递归方可得T(n)= O ( nlogn )。5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向 上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以 备需要时查看，同样也可避免相同子问题的重复求解。参考解答：1、时间2、相同3、1 logn 4、n log az 5S备忘录方法三、简答题（40分，每题8分）1、 （8分）写出下列复杂性函数的

7、偏序关系（即按照渐进阶从低到高排序）：参考解答：IO, Ylog Ylog几 Yn2 y2 y3 y！2、 （8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日 程表：（1）每个选手必须与其他选手各赛一次；每个选手一天只能赛一次； 循环赛一共进行n-1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543213、 （8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场, 每个客户所租用的时间单元如下表所示，s表示开始

8、租用时刻，f（i）表示结束租用时 刻，1。个客户的申请如下表所示：112345678910s(i)03153511886f(i)65498713121110同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。参考解答：将这10位客户的申请按照结束时间千(i)递增排序，如下表：112345678910s(i )13053568811f (i )456789101112131)选择申请1 (1,4)2)依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到

9、所 有申请检查完毕。申请4 (5,7)、申请8 (8,11)、申请10 (11,13)3)最后，可以满足：申请1 (1,4)、申请4 (5,7)、申请8 (8,11)、申请10(11,13)共4个客户申请。这已经是可以满足的最大客户人数。4、 (8分)对于矩阵连乘所需最少数乘次数问题，其递归关系式为：其中mi, j为计算矩阵连乘AiAj所需的最少数乘次数，pi为矩阵Ai的行，p,为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：AiAzA3A4501010404030305PoPiPl P2P2P3P3P4请根据以上的递归关系，计算出矩阵连乘积AiA2A3A4所需要的最少数乘次数0参考解答：

10、5、 (8分)有这样一类特殊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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少参考解答：因为该0 1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先 取重量轻的物品放进背包。最终可以把重量分别为2, 3, 4, 5的三个物品放进背包， 得到的价值和为15 + 8 + 6 + 4=33,为最大值。、算法

11、设计题（30分，前三题每题8分，最后一题6分）1、【最优服务次序问题】（8分）提示：此题可采用贪心算法实现问题描述：设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti,l=il时，格雷码的长度为2,即共有2个码序列。此时，将问题一分为 二，即上半部分和下半部分。上半部分最高位设为0,下半部分最高位设为lo剩下n-1位的格雷码的构造采用递归的思路。评分准则:1）答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出1位的格雷码如何处理），本题即可得满分；2）说明使用分治算法，但漏边界条件，扣2分以上；3）其它情况酌情考虑。3、【最长上升子序列问题】（8分）提示：此题可采用动态

12、规划算法实现对于给定的一个序列（卬,生，n），1KNK1000。我们可以得到一些递增上升的子序列 （%,卬2，,。火），这里,& WN。比如，对于序歹11（1,7,3,5,9,4,8）,有它的一些上 升子序列，如（1,7）, （3, 4, 8）等等。这些子序列中最长的长度是4,比如子序列（1,3, 5, 8）。你的任 务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的 公式表达。参考解答：设/表示：从左向右扫描过来直到以Q0元素结尾的序列，获得的最 长上升子序列的长度，且子序列包含田元素o即，/是从/，/（2）到/。-1）中找最大的一个值，再加1。或者就是1

13、。 主要是看ai这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是 之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个 单独子序列，长度为1。最后,所要求的整个序列的最长公共子序列长度为maxf （i） : 1=i=n 例如，对于序列：4 2 6 3 1 5 2 11234567array4263152f(i)1122132评分准则：1）答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界 设定清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正 确即可，因其表达形式可能不唯一）2）说明使用动态规划算法，但对递推函数表达错误或含

14、糊，扣2分以上；3）其它情况酌情考虑。4、【骑士问题】（6分）提示:此题可采用广度优先搜索算法实现在一个标准8x8的国际象棋棋盘上，棋盘中有些格子是可能有障碍物的。已知骑士的初始位置 和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置，若无法到达目 标位置，输出notreachable o请用文字或伪代码说明你的算法。注意：骑士只能进行“日”字行对角跳，棋盘上有障碍物的格子不能到达。图（a）:骑士能进行的“日”字行对角跳，n为骑士当前位置，x为骑士下一步可以跳到的格子图（b）:骑士从初始位置n到目标位置N,最小需要7步的实例。b为棋盘障碍参考解答：这也是一个搜索的题目，非

15、常类似于书上的“布线问题”，可参考书 上此例。用一个二维数组board12 12来记录棋盘的状况。为何大小是12*12呢棋盘大小8*8,为了减少对周围边界的判断，在上下左右四边 各加上2行2列做“围墙”（障碍），因此board棋盘的大小12*12。有如下几个步骤需要解决：1）障碍格子：将输入的障碍格子填写到board当中对应格上，设置为7;2）起始格子和结束格子：将起始点start和结束点end,这两个点记录下来，在 board中这两个格子设置为0;3）围墙：在8*8的棋盘外面，上下左右各加2行2列做围墙，围墙和障碍一样，设 置为-1 ;4）除障碍围墙起始结束格子这些格子特殊对待输入之外，其余

16、格子全部初始化为0;5）队列初始为空。队列是用来在骑士做日字型对角跳的时候，候选位置放入 队列中的一个辅助的数据结构，以便于“广度优先搜索”。6）从起点开始，将这个位置所能跳的周围8个位置都检查一下：只要未标记，就标 记为前一个位置值加1,并将该格子位置加入队列；如果不能标记（比如障碍 或围墙等），就跳过，继续检查下一个位置，一共骑士所能跳的8个位置。7）取出队列首个位置结点，又继续检查这个结点周围的8个位置，类同上一步，直 到找到对终点标记位置。8）最后，输出终点所标记的数值（正数），就是骑士所需的最少移动步数，若为0 表示终点无法标记到，输出：“not reachabIen这样的信息。评分准则：1）答到使用搜索算法，并且说明采用广度优先的搜索策略，算法描述清晰准确， 本题即可得满分；2）算法表达含糊或不准确，扣2分以上；3）其它情况酌情考虑。