常见算法面试题及答案
单项选择题（每题2分，共10题）
1.以下哪种排序算法平均时间复杂度为O(nlogn)？
A.冒泡排序
B.选择排序
C.归并排序
D.插入排序
答案：C
2.计算斐波那契数列第n项的递归算法时间复杂度是？
A.O(n)
B.O(2^n)
C.O(n^2)
D.O(logn)
答案：B
3.深度优先搜索（DFS）通常使用什么数据结构实现？
A.队列
B.栈
C.堆
D.哈希表
答案：B
4.二分查找要求数据是？
A.无序的
B.有序的
C.部分有序
D.都可以
答案：B
5.以下哪个不是哈希函数的特性？
A.高效性
B.唯一性
C.均匀性
D.确定性
答案：B
6.图的广度优先搜索（BFS）类似于树的什么遍历？
A.前序遍历
B.中序遍历
C.后序遍历
D.层序遍历
答案：D
7.快速排序的平均时间复杂度是？
A.O(n^2)
B.O(nlogn)
C.O(n)
D.O(logn)
答案：B
8.以下哪种数据结构适合实现优先队列？
A.数组
B.链表
C.堆
D.哈希表
答案：C
9.计算两个字符串最长公共子序列（LCS）可以使用什么算法？
A.贪心算法
B.动态规划
C.分治算法
D.回溯算法
答案：B
10.以下哪种排序算法是稳定的？
A.快速排序
B.堆排序
C.归并排序
D.希尔排序
答案：C
多项选择题（每题2分，共10题）
1.以下属于贪心算法应用场景的有？
A.哈夫曼编码
B.活动安排问题
C.背包问题（0-1背包）
D.最小生成树（Prim算法）
答案：ABD
2.以下哪些算法的时间复杂度为多项式时间复杂度？
A.冒泡排序
B.快速排序
C.旅行商问题（暴力解法）
D.矩阵乘法（普通算法）
答案：ABD
3.动态规划算法的特点有？
A.重叠子问题
B.最优子结构
C.无后效性
D.贪心选择性质
答案：ABC
4.以下哪些是图的存储结构？
A.邻接矩阵
B.邻接表
C.十字链表
D.邻接多重表
答案：ABCD
5.排序算法中，哪些在最坏情况下时间复杂度为O(n^2)？
A.冒泡排序
B.选择排序
C.插入排序
D.归并排序
答案：ABC
6.以下哪些数据结构支持快速查找（平均时间复杂度接近O(1)）？
A.哈希表
B.平衡二叉搜索树
C.普通二叉搜索树
D.堆
答案：AB
7.以下哪些算法可以用于图的遍历？
A.DFS
B.BFS
C.Dijkstra算法
D.Prim算法
答案：AB
8.递归算法的缺点有？
A.空间复杂度高
B.容易栈溢出
C.执行效率低
D.逻辑复杂
答案：ABC
9.以下哪些属于分治算法？
A.快速排序
B.归并排序
C.二分查找
D.矩阵乘法（Strassen算法）
答案：ABCD
10.以下哪些算法常用于字符串匹配？
A.暴力匹配算法
B.KMP算法
C.BM算法
D.Dijkstra算法
答案：ABC
判断题（每题2分，共10题）
1.哈希表查找元素的时间复杂度一定是O(1)。（）
答案：错
2.所有的排序算法都可以保证相同元素的相对顺序不变。（）
答案：错
3.深度优先搜索和广度优先搜索都可以用于遍历树结构。（）
答案：对
4.贪心算法一定能得到全局最优解。（）
答案：错
5.动态规划算法通常需要使用额外的空间来存储中间结果。（）
答案：对
6.快速排序在最坏情况下时间复杂度为O(nlogn)。（）
答案：错
7.二叉搜索树的中序遍历结果是有序的。（）
答案：对
8.图的最小生成树是唯一的。（）
答案：错
9.递归算法和迭代算法在解决相同问题时效率一定相同。（）
答案：错
10.计算一个整数的阶乘可以使用递归和迭代两种方法。（）
答案：对
简答题（每题5分，共4题）
1.简述快速排序的基本思想
答案：选择一个基准值，将数组分为两部分，使左边部分元素小于基准值，右边部分元素大于基准值。然后对左右两部分分别进行同样操作，直到整个数组有序。
2.简述Dijkstra算法的用途及基本思路
答案：用于计算图中一个节点到其他所有节点的最短路径。以起始节点为中心，逐步扩展找到距离它最近的节点，更新其距离值，并以此为基础继续寻找下一个最近节点。
3.简述动态规划算法的求解步骤
答案：分析问题的最优子结构性质；确定状态和状态转移方程；初始化边界条件；按照状态转移方程逐步计算并保存中间结果，直至得出最终答案。
4