数据结构题目【刷题笔记】
本帖最后由 糖逗 于 2020-5-12 13:04 编辑1.一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度为2的节点个数是5，叶子节点个数为(44)
解答：度 节点数 边
4 6 24
3 10 30
2 5 10
1 x 0
边 = 节点数 -1
64=21+x-1
x=44
2.某二叉树有2000个节点，则该二叉树的最小高度为（11）
解答：树高为n的完美二叉树的节点有2**n-1.
3.若一序列进栈顺序为a1、a2、a3、a4，问存在多少种可能的出栈顺序（14）
解答：公式（2n）!/
4、把14、27、71、50、93、39按顺序插入一颗树，插入的过程不断调整使树为平衡排序二叉树，最终形成平衡排序二叉树的高度为（3）
解答：注意平衡二叉排序树要求任何节点的左右子树高度差不超过1.
5、 现在假设对N个元素的链表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）？（n+1）*n/2
解答：第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+...+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。
页:
[1]