《数据结构》-数据结构试卷第六章

数据结构期末复习题及参考答案第6章树和二叉树一、选择题1、在二叉树的第I层I1上最多含有结点数为（）A2IB2I11C2I1D2I12、深度为6的二叉树最多有个结点A64B63C32D313、一棵树高为K的完全二叉树至少有个结点A2K1B2K11C2K1D2K4、有关二叉树下列说法正确的是（）A二叉树的度为2B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为25、N个结点的线索二叉树上含有的线索数为（）A2NBNLCNLDN6、线性表和树的结构区别在于（）A前驱数量不同，后继数量相同B前驱数量相同，后继数量不同C前驱和后继的数量都相同D前驱和后继的数量都不同7、已知一算术表达式的中缀形式为ABCD/E，后缀形式为ABCDE/，则其前缀形式为EFDGAB/CAABC/DEBABCD/ECABC/DEDABC/DE8、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）AABC/DEFGBABC/DEFGCABC/DE（FG）DABC/DEFG9、一棵具有N个结点的完全二叉树的树高度（深度）符号表示取不大于X的最大整X数是（）ABCD2LOG1LOG2N1LOG2N1LOG2N10、利用二叉链表存储树，则根结点的右指针是（）。A指向最左孩子B指向最右孩子C空D非空11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。ACBEFDABFEDCBACCBEDFAD不定12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是AE,G,F,A,C,D,BBE,A,C,B,D,G,FCE,A,G,C,F,B,DD上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_棵不同的二叉树可以得到这一结果。A3B4C5D614、已知某二叉树的后序遍历序列是DABEC,中序遍历序列是DEBAC,则它的前序遍历是（）。AACBEDBDECABCDEABCDCEDBA15、线索二叉树是一种（）结构。A逻辑B逻辑和存储C物理D线性二、填空题1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0_N21_。2、具有256个结点的完全二叉树的深度为_9_。3、一个深度为4的二叉树，其结点至少有4个，至多有15个4、深度为H的完全二叉树至少有_2H1_个结点；至多有2H1_个结点；H和结点总数N之间的关系是HLOG2N1。5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有_2N_个指针域，其中有_N1_个指针域是存放了地址，有_N1_个指针是空指针。6、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是_63_7、已知二叉树的先序遍历次序是ABDCEF，中序遍历次序是BDAECF，则它的后序遍历次序是DBEFCA。8、对一棵完全二叉树，设一个结点的编号为I，若它的左孩子结点存在，则其编号为2I；若右孩子结点存在，则其编号为2I1；而双亲结点的编号为。2/I9、赫夫曼树是带权路径长度最小的二叉树，又称最优二叉树，路径上权值较大的结点离根较近。10、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。TYPEDEFSTRUCTNODEINTDATASTRUCTNODELCHILD_STRUCTNODERCHILD_BITNODE,BITREEVOIDCREATEBITREEBITREEIFCHTNULLELSETBITNODEMALLOCSIZEOFBITNODETDATACHCREATEBITREETLCHILD；_CREATEBITREETRCHILD11、二叉树由_根结点_，_左子树_，_右子树_三个基本单元组成。12、树的链表存储结构常用的有三种，其中，双亲表示法以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子表示法每个结点的孩子以单链表的形式存储，N个结点有N个孩子链表，N个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟表示法以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。/P13513613、利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树_。14、在二叉树中，指针P所指结点为叶子结点的条件是_PLCHILDNULL答案2、已知二叉树中的结点类型BINTREENODE定义为STRUCTBINTREENODEELEMTYPEDATABINTREENODELEFT,RIGHT其中DATA为结点值域，LEFT和RIGHT分别为指向左、右孩子结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。BINTREENODEBTFBINTREENODEBT，ELEMTYPEXIFBTNULL_RETURNNULL_ELSEIFBTDATAX_RETURNBT_ELSEBINTREENODETIFTBTFBTLEFT,XRETURNT_IFTBTFBTRIGHT,XRETURNT_RETURNNULL3、由二叉树的前序序列和中序序列能否唯一确定一棵二叉树由二叉树的中序序列和后序序列能否唯一确定一棵二叉树由二叉树的前序序列和后序序列能否唯一确定一棵二叉树请分别进行论述。答案1给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设L个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设R个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根左子树右子树”的顺序，则由从第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由前序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。2由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。证明如下当N1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当NM1时结论成立，现证明当NM时结论成立。设中序序列为S1，S2，SM,后序序列是P1,P2,，PM。因后序序列最后一个元素PM是根，则在中序序列中可找到与PM相等的结点（设二叉树中各结点互不相同）SI1IM，因中序序列是由中序遍历而得，所以SI是根结点，S1，S2，SI1是左子树的中序序列，而SI1,SI2,SM是右子树的中序序列。若I1，则S1是根，这时二叉树的左子树为空，右子树的结点数是M1,则S2，S3，SM和P1，P2，PM1可以唯一