下载文档原格式
西南交通大学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。
算法设计与分析期末试卷A卷一、选择题1.二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法解析：二分搜索是一种基于分治策略的算法。
2.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树解析：旅行售货员问题的解空间树是子集树，因为每个结点代表一个城市的集合。
3.下列算法中通常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法解析：动态规划法通常以自底向上的方式求解最优解。
4．下面不是分支界限法搜索方式的是（D）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先解析：分支界限法搜索方式包括广度优先、最小耗费优先和最大效益优先，但不包括深度优先。
5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（B）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）解析：最优装载问题采用贪心算法的主要计算量在于将集装箱依其重量从小到大排序，因此时间复杂度为O（nlogn）。
6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
A、最小堆B、最大堆C、栈D、数组解析：分支限界法解最大团问题时，活结点表的组织形式是最大堆。
7、下面问题（B）不能使用贪心法解决。
A 单源最短路径问题C 最小花费生成树问题B N皇后问题D 背包问题解析：N皇后问题不能使用贪心法解决。
8.下列算法中不能解决0/1背包问题的是（A）A 贪心法B 动态规划C 回溯法D 分支限界法解析：贪心法不能解决0/1背包问题。
9.背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）解析：背包问题的贪心算法所需的计算时间为O （nlogn）。
二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有穷性四条性质。
算法设计与分析试题A及答案一．填空题：（每题4分，共20分）1.算法是指（解决问题的）一种方法或一个过程，是（若干指令的）有穷序列。
2质。
3. 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。
4．递归函数的两大基本要素是_递归方程和边界条件_ .5．在回溯法中，一个问题的解空间是指一个大的解决方案可以看作是由若干个小的决策组成。
很多时候它们构成一个决策序列。
解决一个问题的所有可能的决策序列构成该问题的解空间.二．简答题：（每题5分，共20分）1.简述分治法所能解决的问题一般应具有的特征。
1.)该问题的规模缩小到一定的程度就可以容易地解决；2.)该问题具有最优子结构性质；3.)利用该问题分解出的子问题的解可以合并为该问题的解；4.)该问题所分解出的各个子问题是相互独立的。
2．设有待安排的8个活动的开始时间和结束时间如下表。
请采用贪心算法给出活动安排序解：将待安排的8个活动的开始时间和结束时间按结束时间的非减序排列如下：用贪心算法给出活动安排序列：1，3，6，8。
贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
3．请描述分治法的具体过程。
将原问题划分成k 个子问题。
对这k 个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
4. Fibonacci 数列如下定义：10()11(1)(2)1n F n n F n F n n =⎧⎪==⎨⎪-+->⎩1、 请设计一个递归算法，计算F(n)。
2、 分析算法的时间复杂性。
解 1、int fibonacci(int n) { if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2); }2、T(n)=T(n-1)+T(n-2)。
chengcheng算法分析考试试卷（A卷）课程名称算法分析编号题号一二三四总分得分评阅人一、填空题（每小题3分，共30分）1、一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
2、这种不断回头寻找目标的方法称为回溯法。
3、直接或间接地调用自身的算法称为递归算法。
4、 记号在算法复杂性的表示法中表示紧致界。
5、由分治法产生的子问题往往是原问题较小模式，这就为使用递归技术提供了方便。
6、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
7、下列各步骤的先后顺序是②③④①。
①调试程序②分析问题③设计算法④编写程序。
8、最优子结构性质的含义是问题最优解包含其子问题最优解。
9、贪心算法从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择。
10、拉斯维加斯算法找到的解一定是正确的。
二、选择题（每小题2分，共20分）1、哈夫曼编码可利用（ C ）算法实现。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是基本计算模型的是（ B ）。
A、RAMB、ROMC、RASPD、TM3、下列算法中通常以自顶向下的方式求解最优解的是（ C）。
A、分治法B、动态规划法C、贪心法D、回溯法chengcheng 4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( A )A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ BA、递归；B、分治；C、迭代；D、模拟。
6、FIFO是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法7、投点法是（ B ）的一种。
A、分支界限算法B、概率算法C、贪心算法D、回溯算法8、若线性规划问题存在最优解，它一定不在（ C ）A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ B ）对输入进行预处理。
算法与分析综合试卷一、选择题1．算法分析是（）。
A．将算法用某种程序设计语言恰当地表示出来B．在抽象数据集合上执行程序，以确定是否会产生错误的结果C．对算法需要多少计算时间和存储空间作定量分析D．证明算法对所有可能的合法输入都能算出正确的答案2．算法确认是（）。
A．将算法用某种程序设计语言恰当地表示出来B．证明算法对所有可能的合法输入都能算出正确的答案C．对算法需要多少计算时间和存储空间作定量分析D．在抽象数据集合上执行程序，以确定是否会产生错误的结果3．算法与程序的区别在于算法具有（）。
A．能行性B．确定性C．有穷性D．输入和输出4．设A[1..60]={11,12,…,70}。
算法BINARYSEARCH在A上搜索x=33、7、70、77时执行的元素比较次数分别为a、b、c、d，则（）。
A．a<b<c<d B．a>b=c=d C．a<b=c=d D．a<c<b=d5．算法INSERTIONSORT 在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的元素比较次数为（）。
A．14 B．28 C．7 D．226．当A[1..n]中元素取值在范围（）时，算法RADIXSORT 的时间复杂度为T(nlogn)。
A．A．[1..n] B．[n..2n] C．[1..n2] D．[1.. 2n]7．设待排序的序列A[1..n]中元素取值于[1..n!]，则下列哪一个算法最坏情况下排序更慢?A．SELECTIONSORT B．INSERTIONSORTC．RADIXSORT D．BUBBLESORT8．一个排序算法如果能够使得序列中相同元素的位置次序在排序前后保持一致，则称之为稳定的排序算法。
下列几种排序算法中哪一种不是稳定的？A．SELECTIONSORT B．RADIXSORTC．BUBBLEBSORT D．BOTTOMUPSORT9．使用算法EXP来计算下列哪一个整数次幂所花费的乘法次数最多？A．35B．36C．37D．3810．算法MAJORITY在下列哪一个输入上执行时最后j=n，count=1，且c是主元素？A．{5,7,5,4,5} B．{5,7,5,4,8} C．{2,4,1,4,4,4,6,4} D．{1,2,3,4,5} 11．用贪心法设计算法的关键是（）。
1算法设计与分析课程期末试卷A卷（含答案）华南农业大学期末考试试卷（A卷）2008学年第一学期考试科目：算法分析与设计考试类型：（闭卷）考试时间：120分钟学号姓名年级专业一、选择题（20分，每题2分）1.下述表达不正确的是。
DA．n2/2 + 2n的渐进表达式上界函数是O(2n)B．n2/2 + 2n的渐进表达式下界函数是Ω(2n)C．logn3的渐进表达式上界函数是O(logn)D．logn3的渐进表达式下界函数是Ω(n3)2.当输入规模为n时，算法增长率最大的是。
AA．5n B．20log2n C．2n2D．3nlog3n3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。
C A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是。
AA．（4k– 1）/3 B．2k /3 C．4k D．2k5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。
D A．随机选择一个元素作为划分基准B．取子序列的第一个元素作为划分基准C．用中位数的中位数方法寻找划分基准D．以上皆可行。
但不同方法，算法复杂度上界可能不同6.现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。
CA．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0）7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。
如下说法不正确？AA．让水桶大的人先打水，可以使得每个人排队时间之和最小B．让水桶小的人先打水，可以使得每个人排队时间之和最小C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
西南交通大学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的值如下图所示，请用图的形式表示函数执行结束之后的返回值。
