(答案仅供参考)
(答案仅供参考)
另附:各章节重点总结
从每个章节来看,整书大概分为以下章节:绪论、线性表、栈和队列、串、多维数组和广义表、树、图、查找、排序。较为重点的章节为线性表、栈和队列、树、图这四个章节,这四个章节的内容从选择题到代码题都会涉及,而其他章节在分值的分布上相对来说没有这四个章节的比重大。以下分章节进行分析:
绪论一章主要涉及到数据结构的一些基本概念,重点是时空复杂度的分析。
线性表一章主要掌握线性表的顺序存储和链式存储的定义和性质,以及对应存储结构下的各种操作。其中,单链表、循环链表和双向链表是考试的重点和难点,这一部分往往在选择题以及代码题中出现。
栈和队列这一章,主要掌握栈和队列这两类数据结构的定义和性质,以及顺序结构和链式结构下的对应操作,例如出栈入栈、出队入队的操作。这一部分几乎每年的选择题、解答题和代码题中都会出现。
串这一章内容相对单一,考察重点主要是串的定义以及kmp算法的相关内容。kmp算法理解起来比较困难,但是考察方式往往是选择题。串这一部分的定义考察在解答题中出现过,因此也不能够掉以轻心。
多维数组和广义表这一章其实是两部分的内容,一个是多维数组,一个是广义表。多维数组部分,涉及到二维数组、三维数组以及推广到多维数组,还有矩阵的压缩存储,包括特殊矩阵、稀疏矩阵的内容。但是,总结来说,多维数组这一部分,其实是在考察数组地址的计算问题,在复习这一部分的时候,要围绕地址计算这一核心进行复习。广义表部分主要是理解相关定义和概念,往年来看考察内容比较少。
树这一部分是绝对的重点,并且从这一章开始,题目难度开始有所上升。树这一章提到了树的概念,
内容比较多,也比较繁杂,多在选择填空题中出现。之后是二叉树的对应存储结构和相关遍历操作,这是这一章的重点内容。二叉树的遍历操作是树这一章代码题的基础,只有对遍历操作熟练掌握,才能对树的其他代码题迎刃而解。后面有关树的存储结构,树、二叉树、森林的转换这部分,通常在解答题中出现。最后有关哈夫曼树的构造和应用也往往会是一道标准的解答题。
图这一章也是绝对的重点,也是考试的难点。总结来说,这一章讲了四个部分:图的概念、图的存储结构、图的遍历、图的应用。图的概念内容多,易混淆,多在选择题中出现。图的存储结构是理解图的重点,需要同学们记忆并理解。图的遍历是图这一章代码题的基础,图的代码题往往围绕图的遍历进行出题。图的应用主要包含最小生成树、拓扑排序、关键路径、最短路径问题,这几类问题不定期在每年的解答题中出现,因此需要对相关算法思想进行熟练掌握。
查找这一章分为基于线性表的查找:顺序查找、折半查找、索引查找;基于树的查找:二叉排序树、平衡二叉树;散列表。其中,散列表是考试的重点,需要掌握散列表的构造方法和冲突的解决方法,以及asl(平均查找长度)的计算方式。这些往往是以解答题的形式出现。
排序这一章考察的重点是几种内部排序。掌握插入排序、折半排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、二路归并排序的算法思想,能够做到手工模拟排序过程,并且对各种排序的比较进行熟练掌握。这类题目往往在选择题和解答题中出现,并且可能会结合线性表那一章进行出一些代码题。