【数据挖掘】2020奇安信秋招算法方向试卷1 笔试题解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 2020年奇安信秋招算法方向试卷1的题目解析,覆盖了数据结构、机器学习、深度学习、自然语言处理、排序算法、激活函数、主题模型、采样方法、图像处理等多个领域的知识点。

来自牛客网的题库: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,然后利用双栈求解。遍历词表:

  1. ​ 遇到普通词就压入stack,并清空redo栈,因为此时写入了一个新词,再往前的词已经找不回来了;
  2. ​ 遇到undo就从stack中弹栈至redo;
  3. ​ 遇到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))
目录
相关文章
|
27天前
|
负载均衡 算法 Java
Spring Cloud全解析:负载均衡算法
本文介绍了负载均衡的两种方式:集中式负载均衡和进程内负载均衡,以及常见的负载均衡算法,包括轮询、随机、源地址哈希、加权轮询、加权随机和最小连接数等方法,帮助读者更好地理解和应用负载均衡技术。
|
7天前
|
算法 调度
操作系统的心脏:深入解析进程调度算法
本文旨在深入探讨现代操作系统中的核心功能之一——进程调度。进程调度算法是操作系统用于分配CPU时间片给各个进程的机制,以确保系统资源的高效利用和公平分配。本文将详细介绍几种主要的进程调度算法,包括先来先服务(FCFS)、短作业优先(SJF)、时间片轮转(RR)以及优先级调度(PS)。我们将分析每种算法的基本原理、优缺点及其适用场景。同时,本文还将讨论多级反馈队列(MFQ)调度算法,并探讨这些算法在实际应用中的表现及未来发展趋势。通过深入解析这些内容,希望能够为读者提供对操作系统进程调度机制的全面理解。
|
1月前
|
机器学习/深度学习 数据采集 算法
数据挖掘和机器学习算法
数据挖掘和机器学习算法
|
1月前
|
机器学习/深度学习 数据采集 存储
一文读懂蒙特卡洛算法:从概率模拟到机器学习模型优化的全方位解析
蒙特卡洛方法起源于1945年科学家斯坦尼斯劳·乌拉姆对纸牌游戏中概率问题的思考,与约翰·冯·诺依曼共同奠定了该方法的理论基础。该方法通过模拟大量随机场景来近似复杂问题的解,因命名灵感源自蒙特卡洛赌场。如今,蒙特卡洛方法广泛应用于机器学习领域,尤其在超参数调优、贝叶斯滤波等方面表现出色。通过随机采样超参数空间,蒙特卡洛方法能够高效地找到优质组合,适用于处理高维度、非线性问题。本文通过实例展示了蒙特卡洛方法在估算圆周率π和优化机器学习模型中的应用,并对比了其与网格搜索方法的性能。
166 1
|
2月前
|
算法 JavaScript 前端开发
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
131 1
|
2月前
|
缓存 算法 前端开发
深入理解缓存淘汰策略:LRU和LFU算法的解析与应用
【8月更文挑战第25天】在计算机科学领域,高效管理资源对于提升系统性能至关重要。内存缓存作为一种加速数据读取的有效方法,其管理策略直接影响整体性能。本文重点介绍两种常用的缓存淘汰算法:LRU(最近最少使用)和LFU(最不经常使用)。LRU算法依据数据最近是否被访问来进行淘汰决策;而LFU算法则根据数据的访问频率做出判断。这两种算法各有特点,适用于不同的应用场景。通过深入分析这两种算法的原理、实现方式及适用场景,本文旨在帮助开发者更好地理解缓存管理机制,从而在实际应用中作出更合理的选择,有效提升系统性能和用户体验。
82 1
|
2月前
|
JavaScript 算法 前端开发
"揭秘Vue.js的高效渲染秘诀:深度解析Diff算法如何让前端开发快人一步"
【8月更文挑战第20天】Vue.js是一款备受欢迎的前端框架,以其声明式的响应式数据绑定和组件化开发著称。在Vue中,Diff算法是核心之一,它高效计算虚拟DOM更新时所需的最小实际DOM变更,确保界面快速准确更新。算法通过比较新旧虚拟DOM树的同层级节点,递归检查子节点,并利用`key`属性优化列表更新。虽然存在局限性,如难以处理跨层级节点移动,但Diff算法仍是Vue高效更新机制的关键,帮助开发者构建高性能Web应用。
53 1
|
2月前
|
机器学习/深度学习 自然语言处理 负载均衡
揭秘混合专家(MoE)模型的神秘面纱:算法、系统和应用三大视角全面解析,带你领略深度学习领域的前沿技术!
【8月更文挑战第19天】在深度学习领域,混合专家(Mixture of Experts, MoE)模型通过整合多个小型专家网络的输出以实现高性能。从算法视角,MoE利用门控网络分配输入至专家网络,并通过组合机制集成输出。系统视角下,MoE需考虑并行化、通信开销及负载均衡等优化策略。在应用层面,MoE已成功应用于Google的BERT模型、Facebook的推荐系统及Microsoft的语音识别系统等多个场景。这是一种强有力的工具,能够解决复杂问题并提升效率。
57 2

热门文章

最新文章

推荐镜像

更多
下一篇
无影云桌面