2022年数据结构课后习题及解析六.docx

《2022年数据结构课后习题及解析六.docx》由会员分享，可在线阅读，更多相关《2022年数据结构课后习题及解析六.docx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用第六章习题1试分别画出具有 3 个结点的树和 3 个结点的二叉树的全部不同形状；2对题 1 所得各种形状的二叉树,分别写出前序、中序和后序遍历的序列；3已知一棵度为 k 的树中有 n1个度为 1 的结点, n2 个度为 2 的结点, ,nk个度为 k 的结点,就该树中有多少个叶子结点并证明之；4. 假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为 ABCDEFGHIJK,请画出该二叉树；5已知二叉树有 50 个叶子结点,就该二叉树的总结点数至少应有多少个？6给出满意以下条件的全部二叉树：前序和后序相同域的等

2、长链结点储备树的一个结点,就空的Child中序和后序相同前序和后序相同7 n 个结点的 K 叉树,如用具有 k 个 child域有多少个？8画出与以下已知序列对应的树：树的先根次序拜访序列为 GFKDAIEBCHJ树的后根次序拜访序列为 DIAEKFCJHBG9假设用于通讯的电文仅由 8 个字母组成,字母在电文中显现的频率分别为：0.07 ,0.19 ,0.02 ,0.06 ,0.32 ,0.03 ,0.21 ,0.10 请为这 8 个字母设计哈夫曼编码；10已知二叉树采纳二叉链表存放, 要求返回二叉树 T 的后序序列中的第一个结点指针, 是否可不用递归且不用栈来完成 .请简述缘由 .11.

3、画出和以下树对应的二叉树：名师归纳总结 - - - - - - -第 1 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用12已知二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；13编写递归算法：对于二叉树中每一个元素值为 的空间；x 的结点,删去以它为根的子树,并释放相应14分别写函数完成：在先序线索二叉树 T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树 T 中,查找给定结点 *p 在后序序列中的前驱；15分别写出算法,实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继；16编写算法,对一棵以孩子-

4、 兄弟链表表示的树统计其叶子的个数；17对以孩子 - 兄弟链表表示的树编写运算树的深度的算法；18已知二叉树根据二叉链表方式储备,利用栈的基本操作写出后序遍历非递归的算法；19设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正就二叉树；正就二叉树是 指：在二叉树中不存在子树个数为 1 的结点；20运算二叉树最大宽度的算法；二叉树的最大宽度是指：二叉树全部层中结点个数的最大值；21已知二叉树根据二叉链表方式储备,利用栈的基本操作写出先序遍历非递归形式的算法；22. 证明：给定一棵二叉树的前序序列与中序序列,可唯独确定这棵二叉树；给定一棵二叉树的后序序列与中序序列,可唯独确定这棵二叉树；23

5、. 二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；24. 二叉树根据二叉链表方式储备,编写算法,将二叉树左右子树进行交换；实习题1. 问题描述 建立一棵用二叉链表方式储备的二叉树,并对其进行遍历先序、中序和后序）,打印输出遍历结果；名师归纳总结 - - - - - - -第 2 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 基本要求 从键盘接受输入先序序列,以二叉链表作为储备结构,建立二叉树 以先序来建立）并对其进行遍历 先序、中序、后序）,然后将遍历结果打印输出；要求采纳递归和非递归两种 方法实现； 测试数据 ABC DE

6、G F 其中 表示空格字符）输出结果为：先序： ABCDEGF 中序： CBEGDFA 后序： CGBFDBA 2已知二叉树根据二叉链表方式储备,编写算法,要求实现二叉树的竖向显示 n k + 16.5 已知二叉树有 50 个叶子结点,就该二叉树的总结点数至少应有多少个？【解答】 n0 表示叶子结点数, n2 表示度为 2 的结点数,就 n0 = n2+1所以 n2=n 0 1=49,当二叉树中没有度为:1 的结点时,总结点数n=n 0+n2=996.6 试分别找出满意以下条件的全部二叉树1 前序序列与中序序列相同；2 中序序列与后序序列相同；3 前序序列与后序序列相同；【解答】 1 前序与中

7、序相同：空树或缺左子树的单支树； 2 中序与后序相同：空树或缺右子树的单支树； 3 前序与后序相同：空树或只有根结点的二叉树；8 个字母组成,字母在电文中显现的频率分别为：6.9 假设通讯的电文仅由 0.07 ,0.19 ,0.02 ,0.06,0.32,0.03,0.21 ,0.10 请为这 8 个字母设计哈夫曼编码；【解答】名师归纳总结 - - - - - - -第 4 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用构造哈夫曼树如下：哈夫曼编码为：I1：11111 I5：1100I 2：11110 I 6：10I 3：1110 I 7： 01I

