【HBU】2020树结构和图结构月测（选择题）

古城微笑少年丶 2022-12-29 06:37 76阅读 0赞

2-1  
我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？

(2分)

A.深度优先搜索

B.Kruskal算法

C.拓扑排序算法

D.Dijkstra算法

> D  
> A图的遍历算法；B构造最小生成树；C拓补排序

2-2  
下图为一个AOV网，其可能的拓扑有序序列为：  
![在这里插入图片描述][20201220204518418.png]

A.ABCEDF

B.ACBDEF

C.ABCDFE

D.ABCEFD

> A  
> 拓扑排序只输出没有入度的点，输出后删除点，从删除A开始。B选项，DE出错；C选项，DE出错；D选项FD出错

2-3  
任何一个带权无向连通图的最小生成树——

A.有可能不唯一

B.有可能不存在

C.是唯一的

D.是不唯一的

> A  
> 权值相同的路径不一定唯一

2-4  
先序遍历图示二叉树的结果为

![(2分)][2]

A.A，B，D，H，I，E，C，F，G

B.H，I，D，B，E，F，G，A，C

C.H，D，I，B，E，A，F，C，G

D.A，B，C，D，H，E，I，F，G

> A

2-5  
设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？

A.6

B.8

C.10

D.4

> B  
> ![树的入度之和为n0+n1+n2][n0_n1_n2]

2-6  
在AOE网中，什么是关键路径？

A.最短回路

B.最长回路

C.从第一个事件到最后一个事件的最短路径

D.从第一个事件到最后一个事件的最长路径

> D

2-7  
给定有向图的邻接矩阵如下：

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

顶点2（编号从0开始）的出度和入度分别是：

A.0, 2

B.2, 0

C.1, 3

D.3, 1

> A  
> 横为出度，纵为入度。不要弄反了

2-8  
设一段文本中包含4个对象\{a,b,c,d\}，其出现次数相应为\{4,2,5,1\}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？

A.0

B.5

C.4

D.2

> D  
> 不要忘了乘以次数![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]

2-9  
树最适合于用来表示

A.元素之间无联系的数据

B.有序数据元素

C.元素之间具有分支层次关系的数据

D.无序数据元素

> C

2-10  
若一棵二叉树的后序遍历序列是\{ 1, 3, 2, 6, 5, 7, 4 \}，中序遍历序列是\{ 1, 2, 3, 4, 5, 6, 7 \}，则下列哪句是错的？

A.2是1和3的父结点

B.7是5的父结点

C.这是一棵完全二叉树

D.这是一棵二叉搜索树

> C

[20201220204518418.png]: /images/20221120/8423b2ea56644d33ae36daf631df3aab.png
[2]: https://img-blog.csdnimg.cn/20201220205323308.png
[n0_n1_n2]: https://img-blog.csdnimg.cn/20201221173014705.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA==,size_16,color_FFFFFF,t_70
[20201220205645478.png]: https://img-blog.csdnimg.cn/20201220205645478.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201220210107225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAxNDM3OA==,size_16,color_FFFFFF,t_70