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

算法设计与分析课程期末试卷A卷自测华北农业年夜教期终测验试卷（A卷）2008教年第一教期测验科目：算法剖析取计划测验范例：（闭卷）测验光阴：120 分钟教号姓名年级业余一、取舍题（20分，每一题2分）1.下述抒发没有准确的是A．n2/2 + 2n的渐进抒发式上界函数是O(2n)B．n2/2 + 2n的渐进抒发式下界函数是Ω(2n)C．logn3的渐进抒发式上界函数是O(logn)D．logn3的渐进抒发式下界函数是Ω(n3)2.当输出范围为n时，算法删少率最年夜的是A．5n B．20log2n C．2n2 D．3nlog3n（n）暗示当输出范围为n时的算法效力，下列算法效力最劣的是A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n4.正在棋盘掩盖成绩中，对于于2k×2k的特别棋盘（有一个特别圆块），所需的L型骨牌的个数是A．（4k– 1）/3 B．2k /3 C．4k D．2k5.正在觅寻n个元素中第k小元素成绩中，若利用倏地排序算法头脑，使用分治算法对于n个元素举行分别，应怎样取舍分别基准上面问案注释最开理。

A．随机取舍一个元素做为分别基准B．与子序列的第一个元素做为分别基准C．用中位数的中位数圆法觅寻分别基准D．以上皆可止但没有同圆法，算法庞大度上界大概没有同6.有9个村落庄，其坐标地位以下表所示：如今要盖一所邮局为那9个村落庄办事，叨教邮局应当盖正在才干使到邮局到那9个村落庄的总间隔以及最短A．（，0）B．（，）C．（5，5）D．（5，0）团体拎着火桶正在一个火龙头后面列队挨火，火桶有年夜有小，火桶必需挨谦火，火流恒定以下道法没有准确A．让火桶年夜的人先挨火，能够使患上每一团体列队光阴之以及最小B．让火桶小的人先挨火，能够使患上每一团体列队光阴之以及最小C．让火桶小的人先挨火，正在某个断定的光阴t内，能够让尽量多的人挨下水D．若要正在尽量短的光阴内，n团体皆挨完火，依照甚么逆序实在皆同样8.分治法的计划头脑是将一个易以曲接办理的年夜成绩宰割陈规模较小的子成绩，分手办理子成绩，最初将子成绩的解搭配起去构成本成绩的解那请求本成绩以及子成绩A．成绩范围不异，成绩性子不异 B．成绩范围不异，成绩性子没有同C．成绩范围没有同，成绩性子不异 D．成绩范围没有同，成绩性子没有同9.对于布线成绩，下列是没有准确形容。

A．布线成绩的解空间是一个图B．能够对于圆格阵列4周配置围墙，即删设标志的附减圆格的预处置，使患上算法简化对于界限的判断C ．接纳广度劣先的标号法寻到从出发点到末面的布线圆案（那个圆案假如存正在的话）没有必定是最短的D ．接纳先进先出的行列做为死结面表，以末面b 为扩大结面或者死结面行列为空做为算法停止前提10.对于于露有n 个元素的子散树成绩，最坏情形下其解空间的叶结面数量为 A ．n!B ．2nC ．2n+1-1 D ．∑=n i i n 1!/! 问案：DACAD CACCB2、挖空题（10分，每一题2分）1、一个算法庞大性的下低表现正在盘算机运转该算法所需的光阴以及存储器资本上，果此算法的庞大性有 光阴 庞大性以及空间庞大性之分2、出自于“仄衡子成绩”的头脑，一般分治法正在宰割本成绩，构成多少子成绩时，那些子成绩的范围皆年夜致 不异 3、利用2分搜刮算法正在n 个有序元素表中搜刮一个特定元素，正在最佳情形下，搜刮的光阴庞大性为O （ 1 ），正在最坏情形下，搜刮的光阴庞大性为O （ logn ）4、已经知一个分治算法泯灭的盘算光阴T(n)，T(n)谦足以下递回圆程： 解患上此递回圆可患上T(n)= O （ nlogn ）。

5、动静布局算法有一个变形圆法 备记录圆法 那种圆法没有同于动静布局算法“自底背上”的挖充圆背，而是“自顶背下”的递回圆背，为每一个解过的子成绩创建了备记录以备必要时检察，一样也可躲免不异子成绩的反复供解参考解问：1、光阴 2、不异 3、1 logn 4、log n n 5、备记录圆法3、简问题（40分，每一题8分）1、（8分）写出以下庞大性函数的偏偏序闭系（即依照渐进阶从低到下排序）：参考解问：3210log log 23!n n n n n n n n n2、（8分）如今有8位活动员要举行网球轮回赛，要计划一个谦足下列请求的竞赛日程表：（1）每一个选脚必需取其余选脚各赛一次；（2）每一个选脚一天只能赛一次；（3）轮回赛一共举行n – 1天请使用分治法的头脑，给那8位活动员计划一个开理的竞赛日程参考解问：3、（8分）某体育馆有一羽毛球场出租，如今统共有10位客户请求租用此羽毛球场，每一个客户所租用的光阴单位以下表所示，s(i)暗示入手下手租历时刻，f(i)暗示停止租历时刻，10个客户的请求以下表所示：统一时候，该羽毛球场只能租借给一名客户，请计划一个租用安顿圆案，正在那10位客户内里，使患上体育馆能尽量谦足多位客户的需要，并算出针对于上表的10个客户请求，至多能够安顿多少位客户申请。

