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

  1. 这是一棵完全二叉树

  2. 2是1和3的父结点

  3. 这是一棵二叉搜索树

  4. 7是5的父结点

还原，这棵树不是完全二叉树 

树最适合于用来表示 (2分)

  1. 有序数据元素

  2. 无序数据元素

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

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

看图不觉得有层次吗？

 

在AOE网中，什么是关键路径？ (2分)

  1. 最短回路

  2. 最长回路

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

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

 

关键看他有多长，所以就是最长路径。

 

 

任何一个带权无向连通图的最小生成树—— (2分)

  1. 是唯一的

  2. 是不唯一的

  3. 有可能不唯一

  4. 有可能不存在

选的点不一样，根都不一样，肯定是不唯一啊

 

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

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

  1. 3, 1

  2. 1, 3

  3. 0, 2

  4. 2, 0

横着看是出度，都是 0 ，竖着看是入度，有俩，从0开始数，第二行，就是定点2作为起点的边。

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

  1. 0

  2. 2

  3. 4

  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分)

  1. 4

  2. 6

  3. 8

  4. 10

先序遍历图示二叉树的结果为 (2分)

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

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

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

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

先序，A，然后左B，然后左D。选B

下图为一个AOV网，其可能的拓扑有序序列为： (2分)

  1. ACBDEF

  2. ABCEFD

  3. ABCDFE

  4. ABCEDF

作者: DS课程组

 

拓扑排序只输出没有入度的点，输出后删除点，从删除A开始

A选项，A B C 这时，D有入度，为ED，不对

B选项，A B C E 这时，F有入度 DF，不对

C选项，ABCD这时，F有入度，EF，不对

D选项，没问题。

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

  1. Dijkstra算法  （最短路径）

  2. Kruskal算法 （Prim算法和Kruskal算法最小生成树的算法）

  3. 深度优先搜索（深度优先遍历算法和广度优先遍历算法 是图的遍历算法）

  4. 拓扑排序算法（回溯法是求解递归过程的一种重要方法）