数据三要素----数据的：逻辑结构，存储结构，运算 时间复杂度C将算法中基本运算的执行次数的数量级作为时间复杂度。

顺序表有哪些缺点？（逻辑上相邻的元素，在物理位置上也相邻） 优点：顺序表支持随机存取，存储密度大 缺点：插入和删除元素需要移动大量的元素（近一半） 注意：动态分配内存并不是链式存储结构，依然属于顺序存储结构，支持随机存取方式，只是分配的空间大小在运行时动态决定。

链表有哪些缺点？（逻辑上相邻的元素，在物理位置上不一定相邻） 优点：便于插入删除等操作，只要改变指针就行。不用考虑溢出问题。 缺点：不支持随机存取，查找第i个元素只能从链表的第一个结点出发。

静态链表的数据结构？ 答：静态链表是连续存储在一段主存空间上的，它的每个节点除了数据域外，还有一个指针域用来指向下个节点在这个数组的位置。

循环链表的特点 单循环链表：最后一个结点的next指针指向头结点； 双循环链表：最后一个结点的rear指针指向头结点，头结点的front指针指向最后一个结点。 如何逆置一个链表 答：定义一个只含有头结点的链表，依次取下要逆置的链表的各个元素，每次按照头插法插入刚定义的链表中，直到待逆置链表中所有关键字都被插入。最后将待逆置链表的头指针指向新定义的链表的头结点，并将头指针的地址返回出去。

对链表设置头节点的好处是什么? (1)无论链表是否为空，其头指针是指向头结点的非空指针，故空表与非空表的操作也就统一了。 (2)在链表第一个位置的插入与删除操作与其他位置的操作一致，无需特殊处理。

我们几个人围成一圈，从某个人开始数数，数到3的人OUT，说一下这个算法？ 答：这个可以用循环链表实现。 两个有序的链表A，B。如何把B的节点插入A链表，使之仍是有序的表？ 答：依次取B链表的节点，与A链表的节点的关键字比较，找到合适的位置插入即可。 你是说每次都从A链表第一个位置开始比较？ 答：可以设置一个指针，指向A链表中刚插入元素的位置，以后直接从刚插入位置从前往后查找合适的位置插入即，直到B链所有元素插入到A链中。

两个有序数组拼接为有序数组最少和最多比较几次？ 当某个数组的最大元素比另一个数组最小元素小（某个数组的最小元素比另一个数组的最大元素大）时只需要比较一次，即最少比较一次。最多比较两个数组长度中较小值次。min(len a,len b)。

什么是堆？什么是栈？什么是队列？有何区别？举一个队列的例子 队列：只允许在队头删除，在队尾插入的顺序表，队列先进先出eg:排队买饭 栈：只允许在栈顶插入和删除的顺序表，栈后进先出。 堆：堆分为小根堆和大根堆。（1）每个结点都小于它的左右孩子的值―小根堆；（2）每个结点都大于它的左右孩子的值―大根堆；堆又称为优先队列。 循环队列C可以解决假溢出 循环队列：牺牲一个存储单元来区分队空和队满，队空：front指针等于rear指针时；队满：（队尾指针+1）余队列长度等于队头指针；

双端队列C指两端都可以进行入队和出队操作的队列。 受限双端队列C输入受限的双端队列，输出受限的双端队列 输入受限的双端队列：允许在一段进行入队出队，另一端只允许出队操作。 数出受限的双端队列：允许在一段进行入队出队，另一端只允许入队操作。

栈的用法 答：栈的应用有：括号匹配、表达式求值、递归调用、数值转换 括号匹配： （1）若为左括号则入栈，若为右括号则检查与栈顶元素是否匹配，匹配则将栈顶元素出栈，栈顶指针下移一位。 （2）按照这个规则，一直检查到字符串尾部。 （3）检查栈是否为空，栈空，则这个括号串匹配成功，否则匹配失败。

