1、班 级 学 号 姓 名 密封装订线 密封装订线 密封装订线西南交通大学20152016学年第(一)学期考试试卷课程代码 3244152 课程名称 算法分析与设计 考试时间 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） ，然后从这些子问题的解得到原问题的解。二、 选择题
3、（每题2分，共20分）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) | 存在
4、正常数c和n0使得对所有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=pivot
5、key) -high;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,Maxp
7、os,pos=0; 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) flo
8、at Minw; 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
9、!=NULL) 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;i
10、f(strcmp(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=(
11、ArcNode*)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、如下图所示。图中有两行正整数，每行中有若
13、干个正整数。如果第一行的某个数r与第二行的某个数相同，这样就可以在这两个正整数之间划一条线，并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。（共20分） 请编写完整程序，求最大的匹配线段数量，并使得这些匹配线段满足如下条件：（1） 每一个a-匹配线段必须与另一个b-匹配线段相交，且a不等于b.（2） 任何两个匹配线段不能从同一个整数出发。如下图中3-匹配线段是不合法的匹配线段。 不满足上述两个条件的匹配线段则不能称之为匹配线段，不计入匹配线段的数量。例如有两行整数分别如下，则该例中其匹配线段的数量为6. 1 3 1 3 1 33 1 3 1 3 1下面的匹配线段数量则为0。因为虽然最多可划4条匹配线段，但不满足这其中2条匹配线段相交且a-匹配线段不等于b匹配线段的条件，因此其匹配线段的数量为0.1 1 3 3 1 1 3 3
