京东面试算法题

ゝ一世哀愁。 2022-11-28 13:19 182阅读 0赞

**1. 若一序列进栈顺序为a1,a2,a3,a4，问存在多少种可能的出栈序列**  
12  
13  
14  
15

**正确答案：C**

卡特兰数：**f(n)=C(2n,n)/(n+1)**

--------------------

**2. 下列属于有监督学习算法的是：**  
谱聚类  
主成分分析PCA  
主题模型LDA  
线性判别分析LDA  
**正确答案：D**

**题目解析：**  
  聚类是典型的无监督学习方法，谱聚类是很好的聚类算法，往往可以得到不错的聚类结果（缺点是需要计算特征值和特征向量，速度较慢）；主成分分析PCA是使用无标签的数据直接做降维，属于无监督学习。主题模型LDA只使用文本数据本身，在给定主题数目K和超参数αβ的前提下，可以直接学习到主题分布和词分布，属于无监督学习。而线性判别分析LDA使用标签计算类内散列矩阵和类间散列矩阵，是有监督学习算法。需要注意的是，机器学习中有两个算法的简称都是LDA，使用时需要注意上下文。

--------------------

**3. 以下是产生式模型的机器学习算法为：**  
LR  
SVM  
神经网络  
隐马尔科夫（HMM）  
**正确答案：D**

**题目解析：**  
常见判别模型：感知机，KNN，LR，决策树，SVM，CRF  
常见生成模型：贝叶斯，HMM

--------------------

**4. 已知一个二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为？**  
DGEBHFCA  
DGEBHFAC  
GEDBHFCA  
ABCDEFGH  
**正确答案：A**

前序遍历：根节点——左节点——右节点  
中序遍历：左节点——根节点——右节点  
后序遍历：左节点——右节点——根节点

--------------------

**5. 以下关于准确率，召回， f1-score说法错误的是：**  
准确率为TP/(TP+FP)  
召回率为TP/(TP + FN)  
f1-score为 2TP/(2TP + FP + FN)  
f1-score为 准确率\*召回率/(准确率+召回率)  
**正确答案：D**

[机器学习 精准率 — 召回率 — 准确率 — F1-Score][_ _ _ _ _ _ F1-Score]

--------------------

**6. 在贝叶斯线性回归中， 假定似然概率和先验概率都为高斯分布， 假设先验概率的高斯准确率参数为a, 似然概率的高斯准确率参数为b， 则后验概率相当于平方误差+L2正则，则其正则化参数为**  
a + b  
a / b  
a^2 + b^2  
a^2 / (b^2)  
**正确答案：A**

--------------------

**7. 把14,27,71,50,93,39按顺序插入一棵树,插入的过程不断调整使树为平衡排序二叉树,最终形成平衡排序二叉树高度为？**  
3  
4  
5  
6  
**正确答案：A**

–  
**8. 以下关于batch normalization说法正确的是：**  
normalization的均值方差计算是基于全部训练数据的  
normalization的均值方差只基于当前的minibatch  
normalization对输入层的每一维单独计算均值方差，  
normalization的输出分布服从均值为0，方差为1的高斯分布  
**正确答案：B C**

–  
**9. 以下关于二项分布说法正确的是**  
二项分布是一种离散概率分布，表示在n次伯努利试验中， 试验k次才得到第一次成功的概率  
二项分布是一种离散概率分布，表示在n次伯努利试验中，有k次成功的概率  
当n很大时候，二项分布可以用泊松分布和高斯分布逼近  
当n很大时候，二项分布可以用高斯分布逼近，但不能用泊松分布逼近  
**正确答案：B C**

–  
**10. 以下关于random forest说法错误的是**  
rf中的每棵子树都是独立同分布的  
rf中模型方差随着子树的增加而减少  
rf主要通过增加子树之间的相关性来减少模型的方差  
rf中模型偏差随着子树的增加而减少  
**正确答案：A D**

--------------------

**11. 随机变量X1,X2…X100都服从\[1,9\]的均匀分布，则(X1+X2+…+X100)/100近似服从\_\_\_\_\_\_\_\_。**  
高斯分布  
泊松分布  
均匀分布  
指数分布  
**正确答案：A**

