程序算法设计与分析A答案

2009~2010学年第1学期《算法分析与设计》课程试卷（A）参考答案及评分标准开课二级学院：理学院，学生班级：06信算1，2，教师：一、名词解释：（每题5分，共20分）1、递归算法直接或间接地调用自身的算法称为递归算法。使用递归技术往往使算法的描述简捷且易于理解。(5分)2、二分搜索：二分搜索算法的基本思想是将n个排序好的元素分成个数大致相等的两半，取与作比较，如果，则算法终止，如果，则在数组的左半部查找，否则在右半部查找。（5分）3、合并排序：合并排序算法是用分治策略实现对个元素的进行排序的算法，其基本思想是将待排序的元素分成两个大小致相等的两面个子集合，分别对两面个子集合进行排序。最终将排好序的子集合合并成要求的排序好的集合。（5分）4、分治法基本思想分治法的基本思想是将一个规模为的问题分解为k个规模较小的子问题，这些子问题互相独立，分别对这些子问题求解，再把所得到的问题的解合并起来，从而得到整个问题的解的方法。（5分）二、简答题：1、背包问题与0-1背包问题的比较答：0-1背包问题是给定n种物品和一个背包，物品的重量是，其价值为，背包的容量为，问如何选择装入背包的物品，使得背包中物品总价值最大。（3分）背包问题：与0-1背包问题不同的是装入某一物品可以装入其一部分。（5分）两个问题差别不大，但解决问题的方法是不同的，背包问题可以用贪心算法来实现，而0-1背包问题不能用贪心法来实现，一般采用动态规划的方法来实现。（10分）2、写出动态规划算法的基本思想、解题步骤及基本要素。答：动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（4分）通常按以下步骤设计：找出最优解的性质，并刻画其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。（8分）基本要素：最优子结构性质和子问题重叠性质。（10分）3、写出回溯法的基本思想和解题步骤。答：回溯法是从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结成为活结点，同时也成扩展结点，在当前的扩展结点处，按深度优先的方式，进行搜索，直到找到所要求的解，或是没有活结点为止。(4分)通常分以下3个步骤：针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。（10分）4、RAM指令中的操作数有哪几种形式？写出这几种形式的名称、符合及表示的意义。答：RAM指令中的操作数有3种形式：（1）=i（直接数型），操作数是整数i本身。（3分）(2)i（直接地址型），i是一非负整数，操作数是寄存器ri的内容。（6分）(3)*i(间接地址型)，i为非负整数，若寄存器ri的内容为整数j，则操作数为寄存器rj中的内容。当j为负整数时操作数无定义。（10分）三．设计与分析(每小题20分，共40分)1、用快速排序法对数组a[p:r]进行排列。写出快速排序法的基本思想及算法描述。答：快速排序法的基本思想是对于输入的子数组a[p:r]，按以下三个步骤进行排序。（1）分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。（5分）（2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。（9分）（3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。（14分）算法描述：Template<classType>VoidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}Template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];While(true){While(a[++i]<x&&i<r);While(a[--j]>x);If(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}（20分）2、Dijkstra算法（1）描述该算法的基本思想Dijkstra算法是解决单源最短路径的一个贪心算法，其基本思想是，设置顶集合S并不断的做贪心选择来扩充这个集合。一个顶点属于S当且公当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一顶点，反从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用Dist记录当前每一个顶点所对应的最短特殊路径长度。（5分）（2）用图表的形式表求出有向（图1）从顶点1到其它顶点的最短路径的Dijkstra算法的迭代过程。迭代suDist[2]Dist[3]Dis