考研计算机数据结构如何复习.docx

在准备考研计算机数据结构的复习时，考生需要理解并掌握数据结构的基本概念、原理和方法。数据结构是计算机科学中非常重要的一门课程，对于计算机专业研究生的选拔，它占据了相当大的比重。复习时，应注重以下几个方面： 1. 栈、队列和数组： - 栈是后进先出（LIFO）的数据结构，队列则是先进先出（FIFO）的结构。在考试中，进栈出栈序列的问题常常出现在选择题中。 - 了解栈和队列的顺序存储和链式存储结构，熟悉栈顶指针、队首指针和队尾指针的操作，特别是在循环队列中的判满和判空。 - 特殊矩阵的压缩存储，如二维矩阵与一维数组之间的转换，尤其要掌握下标计算方法。 2. 树和二叉树： - 学习树和二叉树的性质，掌握它们的不同存储结构，如顺序存储和链式存储。 - 重点掌握森林、树和二叉树的前序、中序和后序遍历，能够设计相应的算法。 - 熟悉线索化二叉树、二叉排序树、平衡二叉树（如AVL树）和Huffman树。 - 掌握节点数的计算，根据遍历序列还原二叉树，线索化的实质以及平衡二叉树的调整算法。 3. 图： - 理解图的基本定义和存储方式，如邻接矩阵和邻接表。 - 熟练掌握图的深度优先搜索和广度优先搜索算法，这是解决图相关问题的基础。 - 应用问题可能涉及最小生成树（PRIM算法和KRUSKAL算法）、拓扑排序、关键路径和最短路径问题。 4. 查找： - 明确关键字、主关键字和次关键字的含义，理解静态查找和动态查找的区别。 - 掌握平均查找长度（ASL）的概念，计算不同查找算法的ASL值。 - 熟悉B-树的基本操作，对比B-树和B+树的区别，理解Hash表的工作原理和冲突解决策略。 在复习过程中，考生不必过于关注编写完美无误的代码，而是要注重算法设计和分析。能够用伪代码清晰地表达思路即可。对于算法的时间复杂度和空间复杂度分析，也需要有一定的理解。同时，通过做题和实践来巩固理论知识，提高解决问题的能力。记住，复习的重点在于理解和应用，而不仅仅是记忆。