笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
21、设有递归算法如下，
int x(int n)
{
if(n<=3)
return 1;
else
return x(n-2)+x(n-4)+1;
}
试问计算x(x(8))时需要计算（）次x函数。
A、8
B、9
C、16
D、18
21、D
x(8)=x(6)+x(4)+1 递归计算x(8)第一次调用
x(6)=x(4)+x(2)+1 递归计算x(6)第二次调用
x(4)= x(2)+x(0)+1 递归计算x(4)第三次调用
x(4)= x(2)+x(0)+1 递归计算x(4)第四次调用
之后再调用x()计算黑体部分的结果(5次，加上前面4次，一共9次)，最后x(8)返回值为9
接着计算x(9)
x(9)=x(7)+x(5)+1 递归计算x(9)第一次调用
x(7)=x(5)+x(3)+1 递归计算x(7)第二次调用
x(5)=x(3)+x(1)+1 递归计算x(5)第三次调用
x(5)=x(3)+x(1)+1 递归计算x(5)第四次调用
之后再调用x()计算黑体部分的结果(5次，加上前面4次，一共9次)，最后x(8)返回值为9
所以总共调用x()的次数是9+9=18
22、设一组初始记录关键字序列(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是（）
A、F，H，C，D，P，A，M，Q，R，S，Y，X
B、P，A，C，S，Q，D，F，X，R，H，M，Y
C、A，D，C，R，F，Q，M，S，Y，P，H，X
D、H，C，Q，P，A，M，S，R，D，F，X，Y
22、D
第一趟冒泡：从数组第一个元素到最后一个元素扫描，比较相邻的元素，如果后一个元素小于前一个，则交换位置。第一趟结束时，最大元素到达最后一个元素位置
23、堆排序的空间复杂度是（），堆排序中构建堆的时间复杂度是（）。
A、Ｏ(logn)，O(n)
B、O(logn)，O(nlogn)
C、O(1)，O(n)
D、O(1)，O(nlogn)
23、C
“空间复杂度”指占内存大小，堆排序每次只对一个元素操作，是就地排序，所用辅助空间O(1)，空间复杂度是O（1）
在构建堆的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
24、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别0和3。当从队列中删除一个元素，再加入两 个元素后，rear和front的值分别为（）
A、2和4
B、1和5
C、4和2
D、5和1
24、A
因为出队时，front=front+1/MAXSIZE,rear不变，所以front=4
入队时，rear=rear+1/MAXSIZE,front不变，所以rear=2;
25、如下表是用户是否使用某产品的调查结果（）
UID 年龄 地区 学历 收入 用户是否使用调查产品
1 低 北方 博士 低 是
2 高 北方 本科 中 否
3 低 南方 本科 高 否
4 高 北方 研究生 中 是
请计算年龄，地区，学历，收入中对用户是否使用调查产品信息增益最大的属性（Log23≈0.63）
A、年龄
B、地区
C、学历
D、收入
25、C
不用算一眼就能看出来，所有本科学历都不使用调查产品，所有非本科学历都使用了调查产品。这种可以确定的划分导致信息熵为0，信息增益最大
26、假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为（）
A、O(logn)
B、O(n*logn)
C、O(n)
D、O(n^2)
26、B
T(n)=2^k*(T(n/(2^k)))+k*n
2^k = n,k = log(n) (以2为底)
T（n） = n*T(1)+n*log(n)<= c*n*log(n) (c为常数)
所以是O(n*logn)
27、基于统计的分词方法为（）
A、正向最大匹配法
B、逆向最大匹配法
C、最少切分
D、条件随机场
27、D
目前的分词方法归纳起来有3 类:
第一类是基于语法和规则的分词法。其基本思想就是在分词的同时进行句法、语义分析, 利用句法信息和语义信息来进行词性标注, 以解决分词歧义现象。因为现有的语法知识、句法规则十分笼统、复杂, 基于语法和规则的分词法所能达到的精确度远远还不能令人满意, 目前这种分词系统还处在试验阶段。
第二类是机械式分词法（即基于词典）。机械分词的原理是将文档中的字符串与词典中的词条进行逐一匹配, 如果词典中找到某个字符串, 则匹配成功, 可以切分, 否则不予切分。基于词典的机械分词法, 实现简单, 实用性强, 但机械分词法的最大的缺点就是词典的完备性不能得到保证。据统计, 用一个含有70 000 个词的词典去切分含有15 000 个词的语料库, 仍然有30% 以上的词条没有被分出来, 也就是说有4500 个词没有在词典中登录。
第三类是基于统计的方法。基于统计的分词法的基本原理是根据字符串在语料库中出现的统计频率来决定其是否构成词。词是字的组合, 相邻的字同时出现的次数越多, 就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映它们成为词的可信度。
最大匹配是指以词典为依据，取词典中最长单词为第一个次取字数量的扫描串，在词典中进行扫描，这是基于词典分词的方法
1.正向最大匹配法
2.逆向最大匹配法
3.最少切分法：使每一句中切出的词数最小，这也是基于词典分词的方法
条件随机场是一个基于统计的序列标记和分割的方法，属于基于统计的分词方法范畴。它定义了整个标签序列的联合概率，各状态是非独立的，彼此之间可以交互，因此可以更好地模拟现实世界的数据．
28、下列哪个不属于CRF模型对于HMM和MEMM模型的优势（）
A、特征灵活
B、速度快
C、可容纳较多上下文信息
D、全局最优
28、B
隐马尔可夫模型（Hidden Markov Model，HMM），最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM）以及条件随机场（Conditional Random Field，CRF）是序列标注中最常用也是最基本的三个模型。
HMM模型是对转移概率和表现概率直接建模，统计共现概率。
MEMM模型是对转移概率和表现概率建立联合概率，统计时统计的是条件概率，但MEMM容易陷入局部最优，是因为MEMM只在局部做归一化。
RF模型中，统计了全局概率，在 做归一化时，考虑了数据在全局的分布，而不是仅仅在局部归一化，这样就解决了MEMM中的标记偏置（label bias）的问题。
CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。特征设计灵活。（与ME一样） ————与HMM比较
同时，由于CRF计算全局最优输出节点的条件概率，它还克服了最大熵马尔可夫模型标记偏置（Label-bias）的缺点。 ­­————与MEMM比较
CRF是在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布，而不是在给定当前状态条件下，定义下一个状态的状态分布。
CRF需要训练的参数更多，与MEMM和HMM相比，它存在训练代价大、复杂度高的缺点。
29、假设一个完整的扑克牌有52张牌，2黑色（黑葵和梅花）和2红色（方块和红心）。如果给你一副完整的牌，和半副牌（1红色和1黑色），则两种情况下抽两种牌都是红色的概率是多少（）
A、1/2，1/2
B、25/102，12/50
C、50/51，24/25
D、25/51，12/25
29、B
第一种情况 26/52 * 25/51 =25/102
第二种情况 13/26 * 12/25=12/50
30、在二分类问题中，当测试集的正例和负例数量不均衡时，以下评价方案哪个是相对不合理的（）（假设 precision=TP/(TP+FP),recall=TP/(TP+FN)。）
A、Accuracy:(TP+TN)/all
B、F-value:2*recall*precision/(recall+precision)
C、G-mean:sqrt(precision*recall)
D、AUC:曲线下面积
30、A
题目提到测试集正例和负例数量不均衡，那么假设正例数量很少占10%，负例数量占大部分90%。
而且算法能正确识别所有负例，但正例只有一半能正确判别。
那么TP=0.05×all, TN=0.9×all，Accuracy=95%。
虽然Accuracy很高，但正例precision只有50%
31、下面关于ID3算法中说法错误的是（）
A、ID3算法要求特征必须离散化
B、信息增益可以用熵，而不是GINI系数来计算
C、选取信息增益最大的特征，作为树的根节点
D、ID3算法是一个二叉树模型
31、D
ID3 算法生成的决策树是一棵多叉树，分支的数量取决于分裂属性有多少 个不同的取值。
32、圆内接三角形是锐角三角形概率是多少（）
A、1/4
B、1/3
C、1/2
D、2/3
32、A
三角形的三点在圆上的位置是等概率的。这种任意位置组成的三角形中，最大的那个角必定大于等于60度，因此满是三角形是锐角的变化范围是60-90度，钝角的范围是90-180度
33、六个人排成一排，甲与乙不相邻，且甲与丙不相邻的不同排法数是多少（）
A、216
B、240
C、288
D、360
33、C
1，首先将甲乙丙拿出来，剩下三个做全排列，有A(3,3)=6种排列,
2，将甲乙两个插入第一步三个人的四个空隙中，有A(4,2)=12种
3，剩下丙插入到前五个人中的六个空隙中，其中甲的左右两侧不符合，
还有4个符合条件的空隙，C(4,1)=4
4,总共有6*12*4=288
34、在其他条件不变的前提下，以下哪种做法容易引起机器学习中的过拟合问题（）
A、增加训练集量
B、减少神经网络隐藏层节点数
C、删除稀疏的特征 S
D、SVM算法中使用高斯核/RBF核代替线性核
34、B
过拟合就是导致拟合过度，算法的普适性降低
B选项减少神经网络隐层节点数，也就减小了输入层与隐层，隐层与输出层之间的连接矩阵，使其适应性变差
35、计算一个任意三角形的面积，S=√(p(p-a)(p-b)(p-c)),p=(a+b+c)/2,以下等价类测试用例中，不属于无效等价类的是（）
A、a=5，b=3，c=6;
B、a=2，b=3，c=5;
C、a=7，b=3，c=3;
D、a=2，b=6，c=3;
35、A
选项A满足三角形两边之和大于第三边，两边之差小于第三边，是有效的
选项BCD都不满足两边之和大于第三边，属于等级无效的
二、多选题
36、下列排序算法的常规实现中，哪些空间复杂度是O(1)
A、冒泡
B、选择
C、归并
D、快排
E、堆排序
36、A.B.E
冒泡排序,选择排序,堆排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引).
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