8、 4：1101 I 8： 006.11 画出如下图所示树对应的二叉树；【解答】名师归纳总结 - - - - - - -第 5 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用6.15 分别写出算法,实现在中序线索二叉树T 中查找给定结点 *p 在中序序列中的前驱与后继；在先序线索二叉树T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树T 中,查找给定结点 *p 在后序序列中的前驱； /*在中序线索二叉树中查找 p 的中序前驱结点,并用 pre 指针返回结果 */ if p-Ltag= =1 pre = p-LChild； /*直接利用线

9、索 */ else /*在 p 的左子树中查找“ 最右下端” 结点 */ for q=p-LChild ； q-Rtag= =0 ； q=q-RChild ； pre = q ； return pre ；名师归纳总结 - - - - - - -第 6 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用/*在中序线索二叉树中查找p 的中序后继结点,并用succ 指针返回结果 */ if p-Rtag= =1 succ = p-RChild else； /*直接利用线索 */ /*在 p 的右子树中查找“ 最左下端” 结点 */ for q=p-RChil

10、d ； q-Ltag= =0 ； q=q-LChild ； succ= q ； return succ ； 3 找结点的先序后继结点BiTNode *PreSucc BiTNode *p /*在先序线索二叉树中查找 p 的先序后继结点,并用 succ 指针返回结果 */ if p-Ltag= =0 succ = p-LChild； else succ= p-RChild ； return succ ； 4 找结点的后序前驱结点 BiTNode *SuccPre BiTNode *p /*在后序线索二叉树中查找 p 的后序前驱结点,并用 pre 指针返回结果 */ if p-Ltag= =1 p

11、re = p-LChild； else pre= p-RChild ； return pre ；名师归纳总结 - - - - - - -第 7 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 6.21 已知二叉树根据二叉链表方式储备,利用栈的基本操作写出先序遍历非递归形式的算法；【解答】Void PreOrderBiTree root /*先序遍历二叉树的非递归算法*/ InitStack&S ； p=root ； whilep.=NULL | .IsEmptyS ifp.=NULL Visitp-data ；push&S,p ；p=p-Lchil

12、d ； else Pop&S,&p ； p=p-RChild ； 6.24 已知二叉树根据二叉链表方式储备,编写算法,将二叉树左右子树进行交换；【解答】算法 一 Void exchange BiTree root p=root ；名师归纳总结 - - - - - - -第 8 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 if p-LChild .= NULL | p-RChild .= NULL temp = p-LChild；p-LChild = p-RChild ； p-RChild = temp； exchange p-LChild ；

13、exchange p-RChild ； 算法 二 Void exchange BiTree root p=root ； if p-LChild .= NULL | p-RChild .= NULL exchange p-LChild ； exchange p-RChild ； temp = p-LChild；p-LChild = p-RChild ； p-RChild = temp； 第六章 习题解读名师归纳总结 - - - - - - -第 9 页,共 19 页精选学习资料 - - - - - - - - - 1试分别画出具有3 个结点的树和个人资料整理仅限学习使用3 个结点的二叉树的全部不

14、同形态；2对题 1 所得各种形状的二叉树,分别写出前序、中序和后序遍历的序列；3已知一棵度为 k 的树中有 n 1 个度为 1 的结点, n2 个度为 2 的结 点, ,n k 个度为 k 的结点,就该树中有多少个叶子结点？提示 ：参考 P.116 性质 3n=n 0 + n 1 + + n kB=n 1 + 2n 2 + 3n 3 + + kn kn= B + 1 n 0 + n 1 + + nk = n 1 + 2n 2 + 3n 3 + + kn k + 1 n 0 = n 2 + 2n 3 + + k-1n k + 14.假设一棵二叉树的先序序列为 EBADCFHGIKJ,中序序列为A

15、BCDEFGHIJK,请画出该二叉树；提示 ：参考 P.148 6已知二叉树有50 个叶子结点,就该二叉树的总结点数至少应有多少个？提示 ：方法 1名师归纳总结 - - - - - - -第 10 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用1）一个叶子结点,总结点数至多 有多少个？结论：可压缩 一度 结点；2）满二叉树或完全二叉树具有最少的 一度 结点 3）可能的最大满二叉树是几层？有多少叶结点？如何增补？2 550 = 50 得： x = 18此时总结点数目= 26 1 + 18 2方法 2 假设完全二叉树的最大非叶结点编号为 m ,就最大叶

16、结点编号为 2m+1,2m+1-m=50 m=49 总结点数目 =2m+1=99名师归纳总结 - - - - - - -第 11 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用方法 3 由性质 3：n 0=n 2+1 即： 50=n 2+1 所以： n 2=49 令 n1=0 得： n= n 0 + n 2=99 7给出满意以下条件的全部二叉树：a 前序和中序相同 b 中序和后序相同 c 前序和后序相同 提示 ：去异存同；a D L R 与 L D R 的相同点： D R ,假如无 L,就完全相同 , 假如无 LR , ；b L D R 与 L R

