《数据结构第二单元测验答案》由会员分享，可在线阅读，更多相关《数据结构第二单元测验答案（5页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 5 页数据结构第二单元测验答案一、选择题1.由 3 个结点可以构造出多少种不同的有向树( )A.2 B.3 C.4 D.5 2.由 3 个结点可以构造出多少种不同的二叉树( )A.2 B.3 C.4 D.5 3.二叉树的第 I 层上最多含有结点数为( )A.2I B.2I-1-1 C.2I-1 D.2I -14.一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有( )结点A.2h B.2h-1 C.2h+1 D.h+1 除第一层外,每层最少 2 个结点5.一棵树高为 K 的完全二叉树至少有( )个结点A.2k 1 B.2k-1 1 C.2k-1 D.2k6
2、.深度为 6 的二叉树最多有( )个结点 A64 B.63 C.32 D.317.设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为( )A.5 B.6 C.7 D.88.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是( )A.9 B.11 C.15 D.不确定 9.一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )A.250 B.500 C.254 D.505 E以上答案都不对 10.对于有 n 个结点的二叉树, 其高度为( )A.nlog2n B.log2n C.log2n|
3、+1 D.不确定11.将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，按从上到下.从左到右顺序结点编号，那么编号为 41 的双亲结点编号为（ ） A.42 B.40 C.21 D.2012.一个二叉树按顺序方式存储在一个维数组中，如图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14A B C D E F G H I J则结点 E 在二叉树的第（ ）层。A. 1 B. 2 C. 3 D.413.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子14.任何一棵
4、二叉树的叶结点在其先根.中根.后根遍历序列中的相对位置( ) A.肯定发生变化 B.有时发生变化C.肯定不发生变化 D.无法确定15.二叉树线索化后，仍不能有效求解的问题是（ ）A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后续后继第 2 页 共 5 页一共有两种情况:一个是先序线索中求先序前驱和后序线索求后序后继16.如果 T2是由有序树 T 转化而来的二叉树，那么 T 中结点的前序就是 T2中结点的( )A.前序 B.中序 C.后序 D.层次序17.设森林 T 中有 4 棵树，第一.二.三.四棵树的结点个数分别是 n1,n
5、2,n3,n4,那么当把森林 T 转换成一棵二叉树后，且根结点的右子树上有( )个结点。A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 18.设给定权值总数有 n 个,其哈夫曼树的结点总数为( )A.不确定 B.2n C.2n+1 D.2n-119.下面几个符号串编码集合中，不是前缀编码的是( )A.0,10,110,1111 B.11,10,001,101,0001C.00,010,0110,1000 D.b,c,aa,ac,aba,abb,abc20.一个 n 个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn21.n 个结点的完全有向图
6、含有边的数目是（ ） 。An*n n（n） Cn2 Dn*（nl）22.下面关于图的存储的叙述中正确的是（ ） 。A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关23.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历24.已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4,
7、V5,V6,V7，E=,G 的拓扑序列是（ ） 。AV 1,V3,V4,V6,V2,V5,V7 BV 1,V3,V2,V6,V4,V5,V7CV 1,V3,V4,V5,V2,V6,V7 DV 1,V2,V5,V3,V4,V6,V725.关键路径是事件结点网络中（ ） 。A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长回路 D最短回路26.下面关于求关键路径的说法不正确的是（ ） 。A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路
8、径上二、填空题1.具有 n 个结点的满二叉树，其叶结点的个数是_(n+1)/2_。2.完全二叉树中，结点个数为 n，则编号最大的分支结点的编号为_n/2 _。3.一棵共有 n 个结点的树，其中所有分支结点的度均为 k，则该树中的叶子结点个数为 n-(n-1)/k 。4.含 4 个度为 2 的结点和 5 个叶子结点的二叉树，可有_0 至多个_个度为 1 的结点。5.8 层完全二叉树至少有_ 128(第七层满，加第八层个)_个结点，拥有 100 个结点的完全二叉树的最大层数为_7_。6.设一棵完全二叉树叶子结点数为 k,最后一层结点数2，则该二叉树的高度为_ 第 3 页 共 5 页log2k+1
9、_。7.对一棵完全二叉树，设一个结点的编号为 i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 i/2 。8.具有 N 个结点的二叉树，采用二叉链表存储，共有_ N+1 _个空链域。9.在二叉树中，指针 p 所指结点为叶子结点的条件是_ p-lchild=NULL & p-rchlid=NULL _。10.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_前序 _序列中的最后一个结点。11.在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_n_条弧。12.如果含 n 个顶点的图形形成一个
10、环，则它有_ n_棵生成树。13.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历。14.求图的最小生成树有两种算法，_克鲁斯卡尔_算法适合于求稀疏图的最小生成树。三、判断题1.树与二叉树是两种不同的树型结构。2.度为二的树就是二叉树。3.在二叉树的第 i 层上至少有 2i-1个结点(i=1)。4.完全二叉树一定存在度为 1 的结点。5.若一棵二叉树的任一非叶子结点的度为 2，则该二叉树为满二叉树( X )6.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。7.若某二叉树的叶子结点数为 1，则其先序序列和后序序列一定相反(
11、 )8.二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。9.已知一棵树的先序序列和后序序列，一定能构造出该树( )10.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。11.有向图中顶点 V 的度等于其邻接矩阵中第 V 行中的 1 的个数。12.一个有向图的邻接表和逆邻接表中结点的个数可能不等。13.在无向图的深度优先遍历算法中，DFS（从某个顶点出发深度优先遍历图的算法）被调用了几次就说明该图有几个联通分量。 （ ）14.需要借助于一个队列来实现 DFS 算法(深度优先遍历)。 15.广度遍历生成树描述了从起点到各顶点的最短路
12、径。16.既使有向无环图的拓扑序列唯一，也不能唯一确定该图。17.在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。四、解答题1.已知一棵二叉树的前序遍历的结果是 ABKCDFGHIJ, 中序遍历的结果是 KBCDAFHIGJ, 试画出这棵二叉树。当前序序列为 ABKCDFGHIJ，中序序列为 KBCDAFHIGJ 时，逐步形成二叉树的过程如下图所示：第 4 页 共 5 页2.对于给定的 5 个实数 W=8，5，13，2，6，试构造哈夫曼树；并求出每个叶子结点的哈夫曼编码。 8 5 2 613 7 5 13 6 7 5 2 8 13 2 34 6 7 5 2 8 13
13、 2 每个叶子的哈夫曼编码为：权值为 8 的哈夫曼编码：10权值为 5 的哈夫曼编码：011权值为 13 的哈夫曼编码:11权值为 2 的哈夫曼编码：010权值为 6 的哈夫曼编码：00注意：哈夫曼树及编码不唯一3.对带权无向图（如图 1 所示）采用 prim 算法从顶点开始构造最小生成树。(写出加入生成树顶点集合 S 和选择边 Edge 的顺序)顶点号 （顶点，顶点，权值） （ 1， 2，9 ） （ 2， 4，5 ） （ 2， 3，7 ）Edge：（ 3， 5，6 ） （ 3， 6，7 ）S：第 5 页 共 5 页四、算法设计题1.编写算法实现二叉树的层次遍历顺序（同一层次从左至右）算法。v
14、oid LayerOrder(Bitree T) /层序遍历二叉树InitQueue(Q); /建立工作队列 .(1 分)if（T）EnQueue(Q,T); .(1 分)while(!QueueEmpty(Q) DeQueue(Q,p); .(4 分)visit(p);if(p-lchild) EnQueue(Q,p-lchild); .(2 分)if(p-rchild) EnQueue(Q,p-rchild); .(2 分)/LayerOrder2. 试写出一递归函数，复制一棵二叉树。BiTree Copy(BiTree t)/复制二叉树 tBiTree bt;if (t=null) bt=null;elsebt=(BiTree)malloc(sizeof(BiNode); bt-data=t-data;bt-lchild=Copy(t-lchild);bt-rchild=Copy(t-rchild); return(bt); /结束
