来自牛客网的题库：2020奇安信秋招算法方向试卷1
1、在什么情况下，新插入链表的节点既是首节点也是尾节点
答案：链表为空时
2、一个有向无环图是否存在拓扑排序？
答案：存在
3、以下关于哈希表的描述哪个是正确的？
哈希表中的key的存放是有序的
哈希表只适合存储数字
哈希表适于做优先级队列
哈希表查询的时间复杂度是O(1)
答案：D
解析
1.哈希表不保存插入顺序，不可以按照下标读取元素；
2.哈希表的查询时间是，hashmap.get(key)，常数级的查询时间；
4、存在一个数字组成的序列[a1,a2,…,aN]，若要统计所有数字出现的次数，用以下哪种数据结构比较适合？
答案：哈希表
5、存在若干个字符串，若要查找具有相同前缀的字符串，以下哪种数据结构比较适合
答案：Trie树
解析：
Trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
6、以下哪个算法是用于求解两个正整数的最大公约数的算法？
答案：辗转相除法
7、以下哪个数据结构可用来抽象在电影院售票厅排队买票的场景？
答案：队列
8、skiplist的查询时间复杂度和以下哪种数据结构不相同？
A.红黑树，是一颗二叉搜索树，O(log2n)
B.AVL树，是一颗二叉排序树，O(log2n)
C.单链表，查找O(n)，插入删除O(1)
D.有序数组，二分查找O(log2n)
9、一个台阶总共有10 级，一次可以向上走1 级，也可以向上走2 级，请问一共有多少种走法？
答案：89
解析：斐波那契数列
2：1+1 =2
3：2+1 = 3
4: 3+2 = 5
5:5+3 = 8
6:8+5 = 13
7: 13+8 = 21
8:21 +13 = 34
9:34+21 =55
10:34+55 = 89
10、mysql的数据库索引使用的是下面那种数据结构
答案：B+树
11、关于文本表示模型，以下说法错误的是
A. 文本模型中，每篇文章可以表示成长向量，向量中的每一维代表一个单词
B. 每一维对应的权重反映了这个词在原文章的重要程度
C. 在实际应用中，一般会将不同词性的单词统一成为同一词干的形式
D. 词嵌入的核心思想是将每个词都映射成高维空间上的一个稠密向量
答案：D
解析：
词嵌入是在原来基于字典的词独热编码的一种改进。核心思想是将每个词映射成低维空间上的一个稠密向量。
12、关于隐马尔科夫模型，下列说法正确的是
A. 隐马尔科夫模型是对含有未知参数的马尔科夫链进行建模的生成模型
B. 隐马尔科夫模型中，对于每个隐状态xi和对应的输出yi都是可见的
C. 隐马尔科夫模型中的参数不包括隐状态间的转移概率
D .隐马尔科夫模型不能将分词问题转化为一个序列标注问题来建模
答案：A
解析：
“隐”指的是马尔科夫链中任意时刻的状态变量不可见
隐含状态转移概率矩阵 A 描述了马尔科夫链模型中各个隐含状态之间的转移概率隐马尔可夫模型的作用并不仅限于预测标注序列，它一共解决如下三个问题。
- 样本生成问题：给定模型，如何有效计算产生观测序列的概率？换言之，如何评估模型与观测序列之间的匹配程度？
- 序列预测问题：给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？
- 模型训练问题：给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据
13、多层感知机最少需要多少隐藏层才能表示异或逻辑？
答案：1层
解析：
参考：https://www.jianshu.com/p/9ad4df050978
考虑二元输入的情况，需要 3 个额外结点可以完成次异或操作，真中隐藏层由两个节点构成，输出层需要一个结点，用来输出异或的结果并作为下一个结点的输入。 对于四元输入，包含三次异或需要 3×3=9个节点即可完成。
14、关于集成学习，下列说法正确的是
A.基模型相关性低
B.基模型相关性高
C.bagging和boosting是主要的两类集成学习方法
D.基模型都来自同一算法
答案：C
15、若混淆矩阵中TP=40，FN=20，FP=10，TN=40，则准确率Accuracy=？
答案：8/11
解析：
准确率=（TP+TN）/总数
TP（正确挑出的正样本）+TN（正确挑出的负样本）=80
总数就是TP+FP+TN+FN=110
16、若混淆矩阵中TP=40，FN=20，FP=10，TN=40，则正类精确率Precision=？
答案：0.8
解析：
正类精确率 = 正确预测为正的样本数 /（正确预测为正的样本数 + 错误预测为正的样本数） = TP/（TP+FP）= 4/5 =0.8
17、下列关于关键词提取的说法正确的是
关键词提取中通常使用有监督算法，原因是标注的数据量太少
使用无监督算法的效果通常要好于半监督和有监督的算法
关键词抽取的方法中，textrank方法是一种基于图的算法，可以通过构造节点的权重来对其进行优化
基于主题关键词提取算法主要利用的是主题模型中关于主题的分布的性质进行关键词提取，一般对于短文本而言，这种方法并不适合。
D
解析：
A:有监督算法需要大量标注数据，通常关键词提取算法使用无监督和半监督的方法较多；B:在数据量充足的情况下，有监督的方法一般比无监督的方法效果要好；C：textrank算法从pagerank演化而来，是一种基于图的算法，可以通过构造边的权重进行优化；D正确。
18、下列关于tf-idf的中正确的是
A.tf-idf只能用于单个字符，可以将字符进行向量化，达到很好的表示效果
B.是基于统计的词表示方法，忽视了词与词的位置关系
C.其中idf公式为log((N+1)/(N(x)+1))+1，表示单个词语在文档中出现的频率
D. 是一种分布式的向量表示，但在word embedding问世之后，它已经没有应用的意义
正确答案：B
题目解析：
解析：A:可以应用于ngram；B：正确；C：idf是逆文档率，tf才是频率；D：这项技术还是有很广应用场景
19、哪种2D变换有可能破坏平行性(平行的线变换后不再平行)
投影变换
刚性变换
相似变换
仿射变换
答案：A
解析：
刚性变换就是图像的平移加旋转，非刚性就是比这更复杂的变换，如伸缩，仿射，透射，多项式等一些比较复杂的变换。
投影比如投影到曲面，可能会出现不平行的情况。
相似变换就是缩放？
仿射变换就是ax+b这种的线性变换。
20、关于SIFT特征描述错误的是
A. 具有尺度不变性
B. 具有旋转不变性
C. 检查的是图像中的极大极小值
D. 受光照变换影响大
答案：D
解析：
SIFT特点：
1.尺度不变性
2.旋转不变性
3.亮度不变性
4.噪点不敏感
5.特征维度小
6.抗遮挡
21、下述排序算法中，平均时间复杂度为nlogn且不稳定的是（ ）
A.堆排序
B. 归并排序
C.直接选择排序
D. 快速排序
答案：A，D
22、下列表述中，正确的是（ ）
A.快速排序算法是稳定的
B.二叉树中节点的数目，等于边数 + 1
C.红黑树进行插入操作的时间复杂度为O(log n)
D.哈夫曼树中的节点可以有一个孩子节点
答案：B，C
解析：
快排不稳定，哈夫曼树，除了叶子结点，全是两个子节点
23、关于GBDT算法，下列说法正确的有？
A. GBDT不适合高维稀疏特征
B. GBDT通过样本、特征、基学习器三方面并行加速训练
C. GBDT模型具有较好的鲁棒性和解释性
D. GBDT对特征值缺失不敏感
答案：A，C，D
24、关于随机森林和GBDT,下列说法正确有？
A.GBDT中的树可以同时训练，随机森林中的树不可以
B.两者都可以通过随机样本子集和随机特征子集的方式来提升模型的泛化能力
C.对任务数据集，GBDT总是优于随机森林
D.GBDT中的树相关性强，而随机森林中的树相关性弱
答案：B,C
25、以下几种NLP预训练模型中包含Transformer结构的有：
A. Word2vec
B. ELMo
C. GPT
D. BERT
答案：C，D
解析：
word2vec：CBOW和skip-grim
ELMO：双向的LSTM
GPT：单向的Transformer的Decoder
BERT：双向的Transformer的Encode
26、以下哪种激活函数的输出值有可能是-0.1？
A.Sigmoid
B.Tanh
C.ReLU
D.Leaky ReLU
答案：B，D
解析：
27、下列关于主题模型的观点中，正确的是
A.主题模型是用来做文档建模的，将文档转化为数值向量，数值向量的每个维度对应于一个主题
B.在LDA主题模型中，文章的生成有三个要素【词语，主题，文章】，词语和主题是多对多的关系，每个词语都可能代表着多个主题，C.每个主题下也有多个代表的词语
C.主题和文章也是多对多的关系，每个主题都对应着多篇文章，每篇文章也可能有多个主题
D.在短文本中使用主题模型可以比长文本得到更好的效果
答案：A，B，C
28、下列关于采样方法的描述正确的是
A. Gibbs采样的过程中首先需要随机初始化状态，随后依据条件概率进行再不同的状态下分别采样，直到马氏链收敛
B. MCMC采样法主要包括两个MC，即Monte Carlo和Markov Chain。Monte Carlo是指基于采样的数值型近似求解方法，Markov Chain则是用于采样
C. SMOTE，全称是Synthetic Minority Oversampling Technique，其思想就是在少数类的样本之间，进行插值操作来产生额外的样本。
D. ADASYN名为自适应合成抽样(Adaptive Synthetic Sampling)，其最大的特点是采用某种机制自动决定每个少数类样本需要产生多少合成样本，而不是像SMOTE那样对每个少数类样本合成同数量的样本。
答案：B，C，D
解析
A选项，gibbs采样无需等到马氏链收敛
29、神经网络训练过程中哪些现象表明可能出现了梯度爆炸
A.模型的损失函数值在训练过程中变成NaN值
B.在更新的时损失有较大的变化
C.每个节点和层的误差梯度值持续大于1.0
D.损失函数值持续减小
答案：A,B ,C
30、图像分类问题中，哪些方法可以解决数据不均衡问题
A.欠采样
B.过采样
C.数据增强
D.使用新评价指标
答案： A B C D
2 编程题
1、老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元，也可以选择一次发3元。请问老板给这位员工发放完n元奖金共有多少种不同的方法？
数据范围：1 <= n <= 10
示例1
输入
2
输出
2
说明
一共有2元奖金，有两种发放方法；第一中：分别每次发放1元，两次发放完，第二种一次全部发放完
示例2
输入
3
输出
4
说明
一共有3元奖金，有4种发放方法；第一种：分别每次发放1元，3次发放完，第二种先第一次发2元，第二次发1元； 第三种第一次发1元，第二次发2元； 第四种方法一次全部发放完
class Solution:
def CalulateMethodCount(self , num_money ):
# write code here
if num_money<=0:
return 0
if num_money==1:
return 1
if num_money==2:
return 2
if num_money==3:
return 4
a=4
b=2
c=1
sum1=0
for i in range(4,num_money+1):
sum1 = a+ b + c
c = b
b = a
a=sum1
return sum1
def CalulateMethodCount(self , num_money ):
#write code here
# 设置递归结束条件
if num_money<=0:
return 0
if num_money==1:
return 1
if num_money==2:
return 2
if num_money==3:
return 4
count=0;
for i in range(num_money-1,num_money-4,-1)
count+=self.CalulateMethodCount(i);
return count
2、撤销/恢复操作具有广泛的用途，比如word文档中输入一个单词，可以点撤销，然后可以再恢复。
编程实现如下功能： 从标准输入读取到一个字符串，字符串可包含0个或多个单词，单词以空格或者tab分隔； 如果遇到 “undo” 字符串，表示"撤销"操作，前一个字符串被撤销掉； 如果遇到"redo"字符串，表示恢复刚才撤销掉的字符串.
例如: 输入字符串 “hello undo redo world.”， 对字符串中的 undo 和 redo 处理后， 最终输出的结果为 “hello world.”
输入描述:
一行字符串： 包含0个或多个单词，单词以空格或者tab分隔
输出描述:
一行字符串： 由0个或多个单词组成，单词以空格分隔
示例1
输入
hello undo redo world.
输出
hello world.
先初始化两个栈stack和redo，然后利用双栈求解。遍历词表：
- 遇到普通词就压入stack，并清空redo栈，因为此时写入了一个新词，再往前的词已经找不回来了；
- 遇到undo就从stack中弹栈至redo；
- 遇到redo就从redo中弹栈至stack。
最终stack中的词就是最后保留下来的词
commands = input().strip().split(" ")
stack, redo = [], []
for cmd in commands:
if cmd == "undo":
if stack:
redo.append(stack.pop())
elif cmd == "redo":
if redo:
stack.append(redo.pop())
else:
redo.clear()
stack.append(cmd)
print(" ".join(stack))