17、 D 的相同点： L D ,假如无 R,就完全相同；c D LR 与 LR D 的相同点： D,假如无 L R ,就完全相同；假如去 D,就为空树）7 n 个结点的 K 叉树,如用具有 k 个 child 域的等长链结点储备树的 一个结点,就空的 Child 域有多少个？提示 ：参考 P.119 名师归纳总结 - - - - - - -第 12 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用8画出与以下已知序列对应的树：树的先根次序拜访序列为GFKDAIEBCHJ；树的后根次序拜访序列为DIAEKFCJHBG；提示 ：1）先画出对应的二叉树2）树的

18、后根序列与对应二叉树的中序序列相同9假设用于通讯的电文仅由 分别为：8 个字母组成,字母在电文中显现的频率0.07 ,0.19 ,0.02 ,0.06 ,0.32 , 0.03 ,0.21 ,0.101）请为这 8 个字母设计哈夫曼编码,2）求平均编码长度；10已知二叉树采纳二叉链表存放 ,要求返回二叉树 T 的后序序列中的第一个结点的指针 ,是否可不用递归且不用栈来完成 .请简述缘由 .提示 ：无右子的“ 左下端”11. 画出和以下树对应的二叉树：名师归纳总结 - - - - - - -第 13 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用12

19、已知二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；13编写递归算法：对于二叉树中每一个元素值为 为根的子树,并释放相应的空间；提示 ：x 的结点,删去以它方法 1：1）按先序查找；2）超前查看子结点 if *bt .= NULL & *bt -data=x FreeTree *bt ；*bt =NULL ； else DelTree *bt, x名师归纳总结 - - - - - - -第 14 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用void DelTree BiTreebt, DataType x if bt if bt

20、-LChild & bt-LChild-data=x FreeTree bt-LChild； bt-LChild=NULL； if bt-RChild & bt-RChild-data=x FreeTree bt-RChild； bt-RChild=NULL；DelTree bt-LChild, x；DelTree bt-RChild, x；名师归纳总结 - - - - - - -第 15 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用方法 2：1）先序查找； 2）直接查看 当前根 结点 3）用 指针参数 ；方法 3：1）先序查找； 2）直接查看

21、当前根 结点3）通过 函数 值,返回 删除后结果 ；参示例程序）14分别写函数完成：在先序线索二叉树 T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树 T 中,查找给定结点 *p 在后序序列中的前驱；提示 ：1）先查看线索,无线索时用下面规律：2）结点 *p 在先序序列中的后继为其左子或右子；3）结点 *p 在后序序列中的前驱也是其左子或右子；15分别写出算法,实现在中序线索二叉树中查找给定结点 *p 在中序序列中的前驱与后继；参例题）16编写算法,对一棵以孩子 提示 ：-兄弟链表表示的树统计其叶子的个数；1）可将 孩子 -兄弟链表 划分为 根、首子树 、兄弟树 ,递归处理；2

22、）可利用 返回值 ,或 全局变量 ；名师归纳总结 - - - - - - -第 16 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用17对以孩子 -兄弟链表表示的树编写运算树的深度的算法；18已知二叉树根据二叉链表方式储备,利用栈的基本操作写出后序遍 历非递归的算法；参课本）19设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正就 二叉树；正就二叉树是指：在二叉树中不存在子树个数为 1 的结点；提示 ：可利用任何递归、非递归遍历算法；20运算二叉树最大宽度的算法；二叉树的最大宽度是指：二叉树全部 层中结点个数的最大值；21已知二叉树根据二叉链

23、表方式储备,利用栈的基本操作写出先序遍 历非递归形式的算法；22. 证明：给定一棵二叉树的前序序列与中序序列,可唯独确定这棵二 叉树；给定一棵二叉树的后序序列与中序序列,可唯独确定这棵二叉树；名师归纳总结 - - - - - - -第 17 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 23. 二叉树根据二叉链表方式储备,编写算法将二叉树左右子树进行交 换；实习题1.建立一棵用二叉链表方式储备的二叉树,并对其进行遍历问题描述 先序、中序和后序）,打印输出遍历结果；基本要求 从键盘接受输入先序序列,以二叉链表作为储备结构,建立二叉树 以先序来建立）

24、并对其进行遍历先序、中序、后序）,然后将遍历结果打印输出；要求采纳递归和非递归两种方法实现；测试数据 ABC DE G F 其中 表示空格字符）输出结果为：先序：ABCDEGF 中序： CBEGDFA 后序： CGBFDBA 2已知二叉树根据二叉链表方式储备,编写算法,要求实现二叉树的 竖向显示 竖向显示就是二叉树的按层显示）；提示 ：1）参习题 6.20 ,实现逐层遍历名师归纳总结 - - - - - - -第 18 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用2）队中储存每个结点的打印位置,其左、右子的距离3如题 1 要求建立好二叉树,按凹入表形式打印二叉树结构,如图6.34 所示；图6.344按凹入表形式打印树形结构,如图 6.35 所示；提示 ：参 P.129 例,用先根遍历；名师归纳总结 - - - - - - -第 19 页,共 19 页