请教:2011年软件设计师考试考前密卷(二)－上午试题第1大题第20小题如何解答?【题目描述】●n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为 (45) 个，其中 (46) 个用于链接子结点， (47) 个空闲着。(45)A．n B．n-1 C．n+1 D．n-2(46) A．n-1 B．n C．n+1 D．n-2(47) A．n+10 B．n C．n+1 D．n+9

题目

请教:2011年软件设计师考试考前密卷(二)－上午试题第1大题第20小题如何解答?

【题目描述】

●n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为 (45) 个，其中 (46) 个用于链接子结点， (47) 个空闲着。

(45)

A．n

B．n-1

C．n+1

D．n-2

(46) A．n-1

B．n

C．n+1

D．n-2

(47) A．n+10

B．n

C．n+1

D．n+9

参考答案和解析

问题1

【参考答案与解析】：

正确答案：B

问题2

【参考答案与解析】：

正确答案：A

问题3

【参考答案与解析】：

正确答案：C

答案分析：

【解析】①二叉树中每个结点有两个子链域，故n个结点有n-1个左、右子链域。②除根结点之外,其他每个结点都有且仅有一个分支，故n个结点的二叉树中有n-1个分支；而这些分支是由上一层结点的子链域发出的，因此n个结点的二叉树中有n-1个链域链接孩子。③空闲的孩子链域数=2n-（n-1)=n+1。

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

●n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为 (45) 个，其中 (46) 个用于链接子结点， (47) 个空闲着。

(45) A．n

B．n-1

C．n+1

D．n-2

(46) A．n-1

B．n

C．n+1

D．n-2

(47) A．n+10

B．n

C．n+1

D．n+9

正确答案：B,A,C
【解析】①二叉树中每个结点有两个子链域，故n个结点有n-1个左、右子链域。②除根结点之外,其他每个结点都有且仅有一个分支，故n个结点的二叉树中有n-1个分支；而这些分支是由上一层结点的子链域发出的，因此n个结点的二叉树中有n-1个链域链接孩子。③空闲的孩子链域数=2n-（n-1)=n+1。

第2题：

请教:全国计算机等级考试二级Access考前密卷(2)第1大题第小题如何解答?

【题目描述】

第 33 题若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（　　）。

A．bdgcefha

B．gdbecfha

C．bdgaechf

D．gdbehfca

正确答案：D

第3题：

齐次坐标表示法就是由n＋1维向量表示一个()

A.n-1维向量

B.n维向量

C.n+1维向量

D.n+2维向量

参考答案：B

第4题：

请教:计算机等级考试二级公共基础知识练习题(1)第2大题第11小题如何解答?

【题目描述】

(11) 设一棵完全二叉树共有 500 个结点，则在该二叉树中有______个叶子结点。

【参考答案分析】：

答：250

设no为度为0的节点数
n1为度为1的节点数
n2为度为2的节点数
n=n0+n1+n2 (1)
根据二叉树定义
n=n1+2*n2+1 (2)
由(1)(2)得
n2=n0-1 (3)
(3)代入(1)
n=2n0+n1-1
500=2n0+n1-1
n1只可能为1或0这里显然为1
n0=250

根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则n0=n2+1.
根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1.
所以:n0+n1+n2=500
n0=n2+1;
2n0=501-n1;
因为结点数为整数，所以n1=1,n0=250

第5题：

n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为(45)个，其中(46)个用于链接子结点，(47)个空闲着。

A．n

B．n-1

C．n+l

D．n-2

正确答案：B

第6题：

请教:2011年网络工程师考试考前密卷(一)－上午试题第1大题第3小题如何解答?

【题目描述】

●一个32K×32位的主存储器，其地址线和数据线的总和为 (3) 根。

A．64

B．47

C．48

D．36

正确答案：B

答案分析：

【解析】32K×32位的存储器，其数据线需要32根；32K是其容量大小，根据2的n次幂=32×1024可以计算出：n=15。于是至少需要15根地址线，所以，所需的地址和数据线总和为47。

第7题：

一棵完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有____个结点。

A.24

B.45

C.46

D.47

正确答案：C

第8题：

请教:2007年9月全国计算机等级考试二级Access笔试试题第1大题第8小题如何解答?

【题目描述】

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

A．219

B．221

C．229

D．231

正确答案：A

第9题：

请教:2011年计算机等级考试二级C语言专家压密试卷(1)第3大题第13小题如何解答?

【题目描述】

第 53 题设一棵完全二叉树共有839个结点，则在该二叉树中有_________个叶子结点。

【参考答案分析】：420

满二叉树是没有度为1的结点。

完全二叉树定义：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

完全二叉树叶子结点的算法：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。

因此叶子结点数是(839+1)/2=420

您好！
满二叉树是没有度为1的结点。完全二叉树定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。完全二叉树叶子结点的算法：如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。因此叶子结点数是(839+1)/2=420

第10题：

具有n个结点的二叉树，采用二叉链表存储，共有______个空链域。

A．n-1

B．n

C．n+1

D．由于二叉树形态不定导致空链域个数不定

正确答案：C
解析：当采用二叉链表存储时，每个结点有两个指针域，分别指向左右子树的根结点，当有n个结点时共有2n个指针，又因为除根结点外每个结点都需要一个指针指向自己，所以就剩下2n-(n-1)=n+1个空链域。

题目

参考答案和解析

相似问题和答案

更多相关问题

相关内容