第一章

　　第二章

　　第三章 队列

　　1、循环队列的判断队满的条件：(rear+1)%maxsize==front，判断对空的条件：rear==front

　　第四章

　　第五章 数组和广义表

　　1、压缩存储 稀疏矩阵的三元组存储方法

　　2、

　　第六章 树(存在一对多的关系)

　　1、数的存储结构分为：双亲表示法、孩子表示法、孩子兄弟表示法(二叉链表表示法)

　　2、树的链式存储结构，空指针域的个数为n(k-1)+1，其中n为节点数，k为度

　　3、深度为k完全二叉树结点数为2的k次方-1，n个结点的满二叉树深度为log2n+1取下限

　　4、中序遍历、前序遍历、后续遍历

　　5、给定一组权重值，构造哈夫曼树，哈夫曼树的高度不是唯一的，唯一的是权重之和

　　6、最小生成树(普里姆算法时间复杂度O(n2)，克鲁斯卡尔算法时间复杂度O(eloge) e为网边数

　　7、

　　第七章 图(存在多对多的关系)

　　1、广度优先遍历、深度优先遍历

　　2、图的存储结构：数组表示法、领接表、领接多重表、十字链表

　　第八章 动态存储管理

　　第九章 查找

　　1、查找分为：静态查找、动态查找

　　2、顺序表的查找：(1)顺序查找(假设每个记录的查找概率相等，当一定能查找成功时，平均查找长度为(n+1)/2;当加入查找不成功的因素后，平均查找长度为3(n+1)/4。

　　(2)折半查找的平均查找长度为log2(n+1)-1

　　(3)用顺序查找确定所在块，则分块查找的平均查找长度为(n/s+s)/2+1; 用折半查找确定所在块，则分块查找的平均查找长度为log2(n/s+1)+s/2，其中n为总长度，s为每一分块儿的长度。

　　(4)二叉排序树，查找长度最差情况(n+1)/2，最好情况与log2n成正比，平均为o(lg10)

　　(5)平衡二叉树，平均查找长度为o(lg10)

　　(6)哈希函数的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法;处理冲突的方法：开放地址法、再哈希法、链地址法、建立一个公共溢出区。

　　查找不成功的平均查找长度1/(1-a)，查找成功的平均查找长度-1/a*ln(1-a)

　　第十章 内部排序

　　1、直接插入排序、折半插入排序时间复杂度为O(n2)

　　2、冒泡排序时间复杂度为O(n2)

　　3、快速排序时间复杂度O(nlnn)、最坏情况O(n2)

　　4、树形选择排序时间复杂度O(nlnn)

　　5、堆排序(最坏情况下/平均)时间复杂度O(nlnn)

　　6、归并排序(最坏情况下/平均)时间复杂度O(nlnn)

　　7、排序分析：

　　(1)从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。

　　(2)上表中的“简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序为最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将它和其它的排序方法，诸如快速排序、归并排序等结合在一起使用。

　　(3)基数排序的时间复杂度也可写成O(d·n)。因此，它最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。

　　(4)从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n2)的简单排序法也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。一般来说，排序过程中的“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。值得提出的是，稳定性是由方法本身决定的，对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来。反之，对稳定的排序方法，总能找到一种不引起不稳定的描述形式。由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键宇进行，则应根据问题所需慎重选择排序方法及其描述算法。

　　第十一章 外部排序

　　1、 置换选择排序

　　第十二章 文件

　　1、 顺序文件

　　2、 索引文件

　　3、 ISAM文件和VSAM文件

　　4、 文件的操作有两类：检索和修改

　　5、 文件检索三种方式：顺序存取、直接存取、按关键字存取