数据结构考研分类复习真题 第六章 树和二叉树 (四)[6]

．假设高度为H的二叉树上只有度为和度为的结点问此类二叉树中的结点数可能达到的最大值和最小值各为多少？【北京邮电大学 一 (分)】

．一棵满k叉树按层次遍历存储在一维数组中试计算结点下标的u的结点的第i个孩子的下标以及结点下标为v的结点的父母结点的下标【北京邮电大学 四(分)】

．二叉树有n个顶点编号为… n设

* T中任一顶点V的编号等于左子树中最小编号减

* T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加

试描绘该二叉树【东南大学 一 (分)】

．设T是具有n个内结点的扩充二叉树I是它的内路径长度E是它的外路径长度

()试利用归纳法证明E=I+n n>=(分)

()利用()的结果试说明成功查找的平均比较次数s与不成功查找的平均比较次数u 之间的关系可用公式表示s=(+/n)un>=【清华大学 四 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []