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

1、班 级 学 号 姓 名 密封装订线 密封装订线 密封装订线西南交通大学20152016学年第(一)学期考试试卷课程代码 课程名称 算法分析与设计 考试时间 120 分钟 题号一二三四五总成绩得分阅卷教师签字： 一、 填空题（每空1分，共15分）1. 回溯法的求解目标是找出解空间树中满足约束条件的所有解，而 （1） 法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2. 分治算法的基本步骤包括：分解、解决和 （2） 。3. 选择排序、插入排序和归并排序算法中， （3） 算法是分治算法。4. 计算一个算法时间复杂度通常可以计算的 （4） 、基本操作的频度或

2、计算步。5. 贪心算法的基本要素是 （5） 性质和 （6） 性质 。6. 以广度优先或以最小耗费方式搜索问题解的算法称为 （7） 。7. 快速排序算法的性能取决于 （8） 。8. 常见的减治策略分为三类： （9） ， （10） ，减可变规模。9. 堆的构建过程对于堆排序而言是一种 （11） 策略，属于变治思想中的实例化简类型。10. 分支限界法主要有 (12) 分支限界法和 （13） 分支限界法。11. 快速排序算法是基于 (14) 的一种排序算法。12. 动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解 （15） ，然后从这些子问题的解得到原问题的解。二、 选择题（每题2分，共2

3、0分）1、二分搜索算法是利用（ ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2. 衡量一个算法好坏的标准是（ ）。A、运行速度快 B、占用空间少 C、 时间复杂度低 D、代码短3. 以下关于渐进记号的性质是正确的有：（ ）A.fn=gn,gn=hnfn=hnB. fn=Ogn,gn=Ohnhn=OfnC. Ofn+O(gn)=O(minfn,gn)D. fn=Ogngn=O(fn)4. 下面不是分支界限法搜索方式的是（ ）。A、广度优先 B、最小耗费优先C、最大效益优先 D、深度优先5. 记号的定义正确的是（ ）。A、 O(g(n) = f(n) | 存在正常数c和n0使

4、得对所有nn0有：0 f(n) cg(n) ；B、 O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；C、 (g(n) = f(n) | 对于任何正常数c0，存在正数和n0 0使得对所有nn0有：0 f(n)0，存在正数和n0 0使得对所有nn0有：0 cg(n) Length);return;void QSort(SqList *L, int low,int high)int pivotloc;if(lowr0=L-rlow;pivotkey=L-rlow; while(lowhigh) while(lowrhigh=pivotkey) -hi

5、gh;L-rlow=L-rhigh;while(lowrlowrhigh=L-rlow; L-rlow=L-r0;return low;(1) 请问上述程序采用什么算法？（2分）(2) 设L-Length的值为n,请求QuickSort(SqList *L)函数的时间复杂度，写出求解过程。（8分）(3) 设传递到Partion（SqList *L, int low,int high）函数的参数如下：（5分）L-Length: 8;L-r: 12,25,15,20,35,48,23,76,18Low: 1High:7请写出该函数执行结束之后L-r的值以及函数返回的值。2、 阅读下面的程序，按要求

6、回答问题。（共10分）typedef struct ArcNodeint adjvex; float weight; struct ArcNode *nextarc; ArcNode;typedef struct VNodeint visited; char data20; ArcNode *firstarc; VNode,*AdjList;typedef struct ALGraph int vexnum,arcnum;VNode *vertices; ALGraph,*Graph;Graph PrimTree(Graph G) Graph CTree; int i,Maxpos,pos=0

7、; CTree=(Graph)malloc(sizeof(ALGraph); CTree-vexnum=0;CTree-vertices=(AdjList)malloc(sizeof(VNode)*(G-vexnum+1); for(i=0;ivexnum;i+) G-verticesi.visited=0; Maxpos=InsertStr(G-verticespos.data,CTree); for(i=0;iG-vexnum)break; return CTree;int FindPrimWeight(Graph G,Graph CTree,int Maxpos) float Minw;

8、 ArcNode *p,*q=NULL; int rpos,pos,curpos,i,cpos; char *s; curpos=Maxpos; Minw=(float)3.4E38; for(i=0;iverticesi.data,G); p=G-verticespos.firstarc; G-verticespos.visited=1; if(p!=NULL) while(p!=NULL) if(G-verticesp-adjvex.visited=0 & Minwp-weight) Minw=p-weight; q=p; cpos=i; p=p-nextarc; if(q!=NULL)

9、G-verticesq-adjvex.visited=1; s=G-verticesq-adjvex.data; rpos=InsertStr(s,CTree); G-arcnum+; InsNode(cpos,rpos,CTree,q-weight); curpos=curposrpos?curpos:rpos; return curpos;int InsertStr(char *stemp,Graph G) int i;char *ctemp;ctemp=G-vertices0.data;for(i=0;ivexnum;i+)ctemp=G-verticesi.data;if(strcmp

10、(stemp,ctemp)=0) break; if(i=G-vexnum)G-vertices=(AdjList)realloc(G-vertices,sizeof(VNode)*(G-vexnum+1); ctemp=G-verticesi.data; strcpy(ctemp,stemp); G-verticesi.firstarc=NULL; G-verticesi.visited=0; G-vexnum+; return i;void InsNode(int pos1,int pos2, Graph G,float weight) ArcNode *p,*q; p=(ArcNode*

11、)malloc(sizeof(ArcNode); p-weight=weight; p-adjvex=pos2; p-nextarc=NULL; if(G-verticespos1.firstarc=NULL) G-verticespos1.firstarc=p; else q=G-verticespos1.firstarc; while(q-nextarc!=NULL) q=q-nextarc; q-nextarc=p; return;（1） 请问上述程序采用什么算法？（2分）（2） 设传递给Graph PrimTree(Graph G)函数的参数G的值如下图所示，请用图的形式表示函数执行结

12、束之后的返回值。（8分）6G70A0B0C0D0E0F120325518343430416519025143130216018219020四、 算法描述题（共20分）。下图为若干个城市之间的连接关系图。某旅行商希望从城市A出发，访问每一个城市且每个城市只访问1次，然后回到城市A，请按要求回答如下问题：94010CB535468253820A6EDA48251112F1、请用文字描述回溯法求解该问题的步骤，画出其解空间树。（共10分）2、请用文字描述分支限界法求解该问题的步骤，画出其搜索空间。（共10分）五、 算法设计及实现(共20分)1、如下图所示。图中有两行正整数，每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同，这样就可以在这两个正整数之间划一条线，并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。（共20分） 请编写完整程序，求最大的匹配线段数量，并使得这些匹配线段满足如下条件：（1） 每一个a-匹配线段必须与另一个b-匹配线段相交，且a不等于b.（2） 任何两个匹配线段不能从同一个整数出发