数据结构题目【刷题笔记】

糖逗

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）!/[n!*(n+1)!]
       

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,也即平均查找长度。