算法分析与设计复习题及参考答案VIP免费

网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。3.简述动态规划算法求解的基本要素。4.简述回溯法的基本思想。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划算法的异同。三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。3.已知k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序（要求给出计算步骤）。4.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[si，fi]，活动i,j相容的条件是：sj≥fi，问题的解表示为(xi|xi=1，2…，n,)，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。10.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组A有n个元素，需要找出其中的最大最小值。①请给出一个解决方法，并分析其复杂性。②把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。12.有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2，...，xi，…，xn)，xi=0，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足，且存放的程序数目最多。13.试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试设计计算的所有不同排列的算法。14.试用动态规划算法实现0-1闭包问题，请写出该算法。15.试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。16.试写出用分治法对一个有序表实现二分搜索的算法。17.试用动态规划算法实现最长公共子序列问题，请写出该算法。18.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值1040305035403019.求解子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。①画出子集和问题的解空间树；②该树运用回溯算法，写出依回溯算法遍历节点的顺序；③如果S中有n个元素，指定d，用伪代码描述求解子集和问题...