《算法分析与设计》期末考试复习题纲(完整版)

1《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（D）等4个特性。A．可行性和安全性B．确定性和易读性C．有穷性和安全性D．有穷性和确定性2.算法分析中，记号O表示（B），记号Ω表示（A）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（B）解题方法：3*2^n*64=3*2^xA．n+8B．n+6C．n+7D．n+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（C）。A．O(logN)B．O(N)C．O(NlogN)D．O(N²logN)5.直接或间接调用自身的算法称为（B）。A．贪心算法B．递归算法C．迭代算法D．回溯法6.Fibonacci数列中，第4个和第11个数分别是（D）。A．5，89B．3，89C．5，144D．3，1447.在有8个顶点的凸多边形的三角剖分中，恰有（B）。A．6条弦和7个三角形B．5条弦和6个三角形C．6条弦和6个三角形D．5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A．重叠子问题B．最优子结构性质C．贪心选择性质D．定义最优解9.下列哪个问题不用贪心法求解（C）。A．哈夫曼编码问题B．单源最短路径问题C．最大团问题D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（B）。A．备忘录法B．动态规划法C．贪心法D．回溯法11.下列算法中不能解决0/1背包问题的是（A）。A．贪心法B．动态规划C．回溯法D．分支限界法12.下列哪个问题可以用贪心算法求解（D）。2A．LCS问题B．批处理作业问题C．0-1背包问题D．哈夫曼编码问题13.用回溯法求解最优装载问题时，若待选物品为m种，则该问题的解空间树的结点个数为（）。A．m!B．2m+1C．2m+1-1D．2m14.二分搜索算法是利用（A）实现的算法。A．分治策略B．动态规划法C．贪心法D．回溯法15.下列不是动态规划算法基本步骤的是（B）。P44A．找出最优解的性质B．构造最优解C．算出最优解(应该是最优值)D．定义最优解16.下面问题（B）不能使用贪心法解决。A．单源最短路径问题B．N皇后问题C．最小花费生成树问题D．背包问题17.使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为（A）。P17A．O(1)，O(logn)B．O(n)，O(logn)C．O(1)，O(nlogn)D．O(n)，O(nlogn)18.优先队列式分支限界法选取扩展结点的原则是（C）。P162A．先进先出B．后进先出C．结点的优先级D．随机19.下面不是分支界限法搜索方式的是（D）。P161A．广度优先B．最小耗费优先C．最大效益优先D．深度优先20.分支限界法解最大团问题时，活结点表的组织形式是（B）。A．最小堆B．最大堆C．栈D．数组21.下列关于计算机算法的描述不正确的是（C）。P1A．算法是指解决问题的一种方法或一个过程B．算法是若干指令的有穷序列C.算法必须要有输入和输出D．算法是编程的思想22.下列关于凸多边形最优三角剖分问题描述不正确的是（A）。A．n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖分对应B．在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦C．该问题可以用动态规划法来求解D．在有n个顶点的凸多边形的三角剖分中，恰有n-2个三角形23.动态规划法求解问题的基本步骤不包括（C）。P44A．递归地定义最优值B．分析最优解的性质，并刻画其结构特征C．根据计算最优值时得到的信息，构造最优解(可以省去的)D．以自底向上的方式计算出最优值24.分治法所能解决的问题应具有的关键特征是（C）。P163A．该问题的规模缩小到一定的程度就可以容易地解决B．该问题可以分解为若干个规模较小的相同问题C．利用该问题分解出的子问题的解可以合并为该问题的解D．该问题所分解出的各个子问题是相互独立的25.下列关于回溯法的描述不正确的是（D）。P114A．回溯法也称为试探法B．回溯法有“通用解题法”之称C．回溯法是一种能避免不必要搜索的穷举式搜索法D．用回溯法对解空间作深度优先搜索时只能用递归方法实现26.常见的两种分支限界法为（D）。P161A.广度优先分支限界法与深度优先分支限界法；B.队列式（FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.队列式（FIFO）分支限界法与优先队列式分支限界法；二、填空题1.f(n)=3n2+10的渐近性态f(n)=O(n2)，g(n)=10log3n的渐近性态g(n)=O(n)。2.一个“好”的算法应具有正确性、可读性、健壮性和高效率和低存储量需求等特性。3.算法的时间复杂性函数表示为C=F(N,I,A)，分析算法复杂性的目的在于比较求解同意问题的两个不同算法的效率的效率。4.构成递归式的两个基本要素是递归的边界条件和递归的定义。5.单源最短路径问题可用分支限界法和贪心算法求解。6.用分治法实现快速排序算法时，最好情况下的时间复杂性为O(nlogn)，最坏情况下的时间复杂性为O(n^2)，该算法所需的时间与运行时间和划分两方面因素有关。P267.0-1背包问题的解空间树为完全二叉树；n后问题的解空间树为排列树；8.常见的分支限界法有队列式（FIFO）分支限界法和优先队列式分支限界法。9.回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝函数。10.分支限界法解最大团问题时，活结点表的组织形式是最大堆；分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆。三、算法填空题1.递归求解Hanoi塔问题/阶乘问题。例1:阶乘函数n!P12阶乘的非递归方式定义：试写出阶乖的递归式及算法。递归式为：边界条件12)2()1(!nnnn00)!1(1!nnnnn4递归方程递归算法：intfactorial(intn){if(n==0)return1;递归出口returnn*factorial(n-1);递归调用}例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15其中Hanoi(intn,inta,intc,intb)表示将塔座A上的n个盘子移至塔座C，以塔座B为辅助。Move(a,c)表示将塔座a上编号为n的圆盘移至塔座c上。voidhanoi(intn,inta,intc,intb){if(n0){hanoi(n-1,a,b,c);move(a,c);hanoi(n-1,b,c,a);}}2.用分治法求解快速排序问题。快速排序算法P25、作业、课件第2章（2）42页-50页templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r)；}}5Partition函数的具体实现templateclassTypeintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到左边区域//将x的元素交换到右边区域while(true){while(a[++i]x&&ir);while(a[--j]x);if(i=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}3.用贪心算法求解最优装载问题。最优装载问题P95课件第4章(2)第3-8页templateclassTypevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i=n;i++)x[i]=0;for(intj=1;j=n&&w[t[j]]=c;j++){x[t[i]]=1;c-=w[t[j]];}}64.用回溯法求解0-1背包/批处理作业调度/最大团问题，要会画解空间树。例1：用回溯法求解0-1背包P133课件第5章(2)第24-38页templatetypenameTypew,typenameTypepclassKnap{private:TypepBound(inti);//计算上界voidBacktrack(inti);Typewc;//背包容量intn;//物品数Typew*w;//物品重量数组Typep*p;//物品价值数组Typewcw;//当前重量Typepcp;//当前价值Typepbestp;//当前最优价值};voidKnapTypew,Typep::Backtrack(inti){if(in){bestp=cp;return;}if(cw+w[i]=c)//进入左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)bestp)//进入右子树Backtrack(i+1);}TypepKnapTypew,Typep::Bound(inti){Typewcleft=c-cw;//剩余的背包容量Typepb=cp;//b为当前价值//依次装入单位重量价值高的整个物品7while(i=n&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}if(i=n)//装入物品的一部分b+=p[i]*cleft/w[i];returnb;//返回上界}classObject//物品类{friendintKnapsack(int*,int*,int,int);public:intoperator(Objecta)const{return(d=a.d);}intID;//物品编号floatd;//单位重量价值};TypepKnapsack(Typepp[],Typeww[],Typewc,intn){//为TypepKnapsack初始化TypewW=0;//总重量TypepP=0;//总价值Object*Q=newObject[n];//创建物品数组，下标从0开始for(inti=1;i=n;i++)//初始物品数组数据{Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W=c)//能装入所有物品returnP;if(W=c)//能装入所有物品returnP;QuickSort(Q,0,n-1);//依物品单位重量价值非增排序8KnapTypew,TypepK;K.p=newTypep[n+1];K.w=newTypew[n+1];for(inti=1;i=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}例2：批处理作业调度课件第5章(2)P2-5问题描述,课本P125-127解空间：排列树算法描述：classFlowshop{staticint[][]m,//各作业所需的处理时间[]x,//当前作业调度[]bestx,//当前最优作业调度[]f2,//机器2完成处理时间f1,//机器1完成处理时间f,//完成时间和bestf,//当前最优的完成时间和n;//作业数staticvoidBacktrack(inti){if(in){for(intj=1;j=n;j++)bestx[j]=x[j];bestf=f;