数据结构练习2-09答案

数据结构练习（二）答案

一、填空题：

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之间

hh-1

关系的表达式 （4）n=2-1,m=n+1-2 n=2m-1 。

3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。

k-1k

一棵深度为k的完全二叉树中最少有 2（6） 个结点，最多有（7）2-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层最多有___ki-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+kh-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)

1

O(n2) ；若用邻接表表示图，访问一个顶点的所有邻接顶点的时间复杂性为 (15) O(n) 。一个有n个顶点的有向图中，最少有 (16)0 弧，最多有 (17) n(n-1) 弧。 二、选择题

1.树型结构最适合用来描述_______ A．有序的数据元素 B．无序的数据元素

C．数据元素之间具有层次关系的数据 D．数据元素之间没有关系的数据 2.对于一棵具有n个结点、度为4的树而言，_____。

A．树的深度最多是n-4 B．树的深度最多是n-3 C．第i层上最多有4×(i-1)个结点 3.”二叉树为空”意味着二叉树______ A．由一些未赋值的空结点组成 B．根结点无子树 C．不存在 D．没有结点

4.按照二叉树的定义，具有3个结点的二叉树有___种形态(不考虑数据信息的组合情况)。

A.2 B.3 C.4 D.5

5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为 。 A．9 B．11 C．15 D．不确定 6.一个具有1025个结点的二叉树的高h为 。 A．11 B．10 C．11—1025 D．12—1024 7．若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是___树。 A．空或仅有一个结点 B．其分支结点无左子树 C．其分支结点无右子树 D．其分支结点的度都为1

8．任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置__

A．都会发生改变 B．不会发生改变 C．有可能会发生改变 D．部分会发生改变 9．如图所示的二叉树T2是由森林T1转换而来

A的二叉树，那么森林T1有_____个叶子结点。 A．4 B．5 C．6 D．7 BE10．设n，m为一棵二叉树上的两个结点，在中

CFH序遍历时，n在m前的条件是_____。

A．n在m右方 B．n是m祖先

DGIJC．n在m左方 D．n是m子孙 11．一棵二叉树的先序遍历序列为ABCDEFG，

2

它的中序遍历序列可能是_____。

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEGB 12．引入线索二叉树的目的是_____。

A．加快查找结点的前驱或后继结点的速度 C．为了能方便找到双亲 B．为了能在二叉树中方便插入和删除 D．使二叉树的遍历结果唯一 13．线索二叉树是一种_____结构。 A．逻辑 B．逻辑和存储 C．物理 D．线性 14．判断线索二叉树中*p结点有右孩子结点的条件是_____。 A．p！=NULL B．P—>rchild!=NULL C．p—>rtag=0 D．p—>rtag=1

15．n个结点的线索二叉树上含有的线索数为_____。 A．2n B．n-1 C．n+1 D．n 16．根据使用频率为5个字符设计的哈夫曼编码不可能是_____。 A．000，001，010，011，1 B．0000，0001，001，01，1 C．000，001，01，10，11 D．00，100，101，110，111 18．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_____个结点。 A．13 B．12 C．26 D．25 19．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A.1/2 B.1 C.2 D.4 20．一个具有n个顶点的无向图最多有______条边。

2

A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n 21．一个具有n个顶点的有向图最多有_________条边。 A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n2

22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边 A.n B.n+1 C.n-1 D.2n 23．具有n个顶点的连通图的生成树一定有________条边。 A.n B.n+1 C.n-1 D.2n

24．若一个非连通的无向图最多有28条边，则该无向图至少有__个项点。 A.6 B.7 C.8 D.9 25．在带权图中，两个顶点之间的路径长度是______。 A．路径上的顶点数目 B．路径上的边的数目

C．路径上顶点和边的数目 D．路径上所有边上的权值之和

26．若具有n个顶点的元向图采用邻接矩阵存储方法,该邻接矩阵一定为一个___。

A．一般矩阵 B．对称矩阵 C．对角矩阵 D．稀疏矩阵 27．若图的邻接矩阵中主对角线上的元素均为0，其余元素全为1，则可以断定

3

该图一定__。

A．是无向图 B．是有向图 C．是完全图 D．不是带权图 28．有向图的邻接表的第i个链表中的边结点数目是第i个顶点的____。 A．度数 B．出度 C．人数 D．边数 29．若某图的邻接表中的边结点数目为奇数，则该图_______。 A．一定有奇数个顶点 B．一定有偶数个顶点 C．一定是有向图 D．可能是无向图

