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

"数据结构应用题参考习题.pdf" 本资源提供了数据结构相关的应用题参考习题，涵盖树、图等数据结构的基础概念和应用题目。题目包括树的基本概念，如树的定义、树的遍历、树的性质等；图的基本概念，如图的定义、图的遍历、图的性质等。 一、树应用题 1. 已知一棵树的边的集合，试画出这棵树，并回答相关问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点g 的双亲？ （4）哪些是结点g 的祖先？ （5）哪些是结点g 的孩子？ （6）哪些是结点e 的孩子？ （7）哪些是结点e 的兄弟？ 哪些是结点f 的兄弟？ （8）结点 b 和 n 的层次号分别是什么？ （9）树的深度是多少？ （10）以结点 c 为根的子树深度是多少？ 2. 一棵度为 2 的树与一棵二叉树有何区别？ 3. 试分别画出具有3 个结点的树和二叉树的所有不同形态？ 4. 已知用一维数组存放的一棵完全二叉树，写出该二叉树的先序、中序和后序遍历序列。 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），试设计相应的哈夫曼树。 二、图应用题 1. 对于一个无向图1(a)，假定采用邻接矩阵表示，试分别写出从顶点0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 2. 对于一个有向图1(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 3. 已知一个无向图的邻接矩阵如图2(a)所示，试写出从顶点0 出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 这些题目涵盖了树和图的基本概念和应用，旨在帮助学习者深入理解数据结构的基础知识，并提高解决问题的能力。