第六章树和二叉树练习

《第六章树和二叉树练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章树和二叉树一、选择题1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．82.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．

2、条件不足，无法确定4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定5．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M36．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对7.有n个叶子的哈夫曼树的结点总数为（）。A．不确定B．2nC．2n+1

3、D．2n-18.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为29．一棵二叉树高度（深度）为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+110．在一棵高度（深度）为k的满二叉树中，结点总数为（）4A．2k-1B．2kC．2k-1D．ëlog2kû+111．在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示

4、法D．顺序存储表示法12．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADBCFEG13．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定14．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba15．二叉树的先序遍历和中序

5、遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：A、EB、F　C、G　D、H16．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树17.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点18.引入二叉线索树的目的是（）A．加快查找结点的

6、前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一19．n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n20．下述编码中哪一个不是前缀码（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）21.一棵有n个结点的完全4二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩

7、子在数组A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．条件不充分，无法确定****一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．条件不充分，无法确定二、判断题1.二叉树的遍历只是为了在应用中找到一种线性次序。（）2．对一棵二叉树进行层次遍历

8、时，应借助于一个栈。（）3．由一棵二叉树的前序序列和后序序列可以唯一确定它。（）4．完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）5.给定一棵树，可以找到唯一的一棵二叉树与之对应。（）6．在二叉树的第i层上至少有2i-1个结点(i>=1)。（）7．完全二叉树的存储结构通常采用顺序存储结构。（）8．将一棵树转成二叉树，根结点没有左子树；（）9．树与二叉树是两种不同的树型结构。（）10．霍夫曼树的结点个数不能是偶数。（）11．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）