算法设计与分析试卷

算法设计与分析期末试卷一.选择题（15*2分）下列不属于一个好的算法应具有的特性的是（C）正确性B.简明性C无限性D最优性矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动态规划算法”贪心算法D、回溯算法广度优先是（A）的一搜索方式。A、分支界限法B、动态规划法”贪心法D、回溯法学校要举行运动会，请你设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是（C）分析问题，编写程序，设计算法，调试程序设计算法，编写程序，提出问题，调试程序提出问题，设计算法，编写程序，调试程序设计算法，提出问题，编写程序，调试程序用计算机程序解决实际问题的过程中，需要进行算法设计，算法指的是（A）A、解决问题的方法和步骤B、数值计算的方法C、实际问题的描述D、最终结果算法分析是（C）。将算法用某种程序设计语言恰当地表示出来在抽象数据集合上执行程序，以确定是否会产生错误的结果对算法需要多少计算时间和存储空间作定量分析证明算法对所有可能的合法输入都能算出正确的答案用贪心法设计算法的关键是（B）。A.将问题分解为多个子问题来分别处理B.选好贪心准则C.获取各阶段间的递推关系式D.满足最优性原理考虑背包问题：n=6,M=10,V(1:6)二(15,59,21,30,60,5),W(1:6)=(1,5,2,3,6,1)。该问题的最大效益值为(C)。若把它看着是0/1背包问题，则最大效益值为(B)。A.101B.110C.115D.120每个归并步恰包含k个文件的归并模式被称为k元归并模式。考虑用贪心法求解文件序列的最优2元归并问题。当要对8个长度为L(1:8)=(3,7,8,9,14,18,25,28)文件进行归并时，记录移动的总数是(D)。A.198B.112C.210D.310找最小生成树的算法Kruskal的时间复杂度为(D)。A.O(n2)B.O(mlogn)C.O(nlogm)D.O(mlogm)算法确认是(B)o将算法用某种程序设计语言恰当地表示出来证明算法对所有可能的合法输入都能算出正确的答案对算法需要多少计算时间和存储空间作定量分析。.在抽象数据集合上执行程序，以确定是否会产生错误的结果算法与程序的区别在于算法具有(C)。A.能行性B.确定性C.有穷性。.输入和输出设A[1..60]={11,12,,70}。算法折半查找在A上搜索x=33、7、70、77时执行的元素比较次数分别为a、b、c、山则(C)oA.a<b<c<dB.a>b=c=dC.a<b=c=dD.a<c<b=d算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的元素比较次数为(D)oA.14B.28C.7D.22二分搜索算法是利用(A)实现的算法。A.分治法B.动态规划法C.贪心法D.回溯法二、填空题（每空2分，共15个空）算法一般分为：算法和算法。一个合法的递归定义包括两部分：和一个算法的是指算法运行所需要的时间。如果无向连通图G中不包含任何关节点，则称该图G为的基本运算是把两个或多个有序序列合并成一个有序序列。和要求问题最优解具有最优子结构特性。使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为下面程序段的所需要的计算时间为intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++)(thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}所谓最优子结构性质是指回溯法的算法框架按照问题的解空间一般分为算法框架与算法框架11..若序列A={xzyzzyx},B={zxyyzxz}，请给出序列A和B的一个最长公共子序列。填空题答案：1、精确启发式。2、基础情况递归部分。3、时间复杂度4、双连通图。5、合并排序6、贪心法动态规划法7、回溯法。8、O（n2）9、问题的最优解包含了其子问题的最优解10、子集树排列树11、XYZZ二.算法设计用欧几里德迭代算法求两个数的最小公倍数#include<iostream>usingnamespacestd;intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;while(m%t||n%t)t--;returnt;}intmain(){inta,b;cout<<"Inputa&b(0<=a<b):〃；cin>>a>>b;intm=a*b/Gcd(a,b);cout<<"TheLeastCommonMultipleis:"<<m<<endl;return0;}用分治法求第K小元素#include<iostream>usingnamespacestd;voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}intPartition(intR[],intlow,inthigh){inti=low,j=high,pivot=R[low];while(i<j){while(i<j&&R[j]>=pivot){j--;}if(i<j){swap(R[i++],R[j]);}while(i<j&&R[i]〈=pivot){i++;}if(i<j){swap(R[i],R[j--]);}}returnj;}intSelect(inta[],intp,intr,intk){if(p==r)returna[p];inti=Partition(a,p,r),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}intmain(){intn,k;//n为数的总个数，k为第几小cout<<"n=";cin>>n;int*a=newint[n];cout<<"Thenumberis：";for(inti=0;i<n;i++){cin>>a[i];}cout<<"k=";cin>>k;cout<<"第〃<<k<<〃小为：〃<<Select(a,0,nT,k);cout<<endl;return0;}四.算法应用题假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M=150,使用回溯方法求解此背包问题。请写出状态空间搜索树(10分)。物品ABCDEFG重3365412量5000005价1435343值0000500答：按照单位效益从大到小依次排列这7个物品为：FBGDECAo将它

们的序号分别记为1〜7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：=177.5(1,1,1,1,0,1|,0)40+40+30+50+30=177.5(1,1,1,1,0,1|,0)40+40+30+50+30x150—11560b.c.d.e.f.g.h.40+40+30+50+10=17040+40+30+35+30x150一105=167.56040+40+50+35+30x150—130=1756040+40+50+35+10x150一130=170.713540+40+50+30=1603d'1'1'"/(1,1,0,1,13,0)(1,1,0,1,1,0,：)(1,1,0,1,0,1,0)150—140°4°+40+35+30+10x—35—=146.85(1,1,。,。,1,1,；)i.J.40+30+50+35+30x^50^=167.5(1,0,1』，启⑵__150—145__i.J.40+30+50+35+30x-60-=157.5(。'1'1'1'1'*。)在Q1处获得该问题的最优解为（1，1，1，1，。，。，1）,背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170,重量为150。已知Ak="))r,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=12,Jiri+1r5=5,r6=50,r7=6,求矩阵链积A1XA2XA3XA4XA5XA6的最佳求积顺序。(要求：