数据结构考研试题精选及答案第6章 树和二叉树答案(7)

结点没有分枝，故二叉树的结点数n与分枝数B有如下关系

n=B+1=n1+2*n2+1 .(2)

由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点

中有（m-1）个度为2，其余度为1。

14．根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是 i/2 ，故A[i]和

A[j]的最近公共祖先可如下求出：

while(i/2!=j/2)

if(i>j) i=i/2; else j=j/2;

退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2。

15．N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，第

i-12H-1 i(1<=i<=H)层的结点数K，则N=1+k+k+ + k，由此得H= logK(N(K-1)+1)

16. 结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。

17．设分枝结点和叶子结点数分别是为nk和n0，因此有n=n0+nk (1)

另外从树的分枝数B与结点的关系有 n=B+1=K*nk +1

(2)

由（1）和（2）有 n0=n-nk=(n(K-1)+1)/K

18.用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是 i/2 (i=1

时无双亲)，其左子女是2i(若2i<=n,否则i无左子女)，右子女是2i+1(若2i+1<=n,否则无

右子女)。

19. 根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是 n/2 ，这是

最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是

n/2 +1。

20. 按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。

21. 设树的结点数为n，分枝数为B，则下面二式成立

n=n0+n1+n2+ +nm (1)

n=B+1= n1+2n2+ +mnm (2)

m

由(1)和(2)得叶子结点数n0=1+ (i 1)ni 1i

22. log2n +1 23.15

24. 该结论不成立。对于任一a

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数据结构考研试题精选及答案第6章 树和二叉树答案(7)全文阅读和word下载服务。