ACM初赛必做试题及参考答案

ACM初赛必做试题及参考答案考试时间：______分钟总分：______分姓名：______选择题（共10题，每题2分，满分20分）1.下列数据结构中，插入和删除操作时间复杂度均为O(1)的是（）。A.顺序栈B.顺序表C.单链表D.二叉排序树2.快速排序的平均时间复杂度是（）。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)3.下列哪种遍历方式会先访问根节点，然后左子树，最后右子树？（）A.前序遍历B.中序遍历C.后序遍历D.层序遍历4.在C++中，以下关于指针和引用的说法正确的是（）。A.引用必须初始化B.指针可以不初始化C.引用可以指向不同对象D.指针不能为空5.下列算法中，不属于贪心算法的是（）。A.Dijkstra算法B.Kruskal算法C.快速排序D.动态规划6.二叉树的深度为h，则最多有（）个节点。A.2^hB.2^h-1C.h^2D.h7.下列哪种排序算法是稳定的？（）A.快速排序B.堆排序C.归并排序D.选择排序8.在Java中，String类的特性是（）。A.可变的B.不可变的C.继承自ObjectD.实现了Comparable9.下列数据结构中，适合实现LRU缓存的是（）。A.数组B.链表C.哈希表D.哈希表+双向链表10.递归函数的终止条件通常是为了避免（）。A.时间复杂度增加B.栈溢出C.内存泄漏D.死循环填空题（共5题，每题4分，满分20分）1.已知数组arr=[3,1,4,1,5,9,2,6]，执行快速排序（以第一个元素为基准）的第一趟划分后，数组变为______，基准元素最终位置为______。2.动态规划的空间复杂度可以通过______优化到O(1)。3.以下代码的输出结果是______：```pythondeffunc(n):ifn==0:return1returnn*func(n-1)print(func(3))```4.在二叉树中，度为2的节点数为5，度为1的节点数为3，则叶子节点数为______。5.哈希表处理冲突的方法有开放地址法和______。程序阅读题（共2题，每题10分，满分20分）1.阅读以下C++代码，写出程序输出结果。```cpp#include<iostream>usingnamespacestd;intfunc(inta,intb){if(b==0)returna;returnfunc(b,a%b);}intmain(){cout<<func(48,18)<<endl;return0;}```2.阅读以下Python代码，写出程序输出结果。```pythondefsum_list(lst):ifnotlst:return0returnlst[0]+sum_list(lst[1:])print(sum_list([1,2,3,4]))```算法设计题（共3题，满分40分）1.二分查找：给定一个有序整数数组nums和一个目标值target，编写一个函数查找target在数组中的位置，若存在则返回索引，否则返回-1。要求时间复杂度O(logn)。2.括号匹配：给定一个只包含'('、')'、'{'、'}'、'['、']'的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且必须正确嵌套。3.背包问题：给定一个整数数组weights表示物品重量，数组values表示物品价值，以及一个整数capacity表示背包容量。编写一个函数返回背包能获得的最大价值，每个物品只能选一次（0-1背包问题）。试卷答案选择题（共10题，每题2分，满分20分）1.A解析：顺序栈的插入（入栈）和删除（出栈）均在栈顶操作，时间复杂度均为O(1)。顺序表插入/删除需移动元素，最坏O(n)；单链表插入/删除需定位节点，定位O(n)；二叉排序树插入/删除最坏O(n)。2.B解析：快速排序平均时间复杂度为O(nlogn)，最坏O(n²)（如数组已有序）。3.A解析：前序遍历顺序为根→左→右；中序为左→根→右；后序为左→右→根；层序按层遍历。4.A解析：C++引用必须初始化且不可指向不同对象；指针可初始化为空；引用本质是指针常量，但语法上更安全。5.D解析：Dijkstra（贪心求最短路径）、Kruskal（贪心求最小生成树）、快速排序（分治+贪心）均属贪心；动态规划是分治优化，非贪心。6.B解析：深度为h的二叉树最多节点数为2^h-1（满二叉树）。7.C解析：归并排序稳定（相等元素顺序不变）；快速排序、堆排序、选择排序不稳定。8.B解析：Java中String对象不可变（final修饰），每次修改创建新对象；C和D正确但非唯一特性。9.D解析：哈希表+双向链表（LRU缓存实现，哈希表存键值对，链表按访问顺序维护）。10.B解析：递归无终止条件会导致无限递归，栈溢出（递归深度过大）。填空题（共5题，每题4分，满分20分）1.[1,1,2,3,5,9,4,6]；2解析：快速排序第一趟划分（Lomuto分区），基准3最终位于下标2（从0开始）。2.滚动数组解析：动态规划仅依赖前几状态时，用数组覆盖旧状态，空间复杂度降至O(1)。3.6解析：func(3)=3×func(2)=3×2×func(1)=3×2×1×func(0)=3×2×1×1=6。4.8解析：二叉树节点数=叶子节点+度1节点+度2节点；设叶子节点为n0，则n0=n2+1（n2=5）→n0=6，总节点=5+3+6=14，但公式应为n0=n2+1→5+1=6，总节点=5+3+6=14？修正：标准公式n0=n2+1，故n0=5+1=6，但题目说度1节点3，总节点=6+3+5=14，叶子节点应为6？重新推导：总节点数N=n0+n1+n2；边数N-1=n1+2n2；代入得n0=n2+1=6。正确。5.链地址法（或拉链法）解析：哈希表冲突处理方法：开放地址法（线性探测）、链地址法（拉链法）、再哈希法等。程序阅读题（共2题，每题10分，满分20分）1.6解析：欧几里得算法求最大公约数，func(48,18)=func(18,48%18=12)=func(12,18%12=6)=func(6,12%6=0)=6。2.10解析：递归求和，sum_list([1,2,3,4])=1+sum_list([2,3,4])=1+2+sum_list([3,4])=1+2+3+sum_list([4])=1+2+3+4+sum_list([])=10。算法设计题（共3题，满分40分）1.二分查找```pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1```解析：初始化左右指针，循环计算中点，比较中点值与目标值，调整左右边界，找到返回索引，否则返回-1。2.括号匹配```pythondefis_valid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack```解析：用栈存储左括号，遇到右括号时弹出栈顶匹配，若栈空或匹配失败则无效；最终栈空则有效。3.0-1背包问题```pythondefknapsack(weights,values,capacity):n=len(weights)dp=[[0]*(capacity+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,capacity+1):ifweights[i-1]<=w:dp[i][w]=m