算法练习题目

说明和算法设计与分析题1渐近复杂性，解释记号O、、和的意义2备忘录方法3贪心选择性质4状态空间树中的活结点、E-结点、死结点5简述分治法和动态规划算法的联系和区别。6简述回溯法求解问题的一般步骤。7简述回溯法和分支限界法的相同点和不同点。8什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。9请描述算法设计的一般过程。10什么是算法复杂性？它主要有哪两个方面构成？11分治算法和动态规划算法都是通过对问题进行分解，通过对子问题的求解然后进行解重构，从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。12动态规划算法的本质是什么，请简要阐述。13如果一个问题可以利用动态规划算法求解，那么该问题应满足什么条件？14动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。15什么是备忘录方法？它同动态规划法相比主要不同点是什么？请指出动态规划法和备忘录方法各自的适用范围。16贪心算法的设计思想是什么，有什么特点？如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件？17请简要描述回溯法的实现过程。18影响回溯法效率的主要因素有哪些？19请简述分支限界法的算法思想以及两种主要的实现方法。20请指出回溯法与分支限界法的相同点与不同点。21对于下图所示的有向图，用Dijkstra算法计算从源顶点1到其它顶点间的最短路径，请列表描述出Dijkstra算法的迭代过程。22对于下图所示的带权图，给出按照Prim算法构造其最小生成树的过程。23子集和数问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之162345631555664251234105020103010060和为d=9。（20分）画出子集和数问题的解空间树；该树运用回溯算法，写出依回溯算法遍历节点的顺序。24对给定的连通带权图，画出用Kruskal算法求最小生成树的选边过程。2515谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。初始状态目标状态26设数组A有n个元素，需要找出其中的最大最小值。请给出一个解决方法，并分析其复杂性。把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法；给出任意的n=8个元素，画出其递归的过程。27已知1()*()iikkijrrAa，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的最佳求积顺序。28假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：对各个物品进行排序时，依据的标准都有哪些？使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。1245637910128131411151234567891011121314151623456245516643上述解中哪个是最优的？物品ABCDEFG重量35306050401025价值1040305035403029多段图问题：设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k2个不相交的子集Vi：1ik，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），图中所有的边（u,v），iuV，1ivV。求由s到t的最小成本路径。给出使用动态规划算法求解多段图问题的基本思想。使用上述方法求解如下多段图问题。1234568791110129732486356241st221171145V1V2V3V4V530n－皇后问题的回溯算法中，用12(,,,)nxxx表示解向量，其中，ix表示第i个皇后的列号，试分析其空间树的表示形式及其约束条件。31分析说明回溯法与分支限界法之间的联系与区别。32排序和查找是经常遇到的问题。按照要求完成以下各题：（1）对数组A={15，29，135，18，32，1，27，25，5}，写出用快速排序方法将其排成递减序的过程。（2）请描述递减数组进行三分搜索的基本思想，并给出递归算法。（3）使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。33设序列12{,,,}mXxxx和12{,,,}nYyyy的最长公共子序列为12{,,,}kZzzz，试说明最长公共子序列问题的最优子结构性质（不必证明）。34请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。35用回溯法解图的m着色问题（给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种着色法使中每条边的两个顶点的着不同颜色），试设计该算法及其剪枝函数（提示：可用图的邻接矩阵来表达图中各顶点是否相连）。36结合实例解释拓扑排序和关键路径的求解过程。