表达式求值： （1）中缀―>后缀 （2）从左到右扫描表达式：遇到数字就进栈，遇到符号则将栈顶的两个元素出栈并运算，将结果压回栈中，直到最后得到表达式的结果。

递归函数？ 递归调用： （1）如果一个函数运行过程中又运用到自身，那么这个函数称为是递归定义的。―递归函数中有：递归式，递归边界。可以用栈来实现递归。 （2）递归思想就是把大问题分解成小问题，直到每个小问题都得到解决为止。（1）递归次数有限；（2）有结束条件终止递归； （3）规模为n的问题可划分为若干结构相同，规模较小的子问题。 队列的应用C树的层次遍历，图的广度优先搜索，基数排序，OS里的缓冲区，就绪队列，阻塞队列等。

矩阵压缩：对多个相同的值，只分配一个存储空间；对零元素不分配空间。压缩存储可将二维矩阵存到一维数组中，对二维数组有行优先、列优先两种存储方式。对特殊矩阵只存储一部分元素。―对称矩阵，上下三角，对角矩阵。

稀疏矩阵？ 答：如果在矩阵中，多数的元素为0，通常认为:非零元素 / 矩阵所有元素<=0.05，则称此矩阵为稀疏矩阵（sparse matrix）。

树的性质 （1）除根结点外，每个结点都有一条边指向，一条边对应一个度，故结点总数等于总度数加1。 （2）度为m的树中，第i层最多有m^(i-1)个结点。

特殊的二叉树―满二叉树，完全二叉树 满二叉树：即每一层的结点都达到最大值，高度为h的树，有2^h -1个结点。 完全二叉树：高度为h的完全二叉树中，每个结点都与高度为h的满二叉树的编号一一对应。

完全二叉树的性质： （1）叶子结点只可能出现在层数最大的两层上； （2）如果有度为1的结点，则该结点只有左孩子，而无右孩子； （3）一旦出现某个结点为叶子结点，或只有左孩子，则编号大于该结点的均为叶子结点。

知道一棵树的先序和后序能不能确定它?要证明. 答：不能，必须知道中序。这是因为前序遍历和后序遍历序列，可能对应不同的二叉树。 可确定一棵树：（先中、中后、中层）

在后序遍历的线索二叉树中，如何找结点直接前驱？ 先把二叉树遍历一遍：即设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。 建一个队列，按照后序遍历方式将各个结点进行入队，如果Ltag=1（Rtag=1），此时把左（右）孩子指针指回队列里的前（后）一个元素，这个元素就是前驱（后继）节点，然后往队尾依次进行线索化。

在中序线索二叉树中，如何找节点的直接前驱？ 建一个队列，按照中序遍历方式将各个结点进行入队，如果Ltag=1，此时把左孩子指针回指队列里的前一个元素，这个元素就是前驱节点，然后往队尾依次进行线索化。

如何在计算机上实现线索二叉树的遍历？ 遍历的总体思路： 先找到最左边的节点，然后判断其右子树是否为线索，如果是线索，那么就遍历它，如果右子树是右孩子，那么就进入到右孩子最左边的节点，进行同样的判断，知道遍历完了整棵树为止。 线索二叉树 在二叉树中希望很快找到某一节点的前驱或后继，但不希望每次都要对二叉树遍历一遍，因此在创建二叉树的过程中，需要将每个结点的前驱和后继记录下来。 为了区分：左指针指向的是左孩子结点还是前驱结点，右指针指向的是右孩子结点还是后继结点，所以增加了两个线索标志位来区分这两种情况： ltag = 0；指向结点的左孩子 ltag = 1；指向结点的前驱 Rtag = 0；指向结点的右孩子 Rtag = 1；指向结点的后继 结点中指向前驱和后继结点的指针称为线索，加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式使其变为线索二叉树的过程称为线索化。

