第六章树和二叉树简答题1、有一棵树的括号表示为A(B,C(E,F(G)),D),回答下面的问题：这棵树的根结点是谁？这棵树的叶子结点是什么？结点C的度是多少？这棵树的度是多少？这棵树的深度是多少？结点C的孩子结点是哪些？结点C的双亲结点是谁？2、若一棵度为4的树中度为1,2,3,4的结点个数分别是4,3,2,2，则该树中叶子结点的个数是多少？总结点个数是多少？3、一棵高度为h的完全k次数，如果按照层次自上向下、自左向右的顺序从1开始对全部结点编号，试问：最多有多少个结点？最少有多少个结点？编号为q的结点的第i个孩子结点的编号是多少？4、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为结点的总个数为5、一棵完全二叉树有1001个结点，其中叶子结点的个数为6、一棵高度为h的完全二叉树至少有个结点。7、一棵高度为5的完全二叉树至多有个结点。8、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树至少包含个结点。9、一个具有1025个结点的二叉树的高度h为10、在一棵完全二叉树中，结点个数为n，则编号最大的分支结点的编号为11、一棵二叉树的先序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为12、一棵二叉树的先序遍历为ABCDEFG，它的中序遍历可能为A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB思考：二叉树的先序和中序遍历相同的条件是？二叉树的后序和中序遍历相同的条件是？13、一棵二叉树的后序遍历为DABEC，中序遍历为DEBAC，则先序遍历为14、一棵二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根结点的右孩子为16、根据使用频率为5个字符设计的赫夫曼编码不可能的是A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,1017、根据使用频率为5个字符设计的赫夫曼编码不可能的是A.000,001,010,011,1B.0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110,11118、设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有个结点。19、若以{4,5,6,7,8}作为叶子结点的权值构造赫夫曼树，则其带权路径长度是，各结点对应的赫夫曼编码为20、以数据集{2,5,7,9,13}为权值构造一棵赫夫曼树，并计算其带权路径长度。121、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格部分的内容，并画出二叉树。先序遍历BFICEHG中序遍历DKFIAEJC后序遍历KFBHJGA15、如图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有叶子结点。第七章图1.在一个无向图中,所有顶点的度数之和等于所有边数的倍。A.1/2B.1C.2D.42.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B.1C.2D.43.一个有n个顶点的无向图最多有条边。A.nB.n(n-1)C.n(n-1）/2D.2n4.具有4个顶点的无向完全图有条边。A.6B.12C.16D.205.具有6个顶点的无向图至少应有条边才能确保是一个连通图。A.5B.6C.7D.86.在一个具有n个顶点的无向图中,要连通全部顶点至少需要条边。A.nB.n+1C.n-1D.n/27.在有n个顶点的有向图中，每个顶点的度最大可达8.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小A.nB.(n-1)2C.n-1D.n29.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为，所有邻接表中的结点总数是。10.采用邻接表存储的图的深度优先遍历算法类似于二叉树的。A.先序遍历B.中序遍历C.后序遍历D.按层遍历11.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的A.先序遍历B.中序遍历C.后序遍历D.按层遍历GJIHFDCEBA212.一个有向图G的邻接表存储如图，现按深度优先遍历，从顶点v1出发，所得到的顶点序列是13.一个如图的无向图，从顶点1出发进行深度优先遍历，，可得到的顶点序列是14.一个如图的无向图，从顶点1出发进行广度优先遍历，，可得到的顶点序列是15.已知图G的邻接表存储如图，从顶点v1出发，现按深度优先遍历所得到的顶点序列是；从顶点v1出发，现按广度优先遍历所得到的顶点序列是v1v3v4v2452^^^v535^34^1326574316.图G是一个非连通无向图，共有28条边，则该图至少有个顶点。17.一个无向连通图的生成树是含有该连通图的全部顶点的A.极小连通子图B.极大连通子图C.极小子图D.极大子...
