|
假设在树中结点x是结点y的双亲时用(xy)来表示树边已知一棵树边的集合为{(im)(in)(ei)(be)(bd)(ab)(gj)(gk)(cg)(cf)(hl)(ch)(ac)}用树形表示法出此树并回答下列问题 ()哪个是根结点? ()哪些是叶结点? ()哪个是g的双亲? ()哪些是g的祖先? ()哪些是g的孩子? ()哪些是e的子孙? ()哪些是e的兄弟?哪些是f的兄弟? ()结点b和n的层次各是多少? ()树的深度是多少? ()以结点c为根的子树的深度是多少? () 树的度数是多少? 一棵度为的有序树与一棵二叉树有何区别? 试分别画出具有个结点的树和个结点的二叉树的所有不同形态 已知一棵度为m的树中有n个度为的结点n个度为的结点nm个度为m的结点问该树中有多少片叶子? 一个深度为h的满k叉树有如下性质第h层上的结点都是叶子结点其余各层上每个结点都有k棵非空子树如果按层次顺序(同层自左至右)从开始对全部结点编号问 ()各层的结点数目是多少? ()编号为i的结点的双亲结点(若存在)的编号是多少? ()编号为i的结点的第j个孩子结点(若存在)的编号是多少? ()编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 在具有n个结点的k叉树(k>=)的k叉链表表示中有多少个空指针? 假设二叉树包含的结点数据为 ()画出两棵高度最大的二叉树 ()画出两棵完全二叉树要求每个双亲结点的值大于其孩子结点的值 试找出分别满足下面条件的所有二叉树 ()前序序列和中序序列相同 ()中序序列和后序序列相同 ()前序序列和后序序列相同 ()前序中序后序序列均相同 试采用顺序存储方法和链接存储方法分别画出（下图）所示各二叉树的存储结构 分别写出图(下图)所示各二叉树的前序中序和后序序列 若二叉树中各结点的值均不相同则由二叉树的前序序列和中序序列或由其后序序列和中序序列均能唯一地确定一棵二叉树但由前序序列和后序序列却不一定能唯一地确定一棵二叉树 ()已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF请画出此二叉树 ()已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA请画出此二叉树 ()已知一棵二叉树的前序序列和后序序列分别为AB和BA请画出这两棵不同的二叉树 对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历遍历所得到的结点序列称为二叉树层次序列现已知一棵二叉树的层次序列为ABCDEFGHIJ中序序列为DBGEHJACIF请画出此二叉树 试画出图(上图)所示各二叉树的前序中序和后序线索树及相应的线索链表 在何种线索树中线索对求指定结点在相应次序下的前趋和后继并无帮助? 对图(下图)所示的森林 ()求各树的前序序列和后序序列 ()求森林的前序序列和后序序列 ()将此森林转换为相应的二叉树 ()给出(a)所示树的以亲链表表示孩子链表表示双亲孩子链表表示及孩子兄弟链表示等四种存储结构并指出哪些存储结构易于求指定结点的祖先哪些易于求指定结点的后代? 画出图(下图)所示的各二叉树所对应的森林 高度为h的严格二叉树至少有多少个结点?至多有多少个结点? 在什么样的情况下等长编码是最优的前缀码? 下述编码哪一组不是前缀码? {}{}{} 假设用于通信的电文由字符集{abcdefgh}中的字母构成这个字母在电文中出现的概率分别为{} ()为这个字母设计哈夫曼编码 ()若用这三位二进制数(…)对这个字母进行等长编码则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少? |
