公司：奇虎360
岗位：机器学习算法工程师
笔试时间：2022年10月9号
1 选择题
1、 $E(X^2)$的计算
P{X=1} = 2/3, P{X=0} = 1/6, P{X=-1} = 1/6
解析：
$E(X^2) = 1^2 * 2/3 + 0^2 * 1/6 + (-1)^2 * 1/6 = 2/3 + 1/6 = 5/6$
2、以下森林转二叉树为什么样子的？
解析：
森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。
将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
3、选择错误的
A. 数组大小无法扩容
B. 数组添加、删除操作方便
答案：B
解析：
数组不擅长插入（添加）和删除元素。数组的优点在于它是连续的，所以查找数据速度很快。但这也是它的一个缺点。正因为它是连续的，所以当插入一个元素时，插入点后所有的元素全部都要向后移；而删除一个元素时，删除点后所有的元素全部都要向前移。
4、 以下降维的方法是有监督学习的是？
A. LDA
B. FA
C. PCA
D. LLE
答案：A
解析：
Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的（supervised）线性降维算法
5、 在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是()。
A、i++
B、i=j+1
C、i=i-j+1
D、i=j-i+1
答案：C
解析：在简单的模式匹配中，当两个字符不等时，目标串i回溯到原来未知的下一个位置，即i=i-j+1
6、Java中Thread 判断线程是否活动的函数是？
答案：isAlive()
解析：
判断线程结束的两种方法
方法1：通过Thread类中的isAlive()方法判断线程是否处于活动状态。
方法2：通过Thread.activeCount()方法判断当前线程的线程组中活动线程的数目，为1时其他线程运行完毕。
7、根据X,Y二维随机变量分布律，求E（X）
分布表我没记住，公式是先计算P(X=a)=m和P(X=b)=n，则E(X) =a×m+b×n
8、已知P（A）= P（B）=P（C）=1/4，P(AB)=1/6,P(AC)=P(BC)=0,求ABC都不发生的概率
因为P(AB)=1/6,P(AC)=P(BC)=0，则A与B集合相交，C集合与谁都不想交，则P（ABC）表示三者相交的概率，则P(ABC)=0
P(A+B+C)=P(A)+P(B)+P©-P(AB)-P(BC)-P(AC)+P(ABC)
\=1/4+1/4+1/4-1/6
\=7/12
A、B、C全不发生的概率=1-P(A+B+C)=1-7/12=5/12
9、Python open以二进制打开只用于哪种模式
答案：w+
解析：
以二进制格式打开一个文件只用于写入。 如果该文件已存在则打开文件，并从开头开始编辑，即原有内容会被删除。 如果该文件不存在，创建新文件。
10、Python异常的基类是
答案：BaseException
11、在Java中，以下关于方法重载和方法重写描述正确的是？
A. 方法重载和方法的重写实现的功能相同
B.方法重载 方法名必须相同
C. 方法重载的返回值类型必须一致，参数项必须不同
D. 方法重写的返回值类型必须相同或相容。（或是其子类）
答案：B，D
解析：
B，Java的方法的重载：方法名相同，参数类型不同
12、图像检索可以分为类似文本搜索引擎的三个步骤？
答案：提取特征、建索引build以及查询
13、以下错误的是
A. 图像分析研究构造图像的描述方法，更多地用符号表示各种图像
B. 图像分析主要研究点，线面和体的表示方法以及视觉信息的显示方法
C . 图像分析主要研究图像内容的分析，解析和识别
D. 图像分析主要研究图像传输、存储增强和复原
答案：D
解析：
图像处理主要研究图像传输、存储、增强和复原
14、etc/shadow加密使用的模型是
A. 不可逆
B . 对称加密
C. 单密钥
答案：A，B，C
目前使用的加密方式主要有以下几类：
1.对称加密
使用对称加密，加密和解密都使用同一个密钥，其特点是速度快，常用的方式为：3DES(Data Encrypt Standard)，该方法采用56位密钥，其中3表示运行三轮；AES(Advanced Encrypt Standard)，采用变长密钥。
对称加密的缺陷在于密钥的管理及分发比较困难。
2.公钥加密
公钥加密也叫非对称加密，即采用 私钥/公钥 (S/P)–> (security/public)的加密方。其中私钥加密的文件只能用与之对应的公钥解密，反之亦然。但是公钥可以从私钥中提取出来，因此有私钥，则可以推测出公钥；反之则不行。
公钥加密的特点是加密速度慢，但是安全性高。它通常用于密钥的分发，主要采用的算法有RSA和DSA。
3.单向加密
单向加密只能加密，不能解密。它是hash算法的一种。主要用于提取数据的特征码，其特征为：
a)无论是输入多大的数据，其输出是定长的。
b)如果输入的数据一样，结果必然一样，反之，输入的数据有微小的改变，将引起输出的巨大变化，通常称为“蝴蝶效应”和“雪崩效应”。单向加密这些特征可以避免加密串被反向推断。
15、用于计算像素区域的修复 负对数 损失函数？
16、基于C4.5算法的决策树节点分裂标准是什么？
答案：信息增益比，或叫信息增益率
17、生成模型和判别模型？
解析：
（1）常见的判别模型
K近邻(KNN)
线性回归(Linear Regression)
逻辑斯蒂回归(Logistic Regression)
神经网络(NN)
支持向量机(SVM)
高斯过程(Gaussian Process)
条件随机场(CRF)
分类回归树CART(Classification and Regression Tree)
（2）常见的生成模型LDA主题模型
朴素贝叶斯
混合高斯模型
隐马尔科夫模型(HMM)！
贝叶斯网络
Sigmoid Belief Networks
马尔科夫随机场(Markov Random Fields)
深度信念网络(DBN)
18、正确的是？
A.P问题属于NP问题
B. P类问题属于NP类问题中可在多项式时间验证并解决的问题
答案：A,B
19、音字转换技术是指由计算机自动地将拼音串转换为汉字串，常用的音字转换技术是。
A.基于统计知识的方法
B.基于模板匹配的方法
C.基于上下文关联的方法
D.A、B、C以上都是
答案：D
20、以下正确 的是
A.友元函数没有this指针
21、信息熵公式
$$H=−∑_xP(x)log_2P(x)$$
22、已知约束下，Z = 2x+6y最小值为2，求a
x−y≥0
x+y≤a
x+2y≥1
23、已下分布律
求 P(1<x≤3)
24、AOV网如下，拓扑序列是？
答案：V6，V1，V4，V3，V2,V 5
解析：
拓扑排序算法思想： 对一个有向无环图，重复下列操作，直到所有顶点输出完。
在有向图中选一个没有前驱的顶点输出（选择入度为0的顶点）；
从图中删除该顶点和所有以它为尾的弧（修改其它顶点入度）。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H47jtgsO-1665412192073)(C:\Users\Mgege\Downloads\拓扑序列.png)]
2 编程题
1、题目
给出一些仅包含正整数，加号，乘号和等号的方程，请判断这些方程能否通过插入至多一个数位（若原方程成立则可以不插）使得方程成立。
插入一个数位即将方程视为一个字符串，并将一个0到9之间的数插入中间，开头或末尾。
输入描述
第一行有一个正整数T(1<=T<=10)，代表方程的数量。
接下来T行，每行均有一个仅包含十进制正整数，加号和乘号的方程。每个方程中均只会包含一个等号。
保证输入的方程合法，即每个数均不含前导零，开头和末尾没有运算符，且没有两个相邻的运算符。
输入中方程两边计算结果的最大值不超过1000000000，且每个方程的长度不超过1000。
输出描述
对于每个方程，若其成立或可以通过往该方程中插入一个数位使得方程成立，则输出Yes，否则输出No。
示例：
样例输入
6
16=1+2_3
7_8_9=54
1+1=1+22
4_6=22+2
15+7=1+2
11+1=1+5
输出
Yes
Yes
No
Yes
Yes
No
（1）解析
暴力求解，在每个位置插入一个0-9的数，都计算一遍等号左右两边是否相等，计算字符串的计算结果，参考LeetCode 计算器这个题的解决方法，用栈来实现【https://leetcode.cn/problems/calculator-lcci/】。但是这种方法超时了，只有54%的AC率。
（2）Python实现
n = int(input())
# 参考https://leetcode.cn/problems/calculator-lcci/
def calculate( s: str) -> int:
n = len(s)
stack = []
preSign = '+'
num = 0
for i in range(n):
if s[i] != ' ' and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0')
if i == n - 1 or s[i] in '+-*/':
if preSign == '+':
stack.append(num)
elif preSign == '-':
stack.append(-num)
elif preSign == '*':
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num))
preSign = s[i]
num = 0
return sum(stack)
for i in range(n):
s = input()
tag = 0
idx = s.find('=')
left = s[:idx]
right = s[idx+1:]
if calculate(left)==calculate(right):
tag = 1
if tag==0:
for i in range(len(s)+1):
for j in range(10):
str_list = list(s)
str_list.insert(i,str(j))
in_s = ''.join(str_list)
id = in_s.find('=')
left_s = in_s[:id]
right_s = in_s[id+1:]
if calculate(left_s)==calculate(right_s):
tag = 1
if tag==0:
print('No')
else:
print('Yes')
print()
2、题目描述：
小马最近找到了一款打气球的游戏。
每一回合都会有n个气球，每个气球都有对应的分值，第i个气球的分值为ai。
这一回合内，会给小马两发子弹，但是由于小马的枪法不准，一发子弹最多只能打破一个气球，甚至小马可能一个气球都打不中。
现给出小马的得分规则：
若小马一只气球都没打中，记小马得0分。
若小马打中了第i只气球，记小马得ai分。
若小马打中了第i只气球和第j只气球（i＜j），记小马得ai|aj分。
（其中 | 代表按位或，按位或的规则如下：
参加运算的两个数，按二进制位进行或运算，只要两个数中的一个为1，结果就为1。
即 0|0=0,1|0=1，1|1=1。
例：2|4即00000010|00000100=00000110，所以2|4=6 ）
现在请你计算所有情况下小马的得分之和。
第一行，一个整数n，表示此回合的气球数量。
第二行，用空格分开的n个整数，第i个整数为ai，表示每个气球对应的分值。
1≤n≤50000,1≤ai≤100000
一行一个整数，代表所有情况下小马的得分之和。
示例
样例输入
3
1 2 3样例输出
15
