《数据结构练习2-08答案》由会员分享，可在线阅读，更多相关《数据结构练习2-08答案（9页珍藏版）》请在金锄头文库上搜索。
1、1数据结构练习（二）答案一、填空题：1若一棵树的括号表示为 A（B（E，F） ，C（G（H,I,J,K ）,L）,D（M （N） ） ，则该树的度为 （1）4 ，树的深度为 （2）4 ，树中叶子结点的个数为（3）8。2一棵满二叉树中有 m 个叶子，n 个结点，深度为 h，请写出 m、n、h 之间关系的表达式 （4）n=2 h-1,m=n+1-2h-1 n=2m-1 。3一棵二叉树中如果有 n 个叶子结点，则这棵树上最少有（5）2n-1 个结点。一棵深度为 k 的完全二叉树中最少有 2k-1（6） 个结点，最多有（7）2 k-1 个结点。4具有 n 个结点的二叉树，当它是一棵 (8)完全 二叉树
2、时具有最小高度 （9）log 2n+1 ，当它为一棵单支树时具有高度 (10) n 。5对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)_i/2_，左孩子的编号为_2i_，右孩子的编号为_2i+1_。6若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有_2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，_n+1_个指针域空闲存放着NULL 。7二叉树的遍历方式通常有_先序_、_中序_、_后序_和_层序_四种。8已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为_DC
3、BFGEA_。9已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为_HIDJEBFGCA_。10若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有_n0-1_个度为2的结点，_n-2n0+1_个度为1的结点。11任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的_根_。度为k的树中第i层最多有_k i-1_个结点(i=1)，深度为h的k叉树最多有_k 0+k1+.+kh-1_个结点。12非空二叉树一共有_4_种基本形态，第i层最多有_ 2 i-1_个结点。13在一棵完全二叉树中，编号 i 和编号 j 的两个结点处于同一层
4、的条件是_log2i=log2j_14有 n 个顶点的强连通图至少有 （7）n 弧，有 n 个顶点的连通图至少有 （8）n-1 边。215设无向图 G 的顶点数为 n，图 G 最少有 (12) 0 边，最多有 (13) n(n-1)/2 条边；若边数为 e，用邻接矩阵表示图，求每一顶点度的时间复杂性为 (14) O(n2) ；若用邻接表表示图，访问一个顶点的所有邻接顶点的时间复杂性为 (15) O(n) 。一个有 n 个顶点的有向图中，最少有 (16)0 弧，最多有 (17) n(n-1) 弧。二、选择题1.树型结构最适合用来描述_A有序的数据元素 B无序的数据元素C数据元素之间具有层次关系的
5、数据 D数据元素之间没有关系的数据2.对于一棵具有n个结点、度为4的树而言，_。A树的深度最多是n-4 B树的深度最多是n-3C第i层上最多有4(i-1)个结点 D最少在某一层上正好有4个结点3.”二叉树为空”意味着二叉树_A由一些未赋值的空结点组成 B根结点无子树C不存在 D没有结点4.按照二叉树的定义，具有3个结点的二叉树有_种形态(不考虑数据信息的组合情况)。A.2 B.3 C.4 D.55若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数为 。A9 B11 C15 D不确定6.一个具有 1025 个结点的二叉树的高 h 为 。A11 B10 C1
6、1 1025 D1210247若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是_树。A空或仅有一个结点 B其分支结点无左子树C其分支结点无右子树 D其分支结点的度都为18任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置_A都会发生改变 B不会发生改变C有可能会发生改变 D部分会发生改变9如图所示的二叉树 T2 是由森林 T1 转换而来的二叉树，那么森林 T1 有_个叶子结点。A4 B5 C6 D710设 n，m 为一棵二叉树上的两个结点，在中AB ECDF HG JI3序遍历时，n 在 m 前的条件是_。An 在 m 右方 Bn 是 m 祖先Cn 在 m 左方
7、 Dn 是 m 子孙11一棵二叉树的先序遍历序列为 ABCDEFG，它的中序遍历序列可能是_。ACABDEFG BABCDEFG CDACEFBG DADCFEGB12引入线索二叉树的目的是_。A加快查找结点的前驱或后继结点的速度 C为了能方便找到双亲B为了能在二叉树中方便插入和删除 D使二叉树的遍历结果唯一13线索二叉树是一种_结构。A逻辑 B逻辑和存储 C物理 D线性14判断线索二叉树中*p 结点有右孩子结点的条件是_。Ap！=NULL BPrchild!=NULLCp rtag=0 Dprtag=115n 个结点的线索二叉树上含有的线索数为_。A2n Bn-1 Cn+1 Dn16根据使用
8、频率为 5 个字符设计的哈夫曼编码不可能是_。A000，001，010，011，1 B0000，0001，001，01，1C000 ，001，01，10，11 D00，100， 101，110，11117若度为 m 的哈夫曼树中，其叶子结点个数为 n，则非叶子结点的个数为_。An-1 B (n/m) -1 C （n-1）/(m-1) D n/(m-1) -1 取消此题18设有 13 个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_个结点。A13 B12 C26 D2519在一个图中，所有顶点的度数之和等于所有边数的_倍。A.1/2 B.1 C.2 D.420一个具有n个顶点的无向图最多有_条边
9、。A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n221一个具有n个顶点的有向图最多有_条边。A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n222在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边A.n B.n+1 C.n-1 D.2n23具有n个顶点的连通图的生成树一定有_条边。A.n B.n+1 C.n-1 D.2n424若一个非连通的无向图最多有28条边，则该无向图至少有_个项点。A.6 B.7 C.8 D.925在带权图中，两个顶点之间的路径长度是_。A路径上的顶点数目 B路径上的边的数目C路径上顶点和边的数目 D路径上所有边上的权值之
10、和26若具有n个顶点的元向图采用邻接矩阵存储方法,该邻接矩阵一定为一个_。A一般矩阵 B对称矩阵 C对角矩阵 D稀疏矩阵27若图的邻接矩阵中主对角线上的元素均为0，其余元素全为1，则可以断定该图一定_。A是无向图 B是有向图 C是完全图 D不是带权图28有向图的邻接表的第i个链表中的边结点数目是第i个顶点的_。A度数 B出度 C人数 D边数29若某图的邻接表中的边结点数目为奇数，则该图_。A一定有奇数个顶点 B一定有偶数个顶点C一定是有向图 D可能是无向图30若某图的邻接表中的边结点数目为偶数，则该图_。A一定是无向图 B可能是有向图C可能是无向图，也可能是有向图 D一定有偶数个顶点31若无向
11、图有k条边，则相应的邻接表中就有_个边结点。A.k-1 B.k C.2k D.k232若有向图有k条边，则相应的邻接表中就有_个边结点。A.k-1 B.k C.2k D.k233对于一个不带权的无向图的邻接矩阵而言，_A矩阵中非零元素的数目等于图中边的数目B矩阵中非全零的行的数目等于图中顶点的数目C第i行的非零元素的数目与第i列的非零元素的数目相等D第i行与第i列的非零元素的总数等于第i个顶点的度数34导致图的遍历序列不惟一的因素有_。A出发点不同、遍历方法不同 B出发点不同、存储结构不同C遍历方法不同、存储结构不同D出发点不同、存储结构不同、遍历方法不同35若从无向图的任意一个顶点出发进行一
12、次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个_图。A非连通 B连通 C .强连通 D.完全36可以进行拓扑排序的图一定是_。5A连通图 B带权连通图 C无回路的图 D无回路的有向图37已知某有向图G=(V,E)，其中V=v1,v2,v3,v4,v5,v6, E=, ,，,G的拓扑序列是_。A. v3,v1,v4,v5,v2,v6 Bv3,v4,v1,v5,v2,v6C. v1,v3,v4,v5,v2,v6 D. v1,v4,v3,v5,v2,v638下面关于AOE网的叙述中，不正确的是_。A若所有关键活动都提前完成，则整个工程一定能够提前完成B即使所有非关键活动都未按时完成，整个工
13、程仍有可能按时完成C任何一个关键活动的延期完成，都会导致整个工程的延期完成 D任何一个关键活动的提前完成，都会导致整个工程的提前完成39无向图的邻接矩阵是一个_.A对称矩阵 B零矩阵 C上三角矩阵 D对角矩阵40如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。A完全图 B连通图 C有回路 D一棵树41采用邻接表存储的图的深度优先遍历算法类似于二叉树的_算法。A先序遍历 B中序遍历 C后序遍历 D按层遍历42一个无向连通图的生成树是含有该连通图的全部顶点的 A极小联通子图 B.极小子图 C极大连通子图 D极大子图43任何一个无向连通图 最小生成树。A只有一棵 B有
14、一棵或多棵 C一定有多棵 D可能不存在44求最短路径的 Dijkstra 算法的时间复杂度为 。AO（n） B. O（n+e ） CO（n 2） D O（n 3）45求最短路径的 Floyd 算法的时间复杂度为 。AO（n） B. O（ne） CO（n 2） DO （n 3）45-2 有向网 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中 。A)第 i 行非 的元素之和 C)第 i 列非的元素之和B)第 i 行非且非 0 的元素个数 D)第 i 列非 且非 0 的元素个数46关键路径是事件结点网中_。A从起点到终点的最长路径 B从起点到终点的最短路径C最长的回路 D最短的回路47已知一个有向图如右图所示，则从顶点 a 出发进行深度优先遍历不可能得到的 DFS 序列为
