数据结构形考作业3

《数据结构形考作业3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、单项选择题（每小题2分，共32分）题目1假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。选择一项：A.17B.16C.15D.47题目2二叉树第k层上最多有（）个结点。选择一项：A.2kB.2k-1C.2k-1D.2k-1题目3设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。选择一项：A.debacB.abdecC.abedcD.debca题目4将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。选择一项：

2、A.36B.35C.33D.34题目5如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。选择一项：A.平衡二叉树B.完全二叉树C.哈夫曼树D.二叉树题目6在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）。选择一项：A.7B.6C.5D.4题目7在一棵度具有5层的满二叉树中结点总数为（）。选择一项：A.31B.32C.16D.33题目8利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。选择一项：A.2*nB.nC.2*n-1D.n+1题目9利用3、6、8、12这四个值作为叶子结点的权

3、，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。选择一项：A.16B.18C.12D.30题目10在一棵树中，（）没有前驱结点。选择一项：A.树根结点B.分支结点C.空结点D.叶结点题目11设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。选择一项：A.2n-1B.2n+1C.2nD.2n+2题目12在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。选择一项：A.4B.2C.1/2D.1题目13邻接表是图的一种（）。选择一项：A.链式存储结构B.散列存储结构C.索引存储结构D.顺序存储结构题目14如果从无向图的

4、任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。选择一项：A.有回路B.一棵树C.完全图D.连通图题目15图的深度优先遍历算法类似于二叉树的（）遍历。选择一项：A.先序B.层次C.后序D.中序题目16已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。选择一项：A.V1V2V4V5V8V3V6V7B.V1V2V4V8V3V5V6V7C.V1V2V4V8V5V3V6V7D.V1V3V6V7V2V4V5V8二、填空题（每小题1分，共20分）题目17结点的度是指结点所拥有的子树树木或后继结点数。题目18树的

5、度是指树中所有结点的度的最大值。题目19度大于0的结点称作__________________或__________________。分支结点、非终端结点题目20满分1.00度等于0的结点称作__________________或__________________。叶子结点、非终端结点题目21在一棵树中，每个结点的_______________或者说每个结点的_______________称为该结点的_______________，简称为孩子。子树的根、后继结点、孩子结点题目22从根结点到该结点所经分支上的所有结点称为该结点的祖先。题目23树的深度或高度是指树中结

6、点的最大层数。题目24具有n个结点的完全二叉树的深度是_____________。[log2n]+1题目25先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树，先序遍历二叉树的右子树。题目26中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左子树；访问而叉树的根结点，中序遍历二叉树的右子树。题目27后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树；后序遍历二叉树的右子树，访问而叉树的根结点。题目28将树中结点赋上

7、一个有着某种意义的实数，称此实数为该结点的权。题目29树的带权路径长度为树中所有叶子结点的带权路径长度之和。题目30哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。题目31若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。题目32具有m个叶子结点的哈夫曼树共有2m-1结点。题目33图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中所有顶点各做一次访问的过程。题目34图的深度优先搜索遍历类似于树的先序遍历。题目35图的广度优先搜索类似于树的按层次遍历。题目36图常用的两种存储结构是__