2020第13-15周练习

青旅半醒 2022-12-28 06:17 279阅读 0赞

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

A.  
![在这里插入图片描述][20201214224758435.png]

B.  
![在这里插入图片描述][20201214224807729.png]

C.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]

D.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 1]  
**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画出哈夫曼树，如下图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 2]

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出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：

![(2分)][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  
下列选项中，不是下图深度优先搜索序列的是：  
![在这里插入图片描述][20201214232405264.png]

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分)  
![在这里插入图片描述][2020121423242123.png]

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出发按广度优先搜索法进行遍历，则得到的一种顶点序列为：

![在这里插入图片描述][20201214232546818.png]

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分)  
![在这里插入图片描述][20201214232616301.png]

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  
给定有权无向图如下。关于其最小生成树，下列哪句是对的？  
![在这里插入图片描述][20201214232646823.png]

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

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

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

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

**A**

[20201214224758435.png]: /images/20221120/8041ee05570c4d60a899d05a62806e1c.png
[20201214224807729.png]: /images/20221120/9f332b62d98e4f6b8b231925e29acaa2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202012142248171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201214224828650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214230751773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA==,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20201214232041144.png
[20201214232405264.png]: https://img-blog.csdnimg.cn/20201214232405264.png
[2020121423242123.png]: https://img-blog.csdnimg.cn/2020121423242123.png
[20201214232546818.png]: https://img-blog.csdnimg.cn/20201214232546818.png
[20201214232616301.png]: https://img-blog.csdnimg.cn/20201214232616301.png
[20201214232646823.png]: https://img-blog.csdnimg.cn/20201214232646823.png