2021年数据结构本形成性考核作业

数据构造（本）课程作业作业3（本某些作业覆盖教材第6-7章内容）一、单项选取题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。A．15B．16C2．二叉树第k层上最多有（）个结点。A．2kB．2k-1C．2k-1D．2k-13．二叉树深度为k，则二叉树最多有（）个结点。A．2kB．2k-1C．2k-1D．2k-14.设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历顺序是（）。A．abdecB．debacC．debcaD．abedc5．将具有150个结点完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为69结点双亲结点编号为（）。A．33B．34C．35D．366．如果将给定一组数据作为叶子数值，所构造出二叉树带权途径长度最小，则该树称为（）。A．哈夫曼树B．平衡二叉树C．二叉树D．完全二叉树7．下列关于二叉树说法对的是（）。A．二叉树中度为0结点个数等于度为2结点个数加1B．二叉树中结点个数必不不大于0C．完全二叉树中，任何一种结点度，或者为0或者为2D．二叉树度是28．在一棵度为3树中，度为3结点个数为2，度为2结点个数为1，则度为0结点个数为（）。A．4B．5C．6D．79．在一棵度具备5层满二叉树中结点总数为（）。A．31B．32C．33D．1610.运用n个值作为叶结点权生成哈夫曼树中共包具有()个结点。A.nB.n+1C.2*nD.2*n-111.运用3、6、8、12这四个值作为叶子结点权，生成一棵哈夫曼树，该树中所有叶子最长带权途径长度为()。A.18B.16C.12D.312．在一棵树中，（）没有前驱结点。A．分支结点B．叶结点C．树根结点D．空结点13．在一棵二叉树中，若编号为i结点存在右孩子，则右孩子顺序编号为（）。A．2iB．2i-1D．2i+114．设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。A．nB．n-1C15．设一棵有n个叶结点二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。A．2nB．2n-1C．2n+1D．2n+216．在一种图G中，所有顶点度数之和等于所有边数之和（）倍。A．1/2B．1C．2D．417．在一种有向图中，所有顶点入度之和等于所有顶点出度之和（）倍。A．1/2B．2C．1D．18．一种具备n个顶点无向完全图包括（）条边。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/219．一种具备n个顶点有向完全图包括（）条边。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/220．对于具备n个顶点图，若采用邻接矩阵表达，则该矩阵大小为（）。A．nB．n2C．n1D．（n1）21．对于一种具备n个顶点和e条边无向图，若采用邻接表表达，则所有顶点邻接表中结点总数为（）。A．nB．eC．2nD．2e22．在有向图邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。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．V1V2V4V8V3V5V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V5V3V6V7D．V1V3V6V7V2V4V5V8V6V6V7V1V2V3V8V4V5二、填空题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．写出如下图所示二叉树先序、中序和后序遍历序列。aajfghidceb2．已知某二叉树先序遍历成果是：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结点所在层号，请在划有横线地方填写适当内容。intNodeLevel(structBinTreeNode*BT，charX){if(BT==NULL)return0；/*空树层号为0*/elseif(BT->data==X)return1；/*根结点层号为1*//*向子树中查找X结点*/else{intc1=NodeLevel(BT->left,X);if(c1>=1)___(1)___________；intc2=______(2)__________；if___(3)__________________；//若树中不存在X结点则返回0elsereturn0;}}2.下面函数功能是按照图深度优先搜索遍历办法，输出得到该图生成树中各条边，请在划有横线地方填写适当内容。voiddfstree(adjmatrixGA，inti，intn){intj;visited[i]=1；(1)if(GA[i][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]){printf("(%d,%d)%d,",i,j,GA[i][j]);