树是否可以用顺序存储？ 是否可以链式存储？ 顺序存储：树的双亲表示法。采用一组连续空间来存储各个结点，同时在每个节点中增设一个指针域，用来指示其双亲结点在数组中的位置。 链式存储： 1.孩子表示法：即邻接表存储结构 2.孩子兄弟表示法：数据结构： （1）指向结点第一个孩子的指针 （2）结点值 （3）指向结点下一个兄弟结点的指针

树的遍历种类，确定一棵树的方法？ 树的遍历种类:先序遍历和后序遍历 树的先序对应二叉树的先序，树的后序对应二叉树的中序。 确定一棵二叉树：（先中）、（中后）、（中层）

树转二叉树（孩子兄弟表示法）： 每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻兄弟结点。 二叉树转森林：依次断开二叉树的右孩树，直到产生一棵没有右子树的二叉树为止，就得到了原森林。

二叉排序树： （1）若左子树非空，则左子树上所有结点的关键字值均小于根节点关键字值； （2）若右子树非空，则右子树上所有结点的关键字值均大于根节点关键字值； （3）左右子树本身也是一棵二叉排序树。 二叉排序树的查找―与折半查找类似----折半查找判定树为一棵二叉排序树 （1）从根节点出发，将给定值与根节点比较，若相等则查找成功。 （2）待查找的关键字大于根节点，在右子树查找； （3）待查找的关键字小于根节点，在左子树查找； 平衡二叉树（左右子树高度差 ≤ 1，平衡因子的绝对值 ≤ 1） 插入结点失衡：LL（右单旋）,RR（左单旋）.LR（左右双旋）,RL（右左双旋） 说一说哈夫曼树？ 哈夫曼树是带权路径长度之和最小的树，权值较大的结点离根较近，权值越小的离根节点越远。 哈夫曼树的构造过程：将N个结点看成N棵仅含一个结点的树，构成森林F，构造一个新的结点，结点的左右子树为森林F中权值最小的两棵树，结点的权值为左右子树的权值之和。在森林F中将刚选出的两棵树删除，同时将新构造的树插入。依次进行这个步骤，直到最后只剩下一棵树为止。 哈夫曼树的特点？ （1）权值较大的结点离根较近，权值越小的离根节点越远。 （2）哈夫曼树的带权路径长度之和最小。 （3）哈夫曼树不存在度为1的结点。 （4）哈夫曼树形态不唯一，但带权路径长度唯一。

哈夫曼树的优表现在哪？ 带权路径长度之和最小，权值越大的结点离根越近，权值越小的结点离根节点越远。哈夫曼编码是前缀编码，利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

大概的编码过程？ 编码是信息从一种形式转换为另一种形式的过程。用预先规定的方法将文字、数字或其它数据编成数码。解码，是编码的逆过程。将代码译为原数据形式。 例如哈夫曼编码的大概过程，首先是将要编码的信息调整为一棵哈夫曼树，在哈夫曼树左子树编码为0或1，右子树编码为1或0。某个元素的编码就是从根结点到自身所经过的路径上的01代码串。 m阶B树： 根节点至少有两颗子树（一个关键字） 除根结点外的非叶结点至少有m/2向上取整棵子树，最多有m棵子树 B树中n个结点有n+1个分支。叶结点在同一层且不带信息。 m阶B+树： 根节点至少有两棵子树，其他分支结点至少有m/2向上取整棵子树 每个分支结点最多有m棵子树 B+树中，n个结点有n个分支，每个非叶结点仅起到索引的作用，B+树的叶子结点包含全部关键字，B+树有一个指向最小关键字的指针。

有向图和无向图的联系,试各举一例说明？ 无向图可以看作每条边都有两个方向的有向图，无向图的邻接矩阵一定是对称阵,而有向图的邻接矩阵不一定对称。（强连通图才对称：i到j有路径，j到i有路径） 实际应用的区别是有向图可以描述非对称的关系,但无向图不能。比如我认识奥巴马,但是他不认识我,用图来表示这个关系时就将我和奥巴马之间连一条线,并且弧头指向他。 无向图能解决的问题都能用有向图表示,但无向图在对称的问题上往往更容易,因为用有向图去表示无向图时需要用两倍的边数。

