习题6 树和二叉树

第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)所示的二叉树，它们的经过先序、中序和后序遍历后得到的结点序列分别是什么？画出它们的先序线索二叉树和后序线索二叉树。

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

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

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

C 唯一性不确定。
D 唯一性与原因的边的权数有关。
14、将递归算法转换成对应的非递归算法时,通常需要使用__________。 A栈 B 队列 C 链表 D树 15 、设二维数组 A[m][n], 每个数组元素占用 K 个存储单元 , 第一个数组元素的存储地址是 Loc(a[0][0]),求按行优先顺序存放的数组元素 a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 A,Loc(a[0][0]+[(i-1)*n+j-1]*k B,Loc(a[0][0])+[i*n+j]*k C,Loc(a[0][0])+[j*m+i]*k D,Loc(a[0][0])+[(j-1)*m+i-1]*k 16 、设二维数组 A[m][n], 每个数组元素占用 k 个存储单元 , 第一个数组元素的存储地址是 Loc(a[0][0]),求按列优先顺序存放的数组元素 a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 A,Loc(a[0][0])+[(i-1)*n+j-1]*k B,Loc(a[0][0])+[i*n+j]*k C,Loc(a[0][0])+[j*m+i]*k D,Loc(a[0][0])+[(j-1)*m+i-1]*k 17 、设二维数组 A[6][10], 每个数组元素占用 4 个存储单元 , 若按行优先顺序存放的数组元 素,a[0][0]的存储地址为 860,则 a[3][5]的存储地址是______。 A,1000 B,860 C,1140 D,1200 18、设二维数组 A[6][10],每个数组元素占用 4 个存储单元,若按行优先顺序存放的数组元素 a[3][5]的存储地址为 1000,则 a[0][0]的存储地址是______。 A,872 B,860 C,868 D,864 19、若将 n 阶上三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1..n(n+1)/2]中,第一个非零 元素 a1,1 存于 B[0]中,则应存放到 B[k]中的非零元素 ai,j(1<=i<=n,1<=j<=i)的下标 i、j 与 k 的对 应关系是______。 A,i(i+1)/2+j B,i(i-1)/2+j-1 C,j(j+1)/2+i D,j(j-1)/2+i-1 20、若将 n 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1..n(n+1)/2]中,第一个非零 元素 a1,1 存于 B[0]中,则应存放到 B[k]中的非零元素 ai,j(1<=i<=n,1<=j<=i)的下标 i、j 与 k 的对 应关系是______。 A,j(2n-j+1)/2+i-j B,(j-1)(2n-j+1)/2+i-j C,i(2n-i+1)/2+j-i D,i(2n-i+2)/2 A 便于进行矩阵运算 B 便于输入和输出 C 节省存储空间 度 22、稀疏矩阵压缩后,必会失去______功能。 A 顺序存储 B 随机存取 C 输入输出 D 以上都不对

1.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？1根据“二叉树的第i层至多有2^(i − 1)个结点；深度为k的二叉树至多有2^k − 1个结点（根结点的深度为1）”这个性质：因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树，这样的话，前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256 所以第十层的叶子结点数是699-511=188个；现在来算第九层的叶子结点个数。

由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。

因为第十层有188个，所以应该去掉第九层中的188/2=94个；所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。

比如图：完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图：此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。

3完全二叉树中，只存在度为2的结点和度为0的结点，而二叉树的性质中有一条是：n0=n2+1；n0指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349；n0=3502.在一棵二叉树上第5层的结点数最多是多少一棵二叉树，如果每个结点都是是满的，那么会满足2^(k-1)1。

所以第5层至多有2^(5-1)=16个结点！3.在深度为5的满二叉树中，叶子结点的个数为答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~4.某二叉树中度为2的结点有18个，则该二叉树中有几个叶子结点？结点的度是指树中每个结点具有的子树个数或者说是后继结点数。

第六章树一．名词解释：1 树 2。

结点的度 3。

叶子 4。

分支点 5。

树的度6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树21 哈夫曼树二、填空题1、树（及一切树形结构）是一种“________”结构。

