数据结构形考作业3.docx
一、单项选择题（每小题2分，共32分）题目1假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）。选择一项：A. 17B. 16C. 15D.47题目2二叉树第k层上最多有（）个结点。选择一项：A. 2kB. 2k-C. 21D. 2k-题目3设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是（）。选择一项：A. debacB. abdecC. abedcD.debca题目4将含有150个结点的彻底二叉树从根这一层开始，每一层从左到右挨次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。选择一项：A. 36B. 35C. 33D. 34题目5如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。选择一项：A.平衡二叉树B.彻底二叉树C.哈夫曼树D.二叉树题目6在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为。的结点个数为（）o选择一项：A.7C.5D.4题目7在一棵度具有5层的满二叉树中结点总数为（）。选择一项：A. 31B. 32C. 16D. 33题目8利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。选择一项：A. 2*nB. nC. 2*n-lD. n+1题目9利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。选择一项：A. 16B. 18C. 12D.30题目10在一棵树中，（）没有前驱结点。选择一项：A.树根结点B.分支结点C,空结点D.叶结点题目11设一棵有n个叶结点的二叉树，除叶结点外每一个结点度数都为2,则该树共有（）个结点。选择一项：A. 2n-lB. 2n+lC. 2nD.2n+2题目12在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。选择一项：A.4C. 1/2D. 1题目13邻接表是图的一种（）。选择一项：A.链式存储结构B.散列存储结构C.索引存储结构D.顺序存储结构题目14如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。选择一项：A.有回路B.一棵树C.彻底图D.连通图题目15图的深度优先遍历算法类似于二叉树的（）遍历。选择一项：A.先序B.层次C.后序D.中序题目16已知下图所示的一个图，若从顶点Vl出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。选择一项：A-v!v2v4vsW6v7B.XV2V4V8V3V5V6V7cv1v2v4v8vsW7D¾v6v7v2v4v5v8二、填空题（每小题1分，共20分）题目17结点的度是指结点所拥有的子树树木或者后继结点数。题目18树的度是指树中所有结点的度的最大值。题目19度大于0的结点称作或者O分支结点、非终端结点题目20满分1.度等于0的结点称作或者O叶子结点、非终端结点题目21在一棵树中，每一个结点的或者说每一个结点的称为该结点的，简称为孩子。子树的根、后继结点、孩子结点题目22从根结点到该结点所经分支上的所有结点称为该结点的祖先。题目23树的深度或者高度是指树中结点的最大层数。题目24具有n个结点的彻底二叉树的深度是。Iog2n+1题目25先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树，先序遍历二叉树的右子树。题目26中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左子树；访问而叉树的根结点，中序遍历二叉树的右子树。题目27后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树；后序遍历二叉树的右子树，访问而叉树的根结点。题目28将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权。题目29树的带权路径长度为树中所有叶子结点的带权路径长度之和。题目30哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。题目31若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。题目32具有m个叶子结点的哈夫曼树共有2mL结点。题目33图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中所有顶点各做次访问的过程。题目34图的深度优先搜索遍历类似于树的光序遍历。题目35图的广度优先搜索类似于树的按层次遍历。题目36图常用的两种存储结构是和邻接矩阵、邻接表三、综合题（每小题8分，共40分）题目37写出如下图所示的二叉树的先序、中序和后序遍历序列。答:二叉树的定义是递归的，所以，一颗二叉树可看做由根结点，左子树和右子树这三个基本部份组成，即挨次遍历整个二叉树，右子树或者左子树又可看做颗二叉树并继续分为根结点、左子树和右子树三部份，这样划分向来进行到树叶结点。（1）先序为“根摆布"，先序序列为：fdbacegihl（2）先序为“左根右”，先序序列为：abcdefghij（3）先序为“摆布根”，先序序列为：acbedhjigf题目38已知某二叉树的先序遍历结果是：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,请画出这棵二叉树，并写出该二叉树后续遍历的结果。该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C、A题目39假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们浮现的频率分别是:10、20、5、15、8、2、3、7和30。请请用这9个字母浮现的频率作为权值求：（1）设计一棵哈夫曼树；（2）计算其带权路径长度WPL；（3）写出每一个字符的哈夫曼编码。(2)带权路径长度WPL值为270每一个字符的哈夫曼编码为：A：100,B：11,C：1010,D：OoO,E：0010,F：10110,G：IOlll,H：0011,I：01题目40请根据以下带权有向图G(1)给出从结点Vl出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；(2)给出G的一个拓扑序列；(3)给出从结点Vl到结点v8的最短路径。深度优先遍历:vl,v2,v3,v8,v5,v7,v4,v6广度优先遍历:vl,v2,v4,v6zv3,v5v7,v8(2)G的拓扑序列为：VI,V2,V4,V6,V5,B5,V3,V5,V7,V8(3)其最短路径为：VI,V2,V5,V7,V8题目41已知无向图G描述如下：G=(V,E)V=V1,V2,V3,V4,V5E=(Vl,V2),(Vl,V4),(V2,V4),(V3,V4),(V2,V5),(V3,V4),(V3,V5)(1)画出G的图示；(2)然后给出G的邻接矩阵和邻接表；(3)写出每一个顶点的度。010101001100011IllOOG的邻接矩阵HZ04EH0HZlzHZIIITIlU卜<3卜|-HZEZHIIG的邻接表2、 3、 2、 3、 2Vl、V2、V3、V4、V5的度分别为:四、程序填空题（每空2分，共8分）题目42满分4.00以下是中序遍历二叉树的递归算法的程序，完成程序中空格部份（树结构中左、右指针域分别为Ieft和right,数据域data为字符型，BT指向根结点）。voidInorder（structBTreeNode*BT）if(BT!=NULL)lnorder(BT->left);printf(',%c",BT->data);lnorderBT->right);)题目43满分4.00以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部份（树结构中左、右指针域分别为Ieft和right,数据域data为字符型，BT指向根结点）。voidInorder（structBTreeNode*BT）if(BT!=NULL)lnorder(BT->left);lnorder(BT->right);printf("%c,BT->data);)
