第6章习题(带答案)

《第6章习题(带答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.在一棵具有5层的满二叉树中结点总数为()。A.31B.32C.33D.162.深度为d的二叉树中第k（k≤d）层最多有2k-1个结点，最少有1个结点。3.若一棵二叉树中某结点的度为1，则该结点仅有一棵子树。（对）4.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间5.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对6.将一棵有80个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号是1，则编号为30的结点的左

2、孩子编号为60，双亲编号为15。7.在一个非空二叉树的中根遍历序列中，根结点的右边()A)只有左子树上的所有结点B)只有左子树上的部分结点C)只有右子树上的所有结点D)只有右子树上的部分结点8.在一棵二叉树中，第5层上的结点数最多为()。A）8B）15C）16D）329.一棵深度为h的完全二叉树的结点总数的最小值为(2h-1)，从左到右次序给结点编号(从1开始)则编号最小的叶子结点的编号是(2h-2+1)，最大值为(2h-1)。10.在深度为5的完全二叉树中，度为2的结点数最多为(15)个。已知一颗完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树

3、的结点个数最少是()。A.39B.52C.111D.11911.某二叉树中度为2的结点有12个，则该二叉树中有(13)个叶子结点。已知二叉树有50个叶子结点，则此二叉树至少有99个结点。12.3个结点可构成2棵不同形状的树，5棵不同形状的二叉树。13.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉中包含的结点数至少为。A.h+1B.2hC.2h-1D.2h+114.一棵二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树．A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子15.下列关于树的说法中正确的是。A.

4、可有任意多个孩子、任意多个双亲B.可有一个孩子、任意多个双亲C.可有任意多个孩子、只有一个双亲D.只有一个孩子、一个双亲16.若某二叉树的中序序列和后序序列相同，则该二叉树一定满足()。A.该二叉树为空B.其中任意一个结点均无左子树C.只有根结点D.其中任意一个结点均无右子树17.在有n个结点的二叉链表中，空指针域有n+1个，利用这些空指针域，存放某种遍历序列中直接前驱或直接后继的指针，这种附加的指针称为线索。18.若已知某二叉树的先序和后序序列相同，则该二叉树一定满足()。A.其中任意一个结点均无左子树B.其中任意一个结点均无右子树C.只有根结点D.该二叉树

5、为空19.已知完全二叉树的第6层有5个结点，则其叶子结点数是18。20.树的后根遍历序列等同于该树对应的二叉树的（）。A、先序遍历B、中序遍历C、后序遍历D、层次遍历21.已知二叉树先根遍历的序列为“CDHAFEGB”,中根遍历的序列为“HDFAECBG”,则后根遍历的序列为___HFEADBGC。22.若一棵满二叉树深度为h,叶子数为m,结点数为n,则_____。A)n=h+mB)h+m=2nC)m=h-1D)n=2h-123.树可以转换成二叉树,下面关于树和对应的二叉树的说法,_____是正确的。A)树的先根遍历序列与对应的二叉树的先根遍历序列相同B)树的

6、先根遍历序列与对应的二叉树的中根遍历序列相同C)树的后根遍历序列与对应的二叉树的先根遍历序列相同D)树的后根遍历序列与对应的二叉树的后根遍历序列相同24.n个叶子结点的哈夫曼树,结点总数为_____。A)不确定B)2n-1C)2nD)2n+125.在线索二叉树中,判断指针p所指结点没有左子树的条件是_____。A)p->lch==NULLB)p->ltag==1C)p->lch==NULL＆＆p->ltag==1D)以上都不对26.下图所示表达式二叉树的后缀表示式为_____。A)a*b+c-d/eB)+*ab/-cdeC)ab*cd-e/+D)ab*+cd-

7、e/+*ab/cde-26.下面关于树和二叉树的说法中,_____是正确的。A)度为m的树第i层至多有mi-1个结点B)二叉树只能采用链式存储结构C)二叉树就是度为2的树D)度为2的树转换为二叉树后,形态完全一样27.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系()A．不一定相同B．都相同C．都不相同D．互为逆序