2025年初级算法考试试题及答案

2025年初级算法考试试题及答案一、单项选择题（每题2分，共20分）1.对于长度为n的无序数组，使用选择排序进行升序排列时，元素交换操作的次数最多为（）。A.n-1B.nC.n²/2D.nlogn2.以下哪种算法的时间复杂度与输入数据的初始顺序无关？（）A.快速排序B.插入排序C.冒泡排序D.归并排序3.若二叉树的前序遍历序列为ABCDE，中序遍历序列为BADCE，则后序遍历序列为（）。A.BDECAB.BEDACC.BDAECD.BEDCA4.对长度为10的有序数组进行二分查找，最坏情况下需要比较的次数为（）。A.3B.4C.5D.65.以下关于哈希表的描述中，错误的是（）。A.哈希冲突是指不同关键字映射到同一哈希地址的现象B.链地址法处理冲突时，哈希表的装载因子可以大于1C.开放定址法处理冲突时，删除操作需要标记“已删除”而不是直接清空D.哈希函数的设计目标是使关键字均匀分布，减少冲突6.若用邻接表存储一个有向图，图中共有n个顶点和m条边，则该邻接表的空间复杂度为（）。A.O(n)B.O(m)C.O(n+m)D.O(n×m)7.执行以下递归函数f(5)的输出结果是（）。deff(n):ifn<=1:return1returnf(n-1)+f(n-2)A.5B.8C.13D.218.对序列[3,1,4,1,5,9,2,6]进行基数排序（按个位优先），第一趟排序后的序列为（）。A.[1,1,2,3,4,5,6,9]B.[3,1,4,1,5,9,2,6]（无变化）C.[1,3,1,4,5,9,2,6]D.[9,5,4,3,6,2,1,1]9.以下动态规划问题中，状态转移方程正确的是（）。A.斐波那契数列：dp[n]=dp[n-1]×dp[n-2]B.最长递增子序列：dp[i]=max(dp[j]+1)（j<i且nums[j]<nums[i]）C.0-1背包问题：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])（j<w[i]时）D.编辑距离：dp[i][j]=min(dp[i-1][j],dp[i][j-1])（当word1[i]≠word2[j]时）10.若某算法的时间复杂度为O(2ⁿ)，则以下哪种n的取值会导致算法无法在合理时间内完成？（）A.n=20B.n=30C.n=40D.n=50二、填空题（每题3分，共30分）11.对数组[7,2,5,8,3,1]进行升序冒泡排序，第三趟（每趟从左到右比较）结束后，数组的状态为________。12.若完全二叉树的第6层（根为第1层）有8个叶子节点，则该树的总节点数最少为________。13.已知一个有序数组为[2,5,7,10,14,17,20]，使用二分查找法查找元素14时，需要比较的元素依次是________。14.执行KMP算法时，模式串“ABABC”的部分匹配值（前缀函数）数组为________。15.用栈实现队列时，若入队操作均在栈A中完成，出队操作需要将栈A的元素全部弹出并压入栈B，则最坏情况下，n次连续出队操作的时间复杂度为________。16.对于带权无向图，若边的权值均为正数，使用Dijkstra算法求单源最短路径时，优先队列（最小堆）中保存的是________。17.计算字符串“algorithm”和“altruism”的最长公共子序列（LCS）长度为________。18.若用堆结构维护一个动态集合，支持插入和删除最大值操作，则该堆应是________（大顶堆/小顶堆）。19.对n个元素进行归并排序时，递归调用的深度（递归层数）为________（假设n是2的幂）。20.若哈希函数为H(key)=keymod7，采用线性探测法处理冲突，将序列[15,23,31,9,18]依次插入哈希表后，元素18的存储地址为________。三、编程题（共50分）21.（10分）编写一个Python函数，输入一个整数列表nums（可能包含重复元素），输出所有不重复的三元组[a,b,c]，使得a+b+c=0，且a≤b≤c。22.（15分）给定一个单链表的头节点head，编写Python代码实现链表的反转（要求迭代和递归两种方法）。23.（15分）设计一个算法，计算两个正整数的最大公约数（GCD），要求同时支持递归（欧几里得算法）和迭代实现，并分析两种方法的时间复杂度。24.（10分）输入一个字符串s（仅包含小写字母），输出s中最长的回文子串。要求时间复杂度不超过O(n²)。参考答案一、单项选择题1.A（选择排序每趟选最小元素交换，最多n-1次交换）2.D（归并排序时间复杂度始终为O(nlogn)）3.D（前序确定根A，中序分左右子树BAD和CE；递归推导后序为BEDCA）4.B（二分查找最坏次数为⌈log₂(n+1)⌉，n=10时为4）5.C（开放定址法删除需标记，但直接清空会破坏后续查找路径）6.C（邻接表存储n个顶点表和m条边表，总空间O(n+m)）7.B（f(5)=f(4)+f(3)=3+5=8）8.A（基数排序个位优先，按个位排序后序列为1(1),1(1),2(2),3(3),4(4),5(5),6(6),9(9)）9.B（A应为加法，C中j≥w[i]时才取max，D需考虑替换操作）10.C（2⁴⁰≈1万亿次，远超合理时间）二、填空题11.[2,3,1,5,7,8]（第一趟后[2,5,3,1,7,8]，第二趟后[2,3,1,5,7,8]，第三趟后[2,3,1,5,7,8]？需重新计算：原始数组[7,2,5,8,3,1]。第一趟比较5次，交换后[2,5,7,3,1,8]（最后是8）；第二趟比较4次，交换后[2,5,3,1,7,8]；第三趟比较3次，交换后[2,3,1,5,7,8]。答案应为[2,3,1,5,7,8]）12.39（完全二叉树前5层满时有2⁵-1=31个节点，第6层最少8个叶子，总节点31+8=39）13.10,17,14（中间元素10，14>10，查右半；中间元素17，14<17，查左半；找到14）14.[0,0,1,2,0]（“A”→0；“AB”→0；“ABA”前缀A和后缀A→1；“ABAB”前缀AB和后缀AB→2；“ABABC”无公共前后缀→0）15.O(n)（均摊分析，每个元素最多入栈和出栈各一次，总时间O(n)）16.待处理节点的当前最短距离（优先队列按距离排序，每次取最小距离节点）17.4（公共子序列如“a”,“l”,“o”,“i”或“a”,“l”,“r”,“i”）18.大顶堆（堆顶为最大值，删除时取堆顶）19.log₂n（每次分半，递归深度为log₂n）20.4（H(15)=15%7=1；H(23)=23%7=2；H(31)=31%7=3；H(9)=9%7=2（冲突，探测3→3已占，探测4→存储4；H(18)=18%7=4（冲突，探测5→存储5？需重新计算：15→1；23→2；31→3；9→2（冲突，线性探测下一个地址3，3被31占，再下一个4，存储4；18→18%7=4（地址4被9占，探测5，存储5）。答案应为5？原计算错误，正确步骤：哈希表地址0-6。插入15→1；23→2；31→3；9→9%7=2（冲突），探测地址3（被31占），探测地址4（空），存入4；18→18%7=4（冲突），探测地址5（空），存入5。故答案为5）三、编程题21.参考代码：```pythondefthree_sum(nums):nums.sort()res=[]n=len(nums)foriinrange(n):ifnums[i]>0:break已排序，正数之和无法为0ifi>0andnums[i]==nums[i-1]:continue去重left,right=i+1,n-1whileleft<right:s=nums[i]+nums[left]+nums[right]ifs==0:res.append([nums[i],nums[left],nums[right]])跳过重复的left和rightwhileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifs<0:left+=1else:right-=1returnres```22.迭代法与递归法：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next迭代法defreverse_list_iter(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev递归法defreverse_list_recur(head):ifnotheadornothead.next:returnheadnew_head=reverse_list_recur(head.next)head.next.next=headhead.next=Nonereturnnew_head```23.最大公约数实现：```python递归（欧几里得算法）defgcd_recur(a,b):ifb==0:returnareturngcd_recur(b,a%b)迭代法defgcd_iter(a,b):whileb!=0:a,b=b,a%breturna时间复杂度分析：两种方法均基于模运算，时间复杂度为O(logmin(a,b))，与欧几里得算法的步骤数相关。```24.最长回文子串（中心扩展法）：```pythondeflongest_palindrome(s):ifnots:return""n=len(s)start,end=0,0defexpand(l,r):whilel>=0andr<nands[l]==s[r]:l-=1r+=1returnrl-1实际长度为(r-1)-(l+1)+1=r-l-1