数据结构复习资料.pdf

《数据结构复习资料.pdf》由会员分享，可在线阅读，更多相关《数据结构复习资料.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构本课程作业数据结构本课程作业作业作业 3 3本局部作业覆盖教材第本局部作业覆盖教材第6-76-7 章的内容章的内容一、单项选择题一、单项选择题1.假定一棵二叉树中，双分支结点数为 15，单分支结点数为 30，那么叶子结点数为。A15 B16 C17 D472二叉树第 k 层上最多有个结点。k-1 A2k B2k-1 C2-1 D2k3二叉树的深度为 k,那么二叉树最多有个结点。A2k B2k-1k-1kC2 D2-14.设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，那么该二叉树后序遍历的顺序是。Aabdec Bdebac Cdebca Dabedc5树最适合于用来表示。A

2、线性结构的数据B顺序结构的数据C元素之间无前驱和后继关系的数据D元素之间有包含和层次关系的数据6设 a,b 为一棵二叉树的两个结点，在后续遍历中，a 在 b 前的条件是。Aa 在 b 上方 Ba 在 b 下方 Ca 在 b 左方 Da 在 b 右方7权值为1，2，6，8的四个结点构成的哈夫曼树的带权路径长度是。A18 B28 C19 D298将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为 1，那么编号为 69 的结点的双亲结点的编号为。A33 B34 C35 D369如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，那么该

3、树称为。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树10以下有关二叉树的说法正确的选项是。A二叉树中度为 0 的结点的个数等于度为2 的结点的个数加 1B二叉树中结点个数必大于0C完全二叉树中，任何一个结点的度，或者为0 或者为 2D二叉树的度是 211在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，那么度为0 的结点个数为。A4 B5 C6 D712在一棵度具有 5 层的满二叉树中结点总数为。A31 B32 C33 D1613.利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有()个结点。A.n B.n+1 C.2*n D.2*n-1 14.利用 n 个

4、值作为叶结点的权生成的哈夫曼树中共包含有()个双支结点。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 的结点存在右孩子，那么右孩子的顺序编号为。A2i B2i-1 D2i+1 C2i+218设一棵哈夫曼树共有n 个叶结点，那么该树有个非叶结点。An Bn-1 Cn+1 D2n19设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为

5、 2，那么该树共有个结点。A2n B2n-1 C2n+1 D2n+220一棵完全二叉树共有5 层，且第 5 层上有六个结点，该树共有个结点。A20 B21 C23 D3021在一个图 G 中，所有顶点的度数之和等于所有边数之和的倍。A1/2 B1 C2 D422在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A邻接矩阵表示法 B邻接表表示法C逆邻接表表示法 D邻接表和逆邻接表23在图的存储结构表示中，表示形式唯一的是。An Bn1 Cn1 Dn/224一个具有 n 个顶点的无向完全图包含条边。Ann1 Bnn1 C nn1/2 D nn1/225一个具有 n 个顶点的有向完全图包

6、含条边。Ann1 Bnn1 C nn1/2 D nn1/226对于具有n 个顶点的图，假设采用邻接矩阵表示，那么该矩阵的大小为。22 An Bn Cn1 Dn127对于一个具有 n 个顶点和 e 条边的无向图，假设采用邻接表表示，那么表头向量的大小为。An Be C2n D2e28对于一个具有 n 个顶点和 e 条边的无向图，假设采用邻接表表示，那么所有顶点邻接表中的结点总数为。An Be C2n D2e29在有向图的邻接表中，每个顶点邻接表链接着该顶点所有邻接点。A入边 B出边C入边和出边 D不是入边也不是出边30在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有邻接点。A入边 B出边C入

7、边和出边 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以下图所示的一

8、个图，假设从顶点V1出发，按深度优先搜索法进行遍历，那么可能得到的一种顶点序列为。AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8V1V2V3二、填空题二、填空题V4V5V6V7V81结点的度是指结点所拥有的。2树的度是指。3度大于 0 的结点称作或。4度等于 0 的结点称作或。5在一棵树中，每个结点的或者说每个结点的称为该结点的，简称为孩子。6一个结点称为其后继结点的。7具有的结点互称为兄弟结点，简称为兄弟。8每个结点的所有子树中的结点被称为该结点的。9从根结点到该结点所经分支上的所有结点称为该结点的

9、。10树的深度或高度是指。11m(m 0)棵互不相交的树的集合称为。12度为 k 的树中的第 i 层上最多有结点。13深度为 k 的二叉树最多有结点。14在一棵二叉树中，如果树中的每一层都是满的，那么称此树为；但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少假设干连续个结点，那么称此二叉树为。15具有 n 个结点的完全二叉树的深度是。16先序遍历二叉树的的操作定义为；假设二叉树为空，那么为空操作，否那么进行如下操作，访问二叉树的；先序遍历二叉树的，先序遍历二叉树的。17中序遍历二叉树的的操作定义为；假设二叉树为空，那么为空操作，否那么进行如下操作，中序遍历二叉树的；访问而叉

