哈夫曼树的构建_哈夫曼树只有度为0和度为2

考研保研面试系列（一）—数据结构面试真题整理（打印版） 　　数据结构面试真题整理 　　为方便大家背诵，整理的答案都是干货，因为在面试的时候，说了很多但说不到重点上，导师会听烦的，即使答在重点上，也要条理清晰的讲述，切记不要啰啰嗦嗦、磕磕巴巴，保证流畅度和准确度，否则会影响导师对大家的印象。大家直接打印背诵就好了，我主页上还有一篇是背诵版的，背过了之后，可以直接看着背诵版的回忆内容，检查自己的背诵情况~~~ 如果有不对的地方，欢迎大家的批评指正~~~ 　　里面标注真题的是我被问到过的，或者是身边有朋友同学被问到过的~~~ 　　1.什么是时间复杂度，空间复杂度，大O表示法？ 　　时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。 　　空间复杂度：算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。 　　一般用大O表示法来表示时间复杂度和空间复杂度。以时间复杂度为例子，O(n)这个大O表示的是最坏情况下的时间复杂度，是算法中所有语句的频度之和T(n)的数量级。 　　2.数据的存储结构有哪几种，每种的优缺点是什么？ 　　存储结构是指数据结构在计算机中的表示，也称物理结构，主要有以下4种: 　　①顺序存储。 　　把逻辑上相邻的素存储在物理位置上也相邻的存储单中，素之间的关系由存储单的邻接关系来体现。其优点是可以实现随机存取，每个素占用最少的存储空间；缺点是只能使用相邻的一整块存储单，因此可能产生较多的外部碎片。 　　②链式存储。 　　不要求逻辑上相邻的素在物理位置上也相邻，借助指示素存储地址的指针来表示素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单；缺点是每个素因存储指针而占用额外的存储空间，且只能实现顺序存取。 　　③索引存储。 　　在存储素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是(关键字，地址)。其优点是检索速度快;缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。 　　④散列存储。 　　根据素的关键字直接计算出该素的存储地址，又称哈希(Hash)存储。其优点是检索、增加和删除结点的操作都很快;缺点是若散列函数不好，则可能出现素存储单的冲突，而解决冲突会增加时间和空间开销。 　　3.介绍一下贪心算法（真题） 　　就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。 　　4.介绍一下动态规划算法（真题，后面弗洛伊德算法是用的动态规划的思想，提到弗洛伊德的时候很容易会引出动态规划） 　　是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。 　　5.数组和链表的区别 或 顺序表和链表的区别？ 　　数组：1. 在内存中占据连续的空间2. 占用内存小3. 数组的长度在定义时需要给定，如果存放的数据个数超过了数组的初始大小，会出现溢出4. 数组利用下标定位素，访问速度快，时间复杂度为O(1)5. 插入或删除素可能需要移动大量的数据，时间复杂度为O(n) 　　链表：1. 在内存中可以占据不连续的空间2. 需要额外存储前驱和后继的信息，总体上需要更多的内存空间3. 链表的长度可以根据实际需要进行伸缩4. 链表访问素相对较慢，需要遍历链表直到找到目标素，时间复杂度O(n)5. 插入或删除素只需修改指针，时间复杂度为O(1) 　　所以说链表适合多插入删除场景，数组线性表适合多读取场景 　　6.头指针和头结点的区别？ 　　头指针:是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要素，无论链表是否为空，头指针都存在。 　　头结点:是放在第一个素节点之前，便于在第一个素节点之前进行插入和删除的操作，头结点不是链表的必须素，可有可无，头结点的数据域也可以不存储任何信息。 　　7.栈和队列的区别？ 　　栈： 　　先进后出： 是一种后进先出的数据结构，最后进入栈的素最先被访问。栈支持两种基本操作，入栈和出栈。入栈将素添加到栈的顶部，而出栈则移除栈顶的素。栈只允许在栈顶进行操作，即只能访问或修改最后入栈的素。 　　队列： 　　先进先出：队列是一种先进先出的数据结构，最先进入队列的素最先被访问。队列支持两种基本操作，即入队和出队。入队将素添加到队列的尾部，而出队则移除队列头部的素。队列允许在队列头部和尾部进行操作，但通常只允许从队列头部出队，从队列尾部入队。 　　区别： 　　访问顺序： 栈的访问顺序是后进先出，而队列的访问顺序是先进先出。 　　栈的主要操作是入栈和出栈，而队列的主要操作是入队和出队。 　　栈只允许在栈顶进行操作，而队列允许在队列的头尾进行操作，但通常只允许从头部出队、尾部入队。 　　8.如何区分循环队列是队空还是队满？ 　　由于队空条件和队满条件都是Q.front == Q.rear，为了区分是队空还是队满，三种方式： 　　①牺牲一个单来区分队空和队满。队满条件是：(Q.rear+ 1) % MaxSize == Q.front 　　②类型中增设表示素个数的数据成员。队空：Q.size == 0；队满：Q.size == MaxSize 　　③类型中增设tag数据成员，tag = 0说明是上一步操作是删除，tag = 1说明是上一步操作是插入。队空：Q.front == Q.rear && tag == 0；队满：Q.front == Q.rear && tag == 1。 　　9.栈和堆的区别？（真题） 　　先回答什么是栈（详看第7题），再回答什么是堆：堆是一种完全二叉树。分为大顶堆和小顶堆。大顶堆是左右子树的结点值都小于根结点值，左右子树都是大顶堆。小顶堆是左右子树的结点值都大于根结点值，左右子树都是小顶堆。 　　栈由操作系统自动分配释放，可由操作系统完成静态分配和动态分配，生长方向向下，内存地址由高到低，分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，效率较高; 　　堆由开发人员分配和释放，只能动态分配，生长方向向上，内存地址由低到高，由库函数或运算符来完成申请与管理，效率较低。 　　10.什么是串的模式匹配？简介一下KMP算法？ 　　子串的定位操作通常称为串的模式匹配，他求的是子串(常称模式串)在主串中的位置。 　　在说KMP算法的时候，先来谈一谈暴力模式匹配算法，它的思想是从主串的第一个字符起，与子串的第一个字符比较，相等则继续比较; 不等则从主串的下一个位置起，继续和子串开始比较，直到最后看是否匹配成功。 　　而KMP算法呢，就是对暴力模式匹配算法的一个改进版本，在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。这样其实无形中增加了匹配的次数。所以可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯， 并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。这样其实是保证了主串的指针是一直向前走的，不会后退，也使得它的效率大大提高。 　　（在面试的时候可以适当加一些口语化内容，如果全是很书面专业的，老师会觉得：这小子，背的挺熟啊！所以说适当用口语化的内容可以拉近你和老师之间的距离，让老师觉得你没有在背，而是我本身脑子里就有东西，现在只不过是把它们讲出来，老师会随着你的引导，听你娓娓道来的讲述，老师能听进去你的答案，你就赢了） 　　11.树的概念性知识，什么是树？什么是二叉树？什么是满二叉树？什么是完全二叉树？ 　　树：树是非线性结构，其素之间有明显的层次关系。在树的结构中，每个节点都只有一个前件称为父节点，没有前件的节点为树的根节点，简称为树的根;每个节点可以有多个后件成为节点的子节点，没有后件的节点称为叶子节点。 　　二叉树：二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树可以用递归的形式定义。 　　满二叉树：满二叉树是指除了最后一层外其他节点均有两颗子树。 　　完全二叉树：完全二叉树是指除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点。 　　12.树的存储结构？ 　　树有三种存储结构，分别是： 　　①双亲表示法 　　这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

