第四章树历年试题
第四章树
⼀、单项选择题
201101--2.树形结构中，度为0的结点称为( )
A.树根
B.叶⼦
C.路径
D.⼆叉树
201101--9.⼆叉树的第i（i≥1）层上所拥有的结点个数最多为( )
A.2i
B.2i
C.2i-1
D.2i-1
201101--14.如果结点A有3个兄弟结点，⽽且B为A的双亲，则B的度为( )
A.1
B.3
C.4
D.5
201001--2.某⼆叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（）
A.acbed
B.becab
C.deabc
201001--3.含有n个结点的⼆叉树⽤⼆叉链表表⽰时，空指针域个数为( )
A.n-1
B.n
C.n+1
D.n+2
200910--5.由带权为9，2，5，7的四个叶⼦结点构造⼀棵哈夫曼树，该树的带权路径长度为（）
A.23
B.37
C.44
D.46
200901--8.具有n个结点的⼆叉树，拥有指向孩⼦结点的分⽀数⽬是（）
A.n-1
B.n
C.n+1
D.2n
200901--9.对⼀棵有100个结点的完全⼆叉树按层序编号，则编号为49的结点，它的左孩⼦的编号为（）
A.99
B.98
C.97
D.50
200901--10.有m个叶⼦结点的哈夫曼树，其结点总数是（）
A.2m-1
B.2m
C.2m+1
D.2（m+1）
200901--14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插⼊结点的⽅法⽣成⼀棵⼆叉排序树，则该树的深度为（）(根据新教材的内容应安排在查)
A.4
B.5
C.6
D.7
200810--8.含有n个结点的⼆叉树采⽤⼆叉链表存储时，空指针域的个数为（）
A.n-1
B.n
C.n+1
D.n+2
200810--9.在⼀棵深度为H的完全⼆叉树中，所含结点的个数不少于．．．（）
A.2H-1
-1 B.2
H-1
C.2
H
-1 D.2
H
200810--12.对⼀棵⼆叉排序树采⽤中根遍历进⾏输出的数据⼀定是（）
A.递增或递减序列
B.递减序列
C.⽆序序列
D.递增序列
200801--8.某⼆叉树的先根遍历序列和后根遍历序列正好相反，则该⼆叉树具有的特征是( )
A.⾼度等于其结点数
B.任⼀结点⽆左孩⼦
C.任⼀结点⽆右孩⼦
D.空或只有⼀个结点
200801--9.在完全⼆叉树中，若⼀个结点是叶结点，则它没有( )
A.左孩⼦结点
B.右孩⼦结点
C.左孩⼦结点和右孩⼦结点
D.左孩⼦结点，右孩⼦结点和兄弟结点200801--12.若构造⼀棵具有n个结点的⼆叉排序树，最坏的情况下其深度不超过( )
A. B. n C. D. n+1
200710--8.除根结点外，树上每个结点( )
A.可有任意多个孩⼦、⼀个双亲
二叉树的基本性质
B.可有任意多个孩⼦、任意多个双亲
C.可有⼀个孩⼦、任意多个双亲
D.只有⼀个孩⼦、⼀个双亲
200710--9.题9图中树的度为( )
A.2
B.3
C.5
D.8
题9图
200701--10．⾼度为h的完全⼆叉树中，结点数最多为（）
A．2h-1 B.2h+1 C.2h
-1 D.2
h
200701--11．由m棵结点数为n的树组成的森林，将其转化为⼀棵⼆叉树，则该⼆叉树中根结点的右⼦树上具有的结点个数是（）A．-1 C.n(m-1) D.m(n-1)
200610--8.含有10个结点的⼆叉树中，度为0的结点数为4，则度为2的结点数为（）
A.3
B.4
C.5
D.6
200610--9.对⼀棵有100个结点的完全⼆叉树按层编号，则编号为49的结点，它的⽗结点的编号为（）
A.24
B.25
C.98
D.99
200610--10.可以惟⼀地转化成⼀棵⼀般树的⼆叉树的特点是（）
A.根结点⽆左孩⼦
B.根结点⽆右孩⼦
C.根结点有两个孩⼦
D.根结点没有孩⼦
200601--7.关于⼆叉树性质的描述，正确的是（）
A.⼆叉树结点的个数可以为0
B.⼆叉树⾄少含有⼀个根结点
C.⼆叉树若存在两个结点，则必有⼀个为根，另⼀个为左孩⼦
D.⼆叉树若存在三个结点，则必有⼀个为根，另两个分别为左、右孩⼦
200601--8.具有4个结点的⼆叉树可有（）
A.4种形态
B.7种形态
C.10种形态
D.11种形态
200601--9.若采⽤邻接表存储结构，则图的深度优先搜索类似于⼆叉树的（）
A.先根遍历
B.中根遍历
C.后根遍历
D.层次遍历
⼆、填空题
201101--23.在树形结构中，没有后继的结点是___________结点。
201101--24.⼀棵深度为n(n>1)的满⼆叉树中共有___________个结点。
201010--23．有m个叶结点的哈夫曼树所具有的结点数为_______。
201010--24．在⼀棵具有n个结点的完全⼆叉树中，从树根起，⾃上⽽下、⾃左⾄右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩⼦，那么其右孩⼦的编号为_______。201010--25．在⼀棵树中，_______结点没有前驱结点。
201001--24.对于⼀棵满⼆叉树，若有m个叶⼦，则树中结点数为____________。
200910--21.若满⼆叉树的结点数为n，则其⾼度为________。
200910--22.在⼀棵具有n个结点的完全⼆叉树中，从树根起，⾃上⽽下、从左到右地给所有结点编号。
若编号为i的结点有⽗结点，那么其⽗结点的编号为________。
200910--23.深度为k的⼆叉树，结点数最多有________个。
200910--24.某⼆叉树的后根遍历为ABKCBPM，则该⼆叉树的根为________。
200901--22.深度为k的⼆叉树⾄多有 _________个结点，最少有 _________个结点。200810--19.对⼀棵深度为10的满⼆叉树按层编号，则编号为51的结点，它的双亲结点编号为________。
200810--21.具有n个叶⼦结点的哈夫曼树，其结点总数为________。
200810--22.⼀棵具有n个结点的树，所有⾮终端结点的度均为k，则该树中叶⼦结点个数为________。
200810--25.某⼆叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。
200801--20.深度为15的满⼆叉树上，第11层有____________个结点。
200801--21.对⼀棵有100个结点的完全⼆叉树按层编号，则编号为49的结点，它的左孩⼦的编号为____________。
200801--24.在⼀棵⼆叉排序树上按____________遍历得到的结点序列是⼀个有序序列。
200710--20.设F、C是⼆叉树中的两个结点，若F是C的祖先结点，则在采⽤后根遍历⽅法遍历该⼆叉树时，F和C的位置关系为：F必定在C的__________。
200710--21.若⽤后根遍历法遍历题21图所⽰的⼆叉树，其输出序列为__________。
题21图
200701--21．有4个结点且深度为4的⼆叉树的形态共有_______种。
200701--22．某⼆叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该⼆叉树中根结点的右孩⼦是_______。200701--25．⼀棵平衡⼆叉树中任⼀结点的平衡因⼦只可能是_______。
200610--21.三个结点可构成________种不同形态的⼆叉树。
200610--22.对于⼀棵具有n个结点的⼆叉树，当进⾏链接存储时，其⼆叉链表中的指针域的总数为2n个，其中________个⽤于链接孩⼦结点。
200610--24.对⼆叉排序树进⾏________遍历，可得到排好序的递增结点序列。
200601--22.深度为k的满⼆叉树其叶⼦结点个数共有________________个。
200601--23.⼆叉树通常采⽤________________两种存储结构表⽰。
三、应⽤题
201101--30.⼀棵⼆叉树的前根遍历序列为ABCDEFG，中根遍历序列为CBDAEGF，试构造出该⼆叉树。
31.下述矩阵表⽰⼀个⽆向连通⽹，试画出它所表⽰的连通⽹及该连通⽹的最⼩⽣成树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。