搜索
数据结构OFFICE公共基础（一）韩磊宁师VIP速成班考点1算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。2．算法的基本要素：一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言（C语言，汇编，文字）等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。传统流程图N-S流程图考点2算法复杂度时间复杂度一个算法所需要时间一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。空间复杂度占用存储空间的大小考点3数据结构的定义数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。考点4线性结构与非线性结构线性结构对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合。它有四个基本特征：1．集合中必存在唯一的一个第一个元素；2．集合中必存在唯一的一个最后的元素；3．除最后元素之外，其它数据元素均有唯一的后继；4．除第一元素之外，其它数据元素均有唯一的前驱。常用的线性结构有：线性表，栈，队列，双队列，数组，串。关于广义表，是一种非线性的数据结构。哈希表常见的非线性结构有：树(二叉树等)，图(网等)非线性结构考点5栈和队列及其基本运算1、栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。2、定义队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。考点6线性链表的基本概念1、链接存储方法链接方式存储的线性表简称为链表（LinkedList）。链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。链表是从头指针开始读数据和下个数据的指针如左图1、Head为1652、读取165内的数据为bat，下一个指针为130读取130cat，135135eat…一直到最后一个指针为NULL(空)时停止考点7树与二叉树及其基本性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k－1个结点（k≥1)。性质3：对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。性质4：具有n个结点的完全二叉树的深度为log2n+1。性质5：如果对一棵有n个结点的完全二叉树(深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点i/2。(2)如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。(3)如果2i+1n，则结点i无右孩子；否则，其右孩子是结点2i+1。二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树均可与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。二叉树的定义二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。定义特点1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。2、子树有左右之分，其次序不能颠倒。3、二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。树当结点只有一个孩子时，就无须区分它是左还是右。（也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了），因此二者是不同的。这是二叉树与树的最主要的差别。二叉树不是树的特殊情况，它们是两个概念。注AB具有两个结点的树只有一种状态ABAB具有两个结点的二叉树有两种状态二叉树的5种基本形态(a)空二叉树(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。完全二叉树(Completebinarytree)深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。特点：叶子只可能分布在层次最大的两层上。对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次必为l或l+1。满二叉树完全二叉树是定一不一定是245361完全二叉树245361非完全二叉树考点8二叉树的遍历二叉树的遍历有三种方式，如下：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC,中序结果连起来是BDAFEHGC后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA顺序查找：从表的一端开始，逐个进行记录的关键字和给定值的比较。查找过程：0123456789101164053719211356649288807564优点：算法简单，适应面广。缺点：平均查找长度大。顺序查找考点9顺序查找在下列两种情况下也只能采用顺序查找：（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。有序表表示静态查找表查找过程：1234567891011513192137566475808892找21lowmidhigh1234567891011513192137566475808892找63lowhighmidHighlow折半查找考点十折半查找性能分析：123456789101151319213756647580889212233334444Cii6391471025811判定树表中一个记录比较次数=路径上的结点数比较次数=结点4的层数比较次数树的深度≤log2n+1＝查找成功：查找不成功：比较次数=路径上的内部结点数比较次数≤log2n+1-13-46-79-101-22-34-55-67-88-910-1111-考点11交换类排序法冒泡排序法和快速排序法都属于交换类排序法。（1）冒泡排序法首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后最大者到了线性表的最后。然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。在最坏的情况下，冒泡排序需要比较次数为n（n－1）/2。（2）快速排序法它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？冒泡排序法的平均执行时间是O（n2），而快速排序法的平均执行时间是O（nlog2n）。