稀疏图：E<V logV时为稀疏图

连通、连通图、连通分量：----无向图 （1）从顶点i到j有路径存在，则称i和j是连通的。 （2）若图中任意两个顶点都是连通的，则称该图为连通图，否则为非连通图。（3）无向图的极大连通子图称为连通分量。

强连通、强连通图、强连通分量：―有向图 （1）有向图中，从顶点i到j，顶点j到i都有路径存在，则称i和j是强连通的。 （2）图中任意一对顶点都是强连通的，则称该图是强连通图。 （3）有向图的极大连通子图称为强连通分量。

完全图 无向完全图：任意两个顶点间都有边存在，n个顶点，有n(n-1)/2条边。 有向完全图：任意两个顶点间都有方向相反的两条弧存在，n个顶点，有n(n-1)条有向边

数据结构中图的存储， ---------邻接矩阵、邻接表

什么情况下用邻接表，什么情况下用邻接矩阵。为什么？ 答：稠密图一般用邻接矩阵，因为图稠密的话，用邻接矩阵，编程简单还相对省空间。稀疏图一般用邻接表。 时间复杂度：邻接矩阵o（n^2）,邻接表o(边+顶点)

邻接矩阵和邻接表的优缺点？ 答：邻接矩阵优缺点：很容易确定图中任意两个顶点之间是否有边相连，但要确定图中有多少条边必须按行、按列对每个元素进行遍历，代价很大。 邻接表优缺点：很容易找到任一顶点的所有边，但要确定任意两个顶点i和j之间是否有边或弧，则需要遍历第i或第j个链表，代价很大。 有向图中邻接矩阵中入度和出度的定义 邻接矩阵中顶点i所在行（列）中1的个数为出度（入度）。 生成树 连通图的生成树是包含图中全部顶点的极小连通子图。若有n个顶点则有n-1条边。如果在生成树上减去一条边会变为非连通图，添加一条边，会形成一个环。 生成森林： 在非连通图中，各个连通分量的生成树，构成了非连通它的生成森林。 什么是最小连通图？-----生成树 答：首先，子图是连通的，用边把极小连通子图中所有结点连接起来，连接时要求不能出现环。若有n个结点，则有n-1条边。“极小”是指边尽量少的连通子图，去掉任何一个边都会使其变为不连通。 如何产生最小连通图？ 可以通过广度优先搜索或深度优先搜索遍历图，调用BFS或DFS的次数就是连通分量数也即有几个连通图。在每个连通分量中依次将顶点加入，并以边连接，边的连接过程要求不能出现环。在每个连通分量中，若有m个顶点，则有m-1条边。当然，也可以考虑使用prim或克鲁斯卡尔算法。 什么是最大连通图？ 极大连通子图： 设G(v,e)是连通图，G’（v’,e’）是连通图，如果对于v’等于v，e’包含于e，那么G’叫G的极大连通子图。 （1）连通图只有一个极大连通子图，就是它本身。 （2）非连通图有多个极大连通子图。每个连通分量都是一个连通图。 （3）极大是指，如果加入任何一个不在图的顶点都会导致它不再连通。 图的遍历： BFS,DFS BFS:-（队列）C类似于二叉树的层次遍历+访问数组标记技术 （1）访问起始顶点V1，并标记数组； （2）依次访问与V1相邻且未被访问的顶点w1,w2…wi，并标记数组; （3）再从w1,w2…wi出发，选择与之相邻但未被访问的顶点，并被标记数组；直到所有与V1有路径相通的顶点都被访问到。 （4）选择另外一个未被访问过的顶点V2作为起始顶点，访问并标记，重复这个步骤，直到所有顶点都被访问。

