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中有三棵树,第一、第二、第三棵树的结点个数分别为M1 ,M2 和M3 。则与森林F对应的二叉树根结点的右子树上的结点个数是:
(2分)
A.M1
B.M1 +M2
C.M2 +M3
D.M3
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出发按深度优先搜索法进行遍历,则得到的一种顶点序列为:
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.V1 , V5 , V4 , V3 , V2
B.V1 , V3 , V2 , V5 , V4
C.V1 , V2 , V5 , V4 , V3
D.V1 , V2 , V3 , V4 , V5
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