《数据结构》应用题参考习题.doc

一．《树》应用题 1. 已知一棵树边的集合为{i，m，i，n，e，i，b，e，b，d，a，b，g，j，g，k，c，g，c，f，h，l，c，h，a，c}，请画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点g的双亲？ （4）哪些是结点g的祖先？ （5）哪些是结点g的孩子？ （6）哪些是结点e的孩子？ （7）哪些是结点e的兄弟？哪些是结点f的兄弟？ （8）结点b和n的层次号分别是什么？ （9）树的深度是多少？ （10）以结点c为根的子树深度是多少？ 2. 一棵度为2的树与一棵二叉树有何区别。 3. 试分别画出具有3个结点的树和二叉树的所有不同形态？ 4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。 5. 一棵深度为H的满m叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有m棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题： （1）各层的结点数目是多少？ （2）编号为n的结点的父结点如果存在，编号是多少？ （3）编号为n的结点的第i个孩子结点如果存在，编号是多少？ （4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 6. 找出所有满足下列条件的二叉树： （1）它们在先序遍历和中序遍历时，得到的遍历序列相同； （2）它们在后序遍历和中序遍历时，得到的遍历序列相同； （3）它们在先序遍历和后序遍历时，得到的遍历序列相同； 7. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。 8. 假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。 9. 给出如图1所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。 10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。 解答： 根据给定的边确定的树如图2所示。 其中根结点为a； 叶子结点有：d、m、n、j、k、f、l； c是结点g的双亲； a、c是结点g的祖先； j、k是结点g的孩子； m、n是结点e的子孙； e是结点d的兄弟； g、h是结点f的兄弟； 结点b和n的层次号分别是2和5； 树的深度为5。 2. 解答： 度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。 3. 解答：　略 4. 解答：　 先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA 5. 解答： （1）第i层上的结点数目是mi-1。 （2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。 （3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。 （4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。 6. 解答： （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 7. 解答：后序序列：ACDBGJKIHFE 8. 解答：先序序列：ABCDGEIHFJK 9. 解答： 先根遍历：ABCDEFGHIJKLMNO 后根遍历：BDEFCAHJIGKNOML 森林转换成二叉树如图3所示。 10. 解答：构造而成的哈夫曼树如图4所示。 二．《图》应用题 1. 对于一个无向图1(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先有哪些信誉好的足球投注网站遍历得到的顶点序列和按广度优先有哪些信誉好的足球投注网站遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 2. 对于一个有向图1(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先有哪些信誉好的足球投注网站遍历得到的顶点序列和按广度优先有哪些信誉好的足球投注网站遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 3. 已知一个无向图的邻接矩阵如图2(a)所示，试写出从顶点0出发分别进行深度优先和广度优先有哪些信誉好的足球投注网站遍历得到的顶点序列。 4. 已知一个无向图的邻接表如图2(b)所示，试写出从顶点0出发分别进行深度优先和广度优先有哪些信誉好的足球投注网站遍历得到的顶点序列。 5. 已知图3所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。 6. 已知图3所示的一