数据结构本形成性考核作业及讲评-参考素材累积资料.docx

数据结构本形成性考核作业及讲评（本局部作业覆盖教材第6-7章的内容）一、单项选择题L假定一棵二叉树中，双分支结点数为15,单分支结点数为 30,那么叶子结点数为（）。A. 15 B. 16 C. 17 D. 47 2.二叉树第k层上最多有（） 个结点。A. 2k（k-l）B. 2k-lC. 2-1D. 2k3 .二叉树的深度为k,那么二叉树最多有（）个结点。A. 2kB. 2k-lC. 2k-lkD. 2-14 .设某一二叉树先序遍历为abdec,中序遍历为dbeac,那么 该二叉树后序遍历的顺序是（）。A. abdec B. debac C. debca D. abedc5 .树最适合于用来表示（）。A.线性结构的数据B.顺序结构的数据C.元素之间无前驱和后继关系的数据D.元素之间有包含和层次关系的数据6.设a, b为一棵二叉树的两个结点，在后续遍历中，a在b 前的条件是（）。A. a在b上方B. a在b下方C. a在b左方D. a在b右方7.权值为1, 2, 6, 8的四个结点构成的哈夫曼树的带权路 径长度是（）。A. 18 B. 28 C. 19 D. 298 .将含有150个结点的完全二叉树从根这一层开始，每一层 从左到右依次对结点进行编号，根结点的编号为1,那么编号为69 的结点的双亲结点的编号为（）。A. 33 B. 34 C. 35 D. 369 .如果将给定的一组数据作为叶子数值，所构造出的二叉树 的带权路径长度最小，那么该树称为（）。A.哈夫曼树B.平衡二叉树C.二叉树D.完全二叉树10 .以下有关二叉树的说法正确的选项是（）。A.二叉树中度为0的结点的个数等于度为2的结点的个数加1B.二叉树中结点个数必大于0C.完全二叉树中，任何一个结点的度，或者为0或者为2D.二叉树的度是211.在一棵度为3的树中，度为3的结点个数为2,度为2 的结点个数为1,那么度为0的结点个数为（）。A. 4 B. 5 C. 6 D. 712 .在一棵度具有5层的满二叉树中结点总数为（）。A. 31 B. 32 C. 33 D. 1613 .利用n个值作为叶结点的权生成的哈夫曼树中共包含有 （）个结点。A. n B. n+1 C. 2*n D. 2*nT14 .利用n个值作为叶结点的权生成的哈夫曼树中共包含有 （）个双支结点。A. n B. n-1 C. n+1 D. 2*n-1 15.利用 3、 6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该 树中所有叶子的最长带权路径长度为（）。A. 18 B. 16 C. 12 D. 3016 .在一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.树根结点D.空结点17 .在一棵二叉树中，假设编号为i的结点存在右孩子，那么右 孩子的顺序编号为（）。A. 2i B. 2i-l D. 2i+l C. 2i+2 18.设 一棵哈夫曼树共有n个叶结点，那么该树有（）个非叶结点。A. n B. n-1 C. n+1 D. 2n 19.设一棵有n个叶结点的二叉树，除叶 结点外每个结点度数都为2,那么该树共有（）个结点。A. 2n B. 2n-l C. 2n+l D. 2n+2 20. 一棵完全二叉树共有5层，且第5层上有六个结点，该树共有()个结点。A. 20 B. 21C. 23 D. 3021 .在一个图G中，所有顶点的度数之和等于所有边数之和 的()倍。A. 1/2 B. 1 C. 2 D. 422 .在一个有像图中，所有顶点的入度之和等于所有顶点的 出度之和的()倍。A.邻接矩阵表示法B.邻接表表示法C.逆 邻接表表示法D.邻接表和逆邻接表23 .在图的存储结构表示中，表示形式唯一的是()。A. n B. nl C. nl D. n/2 24. 一个具有n个顶点的无向完 全图包含()条边。A. n (nl) B. n (nl) C. n (nl) /2 D. n (nl) /225. 一个具有n个顶点的有向完全图包含()条边。A. n (nl) B. n (nl) C. n (nl) /2 D. n (nl) /226.对于具有n个顶点的图，假设采用邻接矩阵表示，那么该矩 阵的大小为()。22A. n B. n C. nl D. (nl)27.对于一个具有n个顶点和e条边的无向图，假设采用邻接 表表示，那么表头向量的大小为()。A. n B. e C. 2n D. 2e28.对于一个具有n个顶点和e条边的无向图，假设采用邻接表表示，那么所有顶点邻接表中的结点总数为（）。A. n B. e C. 2n D. 2e29 .在有向图的邻接表中，每个顶点邻接表链接着该顶点所 有（）邻接点。A.入边B.出边C.入边和出边D.不是入边也不是出边30 .在有向图的逆邻接表中，每个顶点邻接表链接着该顶点 所有（）邻接点。A.入边B.出边C.入边和出边D.不是 入边也不是出边31.邻接表是图的一种（）。A.顺序存储结构B.链式存储结构C.索引存储结构D.散 列存储结构32 .如果从无向图的任一顶点出发进行一次深度优先搜索即 可访问所有顶点，那么该图一定是（）。A.完全图B.连通图C.有回路D. 一棵树33.以下有关 图遍历的说法不正确的选项是（）。A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特 征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶 点仅被访问一次34.无向图的邻接矩阵是一个（）。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵35.图 的深度优先遍历算法类似于二叉树的（）遍历。A.先序B.中 序C.后序D.层次36.以下图所示的一个图，假设从顶点VI出发，按深度优先 搜索法进行遍历，那么可能得到的一种顶点序列为（）。A. V1V2V4V8V3V5V6V7 B. V1V2V4V5V8V3V6V7C. V1V2V4V8V5V3V6V7 D. V1V3V6V7V2V4V5V8V IV 2 V3二、填空题V 4 V5 V6 V7 V8 1.结点的度是指结点所拥有的。2.树的度是指。3.度大于0的结点称作或。4.度等 于0的结点称作或。5 .在一棵树中，每个结点的或者说每个结点的称为该结点 的，简称为孩子。6 . 一个结点称为其后继结点的。7 .具有的结点互称为兄弟结点，简称为兄弟。8.每个结 点的所有子树中的结点被称为该结点的。9.从根结点到该结点所经分支上的所有结点称为该结点的。 10.树的深度或高度是指。11. m（niO）棵互不相交的树的集合称为。12.度为k的树中 的第i层上最多有 结点。13.深度为k的二叉树最多有 结点。14 .在一棵二叉树中，如果树中的每一层都是满的，那么称此 树为；但如果出最后一层外，其余层都是满的，并且最后一层 是满的，或者是在缺少假设干连续个结点，那么称此二叉树为。15 .具有n个结点的完全二叉树的深度是。16.先序遍历 二叉树的的操作定义为；假设二叉树为空，那么为空操作，否那么进行 如下操作，访问二叉树的；先序遍历二叉树的，先序遍历二叉 树的。17 .中序遍历二叉树的的操作定义为；假设二叉树为空，那么为 空操作，否那么进行如下操作，中序遍历二叉树的；访问而叉树的，中序遍历二叉树 的。18 .后序遍历二叉树的的操作定义为；假设二叉树为空，那么为 空操作，否那么进行如下操作，后序遍历二叉树的；后序遍历二 叉树的，访问而叉树的。19 .将树中结点赋上一个有着某种意义的实数，称此实数为 该结点的。20.树的带权路径长度为树中所有叶子结点的。21 .哈夫曼树又称为，它是n个带权叶子结点构成的所有二 叉树中带权路径长度WPL。22 .假设以4, 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树, 那么其带权路径长度是。23 .具有m个叶子结点的哈夫曼树共有 结点。24 .在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系。25 .图的邻接矩阵表示法是用一个 来表示图中顶点之间的相 邻关系。26.邻接表是图中的每个顶点建立一个邻接关系的。27 .图的遍历是从图的某一顶点出发，按照一定的搜索方法 对图中各做访问的过程。28 .图的深度优先搜索遍历类似于树的 遍历。29.图的广 度优先搜索类似于树的遍历。30 .具有n个顶点的有向图的邻接矩阵，其元素个数为。30.具有n个顶点的无向图至少有 条边，才能确保其为一个 连通图。31.图常用的两种存储结构是 和。32 . 一个AOV网（顶点活动图）应该是一个。即不应该带有 回路，否那么回路上的所有活动都。33 .用邻接矩阵存储有向图G,其第i行的所有元素之和等 于顶点i的。34.在有n个顶点的有向图中，每个顶点的度最 大可达。35.在一个带权图中，两顶点之间的最段路径最多经 过 条边。36.为了实现图的深度优先搜索遍历，其非递归的算 法中需要使用的一个辅助数据结构