计算哈夫曼树的wpl值_树的带权路径长度

习题纠错05 　　以下哪些算法是可以用来求最小生成树（） //答案是AD 　　A 　　kruskal算法 　　B 　　dijkstra算法 　　C 　　floyd算法 　　D 　　prim算法 　　// 1.Prim算法(适合稠密图，贪心算法的运用，时间复杂度O(n+e),邻接表存储；O(n^2),图 ) 　　//2.Kruskal算法(适合稀疏图，贪心算法的运用，时间复杂度O(eloge),e为边数 ) 　　//求图最短路径算法： 1.DFS/BFS(单源) 2.Floyed算法(多源) 3.Dijkstra算法(单源) 4.Bellman-Ford算法(单源，负权) 　　将一棵树转换为二叉树后，这棵二叉树的形态是（ ） //答案是B 　　A 　　一定没有左子树 　　B 　　一定没有右子树 　　C 　　一定同时具有左子树和右子树 　　D 　　不确定//这里需要注意的是，根节点的没有兄弟节点，所以在转换成二叉树的时候，也就没有了右子树了 　　设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。//答案是A 　　A 　　N1-1 　　B 　　N2-1 　　C 　　N2+N3 　　D 　　N1+N3 //这里需要注意的是，N1的节点数减去根节点的，所以是N1-1 　　下面关于 B 树和 B+ 树的叙述中，不正确的结论是 。 //答案是A 　　A 　　B树和B+树都能有效的支持顺序查找 　　B 　　B树和B+树都能有效的支持随机查找 　　C 　　B树和B+树都是平衡的多叉树 　　D 　　B树和B+树都可用于文件索引结构//这里需要注意的是 　　//B树和B+树都是支持随机查找的，但是B树不支持顺序查找 　　下列关于m阶的B-树的论述不正确的是 //答案是D 　　A 　　B-树是一种平衡的多路查找树 　　B 　　树中每个结点至多有m棵子树 　　C 　　若根结点不是叶子结点，则至少有两棵子树 　　D 　　B-树中的叶子结点可出现在不同层次上//这里需要注意的是 　　//m阶的B树叫做该树的每个节点最多有m个子节点 　　//所以A是正确的，B也是正确的，B树的平衡性质要求所有的叶子节点都在 　　//同一个层次上，所以D错误，根据B树的特性，B-树的每个非叶子结点都可以有多个子结点， 　　树的基本遍历策略分为：先根遍历和后根遍历。二叉树的基本遍历策略分为：先序遍历、中序遍历和后序遍历。则下面说法正确的是（） //答案是A 　　A 　　树的先根遍历序列与其对应的二叉树的先序遍历序列相同 　　B 　　树的后根遍历序列与其对应的二叉树的先序遍历序列相同 　　C 　　树的先根遍历序列与其对应的二叉树的中序遍历序列相同 　　D 　　以上都不对//树的先根遍历和其对应的二叉树的先序遍历相同，后根和后序对应 　　一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度为2的节点个数是5，叶子节点个数为() //答案是D 　　A 40 　　B 42 　　C 38 　　D 44//这里需要注意的是 　　//无论是什么树，树的总节点等于树的分叉数+1，而树的分叉数的计算为各个各个不同的度与其对应的节点个数相乘后然后相加的和 　　//就如例题：64+310+25+1x+1 = 6+10+5+x+y（其中的x为度为1的节点，y为叶子节点） 　　在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还是线索化信息，若 0 标识树结构信息， 1 标识线索，对应叶结点的左右链域，应标识为 __ __ 。 　　//答案是D 　　A 00 　　B 01 　　C 10 　　D 11//这里需要注意的一个概念就是“树结构信息指向“其实就是子节点 　　// 　　在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点的是：（）//答案是B 　　A 动态规划 　　B 回溯法 　　C 分支限界法 　　D 回溯法和分支限界法//活节点（Active Node）是指当前待处理的节点，即还未被完全探索或展开的节点。 　　//活节点是搜索过程中需要进一步探索的节点，其子节点可能会被生成和扩展，从而继续搜索下去。 　　//回溯法（Backtracking）是一种通过穷举所有可能的解来求解问题的算法。 　　//分支限界法（Branch and Bound）是一种在搜索问题的解空间时，通过设定上界和下界，剪枝无效的分支，从而减少搜索空间的算法。 　　//动态规划（Dynamic Programming）是一种通过将问题划分为多个重叠子问题，并通过存储子问题的解来避免重复计算的算法。 　　. 　　若一个具有N个结点，M条边的无向图构成一个森林，(N>M)， 则该森林必有( )棵树。//答案是C 　　A M 　　B N 　　C N-M 　　D 12 //这里需要注意的是 　　//在一个无向图中，如果构成了一个森林，说明其中没有形成环（即没有闭合路径） 　　//这是因为在一棵树中，节点数比边数多 1。因此，对于整个森林来说，总的节点数 N 和总的边数 M 之间的关系可以表示为：N = M + T 　　//所以森林中的树的数量是N-M 　　若 A=10、B=4、C=6、D=4、E=15 则后缀表达式“ ABCD+-E+ ”的值为 ( ) 。//答案是A 　　A 45 　　B 31 　　C 53 　　D 65//这里需要注意的是 　　//后缀表达式的规则是依靠栈来实现的，遇到操作数则入栈，遇到操作符就出栈 　　//就如例题中A和B先入栈，遇到“”号则AB出栈并相乘，得到40，40继续入栈，CD之后 　　//也入栈，遇到“+”号则，DC和40相继出栈，DC想加得到的和进栈，40也跟着进栈，遇到-号 　　//出栈，40-10，得到的是三十，三十入栈，E15入栈，最后遇到+号，三十和十五想加，得到45 　　红黑树的插入复杂度为（ ）。//答案是D 　　A O(n) 　　B O(1) 　　C O(n^2) 　　D O(log(n))//这里只是需要记住插入复杂度为这个就行了 　　若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是（）。 //答案是C 　　A 1，2，3，4 　　B 2，3，4，1 　　C 3，2，4，1 　　D 4，3，2，1 　　某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（）棵树 //答案是C 　　A 1 　　B 2 　　C 3 　　D 4//这里需要注意的是 　　哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串 “alibaba” 的二进制哈弗曼编码有___位（bit）//答案是C 　　A 11 　　B 12 　　C 13 　　D 14//这里需要注意也就一个概念 　　//也就是计算哈夫曼编码的位数其实就是计算哈夫曼树的带权路径长度，也就是WPL 　　一棵3阶B-树中含有2047个关键字，包含叶结点层，该树的最大深度为（）//答案是B 　　A 11 　　B 12 　　C 13 　　D 14//这里需要注意的是B树深度的计算公式 　　//假设B树的最小阶数为k，总关键字数为n，那么B树的深度可以近似计算为： 　　//深度 ≈ logk((n+1)/2) 　　如果T1是由有序树T转换而来的二叉树，那么T中结点的先序序列就是T1中结点的（）序列 //答案是A 　　A 先序 　　B 中序 　　C 后序 　　D 层次//这里需要注意的是 　　//只需要记住，有序树转二叉树，那么有序树的前序遍历对应着二叉树的前序遍历，有序树的后续遍历对应着二叉树的中序遍历 　　具有3个节点的二叉树有几种形态？//答案是C 　　A 3 　　B 4 　　C 5 　　D 6//这里需要注意的是 　　//题目问的是形态，所以不需要考虑各个节点的不同，只需要考虑树的样子即可 　　具有八个结点的二叉树共有多少种（）？//答案是D 　　A 8 　　B 256 　　C 960 　　D 1430//这里需要注意的是卡特兰数的计算公式 　　//计算公式为f(n)=(2n)!/n!(n+1)! 　　若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）//答案是C 　　A n – 1 　　B n/m – 1 　　C (n-1)/(m-1) 　　D n/(m-1) – 1 　　E (n+1)/(m+1) – 1//这里需要注意的是 　　//对于度为m的哈夫曼树的话，该树中只存在两种节点，也就是度为0的节点（叶子节点）以及度为m的节点 　　//在该题走中，非叶子节点的个数，也就是度为m的节点的个数，根据节点数=分叉数+1，并且分叉数=各个度 　　//的节点的数量乘以对应的度，并且想加得到的和。推导出答案应该是C 　　2-3树是一种特殊的树，它满足两个条件： 　　（1）每个内部节点有两个或三个子节点； 　　（2）所有的叶节点到根的路径长度相同； 　　如果一颗2-3树有9个叶节点，2-3树中非叶节点的个数可能是//答案是BE 　　A 8 　　B 7 　　C 6 　　D 5 　　E 4//这里需要注意的是 　　//要根据两个条件，条件2指出每个叶节点到根的路径相同，所以这些叶子节点应该是在同一层的 　　//其次条件1指出，每个内部节点有两个或者三个子节点，所以根节点至少要有两个， 　　//分两种情况来看，当根节点具有两个节点的时候，那么这两个节点至少需要四个子节点，这一情况是OK的 　　//如果是这两个节点是五个子节点，那么就不满足条件1了，所以，根节点有两个子节点的情况只有这一种 　　//现在分析根节点具有三个子节点，如若三个子节点的还有子节点的话，那么至少需要的子节点是6个，这样叶子节点就不够分了 　　//就不满足条件1了，所以根节点的三个子节点必须是要直接连着叶子节点的，所以情况只能有两种 　　图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。//答案是A 　　A 　　正确 　　B 　　错误//这里需要注意的是，最小生成树不唯一，所以，所以可能相等 　　设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）//答案是A 　　A 　　m – n 　　B 　　m – n – 1 　　C 　　n + 1 　　D 　　条件不足，无法确定//这里需要注意的是森林转对应二叉树的步骤 　　//1、先将森林中的每颗树转变成二叉树 　　//2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。 　　//3、所以转换后的二叉树的左子树的节点数，加上根节点的个数，就是第一颗树的节点数，数，即二叉树总节点个数m减去根节点右子树节点个数n。 　　若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（ ）。 //答案是B 　　A 　　12 　　B 　　20 　　C 　　32 　　D 　　33//这里需要注意的是计算所有非叶子节点的平衡二叉树的节点总数的话，使用到斐波那契数列，机f(n) = f(n-1)+f(n+1),,高度为多少，就加几次 　　//例如，这里的高度为6，那么总节点数为1+1+2+3+5+8=20 　　若二叉排序树（搜索树）中关键码互不相同，则其中最小素和最大素一定是叶子结点。 ( )//答案是B 　　A 　　正确 　　B 　　错误//这里需要注意的是，二叉排序树，不是二叉平衡树，如果只有左子树的话那么，最大值为根节点 　　在一个空的5阶B-树中依次插入关键字序列{6,8,15,16,22,10,18,32,20}，插入完成后，关键字6所在结点包含的关键字个数为（ ）//答案是B 　　A 　　2 　　B 　　3 　　C 　　4 　　D 　　5//这里需要注意的是先要，确定每个节点的关键字个数，计算出每个节点的最少关键字个数是2个，最多是4个 　　//然后排除D选项，最后根据插入，确定所在节点包含3个节点 　　若X是二叉树中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为//答案是C 　　A 　　X的双亲 　　B 　　X的右子树中最左的结点 　　C 　　X的左子树中最右结点 　　D 　　X的左子树中最右叶结点//这里需要注意的是，中序线索树，就是将树进行中序遍历后，得到的遍历结果，查看其前驱后继 　　//包括要是是前序线索化，也是先先序遍历得到结果，然后查看前驱后继 　　已知三叉树T中6个叶结点的权分别是 2, 3, 4, 5, 6, 7，T 的带权（外部）路径长度最小是（）//答案是B 　　A 　　27 　　B 　　46 　　C 　　54 　　D 　　56//这里需要注意的是，三叉树的节点，可以最末端为两个 　　在ASC算法team日常开发中，常常面临一些数据结构的抉择，令人纠结。目前大家在策划一个FBI项目（Fast Binary Indexing），其中用到的词汇有6200条，词汇长度在10-15之间，词汇字符是英文字母，区分大小写。 　　请在下面几个数据结构中选择一个使检索速度最快的：//答案是D 　　A 　　二叉搜索树，比较函数开销：1次运算/每字符 　　B 　　哈希表，hash算法开销：10次运算/每字符 　　C 　　链表，比较函数开销：1次运算/每字符 　　D 　　TRIE树，寻找子节点开销：1次运算/每字符//TRIE又称作于单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。 　　//典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 　　//它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。 　　下面关于平衡二叉树的说法正确的是？//答案是ACD 　　A 　　它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 　　B 　　构造与调整平衡二叉树的常用算法有红黑树、AVL、Treap等。 　　C 　　采用平衡树的优点是使树的结构较好，从而提高查找运算的速度。 　　D 　　采用平衡树的缺点是是插入和删除运算变得复杂化，从而降低了他们的运算速度。 　　//B选项错在红黑树、AVL和Treap都是平衡二叉树的一种实现，但它们并不是用于构造和调整平衡二叉树的算法。、 　　//实际上，它们是平衡二叉树的不同类型。 　　广度遍历生成树描述了从起点到各顶点的最短路径。//答案是B 　　A 　　正确 　　B 　　错误//这里需要注意的是，错就错在要是生成树是带权的，而且权值是不想等的，那么不一定是最短路径了 　　//要想是最短路径，就需要的是无权的或者权值要想等的 　　一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）//答案是B 　　A 　　CABDEFG 　　B 　　ABCDEFG 　　C 　　DACEFBG 　　D 　　ADCFEG//这里需要注意的是，有个规律可以记一下，当知道一种遍历结构，可以将这个遍历的结果， 　　//看成栈的入栈顺序，而另外两种遍历的结果可能性则可以看成出栈的顺序 　　对于有n个结点的二叉树，其高度为（）(第一层高度1)//答案是D 　　A 　　nlog2(n) 　　B 　　log2(n+1) 　　C 　　log2(n) 　　D 　　不确定//这里需要注意的是，二叉树的类型不一定，可能不是完全二叉树 　　集合中任何两个素都可以比较大小，但比较不满足传递性，则以下说法正确的有( )//答案是D 　　A 　　可以通过建立二叉搜索树索引使得在集合中查找素的时间复杂度降到O(logN) 　　B 　　可以进行快排，排序后使用二分查找可以使得在集合中查找素的时间复杂度降到O(logN) 　　C 　　可以通过B树索引使得在集合中查找素的时间复杂度降到O(logN) 　　D 　　可以通过hash索引使得在集合中查找素的时间复杂度降到O(1)//这里需要注意的是题目中有要求比较 　　//不满足传递性，ABC都是具有传递性的，所以应该选择D 　　某段文本中各个字母出现的频率分别是{a:4,b:3,o:12,h:7,i:10}，使用哈弗曼编码，则哪种是可能的编码？//答案是A 　　A a(001), b(000), h(01), i(10), o(11) 　　B a(0000), b(0001), h(001), o(01), i(1) 　　C a(000), b(001), h(01), i(10), o(00) 　　D a(0000), b(0001), h(001), o(000), i(1)//这里需要注意的是这种题目，要考虑两点 　　//1、频次越高，编码越短 　　//2、任一字符的编码都不能是另一字符编码的前缀 　　假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为 2，3，7，15，4，6。 　　根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。 　　(这里假定左节点的值小于右节点的值)//答案是A 　　A 86，1011 　　B 70，1000 　　C 86，0001 　　D 70，0010 　　E 92，1000 　　F 92，0100//这里需要注意的是，最短路径长度计算就好，但是编码由于规定左节点的值小于右节点的值 　　//所以，要变，而且左边为0，右边为1 　　在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。//答案是B 　　A 　　正确 　　B 　　错误//这里需要注意的是删除的节点必须是叶子节点，这样结论才成立 　　在有序表(5,8,36,48,50,58,88)中二分查找字58时所需进行的关键字比较次数是（），对应的判定树高度为（）https://www.cnblogs.com/c-learnmore/p// 答案是B 　　A 2,2 　　B 2,3 　　C 3,2 　　D 3,3//根据二分查找的定义，查找58关键字的比较次数是2次，而判定树的高度的是由关键字的比较次数决定的，当比较一次，那么判定树的 　　//深度也就加1，而根节点的高度认为为1，所以对应的判定树的高度为3。 　　对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。//答案是A 　　A 　　95，22，91，24，94，71 　　B 　　92，20，91，34，88，35 　　C 　　21，89，77，29，36，38 　　D 　　12，25，71，68，33，34//这里需要注意的是解题的做法 　　//例如对于A选项，当95为根节点时，后面的是22，表明之后的都是95的左子树 　　//所以，后面的数字应该都比95小，同样的当到91为子树的根节点时，后面接着的是一个 　　//24，表明91后面的是左子树，也就是91后面的数字，必须要比91要小，而94要比91要大 　　//所以，A选项不能构成一条查找路径的序列 　　若一棵二叉树的前序遍历为a, e, b, d, c，后序遍历为b, c, d, e, a，则根节点的孩子节点为（）//答案是A 　　A 　　只有e 　　B 　　有e、b 　　C 　　有e、c 　　D 　　无法确定//这道题需要注意的是，解题的方法 　　//例如，根据前序和后序可以知道的是，a为该树的根节点 　　//假设e为a的左节点，并且a的右节点不为空，那么在后序遍历中应该知道 　　//a的前面应该是a的右节点，但是实际上a的前面的是节点e，所以假设不成立 　　//那么假设e为a的右节点，左节点假设不为空，那么理想中的前序遍历应该是a后面 　　//跟着的应该是a的左节点，但是实际的前序遍历中，a后面跟着的是e，所以假设不成立 　　//所以，a只有一个子节点，那就是e 　　有关广度优先搜索（Breadth-first Search）和深度优先搜索（Depth-first Search），以下说法中正确的是：（）//答案是A 　　A 　　广度优先搜索和深度优先搜索都可以用于遍历一棵树。 　　B 　　在解决迷宫问题时，深度优先搜索总会比广度优先搜索更快地找到迷宫出口。 　　C 　　在解决最短路径问题时，Dijkstra算法（Dijkstra‘s algorithm）本质上是一种考虑了边（Edge）的权重的深度优先搜索。 　　D 　　广度优先搜索需要在搜索的每一层保存该层的所有结点，这一操作只能用队列这种数据结构来完成。 　　//A选项，树是图的一种特殊情况，所以可以使用广度优先和深度优先 　　//B选项，一般情况下，广度要比深度优先更快能找到迷宫出口，因为广度优先搜索的范围要比深度要大 　　//C选项，Dijkstra算法，是广度优先算法 　　//D选项，广度优先，一般情况下使用队列，但是也可以使用数组