数据结构面试题整理

article/2025/10/16 0:45:34

一数据结构

1.你熟悉什么数据结构？
数组链表
栈队列哈希
二叉树二叉查找树二叉堆
b树 b+树

2.b树 b+树 b*树
b和b+都是节点可以有很多子节点，区别是b树所有的节点都可以存储关键字，而b+树只有叶子节点存储关键字，适用于数据库索引。

3.树的中序遍历

在这里插入图片描述

4.二叉平衡树，怎么用一维数组存储
在这里插入图片描述
使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或者右孩子空缺，则数据的相应位置也空出来。

设计思路：

假设一个父节点的下标是p
左孩子下标=2p +1
右孩子下标=2p+2

反过来，左孩子的下标是l,它父节点下标为：(l - 1)/2

二算法

1.快排？快排的实现过程？复杂度如何？简单代码实现？
方式:
双边循环法（代码实现复杂）
单边循环法（推荐）

复杂度：
nlogn

单边循环法实现过程
1-先找到一个基准元素，起始下标
2-遍历，如果元素比基准元素小，下标+1
此元素与下标对应元素交换位置
3-当遍历完后，基准元素与当前下标元素交换位置，此时基准元素就分成了两组数据
4-两边的数据在递归调用，分而治之，直到起始下标和终止下标结束，则不能在拆分
5-遍历数组元素即可

单边循环法代码实现：

public static void quickSort(int[] arr, int startIndex, int endIndex) 
{ 
// 递归结束条件：startIndex大于或等于endIndex时 if (startIndex >= endIndex) { return;} // 得到基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 根据基准元素，分成两部分进行递归排序quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); 
} /** * 分治（单边循环法） * @param arr 待交换的数组 * @param startIndex 起始下标* @param endIndex 结束下标 */ 
private static int partition(int[] arr, int startIndex, int endIndex) { // 取第1个位置（也可以选择随机位置）的元素作为基准元素int pivot = arr[startIndex]; int mark = startIndex; for(int i=startIndex+1; i<=endIndex; i++){ if(arr[i]<pivot){ mark ++;int p = arr[mark]; arr[mark] = arr[i];arr[i] = p; }
}arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark; } public static void main(String[] args) { int[] arr = new int[] {4,4,6,5,3,2,8,1}; quickSort(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); }

说明：
递归代码的书写特点，先找到一个循环的代码，在找出跳出循环的条件，递归的调用循环代码。

2.二分查找原理，简单的一个代码
算法思想：
设置开始位置start，结束位置end，以及中间位置 mid=(end+start)/2,
如果arr[index]=mid，返回mid
如果arr[index]>mid,从后半段查找，将start设置为mid+1
如果arr[index]<mid,从后半段查找，将end设置为mid-1
如果start>end,返回-1，说明所查元素不存在

代码：

public class Select1_SuanFa2 {public static void main(String[] args) {		System.out.println(select(44));	}	public static int select(int target) {		//定义数组		int[] arr = {21,32,36,44,45,36,47,38,29};		//定义初始位置		int start = 0;		//定义结束位置		int end = arr.length-1;		//定义中间位置		int mid = (start+end)/2;	while(true) {			//如果没有这个元素，则start>=end,返回-1			if(start>end) {		 	return -1;			}			//判断是否和中间位置元素值相等			if(arr[mid] == target) {				//将中间位置的索引赋值给目标位置				return mid;			}else {				if(arr[mid] > target) {					//将end位置设置为中间位置减一					end = mid-1;				}else {					//将start位置设置为中间位置加1					start = mid+1;				}				//取出新的中间位置（别忘记了）				mid = (start+end)/2;			}		}					}    }

3.怎么判断链表是否有环？
在这里插入图片描述

思路：
两个指针分别按照固定步长行走，P1一次走1布，P2一次走2布，如果链表有环，P1和P2会有相遇的时刻。（追击问题解法）

代码：

/** * 判断是否有环 * @param head 链表头节点 
*/ public static boolean isCycle(Node head) { 
Node p1 = head; Node p2 = head; 
while (p2!=null && p2.next!=null){ ;p1 = p1.next; p2 = p2.next.next; if(p1 == p2){ return true; 
} 
return false; } /** * 链表节点 */ 
private static class Node { 
int data; 
Node next;
Node(int data) { this.data = data; 
} 
} public static void main(String[] args) throws Exception { 
Node node1 = new Node(5); Node node2 = new Node(3); Node node3 = new Node(7); Node node4 = new Node(2); Node node5 = new Node(6); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node2; System.out.println(isCycle(node1)); }

4.链表的定义，怎么实现链表翻转？
链表翻转代码参考： https://blog.csdn.net/xu491361421xiao/article/details/81385435

5.怎么求数组的最大子序列和

6.栈中最小值
在这里插入图片描述

代码如下：

private Stack<Integer> mainStack = new Stack<Integer>(); 
private Stack<Integer> minStack = new Stack<Integer>(); /** * 入栈操作 * @param element 入栈的元素 */ 
public void push(int element) { mainStack.push(element); //如果辅助栈为空，或者新元素小于或等于辅助栈栈顶，则将新元素压入辅助栈 if (minStack.empty() || element <= minStack.peek()) { minStack.push(element); } } /** * 出栈操作 */ public Integer pop() { //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 
if (mainStack.peek().equals(minStack.peek())) { 
minStack.pop(); 
}return mainStack.pop(); } /** * 获取栈的最小元素 */ public int getMin() throws Exception { if (mainStack.empty()) { throw new Exception("stack is empty"); } return minStack.peek(); } public static void main(String[] args) throws Exception { MinStack stack = new MinStack(); stack.push(4); stack.push(9); stack.push(7); stack.push(3); stack.push(8); stack.push(5); System.out.println(stack.getMin()); 
stack.pop(); stack.pop(); 
stack.pop(); 
System.out.println(stack.getMin()); }