2025年杭电acm试题及答案java版

2025年杭电acm试题及答案java版本文借鉴了近年相关经典试题创作而成，力求帮助考生深入理解测试题型，掌握答题技巧，提升应试能力。---2025年杭州电子科技大学ACM试题及答案（Java版）一、选择题（每题2分，共10分）1.以下哪个数据结构最适合用于实现一个需要频繁插入和删除操作的集合？A.数组B.链表C.栈D.堆2.在快速排序中，如果每次都选取当前未排序部分的首元素作为基准，这种策略称为：A.随机化快速排序B.三数取中法C.内省排序D.初始基准选择法3.以下哪个算法的时间复杂度是O(nlogn)？A.冒泡排序B.插入排序C.快速排序D.选择排序4.在图的邻接表表示中，如果图中有n个顶点，m条边，则邻接表需要存储多少个边结点？A.nB.mC.n+mD.2m5.以下哪个是递归算法的典型特征？A.无需全局变量B.可读性较差C.递归调用自身D.适合处理所有问题---二、填空题（每空1分，共10分）1.在二分查找中，每次将查找区间缩小为原来的______。2.堆排序的时间复杂度为______。3.图的深度优先遍历算法通常使用______来实现。4.在Dijkstra算法中，使用______来维护当前未访问顶点的最短路径。5.动态规划的核心思想是______。---三、简答题（每题5分，共20分）1.简述快速排序的基本思想。2.解释什么是图的拓扑排序，并说明其适用条件。3.描述堆排序的堆调整过程。4.什么是贪心算法？举例说明其应用场景。---四、编程题（每题15分，共60分）1.问题描述：给定一个数组，请找出其中不重复的元素，并按升序输出。```java//示例输入：[1,2,2,3,4,4,5]//示例输出：[1,3,5]```2.问题描述：实现一个简单的LRU（最近最少使用）缓存，支持get和put操作。```java//示例输入：//put(1,1)→缓存是{1=1}//put(2,2)→缓存是{1=1,2=2}//get(1)→返回1//put(3,3)→缓存满，删除最久未使用的1，缓存是{2=2,3=3}//get(2)→返回2```3.问题描述：给定一个二叉树，判断其是否是平衡二叉树。平衡二叉树是指任意节点的左右子树高度差不超过1。```java//示例输入：//输入：[3,9,20,null,null,15,7]//输出：true```4.问题描述：实现一个字符串匹配算法，支持KMP（Knuth-Morris-Pratt）算法，并输出匹配结果的位置。```java//示例输入：//text="ABABDABACDABABCABAB"//pattern="ABABCABAB"//示例输出：10```---答案与解析一、选择题答案1.B.链表链表支持O(1)时间复杂度的插入和删除操作，而数组需要O(n)时间。2.D.初始基准选择法这种策略称为初始基准选择法，容易受到极端输入的影响，导致性能下降。3.C.快速排序快速排序和归并排序的时间复杂度均为O(nlogn)，而冒泡排序、插入排序和选择排序的时间复杂度为O(n²)。4.C.n+m在无向图中，每条边在邻接表中表示两次，因此需要n+m个边结点。5.C.递归调用自身递归算法的核心是通过函数调用自身来解决问题，通常用于解决分治问题。---二、填空题答案1.1/2二分查找每次将查找区间缩小为原来的一半。2.O(nlogn)堆排序的时间复杂度为O(nlogn)，包括建堆和调整过程。3.栈深度优先遍历通常使用递归或栈来实现。4.优先队列（最小堆）Dijkstra算法使用优先队列来维护当前未访问顶点的最短路径。5.状态转移方程动态规划通过状态转移方程将问题分解为子问题，并存储子问题的解。---三、简答题答案1.快速排序的基本思想快速排序是一种分治算法，基本思想是：-选择一个基准元素（pivot）。-将数组划分为两个子数组，左边的元素都小于基准，右边的元素都大于基准。-递归地对左右两个子数组进行快速排序。时间复杂度平均为O(nlogn)，最坏为O(n²)。2.图的拓扑排序拓扑排序是对有向无环图（DAG）进行线性排序，使得对于每一条有向边(u,v)，u在v之前。适用条件：-图中不包含环。-通常使用Kahn算法或DFS实现。3.堆排序的堆调整过程堆调整（heapify）是将一个部分有序的数组调整成堆的过程。对于最大堆：-从最后一个非叶子结点开始，向上调整。-比较父结点与子结点的大小，若不满足堆性质则交换。-递归地对子树进行堆调整。4.贪心算法贪心算法在每一步选择当前最优解，希望最终得到全局最优解。适用场景：-贪心选择性质：当前最优解能导致全局最优解。-最优子结构：问题的最优解包含子问题的最优解。例子：最小生成树（Prim和Kruskal算法）。---四、编程题答案1.不重复元素输出```javaimportjava.util.HashSet;importjava.util.Arrays;importjava.util.ArrayList;publicclassUniqueElements{publicstaticvoidmain(String[]args){int[]arr={1,2,2,3,4,4,5};ArrayList<Integer>result=findUnique(arr);System.out.println(result);}publicstaticArrayList<Integer>findUnique(int[]arr){HashSet<Integer>set=newHashSet<>();for(intnum:arr){set.add(num);}ArrayList<Integer>result=newArrayList<>(set);result.sort(Integer::compareTo);returnresult;}}```2.LRU缓存```javaimportjava.util.HashMap;importjava.util.Map;publicclassLRUCache{privateintcapacity;privateMap<Integer,Integer>cache;publicLRUCache(intcapacity){this.capacity=capacity;cache=newHashMap<>();}publicintget(intkey){if(!cache.containsKey(key)){return-1;}intvalue=cache.get(key);cache.remove(key);cache.put(key,value);returnvalue;}publicvoidput(intkey,intvalue){if(cache.containsKey(key)){cache.remove(key);}elseif(cache.size()==capacity){intfirstKey=cache.keySet().iterator().next();cache.remove(firstKey);}cache.put(key,value);}publicstaticvoidmain(String[]args){LRUCachelru=newLRUCache(2);lru.put(1,1);lru.put(2,2);System.out.println(lru.get(1));//1lru.put(3,3);System.out.println(lru.get(2));//-1}}```3.平衡二叉树判断```javaclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicclassSolution{publicbooleanisBalanced(TreeNoderoot){returncheckHeight(root)!=-1;}privateintcheckHeight(TreeNodenode){if(node==null)return0;intleftHeight=checkHeight(node.left);if(leftHeight==-1)return-1;intrightHeight=checkHeight(node.right);if(rightHeight==-1||Math.abs(leftHeight-rightHeight)>1)return-1;returnMath.max(leftHeight,rightHeight)+1;}publicstaticvoidmain(String[]args){TreeNoderoot=newTreeNode(3);root.left=newTreeNode(9);root.right=newTreeNode(20);root.right.left=newTreeNode(15);root.right.right=newTreeNode(7);Solutionsol=newSolution();System.out.println(sol.isBalanced(root));//true}}```4.KMP字符串匹配```javapublicclassKMPAlgorithm{publicstaticvoidmain(String[]args){Stringtext="ABABDABACDABABCABAB";Stringpattern="ABABCABAB";System.out.println(kmpSearch(text,pattern));//10}publicstaticintkmpSearch(Stringtext,Stringpattern){int[]lps=computeLPSArray(pattern);inti=0,j=0;while(i<text.length()){if(text.charAt(i)==pattern.charAt(j)){i++;j++;}if(j==pattern.length()){returni-j;//匹配成功}elseif(i<text.length()&&text.charAt(i)!=pattern.charAt(j)){if(j!=0){j=lps[j-1];}else{i++;}}}return-1;//未匹配成功}publicstaticint[]computeLPSArray(Stringpattern){int[]lps=newint[pattern.length()];intlen=0;inti=1;lps[0]=0;while(i<pattern.length()){if(pattern.charAt(i)==pattern.charAt(len)){len++;lps