下载文档原格式
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。
7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。
14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束一般指什么？18.阐述归并排序的分治思路。
19.快速排序的基本思想是什么。
20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。
二、复杂性分析1、MERGESORT(low，high)if low<high；then mid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、procedure S1(P，W，M，X，n)i←1; a←0while i≤ n doif W(i)>M then return endifa←a+ii←i+1 ;repeatend3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v←A(m);i←mlooploop i←i+1 until A(i) ≥v repeatloop p←p-1 until A(p) ≤v repeatif i<pthen call INTERCHANGE(A(i),A(p))else exitendifrepeatA(m) ←A(p);A(p) ←vEnd PARTITION4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1))endifend F1procedure F2(i,n,x,y)if i≤nthen call F2(i+1,n,y,x+y)endifreturn(y)end F25.procedure MAX(A,n,j)xmax←A(1);j←1for i←2 to n doif A(i)>xmax then xmax←A(i); j←i;endif repeatend MAX6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low←1;high←nwhile low≤high domid←|_(low+high)/2_|case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j ←mid; returnendcase repeat j ←0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
算法设计与分析期末试卷A卷A卷一、选择题1.二分搜索算法是利用（A）实现的算法。
A、分治策略2.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树3.下列算法中通常以自底向上的方式求解最优解的是（B）。
B、动态规划法4．下面不是分支界限法搜索方式的是（D）。
D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(。
B。
)。
B、O（nlogn）6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
B、最大堆7、下面问题（B）不能使用贪心法解决。
B N皇后问题8.下列算法中不能解决0/1背包问题的是（A）A贪心法9.背包问题的贪心算法所需的计算时间为（B）A、O （nlogn）B、O（nlogn）10.背包问题的贪心算法所需的计算时间为（B）。
B、O（nlogn）二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有穷性四条性质。
其中算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是回溯法，需要排序的是动态规划和分支限界法。
4.动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
5.回溯法是一种既带有深度优先搜索又带有回溯的搜索算法；分支限界法是一种既带有广度优先搜索又带有回溯的搜索算法。
6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时O(n)。
Bool Color::OK(int k)for(int j=1;j<=n;j++)if((a[k][j] == 1) && (x[j] == x[k])) {return false;return true;8.用回溯法解布线问题时，求最优解的主要程序段如下。
如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n>= N1，f （n）<=C1s(n)；对所有的n>= N2,g(n) <=C2r(n)所以 f（n）+ g(n) <= C1s(n)+ C2r(n)，f（n）*g(n)<= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))f（n）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。
当数据集的规模（即n的取值）很大时，要在现代计算机上运行具有比O（nlog2 n）复杂度还高的算法是很困难的，尤其是指数时间算法，它只有在在n值取得非常小的时候才实用。
例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n^2和nlogn.则N=1024，分别需要1048576和10240次运算。
N=2048：分别需要4194304和22528次运算。
由此，在n加倍的情况下，一个O（n^2)的算法计算时间增长4倍，而一个O（nlogn）算法则只用两倍多一点的时间。
所以数量级的大小对算法的有效性有决定性的影响。
尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000倍的提速即可瞬间化为乌有。
算法设计与分析复习题目及答案.docx一。
选择题1、二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（B）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（B）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（B）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1 背包问题9. 实现循环赛日程表利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（ C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（DA、广度优先B、最小耗费优先C、最大效益优先12．下列算法常以深度优先方式系统搜索问题解的是（A、备忘录法B、动态规划法C、贪心法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法14．哈弗曼编码的贪心算法所需的计算时间为（BnB、 O（nlogn ）n ）A、O（ n2 ）C、O（215．分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B、最大堆C、栈组）。
D、深度优先D）。
D、回溯法D、回溯法）。
D、 O（ n）B）。
D 、数16．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。
北京工业大学2014 ——2015 学年第二学期算法设计与分析期末考试模拟试卷 A卷考试说明：承诺：本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。
若有违反，愿接受相应的处分。
承诺人：学号：班号：。
注：本试卷共三大题，共 6 页，满分100分，考试时答案请写在试卷空白处。
一、算法时间复杂性问题（共30分）Part 1. The Time Complexity Of the Algorithm Test1、试证明下面的定理：[12分](1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n))(2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks](1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n))(2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n))2、已知有如下的断言：f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n)) 请你举出一个反例。
[8分]2. Known as the following assertionIf f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。
Please cite a counter-example [8 marks]3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。
《算法设计与分析》期末必考复习及答案题整理1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，3、 Prim算法：设G=(V,E)是连通带权图，V={1,2,…,n}。
构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[j]最小的边，将顶点j添加到S 中。
这个过程一直进行到S=V时为止。
4、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。
其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。
这两类函数统称为剪枝函数。
6、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。
5、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。
6、最优子结构性质：该问题的最优解包含着其子问题的最优解。
7、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。
这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
新祥旭高硕网站：
/ 一：填空题
1.数据模型的三要素
2.数据库系统与数据库管理系统的区别
3.码键的两个条件()和() ，R(A,B,C,D)A →B,C →D,CB →A,B →C,所有的键是()
4.选择对应于 SQL 的什么语句
5.R(A,B,C)键码为 AC 或 AB ，该关系最高达()范式，为什么()
6.三级体系结构引出的两层数据独立性是什么()
7.R(U)分解为 R1(U1),R2(U2)，无损连接的条件是
二.大题
1.设计数据库存储每个人的父母和孩子。
给出 ER 模型和数据模型查询王立的父母，用关系代数和 SQL 语句分别给出能否查询祖父母信息。
2.R(A,B,C,D,E,F) F={A →B,AC →D,BE →F,EF →C}，分解成 3NF ，使保持依赖。
3.大学学习数据库有否上机课程，是干什么的，用的哪个 DBMS ，它提供哪些基本工具， 使用是否方便。
你是否使用过编程语言连接数据库，如何连接的。
《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树 二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。
2.简述回溯法解题的主要步骤。
3.简述动态规划算法求解的基本要素。
4.简述回溯法的基本思想。
5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。
6.简要分析分支限界法与回溯法的异同。
7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。
9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。
10.简述分析贪心算法与动态规划算法的异同。
三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。
4.根据分枝限界算法基本过程,求解0-1背包问题。
已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
算法与分析考试题及答案一、选择题（每题2分，共10分）1. 以下哪个选项不是算法的特性？A. 有穷性B. 确定性C. 可行性D. 随机性答案：D2. 在分析算法时间复杂度时，通常使用哪种方法？A. 循环不变式B. 递归树C. 模拟运行D. 动态规划答案：B3. 快速排序算法的平均时间复杂度是？A. O(n)B. O(n log n)C. O(n^2)D. O(2^n)答案：B4. 以下哪个排序算法不是基于比较的排序算法？A. 快速排序B. 归并排序C. 堆排序D. 计数排序答案：D5. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别是什么？A. DFS使用栈，BFS使用队列B. DFS使用队列，BFS使用栈C. DFS和BFS都使用栈D. DFS和BFS都使用队列答案：A二、填空题（每题3分，共15分）1. 算法的时间复杂度通常用大O表示法来描述，其中O表示______。
答案：上界2. 在算法分析中，我们通常忽略常数因子和______。
答案：低阶项3. 动态规划算法的核心思想是______。
答案：分治4. 在图的表示方法中，邻接矩阵适用于表示______图。
答案：稠密5. 哈希表的平均查找时间复杂度是______。
答案：O(1)三、简答题（每题10分，共20分）1. 请简述分治法的基本步骤。
答案：分治法的基本步骤包括分解、解决和合并。
首先将原问题分解成若干个规模较小但结构与原问题相同的子问题；然后递归地解决这些子问题；最后将子问题的解合并成原问题的解。
2. 什么是贪心算法？请举例说明。
答案：贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
例如，活动选择问题，其中可以选择结束时间最早的活动，以最大化可以安排的活动数量。
四、计算题（每题15分，共30分）1. 给定一个序列{3, 7, 2, 5, 8, 4, 6}，请使用快速排序算法对其进行排序，并说明排序过程中的划分操作。
装订线华南农业大学期末考试试卷（A卷） 2012学年第1学期 考试科目：算法设计与分析考试类型：（闭卷）考试 考试时间：120 分钟学号姓名年级专业题号一(20) 二(25) 三(16) 四(24) 五(15) 总分得分评阅人说明：（1）请勿漏填学号姓名等信息。
本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。
请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。
得分一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处）1、化简下面f(n)函数的渐进上界表达式。
（5分）nnnf32/)(21，则____)(_________))((1OnfO322)(nnf，则____)(_________))((2OnfO33log)(nnf ，则____)(_________))((3OnfO2log42)(nnf ，则____)(_________))((4OnfOnnf3log)(5，则____)(_________))((5OnfO参考解答：)3())((1nOnfO ；)2())((2nOnfO ；)(log))((3nOnfO ；)())((24nOnfO ；)())((5nOnfO 。
2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。
（3分）算法1：O( )；算法2：O( )；12算法3：O( )参考解答：算法1：)(2n O ；算法2：)(3n O ；算法3：)(4n O 。
3、假设算法A 的计算时间为n n T 2)( ，现在一慢一快的两台计算机上测试算法A ，为解决规模n 的问题慢机运行算法A 花费t 秒，而另一台快机速度是慢机的256倍，则在快机上算法A 同样运行t 秒能解决n1规模，则n1和n 的关系为：n1= ；若算法B 的计算时间为2)(n n T ，其余条件不变，则n1= 。
1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L 型骨牌；并在棋盘上填写L 型骨牌的覆盖情况。
2． 假设有7个物品，给出重量和价值。
若这些物品均不能被分割，且背包容量M ＝140，使用回溯方法求解此0-1背包问题。
请画出状态空间搜索树。
3． 假设有7个物品，它们的重量和价值如下表所示。
若这些物品均可以被分割，且背包容量M＝140，使用贪心算法求解此背包问题。
请写出求解策略和求解过程。
W （35,30,50,60,40,10,25）p （10,40,30,50,35,40,30）4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a 到b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。
5． 画出字符表的哈夫曼编码对应的二叉树。
6． 已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=8，r 5=5，r 6=20，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。
7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，描述出用优先队列式分支限界法求解时的搜索情况。
表示出优先队列、当前扩展结点等的变化情况。
8． 依据优先队列式分支限界法，求从s 点到t 点的单源最短路径，画出求得最优解的解空间树。
一、假设有7个物品，它们的重量和价值如下表所示。
若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。
请写出状态空间搜索树（20分）。
答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。
将它们的序号分别记为1～7。
则可生产如下的状态空间搜索树。
其中各个节点处的限界函数值通过如下方式求得：【排序1分】5x =6x =7x =17分，每个节点1分】a ．1501154040305035190.62540-++++⨯=7(1,1,1,1,,0,0)8b. 1501154040305030177.560-++++⨯=7(1,1,1,1,0,,0)12c ．4040305010170++++=(1,1,1,1,0,0,1)d. 1501054040303530167.560-++++⨯=3(1,1,1,0,1,,0)4e. 150130404050353017560-++++⨯=1(1,1,0,1,1,,0)3f. 1501304040503510170.7135-++++⨯=4(1,1,0,1,1,0,)7g. 40405030160+++=(1,1,0,1,0,1,0)h. 1501404040353010146.8535-++++⨯=2(1,1,0,0,1,1,)7i.1501254030503530167.560-++++⨯=5(1,0,1,1,1,,0)12 j. 1501454030503530157.560-++++⨯=1(0,1,1,1,1,,0)12在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。
分治法1、二分搜索算法是利用分治策略实现的算法;9. 实现循环赛日程表利用的算法是分治策略27、Strassen矩阵乘法是利用分治策略实现的算法;34．实现合并排序利用的算法是分治策略 ;实现大整数的乘法是利用的算法分治策略 ;17．实现棋盘覆盖算法利用的算法是分治法 ;29、使用分治法求解不需要满足的条件是子问题必须是一样的 ;不可以使用分治法求解的是0/1背包问题 ;动态规划下列不是动态规划算法基本步骤的是构造最优解下列是动态规划算法基本要素的是子问题重叠性质 ;下列算法中通常以自底向上的方式求解最优解的是动态规划法备忘录方法是那种算法的变形; 动态规划法最长公共子序列算法利用的算法是动态规划法 ;矩阵连乘问题的算法可由动态规划算法B设计实现;实现最大子段和利用的算法是动态规划法 ;贪心算法能解决的问题：单源最短路径问题,最小花费生成树问题,背包问题,活动安排问题,不能解决的问题：N皇后问题,0/1背包问题是贪心算法的基本要素的是贪心选择性质和最优子结构性质;回溯法回溯法解旅行售货员问题时的解空间树是排列树 ;剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素确定解空间的时间分支限界法最大效益优先是分支界限法的一搜索方式;分支限界法解最大团问题时,活结点表的组织形式是最大堆 ;分支限界法解旅行售货员问题时,活结点表的组织形式是最小堆优先队列式分支限界法选取扩展结点的原则是结点的优先级在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是分支限界法.从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除栈式分支限界法之外都是最常见的方式.1队列式FIFO分支限界法：按照队列先进先出FIFO原则选取下一个节点为扩展节点;2优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点;最优子结构性质是贪心算法与动态规划算法的共同点;贪心算法与动态规划算法的主要区别是贪心选择性质 ;回溯算法和分支限界法的问题的解空间树不会是无序树.14．哈弗曼编码的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On21、下面关于NP问题说法正确的是BA NP问题都是不可能解决的问题B P类问题包含在NP类问题中C NP完全问题是P类问题的子集D NP类问题包含在P类问题中40、背包问题的贪心算法所需的计算时间为 BA、On2nB、OnlognC、O2nD、On42．0-1背包问题的回溯算法所需的计算时间为 AA、On2nB、OnlognC、O2nD、On.47.背包问题的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序,故算法的时间复杂度为 B ;A、On2nB、OnlognC、O2nD、On56、算法是由若干条指令组成的有穷序列,而且满足以下性质D（1）输入：有0个或多个输入（2）输出：至少有一个输出（3）确定性：指令清晰,无歧义（4）有限性：指令执行次数有限,而且执行时间有限A 123 B124 C134 D 1 23457、函数32n+10nlog n的渐进表达式是 B .A. 2nB. 32nC. nlog nD. 10nlog n59、用动态规划算法解决最大字段和问题,其时间复杂性为B .A.lognB.nC.n2D.nlogn61、设fN,gN是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有fN≤CgN,则称函数fN当N充分大时有下界gN,记作fN∈○gN,即fN的阶 A gN的阶.A.不高于B.不低于C.等价于D.逼近二、填空题2、程序是算法用某种程序设计语言的具体实现;3、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的;6、算法是指解决问题的一种方法或一个过程 ;7、从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法 ;11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步;14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划 ,需要排序的是回溯法 ,分支限界法 ;15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ,只使用约束条件进行裁剪的是 N皇后问题 ;30.回溯法是一种既带有系统性又带有跳跃性的搜索算法;33．回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数 ;34.任何可用计算机求解的问题所需的时间都与其规模有关;35.快速排序算法的性能取决于划分的对称性 ;36. Prim算法利用贪心策略求解最小生成树问题,其时间复杂度是On2;37. 图的m着色问题可用回溯法求解,其解空间树中叶子结点个数是m n,解空间树中每个内结点的孩子数是m ;4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列 {BABCD}或{CABCD}或{CADCD｝;5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个最优解8.0-1背包问题的回溯算法所需的计算时间为__on2n__,用动态规划算法所需的计算时间为___omin{nc,2n}_;二、综合题50分1.写出设计动态规划算法的主要步骤;①问题具有最优子结构性质；②构造最优值的递归关系表达式；3最优值的算法描述；④构造最优解；2.流水作业调度问题的johnson算法的思想;①令N1={i|ai<bi},N2={i|ai>=bi}；②将N1中作业按ai的非减序排序得到N1’,将N 2中作业按bi的非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度;3.若n=4,在机器M1和M2上加工作业i所需的时间分别为ai 和bi,且a 1,a2,a3,a4=4,5,12,10,b1,b2,b3,b4=8,2,15,9求4个作业的最优调度方案,并计算最优值;步骤为：N1={1,3},N2={2,4}；N 1’={1,3}, N2’={4,2}；最优值为：384.使用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间从根出发,左1右0,并画出其解空间树,计算其最优值及最优解;解空间为{0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,1,0,1,1,1};解空间树为：该问题的最优值为：16 最优解为：1,1,05.设S=｛X1,X2,···,Xn｝是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,1在二叉搜索树的内结点中找到X=Xi ,其概率为bi;2在二叉搜索树的叶结点中确定X∈X i ,Xi+1,其概率为ai;在表示S的二叉搜索树T中,设存储元素Xi的结点深度为Ci；叶结点Xi ,Xi+1的结点深度为di,则二叉搜索树T的平均路长p为多少假设二叉搜索树Tij=｛Xi ,Xi+1,···,Xj｝最优值为mij,Wij= ai-1+bi+···+bj+aj,则mij1<=i<=j<=n递归关系表达式为什么二叉树T的平均路长P=∑=+ni1Ci)(1*bi+∑=nj0dj*aj{mij=0 i>j6.描述0-1背包问题;已知一个背包的容量为C,有n件物品,物品i的重量为Wi ,价值为Vi,求应如何选mij=Wij+min{mik+mk+1j} 1<=i<=j<=n,mii-1=0择装入背包中的物品,使得装入背包中物品的总价值最大;三、简答题30分1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为ai 和bi,请写出流水作业调度问题的johnson法则中对ai和bi的排序算法;函数名可写为sorts,n2.最优二叉搜索树问题的动态规划算法设函数名binarysearchtree 1.void sortflowjope s,int n{int i,k,j,l;fori=1;i<=n-1;i++//-----选择排序{k=i;whilek<=n&&sk.tag=0 k++;ifk>n break;//-----没有a i,跳出else{forj=k+1;j<=n;j++ifsj.tag==0ifsk.a>sj.a k=j;swapsi.index,sk.index;swapsi.tag,sk.tag; }}l=i;//-----记下当前第一个b i的下标fori=l;i<=n-1;i++{k=i;forj=k+1;j<=n;j++ifsk.b<sj.b k=j;swapsi.index,sk.index; //-----只移动index和tagswapsi.tag,sk.tag; }}2.void binarysearchtreeint a,int b,int n,int m,int s,int w{int i,j,k,t,l;fori=1;i<=n+1;i++{ wii-1=ai-1;mii-1=0;}forl=0;l<=n-1;l++//----l是下标j-i的差fori=1;i<=n-l;i++{ j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;fork=i+1;k<=j;k++{ t=mik-1+mk+1j+wij;ift<mij{ mij=t;sij=k;}}}}一、填空题本题15分,每小题1分1、算法就是一组有穷的规则 ,它们规定了解决某一特定类型问题的一系列运算2、在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型;3个基本计算模型是随机存取机RAM 、随机存取存储程序机RASP 、图灵机 ;3、算法的复杂性是算法效率的度量,是评价算法优劣的重要依据;4、计算机的资源最重要的是时间和空间资源5、fn= 6×2n+n2,fn的渐进性态fn= O 2^n6、贪心算法总是做出在当前看来最好的选择;也就是说贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优结构二、简答题本题25分,每小题5分1、简单描述分治法的基本思想;2、简述动态规划方法所运用的最优化原理;3、何谓最优子结构性质4、简单描述回溯法基本思想;5、何谓P、NP、NPC问题三、算法填空本题20分,每小题5分1、n后问题回溯算法1用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0;2分别用一维数组MN、L2N-1、R2N-1表示竖列、左斜线、右斜线是否放有棋子,有则值为1,否则值为0;forj=0;j<N;j++if 1 /安全检查/{ Aij=i+1; /放皇后/2 ；ifi==N-1 输出结果；else 3 ；; /试探下一行/4 ； /去皇后/5 ；;}2、数塔问题;有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大;forr=n-2;r>=0;r-- //自底向上递归计算forc=0; 1 ;c++if tr+1c>tr+1c+1 2 ；else 3 ；3、Hanoi算法Hanoin,a,b,cif n==1 1 ；else{ 2 ；3 ；Hanoin-1,b, a, c;}4、Dijkstra算法求单源最短路径du:s到u的距离 pu:记录前一节点信息Init-single-sourceG,sfor each vertex v∈VGdo { dv=∞; 1 }ds=0Relaxu,v,wif dv>du+wu,vthen { dv=du+wu,v;2}dijkstraG,w,s1. Init-single-sourceG,s2. S=Φ3. Q=VG4.while Q<> Φdo u=minQS=S∪{u}for each vertex 3do 4四、算法理解题本题10分根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树;要求中间被舍弃的结点用×标记,获得中间解的结点用单圆圈○框起,最优解用双圆圈◎框起;五、算法理解题本题5分设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成;1如果n=2k,循环赛最少需要进行几天；2当n=23=8时,请画出循环赛日程表;六、算法设计题本题15分分别用贪心算法、动态规划法、回溯法设计0-1背包问题;要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间;七、算法设计题本题10分通过键盘输入一个高精度的正整数nn的有效位数≤240,去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数;编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小;样例输入178543S=4样例输出13二、简答题本题25分,每小题5分6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同；对这k个子问题分别求解;如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解;7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的;8、某个问题的最优解包含着其子问题的最优解;这种性质称为最优子结构性质;9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,解为叶子结点;搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程;在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造;10、PPolynomial问题：也即是多项式复杂程度的问题;NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题;NPCNP Complete问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP 里面最难的问题,这种问题就是NPC 问题; 三、算法填空本题20分,每小题5分 1、n 后问题回溯算法 1 Mj&&Li+j&&Ri-j+N 2 Mj=Li+j=Ri-j+N=1; 3 tryi+1,M,L,R,A 4 Aij=05 Mj=Li+j=Ri-j+N=0 2、数塔问题; 1c<=r2trc+=tr+1c 3trc+=tr+1c+1 3、Hanoi 算法 1movea,c2Hanoin-1, a, c , b 3Movea,c 4、1pv=NIL 2pv=u3 v ∈adju 4Relaxu,v,w四、算法理解题本题10分五、18天2分；2当n=23=8时,循环赛日程表3分;六、算法设计题本题15分 1贪心算法 Onlogn➢ 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包;若将这种物品全部装入背包后,背1 2 3 4 5 6 7 82 1 43 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 87 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包;依此策略一直地进行下去,直到背包装满为止; ➢ 具体算法可描述如下：void Knapsackint n,float M,float v,float w,float x {Sortn,v,w; int i;for i=1;i<=n;i++ xi=0; float c=M;for i=1;i<=n;i++ {if wi>c break; xi=1; c-=wi; }if i<=n xi=c/wi; }2动态规划法 Oncmi,j 是背包容量为j,可选择物品为i,i+1,…,n 时0-1背包问题的最优值;由0-1背包问题的最优子结构性质,可以建立计算mi,j 的递归式如下;void KnapSackint v,int w,int c,int n,int m11 {int jMax=minwn-1,c;for j=0;j<=jMax;j++ /mn,j=0 0=<j<wn/ mnj=0;for j=wn;j<=c;j++ /mn,j=vn j>=wn/ mnj=vn;for i=n-1;i>1;i--{ int jMax=minwi-1,c;for j=0;j<=jMax;j++ /mi,j=mi+1,j 0=<j<wi/ mij=mi+1j;for j=wi;j<=c;j++/mn,j=vn j>=wn/ mij=maxmi+1j,mi+1j-wi+vi; }m1c=m2c; ifc>=w1m1c=maxm1c,m2c-w1+v1; }3回溯法 O2ncw:当前重量 cp:当前价值 bestp ：当前最优值i i i i w j w j j i m v w j i m j i m j i m <≤≥⎩⎨⎧++-++=0),1(}),1(),,1(max{),(nn nw j w j v j n m <≤≥⎩⎨⎧=00),(void backtrack int i//回溯法 i初值1{ ifi > n //到达叶结点{ bestp = cp; return; }ifcw + wi <= c //搜索左子树{ cw += wi;cp += pi;backtracki+1;cw -= wi;cp -= pi;}ifBoundi+1>bestp//搜索右子树backtracki+1;}七、算法设计题本题10分为了尽可能地逼近目标,我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符;然后回到串首,按上述规则再删除下一个数字;重复以上过程s次,剩下的数字串便是问题的解了;具体算法如下：输入s, n;while s > 0{ i=1; //从串首开始找while i < lengthn && ni<ni+1{i++;}deleten,i,1; //删除字符串n的第i个字符s--;}while lengthn>1&& n1=‘0’deleten,1,1; //删去串首可能产生的无用零输出n;三、算法填空1.背包问题的贪心算法void Knapsackint n,float M,float v,float w,float x{Sortn,v,w;int i;for i=1;i<=n;i++ xi=0;float c=M;for i=1;i<=n;i++ {if wi>c break;xi=1;c - =wi;}if i<=n xi=c/wi;}2.最大子段和: 动态规划算法int MaxSumint n, int a{int sum=0, b=0； //sum存储当前最大的bj, b存储bjforint j=1； j<=n； j++ {if b>0 b+= aj ；else b=ai; ； //一旦某个区段和为负,则从下一个位置累和 ifb>sum sum=b;}return sum；}3.快速排序template<class Type>void QuickSort Type a, int p, int r{if p<r {int q=Partitiona,p,r;QuickSort a,p,q-1; //对左半段排序QuickSort a,q+1,r; //对右半段排序}}4.排列问题Template <class Type>void permType list, int k, int m{ //产生listk:m的所有排列ifk==m{ //只剩下一个元素for int i=0;i<=m;i++ cout<<listi;cout<<endl;}else //还有多个元素待排列,递归产生排列for int i=k; i<=m; i++{swaplistk,listi;permlist,k+1;m;swaplistk,listi;}}5.给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x;据此容易设计出二分搜索算法：template<class Type>int BinarySearchType a, const Type& x, int l, int r{while l<=r {int m = l+r/2;if x == am return m;if x < am r = m-1; else l = m+1;}return -1;}6、合并排序描述如下：template<class Type>void MergesortType a , int left, int right{if left<right{int i= left+right/2;Mergesorta, left, i ;Mergesorta, i+1, right;Mergea,b, left,i,right;//合并到数组bCopya,b, left,right ; //复制到数组a}}7、以下是计算x m的值的过程int power x, m{//计算x m的值并返回;y= 1 ;i=m;Whilei- - >0y=yx;return y ;}四、问答题1.用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2. 算法定义：算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程3.算法的三要素1、操作2、控制结构3、数据结构13. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解;两者的不同点是：适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的;而用分治法求解的问题,经分解得到的子问题往往是互相独立的;回溯法中常见的两类典型的解空间树是子集树和排列树;22.请叙述动态规划算法与贪心算法的异同;共同点：都需要最优子结构性质,都用来求有优化问题;不同点：动态规划：每一步作一个选择—依赖于子问题的解;贪心方法：每一步作一个选择—不依赖于子问题的解;动态规划方法的条件：子问题的重叠性质;可用贪心方法的条件：最优子结构性质；贪心选择性质;动态规划：自底向上求解；贪心方法：自顶向下求解;可用贪心法时,动态规划方法可能不适用；可用动态规划方法时,贪心法可能不适用; 23. 请说明动态规划方法为什么需要最优子结构性质;答：最优子结构性质是指大问题的最优解包含子问题的最优解;动态规划方法是自底向上计算各个子问题的最优解,即先计算子问题的最优解,然后再利用子问题的最优解构造大问题的最优解,因此需要最优子结构.24. 请说明：1优先队列可用什么数据结构实现2优先队列插入算法基本思想3优先队列插入算法时间复杂度答：1堆;2在小根堆中,将元素x插入到堆的末尾,然后将元素x 的关键字与其双亲的关键字比较, 若元素x 的关键字小于其双亲的关键字,则将元素x 与其双亲交换,然后再将元素x 与其新双亲的关键字相比,直到元素x 的关键字大于双亲的关键字,或元素x 到根为止; 3O log n26. 在算法复杂性分析中,O 、Ω、Θ这三个记号的意义是什么 在忽略常数因子的情况下,O 、Ω、Θ分别提供了算法运行时间的什么界 答：如果存在两个正常数c 和N 0,对于所有的N ≥N 0,有|fN |≤C |gN |,则记作：fN = OgN ;这时我们说fN 的阶不高于gN 的阶;若存在两个正常数C 和自然数N0,使得当N ≥ N 0时有|f N|≥C |gN |,记为fN =ΩgN ;这时我们说fN 的阶不低于gN 的阶;如果存在正常数c1,c2和n0,对于所有的n ≥n0,有c1|gN| ≤|fN| ≤ c2|gN| 则记作 fN = g ,NO 、Ω、Θ分别提供了算法运行时间的上界、下界、平均 五、算法设计与分析题1．用动态规划策略求解最长公共子序列问题： 1给出计算最优值的递归方程;2给定两个序列X={B,C,D,A},Y={A,B,C,B},请采用动态规划策略求出其最长公共子序列,要求给出过程;答：1⎪⎩⎪⎨⎧≠>--=>+--===时y 0且x j 当i,)j]1,c[i 1],j max(c[i,时y 0且x j 当i,11]j 1,c[i 0时0或j 当i 0j]c[i,i i i i2Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1ΘＣ 0 0 1 2 2 Ｄ 0 0 1 2 2Ａ0 1 1 2 2 最长公共子序列：｛ＢＣ｝2．对下列各组函数f n 和g n,确定f n = O g n 或f n =Ωg n 或fn =θgn,并简要说明理由;1 fn=2n ； gn=n2 fn=n ； g n=log n 23 fn=100； gn=log1004 fn=n 3； gn= 3n5 fn=3n ； gn=2n 答：(1) fn = Ogn 因为gn 的阶比fn 的阶高; (2) fn = Ωgn 因为gn 的阶比fn 的阶低; (3) fn = θgn 因为gn 与fn 同阶; (4) fn = Ogn 因为gn 的阶比fn 的阶高; (5) fn = Ωgn 因为gn 的阶比fn 的阶低;3．对下图所示的连通网络G ,用克鲁斯卡尔Kruskal 算法求G 的最小生成树T ,请写出在算法执行过程中,依次加入T 的边集TE 中的边;说明该算法的贪心策略和算法的基本思想,并简要分析算法的时间复杂度;答：TE={3,4, 2,3,1,5,4,64,5}贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边; 基本思想：首先将图中所有顶点都放到生成树中,然后每次都在连接两个不同连通分量的边中选权值最小的边,将其放入生成树中,直到生成树中有n-1条边;时间复杂度为：Oeloge4. 请用分治策略设计递归的归并排序算法,并分析其时间复杂性要求：分别给出divide 、conquer 、combine 这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶; 答 ： Template <class Type>void MergeSort Type a , int left, int right { if left<right { int i=left+right/2; MergeSorta, left, i; MergeSorta, i+1, right; Mergea, b, left, right; Copya, b, left, right; }}Divide 阶段的时间复杂性： O1 Conquer 阶段的时间复杂性： 2Tn Combine 阶段的时间复杂性： Θn用套用公式法：a=2, b=2, n log b a = n , fn=n, 因为fn 与n log b a 同阶, ∴Tn =Θnlogn⎩⎨⎧>+==1当n θ(n)2T(n/2)1当n θ(1)T(n)1 2 3 4 5 6 75、设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次;循环赛要在最短时间内完成.14分循环赛最少需要进行n-1 天.26分当n=23=8时,请画出循环赛日程表:6、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码;这些字符出现在文件中的频数之比为20:10:6:4:44:16;要求：14 分简述使用哈夫曼算法构造最优编码的基本步骤；25 分构造对应的哈夫曼树,并据此给出a,b,c,d,e,f 的一种最优编码;解：1、哈夫曼算法是构造最优编码树的贪心算法;其基本思想是,首先所有字符对应n 棵树构成的森林,每棵树只有一个结点,根权为对应字符的频率;然后,重复下列过程n-1 次：将森林中的根权最小的两棵树进行合并产生一个新树,该新树根的两个子树分别是参与合并的两棵子树,根权为两个子树根权之和;2、根据题中数据构造哈夫曼树如下图所示;由此可以得出a,b,c,d,e,f 的一组最优的编码：01,0000,00010,00011, 1,001;7.考虑在序列A1..n中找最大最小元素的问题;一个分治算法描述如下：如果n≤2 就直接求解;否则,将序列等分成两个子序列A1..n/2和An/2+1..n,分别找出这两子序列的最大最小元素x1,y1 和x2,y2；然后据此求出A1..n的最大元素x=max{x1,x2}及最小元素y=min{y1,y2};请给出该算法计算时间Tn满足的递归方程,并解方程来确定算法的时间复杂度;假定n=2k k 为正整数;答：算法时间复杂度满足如下递归方程：Tn=2Tn/2+2n>2；T2=1;因为n=2 k k 为正整数,所以,Tn= T2 k= 2T2 k-1+2= 22T2 k-2+ 22+2⋯= 2k-1T2+ 2k-2+⋯+23+22+2= 2k-1+⋯+23+22+2;因此,Tn= n;8.考虑使用动态规划方法求解下列问题：01背包数据如下表,求：能够放入背包的最有价值的物品集合;如设： Vi, j —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值;请将如下递推式填写完整： V0, j = 00个物品,Vi, 0 = 0承重量0Vi, j = Vi-1, j 第 i 个物品不能装入, j < wi 超重Vi, j = max { , } j > wi 不超重 i 在最优子集中 i 不在最优子集中 自底向上：按行或列填写下表;答：V0, j = 00个物品,Vi, 0 = 0承重量0Vi, j = Vi-1, j 第 i 个物品不能装入, j < wi 超重Vi, j = max { v i + Vi-1,j-w j , Vi-1, j } j > wi 不超重 i 在最优子集中 i 不在最优子集中V j=0 1 2 3 4 5i=0 0 0 0 0 0 01 0 0 12 12 12 122 0 10 12 22 22 223 0 10 12 22 30 324 0 10 15 25 30 379.请画出用回溯法解4皇后问题的解空间树和搜索空间树：解空间树：用回溯法的搜索空间树：10.考虑用分支限界解0-1背包问题给定n 种物品和一背包;物品i 的重量是wi,其价值为vi,背包的容量为C;问应如何选择装入背包的物品,使得装入背包中物品的总价值最大示例：n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 求：1、问题的解空间树2、约束条件 2、如何剪枝解：问题的解空间树：11c xw ni ii ≤∑=约束条件： 如何剪枝 ：设r 是当前尚未考虑的剩余物品价值总和；Cv 是当前价值；bestv 是当前最优价值;当r ＋Cv ≤bestv 时,可剪去右子树;11,请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10},价值为{20, 30, 25},背包容量为25时搜索空间树; 答：解空间树：搜索空间树：1111111123457 8 1112 14 15310691不可行解价值=20价值=55价值=30价值=25价值=011 110 0 01128 1112 14 15 131069。
《算法设计与分析》历年期末试题整理(含答案)（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
算法设计与分析复习题目及答案一、算法的基本概念1、什么是算法？算法是指解决特定问题的一系列明确步骤，它具有确定性、可行性、有穷性、输入和输出等特性。
例如，计算两个数的最大公约数的欧几里得算法，就是通过反复用较小数去除较大数，然后将余数作为新的较小数，直到余数为 0，此时的除数就是最大公约数。
2、算法的复杂度包括哪些？它们的含义是什么？算法的复杂度主要包括时间复杂度和空间复杂度。
时间复杂度是指算法执行所需要的时间量，通常用大 O 记号来表示。
例如，一个算法的时间复杂度为 O(n)，表示其执行时间与输入规模 n成正比。
空间复杂度则是算法在运行过程中所需要的额外存储空间的大小。
比如说，一个算法需要创建一个大小为 n 的数组来存储数据，那么其空间复杂度就是 O(n)。
二、分治法1、分治法的基本思想是什么？分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题结构相同。
然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。
2、请举例说明分治法的应用。
例如归并排序算法。
将一个未排序的数组分成两半，对每一半分别进行排序，然后将排好序的两部分合并起来。
其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
三、动态规划1、动态规划的基本步骤有哪些？动态规划的基本步骤包括：（1）定义问题的状态。
（2）找出状态转移方程。
（3）确定初始状态。
（4）计算最终的解。
2、解释最长公共子序列问题，并给出其动态规划解法。
最长公共子序列问题是指找出两个序列的最长公共子序列的长度。
假设我们有两个序列 X 和 Y，用 dpij 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。
状态转移方程为：如果 Xi 1 ＝＝ Yj 1，则 dpij ＝ dpi 1j 1 ＋ 1否则 dpij ＝ max(dpi 1j, dpij 1)四、贪心算法1、贪心算法的特点是什么？贪心算法在每一步都做出当前看起来最优的选择，希望通过这种局部最优选择达到全局最优解。
一、算法时间复杂性问题1. 试证明下面的定理：(1)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n));(2)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O 的定义，存在正常数C 1，C 2和自然数N 1,N 2，使得对所有的n>= N 1，f （n ）<=C 1s(n)；对所有的n>= N 2,g(n) <=C 2r(n)所以 f （n ）+ g(n) <= C 1s(n)+ C 2r(n)，f （n ）*g(n)<= C 1C 2s(n)r(n)；令 C3=max （C1,C2），C4=C1*C2；则：f （n ）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))（n ）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))2. 假设某算法在输入规模为n 时的计算时间为：T （n ）=3*2n ，在A 型计算机上实现并完成该算法的时间为t 秒，现有更先进的B 型计算机，其运算速度为A 型计算机的64倍。
试求出若在先进的B 型机上运行同一算法在则T 秒内能求解输入规模为多大的问题？某台t 秒内完成的基本运算的次数=3*2^n 新机器t 秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6)设N 为B 型机上t 秒钟能求解的问题的规模所以T=T(N)=3*2^N=3*2^(n+6) 则：N=n+63. 试说明为什么“在现代计算机上运行指数（如2n ）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为Ο(n 2)的算法则由一个二次多项式来限界。
以下六种计算时间的多项式时间算法是最为常见的，其关系为指数时间算法一般有Ο(2n )、Ο(n!)和Ο(n n )等。
其关系为：其中，最常见的是时间为Ο(2n )的算法。
当n 取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因为根本就找不到一个这样的m ，使得2n 囿界于n^m 。
换言之，对于任意的m ≥0，总可以找到n 0，当n ≥n 0时，有2n ＞n m 。
因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。
Ο(log 2n)、Ο(n)和Ο(nlog 2n)比另外三种时间函数的增长率慢得多。
～ 由这些结果可看出，当数据集的规模(即n 的取值)很大时，要在现代计算机上运行具有比Ο(nlog 2n)复杂度还高的算法往往是很困难的。
尤其是指数时间算法，它只有在n 值取得非常小时才实用。
尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n 足够大时，n 每增加1，1000倍的提速即可瞬间化为乌有，所以要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。
二、简答1.对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。
试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。
寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。
但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。
显然，建立下界要比确定上界困难得多。
2.满足何种性质的问题被称为NP 完全问题？请简述研究NP 完全问题的意义；（1）NP 即是多项式复杂程度的非确定性问题。
而如果任何一个NP 问题都能通过一个多项式时间算法转换为某个NP 问题，那么这个NP 问题就称为NP 完全问题。
如果一个NP 完全问题能在多项式时间内得到解决，那么NP 中的每一个问题都可以在多项式时间内解决。
（2）NP 完全是指这样一类NP 问题,所有的NP 问题都可以用多项式时间划归到他们中的一个.所以显然NP 完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP －完全问题也可以在多项式时间内求解。
这样一来,只要我们找到一个NPC 问题的多项式解,所有的NP 问题都可以多项式时间内划归成这个NPC 问题,再用多项式时间解决,这样NP 就等于P 了.NP 完全性理论的重要性:知道一个问题是NP 完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。
一定不要去优先寻找有效的、精确的算法。
现在比较适当的途径是集中精力致力于其他较低目标的方法。
例如，你可以寻找解决这个问题的各种特殊情况的有效算法。
寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。
或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。
简言之，NP 完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向3. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。
问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
最优子结构是问题能用动态规划算法求解的前提。
Ο(2n )＜Ο(n!)＜Ο(n n ) Ο(1)＜Ο(log 2n)＜Ο(n)＜Ο(nlog 2n)＜Ο(n 2)＜Ο(n n )同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（y1,y2,…,yn ）是0-1背包问题的一个最优解，而（y2,…,yn ）是相应子问题的一个最优解，有2max ni ii v x =∑ 112n i i i w xC w y =≤-∑ {0,1}2x i n ∈≤≤假设（y2,…,yn ）不是一个最优解，而（z2,…,zn ）是最优解，由此可知，这说明（y1,z1,z2,…,zn ）是问题的整体最优解，与（y1,y2,…,yn ）是最优解矛盾，所以证明了最优子结构性质！三、算法设计与分析问题1. 最大值和最小值问题的最优算法（18）给定n 个实数存放于一维数组A 中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A 中的最大值和最小值（为简化，可假设n 为偶数）。
2. 社会名流问题在 n 个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。
现在的问题是如果存在，试找出该社会名流。
你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。
）我们的最终目标是将询问的数目最小化。
给定一个n ×n 邻接矩阵，确定是否存在一个i ，其满足在第i 列所有项（除了第ii 项）都为1，并且第i 行所有项（除了第ii 项）都为0。
大致的算法思路：随便取一个非对角线元素比如Array[i][j]，如果Array[i][j]=0成立，则j 不是社会名流，于是删去第j 行和第j 列。
同样，如果Array[i][j]=1成立，则删去第i 行和第i 列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。
重复此操作直至剩下最后一个元素。
最后，检验该元素是否为社会名流即可。
如果该元素不是，则该群人中不存在社会名流。
3.数列极差问题在黑板上写了N 个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a 和b ，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。
在所有按这种操作方式最后得到的数中，最大的数记为Max ，最小的数记为Min ，则该数列的极差定义为M=Max-Min 。
贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。
贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择来达到。
而最优子结构性质是指一个问题的最优解包含其子问题的最优解。
问题的关键就是MAX MIN 值的求解问题，所以首先看下怎么样来求MAX MIN 值。
设有三个数x y z,且x<y<z ，按问题描述来做的话，结果有下面三种情况：num1=（x*y+1）*z+1=xyz+z+1 , num2=(x*z+1)*y+1=xyz+y+1，num3=(y*z+1)*x+1=xyz+x+1。
很容易看出num1>num2>num3。
所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。
我们可以把整体的MAX ，MIN 值通过一系列局部求MAX,MIN 值来求我们想要的结果。
我们再看下用贪心策略求解的合理性：假设经（N －3）次运算后得到3个数：x y max （max>x>y ），其中max 是（N －2）个数经（N －3）次运算后所得的最大值，此时最大值m ＝（x*y ＋1）×max ＋1。
若经（N －2）次变换后所得的3个数为：x y z （z>x>y ）且z 不为（N －2）次变换后的最大值，即z ＜max 则所求得的最大值为： m ’＝（x*y+1）*z+1， 此时m －m ’＝（1+x*y ）（max －z ）＞0 所以此时不为最优解。
所以若使第k （1≤k ≤N －1）次变换后所得值最大，必使（k －1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。
所以综上所述：该算法可以简单的描述为：MAX：不断地取当前黑板上的两个最小的数进行运算并且放回，会使最后的结果最大。
MIN：不断地取当前黑板上的两个最大的数进行运算并且放回，会使最后的结果最小。
