logo资料库

《数据结构》必须掌握的知识点与算法.doc

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：0.05M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    《数据结构》必须掌握的知识点与算法 第一章 绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破 坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此， 操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一 般关心其循环的次数与 N 的关系、函数递归的计算） 第二章 线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性 表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都 是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设 DataType a[N]的首地址为 A0，每一个数据（DataType 类型）占 m 个字节，则 a[k]的地址为：Aa[k]＝A0+m*k（其直接意义就是求在数 据 a[k]的前面有多少个元素，每个元素占 m 个字节） （2）多维数组，以三维数组为例，设 DataType a[M][N][P]的首地址为 A000，每一个数据（DataType 类型）占 m 个字节，则在元素 a[i][j][k]的前面共有 元素个数为：M*N*i+N*j+k，其其地址为： 4、线性表的归并排序： Aa[i][j][k]＝A000+m*(M*N*i+N*j+k)； 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性 表，并仍然接非递减顺序。可见算法 2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法 2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后， 追加存储空间（就是每次增加若干个空间，一般为 10 个）的处理过程，可见算 法 2.4 9、顺序线性表的删除元素过程，可见算法 2.5 10、顺序线性表的归并算法，可见算法 2.7
    11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法 2.9 14、链表的元素的删除，算法与图解，可见算法 2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表 尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算 法 2.11 16、链表的归并算法，可见算法 2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可 见算法 2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 20、循环链表的插入、删除算法、图解 21、双向链表的定义，意义 22、双向链表的构造算法（其与单链表的区别是在创建时确定的）、图解 23、双向链表的插入、删除算法、图解，可见算法 2.18、2.19 24、补充：在循环链表中，只设立一个表尾指针比只设立一个表头指针更方 便些，为什么？ 第三章 栈和队列 1、栈的顺序表示与实现 2、栈的链表表示与实现 3、栈的入栈、出栈操作算法 4、栈的几个经典应用（迷宫、表达式求值） 5、栈与递归的实现，如 Hanoi 塔问题 6、队列链式表示与实现 7、链式队列的入队、出队操作算法 8、循环队列的表示（顺序表示）和实现，特别注意其判满、判空方法、入 队操作、出队操作的实现（特别重要，考得频率很大） 9、补充：共享栈的方法与实现（即两个栈共享一个空间，他们采用栈顶相 向，迎面增长的存储方式） 10、补充：用两个栈来模拟一个队列的思路、算法 11、补充：表达式（前缀、后缀、中缀）的表达互换，这个操作要求对栈在 表达式求值中的应用相当熟练，并要求对后面的二叉树相当熟练 12、补充：了解双端队列（只需了解） 13、补充：链栈比顺序栈的优点与缺点 14、补充：一系列元素依次入栈再出栈的顺序，经典题目为：有 5 个元素， 其入栈次序为 A、B、C、D、E，以下哪种出栈的顺序是不可能的？ 15、补充：了解用循环链表实现队列，注意在该循环链表中只有一个头指针 或一个表尾指针（只需了解） 16、补充：根据给出的数学公式，写出对应的递归算法，最经典的就是用递 归求阶乘。 第六章 树和二叉树
    1、几个重要的概念：树、森林、子树、根、终端结点（叶子）、非终端结点、 双亲、孩子、兄弟、堂兄弟、度、深度、有序树、无序树、二叉树、k 叉树、完 全二叉树、满二叉树、线索二叉树； 2、二叉树的 5 种基本形态； 3、二叉树的 5 个重要性质： （1）在二叉树的第 i 层上至多有 2i－1 个结点（i≥1）； （2）深度为 k 的二叉树至多有 2k－1 个结点，（k≥1） （3）对任何一棵二叉树 T，如果其终端结点（叶子）数为 n0，度为 2 的 结点数为 n2，则 n0=n2+1； （4）具有 n 个结点的完全二叉树的深度为  log2  1 n ； （5）如果对一棵有 n 个结点的完全二叉树（其深度为  log2  1 n ）的结 log2  1 n 层，每层从左到右），则对任一结点 i （i）如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i>1,则其双亲 点按性层序编号（从第 1 层到第  （1≤i≤n），有： Parent（i）是结点 i 2 孩子 LChild（i）是结点 2i； 是结点 2i+1 （ii）如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左 （iii）如果 2i+1>n，则结点 i 无右孩子；否则其右孩子 RChild（i） 利用完全二叉树的上述性质，能处理大多数完全二叉树的计算题； 4、二叉树的存储结构： （1）了解顺序存储结构，只做了解； （2）链式存储结构，重要，需要掌握，后面的算法都是基于此结构； 5、二叉树的遍历： （1）能对任意一棵二叉树进行手动前序、中序、后序遍历； （2）能将由前序+中序、后序+中序给出的序列还原成一棵二叉树； （3）能将一个数学表达式用中序方法将其用二叉树画出来，并能写出其 前缀（波兰式）、中缀、后缀（逆波兰式）表达出来； 6、二叉树的遍历递归算法（注意前、中、后序三个算法只有细微的差别）， 可见算法 6.1，而他们的非递归算法不作要求； 7、建立二叉树链表的递归算法，可见算法 6.4； 8、线索二叉树的存储结构图； 9、能用手画出任意二叉树对应的线索二叉树（中序、后序线索）； 10、线索二叉树的非递归遍历算法，可见算法 6.5； 11、理解线索二叉树的中序线索化过程算法，可见算法 6.6； 12、手动写出任意森林、树的深度优先、广度优先遍历顺序； 13、森林、二叉树的转换过程，能用手画出即可； 14、哈夫曼树的相关概念：路径长度、带权路径长度 WPL、权值； 15、二叉哈夫曼树的构造过程，能用手动构造，并能将构造好的树用编码表 示出来；
    16、了解哈夫曼树的构造算法，可见算法 6.12，只需要了解，无需掌握； 17、记住树的记数公式：对一棵有 n 个结点的有 18、补充：二叉排序树、插入、删除结点的操作（在查找一章中有详述）； 19、补充：满二叉树、完全二叉树用数组存储方式，其元素、结点对应关系； 20、补充：求二叉树的高度（深度）算法； 21、补充：将二叉树中左、右孩子交换的算法； 22、补充：将用数组存储的完全二叉树转换成链式结构的算法； 23、补充：对用数组存储的完全二叉树进行非递归的前序、中序、后序遍历 棵不同的二叉树 n nC 21 1  n 算法； 24、补充：求二叉树中叶子数、度为 1 的、度为 2 的结点数算法； 25、补充：对于 K 叉树，其结点总数为 N，求出该树的最大高度、高小高 度； 26、补充：构造结点数为 n 的 k 叉哈夫曼树（其所有的结点要么度为 0，要 么度为 k），注意一般都需要增加 m 个权为 0 的结点（称为虚结点），其中如果叶 子结点数目不足以构成正则的 k 叉树（树中只有度为 k 或 0 的结点），即不满足 (n-1)MOD(k-1)=0（其中 MOD 是取余运算），需要添加权为 0 的结点，添加的个 数为 m=k-(n-1)MOD(k-1)-1。添加的位置应该是距离根结点的最远处。假设 n=10，k=3，则需要添加 1 个权为 0 的虚结点（其字母可以为空）。 第七章 图 1、图的几个重要概念：顶点、弧、弧尾、弧头、边、有向图、无向图、完 全图、邻接点、入度、出度、度、路径、回路（环）、连通图、连通分量、强连 通图、强连通分量、生成森林、关节点、重连通图、AOV-网、AOE-网； 2、图的几种存储、表示方法：数组表示法（重要）、邻接表（最重要，应用 最广）、逆邻接表（掌握）、十字链表（理解）、邻接多重表（了解），并能大致掌 握他们各种方法表示的优缺点； 3、图的两种遍历顺序：深度、广度优先，建议同时掌握其算法； 4、图的生成树和生成森林（只需掌握手画方法）； 5、图的最小生成树的两种算法：普里姆（Prim）算法（实质是顶点优先）、 克鲁斯卡尔（Kruskal）算法（实质是边优先），掌握他们的手动构造过程，了解 算法； 6、理解求关节点算法，可见算法 7.10、7.11； 7、了解拓扑排序； 8、掌握由 AOE-网得到关键路径的方法（手动），了解算法（7.13、7.14）； 9、掌握最短路径的手动求解过程、方法（两种：迪杰斯特拉 Dijkstra、弗洛 伊德 Floyd），了解算法； 10、补充：Prim 算法、Kruskal 算法、Dijkstra 算法、Floyd 算法的时间复杂 度； 11、补充：了解拓扑排序算法； 12、补充：能将图的抽象定义，如有向图 G＝（V，{A}），V＝{v1，v2，v3， v4}，A＝{，，，}画成图，也能将图用抽 象定义写出； 13、补充：能根据图的邻接表、逆邻接表、数组表示法表示出来的图画出，
    亦能根据图写出其邻接表、逆邻接表、数组表示法； 14、补充：了解四色定理(Four color theorem)：最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德·摩尔根（Augustus De Morgan，1806～1871） 1852 年 10 月 23 日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。 他在信中简述了自己证明四色定理的设想与感受。四色问题的内容是：“任何一 张地图只用四种颜色就能使具有共同边界的国家染上不同的颜色。”用数学语言 表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用 1，2，3， 4 这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。” 15、补充：了解离散数学中的欧拉图、哥尼斯堡七桥问题； 16、补充：了解汉密尔顿图； 第九章 查找 1、掌握几个重要的概念：静态查找表、动态查找表、平均查找长度、二叉 排序树、平衡二叉树、平衡因子、B－树、B＋树、哈希表； 2、顺序表的查找算法（9.1）及其时间复杂度的性能分析； 3、折半查找（二分查找）算法（9.2）及其性能分析； 4、能画出任意个数元素的二分查找过程形成的判定树； 5、掌握次优二叉查找树的构造过程，能用手画出，其算法只做了解要求； 6、掌握索引顺序表的查找（又称分块查找）基本原理，并能分析其性能； 7、能手动根据元素的顺序，构造出一棵二叉排序树； 8、掌握二叉排序树的几种算法：查找算法（9.5a、9.5b）、二叉排序树的插 入算法（9.6），而插入过程就是构造二叉排序树的过程； 9、掌握二叉排序树的删除结点的手动过程及算法（9.7、9.8）； 10、掌握二叉排序树的查找性能分析过程； 11、平衡二叉树的构造过程，重点在于平衡被破坏后的调整，LL 型、LR 型、 RR 型、RL 型的平衡旋转处理； 12、平衡树查找的性能分析； 13、B－树的查找操作，了解其算法； 14、B－树的查找性能分析； 15、B＋树的查找操作； 16、引入哈希表的目的、优点、基本原理； 17、了解几种常用的哈希函数：直接定址法、数字分析法、平方取中法、折 叠法、除留余数法、随机数法； 18、掌握几种常用的处理冲突的方法：开放定址法（线性探测法、伪随机数 序列法）、再哈希法、链地址法、公共溢出区法； 19、哈希表的查找性能分析； 第十章 内部排序 1、掌握几个重要的概念：排序、排序方法的稳定性（即关键字相同的经排 序后原顺序会不会变化）、排序算法效率的稳定性（即排序算法效率会不会受待 排序数据序列的影响而出现较大的变化）、内部排序、外部排序、堆 2、直接插入排序的过程（手动分析一趟排序的过程、结果）、算法（10.1）； 3、掌握折半插入排序算法（10.2）、理解 2－路插入排序、了解表插入排序； 4、希尔排序过程（手动分析一趟排序的过程、结果）、算法（10.4、10.5）；
    5、冒泡排序过程（手动分析一趟排序的过程、结果）、算法； 6、快速排序过程（手动分析一趟排序的过程、结果）、原理、算法（10.6-8） 7、快速排序性能分析； 8、简单选择排序过程（手动分析一趟排序的过程、结果）、算法（10.9）； 9、堆排序过程（手动分析建初始堆过程、一趟排序的过程、结果）、原理、 算法（10.10-11），堆排序原理、过程、算法非常重要，是常考点； 10、2－路归并排序过程（手动分析一趟排序的过程、结果）、算法（10.2-4）； 11、理解基数排序的原理、过程； 12、掌握各种内部排序方法的比较； 13、补充：各种内部排序的应用场合（这个比较难做，需要对各种排序算法 非常清楚才能做到）； 14、补充：冒泡排序的改进——鲨鱼排序过程、原理、算法； 15、补充：插入、选择、冒泡、快速、堆排序的算法效率稳定性分析，能判 断哪种算法不受初始数据的影响； 16、补充：用链表实现插入排序的过程、算法；
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料