具有n个结点的二叉树中,一共有____[填空1]____个指针域,其中只有____[填空2]_
1、具有n个节点的二叉树采用二叉链表存储结构 共有________个空指针域。
2、对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是____，判断任意两个顶点是否有边相连的方法是____,求任意顶点的度的方法是________。
3、无向图有m条边，则表示该无向图的邻接表中有____个节点。
4、二叉树排序树查找，在最坏的情况下，平均查找长度为____,最好的情况下，平均查找长度为__________。
5、n个元素表进行直接选择排序，所需要的关键字的比较次数为_______________。
6、由8个权值构造一颗哈夫曼树，该哈夫曼树有________个节点。 展开
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个节点。
扩展资料：
二叉树的性质：
性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。
性质2：深度为h的二叉树中至多含有2h-1个节点。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1 。
性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。
最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。
参考资料来源：百度百科-二叉树
参考资料来源：百度百科-二叉排序树
参考资料来源：百度百科-直接选择排序
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
因为有n个节点，每个节点都存了一个lchild，一个rchild，所以共2n个指针域。除了根节点，其他所有的节点都存在自己的父节点，而父节点肯定存在指向其孩子的指针，所以有n-1个存了地址（根节点没有父节点，所以-1），因为总数是2n个所以NULL的就是2n-（n-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
