计算机考研数据结构重难点及复习建议.pdfVIP

计算机考研数据结构重难点及复习建议

计算机考研数据结构重难点及复习建议

计算机考研的重难点解析和复习建议：数据结构

一、重难点解析和复习建议

数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基

本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算

法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本

原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程

序与实现算法的能力。

当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复

习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写

代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不

用强求写出一个没有任何语法错误的程序。

下面我们来解析一下知识点：

线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关

知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一

个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在

综合应用题当中的。

栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本

的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出

栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结

构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针

的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵

的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换

时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放

在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在

于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求

解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。

树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据

结构，要掌握树、二叉树的`各种性质、树和二叉树的不同存储结构、森

林、树和二叉树之间的转换、线索化二叉树、二叉树的应用二叉排序树、

平衡二叉树和Huffman树，重点要熟练掌握的，是森林、树以及二叉树

的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构

考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包

括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相

应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算

采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定

义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用

题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操

作比如结点数统计、左右子树对换等等，判断某棵二叉树是否二叉排序

树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归

的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后

继结点的算法以及给出Huffman编码等等。

图：在这一章中需要识记的是图以及基于图的各种定义，存储方式。

要熟练掌握图的深度遍历和广度遍历算法，这是用图来解决应用问题时常

用的算法基础。需要掌握基于图的多个算法，能够以手工计算的方式在一

个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过

抽象，会成为下列问题：最小生成树求解PRIM算法和__算法，两种方法

思想都很简单，但要注意不要混淆这两种方法，拓扑排序问题这里会用到

数组实现的链表，可以注意一下，关键路径问题数据结构的较大难点，要

把概念理解透，能做出表格找出关键路径，最短路径问题有重要的应用背

景，也是贪心法不多的能给出最优解的典型问题之一。

查找：这一章，需要识记关键字、主关键字、次关键字的含义;静态

查找与动态查找的含义及区别;平均查找长度ASL的概念念及在各种查找

算法中的计算方法和计算结果，特别是一些典型结构的ASL值，B-树的

概念和基本操作冲突解决方法的选择和冲突处理过程的描述，B+树的概

念新增考点，特别要注意B-树和B+树概念的对比，以及Hash表相关的

概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序

查找、二分查找的适用条件比如链表上用二分查找就不合适和算法复杂

度。

排序：排序算法众多，今年大纲还加上了外部排序，总共10种，各

种不同算法还有相应的一些概念定义需要