数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。
数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合
数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = {D, R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。
数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。
判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。 算法效率的衡量方法：后期测试，事前估计 算法分析是算法的渐进分析简称
数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):
逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”
线性表的定义：n（ ? 0）个表项的有限序列 L =（a1, a2, …, an） ai是表项，n是表长度。第一个表项是表头，最后一个是表尾。
线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存储方式。一，顺序存储方式，二，链表存储方式。
顺序表的存储表示有2种方式：静态方式和动态方式。
顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。
顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问 。
单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长度可以很方便地进行扩充。
连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表） 特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间
单链表的类定义：多个类表达一个概念(单链表)。分为：链表结点(ListNode)类 ，链表(List)类。
循环链表的概念：是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址，就能遍历表中其他任何一结点。
双向链表的概念：在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LINK指示它的前驱结点，RLINK指示它的后继结点，因此，双向链表的每个结点至少有3个域：1LINK(前驱指针) DADA（数据） RLINK（后继指针）。 栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出。
递归的定义 ：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法一。 定义是递归的二。 数据结构是递归的三问题的解法是递归的。
队列：队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性：先进先出。
优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。
多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。 字符串是 n ( ? 0 ) 个字符的有限序列， 记作S : “c1c2c3…cn”其中，S 是串名字c1c2c3…cn”是串值ci 是串中字符n 是串的长度，n = 0 称为空串。
广义表是 n ( ≥0 ) 个表元素组成的有限序列，记作LS (a1, a2, a3, …, an)，LS 是表名，ai 是表元素，可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n = 0 的广义表为空表。n > 0时，表的第一个表元素称为广义表 的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail
有根树：一棵有根树 T，简称为树，它是n (n≥0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作 T={ 空集 n=0
{r,T1,T2….Tn},n>0
r 是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为 m (m ? 0) 个互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
二叉树的定义:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
完全二叉树 :─ 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树
二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L 遍历根的右子树记作 R。则可能的遍历次序有：前序 VLR 镜像 VRL；中序 LVR 镜像 RVL；后序 LRV 镜像 RLV
前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点 (V)；前序遍历左子树 (L)；前序遍历右子树 (R)。遍历结果- + a * b - c d / e f
树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历 EFBCGDA；对应二叉树中序遍历 EFBCGDA；树的后根遍历结果与其对应二叉树。
表示的中序遍历结果相同：树的后根遍历可以借助对应二叉树的中序遍历算法实现
最小堆和最大堆：如果有一个关键码集合K={K0,K1，K2，K3，….,Kn-1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki≤K2i+1且Ki≤K2i+2(或者Ki≥K2i+1且KiK2i+2 )i=0,1,….[（n-2）/2]，则称这个集合为最小堆或最大堆。
堆是最高效的一种数据结构，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。
堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到，另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。 路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。
路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根结点到达书中每一结点有且仅有一条路径。
Huffman树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树。 带路径长度最小的扩充二叉树不一定是完全二叉树。
集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。
字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。
散列方法：理想的搜索方法是可以不经过比较，一次直接从字典中得到要搜索的元素。如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash()， 使得每个关键码与结构中一个唯一的存储位置相对应：Address ＝ Hash(key)。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。
散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突
搜索就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，应报告一些信息, 如失败标志、位置等 搜索结构通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。静态环境，搜索结构在插入和删除等操作的前后不发生改变。? 静态搜索表 动态环境，为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。? 动态搜索表
顺序搜索主要用于在线性表中搜索。设若表中有 CurrentSize 个元素，则顺序搜索从表的先端开始，顺序用各元素的关键码与给定值 x 进行比较若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。若整个表都已检测完仍未找到关键码与 x 相等的元素，则搜索失败。给出失败信息
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：1每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。2左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3右子树（如果非空）上所有结点的关键码都大于根结点的关键码。4左子树和右子树也是二叉搜索树。
二叉搜索树为二叉排序树如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树
在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为 x 的元素，搜索过程从根结点开始。如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子 二叉搜索树的插入算法：为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。
图定义：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或E = {<x, y> | x, y ? V && Path (x, y)}，是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。 有向图与无向图：在有向图中，顶点对 <x, y> 是有序的。在无向图中，顶点对(x, y)是无序的。
完全图：若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图
在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。
邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标 dest 和指针 link。对于带权图，边结点中还要保存该边的权值cost。顶点表的第 i 个顶点中保存该顶点的数据，以及它对应边链表的头指针adj 最短路径问题：如果从图中某一顶点（称为源点）另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据元素的有限集合。
排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。 插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。
排序
第二篇：数据结构重点整理
考点
1 算法的时间复杂度 (不会出简单的for循环)
例题.1下面程序段的时间复杂度为 D O(n*log2n) for (k=1;k<=j;k++)
｛ int i=1; while (i<=n)
i=i*2; ｝
O(1)初始化线性表 检查线性表是否为空
O(n)删除线性表中的所有元素；得到线性表的长度；得到线性表中指定序号为pos的元素；遍历一个线性表；从线性表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向线性表中按给定条件插入一个元素；从线性表中删除符合给定条件的第一个元素
O(n^2)对线性表进行排序 2几种数据结构 （数据结构定义：具有结构的数据元素的集合 ）
逻辑结构：集合、线性结构（线性表、广义表、堆栈和队列）非线性结构（树、图） 存储结构：顺序存储结构、链式存储结构、索引结构、散列结构等
集合和线性结构：1 ：1 树形结构：1 ：N 图形结构：N : N 3 线性表顺序存储和链接存储的特点
顺序存储：随机存取，预先定义表长；插入删除时有大量元素的移动（当下标为1开始的实话移动n-i+1，当下标为0开始的实话移动n-i），查找方便。
链式存储：非随机存取，表长不需要预先定义是动态分配，插入删除不需要大量的元素移动，查找时从第一个元素开始查找。
4 根据线性表的常用操作，选择最合适的存储方式
顺序表和链表的比较：
空间方面：a当表长难估较大时，选择链式存储b当表长较小时，选择顺序存储 时间方面：a插入与删除较多时选择链式存储b查找方面较多时用顺序存储
语言方面：当语言没有指针，选用链式存储时选用静态链表（静态链表需要预先设定空间）
某线性链表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点, 用仅有尾指针的单循环链表存储方式实现这两种操作
6 链表的特点
例题：链表不具有的特点是（A）。
A、可随机访问任意元素 B、插入删除不需要移动元素
C、不必事先估计存储空间 D、所需空间与线性表长度成正比
7 链表的插入删除
8 链表各操作的时间复杂度
O(1)初始化链表 检查链表是否为空
O(n)删除链表中的所有元素；得到链表的长度；得到链表中指定序号为pos的元素；遍历一个链表；从链表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向链表中按给定条件插入一个元素；从链表中删除符合给定条件的第一个元素 O(n2)对链表进行排序
例题：在一个长度为n单链表；在表头插入元素的时间复杂度为 O(1) ；在表尾插入元素的时间复杂度为O(n)。
9 栈的特点：先进后出，后进先出。
10 栈的顺序存储、链式存储的出栈入栈时间复杂度：O(1)
13 根据给定递归算法和输入 求输出
（读递归程序）
14 数组上的循环队列 的进队出队操作 （参考期中考试最后大题）
判空：rear == front 满：(rear+1)%MaxSize == front 进队操作：rear = (rear+1)%MaxSize; Q(rear)=x 出队操作：front = (front+1)%MaxSize; X=Q(front)
入队时需先修改入队指针（队尾指针）rear = = (rear +1)% QueueMaxSize 出队时需要修改队头指针front == (front +1)% QueueMaxSize 15 链队的插入O(1)
void EnQueue (LinkQueue& HQ,const ElemType& item) { LNode* newptr=new LNode; if (newptr ==NULL) { cerr<<“Memory alocation failure."<<endl; exit(1); } newptr->data=item; newptr->next =NULL; if (HQ.rear==NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear->next=newptr; }
17 稀疏矩阵的定义：其非零元素的个数远远小于零元素的个数。
稀疏矩阵的严格定义： 稀疏因子?=非零元素/所有元素个数 通常认为 ? ? 0.3 的矩阵为稀疏矩阵
三元组表示形式： ( i, j, value ) i为第i行， j为第j列，value为非0元素的值 18 广义表的特点
规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a是广义表的表头head。其余元素组成表尾tail；
广义表中的数据元素有相对次序;广义表的长度定义为所含元素的个数;
广义表的深度定义为括号嵌套的最大次数;注意:“空表”的深度为 1 ; 广义表可以共享; 广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。 例：D=(E, F) E=(a, (b, c), D) , F=(d, (e)) D的长度为2，深度为无穷 19 求广义表的长度 深度
广义表的深度=Max {子表的深度} +1；空表的深度 = 1；仅由单元素组成的表的深度 = 1 例LS=((),(e),(a,(b,c,d)))长度为3深度为3； LD=(((a),((),b),(c)))长度1深度4 20 树的性质1
树中结点个数等于所有结点的度数加1 21 二叉树的性质4 P185
书中性质4：
若对具有n个结点的完全二叉树按照层次从上到下,每层从
左到右的顺序进行编号, 则编号为i 的结点具有以下性质:
(1) 若编号为i的结点有左孩子,则左孩子结点的编号为2i;若编号为i的结点有右孩子,则右孩子结点的编号为2i+1.
(2) 除树根结点外,若一个结点的标号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子. (3) 若i≦|_n/2_|,即2i ≦n,则编号为i的结点为分支结点,否则为叶子结点.
(4) 若n为奇数,则每个分支结点都既有左孩子,又有右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有.
22 给定权值 构造哈夫曼树 求带权路径长度（参考作业题）
例题1：如右图：
WPL=7*1+5*2+2*3+4*3=35
23 哈夫曼树的特点
又称最优树，是一种带权路径长度WPL最 小的二叉树。
由0和1组成，用哈夫曼编码传送的电文长度；传输速率最快。 叶子结点的度为零；除叶子结点外的所有结点的度都为2
24 二叉排序树求平均查找长度:
K为层数，n表示最大层数，m（k）表示第k层有m结点个数， M表示所有结点个数。
/（M）
25 有向图边数和顶点入度 出度关系
在有向图的邻接表中，从一顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍；在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的1倍；无向图的邻接表中结点个数的边数的2倍。 向图边数=所有度之和/2
26 无向图 顶点数和最小生成树的边数关系
无向图 顶点数n：最小生成树的边数n-1 27 图的邻接表P258
邻接表:是图的一种链式存储结构。在邻接表中，对图中每个顶点建一个单链表，第i个单链表中的结点表示依附于顶
点vi的边（对于有向图是以顶点vi为尾的弧）。 图的邻接表是存放什么的：
无权无向图：列存放所有节点，横向为结点对应邻接结点和指针指向结点对应的下一邻接点
带权有向图：列存放所有节点，横向为结点的出度的所有邻接点，其中第一项为结点名称，第二项为与该结点名称对应的权值，第三项为指针指向结点对应的下一出度邻接点。
28 求最短路径长度P281
两个顶点间可能存在多条路径，其中有一条是长度最短的路径，即最短路径
若带权值要i到j中所经过边权值之和最小的路径称为最短路径，其权值称为最短路径长度。
29 图的边数与顶点数的关系
（以下是网上找的小题）
30 1） 布里姆算法
依次在G中选择一条一个顶点仅在V中,另一个顶点在U中,并且权值最小的边加入集合TE,同时将该边仅在V 中的那个顶点加入集合U. 重复上述过程n-1次,使得U=V,此时T为G的最小生成树.
2） 克鲁斯卡尔算法
将图Ｇ中的边按权值从小到大的顺序依次选取，若选取的边使生成树Ｔ形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止,此时T为G的最小生成树.
31 顺序查找的平均查找长度:（1+2+3……n）/N 32 构造二叉排序树 求平均查找长度
平均查找长度为：（1*1+2*2+3*4+4*1）/8=21/8
33二分查找 给定有序表和待查元素 求依次与哪些元素进行比较
将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一维数组A[0..9]中，然后采用二分查找方法查找元素12，被比较过的数组元素的下标依次为 4，7，5 _。 34冒泡排序 每趟需要进行的比较次数，最多进行多少趟 n-1趟 35 快速排序 第一次划分结果
快速排序（Quick Sorting），又称划分排序.是目前所有排序方法中速度最快的一种（从排序区间选取一个元素为基准,从区间两端向中间顺序进行比较和交换,使得前面单元只保留比基准小的元素,后面单元保留比基准大的元素.然后把基准放到前后两部分之间.）
36 各排序算法空间复杂度
排序方法 时间复杂度
平均情况 最坏情况 最好情况
直接插入 O(n2)
空间复杂稳定性 复杂性 度 O(1)
稳定 简单 不稳定 较复杂 稳定 简单
O(n2) O(n)
希尔排序 O(n*n1/2) O(n2) 冒泡排序 O(n2)
O(nlog2n) O(1) O(n)
O(1)
O(n2)
快速排序 O(nlog2n) O(n2) 直接选择 O(n2)
O(nlog2n) O(log2n) 不稳定 较复杂 O(n2)
O(1)
不稳定 简单 不稳定 较复杂 稳定 较复杂 稳定 较复杂
O(n2)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd)
37 二叉排序树的特点
二叉排序树的中序是有序的；左孩子比根小，右孩子大于等于根
38 顺序查找适合的存储结构
顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。
39排序算法时间复杂度 (见36知识点图) 40 双循环链表 （老师忘记出什么样的了） 41 图连通需要的边数
在n个顶点的无向图中，若边数>=n-1，则该图必是连通图。 42 排序的稳定性(见36知识点图)
稳定的有：直接插入 、归并排序、基数排序、冒泡排序 不稳定的有：快速排序、希尔排序、直接选择、堆排序
43 树的性质3
课件：性质3 深度为h的k叉树中至多有(k-1)/(k-1) 结点。
h
满k叉树：结点个数等于(k-1)/(k-1) 的k叉树。
递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。
h
44 二叉树的定义：二叉树为度为2的有序树。
45 二分查找 最多需要比较次数：N个元素最多比较n/2次 46树的深度的定义：树中所有结点层次的最大值，也称高度。
每次调整至少能排除一半的个数(从x到其x-1层,x层得个数应该是所有个数的一半+1),所以复杂度是log级别
比如有32个元素(为了方便取一个2的幂), 第一次排除 ,16,第二次,8,第三次4,... 2,1. 以这种规律排除几次才能完呢?
比如要排除a次,那么 第一次 2^(a-1) ,第二次2^(a-2)... 第三次2^(a-3) ....第a次2^0=1
是不是 总的个数-1= 1+2+4+...2^(a-1) =2^a-1 那么总的个数=2^a 所以: a=log2 (总的个数)
对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_________ 2n ____个，其中_____ n-1__________个用于指向孩子，____________ n+1_____个指针是空闲的。
若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为____2i+1____,右孩子元素为____ 2i+2 ___________，双亲元素为____(i-1)/2________。
6. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。答： ASL=(1*1+2*2+3*4)/7=17/7
2.从一个长度为n的顺序表中删除第i个元素(0≤i≤n-1)时，需向前移动n-i+1个元素。 [ n-i-1 ]
（×）
1．在一个长度为n的顺序表中删除第i个元素时，需向前移动 n－i－1 个元素。插入i位置，移动 n－i个元素。
8．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有
9．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点。
3、顺序查找查找成功时的最坏比较次数为（n-1）和查找失败时的比较次数为（n）。
4、设有64个元素，用折半查找方法进行查找时，最大比较次数是（7），最小比较次数是（1）。
只有非空的广义表的表尾永远是广义表 表头可以是原子也可以是子表
3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（对 ） 一个n个顶点的无向连通图最多有n(n-1) /2 条边，最少有 n-1 条边。
8、用邻接表表示图进行广度优先遍历时，通常是采用（B队列） 来实现算法的。 9、用邻接表表示图进行深度优先遍历时，通常是采用 (A、栈) 来实现算法的。
6.在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率的情况下，查找成功时的平均查找长度为____________。
A n B n/2 C (n+1)/2 D (n-1)/2
9．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 D 。 A、i<n B、2*i<=n C、2*i+1>n D、2*i>n
5.下面程序段的时间复杂度为____________。
int i=1; while (i<=n) i=i*2; A O(n)
14. 对于长度为N的线性表,在最坏情况下,下列各种排序所对应的比较次数中正确的是______________。 A 冒泡顺序为N/2
B 冒泡顺序为N
B O(n1/2) C O(log2n) D O(n2)
C 快速排列为N D 快速排序为N(N+1)/2
.快速排序的时间复杂度为O(log2n) ×
.结点最少的树为只有一个结点的树 ×
.顺序存储的线形表可以随机存取 √
第三篇：数据结构知识点整理
数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。
数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合
数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = {D, R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。
数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。
判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。 算法效率的衡量方法：后期测试，事前估计 算法分析是算法的渐进分析简称
数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):
逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”
线性表的定义：n（ ? 0）个表项的有限序列 L =（a1, a2, …, an） ai是表项，n是表长度。第一个表项是表头，最后一个是表尾。
线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存储方式。一，顺序存储方式，二，链表存储方式。
顺序表的存储表示有2种方式：静态方式和动态方式。
顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。
顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问 。
单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长度可以很方便地进行扩充。
连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表） 特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间
单链表的类定义：多个类表达一个概念(单链表)。分为：链表结点(ListNode)类 ，链表(List)类。
循环链表的概念：是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址，就能遍历表中其他任何一结点。
双向链表的概念：在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LINK指示它的前驱结点，RLINK指示它的后继结点，因此，双向链表的每个结点至少有3个域：1LINK(前驱指针) DADA（数据） RLINK（后继指针）。 栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出。
递归的定义 ：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法一。 定义是递归的二。 数据结构是递归的三问题的解法是递归的。
队列：队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性：先进先出。
优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。
多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。 字符串是 n ( ? 0 ) 个字符的有限序列， 记作S : “c1c2c3…cn”其中，S 是串名字c1c2c3…cn”是串值ci 是串中字符n 是串的长度，n = 0 称为空串。
广义表是 n ( ≥0 ) 个表元素组成的有限序列，记作LS (a1, a2, a3, …, an)，LS 是表名，ai 是表元素，可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n = 0 的广义表为空表。n > 0时，表的第一个表元素称为广义表 的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail
有根树：一棵有根树 T，简称为树，它是n (n≥0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作 T={ 空集 n=0
{r,T1,T2….Tn},n>0
r 是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为 m (m ? 0) 个互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
二叉树的定义:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
完全二叉树 :─ 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树
二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L 遍历根的右子树记作 R。则可能的遍历次序有：前序 VLR 镜像 VRL；中序 LVR 镜像 RVL；后序 LRV 镜像 RLV
前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点 (V)；前序遍历左子树 (L)；前序遍历右子树 (R)。遍历结果- + a * b - c d / e f
树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历 EFBCGDA；对应二叉树中序遍历 EFBCGDA；树的后根遍历结果与其对应二叉树。
表示的中序遍历结果相同：树的后根遍历可以借助对应二叉树的中序遍历算法实现
最小堆和最大堆：如果有一个关键码集合K={K0,K1，K2，K3，….,Kn-1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki≤K2i+1且Ki≤K2i+2(或者Ki≥K2i+1且KiK2i+2 )i=0,1,….[（n-2）/2]，则称这个集合为最小堆或最大堆。
堆是最高效的一种数据结构，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。
堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到，另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。 路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。
路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根结点到达书中每一结点有且仅有一条路径。
Huffman树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树。 带路径长度最小的扩充二叉树不一定是完全二叉树。
集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。
字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。
散列方法：理想的搜索方法是可以不经过比较，一次直接从字典中得到要搜索的元素。如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash()， 使得每个关键码与结构中一个唯一的存储位置相对应：Address ＝ Hash(key)。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。
散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突
搜索就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，应报告一些信息, 如失败标志、位置等 搜索结构通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。实施搜索时有两种不同的环境。静态环境，搜索结构在插入和删除等操作的前后不发生改变。? 静态搜索表 动态环境，为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。? 动态搜索表
顺序搜索主要用于在线性表中搜索。设若表中有 CurrentSize 个元素，则顺序搜索从表的先端开始，顺序用各元素的关键码与给定值 x 进行比较若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。若整个表都已检测完仍未找到关键码与 x 相等的元素，则搜索失败。给出失败信息
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：1每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。2左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3右子树（如果非空）上所有结点的关键码都大于根结点的关键码。4左子树和右子树也是二叉搜索树。
二叉搜索树为二叉排序树如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树
在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为 x 的元素，搜索过程从根结点开始。如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子 二叉搜索树的插入算法：为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。
图定义：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或E = {<x, y> | x, y ? V && Path (x, y)}，是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。 有向图与无向图：在有向图中，顶点对 <x, y> 是有序的。在无向图中，顶点对(x, y)是无序的。
完全图：若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图
在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。
邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标 dest 和指针 link。对于带权图，边结点中还要保存该边的权值cost。顶点表的第 i 个顶点中保存该顶点的数据，以及它对应边链表的头指针adj 最短路径问题：如果从图中某一顶点（称为源点）另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据元素的有限集合。
排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。 插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。
排序