第一章绪论1、数据结构是数据及其相互之间的联系。
2、数据结构按逻辑结构分类，可分为：集合、线性关系、树、图。
按存储结构分类，可分为：顺序、链接、索引、散列。
3、数据结构的二元组表示由数据元素的集合D和D上二元关系S所组成。
例1.1：D=（D，S），其中D={1,2,3,4,5,6}S={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4 ,6)}请画出对应的数据结构。
（这是图结构）注：在考试时可给出数据结构的二元组表示，做各种操作，如树、图的遍历，图的最小生成树或拓朴排序等。
4、时间复杂度和空间复杂度。
例1.2：请给出下列程序段的时间复杂度（S视为一个原操作）。
(1)for (int i=0;i<n;i++)S; O(n)(2)for (int i=0;i<n;i++)for (int j=i;j<n;j++)S; O(n2)例1.3：求(n2+nlog2n+1)/n的数量级是：O(n2)例1.4：结合具体的算法，求时间复杂度，如：顺序存储线性表，表元素插入的时间复杂度是：O(n)链接存储线性表，表结点插入的时间复杂度是：O(1)快速排序的时间复杂度是：O(n*log2n)5、课后习题：所有选择、填空题、计算题。
第二章线性表1、线性表的定义和抽象数据类型描述：（掌握函数的功能）例2.1：请写出下列程序段执行完后的结果。
InitList(La);int a[]={32,45,24,64,79,8,16};For (int i=0;i<7;i++)Insert(La,i,a[i]);Delete(La,a[3]/2);int x=GetElem(La,5);InsertRear(La,x);TraverseList(La);结果：452464798168注：这种题型注意书写格式，如果题目要求是“请写出下列程序段执行完后的线性表”，则答案为“La=(45,24,64,79,8,16,8)”2、在顺序存储和链接存储结构下的线性表的插入、删除和单链表求长度函数的实现。
（教材主要函数必须理解）顺序存储：判空：L.length==0判满：L.length==L.listsize链接存储：判空：HL==NULL3、几种特殊的单链表：数组存储单链表，附加表头结点单链表，循环链表。
例2.2：在下列数组a中链接着一个线性表，表头指针为a[0].next，则该线性表为 (38,56,25,60,42,74) 。
(注：注意书写格式) a012345678data605642387425next43762014、课后习题：所有选择、填空题和简答题第三章栈和队列1、栈的定义与基本操作运算：（建立栈、入栈、出栈、取栈顶元素等），注意顺序栈、链栈的指针变化例4.1：请写出下列程序段执行后的结果。
InitStack(a);int b[]={5,17,24,18,32,9};for (int i=0 ; i<4 ; i++)push(a,b[i]);int x=pop(a)+32;push(a,x);while (!StackEmpty(a))cout<<pop(a)<<”“;结果：50241752、顺序存储和链接存储的出栈和入栈算法，及相应的时间复杂度O（1）。
顺序存储：判空：S.top==-1判满：S.top==StackMaxSize-1链接存储：判空：HS==NULL3、中缀算术表达式和后缀算术表达式的转化，及后缀算术表达式的求值。
例4.2：将下列中缀算术表达式转化为后缀算术表达式，并求值。
3+4/（25-（6+15））*8 @答案： 3 4 25 6 15 + - / 8 * + @值为11注：若表达式后有“@”符号，则转化后在表达式后也加上“@”4、队列的定义与基本操作运算：（建立队列、入队、出队、循环队列等），注意队列头、尾指针变化例4.3：请写出下列程序段执行后的结果。
InitQueue(q1);InitQueue(q2);int a[]={41,67,34,0,69,24,78,58,62,64};for (int i=0 ; i<10 ; i++) {if (a[i]%2==1) QInsert(q1,x);else QInsert(q2,x);}while (!QueueEmpty(q1) && !QueueEmpty(q2))cout<<Qdelete(q1)<<”“<<Qdelete(q2)<<endl;结果：413467069245、顺序存储和链接存储的出队和入队算法。
顺序存储：判空：Q.front==Q.rear判满：Q.front==(Q.rear+1)%QueueMaxSize队首元素：Q.queue[(Q.front+1)%QueueMaxSize]链接存储：判空：HQ.front==NULL或HQ.rear==NULL队首元素：HQ.front->data6、课后习题：所有选择、填空题、简答题第四章：串1、基本概念：串、子串、空串、串长度、串相等、子串在主串中位置2、存储结构：定长顺序存储、堆分配存储、块链存储及各自特点3、块运算函数：求子串、串连接、求串长、串比较、子串位置及串赋值4、串的特殊性（与线性表比较）、串应用中的特点（下标定位）5、课后习题：所有选择、填空、简答题第五章稀疏矩阵和广义表1、求数组元素的存储位置（行序、列序），特殊矩阵压缩存储到一维数组中的方法。
2、稀疏矩阵的三元组线性表表示，转置矩阵的三元组线性表表示及转置矩阵算法时间复杂度为O(n*t)。
例3.1：请写出下列稀疏矩阵的三元组线性表表示及转置矩阵的三元组线性表表示。
答案：M =（（1,4,1）,（2,1,2）,（2,6,3）,（3,3,4）,（4,2,1）,（4,6,3）） M’ =（（1,2,1）,（2,4,1）,（3,3,4）,（4,1,1）,（6,2,3）,（6,4,3））3、求广义表的表头、表尾，长度和深度，及算法时间复杂度。
都是O(n)。
例3.2：请写出下列广义表的长度和深度。
长度深度（）A=（（a，b），（c，d）） 2 2（）B=（a，（b，（c，d）），（e）） 3 3（）C=（（a，（b，（），c），（（d），e）））1 4 4、课后习题：所有选择、填空题和计算题第六章树和二叉树1、树的基本概念及广义表表示：例5.1：一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中的结点数为 10 个，树的深度为 4 ，树的度为 3 。
2、树和二叉树的性质：例5.2：一棵深度为5的满二叉树中的结点数为 31 个，一棵深度为3的满四叉树中的结点数为 21 个。
3、二叉树的先序、中序、后序和按层遍历。
例5.3：假定一棵二叉树广义表表示为A（B（，D（G）），C（E，F）），分别写出对它进行先序、中序、后序和按层遍历的结果。
先序：A B D G C E F中序：B G D A E C F后序：G D B E F C A按层：A B C D E F G例5.4：根据下述遍历，画出对应二叉树。
、先序：A B D E G H C F I J中序：D B G E H A C I F J答案：A（B（D，（E（G，H））），C（，E（I，J）））4、求二叉树深度算法的时间复杂度为：O（log2n）二叉树的应用部分1、二叉线索树定义及建立：P1332、二叉树查找的递归和非递归算法及时间复杂度O（log2n）。
3、二叉树与树、森林的遍历与转换。
3、二叉链表的定义及存储结构及树的孩子——兄弟表示法5、哈夫曼树：根据一组数据构造哈夫曼树，并求出带权路径长度WPL。
6、课后习题：所有选择、填空题，简答题第七章图1、图的存储结构：邻接矩阵、邻接表。
求出度、入度2、图的深度优先搜索遍历DFS和广度优先搜索遍历BFS。
例7.1：已知一个有向图的顶点集V和边集G分别为：V={a，b，c，d，e，f，g，h}；E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>}；假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。
答案： DFS——a b f h c d g eBFS——a b c f d e h g3、区别图的深度优先搜索遍历和广度优先搜索遍历算法。
注：（1）数据类型为adjmatrix——邻接矩阵（2）数据类型为adjlist——邻接表（3）程序较长，有队列——广度优先搜索遍历例7.2：void AI(adjmatrix GA , int i , int n){cout<<i<<’‘;visited[i]=true;for (int j=0 ; j<n ; j++)if (GA[i][j]!=0 && GA[i][j]!=MaxValue&& !visited[j])AI(GA , j , n);}该算法的功能为：从初始点V i出发深度优先搜索由邻接矩阵GA所表示的图的递归算法。
4、图的最小生成树：Prim算法和Kruskal算法例7.3：已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7}E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9, (3,6)10,(4,6)4,(5,7)20}按照Prim算法从V0出发，画出最小生成树，并写出依次得到的各条边及最后的边集数组，并求出最小生成树的权值。
答案： 0 8 1 6 5（1）最小生成树：2 5 203 2 7106 4 4（2）依次得到的各条边：(0,3)2(0,2)5 (0,1)8(1,5)6 (3,6)10(6,4)4 (5,7)20（3）边集数组：0123456起点0001365终点3215647权值258610420（4）权为55例7.4：已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7}E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9, (3,6)10,(4,6)4,(5,7)20}按照克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
(0,3)2 ，(4,6)4 ，(0,2)5 ，(1,5)6 ，(0,1)8 ，(3,6)10 ，(5,7)20 5、DAG图的拓扑排序：例7.5：已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7，8}；E={ <0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4 ,8>,<5,7>,<6,7>,<7,8>}；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。