数据结构二叉树习题

第6章 二叉树与树一、回答题1. 图6-1所示的树的叶子结点、非中端结点、每个结点的度及树的深度各是多少？图6-1 树2. 已知一棵树边的集合表示为：{ ( L, N ), ( G, K ), ( G, L ), ( G, M ), ( B, E ), ( B, F ), ( D, G ), ( D, H ), ( D, I ), ( D, J ), ( A, B ), ( A, C ), ( A, D ) }，画出这棵树，并回答以下问题：(1) 树的根结点是哪个？哪些是叶子结点？哪些是非终端结点？ (2) 树的度是多少？各个结点的度是多少？ (3) 树的深度是多少？各个结点的层数是多少？(4) 对于结点G ，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点？3. 如果一棵度为m 的树中，度为1的结点数为n 1，度为2的结点数为n 2，……，度为m 的结点数为n m ，那么该树中含有多少个叶子结点？有多少个非终端结点？ABECDFGHJI4. 任意一棵有n 个结点的二叉树，已知有m 个叶子结点，能否证明度为2结点有m-1个？5. 已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点，那么该树含有的叶子结点的数目是多少？6. 一棵含有n 个结点的k 叉树，可能达到的最大深度和最小深度各为多少？7. 对于3个结点A 、B 、C ，可以过程多少种不同形态的二叉树？8. 深度为5的二叉树至多有多少个结点？9. 任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序是发生改变？不发生改变？不能确定？10. 设n 、m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是什么？ 11. 已知某二叉树的后续遍历序列是dabec ，中序遍历序列是debac ，那么它的前序遍历序列是什么？12. 对一棵满二叉树，m 个树叶，n 个结点，深度为h ，则n 、m 和h 之间的关系是什么？ 13. 对图6-2(a)和(b)所示的二叉树，它们的经过先序、中序和后序遍历后得到的结点序列分别是什么？画出它们的先序线索二叉树和后序线索二叉树。

第6章树和二叉树1．选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子（2）由3 个结点可以构造出多少种不同的二叉树？（）A．2 B．3 C．4 D．5（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A．250 B． 500 C．254 D．501（4）一个具有1025个结点的二叉树的高h为（）。

A．11 B．10 C．11至1025之间 D．10至1024之间（5）深度为h的满m叉树的第k层有（）个结点。

(1=<k=<h)A．m k-1 B．m k-1 C．m h-1 D．m h-1（6）利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次（9）在下列存储形式中，（）不是树的存储形式？A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。

A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点 D．是任意一棵二叉树（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A．空或只有一个结点 B．任一结点无左子树C．高度等于其结点数 D．任一结点无右子树（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A．X的双亲 B．X的右子树中最左的结点C．X的左子树中最右结点 D．X的左子树中最右叶结点（13）引入二叉线索树的目的是（）。

数据结构-习题-第六章-树和二叉树E F D G A B / + + * - C * 第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/EC ．-+*ABC/DE D. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ）【南京理工大学1999 一、20（2分）】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-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T。

其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。

哈夫曼编码： a:11 b:101 c:010 d:1001 e:011 f:00 g:1000 2) 等长编码至少需要3 bit 哈夫曼编码WPL=0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.61 压缩率=1-2.61/3=13% 4.程序设计题 1)创建一任意二叉树，统计某子树下值为奇数和偶数结点的个数。 #define INT #include"c1.h" #ifdef CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空*/ #endif #ifdef INT typedef int TElemType; TElemType Nil=0; /* 整型以0为空*/ #endif #include"c6-2.h" #include"bo6-2.c" void GetLeafCounts(BiTree T,int *n,int *m) {
文档之家的所有文档均为用户上传分享文档之家仅负责分类整理如有任何问题可通过上方投诉通道反馈
数据结构习题三（答案）
数据结构习题(三) 学号________ 姓名_______ 课堂号(_________) 1.选择题 1)若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A．9 B．11 C．15 D．不确定 2)设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林 F对应的二叉树根结点的右子树上的结点个数是（ D ） A．M1 B．M1+M2 C．M3 D．M2+M3 3)二叉树的第I层上最多含有结点数为（ C ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 4)在一棵高度为k的满二叉树中，结点总数为（ C ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 5)利用二叉链表存储树，则根结点的右指针是（ C ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 6)已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果 为（ A ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 7)n个结点的线索二叉树上含有的线索数为（ C ） A．2n B．n－l C．n＋l D．n 8)由3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5 9)某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E。二叉树对应的森林 包括多少棵树（ B ） A．l B．2 C．3 D．概念上是错误的 10)设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针 域为空的结点有（ C ）个。 A． n-1 B．n C． n+1 D． n+2 11)下面几个符号串编码集合中，不是前缀编码的是（ B ）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 2.填空题 12)树在计算机内的表示方式有__双亲表示法_，___孩子表示法___，___孩子兄弟表示法/ 二叉链表表示法_____。 13)在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==NULL && p->rchild==NULL________________。