1.7~1.8数算总复习PART1

?

偶数结点就一定是左孩子，奇数结点就一定是右孩子，判断两相邻编号的两节点是否为兄弟，就看他们除以2后的结果是否相同即可?

?

由于先序遍历是“根――左子树――右子树”，而后序遍历是“左子树――右子树――根”，若某二叉树的先序和后序序列正好相反，则该二叉树每层左、右子树只能有1个，即则该二叉树一定是高度等于其结点数。
?如果每层都只有一个结点的话，每层的相对顺序是不变的，变得是访问顺序，

?

运算要N次，然后终止递归要1次，即N+1次?

?

s的值就是等差数列求和?

?

1. 下列叙述中正确的是(D)。
   A）一个逻辑数据结构只能有一种存储结构
   B）数据的逻辑结构属于线性结构，存储结构属于非线性结构
   C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
   D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

?

逻辑结构：结构定义中是对操作对像的数学描述，描述的是数据元素之间的逻辑关系。例如，线性结构，树形结构，图状结构或网状结构。它们都属于逻辑结构。

物理结构：又称存储结构，是数据结构在计算机中的表示（又称映像）。例如，数组，指针。

线性表：属于逻辑结构中的线性结构，它包括顺序表和链表。

顺序表：线性表中的一种，它是用数组来实现的一种线性表，所以它的存储结构（物理结构）是连续的。

链表：线性表中的一种，它的存储结构是用任意一组存储单元来存储数据元素。所以它的存储结构可以是连续的，也可以不是连续的。一般我们说的链表都是不连续的。有一种用数组来表示的链表，叫做静态链表，它的存储结构就是连续的。

数组：一种物理结构，它的存储单元是连续的。
?

?

?

空的判断为队头与队尾重合，满的判断是队尾+1是队头?

?

存储结构，与物理结构类似?

?

?

构造散列函数方法，数字分析法，平方取中法，分段叠加法，伪随机数法，除留余数法?

单链表设置头结点的目的是为了简化运算。

?

?

?

和自己比较也要算一次?

?

?

2,4,,7,12?

?

?

?

?

?

先2，5，ans=7,然后7，7，ans=7+14=21,然后14，9,ans=21+13=44?

?

哈夫曼树的带权路径长度并不等于根节点的数，两者毫无关系，是说在构建的时候就已经往带权路径里加了

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;
int n,num,ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num;
        q.push(num);
    }
    while(q.size()>1){
        int num1=q.top();
        q.pop();
        int num2=q.top();
        q.pop();
        ans+=(num1+num2);
        q.push(num1+num2);
    }
    cout<<ans;
    return 0;
}

?

?

前面的节点，或者比后面的节点都大，或者比后面的节点都小。?

94不满足比91小?

?

?

?

?

