【数据挖掘】2022年深信服科技机器学习工程师笔试

企业：深信服科技 机器学习工程师

1 不定项选择题

1、 均衡二叉树，概念是n-1层的数是满二叉树，当有400个节点，树的高度为多少？

答案：9

n-1是完全二叉树，则高度为n-1的完全二叉树结点数为$2^8-1=255$，高度为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
int main()
{
    int n=10,m=3;

	if(n%(m+1)==0)  
		printf("先手必败\n");
	else 
		printf("先手必胜\n");

}
1
2
3
4
5
6
7
8
9
10
11

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 
using namespace std;
#include
#include
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;
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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