《数据结构形成性考核作业3》由会员分享，可在线阅读，更多相关《数据结构形成性考核作业3（8页珍藏版）》请在金锄头文库上搜索。
1、1 数据结构（本）课程作业作业 3（本部分作业覆盖教材第6-7 章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。A15 B16 C17 D47 2二叉树第k 层上最多有（）个结点。A 2k B2k-1 C 2k-1 D2k-1 3二叉树的深度为k，则二叉树最多有（）个结点。A2k B2k-1 C2k-1 D2k-1 4.设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。A abdec B debac Cdebca Dabedc5将含有150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点
2、进行编号，根结点的编号为1，则编号为69 的结点的双亲结点的编号为（）。A33 B34 C35 D36 6如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树7下列有关二叉树的说法正确的是（）。A二叉树中度为0 的结点的个数等于度为2 的结点的个数加1 B二叉树中结点个数必大于0 C完全二叉树中，任何一个结点的度，或者为0 或者为 2 D二叉树的度是2 8在一棵度为3 的树中，度为3 的结点个数为2，度为 2 的结点个数为1，则度为0的结点个数为（）。A4 B5 C 6 D7 9在一棵度具有5 层的满二叉树中结点
3、总数为（）。A31 B32 C33 D16 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空结点名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -2 13在一棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（）。A 2i B2i-1 D2i+1 C2i+2 14设一棵
4、哈夫曼树共有n 个叶结点，则该树有（）个非叶结点。A n Bn-1 Cn+1 D2n 15 设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。A 2n B2n-1 C2n+1 D2n+2 16在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。A 1/2 B1 C2 D4 17在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A 1/2 B2 C1 D4 18一个具有n 个顶点的无向完全图包含（）条边。A n（n 1）Bn（n 1）C n（n 1）/2 D n（n 1）/2 19一个具有n 个顶点的有向完全图包含（）条边。A n（n 1）
5、Bn（n 1）C n（n 1）/2 D n（n 1）/2 20对于具有n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。A n Bn2 Cn 1 D（n 1）2 21对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。A n Be C2n D2e 22在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A 入边 B出边C 入边和出边 D不是入边也不是出边23邻接表是图的一种（）。A 顺序存储结构 B链式存储结构C 索引存储结构 D散列存储结构 24如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A
6、 完全图 B连通图 C有回路 D一棵树25下列有关图遍历的说法不正确的是（）。A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次 26无向图的邻接矩阵是一个（）。A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵27图的深度优先遍历算法类似于二叉树的（）遍历。A 先序 B 中序 C后序 D层次28已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A V1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V
7、6V7 DV1V3V6V7V2V4V5V8 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -3 二、填空题1结点的度是指结点所拥有的。2树的度是指。3度大于 0 的结点称作或。4度等于 0 的结点称作或。5在一棵树中，每个结点的或者说每个结点的称为该结点的，简称为孩子。6从根结点到该结点所经分支上的所有结点称为该结点的。7树的深度或高度是指。8具有 n 个结点的完全二叉树的深度是。9先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的；先序遍历二叉树的，先序遍历二叉树的。10中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进
8、行如下操作，中序遍历二叉树的；访问而叉树的，中序遍历二叉树的。11后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的；后序遍历二叉树的，访问而叉树的。12将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。13树的带权路径长度为树中所有叶子结点的。14哈夫曼树又称为，它是 n 个带权叶子结点构成的所有二叉树中带权路径长度WPL。15若以4，5，6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是。16具有 m 个叶子结点的哈夫曼树共有结点。17在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系。18图的遍历是从图
9、的某一顶点出发，按照一定的搜索方法对图中各做访问的过程。19图的深度优先搜索遍历类似于树的遍历。20图的广度优先搜索类似于树的遍历。V6V7V1V2V3V8V4V5名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -4 21具有 n 个顶点的有向图的邻接矩阵，其元素个数为。22图常用的两种存储结构是和。23在有 n 个顶点的有向图中，每个顶点的度最大可达。24在一个带权图中，两顶点之间的最段路径最多经过条边。25为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。三、综合题1写出如下图所示的二叉树的先序、中序和后序遍历序列。2已知某二叉树的先序遍历结
10、果是：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 个结点，求 树的高度 叶子结点数 单支结点数 最后一个非终端结点的序号a j f g h i d c e b 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -5 4给出满足下列条件的所有二叉树。（1）先序和中序相同（2）中序和后序相同（3）先序和后序相同5假设通信用的报文由9 个字母 A、B、C、D、E、F、G、H 和 I 组成，它们出现的频率分别是：10
11、、20、5、15、8、2、3、7 和 30。请请用这9 个字母出现的频率作为权值求：（1）设计一棵哈夫曼树；（2）计算其带权路径长度WPL；（3）写出每个字符的哈夫曼编码。6请根据以下带权有向图G（1）给出从结点v1 出发分别按深度优先搜索遍历G 和广度优先搜索遍历G 所得的结点序列；（2）给出 G 的一个拓扑序列；（3）给出从结点v1 到结点 v8 的最短路径。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -6 7已知无向图G 描述如下：G=（V，E）V=V1，V2，V3，V4，V5 E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），
12、（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)_ _;i
13、f _(3)_;/若树中不存在X结点则返回0 else return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -7 2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。void dfstree(adjmatrix GA,int i,int n)int j;visitedi=1;(1)if(GAij!=0&GAij!=MaxValue&!visitedj)printf(%d,%d)%d,i,j,GAij);(2)五、算法设计题1写一个将一棵二叉树复制给另一棵二叉树的算法。2 根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。int BTreeLeafCount(struct BTreeNode*BT);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -8 六、完成：实验3栈、队列、递归程序设计实验 4图的存储方式和应用根据实验要求（见教材P203）认真完成本实验，并提交实验报告。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -
