第一章数据结构与算法
1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。
2.算法的有穷性是指算法程序的运行时间是有限的。
3.算法的时间复杂度：执行算法所需要的计算工作量（基本运算次数）。
算法的空间复杂度：这个算法所需要的内存空间。
两者之间没有必然直接的联系
4. 程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。
5.线性结构的两大条件：有且只有一个根节点；每一个结点最多只有一个前件，也最多有一个后件。
6. 线性表的顺序存储结构具备如下两个基本特征：
（１）线性表中的所有元素所占的存储空间是连续的；
（２）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
7. 栈是先进后出的线性表。
8. 队列是先进先出的线性表。
9.栈和队列都是线性结构。
10. 栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。
11. 循环队列中元素的个数是由队头指针和队尾指针共同决定。
12. 树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。
13. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。
14. 由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。
15. 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化。
16.循环队列是队列的一种顺序存储结构。
17. 循环链表和双向链表都是线性结构。
18. 线性链表中数据的插入和删除都不需要移动表中的元素，只需改变结点的指针域即可。
19. 线性链表中的各数据结点的存储空间可以不连续，各数据元素的存储顺序与逻辑顺序可以不一致。
20. 链式存储结构既可以针对线性结构也可以针对非线性结构。
21. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。
22. 线性表（线性结构）的链式存储结构所需要的存储空间一般要多于顺序存储结构。
23. 栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行。
24. 在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个。
25. 满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。26. 完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
27. 二叉树的遍历：
1．前序遍历：①访问根结点；②前序遍历左子树；③前序遍历右子树
2．中序遍历：①中序遍历左子树；②访问根结点；③中序遍历右子树
3．后序遍历：①后序遍历左子树；②后序遍历右子树；③访问根结点
28.一颗二叉树的前序遍历序列为ABDGCFK，中序遍历序为DGBAFCK，则结点的后序遍历序序列为什么？
后序应该是GDBFKCA。
中序：顺序为左根右。并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
29.顺序查找：最好情况：1次；最坏情况：n次；需要比较n/2次，复杂度为O(n)。
二分法查找：最坏情况：次；复杂度为
30.排序中：最坏情况
冒泡排序，简单插入排序，简单选择排序，选择排序的最坏情况时间都为
而堆排序的最坏情况时间为
冒泡排序，简单插入排序，简单选择排序，选择排序的最坏情况比较次数都为n(n-1)/2次
而堆排序的最坏情况次数为次