--------------------

**12. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。**  
9  
10  
11  
12  
**正确答案：C**

最小高度自然就是等于2000个结点的完全二叉树的高度  
设根结点高度为1，n个结点完全二叉树高度：下取整(log2n) + 1  
现在是下取整(log2(2000)) + 1= 11

--------------------

**13. 下列方面不可以防止过拟合的是**  
加入正则项  
增加样本  
建立更加复杂的模型  
Bootstrap重采样  
**正确答案：C**

**题目解析：**  
ABD都是常用的防止过拟合的方法；而如果使用复杂模型，往往会在训练集中得到更好的结果，但在测试集上效果下降，即：使用复杂模型会增加过拟合的风险。

--------------------

**14. 使用中序遍历一棵二叉树得到E A C K F H D B G，使用后序遍历得到E C K A H B G D F，则先序遍历将得到（）**  
FAEKCDBHG  
FAEKCDHGB  
EAFKHDCBG  
FEAKDCHBG  
正确答案：B

--------------------

**15. 以下模型哪些是无向图**  
朴素贝叶斯  
LR  
CRF  
HMM  
**正确答案：B C**

**题目解析：**  
LR和CRF为无向图， 也是判别式模型， 一般而言很多判别式模型表现为无向图

--------------------

**16. 以下关于神经网络说法正确的是**  
神经网络可以实现非线性分类  
神经网络可以实现线性分类  
神经网络的每层神经元激活函数必须相同  
神经网络的每层神经元激活函数值阈必须在\[-1,1\]

**正确答案：A B**

--------------------

**17. 以下为防止过拟合的方法的是**  
增加样本  
L1正则  
交叉验证  
增加复杂特征

**正确答案：A B C**

--------------------

**18. CRF模型可以用来做专名识别， 语义消歧等， 以下关于CRF模型说法正确的是**  
CRF模型是产生式模型  
CRF模型是判别式模型  
CRF模型的图模型为无向图  
CRF模型的图模型为有向图

**正确答案：B C**

--------------------

**19. 以下哪些函数是凸函数？（）**  
f(x) = x  
f(x) = x3  
f(x) = x4  
f(x) = x3+x4  
**正确答案：A C**

--------------------

**20. 以下属于凸函数的是**  
e的x次方  
x的a次方  
log(x)  
f(x, y) = x的平方/y  
**正确答案：A D**

--------------------

**21. 以下是基于图的特征降维方法的是**  
LE(Laplacian eigenmap)  
LLE(local linear embedding)  
PCA  
KL  
**正确答案：A B**

--------------------

**22. 使用LR来拟合数据， 一般随机将数据分为训练集和测试集。 则随着训练集合的数据越来越多， 以下说法正确的是**  
测试集上的测试误差会越来越小  
测试集上的测试误差会越来越大  
训练集上的训练误差会越来越小  
训练集上的训练误差会越来越大  
**正确答案：A D**

--------------------

**23. 有A，B 两个国家，人口比例为4:6，A国的犯罪率为0.1%，B国的为0.2%。现在有一个新的犯罪事件，发生在A国的概率是？**  
0.15  
0.25  
0.35  
0.45  
**正确答案：B**

问题可以视为已知：P（甲）=0.4，P（乙）=0.6，P(A|甲)=0.01，P(A|乙)=0.02，求取P(甲|A)？

P(甲|A) = P(甲，A)/P(A) = P(A|甲)*P(甲) /P(A) = (0.01*0.4)/(0.01*0.4+0.02*0.6) = 0.25。

--------------------

**24. 以下模型是时序模型的是**  
GRU  
LSTM  
RNN  
CNN

**正确答案：A B C**

**题目解析：**  
RNN为一般的时序模型， LSTM和GRU对神经元进行了改造，缓解了梯度消失等问题

--------------------

**拓展：**

[京东2018秋招数据分析工程师笔试题][2018]

[_ _ _ _ _ _ F1-Score]: https://blog.csdn.net/weixin_43283397/article/details/108065384
[2018]: https://blog.csdn.net/YYIverson/article/details/100044510