2021春年《数据结构》考试大纲(专插本).pdf

《数据结构》是计算机科学与技术专业的重要课程，2021年的春季考试大纲主要针对专升本的学生，旨在评估他们在数据结构领域的基础知识和编程应用技能。考试大纲旨在选拔掌握基本原理、熟悉常见数据结构及算法的优秀专科毕业生，为他们进入本科阶段的学习打下坚实基础。 大纲分为几个部分，涵盖了数据结构的基础理论和实际应用： 1. 绪论部分，考生需要理解数据结构的基本概念，如逻辑结构、存储结构、数据类型和抽象数据类型。此外，还需掌握算法的基本概念和描述方法，以及如何进行算法的时间复杂度和空间复杂度分析。Java的泛型也是一个重要的知识点，考生需了解其在数据结构中的应用。 2. 线性表是基础数据结构之一，包括线性表的基本概念，顺序存储和链式存储的实现。这部分会涉及单链表、循环链表和双向链表，以及线性表在实际问题中的应用。 3. 栈和队列是两种特殊的数据结构。考生需要掌握栈的抽象描述，顺序栈和链式栈的实现，以及栈的应用。队列的抽象描述、顺序队列和链式队列的实现，以及队列在实际问题中的应用也是考察重点。此外，还要求考生能理解和运用栈和队列的综合应用场景。 4. 树和二叉树部分，考生需要理解树的基本概念，重点掌握二叉树的性质、存储结构和遍历方法（先序、中序、后序遍历）。此外，还包括二叉树的构造、哈夫曼树及其编码（最优二叉树、哈夫曼树的构建和哈夫曼编码），以及树与森林的转换。 5. 图论是数据结构中的一个重要分支，考生需要理解图的基本概念，掌握图的存储结构，如邻接矩阵和邻接表。图的遍历（广度优先和深度优先）、最小生成树（克鲁斯卡尔算法和普里姆算法）、最短路径（戴克斯特拉算法和弗洛伊德算法）、拓扑排序和关键路径等内容也将被考察。 6. 内排序是处理大量数据的关键技术，考生需要掌握排序的基本概念，如排序的分类。具体算法包括直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、树形选择排序、堆排序、归并排序和基数排序，以及这些算法的时间复杂度和空间复杂度分析。 7. 查找技术部分，考生需要了解查找的基本概念，熟悉静态表查找（顺序查找、二分查找、分块查找）和动态表查找（二叉排序树、平衡二叉树、B-树、B+树）。此外，哈希表查找，包括哈希函数和冲突解决策略也是重点。 通过这个考试大纲，我们可以看到，《数据结构》课程不仅要求学生具备扎实的理论基础，还强调实际问题的解决能力和算法的分析能力。对这些知识点的深入理解和熟练掌握，将有助于学生在未来的学习和工作中解决各种复杂的数据处理问题。