数据结构练习2

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之间hh-1关系的表达式(4) n=2 -1,m=n+1-2n=2m-1 。3. 棵二叉树中如果有n个叶子结点，则这棵树上最少有(5) 2n-1个结点。k-1k一棵深度为k的完全二叉树中最少有_2 (6)个结点，最多有(7)2-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个叶结点，则该二叉树有_n°-1_个度为2的结点，n-2n°+1个度为1的结点。11. 任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的根。度为k的树中第i层最多有 ki-1 结点(i>=1)，深度为h的k叉树最多有k°+k+.+k h 1个结点。12. 非空二叉树一共有_4种基本形态，第i层最多有_ 2i-1个结点。13. 在一棵完全二叉树中，编号

4、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)0(n2);若用邻接表表示图，访问一个顶点的所有邻接顶点的时间复杂性为 (15) 0(n)。一个有n个顶点的有向图中，最少有 (16)0 弧，最多有 (17) n(n-1)弧。二、选择题1. 树型结构最适合用来描述A. 有序的数据元素B.无序的数据元素C数据元素之间具有层次

5、关系的数据D.数据元素之间没有关系的数据2. 对于一棵具有n个结点、度为4的树而言，。A. 树的深度最多是n-4B.树的深度最多是n-3C.第i层上最多有4 x (i-1)个结点3. ”二叉树为空”意味着二叉树 A.由一些未赋值的空结点组成B.根结点无子树c.不存在D，没有结点4. 按照二叉树的定义，具有3个结点的二叉树有_种形态(不考虑数据信息的 组合情况)。A.2B.3C.4D.55. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结 点个数为。A . 9B. 11C. 15D .不确定6. 一个具有1025个结点的二叉树的高h为。A. 11B. 10C . 111025

6、D . 1210247. 若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是 _树。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

7、. n是m子11 . 一棵二叉树的先序遍历序列为 ABCDEFG，它的中序遍历序列可能是 。A. CABDEFG囘.ABCDEFG C. DACEFBG D. ADCFEGB12. 引入线索二叉树的目的是 。A .加快查找结点的前驱或后继结点的速度C.为了能方便找到双亲B. 为了能在二叉树中方便插入和删除D .使二叉树的遍历结果唯一13. 线索二叉树是一种 吉构。A .逻辑B .逻辑和存储C .物理D .线性14 .判断线索二叉树中*p结点有右孩子结点的条件是 。A . p! =NULLB . P >rchild!=NULLC . p>rtag=0D . p>rtag=115

8、. n个结点的线索二叉树上含有的线索数为 。A . 2nB . n-1C . n+1D . n16 .根据使用频率为5个字符设计的哈夫曼编码不可能是 oA. 000, 001, 010, 011, 1C. 000, 001, 01, 10, 11B. 0000, 0001, 001, 01, 1D. 00, 100, 101, 110, 111个结点18 .设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 A . 13B . 12C . 26D . 2519 .在一个图中，所有顶点的度数之和等于所有边数的 倍D.4A.1/2B.1C.220 . 一个具有n个顶点的无向图最多有 边。A.n

9、(n-1)/2B. n(n-1)C. n(n+1)/2D.n21 . 一个具有n个顶点的有向图最多有 边。A.n(n-1)/2血 n(n-1)C.n(n+1)/2 D.n22 .在一个具有n个顶点的无向图中，要连通全部顶点至少需要 边A.nB.n+1C.n-1D.2 n23 .具有n个顶点的连通图的生成树一定有 边。A.nB.n+1C.n-1D.2 n24 .若一个非连通的无向图最多有28条边，则该无向图至少有 个项点A.6B.7C.8D.925 .在带权图中，两个顶点之间的路径长度是 oA.路径上的顶点数目B.路径上的边的数目C路径上顶点和边的数目D .路径上所有边上的权值之和26 .若具有

10、n个顶点的元向图采用邻接矩阵存储方法，该邻接矩阵一定为一个OA. 一般矩阵B .对称矩阵C.对角矩阵D.稀疏矩阵27 .若图的邻接矩阵中主对角线上的元素均为 0,其余元素全为1,则可以断定该图一定_oA.是无向图 B .是有向图C.是完全图D.不是带权图28. 有向图的邻接表的第i个链表中的边结点数目是第i个顶点的_A.度数B.出度C.人数D.边数29. 若某图的邻接表中的边结点数目为奇数，贝U该图 oA. 定有奇数个顶点B. 定有偶数个顶点C 一定是有向图D.可能是无向图30. 若某图的邻接表中的边结点数目为偶数，则该图 oA.定是无向图B.可能是有向图C可能是无向图，也可能是有向图D. 定

11、有偶数个顶点31. 若无向图有k条边，则相应的邻接表中就有 边结点。A.k-1B.kC.2kD.k232. 若有向图有k条边，则相应的邻接表中就有 边结点。A.k-1B.kC.2kD.k233. 对于一个不带权的无向图的邻接矩阵而言， A.矩阵中非零元素的数目等于图中边的数目矩阵中非全零的行的数目等于图中顶点的数目第i行的非零元素的数目与第i列的非零元素的数目相等第i行与第i列的非零元素的总数等于第i个顶点的度数导致图的遍历序列不惟一的因素有 。出发点不同、遍历方法不同B.出发点不同、存储结构不同遍历方法不同、存储结构不同D.出发点不同、存储结构不同、遍历方法不同35. 若从无向图的任意一个顶

