来自牛客网：【2020】奇安信秋招算法方向试卷3
1、设计一个判别表达式中左，右括号是否配对出现的算法，采用____数据结构最佳
答案：栈
2、对于有n 个结点的二叉树, 其高度为( )
答案：未知，可以随意变换高度
3、如何判定一个头指针为head的带头结点的单链表为空表( )
答案：head→next==NULL
4、对于顺序存储的有序表(1,2,3,4,5,6,7,8,9)，若采用折半查找查找元素4，需要查几次?
答案：4
5、redis在的有序集合中在数据量极少的情况下使用的一下那种结构存储方案
答案：压缩表
6、先进先出页面置换算法中以下描述正确的是
答案：最先进来页面最先淘汰出去
7、从一个大量整数中找出最大的10个数，以下使用最优的算法是（）
A.最大堆算法
B.快速排序
C.冒泡算法
D.选择排序
8、HashMap与HashTable相关以下描述不正确的是
A.HashMap不能进行数组扩容
B.二者都可以进行数组扩容
C.二者都是以链表来作为解决冲突方案
D.二者都是以散列表数据结构存储数据
答案：A
9、下列哪个函数不是常用激活函数？D
A.Sigmoid
B.Tanh
C.Relu
D.Exp
答案：D
10、深度网络反向传播中，第N层发生梯度消失，则？
答案：N层的网络梯度消失
11、以下关于dropout的说法中，正确的有？
A.使用时需要较大的learning rate
B.有助于防止过拟合
C.有助于防止梯度消失
D.减少了模型参数数量
12、多分类函数输出为(P1, P2, …, Pk), 下列哪个函数的Pi之和为1？
A.Relu
B.Sigmoid
C.Tanh
D.Softmax
13、此说法是否正确：word2vec模型由多个深度神经网络模型构成。
答案：错误
14、以下不属于凸函数的是？
A.y = logx
B.y = xlogx
C.y = ||x||
D.y=e^ax
答案：D
15、机器学习中L1正则化和L2正则化的区别是？
答案：使用L1可以得到稀疏的权值，使用L2可以得到平滑的权值。
解析：
16、如下8个点聚为3类，A1(1,2),A2(3,1),A3(8,4),B1(5,8),B2(4,1),B3(6,4),C1(3,5),C2(4,9),采用K均值算法，以下不属于第一次循环后的聚类中心的是？
A.(A1,A2,B2)
B.(B1,A3,C2)
C.(B1,A2,C2)
D.(C1,B3)
答案：C
解析：
17、通常，在LSTM中，遗忘门、输入门和输出门使用（ ）函数作为激活函数。
答案：Sigmoid函数
18、以下关于CNN的描述错误的是？
A.卷积操作可获取图像区域不同类型的特征。
B.汇合等操作可对提取出的特征进行融合和抽象。
C.随着若干卷积、汇合层的堆叠，各层得到的深度特征逐渐从泛化特征过度到高层语义表示。
D.不能通过叠加多层小卷积核取得与大卷积核同等规模的感受野。
答案：D
19、一个有n个顶点的图最少有( )条边。
答案：0
20、8个外观一样的铁球，其中一个较轻，给你一个天秤，至少（ ）次可以找出较轻的球？
答案：2
21、以下属于生成式模型的是？
A.隐马尔科夫模型
B.神经网络
C.贝叶斯网
D.条件随机场
答案：A，C
22、以下关于自然语言处理错误的有？
A.N-gram模型相对神经网络的主要优点是其具有更高的模型容量，且处理样本只需非常少的计算量。
B.在许多自然语言应用中，通常希望模型产生字符作为输出的基本单位。
C.加速神经语言模型训练的一种方式是，避免明确地计算个别未出现在下一位置的词对梯度的贡献。
D.在神经机器翻译中，为生成以源句为条件的整句，模型必须具有表示整个源句的方式。
答案： B,C
23、下列哪些库可以用于词嵌入？
A.Word2vec
B.Glove
C.Fasttext
D.Numpy
答案：A，B，C
24、关于PCA的，哪些说法为真？
A.PCA是非监督学习模型
B.算法优先保留方差最大的维度
C.主成分数量<=特征维度数
D.所有主成分彼此正交
答案：A,B,C,D
25、下列排序算法中不是稳定排序的是？
直接选择排序
直接插入排序
希尔排序
快速排序
答案：A,C,D
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 直接选择排序 | O(n²) | O(n²) | O(n) | O(1) | 不稳定 |
| 直接插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(nlogn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 希尔排序 | O(nlogn) | O(ns) | O(n) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 基数排序 | O(N*M) | O(N*M) | O(N*M) | O(M) | 稳定 |
26、以下激活函数，哪个的输出值不为负？
答案：ReLU、Sigmoid
解析：
27、如果在线性回归模型中增加一个特征变量，下列可能发生的是？
R-squared 增大，Adjust R-squared 增大
R-squared 增大，Adjust R-squared 减小
R-squared 减小，Adjust R-squared 减小
R-squared 减小，Adjust R-squared 增大
答案：A，B
解析：https://zhuanlan.zhihu.com/p/340105912
28、想要训练一个 ML 模型，样本数量有 100 万个，特征维度是 5000，面对如此大数据，如何有效地训练模型？
A.对训练集随机采样，在随机采样的数据上建立模型
B.尝试使用在线机器学习算法
C.使用 PCA 算法减少特征维度
答案：A，B，C
29、下列说法错误的有？
A. Bagging可以降低方差
B. Random Forest可以降低方差
C. Boosting可以降低偏差
D. Decision Tree可以降低偏差
答案：D
Random Forest属于bagging,是降低方差
30、以下描述正确的是？
链表进行插入、删除操作，比顺序表中效率高
散列法存储的思想是由关键字值决定数据的存储地址
一个广义表的表尾总是一个广义表
数组元素的下标值越大，存取时间越长
答案：A、B、C
解析：存取，指读出，写入，时间复杂度都是O(1)，不是插入和删除操作。
2 编程题
1、有一个大型仓库使用拣货机器人从不同的货架间取货。
已知：
（1）货架呈二维网格排列，网格中的每个货架只会放置一种商品。
（2）受这代设备的技术水平所限，机器人只能沿上下左右四个方向移动，还不能沿斜线移动，请理解。
仓库当前使用的拣货算法是这样：
（1）一张订单会包含X种商品，分布在X个货架上
（2）结合将这X种商品的所在位置，将地图上的商品分解为Y个“商品堆”，然后同时派出Y个机器人，并发取货，每个机器人只负责一个“商品堆”。
（3）“商品堆”的定义是上下左右彼此相邻的一组商品。
在订单被分析后，给你一个由 ‘1’（该货架有待取货物）和 ‘0’（该货架没有待取货物）组成的的二维网格表示货架地图，请计算需要派出的机器人的数量。
比如，下面的这张货物地图：
在这个例子中，一共有6“堆”商品，共需要同时派出6个机器人。
输入例子1:
[[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,1,0,1]]
输出例子1:
3
链接：https://www.nowcoder.com/questionTerminal/e683b9c28b594e97a3e498e5db29ea89
来源：牛客网
class Solution:
def numIslands(self , grid ):
# write code here
ls=[(-1,0),(1,0),(0,-1),(0,1)]
n=len(grid)
m=len(grid[0])
nums=0
def dfs(i,j):
grid[i][j]=0
for k in ls:
new_i=k[0]+i
new_j=k[1]+j
if 0<=new_i<n and 0<=new_j<m and grid[new_i][new_j]=="1":
dfs(new_i,new_j)
for i in range(n):
for j in range(m):
if grid[i][j]=="1":
nums+=1
dfs(i,j)
return nums
2 、在某厂，产品经理同学的工作职责除了给开发同学提需求，还有一件极其重要的事：对产品运营数据做归因分析。
某天，该产品经理同学接到老板要求：根据在过去一段时间内产品的“每日活跃用户数”，统计出最长的增长总天数，也就是把保持增长势头（可以不连续）的天数抽出来，你可能会得到多个新序列，计算最长的那个序列的总天数。
我们把该产品自上线以来“每日的活跃用户数”，都按照顺序放入一个数组，比如：
[1,5,122,34,45,232,342,34]，以这组数据为例，把其中所有的增长子序列罗列出来：
形成了
第一个子序列： [1,5,122]
第二个子序列：[34,45,232,342]
第三个子序列：[1,5,122,232,342]
第四个子序列：[1,5,34,45,232,342]
这四个序列，其中最长的是第四个，所以这个例子中，最长的增长总天数是：6
因为该产品上线时间有十几年了，产品同学数了1个小时，眼都数花了，最后只好放弃，她决定用请开发同学吃饭，来解决这个问题，你能帮帮她吗？
输入例子1:
[10,9,2,5,3,6,101,18]
输出例子1:
4
例子说明1:
最长增长的子序列为 [2,3,6,101] 或者 [2,5,6,101]或者[2,3,6,18]或者[2,5,6,18]，所以返回长度 4。
