845数据结构和算法考研高分笔记

2018 年全国攻读硕士学位研究生入学考试试题 南京大学南京大学 20182018 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题 考研高分笔记考研高分笔记 （（845845 数据结构与算法）数据结构与算法） 第一章 概述 一、概念 1．学科数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和操作等等。 2． 概念 由某一数据对象及该对象中所有数据成员之间的关系组成。 具体来说， 数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据 所施加的运算。 3．这三个方面的关系为 1数据的逻辑结构独立于计算机，是数据本身所固有的。 2存储结构也称为物理结构，是逻辑结构在计算机存储器中的映像，必须 依赖于计算机。 3运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但 运算的实现必依赖于存贮结构。 4．数据（data）信息的载体，指能够输入到计算机中，并被计算机识别和处理 的符号的集合。例如数字、字母、汉字、图形、图像、声音都称为数据。 5．数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不 同属性的项（字段） ，故不是组成数据的最小单位。 6．逻辑结构从解决问题的需要出发，为实现必要的功能所建立的数据结构， 它属于用户的视图，是面向对象的。 7． 物理结构 指数据该如何在计算机中存放， 是数据逻辑结构的物理存储方式， 是属于具体实现的视图，是面向计算机的。 8．逻辑结构与存储结构二者关系物理结构是逻辑结构的存储映象。 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采 用的存储结构。 9．从逻辑结构划分数据结构线性结构和非线性结构（树、图） 10．线性结构 1 元素之间为一对一的线性关系 2 第一个元素无直接前驱 3 最后一个元素无直接后继 4 其余元素都有一个直接前驱和直接后继。 k1k1k2k2k3k3k4k4k5k5k6k6k7k7 11．非线性结构 1元素之间为一对多或多对多的非线性关系 2每个元素有多个直接前驱或多个直接后继 1 2018 年全国攻读硕士学位研究生入学考试试题 12．顺序存储数据元素存储方法所有元素存放在一片连续的存贮单元中。 数据元素之间关系表示逻辑上有相邻关系的元素存放到计算机内存仍然相邻， 即存储位置体现了数据元素之间的关系。 13．链式存贮 数据元素存储方法元素可以存放在不连续的存贮单元中。 数据元素之间关系表示逻辑上相邻的元素存放到计算机内存后不一定是相邻 的，因此元素之间的关系通过地址确定。 batcateat mat 14．算法一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算 序列。特性 输入有 0 个或多个输入 2 2018 年全国攻读硕士学位研究生入学考试试题 输出有一个或多个输出处理结果 确定性每步定义都是确切、无歧义的 有穷性算法应在执行有穷步后结束 可行性每一条运算应可通过已经实现的基本运算执行有限次来实现 算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性 （死循环） ，另外，程序中的指令必须是机器可执行的，而算法中的指令则无此 限制。一个算法若用计算机语言来书写，则它就可以是一个程序。 15．算法的分析与度量 1）算法的性能标准 正确性正确执行的功能和性能要求。 可使用性算法能够很方便的使用。 可读性便于理解、测试和修改算法。 效率计算机资源的消耗，包括存储和运行时间。 健壮性检错、报错及纠错的功能。 2）算法的事前估计空间复杂度和时间复杂度 3）算法的后期测试在算法中的某些部位插装时间函数time ，测定算法 完成某一功能所花费的时间。 16．时间复杂度一个算法执行所耗费的时间，从理论上是不能算出来的，必 须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试， 只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个 算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数 多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。 记作TnOfn 表示算法中基本运算次数 Tn是问题规模n的某个函数fn。 1）求下列算法段的语句频度 fori1; iq;--p *p1*p; *qe; L.length ; return; } void ListDel_sqSqlist eL.elem[i-1]; forint ji;j0，则  有一个特定的称为根 （root） 的结点。 它只有直接后继， 但没有直接前驱。  除根结点以外的其它结点可以划分为 m（m≥0）个互不相交的有限集合 T0，T1，，Tm-1，每个集合 Ti（i0,1,,m-1）又是一棵树，称为根的 子树，每棵子树的根结点有且仅有一个直接前驱，但可以有 0 个或多个 直接后继。  由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概 念。 树形表示法广义表嵌套集合表示法 2． 双亲、孩子 祖先、子孙 兄弟 堂兄弟 结点深度 树的深度 结点的度 叶子结点 分支结点 树的度 一对关系中的直接前驱、直接后继。 一对关系集合中的前驱、后继。 具有相同直接前驱的数据元素。 具有相同前驱的数据元素。 根结点的深度为 1 若某结点深度为 i,则其子结点深度为 i1 空树深度为 0； 非空树深度等于子树深度的最大值加 1。 结点拥有的子树数。 度为 0 的结点。 度不为 0 的结点。 树内所有结点的度的最大值。 有序树、 无序树左右结点是否等价 森林m 棵互不相交的树的集合。 m0空集；m1树 3．一棵二叉树是一个结点的有限集合，该集合或者为空，或者是由一个根结点 加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 9 2018 年全国攻读硕士学位研究生入学考试试题 4． 性质 1若二叉树的层次从 0 开始, 则在二叉树的第 i 层最多有 2i 个结点。 i 0  性质 2深度（高度）为 k 的二叉树最多包含的结点数为 2k-1（k0）  性质 3对任何一棵二叉树, 如果其叶结点有 n0个, 度为 2 的非叶结点有 n2个,则有 n0＝n2＋1  定义 1满二叉树 Full Binary Tree 深度为 k，共有 2k-1 个结点 。  定义 2完全二叉树 Complete Binary Tree 若设二叉树的深度为 k，除第 k 层外，其它各层 0 k-1 的结点数都达到 最大个数，即 k-1 层是满二叉树，第 k 层从右向左连续缺若干结点，这就是完 全二叉树。 性质 4具有 n 个结点的完全二叉树的深度为 intlog2n1。 性质 5有 n 个结点的完全二叉树，结点从 0 顺序标号  若 i0，i 的双亲结点是i-1/2。  若 2i1n，i 的左孩子是 2i1；否则 i 无左孩子