LC算法基础笔试试题（含详细答案解析）

LC算法基础笔试试题（含详细答案解析）本次试题适用于算法入门、基础刷题自测，题型包含单项选择题、填空题、编程实操题，覆盖数组、链表、哈希表、双指针、贪心等高频基础考点，题目难度贴合LC简单、中等基础题型，总分100分，答题时间90分钟。一、单项选择题（共10题，每题3分，共30分）1.数组nums=[1,2,3,4,5]，采用二分查找算法查找元素4，需要比较的次数为（）A.1B.2C.3D.42.以下数据结构中，查询效率最高的是（）A.单向链表B.有序数组C.哈希表D.栈3.双指针法无法高效解决以下哪个问题（）A.有序数组两数之和B.链表中环的检测C.无序数组最大值查找D.移除数组重复元素4.时间复杂度O(nlogn)的排序算法是（）A.冒泡排序B.快速排序C.选择排序D.插入排序5.二叉树前序遍历的顺序是（）A.左-根-右B.根-左-右C.左-右-根D.右-根-左6.哈希冲突的常见解决方式不包括（）A.链地址法B.开放定址法C.哈希扩容D.顺序遍历法7.栈的核心特性是（）A.先进先出B.先进后出C.随机存取D.有序存储8.给定长度为n的数组，遍历一次数组的时间复杂度为（）A.O(1)B.O(n)C.O(n²)D.O(logn)9.以下哪种场景最适合用贪心算法求解（）A.最短路径动态规划B.零钱兑换（最优解）C.全排列问题D.二叉树遍历10.单向链表相比于数组的核心优势是（）A.随机访问速度快B.插入删除效率高C.占用内存更小D.查找速度更快二、填空题（共5题，每题4分，共20分）1.链表反转的核心思路是__________，依次改变节点的指向。2.二分查找的前提条件是__________。3.队列的核心特性是__________。4.解决数组去重的两种常用方法：哈希表法和__________。5.递归算法的两个核心要素是__________和递归终止条件。三、编程实操题（共3题，共50分）题目1：两数之和（简单，15分）给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1：输入：nums=[2,7,11,15],target=9输出：[0,1]题目2：移除有序数组重复元素（简单，15分）给你一个升序排列的数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。示例1：输入：nums=[1,1,2]输出：2,nums=[1,2,_]题目3：最长无重复子串（中等，20分）给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例1：输入：s="abcabcbb"输出：3解释：因为无重复字符的最长子串是"abc"，所以其长度为3。完整答案及详细解析一、单项选择题答案及解析1.答案：B解析：初始左边界left=0，右边界right=4，中间位mid=2（数值3），3<4，左边界右移；第二次mid=3（数值4），匹配目标值，共比较2次。2.答案：C解析：哈希表基于哈希映射实现，平均查询时间复杂度为O(1)；有序数组查询为O(logn)，链表、栈查询为O(n)。3.答案：C解析：双指针适用于有序结构、链表遍历、区间筛选类问题；无序数组最大值只需单次遍历比对，无需双指针。4.答案：B解析：冒泡、选择、插入排序平均时间复杂度均为O(n²)；快速排序平均时间复杂度为O(nlogn)，是常用高效排序算法。5.答案：B解析：前序遍历：根节点→左子树→右子树；中序：左→根→右；后序：左→右→根。6.答案：D解析：哈希冲突主流解决方式为链地址法、开放定址法，哈希扩容可减少冲突概率，顺序遍历法不属于冲突解决方式。7.答案：B解析：栈是后进先出（先进后出），队列是先进先出。8.答案：B解析：单次遍历数组，执行次数随数据量n线性增长，时间复杂度为O(n)。9.答案：B解析：贪心算法局部最优推导全局最优，零钱兑换基础场景可通过贪心求解；最短路径多用动态规划，全排列为回溯算法。10.答案：B解析：链表无需连续内存，插入、删除节点仅需修改指针，效率远高于数组；数组支持随机访问，链表不支持。二、填空题答案及解析1.迭代遍历节点解析：常规链表反转通过迭代逐个保存后继节点，修改当前节点指针指向前驱节点，完成反转。2.数组有序解析：二分查找依赖有序序列，通过中间值大小对比缩小查找区间，无序数组无法使用。3.先进先出解析：队列尾部入队、头部出队，遵循先进先出规则。4.双指针法解析：有序数组可通过快慢双指针原地去重，无序数组多采用哈希表去重。5.递归递推公式解析：递归必须具备终止条件避免死循环，同时需要递推公式实现层层拆解问题。三、编程题答案及详细解析（Python版）题目1：两数之和解题思路：采用哈希表一次遍历，遍历过程中存储已遍历元素及下标，计算目标值与当前元素的差值，判断差值是否已存在于哈希表中，存在则直接返回下标，时间复杂度O(n)。python

deftwoSum(nums,target):

#建立哈希字典存储数值和下标

hash_dict={}

forindex,numinenumerate(nums):

#计算所需差值

diff=target-num

ifdiffinhash_dict:

#找到匹配值，返回下标

return[hash_dict[diff],index]

#未匹配则存入当前数值和下标

hash_dict[num]=index

return[]代码解析：遍历数组每个元素，通过差值快速匹配已遍历数据，仅需一次遍历即可完成求解，相比双重暴力遍历效率大幅提升，适配大规模数据。题目2：移除有序数组重复元素解题思路：快慢双指针法，慢指针记录唯一元素位置，快指针遍历数组寻找新的不重复元素，找到后慢指针前移并覆盖数值，最终慢指针长度即为新数组长度。python

defremoveDuplicates(nums):

ifnotnums:

return0

#慢指针初始位置

slow=0

#快指针遍历数组

forfastinrange(1,len(nums)):

#找到不重复元素

ifnums[fast]!=nums[slow]:

slow+=1

nums[slow]=nums[fast]

#长度为慢指针下标+1

returnslow+1代码解析：全程原地修改数组，仅使用常数额外空间，满足题目O(1)空间要求，遍历一次数组，时间复杂度O(n)，是有序数组去重最优解法。题目3：最长无重复子串解题思路：滑动窗口+哈希表，用哈希表记录字符最后出现的下标，维护一个无重复字符的窗口，动态调整窗口左边界，实时更新窗口最大长度。python

deflengthOfLongestSubstring(s):

#记录字符最后出现的位置

char_index={}

max_len=0

#窗口左边界

left=0

forright,charinenumerate(s):

#字符重复且在窗口内，更新左边界

ifcharinchar_indexandchar_index[char]>=left:

left=char_index[char]+1

#更新字符最新下标

char_index[char]=right

#计算当前窗口长度并更新最大值

max_len=max(max_len,right-left