在树上，________结点没有直接前趋。

对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2、一棵树上的任何结点（不包括根本身）称为根的________。

若B是A的子孙，则称A是B的________3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。

4、二叉树第i(i>=1)层上至多有______个结点。

5、深度为k(k>=1)的二叉树至多有______个结点。

6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。

满二叉树也是______二叉树，但反之不然。

8、具有n个结点的完全二叉树的深度为______。

9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。

10.二叉树通常有______存储结构和______存储结构两类存储结构。

11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

一、选择题1．关于二叉树的下列说法正确的是（B ）A．二叉树的度为2 B．二叉树的度可以小于2C．每一个结点的度都为2 D ．至少有一个结点的度为2 2．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（C ）A．3 B．4C．5 D ．63．若一棵完全二叉树中某结点无左孩子，则该结点一定是（D ）A．度为1的结点B．度为2的结点C．分支结点 D ．叶子结点4．深度为k的完全二叉树至多有（C ）个结点，至少有（ B ）个结点。

A．2k-1-1 B．2k-1C．2k-1 D ．2k5．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为（ C 2i ），右孩子结点的层次编号为（ D 2i+1），双亲结点的层次编号为（60/2=30 A ）。

A．30 B．60C．120 D ．1216．一棵具有124个叶子结点的完全二叉树，最多有（B ）个结点。

A．247 B．248C．249 D ．250二、填空题1．树中任意结点允许有零个或多个孩子结点，除根结点外，其余结点有且仅有一个双亲结点。

2．若一棵树的广义表表示法为A（B（E，F），C（G（H，I，J，K），L），D（M （N））），则该树的度为 4 ，树的深度为 4 ，树中叶子结点的个数为8 。

3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数为14 。

n=n0+n1+n2+n3+n4=n0+4+3+2+2=n0+11n=1+孩子=1+4+6+6+8+25n0+11=25n0=144．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是n-2m+1 。

5．深度为k（k>0）的二叉树至多有2k -1 个结点，第i层上至多有2i-1个结点。

6．已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为133 。

7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是30+29+0=59 。

第 7 章 树和二叉树
教材中练习题及参考答案
1. 有一棵树的括号表示为 A(B，C(E，F(G))，D)，回答下面的问题： （1）指出树的根结点。 （2）指出棵树的所有叶子结点。 （3）结点 C 的度是多少？ （4）这棵树的度为多少？ （5）这棵树的高度是多少？ （6）结点 C 的孩子结点是哪些？ （7）结点 C 的双亲结点是谁？ 答：该树对应的树形表示如图 7.2 所示。 （1）这棵树的根结点是 A。 （2）这棵树的叶子结点是 B、E、G、D。 （3）结点 C 的度是 2。 （4）这棵树的度为 3。 （5）这棵树的高度是 4。 （6）结点 C 的孩子结点是 E、F。 （7）结点 C 的双亲结点是 A。
12. 假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法 计算一棵给定二叉树 b 中的所有单分支结点个数。 解：计算一棵二叉树的所有单分支结点个数的递归模型 f(b)如下：
f(b)=0 若 b=NULL
6 f(b)=f(b->lchild)+f(b->rchild)+1 f(b)=f(b->lchild)+f(b->rchild)
表7.1 二叉树bt的一种存储结构 1 lchild data rchild 0 j 0 2 0 h 0 3 2 f 0 4 3 d 9 5 7 b 4 6 5 a 0 7 8 c 0 8 0 e 0 9 10 g 0 10 1 i 0
答：（1）二叉树bt的树形表示如图7.3所示。
a b c e h j f i d g e h j c f i b d g a
对应的算法如下：
void FindMinNode(BTNode *b,char &min) { if (b->data<min) min=b->data; FindMinNode(b->lchild,min); //在左子树中找最小结点值 FindMinNode(b->rchild,min); //在右子树中找最小结点值 } void MinNode(BTNode *b) //输出最小结点值 { if (b!=NULL) { char min=b->data; FindMinNode(b,min); printf("Min=%c\n",min); } }

1. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？1根据“二叉树的第i 层至多有2^(i − 1)个结点；个结点；深度为k 的二叉树至多有2^k − 1个结点（根结点的深度为1）”这个性质：这个性质：因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树，二叉树，这样的话，这样的话，前九层的结点就有前九层的结点就有2^9-1=511个；个；而第九层的结点数是而第九层的结点数是2^(9-1)=256 所以第十层的叶子结点数是699-511=188个；个；现在来算第九层的叶子结点个数。

现在来算第九层的叶子结点个数。

由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。

因为第十层有188个，所以应该去掉第九层中的188/2=94个；个； 所以，第九层的叶子结点个数是256-94=162256-94=162，加上第十层有，加上第十层有188个，最后结果是350个2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点下面一层的结点（叶结点）（叶结点）（叶结点）都依次排列在该层最左边的位置上，都依次排列在该层最左边的位置上，都依次排列在该层最左边的位置上，这样的二叉树为这样的二叉树为完全二叉树。

完全二叉树。

比如图：比如图：完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B ！如果完全二叉树的叶结点都排满了，如果完全二叉树的叶结点都排满了，则是满二叉树，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图：比如图：此题的其实是一棵满二叉树，我们根据以上性质，699+1=700699+1=700，，700/2=350700/2=350，即，即叶结点数为350350，叶结点层以上所有结点数为，叶结点层以上所有结点数为350-1=349350-1=349。

【课后习题】第6章树和二叉树网络工程2010级（）班学号：姓名：一、填空题（每空1分，共16分)1.从逻辑结构看，树是典型的。

