2020第13-15周练习

  • Post author:
  • Post category:其他


2-1

下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是:

A.

在这里插入图片描述

B.

在这里插入图片描述

C.

在这里插入图片描述

D.

在这里插入图片描述



B,该二叉树的后序遍历为dbac,。先判断节点是否有左右孩子,如果没有,就会有箭头指出,指向的规则是左前右后,比如:d左右孩子都没有,左前右后,d没有前驱,左箭头指NULL,后继为b,右箭头指向b,;b没有左孩子,左箭头指向b的前驱d, ac同理,故B

2-2

引人线索二叉树的目的的是( )。

A.加快查找结点的前驱或后继的速度

B.为了能在二叉树中方便地进行插人与侧除

C.为了能方便地找到双亲

D.使二叉树的遍历结果唯一



A书上概念:引人线索二叉树的目的的是加快查找结点的前驱或后继的速度

2-3

若X是后序线索二叉树中的叶结点,且X存在左兄弟结点Y,则X的右线索指向的是( )。

A.X的父结点

B.以Y为根的子树的最左下结点

C.X的左兄弟结点Y

D.以Y为根的子树的最右下结点



A。后序遍历:XY根,Y的后继是Y的父节点也就是X的根,所以右线索指向X的根

2-4

已知字符集{ a, b, c, d, e, f },若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 },则对应字符集中各字符的哈夫曼编码可能是:

A.00, 1011, 01, 1010, 11, 100

B.00, 100, 110, 000, 0010, 01

C.10, 1011, 11, 0011, 00, 010

D.0011, 10, 11, 0010, 01, 000



A画出哈夫曼树,如下图


在这里插入图片描述

2-5

对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是:

(2分)

A.56

B.57

C.58

D.60



C节点数/2+1

2-6

将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是:

父子关系; 2. 兄弟关系; 3. u的父结点与v的父结点是兄弟关系

(2分)

A.只有2

B.1和2

C.1和3

D.1、2和3



B

2-7

对于一个有N个结点、K条边的森林,共有几棵树?

A.N−K

B.N−K+1

C.N−K−1

D.不能确定



A如果不看根节点的话,每条边都连着一个儿子,所以一棵树中 节点数=边数+1;在森林中判断几棵树,只要判断有几个根节点就行了,也就是N-K;

2-8

设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M​1​​ ,M​2 和M​3​​ 。则与森林F对应的二叉树根结点的右子树上的结点个数是:

(2分)

A.M​1

​​

B.M​1​​ +M​2

​​

C.M​2​​ +M​3

​​

D.M​3

​​



C。森林转化为二叉树的步骤:

(1)把每棵树转换为二叉树。

(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。

所以森林二叉树的右子树就是第二、三棵树,节点个数也就是M2+M3

2-9

由若干个二叉树组成的森林F中,叶结点总个数为N,度为2的结点总个数为M,则该集合中二叉树的个数为:

(2分)

A.M−N

B.N−M

C.N−M−1

D.无法确定



B。一棵二叉树中N0=N2+1,所以森林中有几个1就有几棵树,即N-M;

2-10

若森林F有15条边、25个结点,则F包含树的个数是:

A.8

B.9

C.10

D.11



C,解析见2-7。25-15=10

2-11

给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历,则得到的一种顶点序列为:

(2分)

A.V1,V5,V4,V7,V6,V2,V3

B.V1,V2,V3,V4,V7,V6,V5

C.V1,V5,V4,V7,V6,V3,V2

D.V1,V5,V6,V4,V7,V2,V3



C,按照表中的顺序来就行了,注意是深度优先。

2-12

下列选项中,不是下图深度优先搜索序列的是:

在这里插入图片描述

A.V​1​​ , V​5​​ , V​4​​ , V​3​​ , V​2

B.V​1​​ , V​3​​ , V​2​​ , V​5​​ , V​4

C.V​1​ , V​2​​ , V5​​ , V​4​​ , V​3

D.V​1​​ , V​2​​ , V​3​​ , V​4​​ , V​5

​​



D

2-13

给定无向带权图如下,以下哪个是从顶点 a 出发深度优先搜索遍历该图的顶点序列(多个顶点可以选择时按字母序)?(2分)

在这里插入图片描述

A.abecdfhg

B.abcdehgf

C.abcdefgh

D.abchgfde



C


2-14

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则下列说法中不正确的是:

A.G肯定不是完全图

B.G中一定有回路

C.G一定不是连通图

D.G有2个连通分量



B,跟是否有回路无关,根连通分量个数有关


2-15

给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历,则得到的一种顶点序列为:

在这里插入图片描述

A.V1,V2,V3,V4,V5

B.V1,V2,V3,V5,V4

C.V1,V3,V2,V4,V5

D.V1,V4,V3,V5,V2



C注意按照图中给的顺序来就OK了

2-16

已知一个图的邻接矩阵如下,则从顶点V1出发按广度优先搜索法进行遍历,可能得到的一种顶点序列为:

(2分)

在这里插入图片描述

A.V1,V2,V3,V5,V4,V6

B.V1,V2,V4,V5,V6,V3

C.V1,V3,V5,V2,V4,V6

D.V1,V3,V5,V6,V4,V2



A


2-17

图的广度优先遍历类似于二叉树的:

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历



D

2-18

给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:

A.10

B.11

C.12

D.14



D

2-19

给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:

(2分)

A.20

B.22

C.8

D.15



C

2-20

给定有权无向图如下。关于其最小生成树,下列哪句是对的?

在这里插入图片描述

A.最小生成树不唯一,其总权重为23

B.最小生成树唯一,其总权重为20

C.边(B, F)一定在树中,树的总权重为23

D.边(H, G)一定在树中,树的总权重为20



A



版权声明:本文为weixin_46014378原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。