2022年2021.1算法设计与分析课程期末试卷-A卷 .pdf

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

1、1 华南农业大学期末考试试卷（A 卷）2008学年第一学期考试科目：算法分析与设计考试类型：（闭卷）考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人一、选择题（ 20 分，每题 2 分）1.下述表达不正确的是。An2/2 + 2n的渐进表达式上界函数是O(2n) Bn2/2 + 2n的渐进表达式下界函数是(2n) Clogn3的渐进表达式上界函数是O(logn) Dlogn3的渐进表达式下界函数是(n3) 2.当输入规模为n 时，算法增长率最大的是。A5nB20log2nC2n2D3nlog3n3.T（n）表示当输入规模为n 时的算法效率，以下算法效率最优的是。AT（n）= T（

2、 n 1）+1，T（1）=1 BT（n）= 2n2CT（n）= T（n/2）+1，T（1）=1 DT（n）= 3nlog2n4.在棋盘覆盖问题中，对于2k 2k的特殊棋盘（有一个特殊方块），所需的L 型骨牌的个数是。A （4k 1） /3 B 2k /3 C4kD2k5.在寻找 n 个元素中第k 小元素问题中，若使用快速排序算法思想，运用分治算法对 n 个元素进行划分，应如何选择划分基准？下面答案解释最合理。A随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C用中位数的中位数方法寻找划分基准D以上皆可行。但不同方法，算法复杂度上界可能不同名师归纳总结 精品学习资料 - - - -

3、 - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 2 6.有 9 个村庄，其坐标位置如下表所示：i 1 2 3 4 5 6 7 8 9 x（i）1 2 3 4 5 6 7 8 9 y（i）1 2 3 4 5 6 7 8 9 现在要盖一所邮局为这9 个村庄服务，请问邮局应该盖在才能使到邮局到这9 个村庄的总距离和最短。A （4.5，0）B （4.5，4.5）C （5，5）D （5，0）7.n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满

4、水，水流恒定。如下说法不正确？A让水桶大的人先打水，可以使得每个人排队时间之和最小B让水桶小的人先打水，可以使得每个人排队时间之和最小C让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水D若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。A问题规模相同，问题性质相同B问题规模相同，问题性质不同C问题规模不同，问题性质相同D问题规模不同，问题性质不同9.对布线问题，以下是不正确描述。A布线问题的解空间是一个图B可以对

5、方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的D采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件10.对于含有n 个元素的子集树问题， 最坏情况下其解空间的叶结点数目为。An! B2nC2n+1-1 Dniin1!/ !答案： DACAD CACCB 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 9 页

6、 - - - - - - - - - 3 二、填空题（ 10 分，每题 2 分）1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n 个有序元素表中搜索一个特定元素，在最佳情况下， 搜索的时间复杂性为O（1） ，在最坏情况下，搜索的时间复杂性为O（logn） 。4、已知一个分治算法耗费的计算时间T(n)， T(n)满足如下递归方程：22221nnOnTnOnT)()/()()(解得此递归方可得T(n)=

7、O（ nlogn） 。5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。参考解答： 1、时间 2 、相同 3 、1 logn 4、lognn5、备忘录方法三、简答题（ 40 分，每题 8 分）1、 （ 8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：2323log!log10nnnnnnnnn参考解答：3210loglog23!nnnnnnnnn2、 （ 8 分）现在有8 位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程

8、表：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 4 （1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n 1 天。请利用分治法的思想，给这8 位运动员设计一个合理的比赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543213、 （ 8分）某体育馆有一羽毛球场出租，现在总共有10 位

9、客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i) 表示结束租用时刻， 10 个客户的申请如下表所示：i 1 2 3 4 5 6 7 8 9 10 s(i) 0 3 1 5 3 5 11 8 8 6 f(i) 6 5 4 9 8 7 13 12 11 10 同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面， 使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10 个客户申请，最多可以安排几位客户申请。参考解答： 将这 10 位客户的申请按照结束时间f(i)递增排序，如下表：i 1 2 3 4 5 6 7 8 9

