域名买来可以做网站吗,哪个网站可以做条形码,网站描述代码怎么写,北京一度网站建设选填题考的很多都是基础概念#xff0c;对于巩固复习一些仡佬拐角的知识点是很有用的。非北航学生也可以来看看这些题#xff0c;这一节主要是树方面的习题#xff1a; 一、 我们首先需要知道一个公式 这是证明#xff1a; 知道了这个公式#xff0c;我们把题目中的数据…选填题考的很多都是基础概念对于巩固复习一些仡佬拐角的知识点是很有用的。非北航学生也可以来看看这些题这一节主要是树方面的习题 一、 我们首先需要知道一个公式 这是证明 知道了这个公式我们把题目中的数据带入即可 n0n22n33n41 12 * 103 * 201 82 二、 两个知识点 1、二叉树的分支个数等于节点个数-1适用于任何二叉树则mn-1 2、满二叉树的深度与结点个数之间的关系n2^h-1 , hlog(n1)。 因此选D很明显 三、 这个题蛮有意思正着想不太好想那我们就把每个选项都试一试看看哪个符合要求。 A.空和仅有一个节点前序遍历和后序遍历长得一样要说相反好像勉强也行。这个选项暂时保留大概率肯定不是我们往下看。
B.我们画个图实际演示一下 前序遍历A B C D E 后序遍历E D C B A 诶好像可以诶但是别高兴太早了我们发现D选项囊括了B选项那我们就要思考一下这种情况会不会不全面呢
C.其实有了上一个题的疑问我们实际可以直接先验证D选项
这是一个分支节点的度都为1的树我们来验证一下他的前后序遍历 前序遍历A B C D E 后序遍历E D C B A 正好相反因此正确答案为D 四、 这道题的正确答案应该是A。 二叉查找树的查找效率由平均查找长度ASL来决定 查找第一层的元素需要比较1次查找第二层的元素需要比较2次……查找第n层的元素需要查找n次那么上述树的平均查找长度就为1 * 1 2 * 2 3 * 4 4 * 2/925/9
在来看时间复杂度理想情况下查找一个元素需要比较的最多次数为深度次也就是从树冠比到树根那么时间复杂度就是O(h),hlogn (我们这里只说数量级不考虑具体是满二叉树还是完全二叉树还是普通二叉树时间复杂度也可以表示为O(logn。也就是说二叉查找树查找的时间复杂度是由深度决定的。
注意当二叉查找树退化时也就是说差不多快变成一个链表的时候左右子树深度之差过大那么这个时候查找的时间复杂度就和在链表里查找的时间复杂度差不多了就变成O(n)了。 六、 这道题的正确答案应该为D 但是我对此存疑我再问问助教去…… 七、 中缀转前缀的方法为 从右到左扫描表达式 遇到操作数直接输出输出顺序从右到左 遇到操作符 1.遇到 ‘ ’入栈 2.操作符栈空入栈 3.当前操作符优先级 栈顶操作符入栈注意中缀转后缀是要大于才入栈 4.当前操作符优先级 栈顶操作符栈顶操作符出栈然后与新的栈顶元素比较直到栈空或优先级大于等于栈顶操作符或遇到‘ ’ 时入栈。 遇到括号 1.遇到右括号入栈 2.遇到左括号将栈内运算符依次弹出并从右到左输出直到遇到左括号左括号弹出但左括号不输出 将栈内剩余操作符从右到左依次弹出并输出 八、 前缀编码任何一个编码都不能成为其他编码的前缀但是B中10是101的前缀。 九、 先来了解一下哈夫曼树的构造原理 1.树的带权路径长度WPL wi为第i个叶结点被赋予的权值li为根节点到第i个叶结点的路径长度
2.哈夫曼树的定义 给定一组权值构造出的具有最小带权路径长度的二叉树即哈夫曼树 3.哈夫曼树特点 权值越大离根越近权值越小离根越小 无度为1的节点 哈夫曼树不唯一
4.哈夫曼树的构造
对于给定的权值W{w1,w2,…… ,wm},构造出树林F{T1,T2,…… ,Tm}其中Ti为左右子树为空且根节点的权值为wi的二叉树将F中根节点权值最小的两棵二叉树合并成为一棵新的二叉树将这两棵二叉树作为新二叉树的左右子树并将新二叉树的根结点的权值定为这两棵二叉树权值的和。将新二叉树加入F同时从F中删除之前的两棵二叉树重复上一步直到F中只有一棵二叉树。 按照上述步骤我们构造出了一棵哈夫曼树那么带权路径长度就为 2 * 3 3 * 3 5 * 2 6 * 2 9 * 2 55 二、 度为k那么要求最多个结点我们就让每个分支节点的度都为K那么第一层就有k^0个结点 第二层有k^1个 第三层k^2, 第四层k^3 以此类推第i层最多就有k^(i-1)个节点 三、 满二叉树的深度和结点个数关系n2^h-1,则hlog(n1),可得深度为log(2048)11,最后一层的节点个数也就是叶结点个数为n2 ^ (h-1)2 ^ 10 1024。 四、 先恢复一下二叉树
那么后续序列就为
HIDJEBFGCA 五、 每个结点都有left和right两个指针因此共有2n个指针域 分支节点个数等于节点个数减一那么就意味着n-1个指针指向孩子节点剩下的2n-(n-1)n1个指针域就指向空 六、 先恢复一下二叉树 那么后序遍历结果就是DCBFGEA 七、 处在同一层说明深度一样 2^ (h-1) - 1 i 2 ^ (h) - 1 2^ (h-1) - 1 j 2 ^ (h) - 1 八、 这个注意做减法和除法的时候先弹出的减除后弹出的和后缀表达式计算不太一样。 九、 建立好的二叉查找树如上图62先和54比再和73比再和62比发现找到结束比较工比较三次。 十、 则带权路径长度为4×35×38×26×27×2121516121469
