下载文档原格式
数据结构考研笔记整理(全)数据结构考研笔记整理数据结构是计算机科学中非常重要的一门课程，对于计算机专业的学生来说，考研复习过程中对数据结构的准备非常关键。
因此，我们需要系统地整理数据结构的相关知识点，以便更好地理解和掌握。
一、线性表线性表是数据结构中最基本的一种数据结构，它是一种有序的数据元素的集合。
常见的线性表有顺序表和链表。
1. 顺序表顺序表是将数据元素存放在一块连续的存储空间中，通过元素的下标来访问。
具有随机访问的特点，但插入和删除操作比较麻烦。
适用于查找操作频繁的场景。
2. 链表链表是将数据元素存放在任意的存储空间中，通过指针来连接各个元素。
具有插入和删除操作方便的特点，但不支持随机访问。
适用于插入和删除操作频繁的场景。
二、栈和队列栈和队列是特殊的线性表，它们都具有先进先出的特点。
1. 栈栈是一种特殊的线性表，只能在表的一端进行插入和删除操作，即“先进后出”。
常见的应用有函数调用的过程中的参数传递、表达式求值等。
2. 队列队列也是一种特殊的线性表，只能在表的一端进行插入操作，而在另一端进行删除操作，即“先进先出”。
常见的应用有任务调度、缓冲区管理等。
三、树树是一种非常重要的非线性数据结构，它由节点和边组成。
树具有层次结构，常见的树结构有二叉树、二叉搜索树和平衡二叉树等。
1. 二叉树二叉树是每个节点最多有两个子树的树结构，包括左子树和右子树。
二叉树的遍历方式有前序遍历、中序遍历和后序遍历。
2. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。
具有快速查找和插入的特点。
3. 平衡二叉树平衡二叉树是一种特殊的二叉搜索树，它的左右子树的高度差不超过1。
通过旋转操作可以保持树的平衡性。
四、图图是一种非常复杂的非线性数据结构，它由顶点和边组成。
图可以分为有向图和无向图，常见的图算法有深度优先搜索和广度优先搜索。
1. 深度优先搜索深度优先搜索是一种用于遍历或搜索图和树的算法，它从一个节点开始，尽可能深地访问每个节点的所有子节点，直到没有子节点为止。
计算机考研数据结构的复习要点计算机考研数据结构的复习要点考生们在进行计算机考研的复习阶段时，需要把数据结构的复习要点了解清楚。
店铺为大家精心准备了计算机考研数据结构的复习重点，欢迎大家前来阅读。
计算机考研数据结构重点：二叉树二叉树是数据结构中的重点内容，在这两年的考试中也将二叉树作为重点内容来考查。
二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林和二叉树的转换等内容。
算法的重点是二叉树的遍历及其应用，这也是二叉树这部分的重点和难点。
遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作。
例如：求二叉树结点总数，建立二叉树，建立二叉树的存储结构等。
二叉树的很多算法是在遍历算法基础上改造完成的，这就要求大家在复习时，熟练掌握二叉树遍历的递归和非递归算法。
下面为大家介绍一下二叉树的几种遍历方法：由二叉树的定义可知，一颗二叉树由根节点及左、右子树三个基本部分组成，因此，只要依次遍历这三部分，就可以遍历整个二叉树。
1.先序遍历先序遍历的递归过程为：若二叉树为空，遍历结束。
(1)访问根节点;(2)先序遍历根节点的左子树;(3)先序遍历根节点的右子树。
2.中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束。
否则，(1)中序遍历根节点的左子树;(2)访问根节点;(3)中序遍历根节点的右子树。
3.后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。
否则，同济大学四平路(1)后序遍历根节点的左子树;(2)后序遍历根节点的右子树;(3)访问根节点。
层次遍历二叉树的层次遍历，是指从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。
因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：(1)访问该元素所指结点;(2)若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
数据结构考研复习重点归纳数据结构是计算机科学中非常重要的一门基础课程，考研复习数据结构时，需要重点掌握的内容有以下几个方面。
1.线性表：线性表是数据结构中最基本的一种结构，常见的线性表有数组、链表和栈等。
考生需要掌握线性表的定义、插入、删除、查找等基本操作，并能够分析它们的时间复杂度。
2.树：树是一种非常重要且常见的数据结构，它具有分层结构和层次关系。
其中，二叉树是最简单也是最基本的一种树结构，树的遍历（如前序遍历、中序遍历和后序遍历）是树算法中的重要内容。
此外，还要了解一些特殊的树结构，如平衡树和B树等。
3.图：图是由节点和边组成的一种数据结构，它是一种非常灵活的结构，常用来表示各种实际问题中的关系。
在考研复习中，需要掌握图的基本概念（如顶点和边）、图的存储结构（如邻接矩阵和邻接表）以及图的遍历算法（如深度优先和广度优先）等。
4.查找和排序：在实际问题中，经常需要查找和排序数据。
查找算法（如顺序查找、二分查找和哈希查找）和排序算法（如冒泡排序、插入排序和快速排序）是数据结构中常见的算法，考生需要熟练掌握这些算法的原理和实现方法。
此外，还要了解一些高级的查找和排序算法，如二叉查找树和归并排序等。
5.散列表：散列表（也称哈希表）是一种特殊的数据结构，它利用散列函数将数据映射到一个固定大小的数组中。
散列表具有快速的查找和插入操作，常用于实现字典和数据库等应用。
在考研复习中，需要了解散列表的原理和实现方法，以及处理冲突的方法，如链地址法和开放地址法。
6.动态规划：动态规划是一种解决问题的数学方法，也是一种重要的算法思想。
在考研复习中，需要掌握动态规划的基本原理和解题思路，以及常见的动态规划算法，如背包问题和最长公共子序列等。
7.算法复杂度分析：在考研复习中，需要有一定的算法分析能力，能够对算法的时间复杂度和空间复杂度进行分析和估算。
此外，还要能够比较不同算法的效率，并选择合适的算法来解决实际问题。
除了以上重点内容，考生还要注意掌握一些基本的编程知识，如指针、递归和动态内存分配等。
《数据结构》复习重点知识点归纳一．数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。
所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。
但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
·线性表：基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题，如果有，也是与其它章节内容相结合。
·栈和队列：基础章节，容易出基本概念题，必考内容之一。
而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
·串：基础章节，概念较为简单。
专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。
一般如果要出题，多数不会作为大题出。
数组常与“查找，排序”等章节结合来作为大题考查。
·树和二叉树：重点难点章节，各校必考章节。
各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。
通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
·图：重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。
出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。
考研题型包括：简答题；方法选择（分析）；构造题；算法题。
第一章绪论1. 数据结构的基本概念：数据、数据元素、数据对象、数据结构2. 抽象数据类型：数据对象、逻辑关系、一组操作。
ADT的特点：数据抽象、信息隐蔽3. 数据结构三要素：数据元素间的逻辑关系、物理存储和一组操作。
元素间的逻辑关系：集合、线性、树、图元素在计算机内存中的存储结构：顺序、非顺序4. 算法的定义：规则的有限集合，为了解决某个特定问题而规定的一系列基本操作。
算法特性：有限性、确定性、可行性、输入、输出算法设计目标：正确性、可读性、鲁棒性、高效率低存储5. 算法性能评价：时间和空间算法时间复杂度：T(n)=O(f(n))。
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。
其中f(n)是问题规模n的某个函数。
求解算法的时间复杂度的具体步骤是：⑴找出算法中的基本语句；⑵计算基本语句的执行次数的数量级；保留基本语句执行次数的函数中的最高次幂，忽略所有低次幂和最高次幂的系数。
⑶用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < { O(2^n) < O(n!) < O(n^n) }【例】分析下面各算法的时间复杂度算法1：int fact(int n){ if (n<=1) return 1;return n*fact(n-1);}算法2：i=l;while (i<n){for(j=l;j<=n;j++)x=x+l;i=i*2;}算法3：for(i=l;i<=n;i++){ j=l;while (j<=i){x+=l; j++;}}算法:4void sort(int b[]，int n){ int i, j, k;for (i=0; i<n-1; i++){ k = i;for (j=i+1; j<n; j++)if (b[k] > b[j]) k = j;x = b[i]; b[i] = b[k]; b[k] = x;}}算法5void add(int n){ int i = 0, s = 0;while (s<n){ i++;s = s + i;}}设while循环语句执行次数为T(n),则算法6void hanoi(int n, char a, char b, char c){ if (n==1) printf("move %d disk from %c to %c \n", n, a, c);else{ hanoi(n-1, a, c, b);printf("move %d disk from %c to %c \n", n, a, c);hanoi(n-1, b, a, c);}}算法7：void PreOrder(BiTree T){ if (T){ v isit(T->daata)PreOrder(T->lchild);PreOrder(T->rchild);}}算法空间复杂度：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
数据结构考研知识点总结数据结构是计算机科学中一门重要的课程，其是计算机科学的核心基础之一、在考研中，数据结构也是一个必考的科目，对于应试者来说，掌握数据结构的知识点是非常重要的。
下面是对数据结构考研知识点的总结。
1.数据结构的基本概念和分类。
数据结构是指一组数据的存储方式和相应的操作方法。
常见的数据结构包括线性结构、树形结构、图结构等。
线性结构包括数组、链表、栈、队列等；树形结构包括二叉树、堆、哈希树等；图结构包括有向图、无向图等。
2.线性结构。
线性结构是数据元素之间存在一对一的关系的数据结构。
常用的线性结构有数组、链表、栈和队列。
-数组是一种连续存储的线性结构，可以通过下标直接访问元素。
-链表是一种离散存储的线性结构，有单向链表、双向链表和循环链表等。
-栈是一种特殊的线性结构，只能在一端进行插入和删除操作，遵循后进先出（LIFO）的原则。
-队列也是一种特殊的线性结构，只能在一端进行插入操作，另一端进行删除操作，遵循先进先出（FIFO）的原则。
3.树形结构。
树形结构是一种非线性的数据结构，具有层次关系的集合。
常用的树形结构包括二叉树、AVL树、B树和哈夫曼树等。
-二叉树是一种每个节点最多有两个子节点的树形结构，包括满二叉树、完全二叉树和二叉树等。
-AVL树是一种自平衡的二叉树，通过维护平衡因子来保证树的平衡。
-B树是一种多路平衡查找树，用于大规模数据存储和文件系统等。
-哈夫曼树是一种用于数据压缩的最优二叉树。
4.图结构。
图结构是由顶点和边组成的一种数据结构。
常用的图结构包括有向图、无向图、带权图和图的遍历等。
-有向图是边有方向的图结构，边具有指向关系。
-无向图是边无方向的图结构，边没有指向关系。
-带权图是边具有权值的图结构。
-图的遍历有深度优先（DFS）和广度优先（BFS）两种常见方法。
5.排序算法。
排序算法是数据结构中重要的应用之一、常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序等。
考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。
最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。
计算机科学考研备考攻略常见算法与数据结构解析计算机科学考研备考是许多计算机专业学生努力的目标。
在备考过程中，算法与数据结构是必不可少的重要内容。
本文将对常见算法与数据结构进行解析，帮助考生更好地备考。
一、算法解析算法作为计算机科学的核心内容，主要包括排序算法、查找算法、图算法等。
下面将对其中几种常见的算法进行解析。
1. 排序算法排序算法是指将一组无序的数据按照特定规则进行排列的方法。
常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序等。
以下分别对这几种算法进行简要解析。
（1）冒泡排序：通过重复地交换相邻两个元素的位置，使得最大的元素逐渐移动到待排序列的最后位置。
（2）插入排序：将待排序数据逐个插入到已经排好序的序列中，直到所有数据都插入完毕。
（3）选择排序：通过在未排序序列中选择最小（或最大）的元素放到已排序列的末尾，不断重复这一过程。
（4）快速排序：通过选定一个基准值，将数组划分为左右两个子数组，左边的子数组都小于基准值，右边的子数组都大于基准值，再对子数组进行递归排序。
2. 查找算法查找算法是在一组数据中寻找指定元素的过程。
常见的查找算法包括线性查找、二分查找等。
以下对这几种算法进行简要解析。
（1）线性查找：从头到尾依次遍历数据，直到找到目标元素或遍历完所有元素。
（2）二分查找：对于有序的数据集合，首先取中间元素，如果中间元素等于目标元素，则查找成功，否则根据中间元素和目标元素的大小关系，在左半部分或右半部分继续查找。
3. 图算法图算法主要用于解决图相关的问题，如最短路径、最小生成树等。
常见的图算法包括深度优先搜索、广度优先搜索、Dijkstra算法等。
以下分别对这几种算法进行简要解析。
（1）深度优先搜索：从起始节点开始，沿着一条路径一直搜索至最深处，直到无法继续为止，然后回溯到上一节点，再继续搜索其他路径。
（2）广度优先搜索：从起始节点开始，逐层扩展搜索范围，直到找到目标节点或搜索完所有节点。
数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。
1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/ 2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图 G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。
1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。
设置两个新的集合U 和T，其中集合U（顶点集）用于存放G 的最小生成树中的顶点，集合T （边集合）存放G 的最小生成树中的边。
T ，U的初始状态：令集合U 的初值为U＝{u1}（假设构造最小生成树时，从顶点u1 出发），集合T 的初值为T＝{}。
Prim 算法的思想是：从所有u∈U，v∈V－U 的边中，选取具有最小权值的边（u，v）∈E，将顶点v 加入集合U 中，将边（u，v）加入集合T 中，如此不断重复，直到U＝V 时，最小生成树构造完毕，这时集合T 中包含了最小生成树的所有边。
Prim 算法可用下述过程描述，其中用wuv 表示顶点u 与顶点v 边上的权值。
（1）U＝{u1},T={};（2）while (U≠V)do(u，v)＝min{wuv；u∈U，v∈V－U }T＝T＋{(u，v)}U＝U＋{v}（3）结束。
按照Prim 方法，从顶点1 出发，该网的最小生成树的产生过程如图：为实现Prim 算法，需设置两个辅助closedge，用来保存U到集合V－U 的各个顶点中具有最小权值的边的权值。
对每个Vi∈（V-U ）在辅助数组中存在一个相应的分量closedge[i -1],它包括两个域：typedef struct ArcNode{int adjvex; //adjex域存储该边依附的在U中的顶点VrType lowcost; //lowcost域存储该边上的权重}closedge[MAX_VERTEX_NUM];显然：初始状态时，U＝{v1}(u1 为出发的顶点),则到V-U 中各项中最小的边，即依附顶点v1的各条边中，找到一条代价最小的边（u0，v0）= （1，3）为生成树上一条边。
同时将v0（=v3）并入集合U中。
然后修改辅助数组的值。
1）将closedge[2].lowcost = 0；//表示顶点V3三已经并入U2) 由于边（v2,v3）的权值小于closedge[1].lowcost，故需修改closedge[1]为边（v2,v 3）及其权值，同理修改closedge[4]，closedge[5].closedge[1].adjvex = 3.closedge[1].lowcost = 5.closedge[4].adjvex = 1.closedge[4].lowcost = 5.closedge[5].adjvex = 3.closedge[5].lowcost = 6.以此类推，直至U = V;下图给出了在用上述算法构造网图7.16的最小生成树的过程中：Prim 算法实现：按照算法框架:（1）U＝{u1},T={};（2）while (U≠V)do(u，v)＝min{wuv；u∈U，v∈V－U }T＝T＋{(u，v)}U＝U＋{v}（3）结束。
当无向网采用二维数组存储的邻接矩阵存储时，Prim 算法的C 语言实现为：假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。
其中有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1；其二是重新选择具有最小代价的边，其频度为n。
由此，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。
2.克鲁斯卡尔（Kruskal） :由点到线，适合边稀疏的网。
时间复杂度：O(e * loge) Kruskal 算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。
基本思想是：1) 设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。
2) 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量，则将此边加入到T中，否则舍弃此边而选择下一条边（若该边依附的两个顶点属于同一个连通分量，则舍去此边，以免造成回路）。
依此类推，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
按照Kruskal 方法构造最小生成树的过程如图所示：在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。
依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
Kruskal 算法的实现：算法的框架：构造非连通图T＝（V，{}）k = i= 0；//k为边数while（k《< n-1） {i++;检查边E中第i条边的权值最小边（u，v）若（u，v）加入T不是T产生回路，则（u，v）加入T，且k++}c语言实现：C 语言实现Kruskal 算法，其中函数Find 的作用是寻找图中顶点所在树的根结点在数组f ather 中的序号。
需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。
2. AOV网与拓扑排序：由偏序定义得到拓扑有序的操作便是拓扑排序。
建立模型是A OV网2. 1．AOV网(Activity on vertex network)所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。
若以图中的顶点来表示活动，有向边（弧）表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV 网（Activity On Vertex Network）。
在AOV 网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j 是顶点i的后继。
若< i,j>是图中的弧，则称顶点i是顶点j 的直接前驱，顶点j 是顶点i 的直接后驱。
AOV 网中的弧表示了活动之间存在的制约关系。
例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。
学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。
这些课程的名称与相应代号如表所示。
课程之间的优先关系图：该图的拓扑有序系列：注意：在AOV-网中不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。
若设计出这样的流程图，工程便无法进行。
而对程序的数据流图来说，则表明存在一个死循环。
因此，对给定的AOV-网应首先判定网中是否存在环。
检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。
2.2．拓扑排序离散数学基础知识：首先复习一下离散数学中的偏序集合与全序集合两个概念。
若集合A 中的二元关系R 是自反的、非对称的和传递的，则R 是A 上的偏序关系。
集合A 与关系R 一起称为一个偏序集合。
若R 是集合A 上的一个偏序关系，如果对每个a、b∈A 必有aRb 或bRa ，则R 是A上的全序关系。
集合A 与关系R 一起称为一个全序集合。
直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
[例如]，图7.25所示的两个有向图，图中弧(x,y)表示x≤y，则(a)表示偏序，(b)表示全序。
若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(Topological Order)，而由偏序定义得到拓扑有序的操作便是拓扑排序。
2.3 拓扑排序算法对AOV 网进行拓扑排序的方法和步骤是：1、从AOV 网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；2、从网中删去该顶点，并且删去从该顶点发出的全部有向边；3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。
这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路；另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。
以下图(a)中的有向图为例，图中v1，和v6没有前驱，则可任选一个。
假设先输出v6, 在删除v6及弧<v6，v4>，<v6，v5>之后，只有顶点v1没有前驱，则输出vl且删去vl及弧< v1，v2>、<v1，v3>和<v1, v4>，之后v3和v4都没有前驱。
依次类推，可从中任选一个继续进行。
最后得到该有向图的拓扑有序序列为：v6 - v1 - v4 - v3 - v2 - v5图AOV-网及其拓扑有序序列产生的过程(a)AOV-网；(b)输出v6之后；(c)输出v1之后；(d)输出v4之后；(e)输出v3之后；(f)输出v2之后为了实现上述算法，对AOV 网采用邻接表存储方式，并且邻接表中顶点结点中增加一个记录顶点入度的数据域，即顶点结构设为：顶点表结点结构的描述改为：typedef struct vnode{ /*顶点表结点*/int count /*存放顶点入度*/VertexType vertex; /*顶点域*/EdgeNode * firstedge; /*边表头指针*/}VertexNode;当然也可以不增设入度域，而另外设一个一维数组来存放每一个结点的入度。
