数据结构练习2-09答案

数据结构练习2-09答案数据结构练习2-09答案数据结构练习2-09答案数据结构练习2-09答案编制仅供参考审核批准生效日期地址：电话：传真:邮编:数据结构练习（二）答案一、填空题：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-1n=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-4B．树的深度最多是n-3C．第i层上最多有4×(i-1)个结点3.”二叉树为空”意味着二叉树______A．由一些未赋值的空结点组成 B．根结点无子树C．不存在 D．没有结点4.按照二叉树的定义，具有3个结点的二叉树有___种形态(不考虑数据信息的组合情况)。 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为。A．9 B．11 C．15 D．不确定6.一个具有1025个结点的二叉树的高h为。A．11 B．10 C．11—1025 D．12—10247．若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是___树。A．空或仅有一个结点 B．其分支结点无左子树C．其分支结点无右子树 D．其分支结点的度都为18．任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置__A．都会发生改变 B．不会发生改变C．有可能会发生改变 D．部分会发生改变9．如图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有_____个叶子结点。A．4 B．5 C．6 D．710．设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_____。A．n在m右方 B．n是m祖先C．n在m左方 D．n是m子孙11．一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是_____。A．CABDEFGB．ABCDEFG C．DACEFBG D．ADCFEGB12．引入线索二叉树的目的是_____。A．加快查找结点的前驱或后继结点的速度 C．为了能方便找到双亲B．为了能在二叉树中方便插入和删除 D．使二叉树的遍历结果唯一13．线索二叉树是一种_____结构。A．逻辑 B．逻辑和存储 C．物理 D．线性14．判断线索二叉树中*p结点有右孩子结点的条件是_____。A．p！=NULL B．P—>rchild!=NULLC．p—>rtag=0 D．p—>rtag=115．n个结点的线索二叉树上含有的线索数为_____。A．2n B．n-1 C．n+1 D．n16．根据使用频率为5个字符设计的哈夫曼编码不可能是_____。A．000，001，010，011，1 B．0000，0001，001，01，1C．000，001，01，10，11 D．00，100，101，110，11118．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_____个结点。A．13 B．12 C．26 D．2519．在一个图中，所有顶点的度数之和等于所有边数的____倍。2 20．一个具有n个顶点的无向图最多有______条边。(n-1)/2 (n-1) (n+1)/221．一个具有n个顶点的有向图最多有_________条边。(n-1)/2(n-1) (n+1)/222．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边 +1 23．具有n个顶点的连通图的生成树一定有________条边。 +1 24．若一个非连通的无向图最多有28条边，则该无向图至少有__个项点。 25．在带权图中，两个顶点之间的路径长度是______。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条边，则相应的邻接表中就有_______个边结点。 32．若有向图有k条边，则相应的邻接表中就有_____个边结点。 33．对于一个不带权的无向图的邻接矩阵而言，_________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={<v1,v2>,<v1,v4>,<v2,v6>，<v3,v1>,<v3,v4>,<v4,v5>,<v5,v2><v5,v6>},G的拓扑序列是_________。A.v3,v1,v4,v5,v2,v6 B．v3,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算法的时间复杂度为。A．O（n） B.O（n+e） C．O（n2） D． O（n3）45．求最短路径的Floyd算法的时间复杂度为。A．O（n） B.O（ne） C．O（n2） D．O（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）adcbfe D）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，则该树叶子结点的个数是多少总结点个数是多少14253．一棵度为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，请根据书上算法画出相应的哈夫曼树(叶子结点用相应字母表示,左子树的权小于右子树的权)，给出哈