数据结构练习2-08答案.doc

数据结构练习（二）答案一、填空题：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=2h-1,m=n+1-2h-1 n=2m-1 。3一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。一棵深度为k的完全二叉树中最少有 2k-1（6） 个结点，最多有（7）2k-1 个结点。4具有n个结点的二叉树，当它是一棵 (8)完全 二叉树时具有最小高度 （9）log2n+1 ，当它为一棵单支树时具有高度 (10) n 。5对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)_i/2_，左孩子的编号为_2i_，右孩子的编号为_2i+1_。6若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有_2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，_n+1_个指针域空闲存放着NULL 。7二叉树的遍历方式通常有_先序_、_中序_、_后序_和_层序_四种。8已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为_DCBFGEA_。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层最多有_ki-1_个结点(i=1)，深度为h的k叉树最多有_k0+k1+.+kh-1_个结点。12非空二叉树一共有_4_种基本形态，第i层最多有_ 2i-1_个结点。13在一棵完全二叉树中，编号i和编号j的两个结点处于同一层的条件是_log2i=log2j_14有n个顶点的强连通图至少有 （7）n 弧，有n个顶点的连通图至少有 （8）n-1 边。15设无向图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数据元素之间具有层次关系的数据 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的结点个数为 。A9B11 C15 D不确定6.一个具有1025个结点的二叉树的高h为 。A11B10C111025D1210247若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是_树。A空或仅有一个结点B其分支结点无左子树C其分支结点无右子树D其分支结点的度都为18任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置_A都会发生改变B不会发生改变C有可能会发生改变D部分会发生改变9如图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有_个叶子结点。A4B5C6D710设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_。An在m右方Bn是m祖先Cn在m左方Dn是m子孙11一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是_。ACABDEFG BABCDEFGCDACEFBGDADCFEGB12引入线索二叉树的目的是_。A加快查找结点的前驱或后继结点的速度C为了能方便找到双亲B为了能在二叉树中方便插入和删除D使二叉树的遍历结果唯一13线索二叉树是一种_结构。A逻辑 B逻辑和存储 C物理 D线性14判断线索二叉树中*p结点有右孩子结点的条件是_。Ap！=NULL BPrchild!=NULLCprtag=0 Dprtag=115n个结点的线索二叉树上含有的线索数为_。A2n Bn-1 Cn+1 Dn16根据使用频率为5个字符设计的哈夫曼编码不可能是_。A000，001，010，011，1B0000，0001，001，01，1C000，001，01，10，11D00，100，101，110，11117若度为m的哈夫曼树中，其叶子结点个数为n，则非叶子结点的个数为_。An-1 B (n/m) -1 C（n-1）/(m-1) Dn/(m-1) -1 取消此题18设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_个结点。A13 B12 C26 D2519在一个图中，所有顶点的度数之和等于所有边数的_倍。A.1/2 B.1 C.2 D.420一个具有n个顶点的无向图最多有_条边。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.2n24若一个非连通的无向图最多有28条边，则该无向图至少有_个项点。A.6 B.7 C.8 D.925在带权图中，两个顶点之间的路径长度是_。A路径上的顶点数目 B路径上的边的数目C路径上顶点和边的数目 D路径上所有边上的权值之和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若无向图有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若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个_图。A非连通 B连通 C.强连通 D.完全36可以进行拓扑排序的图一定是_。A连通图 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即使所有非关键活动都未按时完成，整个工程仍有可能按时完成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有一棵或多棵 C一定有多棵 D可能不存在44求最短路径的Dijkstra算法的时间复杂度为 。AO（n） B. O（n+e） CO（n2）DO（n3）45求最短路径的Floyd算法的时间复杂度为 。AO（n） B. O（ne） CO（n2）DO（n3）45-2有向网G用邻接矩阵A存储，则顶点i的入度等于A中 。A)第i行非的元素之和C)第i列非的元素之和B)第i行非且非0的元素个数D)第i列非且非0的元素个数46关键路径是事件结点网中_。A从起点到终点的最长路径B从起点到终点的最短路径C最长的回路D最短的回路47已知一个有向图如右图所示，则从顶点a出发进行深度优先遍历不可能得到的DFS序列为_。A）adbefc B）adcefb C）adcbfeD）adefcb三、判断题 (1)在树型结构中,每一个结点最多只有一个前驱结点,但可以有多个后继结点. (2)在树型结构中，每一个结点不能没有前驱结点。 (3)在度为k的树中，至少有一个度为k的结点。(4)在度为k的树中，每个结点最多有k-1个兄弟结点。(5)度为2的树是二叉树。(6)二叉树的度一定为2。(7)在非空完全二叉树中，只有最下面一层的结点为叶结点。 (8)在完全二叉树中，没有左孩子的结点一定是叶结点。(9)在完全二叉树中，没有右孩子的结点一定是叶结点。 (10)在结点数目一定的前提下,各种形态的二叉树中,完全二叉树具有最小深度。 (11)满二叉树一定是完全二叉树。 (12)满二叉树中的每个结点的度不是0就是2。 (13)在所有深度相同的二叉树中，满二叉树具有最大结点数目。 (14)具有n个结点的非空二叉树一定有n-1个分支。(15)n个结点的二叉树采用二叉链表结构,链表中有n-1个存放NULL指针域。 (16)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。 (17)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。 (18)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。 (19)实现二叉树的按层次遍历算法时需要用到队列结构。(20)实现二叉树的遍历算法时不需要用到堆栈结构。 (21)线索二叉树对应的二叉链表中不存在空的指针域。(22)给定一组权值，构造出来的哈夫曼树是惟一的。 (23)哈夫曼树中不存在度为1的结点。(24)在哈夫曼树中，权值相同的叶结点都在同一层上。(25)没有顶点的图称为空图。 (26)图的度是图中所有顶点的度的最大值。 (27)边上带权值的图称为网(络)。 (28)图中一个顶点的度应该是它的出度与人度之和。 (29)n个顶点的无向图最多有n(n-1)条边。 (30)在有向图中，所有顶点的人度之和等于所有顶点的出度之和。 (31)在无向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (32)在有向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (33)连通图的最小生成树是惟一的。 (34)邻接矩阵主要用来表示顶点之间的关系。 (35)若表示某图的邻接矩阵不是对称矩阵，则该图一定是有向图。 (36)若表示某图的邻接矩阵中出现了全零行或者全零列，则该图一定是非连通图或者非强连通图。 (37)对于同一个有向图，邻接表中的边结点数目与逆邻接表中边结点数目相等。 (38)无向图的邻接表中边结点数目一定为偶数。 (39)邻接表中边结点数目为奇数的图一定是有向图。 (40)邻接表中边结点数目为偶数的图一定是无向图。 (41)对图进行广度优先搜索的过程中要用到队列。 (42)对图进行深度优先搜索的过程中要用到堆找。 (43)带权连通图的最小生成树是惟一的。 (44)最短路径一定是简单路径。 (45)求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向网络。 (46)若AOV网中存在拓扑序列，则一般情况下，拓扑序列不是惟一的。 (47)关键路径是由权值最大的边构成的。 (48)给定的AOE网的关键路径一定是惟一的。四、简答题：1已知森林的先序遍历序列为ABDJCEFHK，中序序列为DJBAECHKF，请画出该森林。2若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？ 14 253一棵度为2的树与一棵二叉树有什么区别?将树转化为二叉树的基本目的是什么？ 可以采用二叉树的结构并利用已有的算法解决树的有关问题。4已知一棵完全二叉树共有892个结点，试求：（1）树的高度 10（2）叶子结点数 446（3）单支结点数 1（4）最后一个非终端结点的序号 4465画出二叉树的后序前驱线索。6一文件中只出现9种字符：a、b、c、d、e、f、g、h，它们出现的频率分别为8、9、3、5、6、4、2、1，请根据书上算法画出相应的哈夫曼树(叶子结点用相应字母表示,左子树的权小于右子树的权)，给出哈夫曼编码，并计算其带权的路径长度WPL。7已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表结构的表示。8.已知按前序遍历二叉树的结果为ABC。试问，有几种不同的二叉树可以得到这一遍历结果? 59.将图所示的树林转换为一棵二叉树。10.分别写出如