简述回溯法的基本思想，采用这种算法的关键是什么？

第1题：

第2题：

设计或选择Hash函数的基本要求是什么？并简述J.D.Ullman提出的Hash算法的基本思想。

正确答案:尽可能减少冲突并设计发生冲突后的算法。利用Y=F（X）把码值映射成记录存储地址，直接存取。知道码值立即可算出地址。

第3题：

采用最大效益优先搜索方式的算法是（）

• A、分支界限法
• B、动态规划法
• C、贪心法
• D、回溯法

正确答案:A

第4题：

优先队列插入算法的基本思想是什么？

正确答案:在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。

第5题：

简述Tomasulo算法的基本思想。

正确答案: 核心思想是：
①记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减小到最少；
②通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。
基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。

第6题：

关于回溯搜索法的介绍，下面（）是不正确描述。

• A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
• B、回溯法是一种既带系统性又带有跳跃性的搜索算法
• C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
• D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

正确答案:D

第7题：

算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？

正确答案:递推法：是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i=1出发，由已知i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。
递归法：递归策略是利用函数直接或间接地调用自身来完成某个计算过程。能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。
穷举法：穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。
迭代法：数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。

第8题：

简单描述回溯法基本思想。

正确答案:回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。

第9题：

第10题：

第11题：

第12题：

第13题：

简述ID3算法的基本思想及其主算法和建树算法的基本步骤。

正确答案: 首先找出最有判别力的因素，然后把数据分成多个子集，每个子集又选择最有判别力的因素进一步划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的样例进行分类。
主算法包括如下几步：
①从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；
②用“建树算法”对当前窗口形成一棵决策树；
③对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；
④若存在错判的例子，把它们插入窗口，重复步骤②，否则结束。
建树算法的具体步骤如下：
①对当前例子集合，计算各特征的互信息；
②选择互信息最大的特征A_k；
③把在A_k处取值相同的例子归于同一子集，A_k取几个值就得几个子集；
④对既含正例又含反例的子集，递归调用建树算法；
⑤若子集仅含正例或反例，对应分枝标上P或N，返回调用处。

第14题：

霍夫曼编码算法的基本思想是什么？ 

正确答案:是根据源数据符号发生的概率进行编码的。在源数据中出现概率越大的符号，分配的码字越短；出现概率越小的信号，其码长越长，从而达到用尽可能少的码表示源数据。

第15题：

回溯法中常见的两类典型的解空间树是什么？并简述其定义。

正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。

第16题：

回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。

正确答案:子集树；排列树

第17题：

算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？

正确答案: 分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
回溯策略也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。

第18题：

采用广度优先策略搜索的算法是（）。

• A、分支界限法
• B、动态规划法
• C、贪心法
• D、回溯法

正确答案:A

第19题：

简述种子填充算法与栅格算法的基本思想。

正确答案: 种子填充算法（内部点扩散法）：由一个内部的种子法，向其四个方向的邻点扩散。判断新加入的点是否是否在多边形边界上。如果是，就不作为种子点，否则当作新的种子点，直到区域填满，无种子点为止。该算法比较复杂，而且可能造成阻塞而造成扩散不能完成。此外若多边形不完全闭合时，会扩散出去。栅格算法：栅格指的是一条与扫描线垂直的直线，栅格位置通常取多边形的顶点，并且把多边形分为左右两半。基本思想是对于每个扫描线与多边形的交点，将交点与栅格之间的像素用多边形的属性值填补。若交点位于栅格左边，则将交点右边，栅格左边的所有像素取补；若交点位于右边，则把栅格右边交点左边的像素取补。

第20题：

第21题：

第22题：

第23题：