搜索
数据结构基础练习（二叉树）学号姓名班级.一、选择题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个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为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)n=2h-19．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是A。(A)二叉树不存在(B)若二叉树不为空，则二叉树的深度等于结点数(C)若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子(D)若二叉树不为空，则任一结点的度均为110．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用C遍历实现编号。(A)先序(B)中序(C)后序(D)层序11．一个具有1025个结点的二叉树的高h为C。(A)10(B)11(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．已知一棵二叉树的中序序列是cbedahgijf，后序序列是cedbhjigfa，则该二叉树的先序序列是abcdefghij，该二叉树的深度为5。5．若一棵二叉树的中序遍历结果为ABC，则该二叉树有3中不同的形态。6．在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是log2i==log2j。7．已知完全二叉树的第7层有8个结点，则其叶子结点数为36个。总结点数为71个。8．在对二叉树进行非递归中序遍历过程中，需要用栈来暂存所访问结点的地址；进行层序遍历过程中，需要用队列来暂存所访问结点的地址。三、应用题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;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-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-dataBT-right-data){BTreeNode*t=BT-left;BT-left=BT-right;BT-right=t;}BTC(BT-left);BTC(BT-right);}}函数的功能：调整二叉树，使树中左子树结点的值小于等于右子树结点的值。5.设BT指向一颗二叉树，该二叉树的广义表表示为a(b(a,d(f)),c(e(,a(k)),b))，则依次使用BTC1(BT’a’,C)、BTC1(BT’b’,C)、BTC1(BT’c’,C)和BTC1(BT’g’,C)调用下面算法时，假定每次调用时C的初值为0，引用变量C的带回值依次为3、2、1和0。voidBTC1(BTreeNode*BT,charx,int&k){if(BT!=NULL){if(BT-data==x)k++;BTC1(BT-left,x,k);BTC1(BT-right,x,k);}}五、算法设计题（参照上题，并总结有关二叉树操作实现的常用方法）1．编写求二叉树BT中结点总数的算法。intBTreeCount(BTreeNode*BT){if(BT==NULL)return0;elseif(BT-left==NULL&&BT-right==NULL)return1;elsereturnBTreeCount(BT-left)+BTreeCount(BT-right)+1;}2．编写求二叉树BT中叶子结点数的算法。intBTreeLeafCount(BTreeNode*BT){if(BT==NULL)return0;elseif(BT-left==NULL&&BT-right==NULL)return1;elsereturnBTreeLeafCount(BT-left)+BTreeLeafCount(BT-right);}3．若已知两棵二叉树BT1和BT2皆为空，或者皆不为空且BT1的左、右子树和BT2的左、右子树分别相似，则称二叉树BT1和BT2相似。编写算法，判别给定的两棵二叉树是否相似。intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2){if(BT1==NULL&&BT2==NULL)return1;elseif(BT1==NULL||BT2==NULL)return0;elsereturnSimilarTrees(BT1-left,BT2-left)&&SimilarTrees(BT1-right,BT2-right);}