当前位置：文档之家 › 树形结构练习题

树形结构练习题

  • 格式：doc
  • 大小：11.83 MB
  • 文档页数：17

选择题答案：1.C 3.B 4.B
5.A
6.B
7.B
8.B
9.D 12.D 14.C 15.B 17.C 18.A 19C 20 A 21.C 22 D 23C 26 C 27 C
7.1选择题
2．设无向图的顶点个数为n，则该图最多有（ B ）条边。

A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2
3．连通分量指的是（B ）
A）无向图中的极小连通子图
B）无向图中的极大连通子图
C）有向图中的极小连通子图
D）有向图中的极大连通子图
4．n个结点的完全有向图含有边的数目（D ）
A）n*n B）n（n+1）C）n/2 D）n*（n-1）
6．有向图中一个顶点的度是该顶点的（ C ）
A）入度B）出度C）入度与出度之和D）（入度+出度）/2
7．有e条边的无向图，若用邻接表存储，表中有（B ）边结点。

A）e B）2e C）e-1 D）2(e-1)
8．实现图的广度优先搜索算法需使用的辅助数据结构为（B ）
A）栈B）队列C）二叉树D）树
10．存储无向图的邻接矩阵一定是一个（ C ）
A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵
11．在一个有向图中所有顶点的入度之和等于出度之和的（B）倍
A）1/2 B）1 C）2 D）4
12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为（B ）
A）O(n) B）O(n+e) C）O(n2) D）O(n3)
14．具有10个顶点的无向图至少有多少条边才能保证连通（A ）
A）9 B）10 C）11 D）12
15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ D ）
A）e B）2e C）n2-e D）n2-2e
7.2填空题
1．无向图中所有顶点的度数之和等于所有边数的______2_______倍。

2．具有n个顶点的无向完全图中包含有__n(n-1)/2___________条边，具有n个顶点的有向完全图中包含有___n(n-1)__________条边。

3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要___n-1____________条边。

4．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为______ O(n2)______和___O(n+e) __________。

