程序考试题及答案

程序考试题及答案一、选择题（每题2分，共20分）1.快速排序在最坏情况下的时间复杂度是（）A.O(nlogn)B.O(n²)C.O(n)D.O(n³)2.以下数据结构中，适合用作函数调用时参数传递的是（）A.队列B.栈C.二叉树D.哈希表3.以下Java代码的输出结果是（）```javapublicclassTest{publicstaticvoidmain(String[]args){int[]arr={1,2,3};modify(arr);System.out.println(arr[0]);}publicstaticvoidmodify(int[]arr){arr[0]=10;arr=newint[]{4,5,6};}}```A.1B.10C.4D.编译错误4.二分查找算法要求被查找的数组（）A.无序B.递增有序C.递减有序D.递增或递减有序均可5.已知二叉树的前序遍历序列为ABDCE，中序遍历序列为BADCE，则后序遍历序列为（）A.BDECAB.BDAECC.BDACED.BEDCA6.广度优先搜索（BFS）通常使用的辅助数据结构是（）A.栈B.队列C.优先队列D.哈希表7.动态规划算法的核心是（）A.分治思想B.贪心选择C.重叠子问题与最优子结构D.回溯搜索8.以下关于Java垃圾回收的描述，错误的是（）A.垃圾回收由JVM自动管理B.程序员可以通过System.gc()建议回收，但无法强制C.被回收的对象一定是不可达的D.垃圾回收会释放栈内存中的对象9.以下属于面向对象三大特性的是（）A.封装、继承、多态B.抽象、接口、重载C.单例、工厂、代理D.递归、迭代、循环10.KMP算法的核心是利用（）避免重复匹配A.哈希表B.部分匹配表（前缀函数）C.后缀数组D.平衡树二、填空题（每题3分，共15分）1.快速排序的分区函数中，通常选择一个基准值pivot，将数组分为两部分。请补全以下代码：```javaintpartition(int[]nums,intleft,intright){intpivot=nums[right];inti=left1;for(intj=left;j<right;j++){if(nums[j]<=pivot){i++;swap(nums,i,j);}}swap(nums,i+1,right);return______;}```2.二叉树中序遍历的非递归实现需要使用栈。请补全以下代码：```javaList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();Deque<TreeNode>stack=newLinkedList<>();TreeNodecurr=root;while(curr!=null||!stack.isEmpty()){while(curr!=null){stack.push(curr);curr=curr.left;}curr=stack.pop();res.add(curr.val);curr=______;}returnres;}```3.0-1背包问题中，若背包容量为C，物品重量为w[i]，价值为v[i]，则动态规划的状态转移方程为：dp[i][j]=max(______,dp[i-1][jw[i]]+v[i])（当j>=w[i]时）4.图的邻接表存储结构中，通常使用链表或数组保存每个顶点的邻接顶点。假设顶点类型为int，邻接表的Java定义可以是：```javaList<List<Integer>>adj=newArrayList<>();for(inti=0;i<n;i++){adj.add(______);}```5.归并排序的合并过程中，两个有序子数组nums[left...mid]和nums[mid+1...right]需要合并为一个有序数组。请补全以下代码：```javavoidmerge(int[]nums,intleft,intmid,intright){int[]temp=newint[rightleft+1];inti=left,j=mid+1,k=0;while(i<=mid&&j<=right){temp[k++]=nums[i]<=nums[j]?nums[i++]:nums[j++];}while(i<=mid)temp[k++]=nums[i++];while(j<=right)temp[k++]=nums[j++];System.arraycopy(temp,0,nums,left,______);}```三、编程题（共65分）1.（10分）给定一个整数数组nums和一个整数k，判断是否存在两个不同的索引i和j，使得nums[i]=nums[j]且|ij|≤k。示例：输入：nums=[1,2,3,1],k=3→输出：true输入：nums=[1,0,1,1],k=1→输出：true输入：nums=[1,2,3,1,2,3],k=2→输出：false2.（15分）实现字符串的最长回文子串。给定一个字符串s，找到s中最长的回文子串。示例：输入：s="babad"→输出："bab"（或"aba"）输入：s="cbbd"→输出："bb"3.（15分）给定一个二叉树，判断其是否是高度平衡的二叉树。平衡二叉树的定义是：任意节点的左右子树的高度差的绝对值不超过1，且左右子树也是平衡二叉树。示例：输入：root=[3,9,20,null,null,15,7]→输出：true输入：root=[1,2,2,3,3,null,null,4,4]→输出：false4.（15分）实现Dijkstra算法，计算有向图中从起点到所有其他顶点的最短路径。图的邻接表表示为：List<List<int[]>>graph，其中graph.get(u)包含若干int数组{v,w}，表示从u到v有一条权重为w的边。示例：输入：graph=[[{1,4},{2,1}],[{3,1}],[{1,2},{3,5}],[]],start=0输出：最短路径数组dist=[0,3,1,4]（dist[i]表示起点到i的最短距离）5.（10分）设计一个LRU（最近最少使用）缓存，支持以下操作：get(key)：获取关键字对应的值，若不存在返回-1，且访问后该关键字变为最近使用。put(key,value)：插入或更新关键字的值。若缓存容量已满，删除最久未使用的关键字。要求：get和put操作的时间复杂度均为O(1)。答案一、选择题1.B2.B3.B4.B5.A6.B7.C8.D9.A10.B二、填空题1.i+12.curr.right3.dp[i-1][j]4.newArrayList<>()5.temp.length三、编程题1.解法（滑动窗口+哈希表）：维护一个哈希表记录最近一次出现的元素索引。遍历数组，若当前元素已在哈希表中且索引差≤k，返回true；否则更新哈希表。若窗口大小超过k，移除最左边的元素。```javapublicbooleancontainsNearbyDuplicate(int[]nums,intk){Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){if(map.containsKey(nums[i])&&imap.get(nums[i])<=k){returntrue;}map.put(nums[i],i);}returnfalse;}```2.解法（中心扩展法）：遍历每个字符作为中心（奇数长度）或两个字符之间（偶数长度），向两边扩展，记录最长回文子串的起始和结束位置。```javapublicStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";intstart=0,end=0;for(inti=0;i<s.length();i++){intlen1=expandAroundCenter(s,i,i);//奇数长度intlen2=expandAroundCenter(s,i,i+1);//偶数长度intlen=Math.max(len1,len2);if(len>endstart){start=i(len1)/2;end=i+len/2;}}returns.substring(start,end+1);}privateintexpandAroundCenter(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnrightleft1;//实际长度为(right-left-1)}```3.解法（后序遍历+高度计算）：递归计算左右子树高度，若高度差超过1或子树不平衡，返回-1（表示不平衡），否则返回当前子树高度。```javapublicbooleanisBalanced(TreeNoderoot){returnheight(root)!=-1;}privateintheight(TreeNodenode){if(node==null)return0;intleftHeight=height(node.left);if(leftHeight==-1)return-1;intrightHeight=height(node.right);if(rightHeight==-1)return-1;if(Math.abs(leftHeightrightHeight)>1)return-1;returnMath.max(leftHeight,rightHeight)+1;}```4.解法（优先队列优化Dijkstra）：使用优先队列（最小堆）存储待处理的节点及当前最短距离，每次取出距离最小的节点，更新其邻接节点的距离。```javapublicint[]dijkstra(List<List<int[]>>graph,intstart){intn=graph.size();int[]dist=newint[n];Arrays.fill(dist,Integer.MAX_VALUE);dist[start]=0;PriorityQueue<int[]>pq=newPriorityQueue<>(CparingInt(a->a[1]));pq.offer(newint[]{start,0});while(!pq.isEmpty()){int[]curr=pq.poll();intu=curr[0],d=curr[1];if(d>dist[u])continue;//已找到更短路径，跳过for(int[]edge:graph.get(u)){intv=edge[0],w=edge[1];if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;pq.offer(newint[]{v,dist[v]});}}}returndist;}```5.解法（双向链表+哈希表）：使用哈希表快速查找节点，双向链表维护访问顺序（头部为最近使用，尾部为最久未使用）。```javaclassLRUCache{classNode{intkey,val;Nodeprev,next;Node(intk,intv){key=k;val=v;}}privateMap<Integer,Node>map;privateNodehead,tail;privateintcapacity;publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){if(!map.containsKey(key))return-1;Nodenode=map.get(key);moveToHead(node);//标记为最近使用returnnode.val;}publicvoidput(intkey,intvalue){if(map.containsKey(key)){Nodenode=map.get(k