admin 管理员组文章数量: 1184232
2024年5月30日发(作者：数字组词有哪些组词)
第一章复习要点是：
数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构
分为哪两大类，及其逻辑特征、数据的存储结构可用的四种基本存储方法。时间复杂度与渐近时
间复杂度的概念，如何求算法的时间复杂度。可能出的题目有选择题、填空题或简答题。
第二章复习要点是：
线性表的逻辑结构特征、常见的线性表的基本运算，并可以根据这些基本运算组合得到更复杂
的运算。顺序表的特征、顺序表中结点地址的计算。顺序表上实现的基本运算(算法)：主要是插
入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。单链表的特征、图形表示法。
单链表的各种算法实现，并能运用这些算法解决一些简单问题；循环链表的特征、双链表的特征
以及它们的主要算法实现。可能出的题型有：填空题、简答题、应用题和算法题。
第三章复习要点是：
栈的定义、其逻辑结构特征、栈的基本运算、栈的上溢、下溢的概念。队列的逻辑结构，队列
的基本运算；循环队列的边界条件处理；以上各种基本运算算法的实现。算法的简单应用。可能
出的题型有填空、选择、简答、算法等。
第四章复习要点是：
串是一种特殊的线性表，它的结点仅由一个字符组成。空串与空白串的区别：空串是长度为零
的串，空白串是指由一个或多个空格组成的串。串运算的实现中子串定位运算又称串的模式匹配
或串匹配。串匹配中，一般将主串称为目标(串),子串称为模式(串)。本章可能出的题型多半为选
择、填空等。
第五章复习要点是：
多维数组和广义表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素可能有多个直接
前趋和多个直接后继。多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方
式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表示
(画图形表示)。广义表是线性表的推广，也是树的推广。能画出广义表的图形表示法。广义表的
取表头运算与取表尾运算要注意，表头是广义表的第一个元素，它不一定是原子，表尾则必是子
表。
第六章复习要点是：
本章是重点章，二叉树又是本章的重点内容。据分析，本章在试题中所占分数达到20%左右，
如加上其他章节与二叉树有关的二叉排序树等内容，则占有四分之一以上的分值，可见树是十分
重要的内容，务必仔细掌握各个知识点。
首先是树的概念，包括与树有关的各个名词的意义要能够完全领会，在这方面可能出的题目多
是填空、选择等题型。树的四种表示方法：树(图)形表示法、嵌套集合表示法、凹入表示法和广
义表表示法。二叉树的定义、二叉树的五种基本形态、为什么二叉树不是树的特殊情形，这里要
注意二叉树与度为二的有序树的区别所在。二叉树的四个性质，如果理解了二叉树，应该能够推
导出来。多会出填空题。对于两种特殊情形的二叉树(完全二叉树和满二叉树的定义)应该十分清
楚。二叉树的顺序存储适宜用于完全二叉树。
第七章复习要点是：
图的概念中主要记忆连通图、连通分量、强连通图和强连通分量的定义和应用(填空、选择、
应用)。图的邻接矩阵表示法和邻接表表示法应熟练掌握，根据表示法画出图或者根据图写出邻
接矩阵表示或画出邻接表(应用)。注意一个图的邻接矩阵表示是唯一的，而邻接表表示则不是唯
一的。稀疏图及稠密图的概念及适用的表示法(填空或选择等)。在图中求顶点的度，在邻接表和
邻接矩阵中如何计算(填空题)。图的遍历一定要掌握，对图的深度优先遍历和广度优先遍历的遍
历序列应能正确写出(填空或选择)。两种遍历生成树的作图(选择、应用)。最小生成树的两种算
法思想(Prim算法、Kruskal算法)要掌握，就是要能在给定的图中分别用两种算法作出最小生成
树(包括生成过程)(应用)。最短路径树的生成画图(应用)。拓扑排序的两种方法(无前趋的顶点优
先和无后继的顶点优先)应注意到使用DFS遍历算法是后一种方法所排出的拓扑序列(填空、选
择)。
第九章复习要点是：
查找的基本概念应明确动态查找表和静态查找表的含义、内查找和外查找的含义，平均查找长
度的定义及计算。线性表的查找有三种方法：顺序查找、二分查找和分块查找。二分查找对线性
表的要求。什么是判定树?对于给定的序列，画出二叉判定树。二分查找的平均查找长度，其在
最坏情况下查找成功的比较次数也不超过判定树的深度。为什么在链表上无法实现二分查找？分
块查找的算法思想。分块有序，块内无序。又称索引顺序查找。三种查找方法各自的优缺点。树
上的查找，是重点（这里有二叉排序树、平衡二叉排序树）。
什么是二叉排序树?二叉排序树的插入和生成，给定一个序列，请画出二叉排序树的生成过程。
二叉排序树中结点的删除。其中要注意的是第三种情况，删除的结点若有两个孩子，则用删除结
点的中序后继结点来替换要删的结点。二叉排序树的查找就是从根结点出发走一条从根到待查结
点的路径，应能判断某一序列是否是二叉排序树中可能的查找序列。二叉排序树与二分查找的比
较及选择。什么是平衡二叉树？B-树，主要应了解B-树的生长过程，当结点分裂时产生的两个
结点大约是半满的，向上插入的关键字总是分裂结点中间位置上的关键字，无论按何次序插入关
键字，树都是平衡的。这与二叉排序树是不同的。
散列表(也是重点内容)，什么是散列表?散列函数、散列值、散列的含义。冲突(碰撞)、同义词
的含义。散列函数的选择标准：简单和均匀。学过的几种方法：平方取中法、除余法、相乘取整
法、随机数法。处理散列表中冲突的方法：开放定址法和拉链法。产生聚集的原因是什么？使用
线性探查法画出散列表，并能计算散列表中查找的平均查找长度。使用拉链法画出生成的散列表，
也应能计算查找的平均查找长度。什么是装填因子?装填因子和散列表中冲突发生率的关系。
第十章复习要点是：
本章亦是很重要的章节，通过试卷分析，分值一般占10%左右，但是本章的内容很多，很难
说哪一部分是不重要的。基本概念中应明确稳定排序和不稳定排序的含义、内部排序和外部排序
的含义。排序算法好坏的评价标准是执行时间和所需的空间，另外算法本身的复杂程序也是要考
虑的一个因素。
(1)插入排序：直接插入排序法应掌握算法(包括算法的实现)(算法题)。希尔排序的算法思想，
版权声明：本文标题：大学数据结构复习要点 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1717034950a700034.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论