下载文档原格式
《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f （n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n , g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不----------------------------精品word文档值得下载值得拥有----------------------------------------------再数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。
试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。
要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。
八、在一个由元素组成的表中出现次数最多的元素称为众数。
试写一个寻找众数的算法，并分析其计算复杂性。
九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
算法与程序设计期中考试试题算法与程序设计期中考试试题⼀、选择题：每题2分，30题，共60分（）1．以下问题中最适合⽤计算机编程处理的是。
A．制定本学期的学习计划B．计算正⽅形的周长C．创作⼀⾸歌曲D．求1000以内的所有素数（）2．⽤计算机解决问题的步骤⼀般为。
①编写程序②设计算法③分析问题④调试程序A．①②③④B．③④①②C．②③①④D．③②①④（）3．下⾯说法正确的是。
A．算法+数据结构=程序B．算法就是程序C．数据结构就是程序D．算法包括数据结构（）4．以下是算法具有的特征。
①有穷性②确定性③可⾏性④输⼊⑤输出A．①②③B．②③④C．③④⑤D．①②③④⑤（）5．常⽤的算法描述⽅法有。
A．⽤⾃然语⾔描述算法B．⽤流程图描述算法C．⽤伪代码描述算法D．以上都是（）6．流程图中表⽰判断框的是。
A．矩形框B．菱形框C．圆形框D．椭圆形框（）7．程序设计语⾔的发展阶段不包括。
A．⾃然语⾔B．机器语⾔C．汇编语⾔D．⾼级语⾔（）8．要使命令按钮显⽰⽂字“确定”，正确的设置是把该命令按钮的。
A．Font属性设置为“确定”B．ForeColor属性设置为“确定”C．Caption属性设置为“确定”D．BorderStyle属性设置为“确定”（）10．下⾯的属性中，⽤于设定控件⾼度的是。
A．F ont B．H eight C．Caption D．W idth （）11．窗体的BackColor属性⽤于设置窗体的＿＿＿＿。
(p18)A．宽度B．前景⾊C．⾼度D．背景⾊12．在VB中，若要将变量N定义为单精度型数据，则下列表⽰⽅法中正确的是化。
A．Dim N as String B．Dim N as Single C．Dim N as Integer D．Dim N as Long（）14．在程序设计的过程中，错误的声明⼀个变量会导致程序不能正常编译。
因此，需要规范合理地声明⼀个变量，下列合法的变量名是。
A．if B．zf3 C．8-a D．a#2（）17．某学校打算选拔⾝⾼T超过1.75⽶且体重W不⼤于55公⽄的⼈作为招⽣条件，表⽰该条件的布尔表达式为。
《算法分析与设计》2021-2021-2学期期中测试（信息安全专业DQ 教学班）姓名：学号：得分：1. 证明()()()()()()()O f n O g n O f n g n +=+。
（10分）证明：对于任意f 1(n ) O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n n 1，有f 1(n ) c 1f (n )成立。
类似，对于任意g 1(n )O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n n 2，有g 1(n )c 2g (n )成立。
令c 3=max{c 1, c 2}，n 3 =max{n 1, n 2}，则对所有的nn 3，有f 1(n ) +g 1(n ) c 1f (n ) + c 2g (n )c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n ))即()()()()()()()O f n O g n O f n g n +=+成立。
2. 将下列5个函数按渐近增加率由低至高进行排序，要求写出比较进程。
（15分）解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log limlimlim log n n n f n n nn n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()()423log 1limlimlim 0log n n n f n n n f n n n n→∞→∞→∞===，因此()43()()f n O f n =;(4) 对1()f n 和3()f n 取对数，有()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;因此，5个函数按渐近增加率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。
算法设计参考答案算法设计参考答案在计算机科学领域，算法设计是一门重要的学科，它关注如何设计高效、可靠的算法来解决各种问题。
在实际应用中，算法设计的质量直接影响着计算机系统的性能和用户体验。
本文将探讨一些常见的算法设计问题，并给出参考答案。
一、排序算法排序是算法设计中最基本的问题之一。
在现实生活中，我们经常需要对一组数据进行排序，以便更好地组织和利用这些数据。
以下是两种常见的排序算法及其参考答案：1. 冒泡排序(Bubble Sort)冒泡排序是一种简单但效率较低的排序算法。
它的基本思想是通过相邻元素的比较和交换，将较大的元素逐渐“冒泡”到数组的末尾。
具体实现如下：```pythondef bubble_sort(arr):n = len(arr)for i in range(n - 1):for j in range(n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr```2. 快速排序(Quick Sort)快速排序是一种高效的排序算法，它利用了分治的思想。
具体而言，它通过选择一个基准元素，将数组分割为两部分，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对左右两部分进行排序。
具体实现如下：```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)```二、图算法图是一种常见的数据结构，用于表示各种实际问题的关系和连接。
算法分析与设计期中练习一、选择题1. 实践表明可操作性最好且最有实际价值的是（B）情况下的时间复杂性。
A.最好B.最坏C.平均D.特殊2. 算法的时间复杂性函数用T(n)表示，其中参数n是指（ A ）。
A.问题规模B.运行时间C.输入量D.输出量3. 函数105logn2+n2logn+n3的渐近表达式为（C）。
A.logn2B.n2lognC.n3D. 1054. 二分搜索算法中，如果待查找元素x不在已排好序的n个元素中，则完成该搜索任务需用（B）时间。
A.O(nlogn)B.O(logn)C.O(n)D.O(n2)5. Strassen矩阵乘法问题中，改进算法的计算复杂性关键在于（ A ）。
A.减少矩阵乘法B.增加矩阵乘法C.减少矩阵加法D.增加矩阵加法6. 最优子结构和重叠子问题是（A）算法的两个基本要素。
A.动态规划B. 贪心C.分支限界D. 分治7. 使用贪心算法解决活动安排问题时使用了（B）优先的贪心选择策略。
A.最早开始活动B.最早结束活动C.时间最短活动D.时间最长活动8. f(n)= log7n,g(n)= 100logn，满足f(n)= （ B ）(g(n))。
A. OB.ΩC.Θ9. f(n)= logn8,g(n)= log(100n)，满足f(n)= （C）(g(n))。
A. OB.ΩC.Θ10. f(n)= 30(logn)10,g(n)= 30n5,满足f(n)= （A）(g(n))。
A. OB.ΩC.Θ11. f(n)= 105n,g(n)= log10n,满足f(n)= （ C ）(g(n))。
A. OB.ΩC.Θ12. f(n)= 4n ,g(n)= 410(3n),满足f(n)= （B）(g(n))。
A. OB.ΩC.Θ13. 贪心法解装载问题时，采用的解题策略是（B）。
P95A.平均分配两艘轮船的载重B. 按集装箱重量从轻至重装船C. 将第一艘轮船尽可能装满D. 将第二艘轮船尽可能装满14. 用回溯法解0-1背包问题时，解空间可构造为（C）的形式。
数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。
A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。
A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。
A 、线性表中的数据元素可以是数字、字符、记录等不同类型。
B 、线性表中包含的数据元素个数不是任意的。
C 、线性表中的每个结点都有且只有⼀个直接前驱和直接后继。
D 、存在这样的线性表：表中各结点都没有直接前驱和直接后继。
4、关于单链表的说法，请选出不正确的⼀项( C)。
A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。
A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。
x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。
A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。
T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。
算法设计分析期中试题.pdf《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f（n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n, g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不再数组中时，返回小于x的最大元素位置i和大于x 的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x 在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。
试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。
要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。
八、在一个由元素组成的表中出现次数最多的元素称为众数。
试写一个寻找众数的算法，并分析其计算复杂性。
九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价值为v i ，背包的容量为C，容积为D。
测试题1. 简述下列策略的基本思想 (15) (1) 分治将输入规模为n 的问题分成k （一般取k=2）个子问题，子问题相互独立，与原问题性质相同。
先分别对k 个子问题求解，再将子问题的解合并成原问题的解。
由于子问题还很大，故采用递归技术对子问题不断分割，直至子问题可直接简单地解出。
(2) 贪心贪心法希望从求局部最优达到全局最优，即依据贪心策略逐步构造最优解。
即先按确定贪心策略，将输入量排序。
再依次做出当前最优的选择，即当前输入可以构成合法的部分解，则将此输入量选入。
决策一旦做出，就不可再更改。
(3) 动态规划动态规划也是将问题求解过程分成k 个阶段（划分子问题），逐步决策的方法。
与贪心法不同的是，动态规划采用划分子问题，自底向上规划的方法。
要求子问题的划分具备最优子结构性质，即“最优化原理”成立。
需列出当前决策对前阶段决策状态的依赖关系（贝尔曼方程），求出各子问题的最优解，并将子问题的最优解代到下一步的决策中，逐步规划，解出原问题的解。
贝尔曼方程：⎪⎩⎪⎨⎧+==≠}.{min ,0ij i j i j s w u u u2. 下列数组4,1,3,2,16,9,10,14,8,7构成一个堆吗？如果不是，请用自底向上算法建一个 a max-heap.(10) 1) 不是一个最大堆2）按照算法，从i=n/2-5处开始测试i=5 它的孩子节点 2*i=10 ，满足最大堆的规定i=4 ，2i=8，2i+1=9 不满足，整理如下：i=3 ，2i=6，2i+1=7 不满足，整理如下：i=2 ，2i=4，2i+1=5不满足，整理如下：i=1 ，2i=2，2i+1=3不满足，依次整理如下：3. 针对下列叙述，根据正确或错误，选择T或F，并简要说明卫生么.(30)(1) T F nlogn=O(n3) 是上界(2) T F根据master定理, 递归方程T(n)=3T(n/3)+n 的解是T(n)=Θ(n)正确答案：T(n)=O(nlogn)（3）T F 最坏情况下, 归并排序的时间渐进阶是O（n2）.归并排序最坏情况下的时间是：T(n)=O(nlogn)（4）T F 图的深度优先搜索的时间是O（n+|E|）。
一、函数渐进阶。
对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +5二、设n个不同的整数排好序后存于T[0:n-1]中。
若存在下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的算法找到该下标（15分），并用C/C++编程实现（10分）。
三、分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。
要求：1.说明算法策略（每种方法5分）；2.主要算法步骤（10分）；3.分析算法的时间复杂度（5分）四、试设计解决TSP问题的贪心算法（10分），分析时间复杂度（5分），试分析是否存在O(n2log n)的有效算法（5分）。
1函数渐进阶。
对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +52设n个不同的整数排好序后存于T[0:n-1]中。
若下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的存在算法找到该下标（15分），并用C/C++编程实现（10分）。
解答：由题可知，数组T[ ]是排列好的整数集。
可以用二分搜索的算法对问题进行操作。
取中间值T[mid],如果T[mid]=mid则可以返回mid；如果T[mid]<mid在mid+1到n-1之间进行上述操作；如果T[mid]>mid在0到mid-1之间进行上述操作。
Int Findi(int T[],int m,int n){Int mid=(m+n)/2;If (T[mid]==mid) return mid;else if(T[mid]>mid) return Findi(T[],m,mid-1);else return Findi(T[],mid+1,n);}算法设计：输入：一个数组T[ ]，起始地址m，末端地址n比较指定数组位置的中间元素T[(m+n)/2]与中间地址(m+n)/2.1）如果T[(m+n)/2]等于(m+n)/2，则返回(m+n)/2；2）如果T[(m+n)/2]大于(m+n)/2，则返回在数组T[ ]中m位到(m+n)/2-1之间进行此算法的返回值；3）如果T[(m+n)/2]小于(m+n)/2，则返回在数组T[ ]中(m+n)/2+1到n之间进行此算法的返回值；输出：一个值，若存在则返回i；若不存在则返回0.3分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。
《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ 教学班）姓名： 学号： 得分：1. 证明()()()()()()()O f n O g n O f n g n +=+。
（10分）证明：对于任意f 1(n ) ∈ O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n ≥ n 1，有f 1(n ) ≤ c 1f (n )成立。
类似，对于任意g 1(n ) ∈ O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n ≥ n 2，有g 1(n ) ≤ c 2g (n )成立。
令c 3 = max{c 1, c 2}，n 3 = max{n 1, n 2}，则对所有的n ≥ n 3，有 f 1(n ) +g 1(n ) ≤ c 1f (n ) + c 2g (n ) ≤ c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n ))即()()()()()()()O f n O g n O f n g n +=+成立。
2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。
（15分）解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log limlimlim log n n n f n n nn n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()()423log 1limlimlim 0log n n n f n n n f n n n n→∞→∞→∞===，因此()43()()f n O f n =;(4) 对1()f n 和3()f n 取对数，有()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。
3. 给定按升序排列的n 个不同整数存于数组a [1:n ]中，请设计()log O n 的算法找到下标i ，1i n ≤≤，使得a [i ] = i ，如不存在这样的下标，则返回0。
（15分） 解：令head = 1, rear = n .(1) 当head <= rear 时，令mid = ⌊(head + rear)/2⌋； (2) 如果a [mid] = mid ，返回mid 值，结束。
如果a [mid] > mid ，令rear = mid – 1，返回(1)继续执行； 如果a [mid] < mid ，令head = mid + 1，返回(1) 继续执行； (3)返回0值，结束。
public static int Search(int [] a, int n) {// 在 a[0] <= a[1] <= ... <= a[n -1] 中搜索 a[i] = i // 找到a[i] = i 时返回i ，否则返回0 int left = 0; int right = n – 1; while (left <= right){int mid = ⌊(left + right)/2⌋; if (a[mid] == mid) return mid; if (a[mid] > mid) right = mid – 1; else left = mid + 1; }return 0; // 未找到a[i] = i }4. 利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。
（20分）(1) ()()42T n T n n =+, (2) ()()242T n T n n =+, (3) ()()342T n T n n =+解：(1) 24,2,log log 42,b a b a ==== 因此，()()2T n n =Θ. (2) 24,2,log log 42,b a b a ====因此，()()2log T n n n =Θ.(3) 24,2,log log 42,b a b a ====而且()()()333424223,f n n n n cf n ==≤=其中34n =，因此，()()3T n n =Θ.证明：假设当k n <时，()2log T k ck k ≤，其中c为常数。
因此，命题得证。
5. 利用直接展开法求解下列递归式的渐近界。
（20分）(1) ()()242T n T n n =+, (2) ()T n n=+解：(1)(2) ()T n n =+其中122k n '=，则所以，()()()2log log 1log log 2T n T n n n =+=Θ+， 即()()loglog T n O n n =.6. 某超市中有n 种商品搞活动，每种商品i 的重量是w i ，其价格为v i ，现在给你发一个容量为C 的购物车，你可以在这n 种商品中选一些放入你的购物车中免费带走。
但是要求所选的商品重量之和不能大于购物车容量C ，而且超市中每种商品每人最多选两件。
请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）(a) 为该问题设计一个动态规划算法，要求写出分析过程和递归式。
(b) 若该超市共有3种商品搞活动，商品的价值依次为v = (25, 30, 15)，商品的重量依次为w = (2, 3, 1)，购物车容量为C = 5。
运用自底而上的方法求解上述问题，要求画出表格，并给出最优解与最优值！解： 方法1✧ 将n 种商品全部复制一份得到2n 种商品，这样每种商品最多只能选择1件。
✧ 定义m (i , j )为购物车容量为j ，由第1, …, i 种商品装入购物车的最优值。
✧ Case 1: 不选择第i 种商品➢ 则m (i , j )为当重量限制为j 时，{1, …,i – 1}种商品装入购物车所产生的最大价值 ✧Case 2: 选择第i 种商品.➢ 新的重量限制为 j – w i➢ m (i , j – w i ) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值因此，递归式如下：最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3 最优值 = 25+25+15=65方法2✧ 定义m (i , j )为购物车容量为j ，由第1, …, i 种商品装入购物车的最优值。
✧ Case 1: 不选择第i 种商品➢ 则m (i , j )为当重量限制为j 时，{1, …,i – 1}种商品装入购物车所产生的最大价值✧ Case 2: 仅选择1格第i 种商品.➢ 新的重量限制为 j – w i➢ m (i , j – w i ) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值 ✧ Case 3: 选择两个第i 种商品➢ 新的重量限制为 j – 2w i➢ m (i , j – 2w i ) 为新重量限制下，{1, …,i – 1}种商品装入购物车所产生的最大价值因此，递归式如下：最优解：选择两个商品1, 一个商品3 最优值 = 25+25+15=65 第2章作业：算法分析基础 1. 算法与程序的区别(1).算法特性之一是有穷性，程序不一定满足有穷性。
(2). 计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。
(3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。
2. 将下列函数按渐进增长率由低到高排列出来。
令log m n =，则有显然上述4个函数的渐近增长率排序为()()()()3146g n g n g n g n ≤≤≤； 显然上述3个函数的渐近增长率排序为()()()625g n g n g n ≤≤；因此，原函数的渐近增长率排序为()()()()()()314625f n f n f n f n f n f n ≤≤≤≤≤。
3. 已知()()()g n O f n =，证明()()()()f n g n O f n +=。
证明：因为()()()g n O f n =，存在正常数c 0和自然数n 0，使得对所有n ≥ n 0，有()()0g n c f n ≤成立。
令c 1 = c 0 + 1，则对所有的n ≥ n 0，有 f (n ) +g (n ) ≤ f (n ) + c 0f (n ) ≤ (1 + c 0)f (n ) = c 1f (n )即()()()()f n g n O f n +=成立。
第3章作业：分治递归1.画出T(n)=2T(n/2)+1的递归树，并给出其解的渐进界。
然后用数学归纳法证明给出的界。
证明：假设当k n <时，()12T k c k c ≤-，其中c 1和c 2为常数。
因此，命题得证。
2.直接展开法求解递归式T(n)=T(n/2)+13.用主方法求解递归式1.T(n)=4T(n/2)+n,2.T(n)=4T(n/2)+n 2,3.T(n)=4T(n/2)+n 3,4.T(n)=3T(n/2)+ n 2请参考期中测试答案。
第4章作业：动态规划1、设计一个O(n*log k) 时间的分治递归算法，将k 个排好序的序列合并成一个排好序的序列，其中 k 个序列共计包含n 个元素。
将k 个有序数列两两合并排序，得到2k ⎡⎤⎢⎥个有序数列，再次两两合并排序，得到4k ⎡⎤⎢⎥个有序数列，重复操作直至得到一个长度为n 的有序数列。
共计log k 次合并排序，每次合并排序数据的总体规模为n ，则时间复杂度为O(n log k )2、给定数组a[1…n]，n 为偶数。
设计一个算法，在最坏情况下用 3n/2 – 1 次比较找出a[1…n]中元素的最大值和最小值。
将a[1]…a[N]两两分成一组，即为a[1]和a[2] , a[3]和a[4] , a[5]和a[6] , … 共计N/2组，每组中的两个元素进行比较，得到最大值和最小值，共计N/2次比较；上述每组中的最大值组成数组b[1…N/2]，冒泡排序(或其他排序方法)求得b[1…N/2]中的最大值，即为原数组a[1…N]的最大值，需N/2 –1次比较；同理，上述每组中的最小值组成数组c[1…N/2]，冒泡排序(或其他排序方法)求得c[1…N/2]中的最小值，即为原数组a[1…N]的最小值，需N/2 –1次比较；因此，共需3N/2 – 1次比较.3、设计O(n2)时间的动态规划算法，找出由n个数组成的序列的最长单调递增子序列，要求给出分析过程和递归表达式。
