1. 带权的连通无向图的最小代价生成树是唯一的（X）

　　只有权值不同时，其最小代价生成树才是唯一的

 

2.设有关键字n=2^h -1,构成二叉排序树,每个关键字查找的概率相等,查找成功的ASL最大是n — 错误

 

 

　　ASL是平均查找长度

　　若恰好构成的是满二叉树，设查找每个节点的概率是Pi( 1/n ), 

　　那么每个节点的查找长度 — 比较次数 —— 第0层节点(根节点)比较 1 次　　/　　第1层节点比较2次，有2个节点　　/　　第h - 1层节点比较h-1次，有2^h-1个节点

　　　　EX = (  1 * 2^0 + 2 * 2^1 + 3 * 2^2 + ..... + (log2n + 1) * 2^log2n   )  / n  != n

　　若不是满二叉树

　　　　考虑极端情况，形成一个左侧链（完全左斜）Pi = (1/n) 

　　　　EX = ( 1 * 1 + 2 * 1 + 3 + 4 +......+ n ) / n = ( n + 1) / 2

　　PS：我认为是考虑此树为完全二叉树的情况

 

3. 设一棵m叉树中度数为0的结点数为N₀ ，度数为1的结点数为N_l ，……，度数为m的结点数为Nm，则N₀?

　　m叉树中树杈（指针）总数为 N1 + 2N2 + ...... + mNm (1)

　　又因为其总的节点数为 N0 + N1 + ...... + Nm (2)

　　其指针数又等于 总节点数 - 1 (因为根节点无指针指向 — 只考虑来自父节点的指针) 为 N0 + N1 + ...... + Nm - 1 (3)

　　(1) = (3) 得 N0 = 1 + N2 + 2N3 + ...... + (m-1)Nm

 

4.先序序列为a,b,c,d的不同二叉树的个数是 卡特兰数 （ 2n! ）/ ( ( n+1! ) * ( n! ) )

 

　　根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：

 

　　前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。

　　因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a,b,c,d为入栈次序，则出栈序列的个数为？”

　　对于n个不同元素进栈，即为栈混洗 — 满足卡特兰数