|
||||
“数据结构”课程内容繁杂,知识点多,逻辑性、抽象性强。怎样备考?
“备考时,考生特别要注意对基本概念和基本理论的理解掌握,对各知识点梳理、类比、总结,综合贯通,将知识点串联起来构成知识网。”阅卷赵老师认为,“考生要掌握数据的逻辑结构、数据的存储结构、数据的运算三部分,因为这三部分内容构成了数据结构的主体知识框架,也是考试的重点和难点。”
赵老师说,逻辑结构是数据元素之间固有的逻辑关系的整体,是针对具体问题抽象出来的数据模型。而存储结构是数据和逻辑结构在计算机中的表示,存储必须依赖于计算机。最常见的逻辑结构有线性结构、树型结构和图结构等三种形式。一种数据的逻辑结构可以用多种存储结构来存储,而采用不同的存储结构,其数据处理的效率是不同的。因此,分析算法的时间性能也是数据结构一个重要方面。
赵老师说,算法的时间复杂度分析常采用渐进分析法。求解某程序段的时间复杂度的三个步骤是:找基本语句(通常是最内层循环的循环体);计算执行次数,即建立执行次数求和表达式;计算执行次数的数量级。
赵老师说,要按照逻辑结构、存储结构和运算实现流程学习表、树、图三种数据结构。
一般线性表 线性表是学习其他数据结构的基础。重点是在顺序表和单链表上如何实现各种基本操作,难点是对于线性表相关应用问题如何设计算法来解决。复习时应从线性表主要逻辑结构特征的顺序性、有限性、相同性入手,结合顺序存储和链接存储的不同特点对比分析学习常见操作的实现。主要基本操作尤其要注意查找、插入、删除的实现。
特殊线性表 由于栈和队列是操作受限的特殊线性表,其操作是对线性表操作的简化,只要掌握好线性表的内容,类比理解掌握栈和队列便游刃有余。与线性表相同,其重点是基本运算的实现,而难点在于循环队列中边界条件处理。 树 涉及概念、性质、算法的知识点非常多,重点是二叉树的性质与遍历,难点是以遍历算法为基础设计有效算法解决相关问题。 图 是本课程最难的内容,复习时应以图定义和基本概念(顶点、弧、子图、连通图、连通分量、路径、环和网等)为基础,要深刻理解图的深度优先和广度优先这两种存储结构的邻接矩阵法和邻接表法。图的应用(最小生成树、最短路径、拓扑序列)是图的难点,考题常以应用题的形式出现。 排序与查找 是实际应用中最常用的两种处理技术。该内容属于数据结构课程的知识应用部分。排序要重点掌握各种内部排序方法的特点。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。基于不同的“扩大”有序序列长度的方法,内部排序方法大致可分为插入类、交换类、选择类、归并类等四种类型。插入排序是将记录“插入”到有序序列的正确位置上;交换排序是将两个记录比较,当反序时“交换”来增加有序序列长度;选择排序是从未排序序列中选出最小(大)记录放入有序序列中;归并排序是不断“归并”两个或两个以上记录的有序子序列。复习时可以拿具体实例的各种排序过程理解各种排序方法的基本思路,同时还要注意各种排序方法稳定性和时间复杂度分析。查找要重点掌握各种查找算法基本思想、平均查找长度以及适用条件。在二叉查找树上执行删除操作是这部分内容的难点,常见的有:被删结点是叶子结点;被删结点只有一棵子树;被删结点既有左子树又有右子树的三种情况。 (刘璐)