2026年阿里社招算法测试题及答案

2026年阿里社招算法测试题及答案

一、单项选择题（10题，每题2分）1.以下算法中，平均时间复杂度为O(nlogn)且空间复杂度为O(logn)的是？A.冒泡排序B.归并排序C.快速排序D.计数排序2.动态规划的核心特性不包括以下哪项？A.重叠子问题B.最优子结构C.无后效性D.贪心选择3.以下数据结构中，最适合实现“先进后出”操作的是？A.队列B.栈C.链表D.二叉树4.图的广度优先搜索（BFS）通常使用哪种数据结构实现？A.栈B.队列C.哈希表D.二叉堆5.分布式系统中，Paxos算法的核心是解决什么问题？A.节点通信B.数据一致性C.负载均衡D.容错6.以下排序算法中，属于稳定排序的是？A.快速排序B.堆排序C.归并排序D.选择排序7.哈希表中，当负载因子超过阈值时，通常会采取什么操作？A.扩容B.缩容C.删除旧数据D.增加冲突链长度8.递归算法与迭代算法相比，其主要缺点是？A.可读性差B.时间复杂度高C.可能栈溢出D.空间复杂度低9.以下问题中，适合用贪心算法解决的是？A.最长公共子序列B.0-1背包问题C.分数背包问题D.最短路径（负权边）10.以下算法中，用于解决单源最短路径且允许负权边的是？A.Dijkstra算法B.Bellman-Ford算法C.Floyd-Warshall算法D.拓扑排序二、填空题（10题，每题2分）1.堆排序的时间复杂度是________（最坏、平均）。2.二叉搜索树的中序遍历结果是________序列。3.哈希表的冲突解决方法中，“开放地址法”包括线性探测、二次探测和________。4.分布式系统中的CAP理论指出，一致性、可用性和________三者不可兼得。5.动态规划解决“最长递增子序列”问题的状态转移方程是________（用dp[i]表示前i个元素的最长递增子序列长度）。6.图的两种主要遍历方式是广度优先搜索和________。7.快速排序的平均时间复杂度是________。8.栈的两种基本操作是________和出栈。9.贪心算法的适用条件是问题具有________和贪心选择性质。10.递归算法的终止条件必须满足________，否则会陷入无限递归。三、判断题（10题，每题2分）1.冒泡排序是稳定排序算法。2.动态规划的状态转移方程必须依赖于之前的状态，不能依赖之后的状态。3.哈希表的查找时间复杂度平均为O(1)。4.递归算法的时间复杂度一定比迭代算法高。5.图的深度优先搜索（DFS）一定比广度优先搜索（BFS）快。6.Paxos算法可以保证在异步网络中实现强一致性。7.堆排序是不稳定排序算法。8.0-1背包问题可以用贪心算法得到最优解。9.二叉树的叶子节点数等于度为2的节点数加1。10.排序算法中，归并排序的空间复杂度是O(n)。四、简答题（4题，每题5分）1.请简述动态规划与分治算法的区别及适用场景。2.请说明哈希表的冲突解决方法及各自的优缺点。3.请简述分布式系统中Raft算法的核心思想。4.请说明快速排序的常见优化方法（至少3种）。五、讨论题（4题，每题5分）1.请讨论在海量数据场景下，如何高效实现TopK高频词问题。2.请讨论电商场景中商品推荐排序算法的设计思路（需考虑用户行为、商品热度等因素）。3.请讨论分布式系统中MapReduce的容错机制如何实现。4.请讨论动态规划在路径规划问题中的应用（如最短路径、最长路径）及状态设计思路。答案：一、单项选择题1.C2.D3.B4.B5.B6.C7.A8.C9.C10.B二、填空题1.O(nlogn)2.有序（递增）3.再哈希法（双重哈希）4.分区容错性（PartitionTolerance）5.dp[i]=max(dp[j]+1)，其中j<i且nums[j]<nums[i]6.深度优先搜索（DFS）7.O(nlogn)8.入栈9.最优子结构10.终止条件（或递归出口）三、判断题1.正确2.正确3.正确4.错误5.错误6.错误7.正确8.错误9.正确10.正确四、简答题1.动态规划与分治的区别：分治将问题分解为独立子问题，递归求解后合并；动态规划分解为重叠子问题，用记忆化或迭代存储结果避免重复计算。适用场景：分治适用于子问题独立的问题（如归并排序）；动态规划适用于子问题重叠且有最优子结构的问题（如最长公共子序列）。2.哈希冲突解决方法：①开放地址法（线性/二次探测、再哈希）：优点无额外空间，缺点冲突后查找效率下降；②链地址法：优点冲突处理简单，缺点链表过长时效率低；③再哈希法：用多个哈希函数减少冲突，缺点计算成本高。3.Raft核心思想：①领导者选举：节点分三类，超时无心跳则发起选举；②日志复制：领导者接收请求，复制到多数追随者后提交；③安全性：日志一致性、领导者任期递增，防止数据不一致。4.快速排序优化：①三数取中法：选首、尾、中间数的中位数为pivot；②随机pivot：降低最坏情况概率；③三向切分：分小于、等于、大于pivot三部分，处理重复元素高效；④尾递归优化：迭代代替递归避免栈溢出。五、讨论题1.海量数据TopK高频词：①分治分片：将数据分片，每片用哈希表统计词频；②局部TopK：每片用小根堆（大小K）维护高频词；③全局聚合：合并所有片的局部TopK，再用小根堆筛选最终TopK；若数据极大，结合MapReduce（Map统计词频，Reduce合并TopK）。2.电商推荐排序：①特征工程：提取用户（浏览/购买）、商品（销量/评分）、场景（时间/地域）特征；②排序逻辑：加权融合（用户偏好权重×商品得分+热度权重×全局热度）；③实时优化：在线学习更新权重，结合实时行为调整；④冷启动：新商品用类别热度，新用户用相似聚类推荐。3.MapReduce容错：①任务重试：失败任务重新调度（保证幂等）；②推测执行：慢任务启动备份，先完成有效；③数据本地性：任务调度到数据节点减少网络开销；④节点检测：心跳机制检测存活，故障则重新分配任务；⑤日志记录：恢复任务进度。4.动态规划路径规划：①最短路径（网格）：dp[i][j]为起点到(i,j)的最短距离，转移方程dp[