数据结构练习4

1、数据结构练习(二叉树)一、选择题1按照二义树定义，具有3个结点的二义树共有C种形态。(A) 3 (B) 4 (C) 5 (D) 62. 具有五层结点的完全二叉树至少有D个结点。(A) 9 (B) 15 (C) 31 (D) 163. 以下有关二叉树的说法正确的是B。(A)二义树的度为2 (B)棵二叉树的度可以小于2(C)至少有一个结点的度为2 (D)任一结点的度均为24. 已知二义树的后序遍历是dabec,中序遍历是debac,则其前序遍历是D。(A)acbed (B)decab (C) deabc (D) cedba5. 将一棵有1000个结点的完全二义树从上到下，从左到右依次进行编号，根结

2、点的编号为1,则编号为49的结点的右孩子编号为B o(A) 9899 (C) 50 (D)没有右孩子6. 对具有100个结点的二义树，若有二叉链表存储，则其指针域共有D为空。(A) 50 (B) 99 (C) 100 (D) 1017. 设二叉树的深度为h,且只有度为1和0的结点，则此二义树的结点总数为(A) 2h (B) 2h-l (C) h (D) h+1&对一棵满二叉树,m个树叶,n个结点，深度为h,则D。(A) n二h+m (B) h+m二2n (C)m=h-1 (D)n二2hT9. 某二叉树的先序序列和后序序列正好相反，则下列说法错误的是A。(A) 二叉树不存在(B) 若二叉树不为空

