数据结构练习（二）答案
一、填空题：
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之间关系的表达式（4）n=2h-1,m=n+1-2h-1 n=2m-1 。
3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。
一棵深度为k的完全二叉树中最少有2k-1（6）个结点，最多有（7）2k-1个结点。
4．具有n个结点的二叉树，当它是一棵(8)完全二叉树时具有最小高度（9） log2n」+1，当它为一棵单支树时具有高度(10) n 。
5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。
6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。
7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。
8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。
9．已知某完全二叉树采用顺序存储结构，结点的存放次序为
A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。
11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。
度为k的树中第i层最多有___k i-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+k h-1____个结点。
12．非空二叉树一共有__4__种基本形态，第i层最多有__ 2i-1___个结点。13．在一棵完全二叉树中，编号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)
O(n 2)  ；若用邻接表表示图，访问一个顶点的所有邻接顶点的时间复杂性为  (15) O(n) 。一个有n 个顶点的有向图中，最少有  (16)0  弧，最多有  (17) n(n-1) 弧。
二、选择题
1.树型结构最适合用来描述_______
A ．有序的数据元素
B ．无序的数据元素
数据元素之间具有层次关系的数据    D ．数据元素之间没有关系的数据
2.对于一棵具有n 个结点、度为4的树而言，_____
。
A ．树的深度最多是树的深度最多是n-3
C ．第i 层上最多有4×(i-1)个结点
D ．最少在某一层上正好有4个结点
3.”二叉树为空”意味着二叉树______
A ．由一些未赋值的空结点组成 B
．根结点无子树
C ．不存在 没有结点
4.按照二叉树的定义，具有3个结点的二叉树有___种形态(不考虑数据信息的组合情况)。
A.2
B.3
C.4          5 5．若一棵二叉树具有10个度为2的结点，5个度为10的结点个数为      。
A ．9
11    C ．15      D ．不确定
6.一个具有1025个结点的二叉树的高h
A ．11
B ．10    D ．12—
1024
7．若二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是___树。
A ．空或仅有一个结点
B ．其分支结点无左子树
C ．其分支结点无右子树 其分支结点的度都为1
8．任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置__
A ．都会发生改变 不会发生改变
C ．有可能会发生改变
D ．部分会发生改变
9．如图所示的二叉树T2是由森林T1转换而来
的二叉树，那么森林T1有_____个叶子结点。
A ．4
B ．5    6  D ．7 10．设n ，m 序遍历时，n 在
m 前的条件是_____。
n 在m 右方  B ．n 是m 祖先
n 在m 左方  D ．n 是m 子孙 11．一棵二叉树的先序遍历序列为ABCDEFG ，
_____。
A．CABDEFG ABCDEFG C．DACEFBG ADCFEGB
_____。
加快查结点的前驱或后继结点的速度C．为了能方便到双亲
D．使二叉树的遍历结果唯一13．线索二叉树是一种_____结构。
A．逻辑B．逻辑和存储物理D．线性14．判断线索二叉树中*p_____。
p！=NULL B．P—>rchild!=NULL
p—>rtag=0 D．p—>rtag=1
n_____。
A．2n B．n-1 n+1 D．n
16．根据使用频率为5个字符设计的哈夫曼编码不可能是_____。
A．000，001，010，011，1 0000，0001，001，01，1
C．000，001，01，10，11 00，100，101，110，111先序中序后序遍历二叉树
17．若度为m的哈夫曼树中，其叶子结点个数为n，则非叶子结点的个数为___。A．n-1 B．(n/m) -1 C
．（n-1）/(m-1) D．n/(m-1) -1 取消此题18．设有13个值，用它们组成一棵哈夫曼树，_____个结点。
A．13 B．12 C．26 25
19．在一个图中，所有顶点的度数之和等于所有边数的____倍。
A.1/2
B.1        2        D.4
．一个具有n个顶点的无向图最多有______条边。
B.n(n-1)
C.n(n+1)/2
D.n2
21．一个具有n个顶点的有向图最多有_________条边。
n(n-1)        C.n(n+1)/2      D.n2
22____条边
A.n
B.n+1    n-1        D.2n
23．具有n________条边。
A.n
B.n+1    n-1        D.2n
24．若一个非连通的无向图最多有28条边，则该无向图至少有__个项点。
A.6
B.7
C.8
D.9
25．在带权图中，两个顶点之间的路径长度是______。
A．路径上的顶点数目路径上的边的数目
C．路径上顶点和边的数目 D．路径上所有边上的权值之和
26．若具有n个顶点的元向图采用邻接矩阵存储方法，该邻接矩阵一定为一个___。
A．一般矩阵对称矩阵C．对角矩阵D．稀疏矩阵27．若图的邻接矩阵中主对角线上的元素均为0，其余元素全为1，则可以断定该图一定__。
A．是无向图  B．是有向图是完全图D．不是带权图
28．有向图的邻接表的第i i个顶点的____。
A．度数出度C．人数D．边数
29．若某图的邻接表中的边结点数目为奇数，则该图_______。
A．一定有奇数个顶点B．一定有偶数个顶点
一定是有向图D．可能是无向图
30．若某图的邻接表中的边结点数目为偶数，则该图______。
A．一定是无向图B．可能是有向图
可能是无向图，也可能是有向图D．一定有偶数个顶点
31．若无向图有k_______个边结点。
A.k-1
B.k    2k        D.k2
32．若有向图有k条边，则相应的邻接表中就有_____个边结点。
A.k-1    k        C.2k        D.k2
33．对于一个不带权的无向图的邻接矩阵而言，_________
A．矩阵中非零元素的数目等于图中边的数目
第i行的非零元素的数目与第i列的非零元素的数目相等
D．第i行与第i列的非零元素的总数等于第i个顶点的度数
．导致图的遍历序列不惟一的因素有________。
出发点不同、遍历方法不同B．出发点不同、存储结构不同C．遍历方法不同、存储结构不同
D．出发点不同、存储结构不同、遍历方法不同
35．若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个____________图。
A．非连通连通  C .强连通  D.完全
36．可以进行拓扑排序的图一定是______。
A．连通图    B．带权连通图C．无回路的图无回路的有向图
37．已知某有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}, E={<v1,v2>, <v1,v4>,<v2,v6>，<v3,v1>,<v3,v4>,<v4,v5>,<v5,v2><v5,v6>},G的拓扑序列是_________。
v3,v1,v4,v5,v2,v6    B．v3,v4,v1,v5,v2,v6
C. v1,v3,v4,v5,v2,v6
D. v1,v4,v3,v5,v2,v6
38．下面关于AOE网的叙述中，不正确的是_______。
A．若所有关键活动都提前完成，则整个工程一定能够提前完成
B．即使所有非关键活动都未按时完成，整个工程仍有可能按时完成
C．任何一个关键活动的延期完成，都会导致整个工程的延期完成
任何一个关键活动的提前完成，都会导致整个工程的提前完成
_____.
B．零矩阵C．上三角矩阵D．对角矩阵40．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____。
A．完全图C．有回路D．一棵树
_____算法。
B．中序遍历C．后序遍历D．按层遍历．一个无向连通图的生成树是含有该连通图的全部顶点的
B.极小子图C．极大连通子图D．极大子图．任何一个无向连通图最小生成树。
A．只有一棵C．一定有多棵D．可能不存在44．求最短路径的Dijkstra算法的时间复杂度为。
A．O（n）  B. O（n+e）O（n2）D．O（n3）45．求最短路径的Floyd算法的时间复杂度为。
A．O（n）  B. O（ne）C．O（n2）O（n3）
45-2有向网G用邻接矩阵A存储，则顶点i的入度等于A中。
A)第i行非∞的元素之和i列非∞的元素之和
B)第i行非∞且非0的元素个数i列非∞且非0的元素个数46．关键路径是事件结点网中_____。
从起点到终点的最长路径B．从起点到终点的最短路径
D．最短的回路
47．已知一个有向图如右图所示，则从顶点a出发进行深
度优先遍历不可能得到的DFS序列为_____。
B）adcefb  C）adcbfe
三、判断题
√ (1)在树型结构中，每一个结点最多只有一个前驱结点,
但可以有多个后继结点.
(2)在树型结构中，每一个结点不能没有前驱结点。
√ (3)在度为k的树中，至少有一个度为k的结点。
(4)在度为k的树中，每个结点最多有k-1个兄弟结点。
(5)度为2的树是二叉树。
(6)二叉树的度一定为2。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。