数据结构形考作业3.docx

《数据结构形考作业3.docx》由会员分享，可在线阅读，更多相关《数据结构形考作业3.docx（8页珍藏版）》请在优知文库上搜索。

1、一、单项选择题（每小题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.

2、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这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中

3、所有叶子结点中的最长带权路径长度为（）。选择一项：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如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所

4、有顶点，则该图一定是（）。选择一项：A.有回路B.一棵树C.彻底图D.连通图题目15图的深度优先遍历算法类似于二叉树的（）遍历。选择一项：A.先序B.层次C.后序D.中序题目16已知下图所示的一个图，若从顶点Vl出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。选择一项：A-v!v2v4vsW6v7B.XV2V4V8V3V5V6V7cv1v2v4v8vsW7Dv6v7v2v4v5v8二、填空题（每小题1分，共20分）题目17结点的度是指结点所拥有的子树树木或者后继结点数。题目18树的度是指树中所有结点的度的最大值。题目19度大于0的结点称作或者O分支结点、非终端结点题目20满分1

5、.度等于0的结点称作或者O叶子结点、非终端结点题目21在一棵树中，每一个结点的或者说每一个结点的称为该结点的，简称为孩子。子树的根、后继结点、孩子结点题目22从根结点到该结点所经分支上的所有结点称为该结点的祖先。题目23树的深度或者高度是指树中结点的最大层数。题目24具有n个结点的彻底二叉树的深度是。Iog2n+1题目25先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树，先序遍历二叉树的右子树。题目26中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左子树；访问而叉树的根结点，中序遍历

6、二叉树的右子树。题目27后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树；后序遍历二叉树的右子树，访问而叉树的根结点。题目28将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权。题目29树的带权路径长度为树中所有叶子结点的带权路径长度之和。题目30哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。题目31若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。题目32具有m个叶子结点的哈夫曼树共有2mL结点。题目33图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中所

7、有顶点各做次访问的过程。题目34图的深度优先搜索遍历类似于树的光序遍历。题目35图的广度优先搜索类似于树的按层次遍历。题目36图常用的两种存储结构是和邻接矩阵、邻接表三、综合题（每小题8分，共40分）题目37写出如下图所示的二叉树的先序、中序和后序遍历序列。答:二叉树的定义是递归的，所以，一颗二叉树可看做由根结点，左子树和右子树这三个基本部份组成，即挨次遍历整个二叉树，右子树或者左子树又可看做颗二叉树并继续分为根结点、左子树和右子树三部份，这样划分向来进行到树叶结点。（1）先序为“根摆布，先序序列为：fdbacegihl（2）先序为“左根右”，先序序列为：abcdefghij（3）先序为“摆布

8、根”，先序序列为：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)带

9、权路径长度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题

10、目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卜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);)