企业：深信服科技 机器学习工程师
1 不定项选择题
1、 均衡二叉树，概念是n-1层的数是满二叉树，当有400个节点，树的高度为多少？
答案：9
n-1是完全二叉树，则高度为n-1的完全二叉树结点数为$2^8-1$，高度为n的完全二叉树结点数为$2^9-1 =525 $，则400个节点，是高度为9的均衡二叉树
2、如果一个二分类模型的召回率为99% ，误报率时为1%，正负样本比例时1：100，那么该模型的精确率大概是多少
答案：50%
因为正负样本比例为1:100，则假设正样本数量为100，负样本数量为10000
因为召回率为99%
$$召回率 = \frac{TP}{TP+FN}=99\%$$
当正样本数量为100时，则TP=99，FN =1。
又因为误报率为1%，根据公式
$$误报率 = \frac{FP}{FP+TN} = 1\%$$
假设TN=10000，则FP约等于101
所以精准率
$$精准率 = \frac{TP}{TP+FP} = \frac{99}{99+101} \approx 50\%$$
3、降低过拟合的方法（A、B、D）
A.正则化
B. 增加样本数量
C. 增加模型参数
D. 删除稀疏的特征
4、由3个a,4个b和2个c构成的所有字符串中,包含子串’abc’的共有（ ）个.
答案：390
解析：
明确要的结果是只包含一个“abc”的，所有组合中可能出现0、1、2个abc.将abc作为一个整体就可以去掉0个abc的情况了。
1.包含1~2个abc的组合数：全排列(2个a,3个b，1个C,1个abc)，7！/(2!3!1!1!)=420
2.包含2个abc的组合数：全排列(1个a,2个b,21个abc ) ，5！/（1！2！2！）=30
故只含一个abc的组合数是420-30=390
5、一堆石子由10个，两个人A、B轮流从中取石子，规定每次至少取一个，最多取三个，取走最后石子的人获胜，在A先手的情况下必胜的是
答案：A
解析
只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，取走最后石子的人获胜?
举一个最简单的例子就是，当n=m+1时，此时不管先手取多少，后手都能把剩下的取完，拓展到n等于m+1的倍数时，不管先手取多少，后手都可以取（m+1减去先手取的个数）个，最后先手一定会面临n=m+1的情况，此时先手必败，否则先手必胜。
可以手推一下验证程序的正确性，如n=3,m=1,A 先拿，最后拿的也是A，程序验证也是这样的结果。
#include<stdio.h>
int main()
{
int n=10,m=3;
if(n%(m+1)==0)
printf("先手必败\n");
else
printf("先手必胜\n");
}
2 填空题
1、120名儿童到游乐场去玩，他们可以其旋转木马，坐滑行铁道，成宇宙飞船，已知其中20人三种多玩过，60人至少玩过其中的两种，若每次乘坐一次的费用是5块，游乐场共收入1000，可知多少名儿童没有玩过其中一种
答案：0
解析：
只玩过两种的人：60-20=40
还剩的费用：1000-20×3×5-40×2×5=300元
只玩过一种的人：300/5=60人
什么都没玩过的：120-60-60=0人
2、从1到10000中取出奇数位置的数，再从剩下的数中去除奇数位置的数，反复去除直到所有数都去掉，最后一个被去除的数是
答案：8191
#include <iostream>
using namespace std;
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n=10000;
int k = 1;
while (pow(2, k) <= n + 1) {
k++;
}
cout << pow(2, k - 1) - 1 << endl;
}
3、已知一个有限长度正整数序列a[1]，a[2]…，满足两个条件，
a[i+2]>a[i],对于i>=1；
a[i-2]>a[i],对于i>3，则序列最小长度为
答案：？
4、结点数为2020的二叉树，叶节点数最少是多少
答案：1
只有单边的二叉树结构
5、稳定的排序算法有哪些？不稳定的有哪些？
稳定的排序算法有以下4种：1、冒泡排序；2、插入排序；3、归并排序；4、基数排序
不稳定的排序算法有4种：选择排序、快速排序、堆排序、希尔排序
6、不是基于比较排序算法？
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
3 编程题
1、设定一种五进制数值表示方式，它的每一数位可能是字幕o,y,e、a、s其中一个，分别嗲表数字0，1，2，3，4.例如五进制数ya对应的十进制为8，五进制数为ysoae对应的十进制为1142,现在给定一个五进制数，输出它的十进制数，或给定一个十进制数，输出它的五进制数
输入
4
ya
83
ysoae
3958输出
8
aya
1142
yyyaya
def tansfer_10_to_5(n):
a = [0,1,2,3,4,5,6,7,8,9,'A','B','C','D','E','F']
b = []
while True:
s = n//5
y = n%5
b = b+[y]
if s==0:
break
n = s
b.reverse()
dic= {0:'o',1:'y',2:'e',3:'a',4:'s'}
d = [dic[i] for i in b]
return ''.join(d)
def tansfer_5_to_10(n):
return int(str(n),5)
for i in range(N):
ss = str(input())
if ss.isdigit():
print(tansfer_10_to_5(int(ss)))
else:
dic = {'o':'0','y':'1','e':'2','a':'3','s':'4'}
s = ''.join([dic[i] for i in str(ss)])
print(tansfer_5_to_10(int(s)))
2、 员工旅游，部门中每个人都有一个方便旅游的时间段，如果某个员工方柏霓的时间段内旅游，则这个员工觉得方便，反之
第一行为一个正整数T，表示测试组数，T<=100
每组测试数据的第一行是一个正整数N，表示有多少名员工，
接下来是N行，每行表示一个员工的方便时间段，用两个正整数A，B表示，A＜＝Ｂ ＜＝１００００００，例如A为５，B为８，表示该员工再５，６，７，８这四个时间点旅游都是方便的。
输出每组测试数据输出一行，为一个整数，表示最多可以让多少人觉得方便
输入：
3
2
2 5
8 9
3
4 10
7 12
10 10
10
2 8
9 10
4 7
2 5
5 7
3 6
1 4
6 9
7 8
4 6输出
1
3
6
