Question

数据结构的题 帮忙下 谢谢

1、具有n个节点的二叉树采用二叉链表存储结构 共有________个空指针域。
2、对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是____，判断任意两个顶点是否有边相连的方法是____,求任意顶点的度的方法是________。
3、无向图有m条边，则表示该无向图的邻接表中有____个节点。
4、二叉树排序树查找，在最坏的情况下，平均查找长度为____,最好的情况下，平均查找长度为__________。
5、n个元素表进行直接选择排序，所需要的关键字的比较次数为_______________。
6、由8个权值构造一颗哈夫曼树，该哈夫曼树有________个节点。

Answer 1

jaybestwang的答案都是对的，我只对其中几个作出解释。

1、根据二叉树性质，n0=n2+1，n0+n1+n2=n，联立这两个方程得到2n0+n1=n+1，而=左边恰好就是空指针域的个数。
3、无向图用邻接表表示时，每个顶点都会作为边的出点和入点各出现一次
4、在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。
在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。
5、直接选择排序的思路是：总共遍历n-1次，其中第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，所以第i次需要比较n-i次，总共需要(n-1)+(n-2)+...+(n-n+1)=n(n-1)/2次比较
6、哈夫曼树中没有度为1的结点，而且权值所在点必为叶子，所以根据n0=n2+1，n2=8-1=7，总共15个节点。

Answer 2

1. n+1
2. 邻接矩阵中1的个数除以2 A[i][j]是否为1 计算该行中1的个数
3. 2m
4. (n+1)/2 O(log(n))
5. n*(n-1)/2
6. 15