DFS：-栈C类似于二叉树的先序+访问数组标记技术 （1）访问起始顶点V1，并标记数组； （2）从V1出发，选择与V1相邻且未被访问过的任一顶点V2，并标记数组； （3）再从V2出发，选择与V2相邻且未被访问过的顶点V3，并标记数组。重复这个步骤； （4）当不能继续向下访问时，依次回退到最近访问的顶点，若它还有顶点未被访问，则访问该顶点，并标记。重复这个过程，直到图中所有顶点都被访问。 怎么能够判断判断一个图是连通还是非连通的？ （可通过图的遍历） 答：采用图的深度遍历法，从其中一个结点v出发，直至所有与v有路径相通的结点都被访问到。若此时图中所有点都被访问过，则该图是连通图，反之，说明还有其他连通分量，该图不是一个连通图。 求最小生成树的算法 答：主要有两种：克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法。 普里姆

---

计算机考研数据结构复习推荐资料 计算机复试数据结构知识点

包含数据结构、计算机网络、操作系统、数据库、热点概念

1、顺序存储和链式存储优缺点比较 ① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（＝1），易于查找和修改。 缺点：插入或删除元素时不方便；存储空间利用率低，预先分配内存可能造成存储空间浪费。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活，存储空间利用率高。 缺点：存储密度小（<1），查找和修改需要遍历整个链表。

2、数据结构的存储结构(4个)和对应的存储模式(1对1 1对多 多对多) 4种逻辑结构: 1.集合结构:数据元素之间没有任何关系. 2.线性结构:数据元素之间定义了线性关系.1对1 3.树形结构:数据元素之间定义了层次关系 1对多. 4.图状结构:数据元素之间定义了网状关系 多对多. 4种数据存储结构: 1.顺序存储结构:借助数据元素之间的相对位置来表示元素之间的逻辑结构.（vector动态数组、 deque双端队列、stack栈容器、queue队列容器） 2.链式存储结构:借助数据元素之间的元素的指针表示数组元素的逻辑结构. 3.散列存储结构:顺序存储+算列. 4.索引存储结构:顺序存储+索引.

3、最小生成树两种算法优缺点比较 Prim和Kruskal的不同之处在于两者选择的变量不同，Prim算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。而Kruskal主要是应用了并查集的思想，算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。 Prim算法的时间复杂度为O（｜V｜平方），不依赖于｜E｜，因此它适用于求解边稠密的图的最小生成树。Kruskal的时间复杂度为O（｜E｜log｜E｜），因此它适用于求边稀疏而定点较多的图。

4、hash函数的特点以及如何处理冲突 Hash,也叫哈希或散列，就是把任意长度的输入（也叫预映射），通过散列算法，变换成固定长度的输出，该输出就是散列值。 HASH函数必须具备两个基本特征：单向性 和 碰撞约束。单向性是指其的操作方向的不可逆性，在HASH函数中是指 只能从输入推导出输出，而不能从输出计算出输入；碰撞约束是指 不能找到一个输入使其输出结果等于一个已知的输出结果 或者 不能同时找到两个不同的输入使其输出结果完全一致。一个函数只用同时严格的具备了这样的特性，我们才能认可这样的一个HASH。 解决冲突的方法： 1、开放地址法：基本原理是:当关键字key的哈希地址出现冲突时，计算key的下一个存储地址w1，假如w1被占用；则计算key的下一个存储地址w2,如果w2仍被占用，继续计算key的存储地址w3,w4……直至找到能用的存储地址，将相应元素放入其中。 2、拉链法：也叫链地址法，将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。链地址法适用于经常进行插入和删除的情况。 对于拉链法来说，数组的每一个结点指向一个链表，链表中的每一个结点都存储了散列值为该索引的键值对，而链表的维护需要结点之间的指针来维护。

5、散列表的建立方法 平方取中法:先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。 除余法:它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m 相乘取整法:首先用关键字key乘上某个常数A（A大于0小于1）并抽取出key.A的小数部分；然后用m乘以该小数后取整 随机数法:选择一个随机函数，取关键字的随机函数值为它的散列地址

6、hash适合存储什么样的数据 表示的自然数太大，或是表示的自然数不连续，或者是不是自然数

