2025年算法面试题库及答案

2025年算法面试题库及答案

一、选择题

1.题目：在快速排序算法中，最好情况下的时间复杂度是多少？

-A,0(n'2)

-B.O(nlogn)

-C.O(n)

-D.O(logn)

2.题目：下列哪种数据结构是先进先出(FIFO)的？

-A.栈(Stack)

-B.队列(Queue)

-C.链表(LinkedList)

-D.树(Tree)

3.题目：在二叉搜索树中，新插入的节点总是被插入到哪个位置？

-A.根节点

-B.叶节点

-C.任意位置

-D.最右侧的叶节点

4.题目：下列哪种排序算法在最坏情况下具有线性时间复杂度？

-A.快速排序(Quicksort)

-B.归并排序(MergeSort)

-C.堆排序(HeapSort)

-D.插入排序(InsertionSort)

5.题目：在图论中，表示从一个顶点到另一个顶点存在一条边的术语是什么？

-A.路径(Path)

-B.连接(Connection)

-C.边(Edge)

-D.节点(Node)

二、填空题

1.题目：快速排序算法的平均时间复杂度是____o

2.题目：二叉树的深度是指从根节点到最远叶节点的路径长度，其时间复杂度是

3.题目：在Dijkstra算法中，用于存储每个顶点到源点的最短路径的数组称为

4.题目：冒泡排序的平均时间复杂度是o

5.题目：在哈希表中，解决冲突的两种主要方法是和—

三、简答题

1.题目：简述快速排序和归并排序的区别。

2.题目：解释什么是二叉搜索树，并描述其性质。

3.题目：描述Dijkstra算法的基本思想和步骤。

4.题目：解释什么是递归，并给出一个递归函数的例子。

5.题目：描述哈希表的工作原理，并解释哈希函数的作用。

四、编程题

1.题目：实现一个快速排序算法，并对一个无序数组进行排序。

2.题目：实现一个二叉搜索树的插入和查找功能。

3.题目：实现Dijkstra算法，找出从一个顶点到所有其池顶点的最短路径。

4.题目：实现一个哈希表，支持插入和查找操作，并处理冲突。

5.题目：给定一个字符串，判断它是否是回文串。

五、综合题

1.题目：设计一个算法,找出无向图中所有连通分量。

2.题目：设计一个算法,找出数组中的最长递增子序列。

3.题目：设计一个算法,实现LRU（最近最少使用）缓存。

4.题目：设计一个算法,判断一个图是否是二分图。

5.题设计一个算法,实现一义树的层序遍历.

答案与解析

一、选择题

1.答案：B

-解析：快速排序在最好情况卜.（每次分区都均匀）的时间复杂度是O（nlogn）。

2.答案：B

-解析：队列（Queue）是先进先出（FIFO）的数据结构。

3.答案：B

一解析：在二叉搜索料中，新插入的节点总是被插入到叶节点.

4.答案：D

-解析：插入排序在最坏情况卜.具有线性时间复杂度O(n)。

5.答案：C

-解析：在图论中，表示从一个顶点到另一个顶点存在一条边的术语是边

(Edge)o

二、填空题

1.答案：O(nlogn)

-解析：快速排序的平均时间复杂度是O(nlogn)。

2.答案：0(n)

一解析：二叉树的深度可以通过递归计算，其时间复杂度是0(n)。

3.答案：最短路径数组(或dist数组)

-解析：Dijkstra算法中用于存储每个顶点到源点的最短路径的数组称为最短路径

数组。

4.答案：0(n，2)

-解析：冒泡排序的平均时间复杂度是0(n、2)。

5.答案：开放地址法(或线性探测法)

-解析：在哈希表中，解决冲突的两种主要方法是开放地址法(或线性探测法)和

链地址法。

三、简答题

1.答案：

-快速排序：通过一个分区操作将数据分成两个子序列，然后递归地排序两个子序

列。其平均时间复杂度是O(nlogn),但最坏情况下是0(/2)。

-归并排序：通过递归地将数据分成两个子序列，然后合并两个有序子序列。其时

间复杂度始终是O(nlogn)。

2.答案：

-二叉搜索树：是一种二叉树，其中每个节点的左子树只包含小于该节点的值，右

子树只包含大于该节点的值。其性质包括：

-没有重复元素。

-左右子树也是二叉搜索树c

-可以通过中序遍历得到有序序列。

3.答案：

-Dijkstra算法：用于在一个带权图中找出从源点到所有其他顶点的最短路径。基

本思想是：

1.初始化：将源点的距离设为0,其他点的距离设为无穷大。

2.选取未处理点中距离最小的点，更新其邻接点的距离。

3.重复步骤2,直到所有点都被处理。

4.答案：

-递归：函数调用自身的过程。例如，计算阶乘的递归函数：

python

deffactorial(n):

ifn==0:

returnl

else:

returnnfactorial(n-1)

5.答案：

-哈希表：通过哈希函数将键映射到数组中的•个位置，从而实现快速查找。哈希

函数的作用是将键转换为数组索引，减少查找时间。

-解决冲突的方法：

-开放地址法：当发生冲突时，寻找下一个空闲的槽位。

-链地址法：在每个槽位使用链表存储冲突的键。

四、编程题

1.答案：

python

defquick_sort(arr):

iflen(arr)<=1:

returnarr

pivot=arr[len(arr)//2]

1cft=[xforxinarrifx<pivot]

middle=Lxforxinarrifx==pivotJ

right=[xforxinarrifx>pivot]

roturnquicksort(left)+niiddle+quicksort(right)

2.答案：

python

classTreeNode:

def_init_(self,key):

self.left=None

self.right=None

self.val=key

classBST:

definsert(self,root,key):

ifrootisNone:

returnTreeNode(key)

ifkey<root.val:

root.left=self.insert(root,left,key)

else:

root,right=sell'.insert(root,right,key)

returnroot

defsearch(self,root,key):

ifrootisNoneorroot.val==key:

returnroot

ifkey<root.val:

rcturnself.search(root,left,key)

rcturnself.search(root,right,key)

3.答案：

python

importheapq

defdijkstra(graph,start):

distances={vertex:float(tinfinity')forvertexingraph)

distances[start]=0

priority_queue=[(0,start)]

whilepriorityqueue:

currentdistance,currentvertex=heapq.heappop(priorityqueue)

ifcurrentdistance>distances[current_vertex]:

continue

forneighbor,weightingraph[currentvertex],items():

distance=currentdistemce+weight

ifdistance<distances[neighbor]:

distances[neighbor]=distance

heapq.heappush(priority_queue,(distance,neighbor)'

returndistances

4.答案：

python

classlIashTable:

def_init_(self,size=100):

self.size=size

self.table=[[]for_inrange(size)]

defhashfunction(self,key):

roturnhash(key)%self.size

definsert(self,key):

index=self.hashfunction(key)

ifkeynotinself,table[index]:

self.table[index].append(key)

defsearch(self,key):

index=self.hashfunction(key)

returnkeyinself.tableCindex]

5.答案：

python

defispalindrome(s):

returns==s[:：-l]

五、综合题

1.答案：

python

deffindconnectedcomponents(graph):

visitcd=set()

components=LJ

defdfs(node,component):

stack=[node]

whilestack:

current=stack.pop()

ifeurrentnotinvisited:

visited,add(current)

component,append(current)

forneighboringraph[current]:

ifneighbornotinvisited:

stack,append(neighbor)

fornodeingraph:

ifnodenotinvisited:

component=[]

dfs(node,component)

components,cippend(component)

returncomponents

2.答案：

python

deflongest_increasing_subsequence(arr):

ifnotarr:

returnO

dp=[l]len(arr)

foriinrange(1,1cn(arr)):

forjinrange(i):

ifarr[i]>arr[j]:

dp[i]=max(dp[i],dp[j]+l)

returnmax(dp)

3.答案：

python

classLRUCachc:

def_init_(self,capacity):

self,capacity=capacity

self.cache={}

self.order=[]

defget(self,key):

ifkeyinself,ceiche:

self,order.remove(key)

self,order.append(key)

returnself,cache[key]

return-1

defput(self,key,value):

ifkeyinself.cache:

self,order,remove(key)

eliflen(self.cache)>=self.capacity:

oldest_key=self.order,pop(0)

delself.cache[oldest_key]

self,cache[key]=value

self,order,append(key)

4.答案：

python

defisbipartite(graph):

color={)

fornode