30．若某图的邻接表中的边结点数目为偶数，则该图______。 A．一定是无向图 B．可能是有向图 C．可能是无向图，也可能是有向图 D．一定有偶数个顶点

31．若无向图有k条边，则相应的邻接表中就有_______个边结点。 A.k-1 B.k C.2k D.k2

32．若有向图有k条边，则相应的邻接表中就有_____个边结点。 A.k-1 B.k C.2k D.k2

33．对于一个不带权的无向图的邻接矩阵而言，_________ A．矩阵中非零元素的数目等于图中边的数目 B．矩阵中非全零的行的数目等于图中顶点的数目

C．第i行的非零元素的数目与第i列的非零元素的数目相等 D．第i行与第i列的非零元素的总数等于第i个顶点的度数 34．导致图的遍历序列不惟一的因素有________。

A．出发点不同、遍历方法不同 B．出发点不同、存储结构不同 C．遍历方法不同、存储结构不同

D．出发点不同、存储结构不同、遍历方法不同 35．若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个____________图。

A．非连通 B．连通 C .强连通 D.完全 36．可以进行拓扑排序的图一定是______。

A．连通图 B．带权连通图 C．无回路的图 D．无回路的有向图 37．已知某有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}, E={, ,，,,,},G的拓扑序列是_________。

A. 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．即使所有非关键活动都未按时完成，整个工程仍有可能按时完成

4

C．任何一个关键活动的延期完成，都会导致整个工程的延期完成 D．任何一个关键活动的提前完成，都会导致整个工程的提前完成 39．无向图的邻接矩阵是一个_____. A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵 40．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____。 A．完全图 B．连通图 C．有回路 D．一棵树 41．采用邻接表存储的图的深度优先遍历算法类似于二叉树的_____算法。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 42．一个无向连通图的生成树是含有该连通图的全部顶点的

A．极小联通子图 B.极小子图 C．极大连通子图 D．极大子图 43．任何一个无向连通图 最小生成树。

A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 44．求最短路径的Dijkstra算法的时间复杂度为 。 A．O（n） B. O（n+e） C．O（n2） D． O（n3） 45．求最短路径的Floyd算法的时间复杂度为 。 A．O（n） B. O（ne） C．O（n2） D．O（n3） 45-2有向网G用邻接矩阵A存储，则顶点i的入度等于A中 。 A)第i行非?的元素之和 C)第i列非?的元素之和 B)第i行非?且非0的元素个数 D)第i列非?且非0的元素个数 46．关键路径是事件结点网中_____。

A．从起点到终点的最长路径 B．从起点到终点的最短路径 C．最长的回路 D．最短的回路 47．已知一个有向图如右图所示，则从顶点a出发进行深度优先遍历不可能得到的DFS序列为_____。 A）adbefc B）adcefb C）adcbfe D）adefcb 三、判断题

? (1)在树型结构中,每一个结点最多只有一个前驱结点,

但可以有多个后继结点.

(2)在树型结构中，每一个结点不能没有前驱结点。 ? (3)在度为k的树中，至少有一个度为k的结点。 (4)在度为k的树中，每个结点最多有k-1个兄弟结点。 (5)度为2的树是二叉树。 (6)二叉树的度一定为2。 (7)在非空完全二叉树中，只有最下面一层的结点为叶结点。 ? (8)在完全二叉树中，没有左孩子的结点一定是叶结点。

5

(9)在完全二叉树中，没有右孩子的结点一定是叶结点。

? (10)在结点数目一定的前提下,各种形态的二叉树中,完全二叉树具有最小

深度。

? (11)满二叉树一定是完全二叉树。 ? (12)满二叉树中的每个结点的度不是0就是2。 ? (13)在所有深度相同的二叉树中，满二叉树具有最大结点数目。 ? (14)具有n个结点的非空二叉树一定有n-1个分支。