对于每棵树，除去根节点那么每个结点上边都有一条边，那么设有x个树，非根节点的数量就有n-x(即所谓非终端结点），所有树的边和为n-x=k,故x=n-k?

?

?

?

第一次遇到39，不匹配，那么后续遇到的所有数应该都比39大；再遇到101，不匹配，那么后续遇到的所有数都比101小；遇到25，不满足条件，所以不是查找路径?

?

?

就是说，对于叶子结点，叶子节点出现的相对次序是固定的，都是最底层后，然后从左到右

就是每层结点出现的相对次序都是固定，不同的遍历方式变化的是每层出现的地点?

?

比如最后一个结点是右子树的某个根节点，这个根节点有左孩子，那么在中序种，这个根节点依旧是最后一个结点，但是在前序种时，就不一定是最后的，而它的左孩子才是最后的?

若前序和中序正好一样，前序为根左右，中序为左根右，后序为左右根所以都没有右节点?

3个结点可以构成5中二叉树，三种形态的二叉树

?N代表数据的总量，FN代表这么多的数据出栈的总可能，然后设是以这N个数里的第N……个数最后出栈，如果最后出栈的是N，那么之前的是出X个，后面会出N-1-X个，乘在一起，就是第I个数最后出栈时的所有可能情况，把他们都加起来就是卡特兰数F(0)=1

F(1)=F(0)F(0)=1,F(2)=F(0)F(1)+F(1)F(0)=2,F(3)=F(0)F(2)+F(1)F(1)+F(2)F(0)=5

F(4)=F(0)F(3)+F(1)F(2)+F(2)F(1)+F(3)F(0)=14

F(5)=F(0)F(4)+F(1)F(3)+F(2)F(2)+F(3)F(1)+F(4)F(0)=28+10+4=42

就是说前面的时候，K数被压入栈底的操作总数，总可能就是F(K-1),即入栈K个元素，K被入栈，但是出栈K-1个，K被保留，接下来是剩下的所有元素，剩下N-K个元素，那么他们进进出出的方式有F(N-K)种，最后退出K，就是一种

由F3=5?

?

首先数组下标不可能是负，所以在插入元素时，应该是先加1再存值，不然的话，如果是先存值再加1，就会使数组越界，即A[0]存栈底元素?

?

?

?

对于二分查找失败，100个结点，构成的完全二叉树，高度为1时，结点总数为1，2时为3，3时为7，N时为2^N-1，N=6时，结点总数为63，为7时总数为127.所以是一个不满树，查找失败时，最少要比较6次，最多比较7次

被删除的位置也要打上标记，不能视为空

森林转二叉树的话，兄弟在右边，孩子在左边

?

V是结点数，E是边数?

?

?

?

加权平均长度，指还要考虑到叶子结点的权重，而不是只计算到叶子结点的路径

n个顶点要树，需要N-1的边，需要减去m-(n-1)=m-n+1条边

?

?

?

?

森林的先序是二叉树的先序，后序是二叉树的中序，由此确定唯一的二叉树?

最小元素一定是最右结点，无右子树，即没有比他还小的元素了，但可能有左子树，即比它大的元素连接在它上；对于A，可能没有孩子或者只有一个孩子；对于C，可能还需要调整；最大元素的话，一定没有左子树，左子树在这个题里意味着比它大，那么最大的元素就不应该有左子树，和B是同理

?

log2n+1是二叉树的高度，是正要填或者刚好填完的高度，最少比较次数为log2n（如果不是满二叉树的话）

?

第K层最多有2^(k-1)个结点，最多共用2^k-1个

?

就是说第六次有叶子节点，并不能确定第六次就是最底层，是要填的层，也可能下一层才是，第六层是被逐渐覆盖的，如果是被填的层，那就是2^5-1+8=39个

如果是被覆盖的，第六层有2^(6-1)=32个结点，那么还有8个叶子节点，说明24个结点已被填到第七层，注意第六层的最后一个非叶子结点可能有一个孩子也可能有两个孩子，要问最多，就视为有两个孩子，即2^6-1+24*2=63+48=111

?

p的右子树结点个数为n

森林转二叉树，孩子变为左节点，兄弟变为右节点?

第一步是把每棵树转为二叉树，就用到了孩子变为左节点，然后就是合并每棵二叉树，就只用兄弟变为右节点；在第一步得到的二叉树种，他们根节点都是没右孩子的?

转换后的二叉树左子树结点个数加根节点个数就是第一颗树的结点个数，即m-n，剩下的就是根节点以及左子树结点数量

就是说，原来n个转后依然n个，多一个是最后的树没有兄弟，所以多一个右指针域为空?

?

简单路径要求所有顶点都不重复，简单回路要求起点与终点以外，都不重复?

注意带队尾指针的循环单链表，尾指针下一个就是首指针，所以可以起到双链表的功效

因为双链表就是可以方便首指针向前找到尾指针?

对哈夫曼树，是一棵完满二叉树（注意完全≠完满），每个结点的度为0或2，且任意一个结点的左孩子权值小于或等于右孩子权值，一个非叶子结点的权值等于其左孩子权值和右孩子权值之和

完满二叉树是说不存在度为1的结点。完全是说能顺序存储，这里的话可能会出现树的权值比叶子结点大，就会产生一棵树是左子树是叶子结点，右子树是树，那就不是完全二叉树了

?

?

?

?

?就是说，如果都是同义词，就会往后叠，然后如果删除的时候，先删除前面的同义词，如果直接标记为空，那么在查找后续的同义词时，就会提前直接标记为失败，不再继续查找了，所以删除就是要打一个删除标记，查找的时候遇到它依然要继续向后查找，但是插入的时候遇到删除标记，就要进行插入了

即所谓截断在它之后填入散列表的同义词结点的查找路径

?

?

注意是或，即包含了两种情况，同义词冲突会占用非同义词的空间，即发生了冲突，还会挤占同义词的空间

?

常见的散列函数有，直接定址法，数字分析法，平均取中法，取余法，折叠法，随机法?

?

就是说先让5个结点构成完全联通图，再随便加一条边即可，注意这里说的是至少，保证

而不是最少需要；当有11条边时，无论怎么放都是联通图

?

?

FN=FN-1+FN-2+1,F1=1,F2=2,F3=4,F4=7,F5=12.F6=20?,所以最大高度是6

?

就是相当于两个人，左右都确定了，然后还剩下4个人，在AB之间全排列

?

?

?

注意是排序树，而不一定是平衡树，所以最坏是斜树，ON，为平衡树时就是LOGN

在这里是认为/比*优先级高，即那个*是在分母里的，而不是对前面的分式结果计算，

就有这样的后缀表达式?

即计算中缀，就是转为后缀，然后计算后缀表达式?

?

?

所谓分支数实际就是入度?

路径实际上就是顶点序列，序列种的元素是起点与源点之间的中间结点

?

?

?

也就是说，这就是直接和最后排序结果进行比较，判断有几个元素处于它最后的实际位置，如果大于等于限制条件的话，就有可能，不然的话就没可能。同样的方法适用于其它每趟都能确定一个最后元素的排序方式（不过他们是在一侧）?

注意存储大小是m+1，然后还要注意头指针与尾指针都是实指

?

选择排序是说每次都选最大/小的放入指定位置，朴素选择排序是每次都遍历一遍数组确定，而堆排序就是通过建堆，每次都能从堆顶直接获取最小的元素来放到最后，所以是选择排序，只是优化了找最小值的过程

2^10=1024,向下取整，然后+1，这个+1就代表那些正在填还没填完的层的部分，即对数结果的小数部分；高度最小是完全二叉树，即logn+1,最大是斜树

?

?

无向图的所有顶点度数和为偶数，有向图不一定?

在数据结构的讨论中把数据结构从逻辑上分为 (C )

A 内部结构与外部结构 B 静态结构与动态结构 C?线性结构与非线性结构 D 紧凑结构与非紧凑结构。

逻辑上分为线性以及非线性的

?

知识点?

数据结构基本概念和算法评价

抽象数据类型（ADT）描述了数据的逻辑结构与抽象运算，通常用三元组（数据对象，数据关系，基本操作集）来表示（或者说包括数据和操作），所以可以定义一个完整的数据结构。

数据结构是一个二元组（D,R），D为数据元素的有限集，R为D上关系的有限集。

抽象数据类型按其值的不同特性可分为：原子类型（int、char）、可变聚合类型（序列，长度可变）、固定聚合类型（复数，两个实数组成，次序确定）。

数据的三个层次：数据、数据元素、数据项，其中数据元素是组成数据的基本单位。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据的逻辑结构独立于存储结构。

同一逻辑结构中的所有数据元素具有相同的特性，这意味着不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致。

数据的存储结构是逻辑结构在计算机中的映射，依赖于计算机语言。

数据结构中有四种基本结构：集合结构、线性结构、树、图。

邻接表不是线性表，邻接表是存储结构，线性表是逻辑结构。

散列存储通过散列函数映射到物理空间，不能反应数据之间的逻辑关系。

线性结构中，存在唯一一个被称作“第一个”的数据元素，除第一个元素外，集合中的每个数据元素均只有一个前驱。

集合是最原始的数据结构。

字典可以采用线性表、散列表、跳表的组织方式。

算法的可行性是指算法中的操作都可以通过已经实现的基本运算执行有限次来实现。

输入、输出不是衡量算法的标准。

算法的时间复杂度不能作为其执行时间的绝对度量。

算法与程序的关系：

算法是代表对问题的解，程序是算法在计算机上特定的实现。
计算机程序是算法实现的手段，但不是唯一手段，密码机也可以实现算法。
一个原地算法是一种使用小的，固定数量的额外之空间来转换资料的算法。

所谓时间复杂度是指在最坏情况下，估算算法执行时间的一个上界。

同一个算法，执行效率与语言级别无关。

算法的时间复杂度取决于待处理数据的状态和问题的规模。

递归定义的数据结构（列表、树）通常用递归算法来实现对它的操作。

理论上讲，所有的递归都可以换成非递归。

数据的高位放在低地址，低位放在高地址为大端模式。

线性表

数组是不能频繁进行插入和删除操作的结构。

顺序表中，在逻辑上相邻的元素在物理位置上也相邻。

假设线性表有n个元素，当想要交换表中两个元素时，顺序表比链表效率高，顺序表需要3次交换操作，而链表需要找到两个元素的前驱。当想要顺序输出这n个元素时，顺序表和链表的效率一样，都是O(n)。

链式存储用指针表示逻辑结构，而指针的设置是任意的，故可以很方便地表示各种逻辑结构。

顺序存储方式不仅适用于存储线性结构，同样适用于树和图等非线性结构。

顺序存储方式并不用于各种逻辑结构的存储表示。

某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度可能是 0 或 1。

已知链表的存储空间不需要动态分配（静态链表），未知或变化的链表的存储空间才需要动态分配（单链表、线性链表）。

需要分配较大的空间，插入和删除不需要移动元素的线性表的存储结构是静态链表，单链表不行，因为单链表的存储空间是动态分配的。

单链表头指针为head，没有头结点，判空条件为head==0.

静态链表中指针表示的是下一元素在数组中的位置。

数据结构中不存在基本运算，比如多维数组没有插入、删除操作，栈和队列不需要查找。

原地逆序操作中，数组比链表速度更快。

返回头部结点，数组和链表一样快。

线性表 <= 纯表（树）<= 再入表（兄弟结点之间有连线） <= 递归表（图）

注意头指针≠头结点，头结点就是一个空的结点，不存储元素

链表并不是每个结点中都恰好包含一个指针。

栈和队列

采用非递归方式重写递归程序时不一定需要使用栈，例如计算斐波那契数列只需要循环即可实现。

在用单链表实现队列时，队头设在链表的链头位置，为了方便删除队头元素。

栈是一种特殊的线性结构，要求限定在表尾进行插入删除操作，

链队、循环队列等数据结构要注意队列最多能存储几个元素，M个还是M-1个。

栈的应用：表达式求值，括号匹配，递归，进制转换，迷宫求解，xml校验节点是否闭合。

队列的应用：层次遍历，打印缓冲区，CPU资源竞争，广度有限搜索，页面替换算法。

?

这个结点有左孩子时，如果它的中序前驱还有右孩子，那就不会访问到这个结点，所以它的中序前驱一定没有右孩子?

图

概念复习：弧、简单图、多重图、完全图、有向完全图、连通图、非连通图、极大/小连通子图、连通分量、强连通图、极大强连通子图、强连通分量、生成树、生成森林。

图是由顶点和相邻顶点序偶构成的边所形成的的序列。

完全图分为有向完全图和无向完全图。

图的遍历要注意两点：1.每个顶点只访问一次 2.图中各点可能不连通

强连通有向图的任何顶点到其他所有顶点都有路径，但是未必有弧。

回路对应于路径，简单回路对应于简单路径。

若一个有向图的邻接矩阵的对角线以下的元素为0，则该图的拓扑序列必定存在。

连通分量是无向图的极大连通子图，需要将依附于连通分量中的顶点的所有边都加上，所以连通分量中可能存在回路，不能作为图的生成树，图的生成树是图的极小连通子图。

无向图中有权值相同的边，其生成树也不一定不唯一，因为这个图可能本身就是一棵树。

最短路径一定是简单路径。

Dijkstra算法适合求解有回路的带权图的最短路径，也可以求解任意两个顶点的最短路径，不适合求带负权值的最短路径。

判断有向图是否有环的方法：

深度优先遍历：在向深度查找的过程中，如果存在一个顶点有一条边指向已经遍历过的顶点，且这个顶点不是上一步访问过的顶点，则存在环。
拓扑排序：遍历过程中，图中还有顶点，但是无法找到下一个可以加入拓扑序列的顶点，说明存在回路。
并查集只能判断无向图是否存在环，无法判断有向图是否存在环。
在拓扑排序中为暂存入度为0的顶点，可以使用栈，也可以使用队列。

一个有向图的顶点不能排成一个拓扑序列，则代表图中有顶点数量大于1 的回路，该回路构成一个强连通分量。

强连通图是针对有向图的，n个点强连通图至少n条边（形成回路），至多n（n-1）条边。

有向图的连通包括强连通、弱连通、多侧连通。

在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

AOE网络中，加速某一关键活动不一定会使工程提前完成，但是延迟任意关键活动一定会使工程延期。

AOE网络中，可能同时存在几条关键路径，所有关键路径通过的有向边称为桥。

图中各个定点的编号是人为的，可以根据需要进行改变。

在无向图中定义定义顶点vi和vj之间的路径为从vi到vj的一个顶点序列。

图可以没有边 但不能没有顶点。

当边权值都相等时，BFS算法可用于解决单源最短路径问题。

在任何图中必定有偶数个度数为奇数的结点。

查找

静态查找不涉及插入和删除操作，动态查找设计插入和删除操作，所以两种查找方式的根本区别是施加的操作不同。

即折半查找是严格的二叉平衡搜索树?

长度为16的有序顺序表，使用折半查找不存在的元素，最多比较5次。

log16+1=5,完全二叉树树高为5，最坏为5，至少要4

B+树支持顺序查找和随机查找，B树仅支持随机查找，且B树和B+树都可以作为文件索引结构。

B+树是应文件系统所需而产生的B树的变形，前者比后者更加适用于实际应用中的操作系统文件索引和数据库文件索引，前者的磁盘读写代价更低，查询效率更加稳定。

编译器中的词法分析使用有穷自动机和语法树。

网络中的路由表快速查找主要依靠高速缓存，路由表压缩技术和快速查找算法。

系统一般使用空闲空间链表管理磁盘空闲块。

在开放定址法中散列到同一个地址而引起的“堆积”问题是由于同义词之间或非同义词之间发生冲突引起的。

使用开放定址法处理散列表的冲突时，其平均查找长度高于链接法，或者说开散列法比闭散列法效率高。

在散列法中采取开散列法解决冲突时，其装载因子的取值可以大于1。

三阶B树一定是平衡的三路搜索树，但是三路搜索树不一定是三阶B树。

在一棵B树中所有叶结点都在同一层上，所有叶结点中空指针数等于所有关键码总数+1。（类似于满n叉树中的非叶结点数+1=叶结点数）。

使用再散列法处理冲突时不易产生聚集。

同义词冲突不等于聚集，链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象。

采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是解决冲突的方法选择不当。

Hash操作能够根据散列值直接定位数据的存储地址，设计良好的Hash表能够在常数级时间下找到需要的数据，更适合于内存中的查找。

STL_Map的内部实现是一棵红黑树，在内存中建立，不能用于磁盘操作，查找性能版不如Hash查找。

B树的插入过程中，若根节点发生分裂，则树高一定+1。

内部排序

通常，取大量数据中的k个最大\最小元素时，优先使用堆排序。

对10TB的数据文件进行排序，应该使用归并方法进行排序。

在内部排序时，没有选择插入排序而是选择归并排序，则可能的理由是：归并排序的运行效率更高。

基数排序不能对float和double类型的实数进行排序。

希尔排序和堆排序都使用了顺序存储随机访问的特性，若将顺序存储更换为链式存储，算法的时间效率会降低。

对大部分元素已有序的数组进行排序，直接插入排序（最坏O(n)）比简单选择排序（最坏O（n2））的效率更高，是因为直接插入排序过程中元素之间的比较次数少。

快速排序在被排序数据完全无序的时候最易发挥长处，在数据基本有序的情况下，会退化为冒泡排序。

折半插入排序方法在排序过程中比较次数的是固定的，与初始排列无关。?

不稳定的排序算法：快、选、堆、希。

增加归并路数，可以减少归并趟数，进而减少读写磁盘的次数，提高外部排序速度。
?

?

?