《计算机二级考试知识点 数据结构与算法》思维导图

1、树的总结点数为树中所有结点的度数之和再加1。

2、二叉树的性质：度为0的结点（即叶子结点）总是比度为2的结点多一个。

3、循环链表采用链式存储结构。线性表链式存储结构的特点是，用一组不连续的存储单元存储线性表中的各个元素。线性链表的存储单元是任意的，即各数据结点的存储序号可以连续、也可不连续。

4、若循环队列的存储空间为(1：m)，在循环队列运转起来后，如果front<rear，则队列中的元素个数为rear-front;如果front>rear，则队列中的元素个数为rear-front+m。

5、设循环队列的存储空间为Q（1：m），当front=rear=m时，循环队列为空；当front=rear且不等于m时，循环队列可能为空，也可能为满。

6、二分查找：在最坏情况下，二分法查找需要比较log2n次。

7、双向链表有两个指针域，但属于线性结构。二叉树属于非线性结构，循环队列是队列的一种顺序存储结构。所有的线性结构都可以采用顺序存储结构。

8、当top=boton=NULL时，为栈空;当top=bottom且不等于NULL时，栈中存在一个元素，其他情况无法判断。

9、当front=rear=NULL时，为队空；当front=rear且不等于NULL时，队列中存在一个元素，其他情况无法判断。

10、最坏情况下时间复杂度:有序表的对分查找为O(log2n)，寻找最大项为0(n-1)，顺序查找为o(n)，堆排序为O(nlog2n)。

11、一个非空线性结构应满足两个条件:①有且只有一个根节点;②每个节点最多有一个前件，也最多有一个后件。

12、多重链表具有两个及两个以上的指针域，但多重链表既可以表示线性结构，也可以表示非线性结构。

13、数据的存储结构直接决定数据的输入，而这会影响算法所执行的基本运算次数，影响算法的效率。

14、算法的有穷性指算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成，即算法能在有限的时间内运行结束。

15、算法的时间复杂度是指执行算法所需要的计算工作量，算法空间复杂度指执行这个算法所需要的内存空间，算法的时间复杂度与空间复杂度没有直接关系。

16、如果额外空间量相对于问题规模（即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地(in place)工作的。

17、带链栈的栈底指针在栈空时值为null，在栈不为空时指向栈底结点，值为其的地址，有可能改变。

18、线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点：插入与删除运算效率高。