7、影响hash表平均查找长度的因素 Hash表的平均查找长度依赖于散列表的装填因子，而不直接依赖于表中记录或hash表长度。当装填因子越大的时候，表示装填的记录越满，发生冲突的可能性越大，查找长度越长。 哈希函数、哈希表的大小、碰撞处理方法

8、排序算法有哪些，及其时间复杂度 直接插入排序：平均时间复杂度 n方 冒泡排序：n方 简单选择排序：n方 快速排序：nlog2 n 堆排序：nlog2 n 2路归并排序：nlog2 n 基数排序：d（n+r）

9、排序最优和最差相同的排序算法 简单选择排序都是n方；堆排序都是nlog2 n；2路归并排序都是nlog2 n；基数排序都是d（n+r）。

10、最差和平均的算法复杂度一样的排序算法 直接插入；冒泡；简单选择；堆排序；2路归并排序；基数排序

11、最好最坏平均都一样的排序算法 简单排序；堆排序；2路归并排序；基数排序

12、怎么确定图是一个环 深度优先遍历该图，如果在遍历的过程中，发现某个节点有一条边指向已经访问过的节点，并且这个已访问过的节点不是当前节点的父节点（这里的父节点表示dfs遍历顺序中的父节点），则表示存在环。 //如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。 算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。 第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。 如果最后还有未删除顶点，则存在环，否则没有环。 有向图是否有环的判定算法，主要有深度优先和拓扑排序方法。 拓扑排序，如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。

13、简述线索二叉树 传统的二叉树一般都是以链式存储的结构来表示。这样，二叉树中的每个节点都可以用链表中的一个链节点来存储，每个链节点就包含了若干个指针。但是，这种传统的链式存储结构只能表现出二叉树中节点之间的父子关系，而且不能利用空余的指针来直接得到某个节点的在特定的遍历顺序（先序，中序，后序）中的直接前驱和直接后继。 为了在二叉树中引入结点的前驱后继关系，引入了线索二叉树。 线索化：对二叉树以某种遍历顺序进行扫描并为每个节点添加线索的过程称为二叉树的线索化。进行线索化的目的是为了加快查找二叉树中某节点的前驱和后继的速度。 那么在有N个节点的二叉树中需要利用N+1个空指针添加线索。 //若无左子树，则将左指针指向其前驱结点；若无右子树，则将右指针指向其后继结点。

14、汉罗塔：Hn=Hn-1 x 2 + 1.

15、图的存储 邻接矩阵：用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。 邻接表：邻接表为了避免内存的浪费引入了链式存储，它的处理办法是： 1.用一个一维数组存储顶点，当然你也可以用单链表存储， 2.用单链表存储顶点的邻接点，可以将顶点改为结构体数组，结构体中存放邻接点的指针，邻接点也创建一个结构体，定义指针next存放该顶点的另一个邻接点，这样就可以把该顶点的所有邻接点串起来了。 邻接矩阵的优缺点： 1）优点：a. 便于判断两个顶点是否有联系。确定顶点后再确定矩阵上的相应位置是否非0或非MaxInt即可。 b. 便于计算各个顶点的度。其实也不用计算，数就完事了。对于无向图，多少个(1,n)的值为1，v1的度就是多少；对于有向图，多少个<1,n>的值为1，v1的出度就是多少，多少个<n,1>的值为1，v1的入度就是多少。 2）缺点：a. 不便于增加和删除顶点。非链式结构的通病。 b. 不便于统计边的数目，需要遍历邻接矩阵的所有元素，时间复杂度为O(n2)。无向图遍历完后还要除以2。 c. 空间复杂度高。非链式结构的另一通病，稀疏图（边或弧数较少）尤其浪费空间。 邻接表的优缺点： 1）优点：a. 便于增加和删除顶点。 b. 便于统计边的数量，时间复杂度为O(n+e)。 c. 空间效率高。 2）缺点：a. 不便于判断顶点间是否有联系。 b. 不便于计算有向图各个顶点的入度，需要遍历其余所有起始顶点的单链表。 还有十字链表法和邻接多重表

