2026年58同城算法笔试题及答案

2026年58同城算法笔试题及答案

一、单项选择题（共10题，每题2分）1.以下排序算法平均时间复杂度非\(O(n^2)\)的是？A.冒泡排序B.插入排序C.归并排序D.选择排序2.二叉搜索树的正确描述是？A.左子树节点均大于根节点B.左子树≤根≤右子树C.允许重复键值D.仅能中序遍历3.动态规划的核心是？A.状态转移方程与重叠子问题B.递归调用C.分治策略D.贪心选择4.深度优先搜索（DFS）的典型实现方式是？A.队列B.优先队列C.哈希表D.栈（或递归）5.不属于开放寻址法的哈希冲突解决方法是？A.线性探测B.二次探测C.链地址法D.再哈希法6.\(n\)个顶点的无向完全图边数为？A.\(n\)B.\(n(n+1)/2\)C.\(n(n-1)/2\)D.\(n^2\)7.快速排序最坏时间复杂度是？A.\(O(n^2)\)B.\(O(n\logn)\)C.\(O(n)\)D.\(O(1)\)8.贪心算法适用条件是？A.任意问题B.仅最优子结构C.贪心选择性质+最优子结构D.无约束9.链表相对数组的优势是？A.随机访问快B.插入删除无需移动元素C.空间连续D.存储密度高10.拓扑排序的正确前提是？A.无向图B.任意有向图C.有向无环图（DAG）D.完全图二、填空题（共10题，每题2分）1.堆排序时间复杂度为________。2.二分查找要求数组________。3.栈的操作遵循________原则。4.斐波那契递归实现时间复杂度为________。5.Dijkstra算法不能处理________的图。6.并查集的操作是________和________。7.KMP算法核心是构建________数组。8.归并排序空间复杂度为________。9.递归算法需满足递归基和________。10.二叉树前序遍历顺序是________。三、判断题（共10题，每题2分）1.所有递归算法都可转换为非递归算法。（）2.冒泡排序最好情况时间复杂度是\(O(1)\)。（）3.哈希表理想查找复杂度为\(O(1)\)。（）4.DFS空间复杂度为\(O(n)\)（\(n\)为顶点数）。（）5.动态规划与分治法的区别是子问题是否重叠。（）6.堆是完全二叉树。（）7.快速排序是稳定排序。（）8.无向图邻接矩阵对称。（）9.贪心算法必获全局最优。（）10.链表已知前驱时插入复杂度为\(O(1)\)。（）四、简答题（共4题，每题5分）1.简述动态规划的基本思想，并举例说明。2.分析快速排序的时间复杂度，并说明如何优化其最坏情况。3.对比链表与数组在存储和操作上的主要差异。4.说明深度优先搜索（DFS）与广度优先搜索（BFS）的区别及适用场景。五、讨论题（共4题，每题5分）1.讨论大规模数据处理中排序算法的选择策略。2.分析哈希表在实际应用中的优缺点及优化方向（结合58同城业务场景）。3.探讨动态规划在58同城房源推荐业务中的应用。4.说明算法复杂度分析在工程实践中的重要意义。答案与解析一、单项选择题答案1.C解析：归并排序平均时间复杂度为\(O(n\logn)\)，其余排序（冒泡、插入、选择）平均为\(O(n^2)\)。2.B解析：二叉搜索树满足“左子树≤根≤右子树”，且子树也为二叉搜索树。3.A解析：动态规划通过状态转移方程利用重叠子问题优化，避免重复计算。4.D解析：DFS通过栈（或递归）实现“深度优先”的遍历逻辑。5.C解析：链地址法（拉链法）属于“分离链接法”，非开放寻址法（开放寻址含线性探测、二次探测、再哈希等）。6.C解析：无向完全图中，每对顶点间有1条边，总边数为\(\frac{n(n-1)}{2}\)。7.A解析：快速排序最坏情况（如数据有序，每次划分极不均衡）时间复杂度为\(O(n^2)\)。8.C解析：贪心算法需同时满足贪心选择性质（局部最优→全局最优）和最优子结构（原问题最优解包含子问题最优解）。9.B解析：链表插入/删除仅需修改指针，无需移动元素；数组插入/删除需移动后续元素（时间复杂度\(O(n)\)）。10.C解析：拓扑排序仅适用于有向无环图（DAG），且结果不唯一。二、填空题答案1.\(\boldsymbol{O(n\logn)}\)2.有序3.后进先出（LIFO）4.\(\boldsymbol{O(2^n)}\)（递归实现存在大量重复子问题）5.负权边（Dijkstra基于贪心，无法处理负权环或负权边的“松弛”逻辑）6.查找（find）；合并（union）（并查集核心操作：查找根节点、合并集合）7.next（或部分匹配表）（KMP通过next数组跳过无效匹配，优化字符串匹配效率）8.\(\boldsymbol{O(n)}\)（归并排序需额外数组存储中间结果）9.递归关系（或递归调用）（递归算法需明确“递归基”（终止条件）和“递归关系”（问题分解逻辑））10.根-左-右（前序遍历顺序：先访问根节点，再遍历左子树，最后遍历右子树）三、判断题答案1.√解析：递归可通过栈模拟（显式维护栈结构）消除递归调用。2.×解析：冒泡排序最好情况（数据有序）需比较\(n-1\)次，时间复杂度为\(O(n)\)。3.√解析：理想无冲突时，哈希表查找、插入、删除的时间复杂度均为\(O(1)\)。4.√解析：DFS递归栈的最大深度为顶点数\(n\)，空间复杂度为\(O(n)\)。5.√解析：分治法子问题独立无重叠，动态规划子问题重叠且可复用。6.√解析：堆是完全二叉树（除最后一层外，每层满；最后一层从左到右填充）。7.×解析：快速排序不稳定（如交换相等元素的相对顺序），稳定排序需选归并、基数排序等。8.√解析：无向图中“边\((i,j)\)”与“边\((j,i)\)”等价，邻接矩阵满足对称性。9.×解析：贪心算法仅在“贪心选择性质+最优子结构”下得到全局最优，否则可能局部最优（如背包问题的贪心解非最优）。10.√解析：已知前驱节点时，链表插入仅需修改指针（时间复杂度\(O(1)\)）。四、简答题答案1.动态规划思想：将大问题分解为重叠子问题，通过记忆化（存储子问题解）避免重复计算，利用最优子结构（原问题最优解包含子问题最优解）构建原问题解。举例：斐波那契数列递归\(f(n)=f(n-1)+f(n-2)\)会重复计算\(f(n-2)\)，动态规划从\(f(0)\)、\(f(1)\)开始自底向上计算，时间复杂度从\(O(2^n)\)降为\(O(n)\)。再如背包问题，通过\(dp[i][j]\)（前\(i\)个物品、容量\(j\)的最大价值）的状态转移方程，避免子问题重复计算。2.快速排序复杂度：平均\(O(n\logn)\)，最坏\(O(n^2)\)（如数据有序，每次划分极不均衡）。优化策略：①随机选基准（减少有序数据的影响）；②三数取中（选首、中、尾的中间值，使基准更优）；③小数组用插入排序（子数组长度<10时，插入排序开销更低）；④三路快排（将数组分为“<、=、>基准”三部分，处理重复元素更高效）。3.链表与数组的差异：-存储：数组是连续内存，链表是离散节点+指针连接。-操作：数组随机访问（\(O(1)\)）快，链表需遍历（\(O(n)\)）；数组插入/删除需移动元素（\(O(n)\)），链表已知前驱时\(O(1)\)。-空间：数组固定大小（易溢出/浪费），链表动态分配（灵活但有指针开销）。-场景：数组适合读多写少、规模固定（如成绩统计）；链表适合写多读少、动态增减（如消息队列、LRU缓存）。4.DFS与BFS的区别及场景：-实现：DFS用栈（或递归），优先“深入”路径；BFS用队列，按“层”遍历。-场景：DFS适合连通性、路径存在性（如迷宫找出口）、拓扑排序（逆后序）；BFS适合最短路径（无权图）、层序遍历（如二叉树层次遍历）、最少操作步数（如棋盘问题）。五、讨论题答案1.大规模数据排序策略：-超内存场景：用外部归并排序（分块→内存内排序→多路归并，减少I/O）。-内存充足：选优化的快速排序（随机基准、三数取中），平均快；稳定性要求高选归并/基数排序；数据近有序选插入排序。-分布式场景（如Hadoop）：用MapReduce排序（分片→排序→合并）。-特殊数据（如字符串）：用基数排序更高效。58同城房源排序：超内存用外部归并，内存充足用优化的快速排序，提升查询效率。2.哈希表的优缺点与优化：-优点：查找/插入/删除理想\(O(1)\)，灵活；缺点：冲突（需解决）、空间开销（指针）、哈希函数设计难。-优化：①高效哈希函数（如一致性哈希，适应58分布式部署）；②冲突解决优化（链地址法+红黑树，链表长时转树）；③动态扩容（负载因子0.75时扩容，减少冲突）；④内存优化（布隆过滤器结合，减少存储）。58用户ID哈希表：动态扩容+链地址转树，提升用户信息查询效率。3.动态规划在房源推荐的应用：-多阶段决策：用户浏览历史→阶段1（区域偏好）、阶段2（价格区间）、阶段3（房型），状态为当前选择的特征，转移时计算“匹配度”（如用户点击的房源特征组合）。-资源分配：带看路线规划（将时间/距离作为资源，动态规划找“最优带看顺序”，状态为已用时间和已看房源）。最终通过动态规划优化推荐策略，提升用户转化率和带看效率。4.算法复杂度分析的意义：-指导算法选择：\(n