形考作业三及答案

形考作业三及 本部分作业覆盖教材第6-7章的内容） 一、单项选择题 1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（     ）。 A．15           B．16               C．17           D．47 2．二叉树第k层上最多有（     ）个结点。 A．2k                 B．2k-1 C．2k-1                   D．2k-1    3．二叉树的深度为k，则二叉树最多有（     ）个结点。 A．2k                   B．2k-1 C．2k-1                  D．2k-1 4. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（      ）。 A．abdec      B．debac     C．debca       D．abedc 5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（    ）。 A．33       B．34          C．35        D．36 6．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（   ）。 A．哈夫曼树                B．平衡二叉树 C．二叉树                  D．完全二叉树 7．下列有关二叉树的说法正确的是（   ）。 A．二叉树中度为0的结点的个数等于度为2的结点的个数加1 B．二叉树中结点个数必大于0 C．完全二叉树中，任何一个结点的度，或者为0或者为2        D．二叉树的度是2 8．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（    ）。 A．4         B．5           C．6          D．7 9．在一棵度具有5层的满二叉树中结点总数为（    ）。 A．31         B．32          C．33        D．16 10. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有(    )个结点。 A. n         B. n+1        C. 2*n        D. 2*n-1 11. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为(    )。 A. 18        B. 16         C. 12         D. 30 12．在一棵树中，（    ）没有前驱结点。 A．分支结点        B．叶结点         C．树根结点      D．空结点 13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（   ）。 A．2i                B．2i-1       D．2i+1      C．2i+2          14．设一棵哈夫曼树共有n个叶结点，则该树有（    ）个非叶结点。 A．n                B．n-1        C．n+1           D．2n 15．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（   ）个结点。  A．2n                B．2n-1        C．2n+1         D．2n+2         16．在一个图G中，所有顶点的度数之和等于所有边数之和的（     ）倍。 A．1/2          B．1           C．2          D．4 17．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（    ）倍。 A．1/2            B．2           C．1         D．4 18．一个具有n个顶点的无向完全图包含（        ）条边。 A．n（n-1）       B．n（n+1）       C． n（n-1）/2   D． n（n+1）/2 19．一个具有n个顶点的有向完全图包含（        ）条边。 A．n（n-1）       B．n（n+1）       C． n（n-1）/2   D． n（n+1）/2 20．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（    ）。 A．n              B．n2          C．n-1       D．（n-1）2 21．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（      ）。 A．n              B．e           C．2n        D．2e 22．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（    ）邻接点。 A．入边                             B．   出边          C．入边和出边                       D．   不是入边也不是出边    23．邻接表是图的一种（      ）。 A．顺序存储结构                     B．链式存储结构          C．索引存储结构                     D．散列存储结构 24．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（       ）。 A．完全图          B．连通图       C．有回路        D．一棵树 25．下列有关图遍历的说法不正确的是（      ）。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历每一顶点仅被访问一次 26．无向图的邻接矩阵是一个（      ）。 A．对称矩阵          B． 零矩阵       C．上三角矩阵     D．对角矩阵 27．图的深度优先遍历算法类似于二叉树的（    ）遍历。 A．先序          B．中序      C．后序    D．层次 28．已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（    ）。 A．V1V2V4V8V3V5V6V7           B．V1V2V4V5V8V3V6V7   C．V1V2V4V8V5V3V6V7           D．V1V3V6V7V2V4V5V8 二、填空题 1．结点的度是指结点所拥有的       。 2．树的度是指                                           。 3．度大于0的结点称作                或                。 4．度等于0的结点称作                或                。 5．在一棵树中，每个结点的               或者说每个结点的             称为该结点的               ，简称为孩子。 6．从根结点到该结点所经分支上的所有结点称为该结点的            。 7．树的深度或高度是指               。 8．具有n个结点的完全二叉树的深度是               。 9．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的             ；先序遍历二叉树的            ，先序遍历二叉树的      。 10．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的             ；访问而叉树的            ，中序遍历二叉树的      。 11．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的             ；后序遍历二叉树的             ，访问而叉树的      。 12．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的        。 13．树的带权路径长度为树中所有叶子结点的                          。 14．哈夫曼树又称为               ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL               。 15．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是           。 16．具有m个叶子结点的哈夫曼树共有           结点。 17．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系。 18．图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中             各做   访问的过程。 19．图的深度优先搜索遍历类似于树的          遍历。 20．图的广度优先搜索类似于树的 遍历。 21．具有n个顶点的有向图的邻接矩阵，其元素个数为         。 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个结点，求 ⑴ 树的高度 ⑵ 叶子结点数 ⑶ 单支结点数 ⑷ 最后一个非终端结点的序号 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，V5} E={（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=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; visited[i]=1;  (1)                     if(GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j]) { printf("(%d,%d)%d,",i,j,GA[i][j]); (2)                            } } 五、算法设计题 1．写一个将一棵二叉树复制给另一棵二叉树的算法。 2．根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。 int BTreeLeafCount(struct BTreeNode* BT); 六、完成： 实验3――栈、队列、递归程序设计 实验4——图的存储方式和应用 根据实验要求（见教材P203）认真完成本实验，并提交实验。 数据结构（本）形成性考核作业答案 数据结构（本）作业3 （本部分作业覆盖教材第6-7章的内容） 一、单项选择题 （1） B 说明：任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则 n0 = n2 + 1。 n0 = n2 + 1 = 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 + 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 说明：构造的哈夫曼树如图： 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）中序为“左根右”，中序序列为：abcdefghij （3）后序为“左右根”，后序序列为：acbedhjigf 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，请画出这棵二叉树，并写出该该二叉树后续遍历的结果。 （1） 二叉树图形表示如下： （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3、 答: （1）已知深度为k的二叉树最多有2k-1个结点（K≥1）， 29-1<892< 210-1，故树的高度为10 （2）对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1 得：设n1=0，892=n0+0+n2=2n2+1　得n2不为整数出错 设n1=1，892=n0+1+n2=2n2+2　 得n2 =445→ n0=n2+1=446 叶子结点数为446。 （3）由（2）得单支结点数为1 （4）对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点即为最后一个非终端结点，序号为892/2=446。 4、 答： （1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树 （2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树 （3）先序和后序序列相同的二叉树为空树或仅有一个结点 5、 答： （1）哈夫曼树如图所示。 （2）其带权路径长度WPL值为270。 （3）每个字符的哈夫曼编码为：A：0000，B：01，C：00010， D：100， E：1011，F：00110，G：00111，H：1010，I：11 6、 答： （1）深度优先遍历：v1,v2,v3,v8,v5,v7,v4,v6 广度优先遍历：v1,v2,v4,v6,v3,v5,v7,v8 （2）G的拓扑序列为：v1,v2,v4,v6,v5,v5,v3,v5,v7,v8 （3）最短路径为：v1,v2,v5,v7,v8 7、 答： ①　g1的图示和图g1的邻接表如下图所示。 图G                              ②　图G的邻接矩阵如下图所示： 图G的邻接矩阵                      图G的邻接表 ③　V1、V2、V3、V4、V5的度分别为：2，3，2，3，2  四、程序题 1、 （1）return c1+1 （2）NodeLevel（BT->right,X） （3）（c2>=1） return c2+1 2、 （1）for（j=0; jdata=p->data; t->lchild=CopyTree（p->lchild）; t->rchild=CopyTree（p->rchild）; return（t）; } else return（NULL）; }/*CopyTree*/ 2、 参考答案： int BTreeLeafCount（struct BTreeNode* BT） { if（BT==NULL） return 0; else if（BT->left==NULL && BT->right==NULL） return 1; else return BTreeLeafCount（BT->left）+BTreeLeafCount（BT->right）; } 六、完成：实验3――栈、队列、递归程序设计 实验4——图的存储方式和应用 根据实验要求（见教材P203）认真完成本实验，并提交实验报告。