(15)n个结点的二叉树采用二叉链表结构,链表中有n-1个存放NULL指针域。 ? (16)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。 ? (17)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。 (18)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。 ? (19)实现二叉树的按层次遍历算法时需要用到队列结构。 (20)实现二叉树的遍历算法时不需要用到堆栈结构。 ? (21)线索二叉树对应的二叉链表中不存在空的指针域。 (22)给定一组权值，构造出来的哈夫曼树是惟一的。 ? (23)哈夫曼树中不存在度为1的结点。 (24)在哈夫曼树中，权值相同的叶结点都在同一层上。 (25)没有顶点的图称为空图。 (26)图的度是图中所有顶点的度的最大值。 ? (27)边上带权值的图称为网(络)。 (28)图中一个顶点的度应该是它的出度与人度之和。 (29)n个顶点的无向图最多有n(n-1)条边。 ? (30)在有向图中，所有顶点的人度之和等于所有顶点的出度之和。 ? (31)在无向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (32)在有向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (33)连通图的最小生成树是惟一的。 (34)邻接矩阵主要用来表示顶点之间的关系。 ? (35)若表示某图的邻接矩阵不是对称矩阵，则该图一定是有向图。 ? (36)若表示某图的邻接矩阵中出现了全零行或者全零列，则该图一定是非连通图或者非强连通图。

? (37)对于同一个有向图，邻接表中的边结点数目与逆邻接表中边结点数目相等。

? (38)无向图的邻接表中边结点数目一定为偶数。 ? (39)邻接表中边结点数目为奇数的图一定是有向图。 (40)邻接表中边结点数目为偶数的图一定是无向图。 ? (41)对图进行广度优先搜索的过程中要用到队列。

6

? (42)对图进行深度优先搜索的过程中要用到堆找。 (43)带权连通图的最小生成树是惟一的。 ? (44)最短路径一定是简单路径。

(45)求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向网络。

? (46)若AOV网中存在拓扑序列，则一般情况下，拓扑序列不是惟一的。 (47)关键路径是由权值最大的边构成的。 (48)给定的AOE网的关键路径一定是惟一的。

四、简答题：

1．已知森林的先序遍历序列为ABDJCEFHK，中序序列为DJBAECHKF，请画出该森林。

2．若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？ 14 25

3．一棵度为2的树与一棵二叉树有什么区别?将树转化为二叉树的基本目的是什么？

可以采用二叉树的结构并利用已有的算法解决树的有关问题。 4．已知一棵完全二叉树共有892个结点，试求： （1）树的高度 10 （2）叶子结点数 446 （3）单支结点数 1

（4）最后一个非终端结点的序号 446 5．画出二叉树的后序前驱线索。

6．一文件中只出现9种字符：a、b、c、d、e、f、g、h，它们出现的频率分别为8、9、3、5、6、4、2、1，请根据书上算法画出相应的哈夫曼树(叶子结点用相应字母表示,左子树的权小于右子树的权)，给出哈夫曼编码，并计算其带权的路径长度WPL。

7．已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表结构的表示。

8.已知按前序遍历二叉树的结果为ABC。试问，有几种不同的二叉树可以得到

7

这一遍历结果? 5

9.将图所示的树林转换为一棵二叉树。

10.分别写出如图所示的树的前序遍历序列与后序遍历序列。 ACHABDGEFIJBEFGCHKIDJ

题9 题10 11.已知某树林转化为二叉树后所对应的顺序存储结构为 A B H C E I J D F G 请画出该树林。

5．请写出用普里姆算法对下图求最小生成树的计算过程 6．对下边的图

（1）给出从结点v1出发按广度优先遍历得到的结点序列 （2）给出G的一个拓扑序列

（3）给出从结点v1到结点v8的最短路径和关键路径（给出计算过程） 三、算法设计：

1．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号。假设二叉树采用二叉链表的存储结构，编写void BiTreeNumber(BiTree &T);完成：给各个结点编号，按编号从小到大的顺序输出各结点的data及相应的编号。（提示：使用某种遍历算法） 本题采用的数据结构为：

typedef struct BiTNode { TElemType data;

int number; //结点的编号 struct BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree;

2．写出在中序线索二叉树中找p所指向结点的前驱和后继的算法片段。 3.已知两棵二叉树都采用二叉链表存储结构，根结点的地址分别为T1和T2。请写一算法，判断两棵二叉树是否相似(即具有相同的形态)，并给出相应信息。 4．图G的存储结构为邻接表，试写出对图G进行深度优先遍历的算法。

8

void DFSTraverse(ALGraph G, Status(* Visit)(int v))

9

本文来源：https://www.bwwdw.com/article/hrxt.html