数据挖掘笔试题

数据挖掘笔试题一、单选题。（10分）1、在HMM中,如果已知观察序列和产生观察序列的状态序列,那么可用以下哪种方法直接进行参数估计（）A、EM算法B、维特比算法C、前向后向算法D、极大似然估计2、NaveBayes是一种特殊的Bayes分类器,特征变量是X,类别标签是C,它的一个假定是:（）A、各类别的先验概率P(C)是相等的B、以0为均值，sqr(2)/2为标准差的正态分布C、特征变量X的各个维度是类别条件独立随机变量D、P(X|C)是高斯分布3、在分类问题中,我们经常会遇到正负样本数据量不等的情况,比如正样本为10w条数据,负样本只有1w条数据,以下最合适的处理方法是（）A、将负样本重复10次,生成10w样本量,打乱顺序参与分类B、直接进行分类,可以最大限度利用数据C、从10w正样本中随机抽取1w参与分类D、将负样本每个权重设置为10,正样本权重为1,参与训练过程4、下列哪个不是影响聚类算法效果的主要原因有：（）？A、特征选取B、模式相似性测度C、分类准则D、已知类别的样本质量5、一监狱人脸识别准入系统用来识别待进入人员的身份，此系统一共包括识别4种不同的人员：狱警，小偷，送餐员，其他。下面哪种学习方法最适合此种应用需求：（）。A、二分类问题B、多分类问题C、层次聚类问题D、k-中心点聚类问题6、在其他条件不变的前提下，以下哪种做法容易引起机器学习中的过拟合问题（）A、增加训练集量B、减少神经网络隐藏层节点数C、删除稀疏的特征D、SVM算法中使用高斯核/RBF核代替线性核7、每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。例如，00000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有（）个A、127B、128C、255D、2568、给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是：A、O(n)B、O(nlogn)C、O(n^2)D、O(logn)9、已知一棵二叉树的先序和中序遍历序列如下：先序：A、B、C、D、E、F、G、H、I、J中序：CBAEFDIHJG其后序遍历序列为：（）A、CBDEAGIHJFB、CBDAEGIHJFC、CEDBIJHGFAD、CBFEIJHGDA10、刚毕业的小王上班有两路公交车都可以从家到公司.如果只等A车,平均需要5分钟才等到;如果只等B车,平均需要7分钟才能等到.假定两辆车运行时间独立,那么小王平均需要等多长时间才能等到A车或B车?A、2分钟B、2分35秒C、2分55秒D、3分钟二、多选题（20分）1、数据清理中，处理缺失值的方法是?A、估算B、整例删除C、变量删除D、成对删除2、以下（）属于线性分类器最佳准则?A、感知准则函数B、贝叶斯分类C、支持向量机D、Fisher准则3、以下说法中正确的是（）A、SVM对噪声(如来自其他分布的噪声样本)鲁棒B、在AdaBoost算法中,所有被分错的样本的权重更新比例相同C、Boosting和Bagging都是组合多个分类器投票的方法,二者都是根据单个分类器的正确率决定其权重D、给定n个数据点,如果其中一半用于训练,一般用于测试,则训练误差和测试误差之间的差别会随着n的增加而减少4、下列哪些方法可以用来对高维数据进行降维:A、LASSOB、主成分分析法C、聚类分析D、小波分析法E、线性判别法F、拉普拉斯特征映射5、选项代码中能正确操作数组元素的是（）intmain（）{inta[N][N]={{0,0},{0,0}};for(inti=0;iN;i++){for(intj=0;jN;j++){//访问二维数组a的值//选项代码}}}A、*(*(a+i)+j)=1B、*(a[i]+j)=1C、**(a+i)[j]=1D、*((a+i)+j)=16.e1,e2,e3,e4按顺序依次入栈，以下可能的出栈顺序有（）A、e2,e3,e4,e1B、e1,e2,e4,e3C、e3,e2,e4,e1D、e2,e4,e3,e17.非稳定排序有（）A、冒泡排序B、归并排序C、快速排序D、堆排序E、希尔排序8、关于主键PrimaryKey和索引index，以下说法正确的有（）A.唯一索引列允许为NULLB.一个关系表中的外键必为另一表的主键C.一个关系表只能有一个唯一性索引D.索引只用于查询操作，对插入操作影响不大9、下列属于哪个不属于无监督学习的是：A、k-meansB、SVMC、最大熵D、CRF10、以下与数据的存储结构无关的术语是（）A、循环队列B、链表C、哈希表D、栈三、问答题（50分）：1.谈谈HashMap和Hashtable的区别?(10分)2.有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。现在希望能返回频数最高的100个词，请写出你的方案。（10分）3、什么是聚类分析？聚类算法有哪几种？请选择一种详细描述其计算原理、步骤及优缺点（15分）。4、一维数据的拟合，给定数据集{𝑥𝑖.𝑦𝑖}(i=1,…,n)，𝑥𝑖是训练数据，.𝑦𝑖是对应的预期值。拟使用线性、二次、高次等函数进行拟合,如下：（15分）线性：f(x)=ax+b二次：f(x)=ax^2+bx+c三次：f(x)=ax^3+bx^2+cx+d（1）请依次列出线性、二次、三次拟合的误差函数表达式。（2）按照梯度下降法进行拟合，请给出具体的推导过程。（3）下图给出了线性、二次和七次拟合的效果图。请说明进行数据拟合时，需要考虑哪些问题。在本例中，你选择哪种拟合函数。四、编程题（求一个字符串S中的最长回文）（20分）GivenastringS,findthelongestpalindromicsubstringinS.YoumayassumethatthemaximumlengthofSis1000,andthereexistsoneuniquelongestpalindromicsubstring.