一、题型及分值：
1、填空题（本题10空，每空1分，共10分） 2、单项选择题(共15小题，每小题1分，共15分) 3、算法设计题（本题2小题，共15分 ） 4、简答题(本题2小题，共10分) 5、综合题（本题6小题，共50分）
二、复习及例题 Ch1 概论
1、数据结构的定义及分类
真实世界中的数据经过一定的加工，有效的存储在计算机中并在其上实现相应的运算。
数据结构包括三方面的内容：逻辑结构、物理结构及操作。
2、算法的概念、特点，算法分析（时间复杂度、空间复杂度）及算法分析的目的？ 例：分析以下程序段的时间复杂度 。
void func(int n) { int i=1;
while(i<=n) i=i+2; }
Ch2 线性表
1、什么是线性表？线性表的运算？
2、线性表的顺序存储与链式存储对完成线性表的运算有何不同？存储密度？随机访问？顺序访问？
例：在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）之前插入一个新元素的步骤及关键代码段。
例：带或（不带）头结点的单链表判断链表为空的标志。
例：在单链表中，若*p结点不是末尾结点，在其前或后插入或删除*s结点的步骤关键代码。 3、顺序表和链表的比较
例：顺序表和链表各自的优缺点？ 1.顺序表存储（典型的数组）
原理：顺序表存储是将数据元素放到一块连续的内存存储空间，相邻数据元素的存放地
址也相邻（逻辑与物理统一）。
优点：（1）空间利用率高。（局部性原理，连续存放，命中率高） （2）存取速度高效，通过下标来直接存储。
缺点：（1）插入和删除比较慢，比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序。
（2）不可以增长长度，有空间,当需要存取的元素个数可能多于顺序表的元素个数时,会出现\"溢出\"问题.当元素个数远少于预先分配的空间时,空间浪费巨大。 时间性能 :查找 O(1) ,插入和删除O（n）。 2.链表存储
原理：链表存储是在程序运行过程中动态的分配空间，只要存储器还有空间，就不会发生存储溢出问题，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点关系间的指针。 优点：（1）存取某个元素速度慢。
（2）插入和删除速度快，保留原有的物理顺序，比如：插入或者删除一个元素时，只需要改变指针指向即可。
（3）没有空间,存储元素的个数无上限,基本只与内存空间大小有关. 缺点：（1）占用额外的空间以存储指针(浪费空间，不连续存放，malloc开辟，空间碎片多)
（2）查找速度慢，因为查找时，需要循环链表访问，需要从开始节点一个一个节点去查找元素访问。
时间性能 :查找 O(n) ,插入和删除O（1）。 4、单链表操作编程：查找、插入、删除。
Ch3 栈与队列
1、基本概念
例：为什么说栈和队列是特殊的线性表？它们有何异同点？进出栈操作？进出队操作？引入循环队列的目的是什么？
逻辑结构和线性表相同，只是其运算规则较线性表有更多的。 例：设一个栈的入栈序列为A,B,C,D,则可能的出栈序列有哪些？ 2、一些状态判断
例：判定一个顺序栈ST（元素个数最多为StackSize）为空/满的条件。
例：判定一个循环队列Q（存放元素位置：0至QueueSize-1）队满的条件。 循环队列长度如何计算？
例：若用一个大小为6的数组来实现环形队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 。 3、栈的应用（如括号配对、回文判断） 4、递归：分析递归程序的运行结果。 例：void print(int w) { int i; if(w!=0)
{ for(i=1;i<=w;i++) printf(“%3d”,w); print(w-1);
printf(“\\n”); } }
调用语句print(3)的结果是什么？
Ch4串
1、串的基本概念及特点。
由零个或多个字符组成的优先序列。
2、串的基本运算，串的存储结构，串的模式匹配的概念及步骤。 3、串的简单操作的编程实现（如在串中查找给定字符）、求串的长度。
Ch5数组和广义表
1、数组的定义、数组的两种顺序存储方式：给定数组元素的大小及存储数组的起始地址，如何计算出其中某个数组元素的存储地址？
例：数组A[0..6][0..8]的每个元素占5个单元，将其按列优先次序存储在起始地址为2000的连续内存单元中，则元素a[5][5]的地址为 。
例：二维数组A[0..4][0..4]的元素起始地址是LOC(A[0][0])=4000，每个元素占2个字节，则按行优先次序存储时LOC(A[3][3])为多少？ 2、特殊矩阵的存储
3、稀疏矩阵的概念及两种存储方式
4、广义表的定义，如何求广义表的长度与深度？广义表的求表头/表尾运算。 例：对广义表(a,(B,A),(e,f))做表头运算和表尾运算的结果分别是什么？
Ch6树
1、树的定义：根结点、分支结点、叶子结点、树的度？结点的层数？树与森林？ 树是n个结点的具有层次关系的有限集合T
2、二叉树的定义；二叉树的性质（性质1—性质3）的运用；完全二叉树、满二叉树的概念。 例：深度为4的二叉树最多有多少个结点？
例：n个结点的二叉树中如果有m个叶结点，则一定有 个度为2的结点。
例：在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为 个。
3、树的存储方式：双亲表示法、孩子链表示法、孩子兄弟链表示法
二叉树的存储P92：根据存储画出二叉树、根据二叉树写出顺序/链式存储形式 4、二叉树的遍历：前序、中序、后序。
对给定二叉树写出遍历序列；对给定的两个遍历序列，画出二叉树并给出第三种遍历序列。 例：已知一棵二叉树的中序遍历序列为CBEDAHGIJF，后序遍历序列为CEDBHJIGFA，给出该二叉树树形表示，并写出其前序遍历的结点序列。 5、树（森林）与二叉树的相互转换
6、树的遍历：前/后序遍历；树的遍历结果与对等二叉树的遍历结果之间的对应关系。 7、线索二叉树的概念、结点结构，线索化的方法，如何在中序线索树中查找某结点的中序前趋/后继结点？
8、哈夫曼树的构造及编码、WPL计算
例：设给定权集W={2,3,4,6,8,11}，试构造关于W的一棵哈夫曼树，写出各数据的哈夫曼编码，并求其带权路径长度WPL。
Ch7图
1、基本概念：连通图、有向图、无向图、子图 2、图的存储（邻接矩阵/邻接表）及其特点。
例：一个有n个顶点的简单无/有向图最多有多少条边？ 例：在一个无向图中，所有顶点的度之和等于边数的多少倍？ 例：给定带权无向图G，画出该图的邻接矩阵/邻接表存储结构。 3、图的遍历：DFS、BFS
4、生成树与最小生成树
给出用普里姆prim/克鲁斯卡尔Kruskar算法构造最小生成树的过程。 5、单源最短路径：Dijkstra算法的执行过程。 6、拓扑排序
Ch8 排序
1、基本概念：什么是排序？排序的目的？什么是排序稳定性？ 2、各种排序算法的过程、效率及特点：
插入排序：直接插入、希尔插入 交换排序：冒泡排序、快速排序 选择排序：直接选择、堆排序 归并排序：
例：假设需对数据{54,28,16,34,73,62,95,60,26,43}进行排序，给出各种排序算法实现排序的过程，比较哪些是稳定的排序？哪些不是？若待排序的数据已经有序时，其中哪个排序花费的时间最少？哪个花费的时间最多？比较次数最少的是哪种？最多的又是哪种排序？ 3、掌握简单排序算法编程：直接插入、冒泡、直接选择。
Ch9 查找
1、几种查找算法（顺序、二分、分块、二叉排序树、散列）的过程及其特点。用ASL衡量查找算法效率（查找成功与失败）。
例：对给定关键字序列，构建一棵二叉排序树，并做中序遍历。
例：在一个有序表R[1..13]={1,3,9,12,32,41,45,62,75,77,82,95,100}，当用二分查找法查找值为82的结点时，经过 次比较后查找成功。
例：有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为 。
2、几种查找算法的比较及选择：顺序查找、二分（折半）查找（排列有序且顺序存储）、分块查找（块间有序块内无序，索引+顺序表）、二叉排序树、散列查找（既是存储方法也是查找方法，查找效率理想状态为O(1)且与查找表长度n无关，冲突不可避免但可解决） 例：在数据元素有序，元素个数较多而且固定不变的情况下，宜采用 查找方法。 3、哈希（散列表）查找：Hash函数？处理冲突的方法？
例：对于关键字序列{30,15,21,40,25,26,36,37}，若查找表长度为10，哈希函数为H(key)=key%7，采用线性探测法解决冲突：（1）画出哈希表；（2）计算查找成功和查找失败时的平均查找长度。