16、图的深度和广度遍历是什么，在工程中有哪些应用 广度优先搜索BFS：类似于二叉树的层序遍历算法。首先访问起始顶点v，接着从v出发，依次访问v的各个未访问过的邻接顶点w1，w2…，wi的所有未访问过的邻接顶点，再从这些访问过的顶点出发，直至图中所有顶点都被访问过为止。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，因此它不是一个递归算法。Dijkstra单源最短路径算法和prim最小生成树算法也应用了类似的思想。 深度优先搜索DFS：类似于树的先序遍历，运用了递归的思想，这种算法所遵循的搜索策略是尽可能深地搜索一个图。首先访问图中某一起始顶点v，然后从v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2…重复上述过程，当不能再继续向下访问时，依次退回到最近被访问的顶点，直至所有顶点均被访问过为止。 BFS应用：用来确定在互联网中从一个结点到另一个结点（一个网络到其他网络的网关）的最佳路径，最短路径 DFS应用：拓扑排序，走迷宫

17、树和图的遍历的区别，存储方式; 存储方式：邻接矩阵、邻接表 遍历方式：BFS和DFS

18、两个最短路径算法有什么不同，用于什么情况 Floyd算法是按顺序逐渐允许每个顶点作为中间节点，按照这个中间节点的变化去进行松弛。 Dijsktra算法是根据当前离开始节点最近为标准来确定当前扩展节点，按照这个起始节点的变化去进行松弛。 拓扑排序中使用了哪些数据结构 栈

19、简述二叉排序树 二叉排序树：二叉排序树也叫二叉查找树、二叉搜索树（简称：BST）对于二叉树中的任何一个非叶子节点要求左子节点比当前节点值小，右子节点比当前节点值大（一个空树也可以称为一个二叉排序树）。

20、二叉树和度为二的树的区别 1、度不同 度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。 2、分支不同 度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。 3、次序不同 度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

21、解释下关键路径和关键活动，什么情况下才有关键路径 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销，称之为用边表示活动的网络，简称AOE网。在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。

