2-1
下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是: (2分)
后序遍历 dbca
所以 d前驱动为null,d后继b
b没有左孩子,前驱为d。
C没有孩子,前驱为b,后继为a
a有左右孩子
所以选B
作者: DS课程组
单位: 浙江大学
2-2
引人线索二叉树的目的的是( )。 (2分)
- 加快查找结点的前驱或后继的速度
- 为了能在二叉树中方便地进行插人与侧除
- 为了能方便地找到双亲
- 使二叉树的遍历结果唯一
线索树就是根据前驱后继生成的能不选A吗?
作者: 王俊玲
单位: 集美大学
2-3
若X是后序线索二叉树中的叶结点,且X存在左兄弟结点Y,则X的右线索指向的是( )。 (2分)
- X的父结点
- 以Y为根的子树的最左下结点
- X的左兄弟结点Y
- 以Y为根的子树的最右下结点
作者: 王东
单位: 贵州师范学院
左前驱,右后继,后序遍历,是左右中,X为右,所以他的后继是中,选A
2-4
已知字符集{ a, b, c, d, e, f },若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 },则对应字符集中各字符的哈夫曼编码可能是:(2分)
- 00, 1011, 01, 1010, 11, 100
- 00, 100, 110, 000, 0010, 01
- 10, 1011, 11, 0011, 00, 010
- 0011, 10, 11, 0010, 01, 000
作者: 考研真题
单位: 浙江大学
画图,就是A
2-5
对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是:(2分)
- 56
- 57
- 58
- 60
作者: 考研真题
单位: 浙江大学
n=(115+1)/2=58 选C
2-6
将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是: (2分)
- 父子关系; 2. 兄弟关系; 3. u的父结点与v的父结点是兄弟关系
- 只有2
- 1和2
- 1和3
- 1、2和3
作者: DS课程组
单位: 浙江大学
选B,3说的不是很清楚,语境是 森林中 u的父节点 与V的父节点是兄弟关系。不对。但是在二叉树中是对的。只能说这题太坑了。
2-7
对于一个有N个结点、K条边的森林,共有几棵树? (2分)
- N−K
- N−K+1
- N−K−1
- 不能确定
作者: DS课程组
单位: 浙江大学
每个边涉及两个节点,只有根不消耗边,有几个根,有几个树,说以树==根==N-K选A
2-8
设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M1,M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是: (2分)
- M1
- M1+M2
- M2+M3
- M3
作者: DS课程组
单位: 浙江大学
左子树应该是M1,那么右子树只能是M2+M3选C
2-9
由若干个二叉树组成的森林F中,叶结点总个数为N,度为2的结点总个数为M,则该集合中二叉树的个数为: (2分)
- M−N
- N−M
- N−M−1
- 无法确定
作者: DS课程组
单位: 浙江大学
节点只有度为2和为3两种,一颗树中,度为2个数比叶子节点少一。
所以二叉树个数为N-M选B
2-10
若森林F有15条边、25个结点,则F包含树的个数是:(2分)
- 8
- 9
- 10
- 11
作者: DS课程组
单位: 浙江大学
25-15=10选C
2-11
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历,则得到的一种顶点序列为:(2分)
- V1,V5,V4,V7,V6,V2,V3
- V1,V2,V3,V4,V7,V6,V5
- V1,V5,V4,V7,V6,V3,V2
- V1,V5,V6,V4,V7,V2,V3
作者: 陈越
单位: 浙江大学
深度,所以V1了V5就跳到V5从V5后面找依次类推选C
2-12
下列选项中,不是下图深度优先搜索序列的是:(2分)
- V1, V5, V4, V3, V2
- V1, V3, V2, V5, V4
- V1, V2, V5, V4, V3
- V1, V2, V3, V4, V5
作者: DS课程组
单位: 浙江大学
D V2到V3不是深度优先
2-13
给定无向带权图如下,以下哪个是从顶点 a 出发深度优先搜索遍历该图的顶点序列(多个顶点可以选择时按字母序)? (2分)
- abecdfhg
- abcdehgf
- abcdefgh
- abchgfde
3C是,自己走一下就知道了
作者: 魏宝刚
单位: 浙江大学
2-14
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则下列说法中不正确的是: (2分)
- G肯定不是完全图
- G中一定有回路
- G一定不是连通图
- G有2个连通分量
作者: DS课程组
单位: 浙江大学
走两次说明没通,路回路不回路不知道,选B
2-15
给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历,则得到的一种顶点序列为: (2分)
- V1,V2,V3,V4,V5
- V1,V2,V3,V5,V4
- V1,V3,V2,V4,V5
- V1,V4,V3,V5,V2
作者: DS课程组
单位: 浙江大学
广度,所以先走第一行,213 代表 V1 V3 V2 V4最后V5选C
2-16
已知一个图的邻接矩阵如下,则从顶点V1出发按广度优先搜索法进行遍历,可能得到的一种顶点序列为: (2分)
- V1,V2,V3,V5,V4,V6
- V1,V2,V4,V5,V6,V3
- V1,V3,V5,V2,V4,V6
- V1,V3,V5,V6,V4,V2
作者: DS课程组
单位: 浙江大学
自己走一下,选A
2-17
图的广度优先遍历类似于二叉树的:(2分)
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
作者: 陈越
单位: 浙江大学
广度是一层一层走,所以选D
2-18
给定有权无向图的邻接矩阵如下,其最小生成树的总权重是: (2分)
- 10
- 11
- 12
- 14
作者: DS课程组
单位: 浙江大学
自己找一下,是14 选D
2-19
给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:(2分)
- 20
- 22
- 8
- 15
作者: 陈越
单位: 浙江大学
8自己画图选C
2-20
给定有权无向图如下。关于其最小生成树,下列哪句是对的? (2分)
- 最小生成树不唯一,其总权重为23
- 最小生成树唯一,其总权重为20
- 边(B, F)一定在树中,树的总权重为23
- 边(H, G)一定在树中,树的总权重为20