2008信息与计算科学专业数据结构习題

个度为2其余度为1。

13. 已知A[1..N]是一棵顺序存储的完全二叉树第n层有多少个节点如何求出A[i]和A[j]的最近的共同祖先？

14．给定K(K>=1),对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度

15．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个

16．一棵共有n个结点的树，其中所有分支结点的度均为K求该树中叶子结点的个数。17． 如在内存中存放一个完全二叉树第n层有多少个节点茬树上只进行下面两个操作： （1）寻找某个结点双亲 （2）寻找某个结点的儿子； 请问应该用何种结构来存储该二叉树？

18．求含有n个结点、采用顺序存储结构的完全二叉树第n层有多少个节点中的序号最小的叶子结点的下标要求写出简要步骤。

19．设二叉树T中有n个顶点其编号為1，23，…,n,若编号满足如下性质： （1）T中任一顶点v的编号等于左子树中最小编号减1；

（2）对T中任一顶点v,其右子树中最小编号等于其左子树Φ的最大编号加1试说明对二叉树中顶点编号的规则（按何种顺序编号）。

20．若一棵树中有度数为1至m的各种结点数为n1,n2,…,nm(nm表示度数为m的结点個数)请推导出该树中共有多少个叶子结点n0的公式

21．若一棵完全二叉树第n层有多少个节点中叶子结点的个数为n,且最底层结点数