2015年算法分析与设计期末考试试卷A卷

西南交通大学2015－2016学年第(一)学期考试试卷课程代码3244152课程名称算法分析与设计考试时间120分钟题号一二三四五总成绩得分·阅卷教师签字：一、填空题（每空1分，共15分）1.回溯法的求解目标是找出解空间树中满足约束条件的所有解，而（1）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2.分治算法的基本步骤包括：分解、解决和（2）。3.选择排序、插入排序和归并排序算法中，（3）算法是分治算法。4.计算一个算法时间复杂度通常可以计算的（4）、基本操作的频度或计算步。5.贪心算法的基本要素是（5）性质和（6）性质。6.以广度优先或以最小耗费方式搜索问题解的算法称为（7）。7.快速排序算法的性能取决于（8）。8.常见的减治策略分为三类：（9），（10），减可变规模。9.堆的构建过程对于堆排序而言是一种（11）策略，属于变治思想中的实例化简类型。10.分支限界法主要有(12)分支限界法和（13）分支限界法。11.快速排序算法是基于(14)的一种排序算法。12.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解（15），然后从这些子问题的解得到原问题的解。二、选择题（每题2分，共20分）1、二分搜索算法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2.衡量一个算法好坏的标准是（）。班级学号姓名密封装订线密封装订线密封装订线A、运行速度快B、占用空间少C、时间复杂度低D、代码短3.以下关于渐进记号的性质是正确的有：（）A.f(n)=Θ(g(n)),g(n)=Θ(h(n))⟹𝑓(𝑛)=Θ(h(n))B.f(n)=O(g(n)),g(n)=O(h(n))⟹ℎ(𝑛)=O(f(n))C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.f(n)=O(g(n))⟺𝑔(𝑛)=𝑂(𝑓(𝑛))4.下面不是分支界限法搜索方式的是（）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5.记号的定义正确的是（）。A、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；B、O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；C、(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0f(n)cg(n)}；D、(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0cg(n)f(n)}；6.以深度优先方式系统搜索问题解的算法称为()。A、分支界限算法B、概率算法C、贪心算法D、回溯算法7.矩阵连乘问题的算法可由（）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法8.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为()。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）9.合并排序算法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法10.优先队列式分支限界法选取扩展结点的原则是（）。A、先进先出B、后进先出C、结点的优先级D、随机三、算法及程序分析（共25分）。1、阅读下面的程序，按要求回答问题：（共15分）typedefstructSqList{int*r;intLength;}SqList;voidQuickSort(SqList*L){QSort(L,1,L-Length);return;}voidQSort(SqList*L,intlow,inthigh){intpivotloc;if(lowhigh){pivotloc=Partion(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}return;}intPartion(SqList*L,intlow,inthigh){intpivotkey;L-r[0]=L-r[low];pivotkey=L-r[low];while(lowhigh){while(lowhigh&&L-r[high]=pivotkey)--high;L-r[low]=L-r[high];while(lowhigh&&L-r[low]=pivotkey)++low;L-r[high]=L-r[low];}L-r[low]=L-r[0];returnlow;}(1)请问上述程序采用什么算法？（2分）(2)设L-Length的值为n,请求QuickSort(SqList*L)函数的时间复杂度，写出求解过程。（8分）(3)设传递到Partion（SqList*L,intlow,inthigh）函数的参数如下：（5分）L-Length:8;L-r:{12,25,15,20,35,48,23,76,18}Low:1High:7请写出该函数执行结束之后L-r的值以及函数返回的值。2、阅读下面的程序，按要求回答问题。（共10分）typedefstructArcNode{intadjvex;floatweight;structArcNode*nextarc;}ArcNode;typedefstructVNode{intvisited;chardata[20];ArcNode*firstarc;}VNode,*AdjList;typedefstructALGraph{intvexnum,arcnum;VNode*vertices;}ALGraph,*Graph;GraphPrimTree(GraphG){GraphCTree;inti,Maxpos,pos=0;CTree=(Graph)malloc(sizeof(ALGraph));CTree-vexnum=0;CTree-vertices=(AdjList)malloc(sizeof(VNode)*(G-vexnum+1));for(i=0;iG-vexnum;i++)G-vertices[i].visited=0;Maxpos=InsertStr(G-vertices[pos].data,CTree);for(i=0;i=Maxpos;i++){Maxpos=FindPrimWeight(G,CTree,i);if(MaxposG-vexnum)break;}returnCTree;}intFindPrimWeight(GraphG,GraphCTree,intMaxpos){floatMinw;ArcNode*p,*q=NULL;intrpos,pos,curpos,i,cpos;char*s;curpos=Maxpos;Minw=(float)3.4E38;for(i=0;i=Maxpos;i++){pos=InsertStr(CTree-vertices[i].data,G);p=G-vertices[pos].firstarc;G-vertices[pos].visited=1;if(p!=NULL){while(p!=NULL){if(G-vertices[p-adjvex].visited==0&&Minwp-weight){Minw=p-weight;q=p;cpos=i;}p=p-nextarc;}}}if(q!=NULL){G-vertices[q-adjvex].visited=1;s=G-vertices[q-adjvex].data;rpos=InsertStr(s,CTree);G-arcnum++;InsNode(cpos,rpos,CTree,q-weight);curpos=curposrpos?curpos:rpos;}returncurpos;}intInsertStr(char*stemp,GraphG){inti;char*ctemp;ctemp=G-vertices[0].data;for(i=0;iG-vexnum;i++){ctemp=G-vertices[i].data;if(strcmp(stemp,ctemp)==0)break;}if(i==G-vexnum){G-vertices=(AdjList)realloc(G-vertices,sizeof(VNode)*(G-vexnum+1));ctemp=G-vertices[i].data;strcpy(ctemp,stemp);G-vertices[i].firstarc=NULL;G-vertices[i].visited=0;G-vexnum++;}returni;}voidInsNode(intpos1,intpos2,GraphG,floatweight){ArcNode*p,*q;p=(ArcNode*)malloc(sizeof(ArcNode));p-weight=weight;p-adjvex=pos2;p-nextarc=NULL;if(G-vertices[pos1].firstarc==NULL)G-vertices[pos1].firstarc=p;else{q=G-vertices[pos1].firstarc;while(q-nextarc!=NULL)q=q-nextarc;q-nextarc=p;}return;}（1）请问上述程序采用什么算法？（2分）（2）设传递给GraphPrimTree(GraphG)函数的参数G的值如下图所示，请用图的形式表示函数执行结束之后的返回值。（8分）四、算法描述题（共20分）。下图为若干个城市之间的连接关系图。某旅行商希望从城市A出发，访问每一个城市且每个城市只访问1次，然后回到城市A，请按要求回答如下问题：1、请用文字描述回溯法求解该问题的步骤，画出其解空间树。（共10分）2、请用文字描述分支限界法求解该问题的步骤，画出其搜索空间。（共10分）五、算法设计及实现(共20分)1、如下图所示。图中有两行正整数，每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同，这样就可以在这两个正整数之间划一条线，并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。（共20分）6G70A0B0C0D0E0F120325518^343430^416519^025143^130216^018219^020ABCDEF10124820389402584635511256请编写完整程序，求最大的匹配线段数量，并使得这些匹配线段满足如下条件：（1）每一个a-匹配线段必须与另一个b-匹配线段相交，且a不等于b.（2）任何两个匹配线段不能从同一个整数出发。如下图中3-匹配线段是不合法的匹配线段。不满足上述两个条件的匹配线段则不能称之为匹配线段，不计入匹配线段的数量。例如有两行整数分别如下，则该例中其匹配线段的数量为6.131313313131下面的匹配线段数量则为0。因为虽然最多可划4条匹配线段，但不满足这其中2条匹配线段相交且a-匹配线段不等于b匹配线段的条件，因此其匹配线段的数量为0.11331133