第11-12周练习题树与选择题

版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/103120660

2-1

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是： (2分)

后序遍历 dbca

所以 d前驱动为null，d后继b

b没有左孩子，前驱为d。

C没有孩子，前驱为b，后继为a

a有左右孩子

所以选B

作者: DS课程组

单位: 浙江大学

2-2

引人线索二叉树的目的的是（ ）。 (2分)

1. 加快查找结点的前驱或后继的速度
2. 为了能在二叉树中方便地进行插人与侧除
3. 为了能方便地找到双亲
4. 使二叉树的遍历结果唯一

线索树就是根据前驱后继生成的能不选A吗？

作者: 王俊玲

单位: 集美大学

2-3

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

1. X的父结点
2. 以Y为根的子树的最左下结点
3. X的左兄弟结点Y
4. 以Y为根的子树的最右下结点

作者: 王东

单位: 贵州师范学院

左前驱，右后继，后序遍历，是左右中，X为右，所以他的后继是中，选A

2-4

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

1. 00, 1011, 01, 1010, 11, 100
2. 00, 100, 110, 000, 0010, 01
3. 10, 1011, 11, 0011, 00, 010
4. 0011, 10, 11, 0010, 01, 000

作者: 考研真题

单位: 浙江大学

画图，就是A

2-5

对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是：(2分)

1. 56
2. 57
3. 58
4. 60

作者: 考研真题

单位: 浙江大学

n=（115+1）/2=58 选C

2-6

将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是： (2分)

1. 父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系
2. 只有2
3. 1和2
4. 1和3
5. 1、2和3

作者: DS课程组

单位: 浙江大学

选B，3说的不是很清楚，语境是 森林中 u的父节点 与V的父节点是兄弟关系。不对。但是在二叉树中是对的。只能说这题太坑了。

2-7

对于一个有N个结点、K条边的森林，共有几棵树？ (2分)

1. N−K
2. N−K+1
3. N−K−1
4. 不能确定

作者: DS课程组

单位: 浙江大学

每个边涉及两个节点，只有根不消耗边，有几个根，有几个树，说以树==根==N-K选A

2-8

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

1. M​1​​
2. M​1​​+M​2​​
3. M​2​​+M​3​​
4. M​3​​

作者: DS课程组

单位: 浙江大学

左子树应该是M1，那么右子树只能是M2+M3选C

2-9

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

1. M−N
2. N−M
3. N−M−1
4. 无法确定

作者: DS课程组

单位: 浙江大学

节点只有度为2和为3两种，一颗树中，度为2个数比叶子节点少一。

所以二叉树个数为N-M选B

2-10

若森林F有15条边、25个结点，则F包含树的个数是：(2分)

1. 8
2. 9
3. 10
4. 11

作者: DS课程组

单位: 浙江大学

25-15=10选C

2-11

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

1. V1,V5,V4,V7,V6,V2,V3
2. V1,V2,V3,V4,V7,V6,V5
3. V1,V5,V4,V7,V6,V3,V2
4. V1,V5,V6,V4,V7,V2,V3

作者: 陈越

单位: 浙江大学

深度，所以V1了V5就跳到V5从V5后面找依次类推选C

2-12

下列选项中，不是下图深度优先搜索序列的是：(2分)

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

作者: DS课程组

单位: 浙江大学

D V2到V3不是深度优先

2-13

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

6-7.JPG

1. abecdfhg
2. abcdehgf
3. abcdefgh
4. abchgfde

3C是，自己走一下就知道了

作者: 魏宝刚

单位: 浙江大学

2-14

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

1. G肯定不是完全图
2. G中一定有回路
3. G一定不是连通图
4. G有2个连通分量

作者: DS课程组

单位: 浙江大学

走两次说明没通，路回路不回路不知道，选B

2-15

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

1. V1,V2,V3,V4,V5
2. V1,V2,V3,V5,V4
3. V1,V3,V2,V4,V5
4. V1,V4,V3,V5,V2

作者: DS课程组

单位: 浙江大学

广度，所以先走第一行，213 代表 V1 V3 V2 V4最后V5选C

2-16

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

1. V1,V2,V3,V5,V4,V6
2. V1,V2,V4,V5,V6,V3
3. V1,V3,V5,V2,V4,V6
4. V1,V3,V5,V6,V4,V2

作者: DS课程组

单位: 浙江大学

自己走一下，选A

2-17

图的广度优先遍历类似于二叉树的：(2分)

1. 先序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历

作者: 陈越

单位: 浙江大学

广度是一层一层走，所以选D

2-18

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是： (2分)

1. 10
2. 11
3. 12
4. 14

作者: DS课程组

单位: 浙江大学

自己找一下，是14 选D

2-19

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：(2分)

1. 20
2. 22
3. 8
4. 15

作者: 陈越

单位: 浙江大学

8自己画图选C

2-20

给定有权无向图如下。关于其最小生成树，下列哪句是对的？ (2分)

1. 最小生成树不唯一，其总权重为23
2. 最小生成树唯一，其总权重为20
3. 边(B, F)一定在树中，树的总权重为23
4. 边(H, G)一定在树中，树的总权重为20

自己画图选A，不唯一是 EA EB都是4都可联通E