5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为____ O(n2) ____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_______ O(e _______。

6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____ e ________和______2 e _______条。

7．在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有___出边__________和___入边__________结点。

9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为____ n _________和_________ n -1____。

11．针对下图所示的连通网络，试按如下格式给出在Kruscal算法构造最小生成树过程中顺序选出的各条边。

【答案】设边的信息表示为（始点，终点，权值），则在Kruscal算法构造最小生成树过程中顺序选出的各条边为：（3 ，5，1），（2，4，2），（1，5，3），（1，2，3）。

7.3判断题
1．图是一种非线性结构，所以只能用链式存储。

（×）
2．图的最小生成树是唯一的。

（×）
3．如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。

（√）
4．有n-1 条边的图一定是生成树。

（×）
5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。

（√）
7．逆邻接表只能用于有向图，邻接表对于有向图和无向图的存储都适用。

（√）
11．图的邻接矩阵存储是唯一的，邻接表存储也是唯一的。

（×）
13．任意一个图都是其自身的子图。

（√）
14．一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。

（×）
7.4应用题
1．设有一有向图为G=(V，E)。

其中，V={ v1, v2, v3, v4, v5}，E={<v2, v1>, <v3, v2>, <v4, v3>, <v4, v2>, <v1, v4>, <v4, v5>, <v5, v1>}，请画出该有向图并判断是否是强连通图。

答：该有向图是强连通图，表示如下
2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。

并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。

答
3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：
（1）图中有多少条边?
答：无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数
（2）任意两个顶点i和j是否有边相连?
答：邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。

（3）任意一个顶点的度是多少?
答：任意一个顶点vi的度是第i行或第i列上非0元的个数。

4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。

写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。

邻接矩阵如下：
，邻接表如下：
，逆邻接表如下：
，十字链表如下：
5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。

答：该无向图如下所示：
6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树。

9．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。

10．利用Floyd算法求下图中各对顶点之间的路径。

合集下载

第七章和第八章补充练习题(答案)

第七章和第八章补充练习题(答案)

7.3补充练习题及参考答案7.3.1单项选择题1.对于一棵具有n 个结点、度为4的树来说,_____________.A.树的高度最多是n-3B.树的高度最多是是n-4C.第i 层上最多有4(i-1)个结点D.至少在某一层上正好有4个结点答:这样的树中至少有一个结点的度为4,也就是说,至少有一层中有4个或以上的结点,因此树的高度最多是n-3。

本题的答案为A 。

2.度为4、高度为h 的树_____________.A.至少有h+3个结点B.最多有4h -1个结点C.最多有4h 个结点D.至少有h+4个结点答:与上小题分析相同,本题的答案为A 。

3.对于一棵具有n 个结点、度为4的树来说,树的高度至少是_____________.A.)]2([log 4nB.)]13([log 4-nC.)]13([log 4+nD.)]12([log 4+n答:由树的性质4可知,具有n 个结点的m 次树的最小高度为)]1)1(([log +-m n m 。

这里m=4,因此最小高度为)]13([log 4+n 。

本题的答案为C 。

4.在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为_____________个。

A.4B.5C.6D.7答：3n =2，2n =1，1n =2，001235n n n n n n +=+++=，n=度之和+1=33n +22n +1n +1=11， 所以65110=-=n 。

本题的答案为C 。

5.若一棵有n 个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数 是_____________。

A.n(k 一1)/kB.n-kC.(n+1)/kD.(nk 一n+1)/k答:m=k,有k n n n +=0,度之和=n-1=k kn ,k n n k /)1(-=,所以0n =n-k n =n-(n-1)/k=(nk-n+1)/k.本题的答案为D 。

数据结构习题第六章 树和二叉树答案

数据结构习题第六章 树和二叉树答案

第六章树和二叉树注：参考答案只能作为参考，也是有错的，自己要学会辨别。

一、单项选择题1.A2.D3．A4．C5．B6．D7．E8. D9．C10．B11. C12．A13．D14．B15．C16．B17．D18．B19. D20．C二、判断题（在各题后填写“√”或“×”）1. 完全二叉树一定存在度为1的结点。

×2. 对于有N个结点的二叉树，其高度为log2n。

×3. 二叉树的遍历只是为了在应用中找到一种线性次序。

√4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。

×5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

×6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列√7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。

√8. 二叉树只能用二叉链表表示。

×9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。

√10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。

×11．树形结构中元素之间存在一个对多个的关系。

√12．将一棵树转成二叉树，根结点没有左子树。

×13．度为二的树就是二叉树。

×14.二叉树中序线索化后，不存在空指针域。

×15．霍夫曼树的结点个数不能是偶数。

√16．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

√三、填空题1．p->lchild==null && p->rchlid==null2.(1)2k-1 (2)2k-13．644. 2n n-1 n+15．先序遍历后序遍历中序遍历6．.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ⎣log2i⎦+1 7．48．任何结点至多只有右子女的二叉树。

数据结构树和二叉树习题

数据结构树和二叉树习题

数据结构树和二叉树习题一、树的基本概念1.请简要描述树的基本概念及其特点。

答：树是由n(n≥0)个节点组成的有限集合。

其中：-若n=0，则为空树。

-若n＞0，则树有且仅有一个称为根的节点，其他节点可以分为多个互不相交的有限集合，每个集合本身又是一棵树，称之为根的子树。

树的特点包括：-每个节点存放的数据可以是同种或不同种的数据类型。

-每个节点最多有一个父节点和多个子节点。

2.请列举树的应用场景。

答：树的应用场景包括但不限于以下几个方面：-文件系统：操作系统中的文件系统通常使用树来组织文件和目录。

-数据库：数据库中的索引通常使用树来存储和组织数据。

-编译原理：编译器使用语法树来解析源代码。

-社交网络：社交网络中的关注和粉丝关系可以表示为树。

二、二叉树3.请定义二叉树。

答：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

4.请画出以下二叉树的结构图：A/\BC/\/\DEFG答：以下是该二叉树的结构图：A/\BC/\/\DEFG5.请写出以下二叉树的前序遍历、中序遍历和后序遍历结果：/\23/\45答：-前序遍历结果：1,2,4,5,3-中序遍历结果：4,2,5,1,3-后序遍历结果：4,5,2,3,1三、二叉树的操作6.请实现二叉树的插入操作。

答：以下是二叉树的插入操作的示例代码：```class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef insert(root, value):if root is None:root = Node(value)else:if value < root.value:if root.left is None:root.left = Node(value)else:insert(root.left, value)else:if root.right is None:root.right = Node(value)else:insert(root.right, value)```7.请实现二叉树的查找操作。

数据结构练习题库与答案

数据结构练习题库与答案

数据结构练习题库与答案一、单选题（共100题，每题1分，共100分）1.树形结构是数据元素之间存在一种（）。

A、多对多关系B、多对一关系C、一对多关系D、一对一关系正确答案：C2.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。

若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。

A、23B、62C、21D、41正确答案：A3.对于一个无向图，下面( )种说法是正确的。

A、每个顶点的入度等于出度B、每个顶点的度等于其入度与出度之和C、每个顶点的入度为0D、每个顶点的出度为0正确答案：A4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( )A、120B、100C、108D、110正确答案：C5.哈夫曼树中度为1的结点个数为( )。

A、1B、2C、0D、不确定正确答案：C6.在有n个叶子结点的哈夫曼树中，其结点总数为（）。

A、2nB、不确定C、2n+1D、2n-1正确答案：D7.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A、101B、102C、99D、100正确答案：D8.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。

A、n-1-IB、n-IC、n+1-ID、不能确定正确答案：C9.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是( )。

A、m2B、m2+m3C、m3D、m1+m2正确答案：B10.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（）。

A、s->next=hs；hs=s；B、s->next=hs；hs=hs->next；C、hs->next=s；D、s->next=hs->next；hs->next=s；正确答案：A11.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A、数据元素的相邻地址表示B、数据元素在表中的序号表示C、数据元素的值表示D、指向后继元素的指针表示正确答案：D12.假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( ).A、f==0B、f+1==rD、r+1==f正确答案：C13.对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（）A、O(n+e)B、O(e)C、O（n）D、O(n2)正确答案：D14.排序算法中，不稳定的排序是（）。