《数据结构》课程教学资源（知识点）数据结构各章重点难点

第一章 绪论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;0(n)(2)for (int i=0;i<n;i++)for (int j=ij<n;j++)

第一章 绪论 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;0(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);结果:4524 6479 8 16 8

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); 结果：45 24 64 79 8 16 8

注：这种题型注意书写格式，如果题目要求是“请写出下列程序段执行完后的线性表”则答案为“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)。(注：注意书写格式)301245687a605642387425data6207next44、课后习题：所有选择、填空题和简答题第三章栈和队列1、栈的定义与基本操作运算：（建立栈、入栈、出栈、取栈顶元素等）注意顺序栈、链栈的指针变化

注：这种题型注意书写格式，如果题目要求是“请写出下列程序段执行 完后的线性表”，则答案为“La=(45,24,64,79,8,16,8)” 2、在顺序存储和链接存储结构下的线性表的插入、删除和单链表求长 度函数的实现。（教材主要函数必须理解） 顺序存储： 判空：L.length==0 判满：L.length==L.listsize 链接存储： 判空：HL==NULL 3、几种特殊的单链表：数组存储单链表，附加表头结点单链表，循环 链表。 例 2.2：在下列数组 a 中链接着一个线性表，表头指针为 a[0].next，则该线性表为 (38,56,25,60,42,74) 。(注：注意书写格式) a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 4、课后习题：所有选择、填空题和简答题 第三章 栈和队列 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 (IStackEmpty(a)cout<<pop(a)<<"“;结果：50241752、顺序存储和链接存储的出栈和入栈算法及相应的时间复杂度α1）顺序存储：判空：S.top==-1判满：S.top==StackMaxSize-1链接存储：判空：HS==NULL3、中缀算术表达式和后缀算术表达式的转化，及后缀算术表达式的求值。例4.2：将下列中缀算术表达式转化为后缀算术表达式，并求值。3+4/（25-（6+15））*8@

例 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)<<” “; 结果：50 24 17 5 2、顺序存储和链接存储的出栈和入栈算法，及相应的时间复杂度 O（1）。 顺序存储： 判空：S.top==-1 判满：S.top==StackMaxSize-1 链接存储： 判空：HS==NULL 3、中缀算术表达式和后缀算术表达式的转化，及后缀算术表达式的求 值。 例 4.2：将下列中缀算术表达式转化为后缀算术表达式，并求 值。 3+4/（25-（6+15））*8 @

答案：3425615+-/8*+@值为11注：若表达式后有“@”符号，则转化后在表达式后也加上“@”"4、队列的定义与基本操作运算：（建立队列、入队、出队、循环队列等），注意队列头、尾指针变化例4.3：请写出下列程序段执行后的结果。InitQueue(q1);InitQueue(q2);inta[]=[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);1while (!QueueEmpty(q1)&&!QueueEmpty(q2))cout<<Qdelete(q1)<<”"<<Qdelete(q2)<<endl;结果：413467069245、顺序存储和链接存储的出队和入队算法

答案： 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; 结果：41 34 67 0 69 24 5、顺序存储和链接存储的出队和入队算法

顺序存储：判空：Q.front==Q.rear判满：Q.front==(Q.rear+1)%QueueMaxSize队首元素：Q.queue[(Q.front+1%QueueMaxSize链接存储：判空：HQ.front==NULL或HQ.rear==NULI队首元素：HQ.front->data6、课后习题：所有选择、填空题、简答题第四章：串基本概念：串、子串、空串、串长度、串相等、子串在主串中位置存储结构：定长顺序存储、堆分配存储、块链存储及各自特点2块运算函数：求子串、串连接、求串长、串比较、子串位置及串赋值3、串的特殊性（与线性表比较）、串应用中的特点（下标定位）5课后习题：所有选择、填空、简答题第五章稀疏矩阵和广义表1、求数组元素的存储位置（行序、列序），特殊矩阵压缩存储到一维数组中的方法。稀疏矩阵的三元组线性表表示，转置矩阵的三元组线性表表示及转置矩阵算法时间复杂度为O(n*t)

顺序存储： 判空：Q.front==Q.rear 判满：Q.front==(Q.rear+1)%QueueMaxSize 队首元素：Q.queue[(Q.front+1)%QueueMaxSize] 链接存储： 判空：HQ.front==NULL 或 HQ.rear==NULL 队首元素：HQ.front->data 6、 课后习题：所有选择、填空题、简答题 第四章：串 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)(cd))22()B=(a,(b,(c,d)),(e))33()C=((ar(b,(),c)r((d),e))）144、课后习题：所有选择、填空题和计算题第六章树和二叉树1、树的基本概念及广义表表示：

例 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，树的度为32、树和二叉树的性质：例5.2：一棵深度为5的满二叉树中的结点数为31_个，一棵深度为3的满四叉树中的结点数为21 个。3、二叉树的先序、中序、后序和按层遍历。例5.3：假定一棵二叉树广义表表示为A（B（，D（G）），C（E，F））分别写出对它进行先序、中序、后序和按层遍历的结果先序:ABDGCEF中序BGDAECF后序:Ｇ D B Ｅ ＦＣ A按层:ABCDEFG例5.4：根据下述遍历，画出对应二叉树。先序:ABDEGHCFIJ中序:DBGEHACIFJ答案:A(B(D,(E(G,H))),C(,E(I,J)))4、求二叉树深度算法的时间复杂度为：O（log2n）二叉树的应用部分1、二叉线索树定义及建立：P1332、二叉树查找的递归和非递归算法及时间复杂度O（log2n）。3、二叉树与树、森林的遍历与转换3、二叉链表的定义及存储结构及树的孩子一一兄弟表示法

例 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、二叉线索树定义及建立：P133 2、二叉树查找的递归和非递归算法及时间复杂度 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出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。答案 :DFs——a b f h 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<<’‘;

5、哈夫曼树：根据一组数据构造哈夫曼树，并求出带权路径长度 WPL。 6、 课后习题：所有选择、填空题，简答题 第七章 图 1、图的存储结构：邻接矩阵、邻接表。求出度、入度 2、图的深度优先搜索遍历 DFS 和广度优先搜索遍历 BFS。 例 7.1：已知一个有向图的顶点集 V 和边集 G 分别为： V={a，b，c，d，e，f，g，h}； E={,,,,,,,,,}； 假定该图采用邻接矩阵表示，则分别写出从顶点 a 出发进行深度优先搜 索遍历和广度优先搜索遍历得到的顶点序列。 答案： DFS——a b f h c d g e BFS——a b c f d e h g 3、区别图的深度优先搜索遍历和广度优先搜索遍历算法。 注： （1）数据类型为 adjmatrix ——邻接矩阵 （2）数据类型为 adjlist ——邻接 表 （3）程序较长，有队列 ——广度优 先搜索遍历 例 7.2： void AI(adjmatrix GA , int i , int n) { cout<<i<<’ ‘;

visited[] =true;for (intj=0;j<n;j++)if (GA[i]j]!=O &&GA[i][j]!=MaxValue&&!visited[j])AI(GAj, n);1该算法的功能为丛初始点V出发深度优先搜索由邻接矩阵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算法从Vo出发，画出最小生成树，并写出依次得到的各条边及最后的边集数组，并求出最小生成树的权值。答案：08（1）最小生成树：2520

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); } 该算法的功能为：从初始点 Vi 出发深度优先搜索由邻接矩阵 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 20