算法考试重点.doc

算法考试重点
算法的概念
答：算法是求解一类问题的任意一种特殊的方法。较严格的说法是，一个算法是对特定问题求解的一种描述，它是指令的有限序列。
算法具有的五个特征：（1）输入（2）输出（3）确定性（4）能行性（5）有穷性
问题求解过右子树高度最多相差1的二叉搜索树。每次插入或删除后，按规则重新平衡树形，使之始终保持平衡，限制树形的高度，避免退化。能保证性能，但增加了实现难度。
18自调节搜索树。在伸展树上，执行一个m次运算（搜索、插入、删除）序列，总的时间为O(mlogn)具有良好的平均分摊代价。是平衡搜索树的很好替代结构。
19伸展树: 一颗二叉搜索树,但要求每访问一个元素后,将最新访问的元素移至二叉搜索树的根部,以保证经常被访问的元素靠近根节点，而较少访问的元素位于搜索树较低的层次上是自调整搜索树，,一个元素被访问后,下一次还要访问它的机会比较大.
20伸展节点的确定



,则搜索过程中遇到的最后一个节点为伸展节点.
21搜索: 一种通过系统地检查给定数据对象的每个结点,寻找一条从开始结点到答案结点的路径,最终输出问题解的求解方法.
22遍历:要求系统地检查数据对象的每个结点.
分为：树遍历和图遍历
23状态空间:用于描述所求问题的各种可能的情况。每一种情况对应状态空间的一个状态。
分为：初始状态—代表搜索开始,
目标（答案）状态—代表已求得问题的解
24问题的求解过程：从初始状态出发，以某种次序系统地检查状态空间的每一个状态，搜索答案状态的过程。
问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态.
穷举搜索=盲目搜索=无知搜索，把所有的状态逐个检查，直到找到解或者检查完。
深度搜索和广度搜索都是无知搜索
有知搜索
已知的信息为指导，排除一部分状态空间。
有时可能找不到解，比如指导搜索的信息是错误的，则会误入歧途。
启发式搜索
使用经验法则，边搜索边评估到达目标状态的剩余距离。
24广度优先搜索
对于一个未检测结点,访问完其全部后继结点后才访问其他未检测结点
深度优先搜索:如果一个算法一旦访问某个结点，该结点成为未检测结点后，便立即被算法检测，成为E-结点，而此时，原E-结点尚未检测完毕，仍处于检测状态，需要在以后适当时候才能继续检测，这种做法成为深度优先搜索
25活结点—未检测结点
死结点—其后续结点已全部访问过
26分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
27分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
28将问题表示为：I=(n,a1,…,an,x)
选取一个下标k，可得到三个子问题：
I1=(k-1,a1,…,ak-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,…,an,x)
如果对所求解的问题（或