1.各种排序算法的时间复杂度和空间复杂度分析
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
---|---|---|---|---|---|
冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9),R是基数(个十百) |
Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
详细分析见:http://www.cnblogs.com/heyonggang/p/3356930.html
2.满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
满二叉树的特点有:
3.完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
顺序存储结构一般只使用于完全二叉树。
完全二叉树的特点:
从这些特点可以得出一个判断是否是完全二叉树的方法:那就是看着树的示意图,心中默念给每个结点按照满二叉树的结构逐层顺序编号,如果编号出现空档,就说明不是完全二叉树,否则就是。
4.二叉树性质
性质1:在二叉树的第i层上至多有2i-1个结点。
性质2:深度为k的二叉树至多有2k - 1个结点(k≥1)。
性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 。
性质4:具有n个结点的完全二叉树的深度[log2n+1] ([x]表示不大于x的最大整数)。
性质5:如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层,每层从左到右),对任一结点i(1≤i≤n)有:
5.____的先序序列和后序序列正好相反。
A.二叉排序树 B.3个结点的二叉树 C.平衡二叉树 D.无右孩子的二叉树