参考解问：将那10位客户的请求依照停止光阴f(i)递删排序，以下表：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分）对于于矩阵连乘所需至少数乘次数成绩，其递回闭系式为： 个中m[i ，j]为盘算矩阵连乘Ai …Aj 所需的至少数乘次数，p i-1为矩阵Ai 的止，i p 为矩阵Ai 的列现有4个矩阵，个中各矩阵维数分手为：请依据以上的递回闭系，盘算出矩阵连乘积A 1A 2A 3A 4所必要的至少数乘次数参考解问：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的3个物品放进背包，患上到的代价以及为15 + 8 + 6 + 4 = 33，为最年夜值4、算法计划题（30分，前3题每一题8分，最初一题6分）1、【最劣办事序次成绩】（8分）——提醒：此题可接纳贪婪算法真现成绩形容：设有n个瞅客同时守候一项办事，瞅客i必要的办事光阴为ti，1参考解问：贪婪战略：最短办事光阴劣先将n个瞅客的办事光阴ti依照由小到年夜排序，n个瞅客的办事调剂圆案即为排序后的逆序，便可使患上仄均守候光阴最小评分原则：1)问到利用贪婪算法，而且道明贪婪的战略是短办事劣先，本题便可患上谦分；2)仅道明利用贪婪算法，但已道明贪婪战略，问题没有完全，扣2分以上；3)别的情形酌情思索2、【Gray码机关成绩】（8分）——提醒：此题可接纳分治递回算法真现成绩形容：“格雷码”是一个少度为n2的序列，谦足：（a）每一个元素皆是少度为n比特的串（b）序列中无不异元素（c）一连的两个元素刚好只要1个比特没有同比方：n=2时，格雷码为{00，01，11，10}Gray码是一种编码，那种编码能够躲免正在读与时，果各数据位时序上的好同制成的误读格雷码正在工程上有宽泛使用。

但格雷码没有便于运算，请您计划一种机关圆法，输出少度序列n，输入格雷码（您只有做出一种机关圆案便可，格雷码其实不仅有）参考解问：此题可用分治法办理当n＝1时，输入格雷码{0, 1}当n>1时，格雷码的少度为n2，即共有n2个码序列此时，将成绩一分为2，即上半全体以及下半全体上半全体最下位设为0，下半全体最下位设为1剩下n-1位的格雷码的机关接纳递回的思绪评分原则：1)问到利用分治算法，而且推导出分治算法的历程，界限设定浑晰（即当仅输入1位的格雷码怎样处置），本题便可患上谦分；2)道明利用分治算法，但漏界限前提，扣2分以上；3)别的情形酌情思索3、【最少回升子序列成绩】（8分）——提醒：此题可接纳动静布局算法真现对于于给定的一个序列12(,,,)N a a a ，11000N ≤≤咱们能够患上到一些递删回升的子序列12(,,,)i i iK a a a ，那里121K i i i N ≤8)您的义务：便是对于于给定的序列，供出最少回升子序列的少度请求写出您计划的算法头脑及递推函数的公式抒发参考解问：设()f i 暗示：从左背左扫描过去曲到以[]a i 元素开头的序列，取得的最少回升子序列的少度，且子序列包孕[]a i 元素（1i n ≤≤）。

即，()f i 是从(1)f ，(2)f ……到(1)f i -中寻最年夜的一个值，再减1或者者便是1次要是瞧a[i]那个元素可否减进到以前已经经取得的最少回升子序列，假如能减进，是以前已经取得的最少回升子序列少度减一；假如没有能减进，便与那最初一个元素做为一个独自子序列，少度为1最初，所请求的全部序列的最少大众子序列少度为max{f(i): 1比方，对于于序列：4 2 6 3 1 5 2评分原则：1)问到利用动静布局算法，而且推导出动静布局算法的递推函数公式抒发，界限设定浑晰，本题便可患上谦分；（阅卷时子细瞧递推公式抒发，公式抒发露义准确便可，果其抒发情势大概没有仅有）2)道明利用动静布局算法，但对于递推函数抒发同伴或者露糊，扣2分以上；3)别的情形酌情思索4、【骑士成绩】（6分）——提醒：此题可接纳广度劣先搜刮算法真现正在一个尺度8×8的国内象棋棋盘上，棋盘中有些格子是大概有停滞物的已经知骑士的初初地位以及宗旨地位，您的义务是盘算出骑士至少必要几步能够从初初地位抵达宗旨地位，若无奈抵达宗旨地位，输入“not reachable”请用笔墨或者真代码道明您的算法注重：骑士只能举行“日”字止对于角跳，棋盘上有停滞物的格子没有能抵达。

图（a）：骑士能举行的“日”字止对于角跳，n为骑士以后地位，x为骑士下一步能够跳到的格子图（b）：骑士从初初地位n到宗旨地位N，最小必要7步的真例b为棋盘停滞参考解问：那也是一个搜刮的标题，十分相似于书上的“布线成绩”，可参考书上此例用一个2维数组board[12][12]去纪录棋盘的情况为什么年夜小是12*12呢棋盘年夜小8*8，为了加少对于四周界限的判别，正在高低摆布4边各减上2止2列做“围墙”（停滞），果此board棋盘的年夜小12*12有以下多少个步调必要办理：1)停滞格子：将输出的停滞格子挖写到board之中对于应格上，设置为-1；2)肇始格子以及停止格子：将肇始面start以及停止面end，那两个面纪录上去，正在board中那两个格子配置为0；3)围墙：正在8*8的棋盘中里，高低摆布各减2止2列做围墙，围墙以及停滞同样，配置为-1；4)除了停滞围墙肇始停止格子那些格子特别对于待输出以外，其他格子齐部初初化为0；5)行列初初为空行列是用去正在骑。