22、简述背包问题 f[v]=max{f[v],f[v-w[i]]+v[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。

23、数组和链表有哪些优缺点 数组优点：查找效率高，可随机访问； 数组缺点：1、增删操作不方便，会引起大量元素的移动； 2、内存空间大小固定，不能动态拓展，且容易造成内存浪费。 链表优点：1、增删操作方便，只需移动指针； 2、可动态分配空间，内存利用率高； 链表缺点：不能随机访问，必须从第一个开始遍历，查找效率低。

24、计算机的局部性是什么？ 局部性分为时间局部性和空间局部性 时间局部性是指一个信息被访问，那么它在近期很可能再次被访问； 空间局部性是指一个存储位置被访问，那么它附近的存储位置很可能下次被访问。

25、b树 全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而B-tree有多条路，即父节点有多个子节点。 使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。这个数据结构一般用于数据库的索引，综合效率较高。 对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。即遍观整棵树，子节点最多的个数是m，那么这棵树就是m阶树。 所有的叶子结点都出现在同一层次上，即所有叶节点具有相同的深度，等于树高度。并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

26、顺序表和链表的区别 相同点 1.都是线性表 2.元素在逻辑上都是连续的（存储上顺序表连续，链表不连续） 3.每个元素都有唯一的前驱和唯一的后继（注意：第一个元素没有前驱，最后一个元素没有后记―>循环链表除外） 不同点 1.底层存储空间不同： 顺序表底层存储空间连续； 链表不连续； 2.插入和删除的方式不同： 顺序表插入和删除得搬移后面的所有元素，效率低，时间复杂度为O（N）； 链表不需要搬移后面的元素，效率高，时间复杂度位O（1）； 3.随机访问： 顺序表底层空间连续，支持随机访问，访问元素时间复杂度为O（1）； 链表底层空间不连续，不支持随机访问，访问元素时间复杂度为O（N）； 4.扩容： 顺序表在插入时需要扩容C>开辟新空间，拷贝元素，释放就空间； 链表在插入时不需要扩容； 5.空间利用率： 一般情况顺序表空间利用率较高（链表每个节点中需要存储date和next，顺序表只存储元素date）； 链表中的元素存储再一个一个节点中，而每个节点都是malloc出来的：频繁向堆申请小的内存块C造成内存碎片，效率低；

1、TCP/IP 位于哪一层？ TCP位于传输层；IP位于网络层

2、TCP/IP 有几层，为什么没有物理层 有四层，分别是网络接口层，网际层，传输层和应用层。网络接口层类似于OSI模型中的物理层和数据链路层。

3、TCP和UDP有什么区别 TCP面向连接，提供可靠的服务，通过TCP连接传送的数据是无差错的且按序到达；UDP是无连接的，它是一种尽最大努力交付，不能保证可靠交付，但是UDP具有较好的实时性。

4、TCP怎么实现可靠传输 TCP保证可靠性主要依靠几种机制：首先是TCP将每个字节的数据都进行了编号，就是序列号，序列号能够保证数据的按序到达；第二是确认应答机制，即ACK，接收方对于按序到达的数据会发送ACK进行确认；第三是超时重传机制，当发送方发出后在一定时间内未收到接收方的确认，发送方就会进行重传；第四是流量控制，接收端处理数据的速度是有限的，如果发送方发送数据的速度过快，导致接收端的缓冲区满，而发送方继续发送，就会造成丢包，继而引起丢包重传等一系列连锁反应，因此TCP支持根据接收端的处理能力，来决定发送端的发送速度。

5、TCP怎么解决拥塞控制 拥塞控制是防止过多的数据注入到网络中，可以使网络中的路由器或链路不致过载，是一个全局性的过程。拥塞控制主要是慢开始、拥塞避免、快重传和快恢复四个算法。发送方维持一个叫做拥塞窗口cwnd（congestion window）的状态变量，慢开始算法的思路就是，不要一开始就发送大量的数据，先探测一下网络的拥塞程度，也就是说由小到大逐渐增加拥塞窗口的大小。无论是在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞，就把慢开始门限设置为出现拥塞时的发送窗口大小的一半。然后把拥塞窗口设置为1。 TCP的拥塞控制采用了四种算法，即慢开始、拥塞避免、快重传和快恢复。 （1）慢开始算法 在TCP刚刚连接好并开始发送TCP报文段时，先令拥塞窗口cwnd = 1，即一个最大报文段长度MSS。每收到一个对新报文段的确认后，将cwnd 加1，即增大一个MSS。用这样的方法逐步增大发送方的拥塞窗口 cwnd，可使分组注入网络的速率更加合理。 （2）拥塞避免算法 拥塞避免算法的做法如下：发送端的拥塞窗口cwnd每经过一个往返时延RTT就增加一个MSS的大小，而不是加倍，使cwnd按线性规律缓慢增长（即加法增大)，而当出现一次超时(网络拥塞)时，令慢开始门限ssthresh等于当前cwnd的一半（即乘法减小)。 （3）快重传 快重传技术使用了冗余ACK来检测丢包的发生。同样，冗余ACK也用于网络拥塞的检测（丢了包当然意味着网络可能出现了拥塞)。快重传并非取消重传计时器，而是在某些情况下可更早地重传丢失的报文段。 当发送方连续收到三个重复的ACK报文时，直接重传对方尚未收到的报文段，而不必等待那个报文段设置的重传计时器超时。 （4）快恢复 快恢复算法的原理如下：发送端收到连续三个冗余ACK(即重复确认）时，执行“乘法减小”算法，把慢开始门限ssthresh设置为出现拥塞时发送方cwnd的一半。与慢开始（慢开始算法将拥塞窗口cwnd 设置为1)的