双亲表示法 　　②孩子表示法 　　孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，这时n个结点就有n个孩子链表(叶子结点的孩子链表为空表)，这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

孩子表示法 　　③孩子兄弟表示法 　　孩子兄弟表示法又称二叉树表示法，就是用二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点) 。这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

孩子兄弟表示法 　　13.什么是二叉排序树，它是怎么查找的呢？ 　　二叉排序树：二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树: 　　①若左子树非空，则左子树上所有结点的值均小于根结点的值。 　　②若 右子树非空，则右子树上所有结点的值均大于根结点的值。. 　　③ 左、右子树也分别是一棵二叉排序树。 　　二叉排序树的查找是从根节点开始的，延某个分支逐层向下比较的过程。若二叉树非空，先将给定值与根结点的关键字比较，若相等，则查找成功;若不等，如果小于根结点的关键字，则在根结点的左子树.上查找，否则在根的右子树上查找。这显然是一个递归的过程。 　　14.什么是平衡二叉树？ 　　平衡二叉树：二叉树中任意结点的左、右子树高度差的绝对值不超过1。 　　结点左子树与右子树的高度差是这个结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0或1。所以，平衡二叉树可定义为或者是一棵空树，或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。 　　15.什么是带权路径长度，什么是哈夫曼树？ 　　在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度(WPL)。 　　在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树。 　　16.来简述一下哈夫曼树的构造过程吧 　　给定n个权值分别为W1, W2…， Wn的结点，构造哈夫曼树的算法描述如下： 　　第一步将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。 　　第二步构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。 　　第三步从F中删除刚才选出的两棵树，同时将新得到的树加入F中。 　　第四步重复第二步和第三步直至F中只剩下一棵树为止。 　　从上述构造过程中可以看出哈夫曼树具有如下特点: 　　①每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。 　　②构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1。 　　③每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。 　　17.图的存储结构？ 　　①邻接矩阵法 　　邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