3、，则二义树的深度等于结点数(0若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子(D)若二叉树不为空，则任一结点的度均为110. 对二义树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子 的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号,可采用C遍 历实现编号。(A)先序(B)中序(C)后序(D)层序11. -个具有1025个结点的二叉树的高h为C o(A) 10 (B)ll (O1T1025 (D) 10102412. 设n, m为一棵二叉树上的两个结点，在中序遍历时,n在m前的条件是C O(A) n在m右方(B) n是m祖先(C) n在m左方(D) n是m子孙13.

4、 实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是 二叉树采用C存储结构。(A)二叉链表(B)广义表(C)三叉链表(D)顺序14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是A。(A) 树的先根遍历序列与其对应的二叉树的先序遍历相同(B) 树的后根遍历序列与其对应的二义树的后序遍历相同(0树的先根遍历序列与其对应的二叉树的中序遍历相同(D) 以上都不对二、填空题1. 对一棵具有n个结点的二叉树，当它为一棵完全二义树时具有最小高度；当 它为单分支时，具有最大高度。2. 在二义树的第i (i$l)层上至多有2i-l个结点，深度为k(kl)的完全二叉 树至多2k-l个结点，

5、最少2k-l个结点；3. 如果二叉树的终端结点数为nO,度为2的结点数为n2,则n0n2+l。4. 已知一棵.叉树的中序序列是cbedahgi jf,后序序列是cedbhjigfa,则该二 义树的先序序列是abcdefghij，该二叉树的深度为5 o5. 若一棵二叉树的中序遍历结果为ABC,则该二义树有5中不同的形态。6. 在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是Iog2i=log2j 。7. 已知完全二义树的第7层有8个结点，则其叶子结点数为36个。总结点数 为71个。8. 在对二义树进行非递归中序遍历过程中，需要用栈来暂存所访问结点的地址; 进行层序遍历过程中，需要用

6、队列来暂存所访问结点的地址；9. 高度为h,度为k的树中至少有h+k-l个结点，至多有(k n-l)/(k-l)个结 点。10. 一维数组存放完全二叉树:ABCDEFGHI,则后序遍历该二义树的序列为 HIDEBFGCA 。三、应用题1. 应用题：说明分别满足下列条件的.二义树各是什么？(1) 先序遍历和中序遍历相同；中序遍历和后序遍历相同；(3)先序遍历和后序遍历相同；思考:TLR、LTR、LRT(1) 空树、只有根结点、右单分支二叉树；(2) 空树、只有根结点、左单分支二义树(3) 空树、只有根结点2. 已知一棵二义树的中序序列是cbedahgi jf,后序序列是cedbhjigfa,画出

7、 这棵二义树的逻辑结构图。3. 棵二叉树的先序、中序、后序序列如下，其中一部分未标出，试构造出该 二叉树。先序序列：ABCDEFGHIJK中序序列:C BEDFAHJKIG后序序列：CEFDBKJIHGA4. 有n个结点的二叉树，已知叶子结点个数为nO,回答下列问题：(1) 写出求度为1的结点的个数nl的计算公式；(2) 若此树是深度为k的完全二义树，写出n为最小的公式；(3) 若二义树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公 式；(1) 记度为2的结点个数为n2,则n二n0+nl+n2,另一方面，除了根结点以外，其 余结点均有父结点的分支射出，所以结点数n二l+nl+2柏2;

8、综合上面两式可得 nl=n+l2n0o(2) 当树是深度为k的完全二义树时,n的最小值n min=2k-l;(3) 当二义树中仅有度为0和2的结点时，二义树的结点个数n二2n0-1。四、算法设计题1. 编写求二义树BT中结点总数的算法。int BTreeCount (BTreeNode *BT) /二叉树中结点的总数if(BT二二NULL)return 0;else 辻(BT-left =NULL&BT-right 二二NULL)return 1;elsereturn BTreeCount(BT-left ) BTreeCount(BT-right ) + 1;2. 编写求二叉树BT中叶子结点

9、数的算法。int BTreeCount (BTreeNode *BT) / .X树中结点的总数辻(BT二二NULL)return 0;else 辻(BT-left =NULL&BT-right 二二NULL)return 1;elsereturn BTreeCount(BT-left ) BTreeCount(BT-)right );3. 若已知两棵二义树BT1和BT2皆为空，或者皆不为空且BT1的左、右子树和 BT2的左、右子树分别相似，则称二叉树BT1和BT2相似。编写算法,判别给定的两 棵二叉树是否相似。int BTreeSim(BTreeNode *BT1, BTreeNode *BT

10、2) /判断两棵二叉树是否相 似if(!BTl&!BT2) return 1;else if (!BT1!BT2) return 0;elsereturn BTreeSim(BTl-lchild, BT2-lchile)&BTreeSim(BTl-rchild,BT2- rchild);4. 编写算法，求二义树中以元素值为x的结点为根的子树的深度。int Get_Sub_Depth(BTreeNode *BT , ElemType x) /值为 x 的结点为根的 子树的深度if(!BT) return 0;else if(BT-data=x) return DepthBTree(BT);els

11、e if(BT-lch订d!二NULL) return Get_Sub_Depth(BT-lch订d , x);else 辻(BT-rchild!二NULL) return Get_Sub_Depth(BT-rchild, x);else return 0;int DepthBTree (BTreeNode *BT) /求二义树 BT 的深度if (!BT) return 0; /空树深度为 0else int depl二DepthBTree(BT-lchiid) ; /先求根结点左子树的深度int dep2=DepthBTree(BT-rchild) ; /再求根结点右子树的深度 辻(dep

12、ldep2) /返回最大值，并加上根结点这一层return depl+1;elsereturn dep2+l;5. 编写算法，计算二叉树中度为1的结点数和度为2的结点数。int si二0, s2=0;void BTreebranch(BTreeNode *BT) 辻（BT!二NULL） 辻（BT-lchild!二NULL） 辻（BT-rchild!=NULL） s2+;else sl+;BTreebranch（BT-lchild）;辻（BT-rchild!二NULL） 辻（BT-lchild!二NULL） sl+;BTreebranch（BT-rchild）;6. 试利用栈的基本操作编写一个先序遍历的非递归算法。若二义树非空，首先访问根结点并将其地址进栈，然后沿着左链遍历根结点的 左子树。若二义树为空，则弹出栈顶元素，取得最近访问过的根结点地址，然后沿右 链遍历根结点的右子树。【算法源代码】void PreOrder