计算机软件技术02第二章 基本数据结构及其运算_作业03.ppt

第二章 作业 第三部分 2.19 写出下列各算术表达式的表达式树，再分别转化成二叉树，最后分别写出其波兰表达式。 ⑴ 2.20 设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。问T中有多少个叶子结点？ 树T中分支总数： 树T中的总结点数为： 非叶子结点总数： 叶子结点数为： 2.25 若图有n个结点，并用关联矩阵表示，则第k个结点的度为多少？ 2.25 若图有n个结点，并用关联矩阵表示，则第k个结点的度为多少？ 2.21（第154页） 已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG。试画出该二叉树，并写出该二叉树的后序序列。 2.22（第154页） 设一棵完全二叉树具有1000个结点。问该完全二叉树有多少个叶子结点？有多少个度为2的结点？有多少个度为1的结点？若完全二叉树有1001个结点，在回答上述问题，并说明理由。 补充习题01：给定权值{4，5，7，10，12，17}， ①??? 构造一棵哈（赫）夫曼树； ② 求其带权路径长度。 补充习题02：已知图G的邻接表如下图所示，求：①从顶点v1出发的深度优先搜索序列；②从顶点v1出发的广度优先搜索序列。 * A B C D 1 2 3 4 顶点的度=顶点出度+顶点入度 1 2 4 5 3 顶点的度= D B F A C E G ACBEGFD 6 2 1 7 5 4 3 8 9 10 11 12 6 2 1 7 5 4 3 8 9 10 11 13 12 4 5 9 7 16 10 12 22 17 33 55 1 2 3 4 ^ 5 2 5 4 ^ 3 5 ^ 5 4 ^ 2 3 4 ^ *