数据结构第二单元测验答案

《数据结构第二单元测验答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第二单元测验答案一、选择题1.由3个结点可以构造出多少种不同的有向树()A.2B.3C.4D.52.由3个结点可以构造出多少种不同的二叉树()A.2B.3C.4D.53.二叉树的第I层上最多含有结点数为()A.2IB.2I-1-1C.2I-1D.2I-14.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A.2hB.2h-1C.2h+1D.h+1除第一层外,每层最少2个结点5.一棵树高为K的完全二叉树至少有()个结点A.2k–1B.2k-1–1C.2k-1D.2k6.深度为6的二叉树最多有()个结点A．64B.63C

2、.32D.317.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为()A.5B.6C.7D.88.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()A.9B.11C.15D.不确定9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是()A.250B.500C.254D.505E．以上答案都不对10.对于有n个结点的二叉树,其高度为()A.nlog2nB.log2nC.ëlog2nû

3、+1D.不确定11.将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下.从左到右顺序

4、结点编号，那么编号为41的双亲结点编号为（）A.42B.40C.21D.2012.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCD　EF　G　　H　IJ则结点E在二叉树的第（）层。A.1B.2C.3D.413.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子14.任何一棵二叉树的叶结点在其先根.中根.后根遍历序列中的相对位置()A.肯定发生变化B.有时发生变化C.肯定不发生变化D.无法确定15.二叉树线索化后，

5、仍不能有效求解的问题是（）A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后续后继第5页共5页一共有两种情况:一个是先序线索中求先序前驱和后序线索求后序后继16.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的()A.前序B.中序C.后序D.层次序17.设森林T中有4棵树，第一.二.三.四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有()个结点。A.n1-1B.n1C.n1+n2+n3D.n2+n3+n418.设

6、给定权值总数有n个,其哈夫曼树的结点总数为()A.不确定B.2nC.2n+1D.2n-119.下面几个符号串编码集合中，不是前缀编码的是()A.{0,10,110,1111}B.{11,10,001,101,0001}C.{00,010,0110,1000}D.{b,c,aa,ac,aba,abb,abc}20.一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn21.n个结点的完全有向图含有边的数目是（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）22.下面关于图的存储的叙述中正确的是（）。A.用邻接

7、表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关23.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历24.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,<

8、V3,V5>,,,,},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V725.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路26.下面关于求关键路径的说法不正确的是（）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始

9、时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上二、填空题1.具