2022宇视科技算法岗笔试真题及答案 附代码实现过程

2022宇视科技算法岗笔试真题及答案附代码实现过程

一、单项选择题（总共10题，每题2分）1.对于长度为n的无序数组，快速排序的平均时间复杂度是（）。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)2.以下数据结构中，插入和删除操作不需要移动元素的是（）。A.数组B.单向链表C.双向队列D.栈3.一棵完全二叉树有100个节点，其叶子节点数为（）。A.49B.50C.51D.524.动态规划适用于解决（）问题。A.子问题独立且重叠B.子问题独立且不重叠C.子问题不独立且重叠D.子问题不独立且不重叠5.KMP算法的核心是利用（）避免重复匹配。A.后缀函数B.前缀函数（部分匹配表）C.哈希表D.平衡树6.Dijkstra算法用于求解（）。A.有向无环图的最长路径B.带权无向图的单源最短路径（非负权）C.带权有向图的多源最短路径D.无向图的最小生成树7.以下哪种方法不能缓解过拟合？（）A.增加正则化项B.减少训练数据量C.提前终止D.dropout层8.处理哈希冲突的方法不包括（）。A.开放寻址法B.链地址法C.再哈希法D.二分查找法9.梯度下降中，批量梯度下降（BGD）的特点是（）。A.每次用全部数据计算梯度B.每次用单个样本计算梯度C.每次用小批量数据计算梯度D.梯度方向随机10.以下排序算法中，稳定的是（）。A.快速排序B.堆排序C.归并排序D.希尔排序二、填空题（总共10题，每题2分）1.堆排序的时间复杂度为________（平均情况）。2.BFS（广度优先搜索）通常使用________数据结构来实现。3.归并排序的核心思想是________。4.KMP算法中，模式串“ABABC”的next数组为________（从0开始索引）。5.动态规划中，状态转移方程描述的是________之间的关系。6.求解所有点对最短路径问题，通常使用________算法。7.卷积神经网络（CNN）中，________层用于减少特征图尺寸。8.决策树中，常用的划分准则有信息增益、基尼系数和________。9.哈希表的负载因子是指________与表长的比值。10.深度神经网络中，梯度消失的常见原因是使用了________激活函数（如sigmoid）。三、判断题（总共10题，每题2分）1.快速排序是稳定的排序算法。（）2.二叉搜索树的中序遍历结果一定是有序的。（）3.KMP算法的时间复杂度为O(n+m)，其中n是主串长度，m是模式串长度。（）4.动态规划要求子问题之间必须独立。（）5.BFS适合求解无权图中的最短路径问题。（）6.过拟合的主要原因是模型复杂度低，无法拟合数据。（）7.归并排序的空间复杂度为O(n)。（）8.支持向量机（SVM）只能处理线性可分问题。（）9.哈希表的查找时间复杂度在平均情况下是O(1)。（）10.梯度下降算法一定能找到全局最优解。（）四、简答题（总共4题，每题5分）1.简述快速排序的基本步骤。2.KMP算法中next数组的作用是什么？如何计算？3.动态规划与分治算法的主要区别是什么？4.卷积神经网络中卷积层的作用是什么？五、讨论题（总共4题，每题5分）1.过拟合的常见原因有哪些？可以采取哪些方法缓解？2.比较Dijkstra算法和Floyd算法的适用场景。3.归并排序和快速排序的优缺点分别是什么？4.梯度下降优化方法（如SGD、Adam）的主要区别是什么？如何选择？---答案及解析一、单项选择题1.B（快速排序平均时间复杂度为O(nlogn)）2.B（链表插入删除只需调整指针，无需移动元素）3.B（完全二叉树叶子节点数为⌈n/2⌉，100/2=50）4.A（动态规划要求子问题重叠且独立）5.B（KMP利用前缀函数（部分匹配表）跳过重复匹配）6.B（Dijkstra用于单源最短路径，要求权值非负）7.B（减少训练数据会加剧过拟合）8.D（二分查找法是查找方法，非冲突处理）9.A（BGD每次用全部数据计算梯度）10.C（归并排序是稳定排序）二、填空题1.O(nlogn)2.队列3.分而治之（将数组分成两半，分别排序后合并）4.[-1,0,0,1,2]（模式串“ABABC”的前缀函数值）5.子问题与原问题6.Floyd-Warshall7.池化（或下采样）8.信息增益比9.已存储元素个数10.饱和（或导数易趋近于0的）三、判断题1.×（快速排序不稳定，交换可能破坏顺序）2.√（二叉搜索树中序遍历是升序序列）3.√（KMP预处理模式串O(m)，匹配O(n)，总O(n+m)）4.×（动态规划要求子问题重叠，分治要求子问题独立）5.√（BFS按层遍历，首次到达目标即为最短路径）6.×（过拟合是模型复杂度过高，过度拟合训练数据）7.√（归并排序需要O(n)辅助空间）8.×（SVM通过核函数可处理非线性问题）9.√（哈希表平均查找O(1)，最坏O(n)）10.×（非凸函数中可能陷入局部最优）四、简答题1.快速排序步骤：选择基准值（如首尾或中间元素），将数组分为小于基准和大于基准的两部分（分区），递归对两部分排序。核心是分区操作（partition）。2.next数组记录模式串前缀与后缀的最长公共长度，用于匹配失败时跳过不必要的比较。计算方法：遍历模式串，对每个位置i，找到最大k使得前k个字符等于后k个字符（k<i），next[i]=k。3.动态规划处理子问题重叠的情况，通过存储子问题解避免重复计算；分治处理子问题独立的情况，子问题无重叠，直接递归求解。4.卷积层通过卷积核（滤波器）提取局部特征（如边缘、纹理），共享权值减少参数，保留空间信息，实现特征的层次化提取。五、讨论题1.过拟合原因：模型复杂度过高（如深度过深的神经网络）、训练数据量少、噪声干扰。缓解方法：增加正则化（L1/L2）、早停法、数据增强、dropout、简化模型结构。2.Dijkstra适用于单源最短路径（非负权图），时间复杂度O(M+NlogN)（堆优化）；Floyd适用于多源最短路径（允许负权但无负环），时间复杂度O(N³)。小图用Floyd，大图单源用Dijkstra。3.归并排序：稳定，时间复杂度稳定O(nlogn)，但需要O(n)额外空间；快速排序：平均O(nlogn)，空间O(logn)（递归栈），但不稳定，最坏O(n²)（已排序数组）。4.SGD（随机梯度下降）每次用单个样本，训练快但波动大；Adam结合动量和自适应学习率，收敛更稳定。数据量大用SGD/小批量SGD，需要稳定收敛用Adam，需调参时可尝试多种方法。---代码实现示例（部分核心算法）1.快速排序```pythondefquick_sort(arr,low,high):iflow<high:pivot_idx=partition(arr,low,high)分区操作quick_sort(arr,low,pivot_idx-1)递归左半部分quick_sort(arr,pivot_idx+1,high)递归右半部分defpartition(arr,low,high):pivot=arr[high]选择最后一个元素为基准i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1测试arr=[3,1,4,1,5,9,2,6]quick_sort(arr,0,len(arr)-1)print(arr)输出：[1,1,2,3,4,5,6,9]```2.KMP算法（next数组计算与匹配）```pythondefcompute_next(pattern):m=len(pattern)next_arr=[-1]mk=-1前缀长度foriinrange(1,m):whilek>-1andpattern[i]!=pattern[k+1]:k=next_arr[k]ifpattern[i]==pattern[k+1]:k+=1next_arr[i]=kreturnnext_arrdefkmp_search(text,pattern,next_arr):n,m=len(text),len(pattern)k=-1已匹配长度foriinrange(n):whilek>-1andtext[i]!=pattern[k+1]:k=next_arr[k]iftext[i]==pattern[k+1]:k+=1ifk==m-1:完全匹配