【HBU】数据结构月考2019-11选择题
- 2019 年 12 月 3 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/103315072
若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 }，中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？(2分)
- 这是一棵完全二叉树
- 2是1和3的父结点
- 这是一棵二叉搜索树
- 7是5的父结点
还原，这棵树不是完全二叉树
树最适合于用来表示 (2分)
- 有序数据元素
- 无序数据元素
- 元素之间无联系的数据
- 元素之间具有分支层次关系的数据
看图不觉得有层次吗？
在AOE网中，什么是关键路径？ (2分)
- 最短回路
- 最长回路
- 从第一个事件到最后一个事件的最短路径
- 从第一个事件到最后一个事件的最长路径
关键看他有多长，所以就是最长路径。
任何一个带权无向连通图的最小生成树—— (2分)
- 是唯一的
- 是不唯一的
- 有可能不唯一
- 有可能不存在
选的点不一样，根都不一样，肯定是不唯一啊
给定有向图的邻接矩阵如下：
顶点2（编号从0开始）的出度和入度分别是：(2分)
- 3, 1
- 1, 3
- 0, 2
- 2, 0
横着看是出度，都是 0 ，竖着看是入度，有俩，从0开始数，第二行，就是定点2作为起点的边。
设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ (2分)
- 0
- 2
- 4
- 5
节省了俩，画图看看。
5*1+4*2+2*3+1*3=22
4*2+2*2+5*2+1*2=24,差2
设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？ (2分)
- 4
- 6
- 8
- 10
先序遍历图示二叉树的结果为 (2分)
- A，B，C，D，H，E，I，F，G
- A，B，D，H，I，E，C，F，G
- H，D，I，B，E，A，F，C，G
- H，I，D，B，E，F，G，A，C
先序，A，然后左B，然后左D。选B
下图为一个AOV网，其可能的拓扑有序序列为： (2分)
- ACBDEF
- ABCEFD
- ABCDFE
- ABCEDF
作者: DS课程组
拓扑排序只输出没有入度的点，输出后删除点，从删除A开始
A选项，A B C 这时，D有入度，为ED，不对
B选项，A B C E 这时，F有入度 DF，不对
C选项，ABCD这时，F有入度，EF，不对
D选项，没问题。
我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？ (2分)
- Dijkstra算法 （最短路径）
- Kruskal算法 （Prim算法和Kruskal算法最小生成树的算法）
- 深度优先搜索（深度优先遍历算法和广度优先遍历算法 是图的遍历算法）
- 拓扑排序算法（回溯法是求解递归过程的一种重要方法）