2.设一棵完全二叉树具有999个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个度为1的结点。

3.由n个权值构成的哈夫曼树共有个结点。

4.在线索化二叉树中，T所指结点没有左子树的充要条件是。

5.在非空树上，_____没有直接前趋。

6.深度为k的二叉树最多有结点，最少有个结点。

7.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为且小于n时，结点i的右兄弟是结点，否则结点i没有右兄弟。

8.N个结点的二叉树采用二叉链表存放，共有空链域个数为。

9.一棵深度为7的满二叉树有___ ___个非终端结点。

10.将一棵树转换为二叉树表示后,该二叉树的根结点没有。

11.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的遍历结果是一样的。

12.一棵Huffman树是带权路径长度最短的二叉树，权值的外结点离根较远。

二、判断题（如果正确，在对应位置打“√”，否则打“⨯”。

每题0.5分，共5分)1.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。

2.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。

3.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

4.度≤2的树就是二叉树。

5.一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。

6.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

7.不存在有偶数个结点的满二叉树。

8.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

9.已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；10.已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；三、单项选择（请将正确答案的代号填写在下表对应题号下面。

第三单元课后练习题（参考答案）知识点范围：第6章树与二叉树、第7章图一、选择题（每小题1分，共25分）1．树最适合用来表示 C 。

A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据2．深度为5的二叉树至多有 C 个结点。

A．16 B．32 C．31 C．103．对一个满二叉树，m个叶子，n个结点，深度为h，则 D 。

A．n = h+m B．h+m = 2n C．m = h-1 D．n = 2h-14．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A 。

A．不发生改变B．发生改变C．不能确定D．以上都不对5．设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为：AA．10 B．11 C．12 D．不确定6．在下述论述中，正确的是 D 。

①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③B．②③④C．②④D．①④7．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是 A 。

A．m-n B．m-n-1 C．n+1 D．不能确定8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B 。

A．9 B．11 C．15 D．不能确定9．具有10个叶子结点的二叉树中有 B 个度为2的结点。

A．8 B．9 C．10 D．1110．在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。

A．1/2 B． 1 C．2 D． 411.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A． 2i+1 B． 2i C． i/2 D． 2i-112．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为： CA．3 B．2 C．4 D．513．已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *+DE/–，其前缀形式为 D 。

