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

1、数据结构期末复习题及参考答案 - 第6章 树和二叉树一、 选择题 1、在二叉树的第I层(I1)上最多含有结点数为（ ） A. 2I B. 2I-1-1 C. 2I-1 D. 2I -12、深度为6的二叉树最多有( )个结点 A64 B.63 C.32 D.313、一棵树高为K的完全二叉树至少有( )个结点 A.2k 1 B.2k-1 1 C.2k-1 D.2 k 4、有关二叉树下列说法正确的是（ ）A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 5、n个结点的线索二叉树上含有的线索数为（ ）A. 2n B. nl

2、 C. nl D. n 6、线性表和树的结构区别在于（ ）A前驱数量不同，后继数量相同B前驱数量相同，后继数量不同C前驱和后继的数量都相同D前驱和后继的数量都不同7、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），EFDGAB/+*-C*它所表示的算术表达式是（ ）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*

3、B+C/D*E+F-G9、一棵具有 n个结点的完全二叉树的树高度（深度）(符号表示取不大于x的最大整数)是（ ）A. B. C. D.10、利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不

4、对 13、若前序遍历二叉树的结果为序列A、B、C，则有_棵不同的二叉树可以得到这一结果。A. 3 B. 4 C. 5 D. 6 14、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 则它的前序遍历是（ ）。 A. acbed B. decab C. deabc D. cedba 15、线索二叉树是一种（ ）结构。A逻辑 B逻辑和存储 C物理 D线性 二、填空题 1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=_ N2 + 1_。2、具有256个结点的完全二叉树的深度为_9_。3、一个深度为4的二叉树，其结点至少有 4

5、个，至多有 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 。8、对

6、一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 ë û 。 9、赫夫曼树是带权路径长度 最小的 二叉树，又称最优二叉树，路径上权值较大的结点离根较近。10、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct node int data; struct node *lchild;_ struct node *rchild _; BiTNode, *BiTree;void createBitree(BiTree &T) scanf(“%

7、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个头指针又组成一个线性表，并以

8、顺序存储结构存储。孩子兄弟 表示法以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。/P135-13613、利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树_。14、在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild=NULL && p->rchlid=NULL _。15、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。16、树和二叉树逻辑上都是树形

9、结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度 至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是 左子树还是右子树，树无此限制。三、简答题 1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树，并写出后序遍历结果。 答案：当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：这棵二叉树的后序遍历结果是：K D C B I H J G F A2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是1

10、6，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。答案：哈夫曼树如下：对应的哈夫曼编码如下：A: 0B: 101C: 110D: 1001E: 111F: 1000带权路径长度为: WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序中序后序遍历，给出相应的结点序列，同时给二叉树加上中序线索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA （4）中序线索见图中虚线箭头所示。四、

11、算法分析题1、已知二叉树的存储结构为二叉链表，阅读下面算法，之后，对于如下所示的二叉树：（1）画出执行下面算法后所建立的结构； （2）说明该算法的功能。typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList； LinkList Leafhead = NULL； void Inorder ( BinTree T ) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rch

12、ild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data； s>next=Leafhead； Leafhead=s； Inorder(T>rchild); 答案：2、已知二叉树中的结点类型BinTreeNode定义为:        struct BinTreeNode ElemType data;  BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右孩子

13、结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。    BinTreeNode* BTF(BinTreeNode* BT，ElemType x)            if(BT=NULL) _ return NULL _;        else if

14、(BT->data=x) _ return BT  _;             else   BinTreeNode* t;                 if(t=BTF(BT->left, x) return t;    

15、0;            _ if(t=BTF(BT->right, x) return t   _;                 return NULL;            

16、;               3、由二叉树的前序序列和中序序列能否唯一确定一棵二叉树？由二叉树的中序序列和后序序列能否唯一确定一棵二叉树？由二叉树的前序序列和后序序列能否唯一确定一棵二叉树？请分别进行论述。答案： (1)给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍

17、历中“根左子树右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。(2)由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。证明如下：当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，Sm,后序序列是P1,P2,，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1im)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，Si-

18、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唯一确定左子树，从而也确定了二叉树。最后，当1<i<m时，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)由二叉树的前序序列和后序序列不能唯一确定一棵二叉树。因为无法确定左右子树两部