天津工业大学《计算机算法设计与分析》期末复习重点（含答案）

"这是一份来自天津工业大学的《计算机算法设计与分析》课程的期末复习题，包含了填空题和综合题，涵盖了算法设计的基本概念、动态规划算法、流水作业调度问题以及最优二叉搜索树等相关知识点。" 知识点详细说明： 1. **算法的性质**：算法通常具有五个基本性质，即输入、输出、有穷性、确定性和可行性。填空中提到的是前三个，输入是指算法处理的数据，输出是算法运行后的结果，而有限性则指算法必须在有限步骤内结束。 2. **动态规划算法**：动态规划是一种解决最优化问题的有效方法，基本思想是将复杂问题分解为子问题，通过求解子问题的最优解来构建原问题的最优解。填空中的第二题可能是在询问动态规划的这一核心思想。 3. **设计动态规划算法的步骤**：通常包括四个步骤：(1)定义状态；(2)找出状态转移方程；(3)确定初始条件；(4)构造并返回最优解。填空中的空白部分分别对应这些步骤。 4. **流水作业调度问题**：这是运筹学中的经典问题，目的是在给定条件下找到一个作业调度方案，使完成所有作业的总时间最短。Johnson算法是解决该问题的一种方法，填空涉及算法的具体步骤，如找出作业的最早结束时间并按照某种顺序排列。 5. **Johnson不等式**：在流水作业调度问题中，这个不等式是判断调度是否最优的一个关键条件，即对于任何最优调度，作业i和i+1的开始时间和结束时间必须满足特定的不等式关系。 6. **最优二叉搜索树**：这是一种特殊的二叉搜索树，其每个节点的左子树上的所有节点的键值小于该节点，右子树上所有节点的键值大于该节点，同时，它的形状使得在所有满足二叉搜索树性质的树中，查找效率最高。 7. **最大子段和问题**：这是一个经典的线性时间复杂度算法问题，用于寻找一串数字中连续子序列的最大和。提供的代码片段是一个简单的算法实现，其中`thissum`累加子序列的和，`sum`记录当前最大和，`bestj`保存最大和对应的结束位置。 8. **最优二叉搜索树问题**：动态规划可以用来解决最优二叉搜索树问题，给定一组键值和相应的权重，目标是构建一棵二叉搜索树，使得对每个键的查找成本最小。`OptimalBinarysearchTree`函数可能是用来构建这样的树，其中`m`和`w`可能分别表示成本矩阵和权重矩阵，需要填充的部分可能是初始条件或状态转移方程。 以上内容详细阐述了题目中涉及的计算机科学中的算法设计和分析相关知识，包括基本概念、动态规划、调度算法和数据结构优化等方面。这些知识点是计算机科学和信息技术领域的基础，对于理解和解决问题至关重要。