六、树和二叉树一、选择题：1、在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（D ）A．2i B．不存在C．2i+1 D．⌊ i/2⌋3、下列陈述中正确的（A ）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分4、以二叉链表作为二叉树的存储结构，在具有ｎ个结点的二叉链表中(n>0)，空链域的个数为（ C ）A．2n - 1 B．n - 1 C．n + 1 D．2n + 15、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（B ）A．99 B．98 C．50 D．486、在一棵具有五层的满二叉树中，结点总数为（ A ）A．31 B．32 C．33 D．167、在一棵二叉树中，第5层上的结点数最多为（C ）A．8 B．15 C．16 D．328、由二叉树的（B）遍历，可以惟一确定一棵二叉树A．前序和后序B．前序和中序C．后序D．中序9、具有35个结点的完全二叉树的深度为（ B ）。

A.5B.6C.7D.810、已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（ C ）。

A．E B. F C. G D. J11、由4个结点构造出的不同的二叉树个数共有（ C ）。

A．8 B. 10 C．12 D．1412、在完全二叉树中，如果一个结点是叶子结点，则它没有（D ）。

A.左孩子结点B. 右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点13、深度为6的二叉树最多有（ B ）个结点。

A．64 B．63 C．32 D．3114、二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则（ A ）。

A．p结点左儿子为空B．p结点有右儿子C．p结点右儿子为空D．p结点有左儿子15、在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（ A ）。

第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-1D．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）引入二叉线索树的目的是（）。

一、单项选择1.二叉树是非线性数据结构,所以()A、它不能用顺序存储结构存储B、它不能用链式存储结构存储C、顺序存储结构和链式存储结构都能存储D、顺序存储结构和链式存储结构都不能存储参考答案 C2.把一棵树转换为二叉树后，这棵二叉树的形态是()A、唯一的B、有多种C、有多种，但根结点都没有左孩子D、有多种，但根结点都没有右孩子参考答案 A 3.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（）。

A）GEDHFBCA B）DGEBHFCAC）ABCDEFGH D）ACBFEDHG参考答案 B 4.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)参考答案 C 5.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对接点编号，根为1，则编号为49的结点的左孩子编号为( ) 。

A.98 B．99 C．50 D．48参考答案 A 6. 高度k的二叉树的最大结点数为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k+1参考答案 A 9.在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为：（）A.15 B．16 C．17 D．47参考答案 B 10.如果T1是由有序数T转换而来的二叉树，那么T中结点的后序遍历序列就是T1结点的（）遍序序列A.前序 B．中序 C．后序 D．层次参考答案 B 11.如图所示T2是由森林T1转换而来的二叉树，那么森林T1有（）叶结点。

A.4 B．5 C．6 D．7参考答案 C 12.有n个叶子结点的哈弗曼树的结点总数是（）A.不确定 B．2n C．2n+1 D．2n-1参考答案 D 二、填空题1.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。

13.2课后习题详解一、问答题1．股票的当前价格为40美元，已知在1个月后股票的价格将可能变为42美元或38美元，无风险利率为每年8%（连续复利），执行价格为39美元、1个月期限的欧式看涨期权价值是多少？答：（1）考虑下面这个组合：-1：看涨期权，＋Δ：股票如果股票价格上升到42美元，组合价值为42Δ-3。

如果股票价格下降到38美元，组合价值为38Δ。

当42Δ-3=38Δ，即Δ=0.75（美元）时，两种情况下组合价值相等，此时1个月后的组合价值为28.5美元，当前的价值必定等于28.5美元的现值，即28.5e-0.08×0.08333=28.31。

这意味着：-f+40Δ=28.31其中，f是看涨期权价格。

由于Δ=0.75，看涨期权价格为40×0.75－28.31=1.69（美元）。

（2）使用另一种方法，可以计算出风险中性世界中上升概率p，必定有下式成立：42p+38（1-p）=40e0.08×0.08333得到：4p=40e0.08×0.08333-38即p=0.5669。

此时期权价值等于按无风险利率折现后的期望收益：（3×0.5669+0×0.4331）e-0.08×0.08333=1.69（美元）这与前一种方法的计算结果相同。

2．用一步二叉树说明无套利方法与风险中性定价方法对于欧式期权的定价过程。

答：在无套利方法中，需要设定一个由期权头寸和股票头寸构成的无风险组合。