10、树的，中序遍历二叉树的。18后序遍历二叉树的的操作定义为；假设二叉树为空，那么为空操作，否那么进行如下操作，后序遍历二叉树的；后序遍历二叉树的，访问而叉树的。19将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。20树的带权路径长度为树中所有叶子结点的。21哈夫曼树又称为，它是 n 个带权叶子结点构成的所有二叉树中带权路径长度 WPL。22假设以 4，5，6，7，8 作为叶子结点的权值构造哈夫曼树，那么其带权路径长度是。23具有 m 个叶子结点的哈夫曼树共有结点。24在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系。25图的邻接矩阵表示法是用一个来表示图中顶

11、点之间的相邻关系。26邻接表是图中的每个顶点建立一个邻接关系的。27图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中各做访问的过程。28图的深度优先搜索遍历类似于树的遍历。29图的广度优先搜索类似于树的遍历。30具有 n 个顶点的有向图的邻接矩阵，其元素个数为。30具有 n 个顶点的无向图至少有条边，才能确保其为一个连通图。31图常用的两种存储结构是和。32一个 AOV 网顶点活动图应该是一个。即不应该带有回路，否那么回路上的所有活动都。33用邻接矩阵存储有向图G，其第 i 行的所有元素之和等于顶点i 的。34在有 n 个顶点的有向图中，每个顶点的度最大可达。35在一个带权图中，两顶点之

12、间的最段路径最多经过条边。36 为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。三、综合题三、综合题1写出如以下图所示的二叉树的先序、中序和后序遍历序列。fdgbieachj2某二叉树的先序遍历结果是：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 个结点，求 树的高度 叶子结点数 单支结点数 最后一个非终端结点的序号4给出满足以下条件的所有二叉树。1先序和中序相同2中序和后序相同3先序和后序相同5假设通信用

13、的报文由 9 个字母 A、B、C、D、E、F、G、H 和 I 组成，它们出现的频率分别是：10、20、5、15、8、2、3、7 和 30。请请用这9 个字母出现的频率作为权值求：1设计一棵哈夫曼树；2计算其带权路径长度WPL；3写出每个字符的哈夫曼编码。6请根据以下带权有向图G1给出从结点 v1 出发分别按深度优先搜索遍历G 和广度优先搜索遍历 G 所得的结点序列；2给出 G 的一个拓扑序列；3给出从结点 v1 到结点 v8 的最短路径。7无向图 G 描述如下：G=V，EV=V1，V2，V3，V4，V5E=V1，V2，V1，V4，V2，V4，V3，V4，V2，V5，V3，V4，V3，V51画出

14、 G 的图示；2然后给出 G 的邻接矩阵和邻接表；3写出每个顶点的度。8答复以下问题：对于存储结构采用邻接矩阵的无向图，如何判断以下有关问题？图中有多少条边？任意两顶点间是否有边相连？任意一个顶点的度是多少？对于存储结构采用邻接表的有向图，如何判断以下有关问题？图中有多少条边？图中是否存在从 Vi到 Vj的边？如何求顶点 Vi的入度和出度？四、程序填空题四、程序填空题1.下面函数的功能是返回二叉树BT 中值为 X 的结点所在的层号，请在划有横线的地方填写适宜内容。int NodeLevel(struct BinTreeNode*BT,char X)if(BT=NULL)return 0;/*空

15、树的层号为 0*/else if(BT-data=X)return 1;/*根结点的层号为 1*/*向子树中查找 X 结点*/else int c1=NodeLevel(BT-left,X);if(c1=1)_(1)_;int c2=_(2)_ _;if _(3)_;/假设树中不存在 X 结点那么返回 0 else return 0;2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写适宜内容。void dfstree(adjmatrix GA,int i,int n)int j;visitedi=1;(1)if(GAij!=0&GAij!

16、=MaxValue&!visitedj)printf(%d,%d)%d,i,j,GAij);(2)五、算法设计题五、算法设计题1写一个将一棵二叉树复制给另一棵二叉树的算法。2根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数 BT 初始指向二叉树的根结点。int BTreeLeafCount(struct BTreeNode*BT);3有 n 个顶点的有向图邻接表，设计算法分别实现以下功能：1求出图 G 中每个顶点的出度、入度。2计算图中度为 0 的顶点数。六、完成：实验六、完成：实验 3 3栈、队列、递归程序设计栈、队列、递归程序设计实验实验 4 4图的存储方式和应用图的存储方式和应用根据实验要求见教材P203认真完本钱实验，并提交实验报告。