形考作业三及答案

1、形考作业三及答案本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。A15 B16 C17 D472二叉树第k层上最多有（ ）个结点。A2k B2k-1C2k-1 D2k-1 3二叉树的深度为k，则二叉树最多有（ ）个结点。A2k B2k-1C2k-1 D2k-14. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。Aabdec Bdebac Cdebca Dabedc5将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编

2、号为69的结点的双亲结点的编号为（ ）。A33 B34 C35 D366如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树7下列有关二叉树的说法正确的是（ ）。A二叉树中度为0的结点的个数等于度为2的结点的个数加1B二叉树中结点个数必大于0C完全二叉树中，任何一个结点的度，或者为0或者为2 D二叉树的度是28在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。A4 B5 C6 D79在一棵度具有5层的满二叉树中结点总数为（ ）。A31 B32 C33 D1610. 利用

3、n个值作为叶结点的权生成的哈夫曼树中共包含有( )个结点。A. n B. n+1 C. 2*n D. 2*n-111. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( )。A. 18 B. 16 C. 12 D. 3012在一棵树中，（ ）没有前驱结点。A分支结点 B叶结点 C树根结点 D空结点13在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A2i B2i-1 D2i+1 C2i+2 14设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。An Bn-1 Cn+1 D2n15设一棵有n个叶结点的二叉树，除叶

4、结点外每个结点度数都为2，则该树共有（ ）个结点。 A2n B2n-1 C2n+1 D2n+2 16在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。A1/2 B1 C2 D4 17在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。A1/2 B2 C1 D418一个具有n个顶点的无向完全图包含（ ）条边。An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/219一个具有n个顶点的有向完全图包含（ ）条边。An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/220对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。

5、An Bn2 Cn-1 D（n-1）221对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。An Be C2n D2e22在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。A入边 B 出边 C入边和出边 D 不是入边也不是出边 23邻接表是图的一种（ ）。A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构24如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。A完全图 B连通图 C有回路 D一棵树25下列有关图遍历的说法不正确的是（ ）。A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中

6、邻接点的寻找具有“先进先出”的特征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次26无向图的邻接矩阵是一个（ ）。A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵27图的深度优先遍历算法类似于二叉树的（ ）遍历。A先序 B中序 C后序 D层次28已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8二、填空题1结点的度是指结点所拥有的 。2树的度是指 。3度大于0的结点称作 或 。4度等于0

7、的结点称作 或 。5在一棵树中，每个结点的 或者说每个结点的 称为该结点的 ，简称为孩子。6从根结点到该结点所经分支上的所有结点称为该结点的 。7树的深度或高度是指 。8具有n个结点的完全二叉树的深度是 。9先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 ；先序遍历二叉树的 ，先序遍历二叉树的 。10中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 ；访问而叉树的 ，中序遍历二叉树的 。11后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 ；后序遍历二叉树的 ，访问而叉树

8、的 。12将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 。13树的带权路径长度为树中所有叶子结点的 。14哈夫曼树又称为 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL 。15若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。16具有m个叶子结点的哈夫曼树共有 结点。17在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系。18图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 各做 访问的过程。19图的深度优先搜索遍历类似于树的 遍历。20图的广度优先搜索类似于树的 遍历。21具有n个顶点的有向图的邻接矩阵，其元

9、素个数为 。22图常用的两种存储结构是 和 。23在有n个顶点的有向图中，每个顶点的度最大可达 。24在一个带权图中，两顶点之间的最段路径最多经过 条边。25为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 。三、综合题1写出如下图所示的二叉树的先序、中序和后序遍历序列。2已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。3已知一棵完全二叉树共有892个结点，求 树的高度 叶子结点数 单支结点数 最后一个非终端结点的序

