《数据结构》期末复习题及参考答案---第6章-树和二叉树【HSH2013级】给学生

1EFDGAB/++*-C*《数据结构》期末复习题及参考答案-第6章树和二叉树一、选择题1、在二叉树的第I层(I≥1)上最多含有结点数为（）A.2IB.2I-1-1C.2I-1D.2I-12、深度为6的二叉树最多有()个结点A．64B.63C.32D.313、一棵树高为K的完全二叉树至少有()个结点A.2k–1B.2k-1–1C.2k-1D.2k4、有关二叉树下列说法正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为25、n个结点的线索二叉树上含有的线索数为（）A.2nB.n－lC.n＋lD.n6、线性表和树的结构区别在于（）A．前驱数量不同，后继数量相同B．前驱数量相同，后继数量不同C．前驱和后继的数量都相同D．前驱和后继的数量都不同7、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G9、一棵具有n个结点的完全二叉树的树高度（深度）(符号x表示取不大于x的最大整数)是（）A.n2logB.1log2nC.)1(log2nD.1log2n210、利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。A.3B.4C.5D.614、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍历是（）。A.acbedB.decabC.deabcD.cedba15、线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性二、填空题1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___N2+1_________。2、具有256个结点的完全二叉树的深度为___9___。3、一个深度为4的二叉树，其结点至少有4个，至多有15个：4、深度为H的完全二叉树至少有_2H-1__个结点；至多有2H-1_个结点；H和结点总数N之间的关系是H=log2N+1。5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有__2N__个指针域，其中有_N-1__个指针域是存放了地址，有__N+1_____个指针是空指针。6、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是__63____7、已知二叉树的先序遍历次序是abdcef，中序遍历次序是bdaecf，则它的后序遍历次序是：dbefca。38、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为2i；若右孩子结点存在，则其编号为2i+1；而双亲结点的编号为2/i。9、赫夫曼树是带权路径长度最小的二叉树，又称最优二叉树，路径上权值较大的结点离根较近。10、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;_structnode*rchild__;}BiTNode,*BiTree;voidcreateBitree(BiTree&T){scanf(“%c”,&ch);if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T-data=ch;createBitree(T-lchild)；___createBitree(T-rchild);}}11、二叉树由_根结点__，__左子树_，_右子树__三个基本单元组成。12、树的链表存储结构常用的有三种，其中，双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。//P135-13613、利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。14、在二叉树中，指针p所指结点为叶子结点的条件是_p-lchild==NULL&&p-rchlid==NULL_____。15、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。16、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝4的情况下，也必须指出是左子树还是右子树，树无此限制。三、简答题1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ,试画出这棵二叉树，并写出后序遍历结果。答案：当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：这棵二叉树的后序遍历结果是：KDCBIHJGFA2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是16，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。答案：哈夫曼树如下：对应的哈夫曼编码如下：A:0B:101C:110D:1001E:111F:1000带权路径长度为:WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序﹑中序﹑后序遍历，给出相应的结点序列，同时给二叉树5加上中序线索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA（4）中序线索见图中虚线箭头所示。四、算法分析题1、已知二叉树的存储结构为二叉链表，阅读下面算法，之后，对于如下所示的二叉树：（1）画出执行下面算法后所建立的结构；（2）说明该算法的功能。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；voidInorder(BinTreeT){LinkLists；If(T){Inorder(T－lchild)；If((!T－lchild)&&(!T－rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－data=T－data；s－next=Leafhead；ABCDFGEHnullnull6Leafhead=s；}Inorder(T－rchild);}}答案：2、已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右孩子结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。BinTreeNode*BTF(BinTreeNode*BT，ElemTypex){if(BT==NULL)_returnNULL__;else{if(BT-data==x)_returnBT_;else{BinTreeNode*t;if(t=BTF(BT-left,x))returnt;___if(t=BTF(BT-right,x))returnt_____;returnNULL;}}}3、由二叉树的前序序列和中序序列能否唯一确定一棵二叉树？由二叉树的中序序列和后序序列能否唯一确定一棵二叉树？由二叉树的前序序列和后序序列能否唯一确定一棵二叉树？请分别进行论述。答案：(1)给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。(2)由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。证明如下：7当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。最后，当1im时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。(3)由二叉树的前序序列和后序序列不能唯一确定一棵二叉树。因为无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。五、算法描述题试写出复制一棵二叉树的递归函数的算法。BiTreeCopy(BiTreet)//复制二叉树t{BiTreebt;if(t==null)bt=null;else{bt=(BiTree)malloc(sizeof(BiNode));bt-data=t-data;bt-lchild=Copy(t-lchild);bt-rchild=Copy(t-rchild);}return(bt);}