《数据结构》-第六章

习题61选择题1、假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B）。A、15B、16C、17D、472、设N，M为一棵树上的两个结点，在中根遍历时，N在M前的条件是（C）。A、N在M右方B、N是M祖先C、N在M左方D、N是M子孙3、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D）。A、23B、37C、46D、444、如果F是由树T转换而来的二叉树，则T中结点的前根就是F中结点的（B）。A、中根遍历B、先根遍历C、后根遍历D、按层遍历5、某二叉树的先根遍历结点序列和后根遍历结点序列刚好相反，则该二叉树一定是（D）。A、空树或只有一个根结点B、完全二叉树C、二叉排序树D、高度等于其结点数62填空题1、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（后继）结点，其余结点的后继结点可以（任意多个）。2、在具有N个结点的二叉树中，有（N1）个空指针。3、深度为K的完全二叉树至少有（2K1）个结点，至多有（2K1）个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是（N/21）。4、由A，B，C三个结点构成的二叉树，共有（5）种不同形态。5、树所对应的二叉树其根结点的（右）子树一定为空。63应用题1、给定的树如图624（A）所示，回答以下问题（1）哪个是根结点，哪些是叶子结点答根结点是A，叶子结点是B，K，L，M，G，D，H，I，J。（2）哪个是结点F的双亲结点，哪些是结点F的祖先结点，哪些是结点F的孩子结点答结点F的双亲结点是C，祖先结点是A，C，孩子结点是K，L，M。（3）哪些是结点C的子孙结点，哪些是结点C的兄弟结点答结点C的子孙结点是F，G，K，L，M，结点C的兄弟结点是B，D，E。（4）给定树的层数是多少，结点I所在的层数是多少答树的层数为4，结点I在第三屋。（5）写出先根遍历、后根遍历和按层遍历的结点序列。答先根ABCFKLMGDEHIJ。后根BKLMFGCDHIJEA。按层ABCDEFGHIJKLM。2、给定的二叉树如图625所示（1）写出先根遍历、后根遍历、中根遍历和按层遍历的结点序列。答先根ABDIKECFGN。中根DIKBEAFCNG。后根KIDEBFNGCA。按层ABCDEFGTNK。（2）画出先根遍历和中根遍历的线索二叉树。答ABDEIKCGNFNULLABDEIKCGNFNULL先根遍历的线索二叉树中根遍历的线索二叉树ABCDEFGKLMHIJABCEFIDGH（A）将图中给定的树转换成二叉树（B）将图中给定的二叉树转换成树ABCDEFGHJKLMI0PQN（C）将图中给定的森林转换成二叉树图624题635ABDEIKCGNF图625题6323、图624中的树、森林与二叉树之间进行转换（1）将图（A）中给定的树转换成二叉树（2）将图（B）中给定的二叉树转换成树答ABCDEFGKLMHIJABCEFIDGH（1）（2）（3）将图（C）中给定的森林转换成二叉树（4）将图624中给定的二叉树转换成森林答ABCDEFGHJKLMIOPQNABDEIKCGNF（3）（4）4、出所有满足以下条件的二叉树（1）先根遍历和中根遍历时，得到的结点序列相同答空树、只有根结点的二叉树或所有的结点都没有左分支的二叉树。（2）后根遍历和中根遍历时，得到的结点序列相同答空树、只有根结点的二叉树或所有的结点都没有右分支的二叉树。（3）先根遍历和后根遍历时，得到的结点序列相同答空树或只有根结点的二叉树。5、已知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK，先根遍历的结点序列为ABCDEGFHJIK，画出对应的二叉树，并写出后根遍历的结点序列。答解题依据对先根遍历得到的结点序列来讲，第一个访问的结点肯定是二叉树的根结点，根据根结点可以将中根遍历的结点序列分为左子树、根结点和右子树三部分。根据分到的左、右子树包含的结点将先根遍历结点序列分出根结点、左子树和右子树。对左、右子树也是按先根遍历，所以可重复使用上述规则，就可以分出所有结点在二叉树中的位置。得到的二叉树如图所示ABCEGFJIHDK6、一个度为2的树与一棵二叉树有什么区别答一个度为2的树是一棵无序树，它的两个分支不分顺序；二叉树是一棵有序树，它的两个分支是有顺序的，分别称为左右子树。7、已知如下所示长度为12的表（JAN,FEB,MAR,APR,MAY,JUNE,JULY,AUG,SEP,OCT,NOV,DEC）,按表中元素的顺序构造一棵二叉排序树，插入时按字典序大小进行比较。答JANFEBMARAPRAUGDECJUNEJULYMAYSEPOCTNOV8、有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫曼树（要求按每个结点的左子树根结点的权值小于等于右子树根结点的权值的次序构造）。答构造的哈夫曼树为3016578249、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为007，019，002，006，032，003，021，010。试为这8个字母设计哈夫曼编码。使用另一种编码方式是采用二进数的等长编码，给出每个字母的编码，并比较两种编码方案的优缺点。答第一种方法哈夫曼编码。为了简简化求哈夫曼树的过程，将每个字母的出现频率看成整数，即将007看到是7，依次类推。则构造的哈夫曼树如下所示19216237103200000010111111按左分支是0，右分支是1的规则编码，则8个字母的编码依次为1010，00，10000，1001，11，10001，01，1011（如图所示）。第二种方法等长编码。电文由8个字母组成，所以共有八种情况，可以用三位二进制数来表示。则8个字母的编码依次为000，001，010，011，100，101，110，111。比较哈夫曼编码采用了高频率字母的编码较短的特点，所以同等个数的电文发送时翻译后所得的电文总长会比采用等长编码要短。假设发送的电文是52715326451275785，以数字代表八个字母，即数字1代表第一个字母，依次类推。通过计算可得，蛤夫曼编码的总长为48，等长编码的总长为51。若发送的电文越长这个优点体现的越明显。64算法题（算法没做要求）1、编写一个以二叉链表形式存储的二叉树中所有叶子结点的个数。2、编写一个交换二叉链表形式存储的二叉树中所有结点的左、右子树的算法。（可作为上机实践题目）3、编写一个按从大到小的顺序输出一个以二叉链表形式存储的二叉排序树的所有结点的算法。4、编写一个判断两棵二叉树是否等价的算法。等价的条件如果T1和T2都是空二叉树；或者T1和T2的根结点的值相同，并且T1的左子树与T2的左子树等价，T1的右子树与T2的右子树是等价的，则称T1和T2是等价的。5、编写一个复制一棵以二叉链表形式存储的二叉树的非递归算法。