下载文档原格式
算法考试题目及答案解析一、单项选择题1. 在算法中，以下哪个选项不是算法的特性？A. 有穷性B. 确定性C. 可行性D. 随机性答案：D解析：算法的特性包括有穷性、确定性和可行性。
有穷性指的是算法必须在执行有限步骤后终止；确定性指的是算法的每一步操作都是明确的，不存在二义性；可行性指的是算法的每一步操作都必须足够基本，以至于可以准确地执行。
随机性并不是算法的特性之一。
2. 以下哪个排序算法的时间复杂度是O(n^2)？A. 快速排序B. 归并排序C. 冒泡排序D. 堆排序答案：C解析：冒泡排序是一种简单的排序算法，其时间复杂度为O(n^2)，在最坏的情况下，需要比较每一对元素。
快速排序的平均时间复杂度为O(n log n)，归并排序的时间复杂度为O(n log n)，堆排序的时间复杂度为O(n log n)。
3. 在图的遍历中，深度优先搜索（DFS）使用的栈是什么类型的栈？A. 后进先出栈B. 先进后出栈C. 先进先出栈D. 随机进随机出栈答案：B解析：深度优先搜索（DFS）使用的数据结构是栈，遵循的是先进后出的原则，即后进先出栈。
4. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 二分查找法答案：D解析：哈希表解决冲突的方法主要包括分离链接法、开放寻址法和链地址法。
二分查找法是一种查找算法，不是用来解决哈希表冲突的方法。
5. 以下哪个算法不是动态规划算法？A. 斐波那契数列B. 0-1背包问题C. 最短路径问题D. 快速排序答案：D解析：斐波那契数列、0-1背包问题和最短路径问题都可以使用动态规划算法来解决。
快速排序是一种排序算法，不属于动态规划算法。
二、多项选择题1. 以下哪些是算法设计中常用的数据结构？A. 数组B. 链表C. 栈D. 队列E. 树答案：ABCDE解析：数组、链表、栈、队列和树都是算法设计中常用的数据结构，它们各自有不同的特点和适用场景。
设计与算法分析考试题库一、选择题（每题2分，共20分）1. 在算法分析中，时间复杂度用来衡量算法的什么？A. 可读性B. 执行速度C. 资源消耗D. 可维护性2. 以下哪个排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 选择排序D. 堆排序3. 动态规划与分治算法的主要区别是什么？A. 递归使用B. 子问题重叠C. 问题分解方式D. 算法效率4. 递归算法的基本原理是什么？A. 循环调用B. 重复执行C. 问题分解D. 迭代求解5. 在图算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于？A. 搜索顺序B. 搜索深度C. 使用的数据结构D. 搜索效率6. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别是什么？A. 存储方式B. 冲突处理机制C. 访问速度D. 空间利用率7. 贪心算法在解决优化问题时，其选择的策略是？A. 随机选择B. 局部最优C. 全局最优D. 动态选择8. 以下哪个算法是解决最近公共祖先问题的？A. 二分查找B. 欧拉路径C. 弗洛伊德算法D. 树的深度优先搜索9. 算法的时间复杂度为O(1)表示该算法的执行时间与输入规模的大小？A. 成正比B. 成反比C. 无关D. 指数关系10. 在大O符号中，O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n)，按算法效率从高到低排序正确的是？A. O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)B. O(2^n), O(n^2), O(n log n), O(n), O(log n), O(1)C. O(1), O(log n), O(n log n), O(n), O(n^2), O(2^n)D. O(1), O(n), O(log n), O(n log n), O(n^2), O(2^n)二、简答题（每题10分，共30分）11. 简述二分查找算法的基本思想及其时间复杂度。
西安电子科技大学网络教育2010学年上学期期末考试模拟试题一课程名称：__ 算法分析与设计 考试形式： 闭 卷学习中心：_________ 考试时间： 90分钟姓 名：_____________ 学 号：一、填空题（每小题4分，共计40分）1. 通常只考虑三种情况下的时间复杂度，即 最坏 情况、 最好情况和 平均 情况下的时间复杂度，分别记为T max(N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 最坏 情况下的时间复杂度。
2. n n 1032 的渐近表达式是)(2n O ，)log(3n 的渐近表达式是 )(log n O 。
3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中的 常数因子 。
4. 递归算法是指 直接或间接地调用自身 的算法，递归函数是指用函数自身给出定义 的函数。
5. 贪心算法总是做出在当前看来___最好__的选择，也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的____局部最优选择_。
6. 如果某问题具有__贪心选择性质__和__最优子结构性质_两个重要性质，该问题可以用贪心算法求解。
7. 单源最短路径问题适合用__贪心算法__算法来求解、0-1背包问题适合用__动态规划算法__算法来求解。
8. 分治法是将一个规模为n 的问题分解为k 个规模__较小_的子问题，这些子问题_互相独立_且与原问题_相同_。
递归地求解这些子问题，然后将各个子问题的解_合并_得到原问题的解。
9. 动态规划算法的两个基本要素是__最优子结构（性质）_和__子问题重叠（性质）__。
10.__ 动态规划算法 算法可以有效地解凸多边形最优三角剖分问题，而_贪心算法_算法是求解最优装载问题的有效方法。
1. 算法是满足输入、输出、确定性和有限性的指令序列。
程序与算法不同，程序是算法用某种 程序设计语言的具体实现。
算法分析经典算法题第一章1.计算A+B的值：#includeint main(){ int a,b;cin>>a>>b;cout<<a+b<<endl;}< p="">2.输入n个整数，找最大值：第一行为整数n，表示n个数。
第二行输入n个整数。
输出最大值import java.util.Scanner;public class Main{ public static void main(String[] args) throws Exception {Scanner input = new Scanner(System.in);int n = input.nextInt();int arr[]=new int[n];for(int i = 0;i<n;i++){< p="">arr[i]=input.nextInt();}int max = arr[0];for(int i = 1;i<n;i++){< p="">if(arr[i]>max){max = arr[i];}}System.out.println(max);}}第二章1.士兵站队问题在一个划分成网格的操场上，n个士兵散乱地站在网格点上。
网格点由整数坐标(x,y)表示。
士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。
按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。
如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。
计算使所有士兵排成一行需要的最少移动步数。
输入：第1 行是士兵数n，1?n?10000。
接下来n 行是士兵的初始位置，每行2 个整数x 和y，-10000《=x，y《=10000。
一、假设有7个物品，它们的重量和价值如下表所示。
若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。
请写出状态空间搜索树（20分）。
答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。
将它们的序号分别记为1～7。
则可生产如下的状态空间搜索树。
其中各个节点处的限界函数值通过如下方式求得：【排序1分】5x =6x =7x =17分，每个节点1分】a ．1501154040305035190.62540-++++⨯= 7(1,1,1,1,,0,0)8b. 1501154040305030177.560-++++⨯=7(1,1,1,1,0,,0)12c ．4040305010170++++=(1,1,1,1,0,0,1)d. 1501054040303530167.560-++++⨯= 3(1,1,1,0,1,,0)4e. 150130404050353017560-++++⨯=1(1,1,0,1,1,,0)3f. 1501304040503510170.7135-++++⨯=4(1,1,0,1,1,0,)7g. 40405030160+++=(1,1,0,1,0,1,0)h. 1501404040353010146.8535-++++⨯= 2(1,1,0,0,1,1,)7i.1501254030503530167.560-++++⨯=5(1,0,1,1,1,,0)12 j. 1501454030503530157.560-++++⨯=1(0,1,1,1,1,,0)12在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。
即在背包中装入物品F 、B 、G 、D 、A 时达到最大效益，为170，重量为150。
【结论2分】一、已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。
数据结构与算法模拟测试题数据结构与算法是计算机科学中非常重要的基础知识，它们对于编写高效、可靠的程序起着至关重要的作用。
以下是一组数据结构与算法的模拟测试题，希望能帮助您巩固和检验对这部分知识的掌握程度。
一、选择题（每题 5 分，共 30 分）1、在一个具有 n 个元素的有序单链表中插入一个新元素，平均需要移动的元素个数为（）A nB n/2C （n ＋ 1)／2D log₂n2、设栈的初始状态为空，元素 1、2、3、4、5 依次入栈，出栈序列不可能是（）A 5 4 3 2 1B 2 1 5 4 3C 2 1 3 4 5D 1 2 5 4 33、对于一个具有 n 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小为（）A nB n²C n(n 1)／2D n(n ＋ 1)／24、以下排序算法中，在最坏情况下时间复杂度不是O(n²)的是（）A 冒泡排序B 选择排序C 插入排序D 快速排序5、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED CDGBFEA6、以下数据结构中，不属于线性结构的是（）A 队列B 栈C 二叉树D 线性表二、填空题（每题 5 分，共 30 分）1、设一棵完全二叉树共有 700 个结点，则在该二叉树中有______个叶子结点。
2、对于顺序存储的线性表，访问第 i 个元素的时间复杂度为______。
3、在一个长度为 n 的顺序表中删除第 i 个元素（1≤i≤n），需要向前移动______个元素。
4、若对序列(49, 38, 65, 97, 76, 13, 27)进行冒泡排序，在第一趟排序过程中，需要进行相邻元素比较的次数为______。
5、具有 10 个顶点的无向完全图，其边的数量为______。
6、已知一个图的邻接表如下所示，从顶点 1 出发进行深度优先遍历的序列为______。
一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外,算法还应具有以下五个重要特性：_________,________,________，__________，__________。
2。
算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3。
某一问题可用动态规划算法求解的显著特征是____________________________________.4.若序列X={B，C,A，D,B，C,D},Y={A，C，B,A，B，D，C,D}，请给出序列X和Y的一个最长公共子序列_____________________________.5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6。
动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7。
以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________.9。
动态规划算法的两个基本要素是___________和___________。
10。
二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1。
写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3。
若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2，a3,a4)=（4，5，12,10），(b1,b2,b3，b4)=（8，2，15,9)求4个作业的最优调度方案，并计算最优值。
4。
使用回溯法解0/1背包问题：n=3，C=9，V={6，10，3｝，W={3,4，4}，其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。
答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。
其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。
2. 什么是动态规划算法？请给出一个动态规划算法的示例。
答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。
它的特点是具有重叠子问题和最优子结构性质。
以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。
3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。
而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。
DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。
4. 请简述贪心算法的特点及其应用场景。
答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。
然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。
计算机算法设计与分析练习题一． 最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如∑=ji k k a 的子段和的最大值： ⎭⎬⎫⎩⎨⎧∑=≤≤≤j i k k n j i a 1max ,0max 1. 一个简单算法如下：int Maxsum(int n,int a,int& besti,int& bestj){int sum = 0;for (int i=1;i<=n;i++){int suma = 0;for (int j=i;j<=n;j++){suma + = a[j];if (suma > sum){sum = suma;besti = i;bestj = j;}}}return sum;}试分析该算法的时间复杂性。
2. 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3. 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。
分析算法的时间复杂度。
二．设n x x x ,,,21 是n 个互不相同的元素，每个元素i x 有一个正实数权值i w ，且满足11=∑=ni i w 。
n 个元素n x x x ,,,21 的带权)1(n i w i ≤≤的中位数是满足下面不等式的元素k x ：⎪⎪⎩⎪⎪⎨⎧≤≤∑∑><ki k i x x i x x i w w 2121 (1) 1). 证明n x x x ,,,21 的（不带权的）中位数是带权n w i /1= （,2,1=i n , ）的带权中位数（不带权的中位数是指按照大小排在中间位置的数，如果有两个，则取小者）。
2). 说明如何通过排序，在最坏情况下用)log (n n O 时间求出n 个元素的带权中位数。
3). 说明如何利用一个线性时间选择算法，在最坏情况下用)(n O 时间求出n 个元素的带权中位数。
4). 邮局位置问题是：已知n 个点n p p p ,,,21 以及与它们相联系的权n w w w ,,,21 ，要求确定一点p （未必是输入的点），使和式∑=ni i i p p d w 1),(达到最小，其中),(b a d 表示a 与b 之间的距离。
信息工程学院算法分析实践环节习题集（2011年）序号项目名称任务描述设计要求指导教师人数1． 12．二进制位串的压缩树算法设计与实现第一步输入：二进制位串，例如：0000010000001111输出：如下图1所示的二进制压缩树第二步输入：二进制压缩树，如图1输出：二进制路径码数组如图2第三步：输入两个路径码数组，如图2，图3输出：相与后的路径码数组，如图4两个路径码数组相与就是求子码的过程，对于两个路径码x,y，如果x是y的前缀，那么y是x的子码，比如：0是0101的前缀，因此0101是0的子码。
所以图2和图3相与后的路径码数组是图4.用Java语言，或者C语言，推荐用Java语言。
要求：读文件，读取文件中所有的项，得到二进制串，然后构造每个项的二进制串的压缩树，并得到每个项的路径码。
刘全中 1图1图2图3图43．4．简单数据集跳跃显露模式挖掘算法设计与实现跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生次数大于等于一个支持度计数阈值ξ的模式。
例如下表中数据，假定2=ξ。
那么在类别为1D上的跳跃显露模式有：},{eb，},,{edc利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。
刘全中 15．简单数据集频繁关闭模式挖掘算法设计与实现频繁模式是指在数据集中，出现的次数大于等于给定阈值ξ的项集。
如下表所示的数据集，假设2=ξ。
频繁模式：}{a，}{b，}{c, …….., },,,{mfca等对于模式p，如果不存在模式'p,'pp⊂. 使得包含p的事物和包含'p的事物相同。
那么p就是一个关闭频繁模式。
利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有的频繁关闭刘全中 1例如，假设2=ξ，},,,{m f c a 就是一个关闭频繁模式。
6．利用分治思想设计循环赛日程表假设有n=2k 个运动员要进行网球循环赛。
设计一个满足一下要求的比赛日程表：(1). 每个选手必须与其他n-1个选手各赛一次 (2). 每个选手一天只能赛一次 (3). 循环赛一共进行n-1天利用Java 语言开发一个界面，输入运动员的个数，输出比赛日程表。
西安电子科技大学网络教育2010学年上学期期末考试模拟试题一课程名称：__ 算法分析与设计 考试形式： 闭 卷学习中心：_________ 考试时间： 90分钟姓 名：_____________ 学 号：一、填空题（每小题4分，共计40分）1. 通常只考虑三种情况下的时间复杂度，即 最坏 情况、 最好情况和 平均 情况下的时间复杂度，分别记为T max(N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 最坏 情况下的时间复杂度。
2. n n 1032 的渐近表达式是)(2n O ，)log(3n 的渐近表达式是 )(log n O 。
3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中的 常数因子 。
4. 递归算法是指 直接或间接地调用自身 的算法，递归函数是指用函数自身给出定义 的函数。
5. 贪心算法总是做出在当前看来___最好__的选择，也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的____局部最优选择_。
6. 如果某问题具有__贪心选择性质__和__最优子结构性质_两个重要性质，该问题可以用贪心算法求解。
7. 单源最短路径问题适合用__贪心算法__算法来求解、0-1背包问题适合用__动态规划算法__算法来求解。
8. 分治法是将一个规模为n 的问题分解为k 个规模__较小_的子问题，这些子问题_互相独立_且与原问题_相同_。
递归地求解这些子问题，然后将各个子问题的解_合并_得到原问题的解。
9. 动态规划算法的两个基本要素是__最优子结构（性质）_和__子问题重叠（性质）__。
10.__ 动态规划算法 算法可以有效地解凸多边形最优三角剖分问题，而_贪心算法_算法是求解最优装载问题的有效方法。
1. 算法是满足输入、输出、确定性和有限性的指令序列。
程序与算法不同，程序是算法用某种 程序设计语言的具体实现。
程序不满足算法的 有限性 性质。
2. 实践表明，可操作性最好且最有实际价值的是_最坏__情况下的时间复杂性。
3. 直接或间接调用自身的算法称为_递归算法_，用函数自身给出定义的函数是 __递归函数_。
4. 找硬币问题是用_贪心算法__求解的典型例子，而最长公共子序列问题则适合用_动态规划算法_求解。
5. 函数式An2+Bn+C 的复杂度是__)(2n O _，函数式Cn 复杂度是__ O(C n)__。
6. 对于表达式3n 、25n 、n log ，n 20, 按照渐近阶从低到高的顺序排列, 顺序是__n log __、__n 20_、__25n __、_3n __。
7. 二分搜索算法是应用__分治策略__的典型例子。
这个方法很好地利用n个元素__已排好序__这个条件。
可在最坏情况下用_)(log n O _时间完成搜索,而顺序搜索法在最坏情况下需要_)(n O _时间完成搜索。
8. 如果某问题具有__最优子结构（性质）__和__子问题重叠（性质）___两个重要性质_，该问题可以用动态规划算法求解。
9. 备忘录方法是动态规划算法的变形。
与动态规划算法不同的是，备忘录方法的递归方式是 自顶向下 ，而动态规划算法的递归方式则是 自底向上。
10.部分背包问题适用于__贪心算法__算法求解、而0-1背包问题适用于__动态规划算法___算法求解。
1. 算法是满足输入、输出、确定性和有限性等四个性质的指令序列。
2. 算法复杂性的高低体现在运行该算法所需的计算机资源的多少上，计算机的资源最重要的是时间和空间（即存储器），因此算法的复杂性有时间复杂性和空间复杂性之分。
3.与分治法类似，动态规划算法的基本思想是__将待求解问题分解为若干个子问题__，先求解__子问题_，然后从这些解得到原问题的解。
与分治法不同的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是__互相独立__的。
4. Java语言的类(class)体现了抽象数据类型(ADT)的思想，一般由4个部分组成：类名、数据成员、方法和访问修饰。
5. 抽象数据类型的英文简称是 ADT ，它是算法的一个 __数据模型_连同定义在该模型上并作为算法构件的一组__运算__ 。
6. O(f)+O(g)= O(f+g)__，O(f)O(g)= O(fg) 。
7. 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模__较小__的相同问题 , 以便各个击破，____分而治之___。
8. 动态规划算法的第一步通常是刻画最优解的结构。
当问题的最优解包含了其___子问题___的最优解时，称该问题具有最优子结构性质。
9. 动态规划算法与贪心算法的主要区别是__贪心选择性质__性质。
10.表示最优前缀码的二叉树总是一颗完全二叉树，即树中任一个结点都有两个儿子结点。
二、简答题（每小题10分，共计40分）1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？如果只需要求解问题的最优值，动态规划算法步骤如下：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；如果需要构造最优解，则还需要加上如下步骤：（4）根据计算最优值时得到的信息，构造最优解。
2. 请简述什么是贪心选择性质所谓贪心选择性质是指，所求问题的全局最优解可以通过一系列局部最优选择，即贪心选择来达到。
3. 请简述什么是最小生成树。
如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树上各边权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小生成树。
4. 请简述贪心算法比动态规划算法效率高的原因。
动态规划算法需要知道所有子问题的解，而贪心算法不需要知道所有子问题的解，它只是在每一步迭代中选择看起来最好的解，并不从整体进行最优考虑，因此效率较高。
1. 请简述为什么部分背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
对于部分背包问题，依照贪心选择策略，可以得到最优解。
而0-1背包问题，贪心选择之所以不能得到最优解，是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
因而我们选择的判断标准出现了误差。
2. 请写出如图语法树所对应的矩阵链相乘的最优完全加括号方式。
((A1(A2A3))(A4(A5A6)))3. 按照下表中的字母出现频率，请画出哈夫曼树，并设计相应的哈夫曼编码。
哈夫曼编码：4. 请简述动态规划算法求解最优化问题的步骤。
（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造最优解。
1. 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写出该方程的一般形式，并指出其中各参数的意义。
分治算法的一般步骤：分解 → 直接或递归求解子问题 → 组合递归方程分治算法的时间复杂性C(n)往往满足如下的递归方程：其中，n: 问题的规模。
n 0: 可直接解的问题规模的阈值。
a: 分解出的需要求解的子问题的个数。
n/c: 分解出的子问题的规模。
g(n): 分解规模为n 的问题以及组合相应子问题的解所需的时间。
d: 直接解规模为n 0的问题所需的时间。
2. 0-1背包问题的形式化描述是什么？∑∑==≤∈-≤≤>>>n i i i n i i i i n i i C x x x x v w C 1121x v ,x w },1,0{),,...,,(10n ,n i 1,0,0,0达到最大。
而且使得向量元要求找出给定3.请简述贪心算法的简要求解步骤。
贪心算法的简要求解步骤如下：① 将优化问题转化成这样的一个问题，即先做出选择，再解决剩下的⎩⎨⎧>+===00n n , )()()(n , )(n g c n aC n C n d n C一个子问题。
②证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全性。
③说明在做出贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解。
4.请简述归并排序的基本思想。
将待排序的序列分成长度大致相等的两个子序列，分别对2个子序列进行排序，最终将2个已排好序的子序列合并为有序的完整序列。
三、算法分析和设计题（每小题10分，共计20分）1. 请写出汉诺塔问题的简要递归算法。
public static void Hanoi(int n, int a, int b, int c){if( n>0 ){Hanoi( n-1, a,c,b );Move( a, b );Hanoi( n-1, c,b,a )；}}2. 请设计一个在有序数组a[1..n]中二分搜索元素x的递归算法，要求若x在数组中则返回其下标否则返回0.输入：正整数n和存储n个元素的数组a[1..n],被搜索的元素x输出：若x在数组中则返回其下标否则返回0i=binarysearch(1,n,a,x);return I;end BINARYSEARCH1过程 binarysearch(low,high,a,x)//在数组a 的下标为low 到high 范围内寻找x,//若找到x 则返回其下标否则返回0if low>high thenreturn 0;elsemid=[]2/)(high low +;if a[mid]=x thenreturn mid;else if a[mid]<x thenreturn binarysearch(low,mid-1,a,x);else return binarysearch(mid+1,high,a,x); end ifend if1. 请写出Fibonacci 数列的递归定义式及其简要递归算法。
Fibonacci 数列的递归定义式是：⎩⎨⎧>=-+-=11,0)2()1(1)(n n n F n F n F 当当 第n 个Fibonacci 数可以递归计算如下:public static int Fibonacci(int n){if( n<=1 ) return 1;return Fibonacci(n-1) + Fibonacci(n-2) ;}2. 请写出二分搜索算法的简单程序描述(用java 或C++语言)。
public static int BinarySearch(int[ ] a, int x, int n) {int left=0; int right=n-1;while(left<=right) {int middle = (left+right)/2;if(x==a[middle])return middle;if(x>a[middle])left = middle+1;elseright = middle-1;}return -1;}1. 请写出阶乘函数的递归定义式及其简要递归算法。
