下载文档原格式
算法分析与设计试卷及参考答案济南⼤学继续教育学院算法分析与设计试卷（A）学年：学期:年级：专业：学习形式：层次：（本试题满分100分，时间90分钟）⼀、单选题（每⼩题2分，共计20分。
）1. 下列情况不适合使⽤计数排序的是（）。
A 要排序的数据表的数量很⼤B 要排序的数据表中有相同的关键字C 要排序的数据表基本有序D 要排序的数据表元素各不相同2. 集合｛Ａ，Ｂ｝的幂集合为（）。
Ａ．｛Ａ｝，｛Ｂ｝Ｂ．｛Ａ｝，｛Ｂ｝，ΦC． { ｛Ａ｝，｛Ｂ｝} D {｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}3．下列字符串序列不符合字典排序的是（）。
A． abc acb bca B. abc acb cbaC． bac bca abc D abc bac bca4．对于根树，出度为零的节点为（）。
Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分⽀节点5．对完全⼆叉树⾃顶向下，从左向右给节点编号，节点编号为１0的⽗节点编号为（）。
Ａ０Ｂ２Ｃ４Ｄ６6．下列程序段的算法时间的复杂度为（）。
for i ←0 to n dofor j ←0 to m do s //某种基本操作A O（n2）B O(m2)C (m+n)D O(m*n)7.三个盘⼦的汉诺塔，⾄少要执⾏移动操作的次数为 ( )。
A 1次B 3次C 6次D 7次8．与算法英⽂单词algorithm具有相同来源的单词是（）。
A logarithmB algirosC arithmosD algebra9．从排序过程是否完全在内存中显⽰，排序问题可以分为（）。
Ａ稳定排序与不稳定排序Ｂ内排序与外排序Ｃ直接排序与间接排序Ｄ主排序与辅助排序10．下列（）不是衡量算法的标准。
Ａ时间效率Ｂ空间效率Ｃ问题难度Ｄ适应能⼒⼆、简答题（每题8分，共计24分。
）1．贪婪技术的基本思想是什么？它有哪些应⽤（给出2种）？2. 拓扑排序的基本思想是什么？它可⽤于哪些实际问题中（给出2种）？3．是么是算法，算法与程序有什么区别？三、算法设计题（每题14分，共计56分。
《算法分析与设计》期末试题及参考答案《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<="">7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
华南农业大学期末考试试卷（A卷）2006学年第二学期考试科目：算法分析与设计考试类型：（开卷）考试时间：120分钟学号姓名年级专业一、选择题（30分，每题2分）1、一个算法应该包含如下几条性质，除了。
（A）有限性（B）二义性（C）正确性（D）可终止性2、我们常用算法的最坏运行时间来估计算法的时间复杂度，下面不是这样做的原因：（A）在实际问题中，算法的运行时间常常达到这个上界（B）平均运行时间难以计算（C）假设每一个输入具有相同的概率有时没有意义（D）平均运行时间与最坏运行时间有相同的数量级3、当输入规模为n时，算法增长率最小的是。
（A）12n （B）100log2n （C）2n2（D）3nlog3n4、void hanoi(int n, int a, int b, int c){if (n > 0){hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);}}上述算法的时间复杂度为A．O （2n） B．O （nlog n）C．Θ（n！）D．Θ（n n）5、对于下列各组f（n）和g（n），下面答案不满足f（n）= O（g（n））（A）f（n）= log n2 g（n）= log n + 5（B）f（n）= log n n g（n）= n（C）f（n）= n！g（n）= n n（D）f（n）= log n g（n）= n6、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面答案解释最合理。
（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。
但不同方法，算法复杂度上界可能不同7、将一个正整数n表示成一系列正整数之和，n = n1 + n2 + …+n k（其中，n1≥n2≥…≥n k≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。
华南农业大学期末考试试卷（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 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是 。 A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是 。 A．（4k – 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面 答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 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个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水 D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A．问题规模相同，问题性质相同 B．问题规模相同，问题性质不同 C．问题规模不同，问题性质相同 D．问题规模不同，问题性质不同 9.对布线问题，以下 是不正确描述。 A．布线问题的解空间是一个图 B．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D．采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件 10.对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A．n! B．2n C．2n+1-1 D．niin1!/! 答案：DACAD CACCB 二、填空题（10分，每题2分）
1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间 复杂性和空间复杂性之分。 2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同 。 3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn ）。 4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： 解得此递归方可得T(n)= O（ nlogn ）。
5、动态规划算法有一个变形方法 备忘录方法 。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。
参考解答：1、时间 2、相同 3、1 logn 4、lognn 5、备忘录方法 三、简答题（40分，每题8分） 1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）： 参考解答：3210loglog23!nnnnnnnnnppppppp 2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他选手各赛一次； （2）每个选手一天只能赛一次； （3）循环赛一共进行n – 1天。 请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。 参考解答： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 3、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，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 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分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为： 其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，
ip为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为： A1 A2 A3 A4 5010 1040 4030 305 p 0 p 1 p 1 p 2 p 2 p 3 p 3 p 4 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。 参考解答： 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，为最大值。
四、算法设计题（30分，前三题每题8分，最后一题6分） 1、【最优服务次序问题】（8分）—— 提示：此题可采用贪心算法实现 问题描述：设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，1<=i<=n。应该如何安排n个顾客的服务次序才能使平均等待时间达到最小？（平均等待时间是n个顾客等待服务时间的总和除以n）。 参考解答：贪心策略：最短服务时间优先。 将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个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。 评分准则： 1)答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出1位的格雷码如何处理），本题即可得满分；
