《数据结构习题.doc》由会员分享，可在线阅读，更多相关《数据结构习题.doc（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题及解析第6 章 树和二叉树基础知识题6.1 已知一棵树边的集合为 , ，请画出这棵树，并回答下列问题：（1） 哪个是根结点？（2） 哪些是叶子结点？（3） 哪个是结点G的双亲？（4） 哪些是结点G的祖先？（5） 哪些是结点G的孩子？（6） 哪些是结点E的子孙？（7） 哪些是结点E的兄弟？哪些是结点F的兄弟？（8） 结点B和N的层次号分别是什么？（9） 树的深度是多少？（10） 以结点C为根的子树的深度是多少？ 6.2一棵度为2的树与一棵二叉树有何区别？ 6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6.4一棵深度为H的满k叉树有如下性质；第H层上的结点都是叶子
2、结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点的编号，问：（1） 各层的结点树目是多少？（2） 编号为p的结点的父结点（若存在）的编号是多少？（3） 编号为p的结点的第i 个儿子结点（若存在）的编号是多少？（4） 编号为p的结点有右兄弟的条件什么？其右兄弟的编号是多少？ 6.5已知一棵树为k的树中有n1 个度为1的结点，n2 个度为2的结点,nk 个度为k的结点,问该树中有多少个叶子结点? 6.6已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点.试求该树含有的叶子结点的数目. 6.7一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
3、 6.8证明：一棵满k叉树上的叶子结点数n0 和 非叶子结点数n1 之间满足以下关系：n0 =（k - 1）n1 + 1 6.9试分别推导出含有n个结点和含有n0 个叶子结点的完全三叉树的深度H。 6.10对于那些所有非叶子结点均有非空左右子树的二叉树：（1） 试问：有n个叶子结点的树中共有多少个结点？（2） 试证明：2-（li-1 ） =1 其中n 为叶子节点的个数，li 表示第 i 个叶子节点所在的层次（设根结点所在层次为1）。 6.11 在二叉树的顺序存储结构中，实际上隐含这双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节的存储，每个信息域占k个字节的存储，试问：对于一棵有n个
4、结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？ 6.12 对应6.3所得各种形态的二叉树，分别写出前序、中序、后序遍历的序列。 6.13 假设n和m为二叉树中二结点，用“1”、“0”或“”（分别表示肯定、恰恰相反或者不一定）填写下表： 答问已知前序遍历时 n在m前？中序遍历时 n在m前？后序遍历时 n在m前？ n在m左方n在m左方n在m祖先n在m子孙 注意：如果（1）离a 和 b 最近的共同祖先p存在且（2）a 在p 的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。6.14 找出所有满足下列条件的二叉树；（a） 它们在先
5、序遍历和中序遍历时，得到的结点访问序列相同；（b） 它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c） 它们在先序遍历和后序遍历时，得到的结点访问序列相同； 6.15请对右图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。 6.16将下列二叉链表改为先序线索链表（不画出树的形态）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14InfoABCDEFGHIJKLMNLtag Lchild24607010012130000RtagRchild3500891100014000 6.17 阅读下列算法，若有错，则改之。BiTree InSucc（BiTree
6、q） / 已知q 是指向中序线索二叉树上某个结点的指针， / 本函数返回指向*q的后继的指针。 r= q-rchild; if (!r-rtag) while (!r-rtag) r=r-rchild; return r; /InSucc6.18试讨论，能否在一棵中序全线索二叉树上查找给定结点*p 在后序序列中的后继。6.19 分别画出和下列树对应的各个二叉树；6.20将下列森林转换为相应的二叉树，并分别按以下说明进行线索化；（1） 先序前驱线索化；（2） 中序全线索化；（3） 后序后继线索化。6.21画出和下列二叉树相应的森林；6.22对于6.19题中给出的各树分别求出以下遍历序列； （1）
7、先序遍历 （2） 后序遍历6.23画出和下列已知序列对应的树T： 树的先根次序访问序列为GFKDAIEBCHG 树的后跟次序访问序列为DIAEKFCJHBG。6.24画出和下列已知序列对应的森林F： 森林的先根次序访问序列为ABCDEFGHIJKL 树的后跟次序访问序列为CBEFDGAJIKLH。6.25证明：在结点数多于1的哈夫曼树中不存在度为 1的结点。6.26 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07。0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫编码，使用07的二进制表示形式是另一种编码方案，对于上述实例，比
8、较这两种方案的优缺点。6.27假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出树。6.28假设一棵二叉树的中序序列为D CBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出树。6.29假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出树。6.30证明：树中结点u 是结点v的祖先，当且仅当在先序 序列中u在v之前，且在后序序列中u在v之后。6.31证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。6.32证明；如果一棵二叉树的先序序列是u1，u2. un 中序序列为up1 up2.upp 则序列1,
9、2,.,n可以通过一个栈得到序列 p1，p2. pn ;反之,若以上述中的结论作为前提,则存在一棵二叉树,若其前序序列是u1，u2. un ,则其中序序列为 up1 up2.upp. 算法设计题 6.33假定用两个一维数组L1n和R1.n作为有n个结点的二叉树的存储结构,Li和Ri分别指出结点i的左孩子和右孩子,0表示空,试写一算法判别结点是否为结点V的子孙.6.34同6.33题条件。先由L和R建立一维数组T1n,使T中第 i ( i=1,2,n )个分量指示结点i 的双亲,然后写判别结点u是否为结点v的子孙的算法.6.35 假设二叉树中左分支的标号为”0”,右分支的标号为”1”,并对二叉树增
10、设一个头结点,令根结点为其右孩子,则从头结点到树中任一点所经分支的序列为一个二进制序列,可以作是某个十进制数的二进制表示.例如,右图所示二叉树中,和节点A对应的二进制序列为”110”,即十进制整数6的二进制表示,已知一棵非空二叉树以顺序存储结构表示,试写一尽可能简单的算法,求出与树的顺序存储结构中下标值为i 的结点对应的十进制数.以下6.36至6.38和6.41至6.53题中,均以二叉链表作为二叉树的存储结构.6.36若已知两棵二叉树B1和B2皆为空,或者皆不为空且B1的左右子树 和B2的左子树分别相似,则称二叉树B1和B2相似,试编写算法,判别给定两棵二叉树是否相似.6.37试利用栈的基本操
11、作写出先序遍历的非递归形式的算法。6.38同6.37条件，写出后序遍历的非递归形式的算法（提示：为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈）。6.39若在二叉链表的结点中增设两个域：双亲域（parent）以指示其双亲结点，标志域（mark取值0.2）以区分在遍历过程中达到该结点时应继续向左或向右或访问该结点，试以存储结构编写不用栈进行后序遍历的递推形式的算法。6.40若在二叉链表的结点中只增设一个双亲域以指示其双亲结点，则在遍历过程中能否不设栈？试以存储结构编写不设栈进行中序遍历的递推形式的算法。6.41编写递归算，在二叉树中求位于先序序列中第k个位置的结点的值。6
12、.42编写递归算法，计算二叉树中叶子结点的数目。6.43编写递归算法，将二叉树中所有结点的左、右子树相互交换。6.44编写递归算法，求二叉树中以元素值为x 的结点为根的子树的深度。6.45编写递归算法，对于二叉树中的每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。6.46编写复制一棵二叉树的非递归算法。6.47已知在二叉树中，*root 为根结点，*p和*q为二叉树中的两个结点，试编写求距离它们最近的共同祖先的算法。6.48编写按层次顺序中（同一层自左向右）遍历二叉树的算法。6.49编写算法判别给定二叉树是否为完全二叉树。6.50假设以三元组（F，C，L/R）的形式输入一棵二叉树
13、的诸边（其中F表示双亲结点的标识，C表示孩子结点标识，L/R表示C为F的左孩子或右孩子），且在输入的三元组序列中，C是按层次顺序出现的，设结点的标识是字符型，F=时C为根结点标识，若C也为，则表示输入结束，例如，6.15题所示二叉树的三元组序列输入格式为： ALABLACRBDLCELCFRDGRFHLL试编写算法，由输入的三元数组序列建二叉树的二叉链表。6.51编写算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。6.52一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积，试写一算法求二叉树的繁茂度。6.53试编写算法，求给定二叉树上从根结点到叶子结点的一条
14、其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的路径存在多条，则输出路径终点（叶子结点）在“最左”的时间复杂度。6.54已知一棵完全二叉树存于顺序表sa中，sa.elm1.sa.last含结点值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。6.55二叉链表的结点增加DescNum域，试编写算法，求二叉树的每个结点的子孙数目并存入其DescNum域。请给出算法的 时间复杂度。6.56试写一个算法，在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）。并讨论实现此算法对存储结构有何要求？6.57试编写一算法，在后序后继线索二叉树中 ，