10、号4给出满足下列条件的所有二叉树。（1）先序和中序相同（2）中序和后序相同（3）先序和后序相同5假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求：（1）设计一棵哈夫曼树；（2）计算其带权路径长度WPL；（3）写出每个字符的哈夫曼编码。6请根据以下带权有向图G（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；（2）给出G的一个拓扑序列；（3）给出从结点v1到结点v8的最短路径。7已知无向图G描述如下：G=（V，E）V=V1，V2，V3，V4，V

11、5E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）（1）画出G的图示；（2）然后给出G的邻接矩阵和邻接表；（3）写出每个顶点的度。四、程序填空题1. 下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。 int NodeLevel(struct BinTreeNode* BT, char X) if(BT=NULL) return 0; /*空树的层号为0*/ else if(BT-data=X) return 1; /*根结点的层号为1*/ /*向子树中查找X结点*/ else int c1

12、=NodeLevel(BT-left,X); if(c1=1) _(1)_; int c2=_(2)_ _; if _(3)_; /若树中不存在X结点则返回0 else return 0; 2. 下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。 void dfstree(adjmatrix GA, int i, int n) int j; visitedi=1; (1) if(GAij!=0 & GAij!=MaxValue & !visitedj) printf(%d,%d)%d,i,j,GAij); (2) 五、算法设计题1写

13、一个将一棵二叉树复制给另一棵二叉树的算法。2根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。 int BTreeLeafCount(struct BTreeNode* BT);六、完成：实验3栈、队列、递归程序设计实验4图的存储方式和应用根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）形成性考核作业答案数据结构（本）作业3（本部分作业覆盖教材第6-7章的内容）一、单项选择题（1） B说明：任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则 n0 = n2 + 1。 n0 = n2 + 1 =

14、15+1 = 16 该题跟单分支结点数无关。（2） B（3） D （4） C 说明：根据先序和中序遍历得到二叉树为：所以后序遍历为debca。（5） B （6） A （7） A（8） C 说明：任何一棵三叉树，若叶子结点数为n0，度为2的结点数为n2，度为3的结点数为n3，则 n0 = n3 + n2 + 1。（9） A说明：25-1=31（10） D（11） A说明：构造的哈夫曼树如图：每个叶子结点最长带权路径长度的为：9 ：18 ：16 ：12最长叶子结点最长带权路径长度的为：18（12） C（13） C（14） B（15） B说明：n0 = n2 + 1，那么n2 = n0 - 1，n0

15、 + n2 = 2n0 1。（16） C（17） C（18） C （19） A（20） B（21） D（22） B （23） B （24） B （25） C（26） A（27） A（28） C二、填空题 （1） 非空子树数或后继结点数（2） 树中所有结点的度的最大值（3） 分支结点 非终端结点（4） 叶子结点 终端结点（5） 子树的根 后继结点 孩子结点（6） 祖先（7） 树中结点的最大层数（8） （9） 根结点 左子树 右子树（10） 左子树 根结点 右子树（11） 左子树 右子树 根结点（12） 权（13） 带权路径长度之和（14） 最优二叉树 最小的二叉树（15） 69说明：构造的哈夫曼

16、树如图：WPL=（4+5）*3 +（6+7+8）*2 =69（16） 2m-1（17） 多对多（18） 所有顶点 一次（19） 先序（20） 按层次（21） n2（22） 邻接矩阵 邻接表（23） 2（n-1）（24） n-1（25） 栈三、综合题1、 写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分.，这样划分一直进行到树叶结点。（1）先序为“根左右”，先序序列为：fdbacegihl（2）中序为“左根

17、右”，中序序列为：abcdefghij（3）后序为“左右根”，后序序列为：acbedhjigf2、 已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该该二叉树后续遍历的结果。（1） 二叉树图形表示如下： （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3、 答:（1）已知深度为k的二叉树最多有2k-1个结点（K1）， 29-1892right,X）（3）（c2=1） return c2+12、 （1）for（j=0; jdata=p-data;t-lchild=CopyTree（p-lchild）;t-rchild=CopyTree（p-rchild）;return（t）;el