Java算法笔试真题（含详细答案解析）

Java算法笔试真题（含详细答案解析）说明：本套试题贴合互联网、软件开发企业真实笔试场景，涵盖基础算法、数组、链表、排序、递归、哈希等核心考点，题型包含选择题、填空题、编程题，适配初级Java开发岗位笔试，答案解析详细易懂，侧重实战思路。一、单项选择题（共5题，每题4分，共20分）1.以下排序算法中，时间复杂度最优且属于稳定排序的是（）A.快速排序B.冒泡排序C.归并排序D.选择排序答案：C解析：-快速排序：平均O(nlogn)，最坏O(n²)，不稳定排序；-冒泡排序：最好最坏均为O(n²)，稳定排序，效率低；-归并排序：最好最坏均为O(nlogn)，稳定排序，时间复杂度最优；-选择排序：O(n²)，不稳定排序。2.已知一个有序数组，查找指定元素，效率最高的算法是（）A.顺序查找B.二分查找C.哈希查找D.遍历查找答案：B解析：二分查找仅适用于有序数组，时间复杂度为O(logn)，远优于顺序遍历的O(n)。哈希查找虽效率高，但依赖哈希表结构，不适用于普通有序数组的原生查找。3.以下关于递归算法的说法，错误的是（）A.递归必须有终止条件B.递归层数过深会出现栈溢出C.递归执行效率一定高于循环D.递归代码简洁，逻辑清晰答案：C解析：递归每次调用都会创建栈帧，存在额外的栈开销和重复计算，多数场景下执行效率低于普通循环，仅部分场景（树、回溯问题）更适合用递归。4.Java中HashMap底层解决哈希冲突的主要方式是（）A.线性探测B.链地址法（数组+链表+红黑树）C.二次探测D.再哈希法答案：B解析：JDK1.8及以上，HashMap采用数组+链表+红黑树结构，通过链地址法解决哈希冲突，链表长度超过8且数组长度大于64时，链表转为红黑树，提升查询效率。5.时间复杂度为O(n)的算法是（）A.二分查找B.单层for循环遍历数组C.双层for循环嵌套D.斐波那契递归答案：B解析：单层循环遍历数据，执行次数与数据量n成正比，复杂度O(n)；二分查找O(logn)，双层循环O(n²)，普通斐波那契递归O(2ⁿ)。二、填空题（共3题，每题6分，共18分）1.二叉树的三种遍历方式分别是________、________、________。答案：前序遍历、中序遍历、后序遍历2.栈的特点是________，队列的特点是________。答案：后进先出（LIFO）、先进先出（FIFO）3.冒泡排序的核心逻辑是________，每一轮排序都会将当前未排序部分的最大值冒泡至末尾。答案：相邻元素两两比较，逆序则交换三、编程算法题（共3题，总分62分）编程题1：数组去重（简单，18分）题目描述：给定一个int类型无序数组，编写Java方法，去除数组中重复元素，返回无重复元素的新数组，保持原有元素相对顺序不变。示例：输入：[2,3,2,5,3,6]输出：[2,3,5,6]解题思路：1.利用HashSet元素不可重复的特性存储数组元素，自动去重；2.结合LinkedHashSet保证元素遍历顺序与原数组一致；3.将集合转为数组返回，完成需求。完整代码：java

importjava.util.LinkedHashSet;

importjava.util.Set;

publicclassArrayDistinct{

publicstaticint[]distinctArray(int[]arr){

//处理空数组

if(arr==null||arr.length==0){

returnnewint[0];

}

//LinkedHashSet保证去重且顺序不变

Set<Integer>set=newLinkedHashSet<>();

for(intnum:arr){

set.add(num);

}

//集合转数组

int[]res=newint[set.size()];

intindex=0;

for(Integernum:set){

res[index++]=num;

}

returnres;

}

//测试方法

publicstaticvoidmain(String[]args){

int[]arr={2,3,2,5,3,6};

int[]result=distinctArray(arr);

for(intnum:result){

System.out.print(num+"");

}

}

}复杂度分析：时间复杂度O(n)，遍历一次数组；空间复杂度O(n)，用于存储去重后的元素。编程题2：两数之和（中等，22分）题目描述：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。假设每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。示例：输入：nums=[1,7,3,5],target=8输出：[0,1]解题思路：1.采用HashMap存储遍历过的元素和对应下标；2.遍历数组，计算目标差值（target-当前元素）；3.若差值存在于Map中，直接返回两个下标；不存在则将当前元素和下标存入Map，继续遍历。该思路避免了双层循环的冗余计算，大幅提升效率。完整代码：java

importjava.util.HashMap;

importjava.util.Map;

publicclassTwoSum{

publicstaticint[]twoSum(int[]nums,inttarget){

Map<Integer,Integer>map=newHashMap<>();

for(inti=0;i<nums.length;i++){

//计算需要匹配的差值

intdiff=target-nums[i];

//差值存在，返回结果

if(map.containsKey(diff)){

returnnewint[]{map.get(diff),i};

}

//存入当前元素和下标

map.put(nums[i],i);

}

//无匹配结果返回空数组

returnnewint[0];

}

publicstaticvoidmain(String[]args){

int[]nums={1,7,3,5};

inttarget=8;

int[]res=twoSum(nums,target);

System.out.println("下标："+res[0]+","+res[1]);

}

}复杂度分析：时间复杂度O(n)，仅遍历一次数组；空间复杂度O(n)，哈希表存储元素。编程题3：反转单链表（中等偏难，22分）题目描述：给定一个单链表的头节点，反转该链表，返回反转后的链表头节点。示例：输入：1->2->3->null输出：3->2->1->null解题思路（迭代法，最优解）：1.定义三个指针：前驱节点pre、当前节点cur、后继节点next；2.遍历链表，每次保存当前节点的下一个节点；3.将当前节点的next指向前驱节点，完成局部反转；4.依次后移pre和cur，直至遍历结束，pre即为新链表头节点。完整代码：java

//定义链表节点

classListNode{

intval;

ListNodenext;

ListNode(intval){

this.val=val;

this.next=null;

}

}

publicclassReverseLinkList{

//反转链表核心方法

publicstaticListNodereverseList(ListNodehead){

ListNodepre=null;//前驱节点

ListNodecur=head;//当前节点

while(cur!=null){

//保存后继节点

ListNodenext=cur.next;

//反转指针

cur.next=pre;

//指针后移

pre=cur;

cur=next;

}

//pre为新链表头节点

returnpre;

}

//遍历打印链表

publicstaticvoidprintList(ListNodehead){

ListNodetemp=head;

while(temp!=null){

System.out.print(temp.val+"");

temp=temp.next;

}

}

publicstaticvoidmain(String[]args){

//构建链表1->2->3

ListNoden1=newListNode(1);

ListNoden2=newListNode(2);

ListNoden3=newListNode(3);

n1.next=n2;

n2.next=n3;

ListNodenewHead=re