数据结构第二单元测验题目的参考答案
数据结构第二单元测验答案
一、选择题
1.由3 个结点可以构造出多少种不同的有向树( )
A.2
B.3
C.4
D.5
2.由3 个结点可以构造出多少种不同的二叉树( d)
A.2
B.3
C.4
D.5
3.二叉树的第I层上最多含有结点数为(c )
A.2I
B.2I-1-1
C.2I-1
D.2I -1
4.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( b )结点
A.2h
B.2h-1
C.2h+1
D.h+1
除第一层外,每层最少2个结点
5.一棵树高为K的完全二叉树至少有( c )个结点
A.2k–1
B.2k-1–1
C.2k-1
D.2k
6.深度为6的二叉树最多有( c )个结点
A．64 B.63 C.32 D.31
7.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )
A.5
B.6
C.7
D.8
8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( c )
A.9
B.11
C.15
D.不确定
9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( e )
A.250
B.500
C.254
D.505 E．以上答案都不对
10.对于有n 个结点的二叉树, 其高度为( d )
A.nlog2n
B.log2n
C.?log2n?|+1
D.不确定
11.将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为（）
A.42
B.40
C.21
D.20
12.一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I J
则结点E在二叉树的第（c ）层。
A. 1
B. 2
C. 3
D.4
13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ b）的二叉树
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
14.任何一棵二叉树的叶结点在其先根.中根.后根遍历序列中的相对位置( c )
A.肯定发生变化
B.有时发生变化
C.肯定不发生变化
D.无法确定
15.二叉树线索化后，仍不能有效求解的问题是（d ）
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱
D.后序线索二叉树中求后续后继
一共有两种情况:一个是先序线索中求先序前驱和后序线索求后序后继
16.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的( a )
A.前序
B.中序
C.后序
D.层次序
17.设森林T中有4棵树，第一.二.三.四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有( d )个结点。
A.n1-1
B.n1
C.n1+n2+n3
D.n2+n3+n4
18.设给定权值总数有n 个,其哈夫曼树的结点总数为( d )
A.不确定
B.2n
C.2n+1
D.2n-1
19.下面几个符号串编码集合中，不是前缀编码的是( b)
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 ）。
A．n-1 B．n C．n+1 D．nlogn
21.n个结点的完全有向图含有边的数目是（ d ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
22.下面关于图的存储的叙述中正确的是（ b ）。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
23.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（ a ）
A.先根遍历
B.中根遍历数据结构与算法题库
C.后根遍历
D.按层次遍历
24.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={,,,,,,,,},G的拓扑序列是（ a ）。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
25.关键路径是事件结点网络中（ a ）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路 D．最短回路26.下面关于求关键路径的说法不正确的是（ c ）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
二、填空题
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，则该二叉树的高度为__ ?log2k?+1 ____。
7.对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为2i；若右孩子结点存在，则其编号为2i+1；而双亲结点的编号为? i/2 ?。
8.具有N个结点的二叉树，采用二叉链表存储，共有_ N+1 _____个空链域。