东北大学数据结构期末复习

期末复习题型•选择题（10分）•填空题（10分）•算法应用题（算法填空，简单问题回答）（3-4个题，35-40分）•算法设计（按照已知条件设计算法或为算法补充完整）（3个题，45-50分）第1章•算法的性质及其与程序的区别•算法复杂性分析–渐进意义下的四种记号–简单的程序段的复杂度分析算法的五个重要特征–输入有零个或多个由外部提供的量作为算法的输入–输出算法产生至少一个量作为输出.–确定性组成算法的每条指令是清晰的,无歧义的.–有限性在执行了有穷步骤后运算终止–可行性运算都是基本运算，原理上能在有限时间内完成。渐进意义下的记号：O,Ω,θ,о•f(N)和g(N)是定义在正整数上的正函数定义1.1如果存在两个正常数c和N0,对于所有的N≥N0，有f(N)≤Cg(N)，则记作：f(N)=O(g(N))。N0f(N)g(N)当说一个算法具有O(g(n))的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)符号Ω的定义•定义1.2如果存在两个正常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界；且g(N)是它的一个下界，记为f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。θ，o的定义•θ——定义f(N)=θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶•o——如果对于任意给定的ε0，都存在正整数N0，使得当N≥N0时有f(N)/g(N)ε，则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))•例如：4NlogN+7=o(3N2+4NlogN+7)1.2算法分析初步多项式时间算法(polynomialtimealgorithm):可用多项式来对其计算时间限界的算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法(exponentialtimealgorithm):计算时间用指数函数限界的算法O(2n)O(n!)O(nn)•作业1-7第2章•递归•分治法基本思想•二分搜索算法•Strassen矩阵乘法•合并排序和快速排序递归复杂度分析汉诺塔移动次数M(1)=1M(n)=2M(n-1)+1=2[2M(n-2)+1]+1=22M(n-2)+2+1=23M(n-3)+22+2+1=……=2iM(n-i)+2i-1+2i-2+……+2+1=2iM(n-i)+2i-1令i=n-1则M(n)=2n-1+2n-1-1=2n-12.1递归分治法的基本思想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。例2-6在[9,12,15,27,39]中分别查找27，12，1491215273901234leftrightmidmid=(left+right)/2=(0+4)/2=2mid=(3+4)/2=3912152739leftrightmid查找27成功返回3，leftright912152739leftrightmid912152739leftright查找12成功返回1,left=right查找14失败返回-1,leftrightmid912152739leftrighttemplateclassTintBinarySearch(Ta[],constT&x,intn){//在a[0]=a[1]=···=a[n-1]中搜索x//如果找到，则返回所在位置，否则返回–1intleft=;intright=;while(){intmiddle=;if(x==a[middle])returnmiddle;if(xa[middle])left=;elseright=;}return–1;//未找到x}n-10left=right(left+right)/2middle+1middle–1当n1时，Tw(n)=Tw([n/2])+1,T(1)=1Tw(n)=Tw([n/2])+1=Tw([n/4])+1+1……=Tw(1)+1+...+1=1+k=1+logn二分搜索的时间复杂度最坏情况下的成功检索计算时间Θ(logn)最坏情况下的不成功检索计算时间Θ(logn)最好情况下的成功检索计算时间Θ(1)最好情况下的不成功检索计算时间Θ(logn)每种不成功的检索时间都为Θ(logn)2.2二分搜索技术作业：1.P34，2-2中第二个和第五个算法的正确性，错误的说明原因或者给出反例2.P35,2-32-3：二分搜索中当程序停止时，左右指针或者指向同一个元素，此时该元素等于待查找元素或者left=right+1，此时right指向的为比待找元素小的元素，left为比待找元素大的元素归并排序主程序伪代码templateclassTypevoidMergeSort(Typea[],intleft,intright){//A[left:right]是一个全程数组，含有right-left+1个待排序的元素。if(){//至少有2个元素intmid=(left+right)/2;//求当前数组的分割点MergeSort(a，left,mid);MergeSort(a，mid+1,right);Merge(a，b，left,mid,right);copy（a，b，left，right）；}}leftright递归调用，分别对分解出来的两个子问题排序合并两个排好序的子问题，放入另一个数组b中2.4合并排序考虑数组a的两段为[1,7,8,9]和[2,3,4,5]1,7,8,92,3,4,51,7,8,92,3,4,511,21,7,8,92,3,4,51,2,31,7,8,92,3,4,51,2,3,41,7,8,92,3,4,51,2,3,4,5数组a的两部分数组b1,2,3,4,5,71,2,3,4,5,7,81,2,3,4,5,7,8,9在移动扫描指针的同时，要判断其是否已经到达数组的尾部，如到达，则停止扫描，把未参加排序的数全部放入备用数组中2.4合并排序合并函数templateclassTypevoidMerge(Typea[],Typeb[],intl,intm,intr){//合并a[l:m]和a[m+1:r]到b[l:r]inti=l;j=m+1,k=l;while(()&&())if(a[i]=a[j])b[k++]=a[i++];elseb[k++]=a[j++];if(im)for(intq=j;q=r;q++)b[k++]=a[q];elsefor(intq=I;q=m;q++)b[k++]=a[q];}把a[l:m]和a[m+1:r]中的数据进行比较，按顺序放入b[]中如果前一段数据小于后一段的多，则先排完，把后段剩余数赋给b[n],否则将前段数据赋给b[n]前半段指针后半段指针数组b的下标指针i=mj=r2.4合并排序作业•分析merge函数最好与最坏的键值比较次数。最好比较1次最差比较m+n-1，m和n分别为两段数组的长度快速排序TemplateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}a的起始位置A的终止位置Partition函数负责将a进行一次分割，返回分割元素的位置快速排序问题划分程序templateclassTypeintPartition(Typea[],intp,intr){inti=,j=;Typex=;while(true){while(a[++i]x);while(a[--j]x);if()break;Swap(a[i],a[j]);}a[p]=;a[j]=;returnj;}快速排序问题pr+1a[p]i=ja[j]x左侧扫描指针起始右侧扫描指针起始中轴元素移动左侧扫描指针移动右侧扫描指针算法分析•最坏情况：划分的两个区域分别包含n－1个元素和1个元素，如果每一步都出现这种情况，其复杂性T(n)O(1)n≤1T(n)=T(n-1)+O(n)n1解得：T(n)=O(n2)快速排序问题•最好情况•每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，O(1)n≤1T(n)=2T(n/2)+O(n)n1T(n)=O(nlogn)快速排序问题•2-19•将算法Partition中的不等号反向第3章•动态规划思想，基本要素•矩阵连乘算法及最优解构造•0-1背包问题最优值及最优解•最优二叉搜索树（通过具体实例弄清每个算法的流程及算法的具体实现）动态规划算法将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。算法思想动态规划算法的基本要素1最优子结构性质2重叠子问题性质1.最优子结构•当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。•分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。动态规划算法的基本要素2.重叠子问题•在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。动态规划算法的基本要素动态规划与分治的联系区别•都是分解成子问题，由子问题的解得到原问题的解。•分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。动态规划算法设计步骤（1）找出最优解的性质，刻画其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造一个最优解矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中Ai是一个ri-1×ri矩阵(1≤i≤n)，即Ai×Ai+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。问题提出设三个矩阵A1,A2,A3大小分别为10×100，100×5，5×50，考虑(A1(A2A3)),(A1A2)A3的结果与相乘的次数。最优子结构特征•计算A[1:n]的一个最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的•矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。矩阵连乘问题考虑A[1:k]和A[k+1:n]相乘所需的计算量，A[i:k]和A[k+1:j]相乘呢A[1:k]的结果为r0*rk的矩阵，A[k+1:n]的结果为rk*rn的矩阵，则它们相乘的计算量为p0*pk*pn2.建立递归关系•设计算A[i:j]所需的最少次数为m[i][j],原问题的最优解为m[1][n]。•当i=j时，A[i:j]=Ai,m[i][i]=0,i=1,2,···,n。当ij时m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpjk∈{i,i+1,···,j-1}jipppjkmkimjijimjkijki}]][1[]][[{min0]][[1矩阵连乘问题采用递归方法计算intRecurMatrixChain(inti,int,j,intp[]){if()return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j,p)+p[i-1]*p[i]*p[j];s[i]