10、10 s(i) 1 3 0 5 3 5 6 8 8 11 f(i) 4 5 6 7 8 9 10 11 12 13 1） 选择申请1（1,4 ）2） 依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申请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分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：名师归纳总结 精品学习资料 - - - - -

11、- - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 5 1ikj0 , min , 1, ikjijm i jm i km kjpp pij其中 mi， j为计算矩阵连乘Ai Aj 所需的最少数乘次数，pi-1为矩阵 Ai 的行，ip为矩阵 Ai 的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A450 1010 4040 3030 5p 0 p 1 p 1 p 2p 2 p 3p 3 p 4请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最

12、少数乘次数。参考解答：01402403411240800050 10 51050014min123420000600050 40 536000134427000050 30 53450010500mmp p pmmmp p pmmp p p5、 （ 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 背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值

13、多少？参考解答： 因为该01 背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3， 4，5 的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。四、算法设计题（ 30分，前三题每题8 分，最后一题 6 分）1、 【最优服务次序问题】 （8 分） 提示：此题可采用贪心算法实现问题描述：设有 n 个顾客同时等待一项服务，顾客 i 需要的服务时间为ti， 1=i1 时，格雷码的长度为n2，即共有n2个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下 n-1 位的格

14、雷码的构造采用递归的思路。评分准则：1)答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出 1 位的格雷码如何处理） ，本题即可得满分；2)说明使用分治算法，但漏边界条件，扣2 分以上；3)其它情况酌情考虑。3、 【最长上升子序列问题】（8 分） 提示：此题可采用动态规划算法实现对于给定的一个序列12(,)Na aa，11000N。我们可以得到一些递增上升的子序列12(,)iiiKaaa， 这里121KiiiN。比如，对于序列 (1, 7, 3, 5, 9, 4, 8)， 有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，名师归纳总结

15、 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 7 比如子序列 (1, 3, 5, 8)。你的任务： 就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。参考解答： 设( )f i表示：从左向右扫描过来直到以 a i元素结尾的序列，获得的最长上升子序列的长度，且子序列包含 a i元素（1in） 。11( )max( )1: ;1111;(1) if ifja ia jjiiijjia

16、 ia j当, 都有即，( )f i是从(1)f，(2)f到(1)f i中找最大的一个值，再加1。或者就是 1。主要是看ai这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。最后，所要求的整个序列的最长公共子序列长度为maxf(i): 1=i=n 例如，对于序列：4 2 6 3 1 5 2i 1 2 3 4 5 67 array 4 2 6 3 1 5 2 f(i) 1 1 2 2 1 3 2 评分准则：1)答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设定清晰，

17、 本题即可得满分； （阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一）2)说明使用动态规划算法，但对递推函数表达错误或含糊，扣2 分以上；3)其它情况酌情考虑。4、 【骑士问题 】 （6 分） 提示：此题可采用广度优先搜索算法实现在一个标准8 8 的国际象棋棋盘上，棋盘中有些格子是可能有障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置，若无法到达目标位置，输出“not reachable”。请用文字或伪代码说明你的算法。注意：骑士只能进行“日”字行对角跳，棋盘上有障碍物的格子不能到达。名师归纳总结 精品学习资料 - -

18、 - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 8 图（ a） ：骑士能进行的“日”字行对角跳，n 为骑士当前位置，x 为骑士下一步可以跳到的格子图（ b） ：骑士从初始位置n 到目标位置N，最小需要7 步的实例。 b 为棋盘障碍参考解答： 这也是一个搜索的题目，非常类似于书上的“布线问题”，可参考书上此例。用一个二维数组board1212来记录棋盘的状况。为何大小是12*12 呢？棋盘大小8*8 ，为了减少对周围边界的判断，在上下左右四边各加

19、上2 行 2 列做“围墙” （障碍），因此 board 棋盘的大小12*12。有如下几个步骤需要解决：1)障碍格子：将输入的障碍格子填写到board 当中对应格上，设置为-1 ；2)起始格子和结束格子：将起始点start和结束点end，这两个点记录下来，在 board 中这两个格子设置为0；3)围墙： 在 8*8 的棋盘外面， 上下左右各加2 行 2 列做围墙， 围墙和障碍一样，设置为 -1 ；名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 9 页 -

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