下载文档原格式
算法设计与分析_武汉理工大学中国大学mooc课后章节答案期末考试题库2023年1.在寻找 n 个元素中第 k 小元素问题中，如快速排序算法思想，运用分治算法对 n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
答案:以上皆可行。
但不同方法，算法复杂度上界可能不同2.减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（）值。
答案:a3.使用分治法求解不需要满足的条件是（）。
答案:子问题不能够重复4.改进分治算法的方法有（）。
答案:减少子问题的个数_减少合并的时间_改进分治的均衡度5.阅读以下代码:int Fun(int n){ if(n <= 1) return 1; int First = Fun(n-1); intSecond = Fun(n-2); int iSum = First + Second; return iSum;}调用该函数，假设输入参数n值为5，当程序第二次执行语句 iSum = First + Second时，iSum的值为（）。
答案:36.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题（）。
答案:问题规模不同，问题性质相同7.【图片】表示当输入规模为【图片】时的算法效率，以下算法效率最优的是（）答案:8.以下哪些是算法的基本特点（）。
答案:有穷性_确定性_可行性9.以下关于渐近记号的性质，正确的有（）答案:10.下列关于算法的说法中正确的有（）。
答案:算法必须在有限步操作之后停止_算法的每一步操作必须是明确的，不能有歧义或含义模糊_算法执行后一定产生确定的结果11.若一个算法的递归方程为【图片】，则其时间复杂度为（）答案:12.以下关于记号【图片】的定义，正确的是（）答案:存在正常数和使得对所有有：。
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：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.一个算法就是一个有穷规矩的聚集,个中之规矩划定懂得决某一特别类型问题的一系列运算,此外,算法还应具有以下五个重要特点:_________,________,________,____ ______,__________.,权衡一个算法利害的尺度是______________________.3.某一问题可用动态计划算法求解的明显特点是____________________________________.4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列_____________________________.5.用回溯法解问题时,应明白界说问题的解空间,问题的解空间至少应包含___________.6.动态计划算法的根本思惟是将待求解问题分化成若干____________,先求解___________,然后从这些____________的解得到原问题的解.7.以深度优先方法体系搜刮问题解的算法称为_____________.8.0-1背包问题的回溯算法所需的盘算时光为_____________,用动态计划算法所需的盘算时光为____________.9.动态计划算法的两个根本要素是___________和___________.10.二分搜刮算法是应用_______________实现的算法.二.分解题（50分）1.写出设计动态计划算法的重要步调.2.流水功课调剂问题的johnson算法的思惟.3.若n=4,在机械M1和M2上加工功课i所需的时光分离为a i和b i,且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4个功课的最优调剂计划,并盘算最优值.4.应用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量构成,请求用一棵完整二叉树暗示其解空间（从根动身,左1右0）,并画出其解空间树,盘算其最优值及最优解.5.设S=｛X1,X2,···,X n｝是严厉递增的有序集,应用二叉树的结点来存储S中的元素,在暗示S的二叉搜刮树中搜刮一个元素X,返回的成果有两种情况,（1）在二叉搜刮树的内结点中找到X=X i,其概率为b i.（2）在二叉搜刮树的叶结点中肯定X∈（X i,X i+1）,其概率为a i.在暗示S的二叉搜刮树T中,设存储元素X i的结点深度为C i;叶结点（X i,X i+1）的结点深度为d i,则二叉搜刮树T的平均路长p为若干？假设二叉搜刮树T[i][j]=｛X i,X i+1,···,X j｝最优值为m[i][j],W[i][j]=a i-1+b i+···+b j+a j,则m[i][j](1<=i<=j<=n)递归关系表达式为什么？6.描写0-1背包问题.三.简答题（30分）1.流水功课调剂中,已知有n个功课,机械M1和M2上加工功课i 所需的时光分离为a i和b i,请写出流水功课调剂问题的johnson轨则中对a i和b i的排序算法.（函数名可写为sort(s,n)）2.最优二叉搜刮树问题的动态计划算法（设函数名binarysearchtree)）答案：一.填空1．肯定性有穷性可行性0个或多个输入一个或多个输出2.时光庞杂性空间庞杂性时光庞杂度高下具有最优子构造性质4.{BABCD}或{CABCD}或{CADCD｝5.一个（最优）解6.子问题子问题子问题7.回溯法8. o(n*2n) o(min{nc,2n})9.最优子构造重叠子问题10.动态计划法二.分解题1.①问题具有最优子构造性质;②构造最优值的递归关系表达式;③最优值的算法描写;④构造最优解;2.①令N1={i|a i<b i},N2={i|a i>=b i};②将N1中功课按a i的非减序排序得到N1’,将N2中功课按b i的非增序排序得到N2’;③N1’中功课接N2’中功课就构成了知足Johnson轨则的最优调剂.3.步调为：N1={1,3},N2={2,4};N 1’={1,3},N 2’={4,2}; 最优值为：384.解空间为{(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,0） 5.二叉树T 的平均路长P=∑=+n i 1Ci)(1*bi +∑=nj 0dj *aj{m[i][j]=0(i>j)6.已知一个背包的容量为C,有n 件物品,物品i 的重量为W i ,价值为V i ,求应若何选择装入背包中的物品,使得装入背包中物品的总价值最大. 三.简答题m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)1.void sort(flowjope s[],int n){int i,k,j,l;for(i=1;i<=n-1;i++)//-----选择排序{k=i;while(k<=n&&s[k].tag!=0) k++;if(k>n) break;//-----没有a i,跳出else{for(j=k+1;j<=n;j++)if(s[j].tag==0)if(s[k].a>s[j].a) k=j;swap(s[i].index,s[k].index);swap(s[i].tag,s[k].tag); } }l=i;//-----记下当前第一个b i的下标for(i=l;i<=n-1;i++){k=i;for(j=k+1;j<=n;j++)if(s[k].b<s[j].b) k=j;swap(s[i].index,s[k].index); //-----只移动index和tag swap(s[i].tag,s[k].tag); }}2.void binarysearchtree(int a[],int b[],int n,int **m,int**s,int **w){int i,j,k,t,l;for(i=1;i<=n+1;i++){ w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){ t=m[i][k-1]+m[k+1][j]+w[i][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}一、填空题（本题15分,每小题1分）1、算法就是一组有穷的,它们划定懂得决某一特定类型问题的 .2、在进行问题的盘算庞杂性剖析之前,起首必须树立求解问题所用的盘算模子.3个根本盘算模子是...3、算法的庞杂性是的器量,是评价算法好坏的重要根据.4、盘算机的资本最重要的是和资本.因而,算法的庞杂性有和之分.5、f(n)= 6×2n+n2,f(n)的渐进性态f(n)= O( )6、贪婪算法老是做出在当前看来的选择.也就是说贪婪算法其实不从整体最优斟酌,它所做出的选择只是在某种意义上的. 7、很多可以用贪婪算法求解的问题一般具有2个重要的性质：性质和性质.二.简答题（本题25分,每小题5分）1、简略描写分治法的根本思惟.2、简述动态计划办法所应用的最优化道理.3、何谓最优子构造性质？4、简略描写回溯法根本思惟.5、何谓P.NP.NPC问题三.算法填空（本题20分,每小题5分）1.n后问题回溯算法(1)用二维数组A[N][N]存储皇后地位,若第i行第j列放有皇后,则A[i][j]为非0值,不然值为0.(2)分离用一维数组M[N].L[2*N-1].R[2*N-1]暗示竖列.左斜线.右斜线是否放有棋子,有则值为1,不然值为0.for(j=0;j<N;j++)if( 1 ) /*安然检讨*/{ A[i][j]=i+1; /*放皇后*/2 ;if(i==N-1)输出成果;else 3 ;; /*试探下一行*/4 ; /*去皇后*/5 ;;}2.数塔问题.有形如下图所示的数塔,从顶部动身,在每一结点可以选择向左走或是向右走,一路走到底层,请求找出一条路径,使路径上的值最大.for(r=n-2;r>=0;r--) //自底向上递归盘算for(c=0; 1 ;c++)if( t[r+1][c]>t[r+1][c+1]) 2 ;else 3 ;3.Hanoi算法Hanoi(n,a,b,c)if （n==1） 1 ;else{ 2 ;3 ;Hanoi(n-1,b, a, c);}4.Dijkstra算法求单源最短路径d[u]:s到u的距离 p[u]:记载前一节点信息Init-single-source(G,s)for each vertex v∈V[G]do { d[v]=∞; 1 }d[s]=0Relax(u,v,w)if d[v]>d[u]+w(u,v)then { d[v]=d[u]+w[u,v];2}dijkstra(G,w,s)1. Init-single-source(G,s)2. S=Φ3.Q=V[G]4.while Q<> Φdo u=min(Q)S=S∪{u}for each vertex 3do4四.算法懂得题（本题10分）根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树.请求中央被舍弃的结点用×标识表记标帜,获得中央解的结点用单圆圈○框起,最优解用双圆圈◎框起.五.算法懂得题（本题5分）设有n=2k个运发动要进行轮回赛,现设计一个知足以下请求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次;②每个选手一天至多只能赛一次;③轮回赛要在最短时光内完成.（1）假如n=2k,轮回赛起码须要进行几天;（2）当n=23=8时,请画出轮回赛日程表.六.算法设计题（本题15分）分离用贪婪算法.动态计划法.回溯法设计0-1背包问题.请求：解释所应用的算法计谋;写出算法实现的重要步调;剖析算法的时光.七.算法设计题（本题10分）经由过程键盘输入一个高精度的正整数n(n的有用位数≤240),去失落个中随意率性s个数字后,剩下的数字按原阁下次序将构成一个新的正整数.编程对给定的n 和s,查找一种计划,使得剩下的数字构成的新数最小.【样例输入】178543S=4【样例输出】13答案：一.填空题（本题15分,每小题1分）1．规矩一系列运算2. 随机存取机RAM(Random Access Machine);随机存取存储程序机RASP(Random Access Stored Program Machine);图灵机(Turing Machine)3. 算法效力4. 时光.空间.时光庞杂度. 空间庞杂度5．2n6．最好局部最优选择7. 贪婪选择最优子构造二.简答题（本题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、P(Polynomial问题)：也等于多项式庞杂程度的问题.NP就是Non-deterministic Polynomial的问题,也等于多项式庞杂程度的非肯定性问题.NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才干得出答案,如许的问题是NP里面最难的问题,这种问题就是NPC问题.三.算法填空（本题20分,每小题5分）1.n后问题回溯算法(1) !M[j]&&!L[i+j]&&!R[i-j+N](2) M[j]=L[i+j]=R[i-j+N]=1;(3) try(i+1,M,L,R,A)(4) A[i][j]=0(5) M[j]=L[i+j]=R[i-j+N]=02.数塔问题.（1）c<=r(2)t[r][c]+=t[r+1][c]（3）t[r][c]+=t[r+1][c+1]3.Hanoi算法（1）move(a,c)（2）Hanoi(n-1, a, c , b)（3）Move(a,c)4.（1）p[v]=NIL（2）p[v]=u(3) v∈adj[u]（4）Relax(u,v,w)四.算法懂得题（本题10分）五.（1）8天（2分）;（2）当n=23=8时,轮回赛日程表（3分）.六.算法设计题（本题15分）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（1）贪婪算法 O（nlog（n））➢起首盘算每种物品单位重量的价值Vi/Wi,然后,依贪婪选择计谋,将尽可能多的单位重量价值最高的物品装入背包.若将这种物品全体装入背包后,背包内的物品总重量未超出C,则选择单位重量价值次高的物品并尽可能多地装入背包.依此计谋一向地进行下去,直到背包装满为止.➢具体算法可描写如下：void Knapsack(int n,float M,float v[],float w[],float x[]){Sort(n,v,w);int i;for (i=1;i<=n;i++) x[i]=0;float c=M;for (i=1;i<=n;i++){if (w[i]>c) break;x[i]=1;c-=w[i];}if (i<=n) x[i]=c/w[i];}（2）动态计划法 O(nc)m(i,j)是背包涵量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值.由0-1背包问题的最优子构造性质,可以树立盘算m(i,j)的递归式如下.void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c);for (j=0;j<=jMax;j++)/*m(n,j)=0 0=<j<w[n]*/m[n][j]=0;for (j=w[n];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/m[n][j]=v[n];for (i=n-1;i>1;i--){ int jMax=min(w[i]-1,c);for (j=0;j<=jMax;j++)/*m(i,j)=m(i+1,j) 0=<j<w[i]*/m[i][j]=m[i+1][j];for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}（3）回溯法 O(2n)cw:当前重量 cp:当前价值 bestp：当前最优值void backtrack(int i)//回溯法i初值1{ if(i > n) //到达叶结点{ 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);}七.算法设计题（本题10分）为了尽可能地逼近目的,我们拔取的贪婪计谋为：每一步老是选择一个使剩下的数最小的数字删去,即按高位到低位的次序搜刮,若列位数字递增,则删除最后一个数字,不然删除第一个递减区间的首字符.然后回到串首,按上述规矩再删除下一个数字.反复以长进程s次,剩下的数字串等于问题的解了.具体算法如下：输入s, n;while（ s > 0 ）{ i=1; //从串首开端找while (i < length(n)) && (n[i]<n[i+1]){i++;}delete(n,i,1); //删除字符串n的第i个字符s--;}while (length(n)>1)&& (n[1]=‘0’)delete(n,1,1); //删去串首可能产生的无用零输出n;。
装订线华南农业大学期末考试试卷（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= 。
附表５:考试课程： 班级： 姓名： 学号：------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------、⑴ 证明:令F(N)=Ｏ(ｆ）,则存在自然数N1、Ｃ1,使得对任意的自然数N 1N ≥,有： Ｆ（Ｎ));(1N f C ≤……………………………．.（2分）同理可令G(Ｎ)＝O(ｇ), 则存在自然数N ２、C2,使得对任意的自然数N 2N ≥,有:G(N));(2N g C ≤ …………………………….．（3分）令 Ｃ3＝m ａx{C1,C2},N3=ma ｘ{N1,N2｝，则对所有的N 3N ≥,有： F(Ｎ));(3)(1N f C N f C ≤≤G （N ）);(3)(2N g C N g C ≤≤ ……………………………．.（5分） 故有：O （f)＋O(g)=F(Ｎ)+Ｇ（N))())()((3)(3)(3g f O N g N f C N g C N f C +=+=+≤ 因此有:O(f)+O(g)=Ｏ(f+g ） ……………………………..(7分)⑵ 解:① 因为:;01033)103(lim 222=+-+∞→nn n n n n 由渐近表达式的定义易知: 103322+n n 是的渐近表达式。
……………………………..（3分)② 因为:;0/12121)/121(lim=+-+∞→nn n 由渐近表达式的定义易知：２1是2１+1/n 的渐近表达式。
……………………………..（6分)2、解：经分析结论为:(1）);5(log log 2+=n n θ………………………….(5分)(2))(log 2n n O =；………………………….(10分）（3）)(log 2n n Ω=;………………………….(１5分）3、解：用分治法求解的算法代码如下:int partit ｉo ｎ(float A[],int p,ｉn ｔ r ） {i ｎｔ ｉ＝p,j ＝ｒ+１; f ｌo ａt x ＝a[ｐ］; w ｈile （1) {while(a[＋+i]<x&＆i ＜r)； w ｈile(a[-－ｊ］>ｘ);if(i>＝ｊ）break;ａ［i］];……………………………．.(４分)[ja};a[ｐ]=a[ｊ];a［j]=x;retuｒｎｊ;……………………………..(7分)}voｉｄＱuickｓorｔ（floａｔａ[］, int p, inｔr){if( p<r）{ｉnt q＝ｐarｔitioｎ(a,ｐ,r);……………………………..（10分）Ｑuicksoｒt(ａ,p,q-1);Qｕickｓort(a,q+１,r);｝}；Qｕiｃksｏrｔ(a，0,n－1);……………………………..(1３分）4、解：用动态规划算法求解的算法代码如下：ｉnt lｃs_ｌen(char *a，cｈａr *b,int c[][N］){ｉｎｔm＝ｓtrlen(a)，n＝strlen(b）,i，ｊ;ｆor（ｉ＝０;i<=ｍ;i++) c[i］[0]＝0;fｏｒ(j＝１；j<=n;j++) ｃ[0][j］=0;…………………………….．(4分)for(ｉ=1;i<＝ｍ;i+＋)for(j=1;ｊ<=n;j++)if(a[i－1]= =b[j-１])ｃ[i]［ｊ]=ｃ[ｉ-１]［j-1］+1;else iｆ(c[i-1］[j］>=c[ｉ][ｊ-1])ｃ[i][j]＝c[i-1][j］;eｌse c［i][j］=ｃ[ｉ][j-１];……………………………..(7分) rｅturn c［ｍ]［n];……………………………..(8分)}；cｈar *bｕｉld＿ｌｃｓ(cｈar s[]，char *a,char ＊b)｛intｋ，i=sｔrlen(a）,j=strlｅn(b),ｃ[Ｎ］[N］;k=lcs_ｌen(a,b,c）;s［k]=’\0’;whiｌe(k>0){if（c[i］[ｊ]＝=c[i－1］[j])i－-;……………………………..（11分)ｅｌse iｆ（ｃ[ｉ][j]＝＝c[i][ｊ－1]) j--;elｓe{s[--k］＝ａ[i-1]；i－-,j--;}｝rｅtuｒｎs；……………………………..(１5分）}5、解：iｎt gｒeeｄy（vecteｒ<int>x,int n){int sum＝０,ｋ=x.sｉze（);for(ｉnt j=０;j<k;j+＋)ｉf（ｘ[ｊ]>n）{cｏｕt<<”No soｌuｔion”＜<endl;re ｔur ｎ -1；……………………………．.(6分) }for(int i=0,ｓ＝０；i<k ；i ＋＋){ s+=x[ｉ];if(ｓ>n){ sum ＋+;s=x[i];}……………………………..（9分)}return sum;……………………………..（1２分)} 6、解：此题用动态规划算法求解:i nt di ｓｔ（ ） {i ｎt m=a.si ｚe （ )； int n=b.s ｉze( );vec ｔor<i ｎt>d(ｎ+1,０);for(int i ＝1;ｉ＜=ｎ;i ＋+) d[i]=i;……………………………..（５分) f ｏr(i=1;i<＝ｍ；ｉ++){ int ｙ＝i －１;f ｏｒ(ｉnt j ＝１;ｊ<=n;j ＋+){ int x ＝y; y=ｄ[j];ｉnt z=j>1?d[j-1］:ｉ; …………………………….．(１０分） int del=a[ｉ-１］= =b[j-1］?０：1;d ［j ］＝ｍｉn(x+d ｅl,y+１,z+1); ……………………………..（13分) } }ｒｅt ｕrn d[n]; ……………………………..（1６分） }７、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：⎣⎦2/)(;3)(i i g i i f ==。
2022年广州大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、连续存储设计时，存储单元的地址（）。
A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一个具有1025个结点的二叉树的高h为（）。
A.11B.10C.11至1025之间D.10至1024之间10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
2022年华南理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。
A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.46、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一个具有1025个结点的二叉树的高h为（）。
A.11B.10C.11至1025之间D.10至1024之间10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
华南理工大学数值分析教学内容及复习提纲全日制硕士生“数值分析”教学内容与基本要求一、教学重点内容及其要求（一）引论1、误差的基本概念理解截断误差、舍入误差、绝对（相对）误差和误差限、有效数字、算法的数值稳定性等基本概念。
2、数值算法设计若干原则掌握数值计算中应遵循的几个原则：简化计算步骤以节省计算量（秦九韶算法），减少有效数字的损失选择数值稳定的算（避免相近数相减），法。
重点：算法构造（如多项式计算）、数值稳定性判断（舍入误差的分析）（二）插值方法1、插值问题的提法理解插值问题的基本概念、插值多项式的存在唯一性。
2、Lagrange插值熟悉Lagrange插值公式（线性插值、抛物插值、n次Lagrange 插值），掌握其余项表达式（及各种插值余项表达式形式上的规律性）。
3、Newton插值熟悉Newton插值公式，了解其余项公式，会利用均差表和均差的性质计算均差。
4、Hermite插值掌握两点三次Hermite插值及其余项表达式，会利用承袭性方法构造非标准Hermite插值。
5、分段线性插值知道Runge现象，了解分段插值的概念，掌握分段线性插值（分段表达式）。
6、三次样条函数与三次样条插值概念了解三次样条函数与三次样条插值的定义。
重点：多项式插值问题（唯一性保证、构造、误差余项估计）（三）曲线拟合与函数逼近1、正交多项式掌握函数正交和正交多项式的概念（函数内积、2-范数、权函数，正交函数序列，正交多项式），了解Legendre多项式（授课时，将其放在课高斯型数值积分这部分介绍）。
2、曲线拟合的最小二乘法熟练掌握曲线拟合最小二乘法的原理和解法（只要求线性最小二乘拟合），会求超定方程组的最小二乘解（见教材P103）。
3、连续函数的最佳平方逼近了解最佳平方逼近函数的概念，掌握最佳平方逼近多项式的求法（从法方程出发）。
重点：最小二乘拟合法方程的推导、求解；拟合与插值问题的异同。
（四）数值微积分1、数值求积的基本思想、插值型求积公式与代数精度掌握插值型求积公式（系数表达式），理解代数精度概念，会利用代数精度构造求积公式。
华工 2023秋算法设计与分析平时作业作业一题目描述请设计一个算法，找出一个无序数组中的第K大元素。
算法设计与分析我们可以使用快速选择算法来解决这个问题。
快速选择算法的基本思想是选择一个基准元素，将数组中小于基准元素的值放在左边，大于基准元素的值放在右边，然后通过递归地将基准元素所在的位置与K进行比较，从而确定K所在的位置。
具体的步骤如下：1. 选择一个基准元素（可以是数组中的任意一个元素）。
2. 将数组中小于基准元素的值放在左边，大于基准元素的值放在右边。
可以使用双指针法来实现这一步骤。
3. 比较基准元素所在的位置与K的大小关系：- 如果基准元素所在的位置等于K，则找到了第K大元素，返回。
- 如果基准元素所在的位置大于K，则在基准元素的左边继续进行快速选择算法。
- 如果基准元素所在的位置小于K，则在基准元素的右边继续进行快速选择算法。
该算法的时间复杂度为O(n)，其中n为数组的长度。
在最坏情况下，时间复杂度为O(n^2)，但通过随机选择基准元素和合理的划分方式，可以使得算法的平均时间复杂度为O(n)。
示例代码def quick_select(nums, left, right, k):if left == right:return nums[left]随机选择基准元素pivot_index = random.randint(left, right)pivot = nums[pivot_index]将基准元素放在最左边nums[left], nums[pivot_index] = nums[pivot_index], nums[left]划分数组i = leftj = rightwhile i < j:while i < j and nums[j] <= pivot:j -= 1while i < j and nums[i] >= pivot:i += 1nums[i], nums[j] = nums[j], nums[i]将基准元素放在正确的位置nums[left], nums[i] = nums[i], nums[left]if i == k:return nums[i]elif i > k:return quick_select(nums, left, i - 1, k)else:return quick_select(nums, i + 1, right, k)def find_kth_largest(nums, k):return quick_select(nums, 0, len(nums) - 1, len(nums) - k)测试nums = [3, 1, 5, 4, 2]k = 2result = find_kth_largest(nums, k)print(result)结果分析对于给定的无序数组[3, 1, 5, 4, 2]，要找到第2大的元素。
1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ A ）。
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．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
《算法设计与分析》历年期末试题整理(含答案)（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、分治法的基本思想：是将一个规模为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、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。
这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
