数据结构基础练习

《数据结构基础练习》由会员分享，可在线阅读，更多相关《数据结构基础练习（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(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-l (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) 若二

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

4、1是in子孙二、填空题1. 对一棵具有n个结点的二叉树，当它为一棵完全 二叉树时具有最小高度:当它为单分支二叉树时,具有最大高度。2. 在二叉树的第i (il)层上至多有2用 个结点，深度为k (kl)的完全二叉树至多2k-l个结点,最少2心 个结点:3. 如果二叉树的终端结点数为no,度为2的结点数为则no = n2-l4. 己知一棵二叉树的中序序列是cbedahgijf,后序序列是cedbhjigfa,则该二叉树的先序 序列是abcdefqhii ,该二叉树的深度为5 5. 若一棵二叉树的中序遍历结果为ABC,则该二叉树有3中不同的形态。6. 在顺序存储的二叉树中，下标为1和i的两个结点处

5、在同一层的条件是 Ioq2i = = loq2j 7. 己知完全二叉树的第7层有8个结点，则其叶子结点数为36个。总结点数为71个。8. 在对二叉树进行非递归中序遍历过程中，需要用栈来暂存所访问结点的地址:进行层 序遍历过程中，需要用队列来暂存所访问结点的地址。三、应用题1. 有n个结点的二叉树，己知叶子结点个数为n0回答下列问题：(1) 写出求度为1的结点的个数n,的计算公式；ni=n+l-2no(2) 若此树是深度为k的完全二叉树，写出n为最小的公式：nmin = 2kT(3) 若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式； n=2no-l四、算法分析题教材p208习

6、题5-2中：1、2、4、5四题1. 返回二叉树BT中值为X的结点所在的层号。nit NodeLevel(BTieeNode*BT,ElemType X)fif(BT=NULL)return 0:else if(BT-data=X)return 1;else(mt c l=NodeLevel(BT-left,X);if(cl=l)return cl+1;mt c2=NodeLevel(BT-right.X);iRc2=l)return c2+l;return 0:2. 指出下面函数的功能。BTreeNode* BTieeSwopX(BTreeNode* BT)if(BT=NULL)return

7、NULL;else(BTreeNode* pt=new BTreeNode;pt-data=BT-data;pt-right=BTreeSwopX(BT-left);pt-left=BTreeSwopX(BT-iight);return pt;函数的功能：交换二叉树的左右子树，生成新的二叉树。4. 指出下面函数的功能。void BTC(BTieeNode*BT)JIif(BT!=NULL)if(BT.l 知!=NULL&BT.nght!=NULL)if(BT-left-dataBT-iight-data)BTreeNode*t=BT-left;BT-left=BT-right;BT-right

8、=t;iBTC(BT-left);BTC(BT-iight);函数的功能：调整二叉树，使树中左子树结点的值小于等于右子树结点的值。5. 设BT指向一颗二叉树，该二叉树的广义表表示为a(b(a,d(f),c(e(,a(k),b),则依次使用BTCl(BT,a,C)s BTCl(BT，b，,C)、BTCl(BT，c，,C)和 BTCl(BTgC)调用下面算法时，假 定每次调用时C的初值为0,引用变量C的带回值依次为3 、 2、1和0。void BTC 1 (BTreeNode*BT, char x, int&k)if(BT!=NULL)if(BT-data=x)k+;BTCl(BT-left,x,

9、k);BTC! (BTright,x,k);五、算法设计题(参照上题，并总结有关二叉树操作实现的常用方法)1.编写求二叉树BT中结点总数的算法。mt BTreeCount(BTreeNode *BT)if(BT=NULL)return 0:else if(BTleft=NULL&BTnght=NULL)return 1;elsereturn BTreeCount(BT-left)-rBTieeCount(BT-nght)+1;2. 编写求二叉树BT中叶子结点数的算法。hit BTreeLeafCount(BTreeNode *BT)if(BT=NULL)return 0;else if(BTl

10、eft=NULL&BTnght=NULL)return 1;elsereturn BTreeLeafCount(BT-left)+BTieeLeafCount(BT-right);3. 若己知两棵二叉树BT1和BT2皆为空，或者皆不为空且BT1的左、右子树和BT2的 左、右子树分别相似，则称二叉树BT1和BT2相似。编写算法，判别给定的两棵二叉树是否 相似。int SiinilaiTrees(BTreeNode *BT LBTreeNode *BT2)if(BTl NULL&BT2=NULL)return 1;else if(BT 1 =NULL| |BT2=NULL)return 0;elsereturn SmiilarTrees(BTl-left.BT2-left)&SinularTiees(BTl-iighLBT2-right);)