下载文档原格式
《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有（）。
Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。
A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。
答案为C。
2.答：选项A的时间复杂度为O(n)。
选项B的时间复杂度为O(n)。
选项C 的时间复杂度为O(log2n)。
选项D的时间复杂度为O(nlog2n)。
答案为C。
第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题（）。
A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。
但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。
A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。
《计算机算法设计与分析》课程设计用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题一、课程设计目的：《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。
通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。
二、课程设计内容：1、分治法：（2）快速排序；2、动态规划：（4）最优二叉搜索树；3、回溯法：（2）图的着色。
三、概要设计：分治法—快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
分治法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；动态规划—最优二叉搜索树：动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。
设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。
●回溯法—图的着色回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始节点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的或节点，并成为当前扩展结点。
算法设计与分析典型算法概述▌分治法与贪心法▌拾光工作室分治法分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。
如果子问题较大，可以再次使用分治策略。
由此可以得到分治策略解决的问题特点：1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题;3.分解出的子问题的解可以合并为原问题的解；4.分解出的各个子问题是相互独立的。
分治法的应用——二叉查找设a[i]（1<=i<=n）是一个数组，其中的元素以非降序排列.考虑判断一个元素x是否在数组中的问题。
确定一个j，使得a[j]=x。
如果x在数组中返回j，否则，返回0。
分析该问题符合分治法策略解决问题的特点，可以用分治法解决：如果n=1，直接判断a[n]是否与x相等。
如果n>1,可以把问题分解如下新的问题：选择一个下标q(范围[i,l]中)，比较x与a[q]，则有三种情况：1.x=a[q].得到解。
2.x>a[q].问题范围转换为(l-q,a[q+1], (x)3.x<a[q].问题范围转换为(q-i,a[i], (x)转换的子问题可以继续分解。
二叉查找的递归算法int BinSrch(Type a[],int i,int n,Type x)//a[i..n]是非递减排列且 1<=i<=n;{if(n==i) { if(x==a[i]) return i;else return 0; }else{int mid=(i+n)/2;if(x==a[mid]) return mid;else if(x<a[mid]) return BinSrh(a,i,mid-1,x);else if(x>a[mid]) return BinSrh(a,mid+1,n,x);}}分治法的应用——查找最大值与最小值在n个元素中找出最大值和最小值首先看下简单的查找算法：void MaxMin(Type a[],int n,Type &max,Type &min){max=min =a[0];for(int i=1;i<n;i++){ if(a[i]>max) max=a[i];if(a[i]<min) min=a[i];}}算法的时间复杂度体现在比较的次数上，当a[n]中的元素是多项式，矢量及非常大的数时或字符串，元素的比较代价就比其他操作代价高的很。
