一、选择题（每小题3分，共30分）
1. 下列哪一项不是动态规划算法的基本要素？
A. 最优子结构
B. 贪心选择性质
C. 子问题重叠
D. 记忆化存储
2. 在图论中，深度优先搜索（DFS）的时间复杂度为：
A. O(V)
B. O(E)
C. O(V + E)
D. O(V^2)
3. 以下哪种排序算法在最坏情况下的时间复杂度为O(n log n)？
A. 冒泡排序
B. 插入排序
C. 归并排序
D. 快速排序
4. 哈希表的平均查找长度取决于：
A. 哈希函数
B. 冲突解决方法
C. 数据分布
D. 以上都是
5. 关于贪心算法，下列说法正确的是：
A. 总能找到全局最优解
B. 每一步选择局部最优解
C. 适用于所有优化问题
D. 时间复杂度总是最低
6. 二叉搜索树的查找操作的时间复杂度为：
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
7. 动态规划与分治法的主要区别在于：
A. 动态规划不重复计算子问题
B. 分治法需要记录中间结果
C. 动态规划适用于无后效性问题
D. 分治法可以解决所有动态规划问题
8. 关于快速排序，下列说法错误的是：
A. 平均时间复杂度为O(n log n)
B. 最坏情况下时间复杂度为O(n^2)
C. 是一种稳定的排序算法
D. 使用了分治思想
9. 在图论中，拓扑排序适用于哪种类型的图？
A. 有向无环图
B. 有向图
C. 无向图
D. 完全图
10. 关于回溯法，下列说法正确的是：
A. 回溯法是一种暴力搜索算法
B. 回溯法适用于所有NP问题
C. 回溯法通过剪枝减少不必要的搜索
D. 回溯法的时间复杂度总是最低
二、填空题（每小题4分，共20分）
1. 动态规划的核心思想是将一个问题分解为若干个__________，并通过记录这些子问题的解来避免重复计算。
2. 在图的广度优先搜索（BFS）中，通常使用__________数据结构来实现。
3. 快速排序的基本思想是通过__________将数组分为两部分，然后递归地对这两部分进行排序。
4. 贪心算法的一个典型应用是__________问题。
5. 在哈希表中，常用的冲突解决方法包括__________和__________。
三、简答题（每小题10分，共30分）
1. 请简述动态规划算法的基本步骤，并举例说明其应用场景。
2. 请比较分治法和动态规划法的区别，并举例说明它们各自的适用场景。
3. 什么是贪心算法？请举例说明贪心算法的应用及其局限性。
四、编程题（每小题10分，共20分）
1. 编写一个程序，实现快速排序算法，并测试其在随机数组上的性能。
2. 编写一个程序，实现Dijkstra算法，用于求解单源最短路径问题。
注意事项：
1. 请认真审题，确保答案完整且准确。
2. 所有解答需清晰明了，条理分明。
3. 鼓励结合实际案例进行分析。
祝考试顺利！