邻接矩阵法 　　②邻接表法 　　邻接表，是指对图G中的每个顶点V建立一个单链表，第i个单链表中的结点表示依附于顶点v的边(对于有向图则是以顶点v为尾的弧)，这个单链表就称为顶点vi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点：顶点表结点和边表结点。

邻接表法 　　③十字链表法 　　十字链表法是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

十字链表法 　　18.图的广度优先搜索和深度优先搜索？ 　　广度优先搜索是用队列实现的，首先访问起始顶点V，接着由V出发依次访问V的各个未访问过的邻接顶点W1, W2, … ，Wn，并把这些结点一 一加入到队列当中，然后将W1出队，再次依次访问出队结点W1的所有未被访问过的邻接顶点，并将这些结点入队，重复上述操作，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为初始点，重复上述过程。Dijkstra源最短路径算法和Prim最小生成树算法也应用了类似的思想。 　　深度优先搜索是用了递归回溯的思想，首先访问图中某一起始顶点V，然后由V出发，访问与V邻接且未被访问的任一顶点W1，再访问与W1邻接且未被访问的任一顶点W2。重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。 　　19.求最小生成树有哪几个算法，分别介绍一下？ 　　Prim算法： 　　基本思想： 从一个初始顶点开始，逐步选择与当前生成树相邻的权值最小的边对应的顶点，将其加入生成树，重复此过程直到所有顶点都包含在生成树中。 　　Kruskal算法： 　　基本思想： 将所有边按照权值从小到大排序，然后逐个加入生成树，但要保证加入的边不构成环。 　　20.求最短路径有哪几个算法，分别介绍一下？ 　　Dijkstra算法： 　　基本思想： 从起始点开始，逐步确定到各个顶点的最短路径。每次选择当前距离最短的顶点，然后更新与该顶点相邻的顶点的距离 　　Floyd算法： 　　基本思想： 通过动态规划的思想，逐步更新所有顶点对之间的最短路径。算法的核心是使用中间顶点作为中介，对路径进行优化。 　　21.什么是折半查找？ 　　折半查找，也称为二分查找，是一种在有序数组中查找特定素的高效算法。 　　基本思想：通过每一步将待查找区域缩小一半的方式，逐步逼近目标素，最终找到目标素的位置或确定目标素不存在。 　　步骤： 　　①初始化搜索区，假设目标数组从小到大已经排序。 　　②比较目标素与搜索区域的中间素。 　　③如果目标素等于中间素，查找成功，返回中间素的索引。 　　④如果目标素小于中间素，说明目标素可能在左半部分，缩小搜索区域到左半部分，重复步骤②。 　　⑤如果目标素大于中间素，说明目标素可能在右半部分，缩小搜索区域到右半部分，重复步骤②。 　　⑥重复步骤②，直到找到目标素或搜索区域为空。 　　时间复杂度: O(logn)，这使得折半查找在大规模有序数据集中的查找效率较高。 　　注意:折半查找要求数据集必须是有序的。 　　22.什么是分块查找？ 　　分块查找的核心思想是将数据划分为若干块，每个块中的素可以是有序的，但块与块之间的顺序可以无序，这种方式有助于减小查找的范围，从而提高查找效率。 　　23.什么是哈希表？哈希函数的构造方法？哈希冲突怎么解决？ 　　24.什么是排序？内部排序和外部排序区别是什么？ 　　排序是将一组数据按照特定的顺序重新排列的过程。 　　①数据规模： 　　内部排序处理的数据集可以完全加载到内存中。 　　外部排序处理的数据集太大，无法一次性加载到内存，需要通过分块或分段的方式进行排序。 　　②数据存储位置： 　　内部排序的数据直接存储在内存中。 　　外部排序的数据通常存储在外部存储介质，如硬盘上，需要通过多次读写来进行排序。 　　③性能： 　　由于内部排序的数据在内存中，通常具有更高的性能。 　　外部排序可能涉及大量的I/O操作，因此性能相对较低，但处理数据的规模较大。 　　25.列举几种常见的排序，它们的时间复杂度分别是多少？ 　　冒泡排序，插入排序，选择排序，归并排序，快速排序，堆排序 　　冒泡排序：O(n^2) 　　插入排序：O(n^2) 　　选择排序：O(n^2) 　　归并排序：O(n log n) 　　快速排序：O(n log n) 　　堆排序：O(n log n) 　　26.具体介绍快速排序，并尽量写出程序(真题，西电真题)。 　　27.具体介绍堆排序。 　　28.具体介绍选择排序。 　　29.具体介绍冒泡排序，并写出程序。 　　30.具体介绍归并排序，并写出程序。 　　明天更新~~~