12、点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个 0A.非连通B.连通C .强连通D.完全36. 可以进行拓扑排序的图一定是 oA.连通图 B .带权连通图C.无回路的图 D.无回路的有向图37. 已知某有向图 G=(V,E)，其中 V=v1,v2,v3,v4,v5,v6, E=<v1,v2>,<v1,v4>,<v2,v6> , <v3,v1>,vv3,v4>,vv4,v5>,vv5,v2>vv5,v6>,G的拓扑序歹寸是oA. v3,v1,v4,v5,v2,v6B. v3,v4,v1,v5,v2,v6

13、C. v1,v3,v4,v5,v2,v6D. v1,v4,v3,v5,v2,v638. 下面关于AO网的叙述中，不正确的是 oA. 若所有关键活动都提前完成，则整个工程一定能够提前完成B. 即使所有非关键活动都未按时完成，整个工程仍有可能按时完成C. 任何一个关键活动的延期完成，都会导致整个工程的延期完成 D任何一个关键活动的提前完成，都会导致整个工程的提前完成39. 无向图的邻接矩阵是一个 .A .对称矩阵B .零矩阵C. 上三角矩阵D .对角矩阵40 .如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是。A .完全图B.连通图C.有回路D .一棵树41 .采用邻接

14、表存储的图的深度优先遍历算法类似于二叉树的 法。A .先序遍历B .中序遍历C.后序遍历D .按层遍历42. 一个无向连通图的生成树是含有该连通图的全部顶点的 A .极小联通子图B.极小子图C.极通子图 D.极大子图43. 任何一个无向连通图 最小生成树。A .只有一棵旦.有一棵或多棵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存

15、储，则顶点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的结点。(

16、4) 在度为k的树中，每个结点最多有k-1个兄弟结点。(5) 度为2的树是二叉树。(6) 二叉树的度一定为2。(7) 在非空完全二叉树中，只有最下面一层的结点为叶结点(8) 在完全二叉树中，没有左孩子的结点一定是叶结点。(9) 在完全二叉树中，没有右孩子的结点一定是叶结点。(10) 在结点数目一定的前提下 , 各种形态的二叉树中 , 完全二叉树具有最小 深度。(11) 满二叉树一定是完全二叉树。(12) 满二叉树中的每个结点的度不是 0就是 2。(13) 在所有深度相同的二叉树中，满二叉树具有最大结点数目。(14) 具有n个结点的非空二叉树一定有n-1个分支。(15) n个结点的二叉树采用二叉

17、链表结构,链表中有n-1个存放NUL指针域(16) 由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。(17) 由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。(18) 由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。(19) 实现二叉树的按层次遍历算法时需要用到队列结构。(20) 实现二叉树的遍历算法时不需要用到堆栈结构。(21) 线索二叉树对应的二叉链表中不存在空的指针域。(22) 给定一组权值，构造出来的哈夫曼树是惟一的。(23) 哈夫曼树中不存在度为 1的结点。(24) 在哈夫曼树中，权值相同的叶结点都在同一层上。(25) 没有顶点的图称为空图。(26) 图的度是图中所

18、有顶点的度的最大值。(27) 边上带权值的图称为网 (络)。(28) 图中一个顶点的度应该是它的出度与人度之和。(29) n 个顶点的无向图最多有 n(n-1) 条边。(30) 在有向图中，所有顶点的人度之和等于所有顶点的出度之和。(31) 在无向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。(32) 在有向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。(33) 连通图的最小生成树是惟一的。(34) 邻接矩阵主要用来表示顶点之间的关系。(35) 若表示某图的邻接矩阵不是对称矩阵，则该图一定是有向图。(36) 若表示某图的邻接矩阵中出现了全零行或者全零列，则该图一定是非 连通

19、图或者非强连通图。(37) 对于同一个有向图，邻接表中的边结点数目与逆邻接表中边结点数目 相等。(38) 无向图的邻接表中边结点数目一定为偶数。(39) 邻接表中边结点数目为奇数的图一定是有向图。(40) 邻接表中边结点数目为偶数的图一定是无向图。(41) 对图进行广度优先搜索的过程中要用到队列。(42) 对图进行深度优先搜索的过程中要用到堆找。(43) 带权连通图的最小生成树是惟一的。(44) 最短路径一定是简单路径。(45) 求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向 网络。(46) 若AON网中存在拓扑序列，则一般情况下，拓扑序列不是惟一的。(47) 关键路径是由权值最

20、大的边构成的。(48) 给定的AO网的关键路径一定是惟一的。四、简答题：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,请根据书上算法画出相应的哈夫曼树(叶子 结点用相应字母表示，左子树的权小于右子树的权)，给出哈夫曼编码，并计 算其带权的路径长度WPL7. 已知某二叉树的中序遍历序列为 CBGEAFHD后序遍历序列为CGEBHFDA青 画出该二叉树的前序线索二叉树的二叉链表结构的表示。8. 已知按前序遍历二叉树的结果为 ABC试问，有几种不同的二叉树可以得