数据结构知识点归纳

、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。对于绝大多数的学校而言，''外排，文件，动态存储分配〃三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。数据结构的章节比重大致为：概论：概念，时间复杂度。线性表:基础章节，必考内容之一。概念，算法设计题。栈和队列:基本概念。串：基本概念。多维数组及广义表：基本概念。树和二叉树：重点难点章节，各校必考章节。概念，问答，算法设计题。图:重点难点章节，各校必考章节。概念，问答，算法设计题。查找：重点难点章节，概念，问答。排序：重点难点章节，问答各种排序算法的排序过程二、各章节的主要内容：第一章概述主要内容：本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点（1） 数据结构的基本概念。（数据；数据元素；数据项；数据结构；数据的逻辑结构：线性和非线性，具体分为集合、线性结构、树形结构和图状结构；数据的存储结构：顺序存储和链式存储；运算）（2） 算法的度量：时间效率和空间效率，分别用时间复杂度和空间复杂度度量，掌握时间复杂度的度量方法量方法。（大O表示法）参考题目填空题：1、 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（）和（ ）。2、 数据结构按逻辑结构可分为两大类，它们分别是（）和（）3、 数据的物理结构主要包括（ ）和（ ）两种情况。4、线性表，栈，队列和二叉树四种数据结构中（ ）是非线性结构，（ ）是线性结构。5、线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在（ ）关系。6、程序段的时间复杂度是。for（i=1;i<=n;i++）{k++;for(j=1;j<=n;j++)x=x+k;}下列算法的时间复杂度是。for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i；下列算法的时间复杂度是i=s=0;while(s<n){i++;s+=i;}判断题：TOC\o"1-5"\h\z1、 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ）2、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （）第二章线性表主要内容：作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。线性表一章注意以下几个方面：（1） .线性表的相关基本概念，如:前驱、后继、表长、空表、首元结点，头结点，头指针等概念。（2） 线性表的结构特点，主要是指:除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。（3） 线性表的顺序存储方式及基本运算（插入、删除操作、平均移动次数、时间复杂度）。（4） 线性表的链式存储方式及基本运算（单链表插入、删除，求长度操作平均移动次数、时间复杂度）。（5） 顺序存储和链式存储的特点，不同之处。（6） 线性表的简单算法题参考题目一、选择题：1、线性表是（ ）一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空 D.一个无限序列，不能为空2、 在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。n B.n/2C.n/3 D.n/43、 链表不具有的特点是（）。A.随机访问 B.不必事先估计存储空间C-插入删除时不需移动元素 D.所需的空间与线性表成正比4、 带头结点的单链表head为空的判定条件是（ ）A.head=NULL； B.head->next=NULL； C.head->next=head；D.head!=NULL；5、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ）A.S->next=P->next;P->next=S B.P->next=S->next;S->next=P；C.P->next=P;P->next=S； D.P->next=S;S->next=P；6、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为()A.O(l) B.O(log2n) C.O(n) D.O(n2)7、 在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入，结点，则执行的操作是()。A.s—〉next=p—〉next;p—〉next=s; B.q->next=s;s->next=p;C.p—〉next=s—〉next;s—〉next=p; D.p—〉next=s;s—〉next=q;8、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中( )个数据元素，TOC\o"1-5"\h\z删除第i个元素(lWiWn)时，需向前移动的元素的个数是()。在顺序表中插入一个元素，需要平均移动( )元素，删除一个元素，需要平均移动( )元素，具体移动的元素个数与( )有关，插入\删除操作的时间复杂度均为( )。9、 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句：( )。10.设指针变量p指向单链表中结点A的前驱结点，若删除单链表中结点A，则执行操作()三、算法设计：设计算法，计算顺序表中数据元素为x的元素个数。顺序表结构如下：typedefstruct{intdata[100];intlength;}sqlist;函数首部为：intcount(sqlistL,intx)2.设计算法，在顺序线性表中，删除顺序表中第i个元素，顺序表结构同上题。函数首部为：intdel(sqlist*L,inti)2.设计算法，在顺序线性表中，删除值为x的元素。函数首部为：voiddelx(sqlist*L,intx)对给定的单链表L(元素各不相同)，编写一个删除L中值为x的结点的算法。链式结构如下：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;intdelx(LinkList*head,intx)编写算法求带头结点的单链表的表长,结构同上题。intcount(LinkList*head)第三章栈与队列主要内容：栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。栈和队列一章注意以下几个方面：（1） 栈的定义及其相关数据结构的概念：合法的出栈序列、出栈序列个数、顺序栈，链栈（2） 队列的定义及其相关数据结构的概念，包括:循环队列。（3） 栈和队列的特点：栈---后进先出；队列一先进先出。（4） 递归算法概念。栈与递归的关系，所有的递归算法都可以借助栈将递归转向于非递归算法。（5） 操作：顺序栈的进栈、出栈操作。循环队列的队空、队满条件，出队、入队、求队列元素个数操作。参考题目循环队列是空队列的条件是（）A.Q.rear==Q.frontB.（Q.rear+1）%maxsize==Q.frontC.Q.rear==0D.Q.front==0链栈与顺序栈相比，比较明显的优点是（ ）A.通常不会出现栈满的情况 B.通常不会出现栈空的情况C-插入操作更加方便 D.删除操作更加方便若一个栈的输入序列是1,2,3,……，n，输出序列的第一个元素是n，则第i个输出元素是（ ）A.n-iB.n-i+1C.i D.不确定对于一个栈，给定输入序列为1，2,3,则下列不可能为输出序列的是（）A.1，2，3 B.3，2，1 C.3，1，2 D.2，1，3栈是限定在（）处进行插入或删除操作的线性表。A.端点 B.栈底 C•栈顶 D.中间当循环队列q是满队列时，存放队列元素的数组data有n个元素，则data中存放（ ）个数据元素。A.n B.n-1 C.n-2 D.0循环队列用数组elem[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。栈的特点是 ，队列的特点是。设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该。若用一个大小为6的一维数组来实现循环队列，当前rear和front的值分别是0和3,从队列中删除一个元素，再加入两个元素后，当前队列中共 个元素，rear的值为，front的值为。第四章串主要内容：最容易自学的章节之一本章注意：（1） 串的基本概念：串（串是其元素均为字符型数据的特殊线性表），子串、空串与空格串的区别，串相等的条件、模式匹配。（2） 串的定长顺序存储（3） 串的基本操作功能，如求串长,串连接，串替换等，给出一个字符串能够写出操作的结果。参考题目串是一种特殊的线性表，其特殊性体现在( )。S1=“ABCD”，S2=“CD”则S2在S1中的位置是( )假设S="abcaabcaaabca”，T="bca”，Index(S,T,3)的结果是(6)设有S1=‘ABCDEFG’，S2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(S,i,j)返回串S的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是。在串中，SubString(“student”，5,2)的结果是 。假设S="abcaabcaaabca"，T="bca"，V="x"，Replace(S,T,V结果是。两个串相等的充分必要条件是且。子串的定位操作通常称为 。第五章数组与广义表主要内容：多维数组中某数组元素的存储位置求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。稀疏矩阵的压缩存储概念，三元组表和十字链表存储。广义表的概念，理解广义表的递归特性，特别应该明确表头与表尾的定义。广义表的存储特性---难以用顺序存储结构存储。能画出头尾表示法广义表的操作GetHead和GetTail，给出一个广义表能够写出取表头和取表尾操作的结果。参考题目TOC\o"1-5"\h\z常对数组进行的两种基本操作是( )。A.建立与删除B.索引和修改C.对数据元素的存取和修改 D.查找与索引二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7]⑷的起始地址为( )。A.SA+141B.SA+144C.SA+222D.SA+225对稀疏矩阵进行压缩存储目的是 。已知广义表：A=(a,b),B=(A,A),C=(a,(b,A),B)，贝Utail(head(tail(C)))运算的结果为。求下列广义表操作的结果：GetTail[GetHead[((a,b),(c,d))]]=GetTail[GetHead[GetTail[((a,b),(c,d))]]]=第六章树与二叉树主要内容：从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。总体来说，树一章的知识点包括：二叉树的概念、性质(性质非常重要)二叉树的存储结构(顺序存储和二叉链表存储)（3） 二叉树遍历的三种算法（①给二叉树能写出遍历序列，根据遍历序列可以构造二叉树；②遍历递归算法（二叉树的其他算法很多都是在遍历的基础上得到的）、在三种基本遍历算法的基础上实现二叉树的其它算法（如求叶子结点、总结点、高度等，仔细揣摩求解思路）（4） 线索二叉树的概念。（利用二叉链表存储时的空链域指向前驱和后继，空链域个数；给出一棵二叉树能画出对应的线索二叉树，如P149—图6.16）（5）树、森林的概念，树与森林的遍历算法（给出树或森林，能写出其要求的遍历序列）树和森林的遍历算法与二叉树遍历算法的联系。（6） 树与森林和二叉树的相互转换。（7）最优二叉树的概念，哈夫曼树的概念，特点（只有0和2的结点），能够按指定权值建立哈夫曼树，给出哈夫曼编码，计算WPL。树一章，处处是重点，道道是考题，大家务必个个过关。参考题目1、 在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（ ）A.2i B.不存在C.2i+1 D.Li/2J2、下列陈述中正确的（ ）二叉树是度为2的有序树二叉树中结点只有一个孩子时无左右之分二叉树中必有度为2的结点二叉树中最多只有两棵子树，并且有左右之分TOC\o"1-5"\h\z3、 以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（ ）A.2n-1 B.n-1C.n+1 D.2n+14、 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）A.99 B.98 C.50 D.485、 在一棵具有五层的满二叉树中，结点总数为（ ）A.31 B.32 C.33 D.166、深度为k的完全二叉树中最少有（）个结点。A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-17、三个结点可以构成（ ）种不同形状的二叉树。A.1 B.2 C.3 D.58、 树中所有结点的度之和等于所有结点数加（ ）。A.0 B.1 C.-1 D.29、含有10个结点的二叉树中，度为0的结点数为4,则度为2的结点数为（），度为1的结点数为（）A.3 B.4 C.5 D.610、 有m个叶结点的哈夫曼树所具有的结点数为（ ）A.mB.m+1C.2mD.2m-1填空：若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的节点数。设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有个结点。若前序遍历二叉树的结果为序列A、B、C，则有棵不同的二叉树可以得到这一结果。线索二叉树的左线索指向其，右线索指向其 。已知完全二叉树T的第5层只有7个结点，则该树共有个叶子结点。简答：已知一棵二叉树的先序遍历序列EFHIGJK，中序遍历序列为HFIEJGK，构造该二叉树，写出后序序列。已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树，写出后序序列。已知一棵二叉树的后序序列“cdbgfea”,中序序列“cbdaegf”，请画出该二叉树，写出先序序列。根据后序序列“cedbhjigfa”和中序序列“cbedahgijf”构建二叉树，并给出其先序序列。假设用于通信的电文字符集为{ABCDE},各字母出现次数分别为{29576}，现需求这些字母的最优编码，计算huffman树的带权路径长度。假设用于通信的电文由8个字母a,b,c,d,e,f,g组成，其频率分别为W={5,2,9,11,8,3,7}，试构造相应的哈夫曼树，给出每个字母的haffman编码，并计算它的带权路径长度。三、算法设计：编写算法求二叉树中叶子结点的数目。数据结构定义为：typedefstructNode{intdata;structNode*Lchild;structNode*Rchild;}BiTNode,*BiTree;函数首部为：intleaf（BiTree*root）利用二叉树遍历算法求二叉树的高度，假设根结点的高度为1.intDepth（BiTree*root）以二叉链表为存储结构写出求二叉树结点总数的算法。第六章图主要内容：如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。图这一章的特点是:概念繁多，与离散数学中图的概念联系紧密，算法复杂，考研时极易被考到，且容易出大题，如果不考查树与图两章的知识，几乎是不可想像的。主要知识点如下：（1） 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量、生成树等概念。与这些概念相联系的相关计算题也应该掌握（如：有向（无向）完全图边的条数、生成树的边的条数等）。（2） 图的存储形式：只看邻接矩阵和（逆）邻接表（3） 图的两种遍历算法:深度遍历和广度遍历，能够画出任意一幅图的深度优先搜索生成树和广度优先搜索生成树。（4） 生成树、最小生成树的概念以及最小生成树的构造RIM算法和KRUSKAL算法。考查时，一般不要求写出算法源码，而是要求根据Prim算法、Kruskal算法构造该图的最小生成树，画出其构造过程及最终生成的最小生成树。以下内容考研很重要（5） 拓扑排序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。要求按指定图，写出拓扑排序序列。（6） 关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面:一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。关键路径问题是工程进度控制的重要方法，具有很强的实用性。要求对指定图，写出关键路径。（7）最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种:一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。注意区分。参考题目1、 在一个具有n个结点的无向图中，要连通全部结点至少需要（ ）A.n条边 B.n+1条边C.n-1条边 D.n/2条边2、 最小生成树指的是（）由连通图所得到的边数最少的生成树由连通图所得到的顶点相对较少的生成树连通图的所有生成树中权值之和最小的生成树连通图的极小连通子图3、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）A.1/2倍B.1倍C.2倍 D.4倍4、有n个结点的无向图的边数最多为（ ）A.n+1B.n（n-1）/2C.n（n+1） D.2n（n+1）5、 若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（ ）A.一般矩阵B.对称矩阵 C.对角矩阵 D.稀疏矩阵6、 下列算法中，算法用来求图中每对顶点之间的最短路径。A.DijkstraB.FloyedC.Prim D.Kruskal7、 最小生成树的构造可使用（A）。A.prim算法 B.冒泡算法C.迪杰斯特拉算法 D.哈夫曼算法8、 有8个结点的有向完全图有（C）条边。A.14 B.28 C.56 D.1129、 已知有向图G=（V,E）,其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ ）。A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7CVVVVVVV DVVVVVVV.▼i^vo, , , , , . ,'c,,,,,r1345267 125346/i V_z i V_z 10、 设无向图G中的边的集合E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为。11、有N个顶点组成的无向连通图，最多可以有 条边。简答题：给出下图中从a出发的深度优先遍历序列和广度优先遍历序列

求下图的最小生成树，要求分别用prim算法和kruskal算法，prim算法从定点1出发。画出最小生成树的生成过程。求下图的最小生成树，要求分别用prim算法和kruskal算法，prim算法从定点a出发。画出最小生成树的生成过程。已知图G如下所示，列出图G的邻接表，写出拓扑排序序列（写出一种即可），求出关键路径。已知图G如下所示，列出图G的邻接表，写出拓扑排序序列（写出一种即可），求出关键路径。第七章查找主要内容:在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。现实生活中，search几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间。在DS的教材中，一般将search分为三类:1在顺序表上的查找；2在树表上的查找；3在哈希表上的查找。本次复习这一章的知识时，要掌握以下内容：（1） 关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；（2） 线性表上的查找：顺序查找和二分查找及其比较次数。（3） 基本哈希表的查找算法：参考题目TOC\o"1-5"\h\z1、顺序查找法适合于存储结构为 的线性表。（ ）A.散列存储 B.顺序存储或链接存储C.压缩存储 D.索引存储2、 在查找过程中，若同时还要做增、删工作，这种查找则称为（ ）A.静态查找 B.动态查找 C.内查找D.外查找3、 对线性表进行二分查找时，要求线性表必须（ ）A.以顺序方式存储 B.以顺序方式存储且兀素有序C.以链接方式存储 D.以链接方式存储且元素有序4、在有序表（12,24,36,48,60,72,84冲二分查找关键字72时所需进行的关键字比较次数为 。5、 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它将依次与表中元素 比较大小。简答题：1、已知散列函数为H（k）=kmod13，关键值序列为（19，01，23，14，55，20，84，27，68，11，10，77）处理冲突的方法为线性探测法，散列表长度为13（1） 构造哈希表（画示意图）；（2） 计算装填因子；（3） 计算查找成功情况下的平均查找长度；2.采用哈希函数H（k）=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,15,40,46,17,13,14,28,38（1） 构造哈希表（画示意图）；（2） 装填因子；（3） 等概率下成功的平均查找长度3.已知散列函数为H（k）