通过令该组合的收益率等于无风险利率，可以为期权定价。

在风险中性定价方法中，首先计算出二叉树中每个分支的概率，这样期权的期望收益率就等于无风险利率，然后通过计算出期权的期望收益并按无风险利率将其贴现，就可以获得期权的价值，实现定价。

3．股票期权Delta的含义是什么？答：股票期权的Delta衡量了期权价格对于股票价格小幅变动的敏感性。

具体而言，Delta是股票期权价格变动与标的股票价格变动之间的比率。

qu[rear].parent=-1;//根结点没有双亲,其parent置为-1
while (front!=rear)//队不空循环
{front++;
p=qu[front].s;//出队一个结点*p,它在qu中的下标为front
if (p->data==x)//找到值为x的结点
{printf("从根结点到%c结点的路径: ",p->data);
解：先序遍历树中结点的递归算法如下：
void PreOrder1(ElemType A[],int i,int n)
{if (i<n)
if (A[i]!='#')//不为空结点时
{printf("%c ",A[i]);//访问根结点
PreOrder1(A,2*i,n);//遍历左子树
PreOrder1(A,2*i+1,n);//遍历右子树
return h;
else
{l=Level(bt->lchild,x,h+1);//在左子树中查找
if (l!=0)
return l;
else//在左子树中未找到,再在右子树中查找
return(Level(bt->rchild,x,h+1));
}
}
上机实验题
假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。
图8.3一棵二叉树
（6）如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。
答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0=n2+1，即n2=n0-1，则总结点数n=n0+n2=2n0-1。

n=2*n0 -1 ， 因此 n1 =（n+1）/2 。
3．在下述结论中，正确的有（ ）。 ①只有一个结点的二叉树的度为 0；②二叉树的度为 2；③二叉树的左右子树可任意交 换，④深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．⑦③④ C．②④ D．①④ 【答案】D 【解析】只有根节点的二叉树的度为 0，二叉树的左右子树隐含着他们的位置关系。因
13．将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后序遍历是 h 的（ ）。 A．前序遍历 B．中序遍历 c．后序遍历 【答案】B 【解析】树的后序遍历恰好对应于二叉树的中序遍历。
叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有 n 个 （n>0）结点的完全二叉树的高度为 log2(n+1) 或 log2n +1；由完全二叉树类推到完全 三叉树可知，n 个结点的完全三叉树的高度为 log3(n+1) 或 log3n +1。
10．在下列存储形式中，哪一个不是树的存储形式? （ ） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示 法 【答案】D 【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结 点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点 的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常 用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
1 / 189
圣才电子书

此，②③均错。
十万种考研考证电子书、题库视频学习平台
4．在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数 为 2 个，则度为 0 的结点数为（ ）个。

树与二叉树一.选择题1. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。

A ．15B ．16C ．17D ．472. 按照二叉树的定义，具有3个结点的不同形状的二叉树有（ ）种。

A. 3B. 4C. 5D. 63. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（ ）种。

A. 5B. 6C. 30D. 324. 深度为5的二叉树至多有（ ）个结点。

1A. 16B. 32C. 31D. 10 5. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。

A. 2hB. 2h-1C. 2h+1D. h+16. 对一个满二叉树2，m 个树叶，n 个结点，深度为h ，则（ ）。

A. n=h+m 3B. h+m=2nC. m=h-1D. n=2 h-17. 任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（ ）。

A.不发生改变B.发生改变C.不能确定D.以上都不对8. 如果某二叉树的前根次序遍历结果为stuwv ，中序遍历为uwtvs ，那么该二叉树的后序为（ ）。

A. uwvtsB. vwutsC. wuvtsD. wutsv9. 某二叉树的前序遍历结点访问顺序是abdgcefh ，中序遍历的结点访问顺序是dgbaechf ，则其后序遍历的结点访问顺序是（ ）。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca 10. 在一非空二叉树的中序遍历序列中，根结点的右边（ ）。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点 11. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树4叫做这1深度为n 的二叉树结点至多有2n-12 满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树3 对于深度为h 的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。