西南交通大学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))⟹f(n)=Θ(h(n))B. f(n)=O(g(n)),g(n)=O(h(n))⟹ℎ(n)=O(f(n))C. O(f(n))+O(g(n))=O(min{f(n),g(n)})D. f(n)=O(g(n))⟺g(n)=O(f(n))4. 下面不是分支界限法搜索方式的是（）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5. 记号Ω的定义正确的是（）。

有：0≤ f(n) ≤A、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥ncg(n) }；B、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；C、(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)<cg(n) }；D、(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有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分）typedef struct SqList{int *r;int Length;}SqList;void QuickSort(SqList *L){QSort(L,1,L->Length);return;}void QSort(SqList *L, int low,int high){int pivotloc;if(low<high){pivotloc=Partion(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}return;}int Partion(SqList *L, int low,int high){int pivotkey;L->r[0]=L->r[low];pivotkey=L->r[low];while(low<high){while(low<high && L->r[high]>=pivotkey)--high;L->r[low]=L->r[high];while(low<high && L->r[low]<=pivotkey)++low;L->r[high]=L->r[low];}L->r[low]=L->r[0];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,18}Low: 1High:7请写出该函数执行结束之后L->r的值以及函数返回的值。

2、阅读下面的程序，按要求回答问题。

（共10分）typedef struct ArcNode{int adjvex;float weight;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int visited;char data[20];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;CTree=(Graph)malloc(sizeof(ALGraph));CTree->vexnum=0;CTree->vertices=(AdjList)malloc(sizeof(VNode)*(G->vexnum+1));for(i=0;i<G->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(Maxpos>G->vexnum)break;}return CTree;}int FindPrimWeight(Graph G,Graph CTree,int Maxpos){float Minw;ArcNode *p,*q=NULL;int rpos,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 && Minw>p->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=curpos>rpos?curpos:rpos;}return curpos;}int InsertStr(char *stemp,Graph G){int i;char *ctemp;ctemp=G->vertices[0].data;for(i=0;i<G->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++;}return i;}void InsNode(int pos1,int pos2, Graph G,float weight){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）设传递给Graph PrimTree(Graph G)函数的参数G的值如下图所示，请用图的形式表示函数执行结束之后的返回值。