数据结构基础练习(第5章二叉树)

《数据结构基础练习(第5章二叉树)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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．将一

2、棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为B。(A)98(B)99(C)50(D)没有右孩子6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有D为空。(A)50(B)99(C)100(D)1017．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为C。(A)2h(B)2h-1(C)h(D)h+18．对一棵满二叉树，m个树叶，n个结点，深度为h，则D。(A)n=h+m(B)h+m=2n(C)m=h-1(D

3、)n=2h-19．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是A。(A)二叉树不存在(B)若二叉树不为空，则二叉树的深度等于结点数(C)若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子(D)若二叉树不为空，则任一结点的度均为110．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用C遍历实现编号。(A)先序(B)中序(C)后序(D)层序11．一个具有1025个结点的二叉树的高h为C。(A)10(B)11

4、(C)11~1025(D)10~102412．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是C。(A)n在m右方(B)n是m祖先(C)n在m左方(D)n是m子孙二、填空题1．对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支二叉树时，具有最大高度。2．在二叉树的第i（i≥1）层上至多有2i-1个结点，深度为k（k≥1）的完全二叉树至多2k-1个结点，最少2k-1个结点；3．如果二叉树的终端结点数为n0，度为2的结点数为n2，则n0=n2-1。4．已知一棵二叉

5、树的中序序列是cbedahgijf，后序序列是cedbhjigfa，则该二叉树的先序序列是abcdefghij，该二叉树的深度为5。5．若一棵二叉树的中序遍历结果为ABC，则该二叉树有3中不同的形态。6．在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是log2i==log2j。7．已知完全二叉树的第7层有8个结点，则其叶子结点数为36个。总结点数为71个。8．在对二叉树进行非递归中序遍历过程中，需要用栈来暂存所访问结点的地址；进行层序遍历过程中，需要用队列来暂存所访问结点的地址。三、应用

6、题1.有n个结点的二叉树，已知叶子结点个数为n0,回答下列问题：(1)写出求度为1的结点的个数n1的计算公式；n1=n+1-2n0(2)若此树是深度为k的完全二叉树，写出n为最小的公式；nmin=2k-1(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式；n=2n0-1四、算法分析题教材p208习题5-2中：1、2、4、5四题1.返回二叉树BT中值为X的结点所在的层号。intNodeLevel(BTreeNode*BT,ElemTypeX){if(BT==NULL)return0

7、;elseif(BT->data==X)return1;else{intc1=NodeLevel(BT->left,X);if(c1>=1)returnc1+1;intc2=NodeLevel(BT->right,X);if(c2>=1)returnc2+1;return0;}}2.指出下面函数的功能。BTreeNode*BTreeSwopX(BTreeNode*BT){if(BT==NULL)returnNULL;else{BTreeNode*pt=newBTreeNode;pt->data=BT-

8、>data;pt->right=BTreeSwopX(BT->left);pt->left=BTreeSwopX(BT->right);returnpt;}}函数的功能：交换二叉树的左右子树，生成新的二叉树。4.指出下面函数的功能。voidBTC(BTreeNode*BT){if(BT!=NULL){if(BT->left!=NULL&&BT->right!=NULL)if(BT->left->data>BT->right->data){BTreeNod