算法设计试卷模式B答案.doc

《算法设计试卷模式B答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、系　　专业　　　　　　　班级　　　　　　　　姓名　　　　　　　　　考号　　　　　　　　　　（密　　封　　线　　内　　不　　准　　答　　题）南阳理工学院2010－2011学年第一学期试卷答案课程：算法设计与分析（B）评卷人（签名）：复核人（签名）：题号一二三四五总分得分一、选择题（每小题1分，共10分）1.选出不是算法所必须具有的特征(C)。A．有限性B．确定性C．高效性D．能行性2.下列(A)不是描述算法的工具。A．数据流图B．伪代码C．自然语言D．程序语言3.下列程序段的算法时间复杂度为(D)。for(inti=0;i<=n;i++）for(in

2、tj=0;j<=m;j++)S;//S是基本操作，耗时常数时间A．B.C.D．4.5个矩阵连乘可能的计算次序有(C)种。A．4种B．5种C．14种D．15种5.折半查找算法在最坏情况下的复杂度为(D)。A．O(n)B．O(n2)C．O(nlogn)D．O(logn)6.Fibonacci数列的第1项为0，第2项为1，那么它的第9项为(C)。A．3B．13C．21D．347.如果X序列包含20个字符，Y序列包含30个字符，则使用动态规划来解最长公共子序列问题，记录各子问题最优值的数组大小为(A)A．651B．600C．620D．6308.背包问题：n

3、=6，C=10，V(1:6)=(15，59，21，30，60，5)，W(1:6)=(1，5，2，3，6，1）。该问题的最大价值为（C）。A．101B．110C．115D．1209.用贪心策略设计算法的关键是（B）。A．将问题分解为多个子问题来分别处理B．选好贪心策略C．获取各阶段间的递推关系式D．满足最优性原理10.下列排序算法不是基于交换的是(C)．A冒泡排序B．快速排序C合并排序D．堆排序二、填空题（每空2分，共30分）1．请将快速排序的分治算法补充完整。数组a存放待排序元素，left:为待排序元素最小下标，right:为待排元素最大下标。in

4、tPartition(inta[],intleft,intright){intx=a[left];inti=left+1;intj=right;while(true){while(a[i]x)j--;if(i>=j)break;swap(a[i],a[j]);}a[left]=a[j];a[j]=x;returnj;}voidQuickSort(inta[],intleft,intright){if(left

5、t(a,left,p-1);QuickSort(a,p+1,right);}}2．动态规划四大解题步骤包括最优子结构性质分析、建立最优值的递归关系式、自底向上求最优值并记录相关信息、根据记录下来的信息构造最优解。3．矩阵连乘问题求最优直算法的复杂度是O(n3)。4．哈夫曼编码算法中采用的贪心策略是从树的集合中取出两棵出现频率最低的树，让它们作为左右子树构造一棵新树，插入到树的集合中。5．旅行商问题的解空间树是一棵排列树，n皇后问题的满足不同行要求的解空间树是一棵满n叉树。图的m着色问题的解空间树是一棵满m叉树。6．随机化算法中，蒙特卡罗算法用于求准

6、确解，数值随机化算法用于求近似解；用于求问题的正确解拉斯维加斯算法算法，但是，算法的每一次运行不一定得到解。当确定性算法中，最坏情况和最好情况下时间的相差很大时，用舍伍德算法削弱这种差异。三、问答题（每小题５分，共20分）1．分治算法有何特征。答：分治算法具有以下特征：（1）问题规模足够小时容易解决；（2）将规模大的问题分成规模较小的子问题；（3）子问题相互独立；（4）子问题的解决方法与原问题相同；（5）递归解决子问题；（6）子问题的解能够合并成原问题的解。2．简述单源最短路径问题的Dijkstra算法的思想。答：初始时令S={源点}，Dist数组

7、记录最短特殊路径长度，重复做如下操作：选择一条特殊路径长度最短的，将其连接的V-S中的点加入到S中。同时考察有没有更优的特殊路径出现。若有，则修正。算法直到S=顶点全集V为止。根据前驱数组的记录，构造最优解。3．简述回溯法搜索的思想。答：从根节点出发，以深度优先的方式进行搜索。判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）4．简述批处理作业调度问题的解空间的定义。答：批处理作业调度问题解的形式为一个n元组（x1,x2,…,xn），其中n表示作业数。xi:表示第

8、i个要处理的作业编号为xi号，i=1,2,3…,n。每个分量的取值如下；令S={1,2,3，…，n}作业编号的集合。则xi