笔试题准备

笔试题准备"/>

笔试题准备

知识点：前序、中序、后序遍历

前序遍历：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

前序遍历结果是（ABDECF） 

中序遍历：二叉树中序遍历的实现思想是：1.访问当前节点的左子树；2.访问根节点；3.访问当前节点的右子树。即考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

中序遍历结果是（4251637） 

后序遍历：二叉树后序遍历的实现思想是：1.访问左子树；2.访问右子树；3.完成该节点的左右子树的访问后，再访问该节点。即考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)

 后序遍历结果（4526731）

1.已知一个二叉树的前序遍历结果是（ACDEFHGB） ，中序遍历结果是（DECAHFBG）,请问后续遍历结果是      EDCHBGFA

2.若使用枚举法求解TSP算法，则时间复杂度是（n-1）!

3.互为对偶的两个线性规划问题的解存在关系（B）

A原问题无可行解，对偶问题也无可行解

B对偶问题有可行解，原问题可能无可行解

C若最优解存在，则最优解相同

D一个问题无可行解，则另一个问题具有无界解

解析：

任何一个线性规划都存在对偶问题，对偶问题的对偶问题就是原问题。互为对偶的线性规划，一个无最优解，另一个也无最优解，但是一个无可行解，另一个可能有可行解，因此A错误，B正确。若最优解存在，其应该是对偶的，并非相同，因此C错误。D选项一个问题无可行解，另一个问题可能也无可行解，可能具有无界解，因此错误

4.以下哪个算法不是整数规划的精确算法（B)

A分支定价

B单纯型算法

CBenders’分解

D隐枚举

5.集成学习中的boosting方法和bagging方法有那些区别？

在集成算法中主要分为bagging算法与boosting算法，Bagging的连接方式是并行的，每个学习器都是学习最终结果；Boosting的连接方式是串行的，每个学习器学习的是上一个学习器的output和最终结果的残差。

Bagging和Boosting的区别：

1）样本选择上：

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

总结

这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

分箱:分箱是将连续变量离散化，将多状态的离散变量合并成少状态。

分箱方法：分箱方法分为无监督分箱和有监督分箱。常用的无监督分箱方法有等频分箱，等距分箱和聚类分箱。有监督分箱主要有best-ks和卡方分箱。

6.下列特征分箱方法中，那些分箱方法是有监督的（C、D）

A.等距分箱  B.等频分箱C.best-ks  D.卡方分箱