数据结构复习资料

《数据结构复习资料》由会员分享，可在线阅读，更多相关《数据结构复习资料（10页珍藏版）》请在金锄头文库上搜索。

1、1数据结构（本）课程作业数据结构（本）课程作业作业作业 3（本部分作业覆盖教材第（本部分作业覆盖教材第 6-7 章的内容）章的内容） 一、单项选择题一、单项选择题 1.假定一棵二叉树中，双分支结点数为 15，单分支结点数为 30，则叶子结点数为（ ）。 A15 B16 C17 D47 2二叉树第 k 层上最多有（ ）个结点。A2k B2k-1C2k-1 D2k-1 3二叉树的深度为 k,则二叉树最多有（ ）个结点。 A2k B2k-1 C2k-1 D2k-1 4. 设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是 （ ） 。Aabdec Bdebac Cd

2、ebca Dabedc 5树最适合于用来表示（ ） 。 A线性结构的数据 B顺序结构的数据 C元素之间无前驱和后继关系的数据 D元素之间有包含和层次关系的数据 6设 a,b 为一棵二叉树的两个结点，在后续遍历中，a 在 b 前的条件是（ ） 。 Aa 在 b 上方 Ba 在 b 下方 Ca 在 b 左方 Da 在 b 右方 7权值为1，2，6，8的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A18 B28 C19 D29 8将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点的编号为 1，则编号为 69 的结点的双亲结点的编号为（ ）。 A33 B3

3、4 C35 D36 9如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则 该树称为（ ）。 A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树 10下列有关二叉树的说法正确的是（ ）。 A二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1 B二叉树中结点个数必大于 0 C完全二叉树中，任何一个结点的度，或者为 0 或者为 2 D二叉树的度是 2 11在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ ）。 A4 B5 C6 D7 12在一棵度具有 5 层的满二叉树中结点总数为（ ）。2A31 B32 C33

4、 D16 13. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有( )个结点。A. n B. n+1 C. 2*n D. 2*n-114. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有( )个双支结点。A. n B. n-1 C. n+1 D. 2*n-115. 利用 3、6、8、12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有 叶子的最长带权路径长度为( )。A. 18 B. 16 C. 12 D. 30 16在一棵树中，（ ）没有前驱结点。 A分支结点 B叶结点 C树根结点 D空结点17在一棵二叉树中，若编号为 i 的结点存在右孩子，则右孩子的顺序编号为（ ） 。

5、A2i B2i-1 D2i+1 C2i+2 18设一棵哈夫曼树共有 n 个叶结点，则该树有（ ）个非叶结点。An Bn-1 Cn+1 D2n 19设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为 2，则该树共有（ ）个结点。 A2n B2n-1 C2n+1 D2n+2 20一棵完全二叉树共有 5 层，且第 5 层上有六个结点，该树共有（ ）个结点。A20 B21 C23 D30 21在一个图 G 中，所有顶点的度数之和等于所有边数之和的（ ）倍。A1/2 B1 C2 D4 22在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。A邻接矩阵表示法 B邻接表表示法 C逆邻

6、接表表示法 D邻接表和逆邻接表 23在图的存储结构表示中，表示形式唯一的是（ ）。An Bn1 Cn1 Dn/2 24一个具有 n 个顶点的无向完全图包含（ ）条边。An（n1） Bn（n1） C n（n1）/2 D n（n1）/2 25一个具有 n 个顶点的有向完全图包含（ ）条边。An（n1） Bn（n1） C n（n1）/2 D n（n1）/2 26对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。An Bn2 Cn1 D（n1）2 27对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大 小为（ ）。An Be C2n D2e 28对于一个

7、具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接 表中的结点总数为（ ）。An Be C2n D2e 29在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。A入边 B 出边 C入边和出边 D 不是入边也不是出边 30在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。3A入边 B出边 C入边和出边 D不是入边也不是出边 31邻接表是图的一种（ ）。A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构32如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图 一定是（ ）。A完全图 B连通图 C有回路 D一棵树 33下列

8、有关图遍历的说法不正确的是（ ）。 A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C非连通图不能用深度优先搜索法 D图的遍历要求每一顶点仅被访问一次34无向图的邻接矩阵是一个（ ）。A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵 35图的深度优先遍历算法类似于二叉树的（ ）遍历。 A先序 B 中序 C后序 D层次36已知下图所示的一个图，若从顶点 V1出发，按深度优先搜索法进行遍历，则可 能得到的一种顶点序列为（ ） 。AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V6V7 DV1V3V6V7

9、V2V4V5V8二、填空题二、填空题 1结点的度是指结点所拥有的 。 2树的度是指 。 3度大于 0 的结点称作 或 。 4度等于 0 的结点称作 或 。 5在一棵树中，每个结点的 或者说每个结点的 称为 该结点的 ，简称为孩子。 6一个结点称为其后继结点的 。 7具有 的结点互称为兄弟结点，简称为兄弟。 8每个结点的所有子树中的结点被称为该结点的 。V6V7V1V2V3V8V4V549从根结点到该结点所经分支上的所有结点称为该结点的 。 10树的深度或高度是指 。 11m(m0)棵互不相交的树的集合称为 。 12度为 k 的树中的第 i 层上最多有 结点。 13深度为 k 的二叉树最多有 结

10、点。 14在一棵二叉树中，如果树中的每一层都是满的，则称此树为 ； 但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少若干连续个 结点，则称此二叉树为 。 15具有 n 个结点的完全二叉树的深度是 。 16先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操 作，访问二叉树的 ；先序遍历二叉树的 ，先序遍历二叉树的 。1 17中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操 作，中序遍历二叉树的 ；访问而叉树的 ，中序遍历二叉树的 。 18后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操 作，后序遍历二叉树的 ；后序遍历二叉树的 ，访问而叉树的 。 19将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 。 20树的带权路径长度为树中所有叶子结点的 。 21哈夫曼树又称为 ，它是 n 个带权叶子结点构成的所有二叉树中带 权路径长度 WPL 。 22若以 4，5，6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。 23具有 m 个叶子结点的哈夫曼