数据结构知识点归纳

一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。数据结构的章节比重大致为：1.概论:概念，时间复杂度。2.线性表:基础章节，必考内容之一。概念，算法设计题。3.栈和队列:基本概念。4.串:基本概念。5.多维数组及广义表:基本概念。6.树和二叉树:重点难点章节，各校必考章节。概念，问答，算法设计题。7.图:重点难点章节，各校必考章节。概念，问答，算法设计题。8.查找:重点难点章节，概念，问答。9.排序:重点难点章节，问答各种排序算法的排序过程二、各章节的主要内容：第一章概述主要内容：本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点:（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;}7．下列算法的时间复杂度是_____。for(i=0;im;i++)for(j=0;jn;j++)a[i][j]=i；8．下列算法的时间复杂度是______。i=s=0;while(sn){i++;s+=i;}判断题：1、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（）2、顺序存储方式优点是存储密度大，且插入和删除运算效率高。（）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）第二章线性表主要内容：作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。线性表一章注意以下几个方面:（1）.线性表的相关基本概念，如:前驱、后继、表长、空表、首元结点，头结点，头指针等概念。（2）线性表的结构特点，主要是指:除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。（3）线性表的顺序存储方式及基本运算（插入、删除操作、平均移动次数、时间复杂度）。（4）线性表的链式存储方式及基本运算（单链表插入、删除，求长度操作、平均移动次数、时间复杂度）。（5）顺序存储和链式存储的特点，不同之处。（6）线性表的简单算法题参考题目：一、选择题：1、线性表是（）A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空2、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。A．nB．n/2C．n/3D．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=SB．P-next=S-next;S-next=P；C．P-next=P;P-next=S；D．P-next=S;S-next=P；6、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）7、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（）。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个位置上插入一个数据元素需要移动表中（）个数据元素，删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）。在顺序表中插入一个元素，需要平均移动（）元素，删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关，插入\删除操作的时间复杂度均为()。9、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:（）。10．设指针变量p指向单链表中结点A的前驱结点，若删除单链表中结点A，则执行操作（）三、算法设计：1.设计算法，计算顺序表中数据元素为x的元素个数。顺序表结构如下：typedefstruct{intdata[100];intlength;}sqlist;函数首部为：intcount(sqlistL,intx)2．设计算法，在顺序线性表中，删除顺序表中第i个元素，顺序表结构同上题。函数首部为：intdel(sqlist*L,inti)3．设计算法，在顺序线性表中，删除值为x的元素。函数首部为：voiddelx(sqlist*L,intx)4.对给定的单链表L(元素各不相同)，编写一个删除L中值为x的结点的算法。链式结构如下：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;intdelx(LinkList*head,intx)5.编写算法求带头结点的单链表的表长,结构同上题。intcount(LinkList*head)第三章栈与队列主要内容：栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。栈和队列一章注意以下几个方面:（1）栈的定义及其相关数据结构的概念：合法的出栈序列、出栈序列个数、顺序栈，链栈（2）队列的定义及其相关数据结构的概念，包括:循环队列。（3）栈和队列的特点：栈---后进先出；队列—先进先出。（4）递归算法概念。栈与递归的关系，所有的递归算法都可以借助栈将递归转向于非递归算法。（5）操作：顺序栈的进栈、出栈操作。循环队列的队空、队满条件，出队、入队、求队列元素个数操作。参考题目：1.循环队列是空队列的条件是（）A．Q.rear==Q.frontB．（Q.rear+1）%maxsize==Q.frontC．Q.rear==0D．Q.front==02.链栈与顺序栈相比，比较明显的优点是（）A．通常不会出现栈满的情况B．通常不会出现栈空的情况C．插入操作更加方便D．删除操作更加方便3.若一个栈的输入序列是1,2,3，……，n，输出序列的第一个元素是ｎ，则第ｉ个输出元素是（）A．n-iB．n–i+1C．iD．不确定4.对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（）A．1，2，3B．3，2，1C．3，1，2D．2，1，35.栈是限定在（）处进行插入或删除操作的线性表。A．端点B．栈底C．栈顶D．中间6.当循环队列q是满队列时，存放队列元素的数组data有n个元素，则data中存放（）个数据元素。A．nB.n-1C.n-2D.07.循环队列用数组elem[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。8．栈的特点是，队列的特点是。9.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是____。10．若用一个大小为6的一维数组来实现循环队列，当前rear和front的值分别是0和3，从队列中删除一个元素，再加入两个元素后，当前队列中共个元素，rear的值为_____，front的值为_____。第四章串主要内容：最容易自学的章节之一本章注意：（1）串的基本概念：串（串是其元素均为字符型数据的特殊线性表），子串、空串与空格串的区别，串相等的条件、模式匹配。（2）串的定长顺序存储（3）串的基本操作功能，如求串长,串连接，串替换等，给出一个字符串能够写出操作的结果。参考题目：1．串是一种特殊的线性表，其特殊性体现在()。2．S1=“ABCD”，S2=“CD”则S2在S1中的位置是（）3．假设S=“abcaabcaaabca”，T=“bca”，Index(S,T,3)的结果是（6）4．设有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))的结果是______。5．在串中，SubString(“student”,5,2)的结果是________。4．假设S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace(S,T,V)结果是_____。7．两个串相等的充分必要条件是______且____。8.子串的定位操作通常称为。第五章数组与广义表主要内容：（1）多维数组中某数组元素的存储位置求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。（2）明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。（3）稀疏矩阵的压缩存储概念，三元组表和十字链表存储。（4）广义表的概念，理解广义表的递归特性，特别应该明确表头与表尾的定义。（5）广义表的存储特性---难以用顺序存储结构存储。能画出头尾表示法（6）广义表的操作GetHead和GetTail，给出一个广义表能够写出取表头和取表尾操作的结果。参考题目：1.常对数组进行的两种基本操作是()。A.建立与删除B.索引和修改C.对数据元素的存取和修改D.查找与索引2.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为()。A.SA+141B.SA+144C.SA+222D.SA+2253.对稀疏矩阵进行压缩存储目的是___。4．已知广义表：A=(a,b),B=(A,A),C=(a,(b,A),B)，则tail(head(tail(C)))运算的结果为________。5．求下列广义表操作的结果：(1)GetTail[GetHead[((a,b),(c,d))]]=_______(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]=________第六章树与二叉树主要内容：从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。总体来说，树一章的知