l题型及复习.docVIP

一、考试题型 单选（15个，15分） 填空（15个，15分） 程序阅读题（2个，10分） 问答（4个，20分） 算法（4个，40分） 二、复习范围 第二章 1.算法的定义及其性质定义：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算性质：5个重特性：1.确定性 2.能行性 3.输入 4.输出 5.有穷性全部满足才能称做算法,仅满足前4条只能叫做计算过程2.算法分析的基础知识全面分析的两个阶段：事前分析和事后测试确定执行时间：频度计数（即语句的执行次数）关于O，?，的定义一个算法具有O（g(n)）的计算时间指的是如果此算法用n值不变的同一类型数据在某台机器上运行，则所用的时间总是小与|g(n)|的一个常数倍。?(g(n))算法的下界函数。第章 法第章 分治法1. 分治法的基本思想求解的思想：将整个问题分成几个小问题后分而治之，通常，由分治法所得到的子问题和原问题具有相同的类型。if(依然太大了)反复分治（）; 2. 二分索及其二树二分索算法及其算法分析其二树：用一棵二元树来描述算法可能的执行过程。内部路径长度：I外部路径长度：EE=I+2n 失败查找平均比较次数。 3. 快速. 选择问题基于PARTITION的选择算法第章 贪心法1. 基本知识基本概念：约束条件、目标函数、可行解、最优解有这样一类问题，它有n个输入，而它的解就由这n个输入的某个子集组成只是这个子集必须满足某些事先给定的条件。约束条件：这些必须满足的条件。可行解 ：满足约束条件的子集。目标函数：为了衡量可行解的优劣，事先给定出了一定的标准，这些标准一般以函数形式给出最优解 ： 使目标函数取极值的可行解。贪心方法的适用对象：求输入的一个可行的子集贪心方法的一般策略：度量标准2. 背包问题：最优度量标准的选择i/wi 3. 带时限的作业排序：pi非增序，入选作业期限di升序 4.最佳合并模式:带权外路径长度最小 5.最小代价生成树：已入选S中边的代价之和增量最小 6.单源最短路径：使得从s到S的所有结点的路径长度之和增量最小的边 7.磁带最优存储：D值的增加最小 第章 动态规划1.基本知识1）基本概念多阶段决策过程：它们的活动过程可以分为几个阶段，而且在任一阶段后的行为都仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关最优性原理：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列. 2）动态规划求解的一般策略：列出递推关系式：向前处理法、向后处理法 2）递归定义最优解值； 3）以自底向上方式计算最优解值； 4）根据计算最优解时得到的信息构造一个最优解。 （4）基本要素：最优子结构性质和重叠子问题性质 2. 重要实例多段图问题：段的定义、基于多段图的多阶段决策过程、导出的递推关系式及算法0/1背包问题：0/1背包问题的定义、向后递推策略、序偶Si的表示方法及其计算过程 1.基本知识1）基本概念1)针对所给问题，定义问题的解空间； 2)确定易于有哪些信誉好的足球投注网站的解空间结构； 3)以深度优先的方式有哪些信誉好的足球投注网站解空间，并且在有哪些信誉好的足球投注网站过程中用剪枝函数避免无效的有哪些信誉好的足球投注网站。 （3）两种常用的解空间树：子集树和排列树。 2. 重要实例第章 1.一般方法及三种分枝限界法 （1）概念2. 重要实例