数据结构课后小结.doc

小结第一章（1）数据结构就是研究数据的逻辑结构、存储结构和运算方法的学科。（2）数据的逻辑结构包括：集合、线性结构、树形结构、图形结构4种类型。（3）集合中不存在结构之间的关系；线性结构元素之间存在一对一的关系；树形结构元素之间存在一对多的关系；图形结构元素之间存在多对多的关系。具有一对多和多对多关系的结构又称为非线性结构。（4）数据的存储结构包括：顺序存储、链式存储、索引存储、散列存储4种。（5）顺序存储可以采用一维数组来存储；链式存储可以采用链表结构来存储；索引存储则在原有存储结构的基础上，附加建立一个存储表来实现，主要作用是为了提高数据的检索速度；而散列存储则是通过构造散列函数来确定数据存储地址或查找地址。（6）算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有有穷性、确定性、可行性、输入、输出等特性。（7）一个好的算法应该达到正确性、可读性、健壮性、高效性和低存储量等目标。（8）算法的效率常用时间复杂度与空间复杂度来评价，应该逐步掌握其基本分析方法。（9）通常把算法中包含简单操作次数的多少叫做算法的时间复杂度。一般只要大致计算出相应的数量级即可；一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。（10）一个算法的时间和空间复杂度越好，则算法的效益就越高。单元练习1一、判断题整理数据的逻辑结构与数据元素本身的内容和形式无关。一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。数据元素是数据的基本单位。从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。数据的存储结构是数据的逻辑结构的存储映像。数据的物理结构是指数据在计算机内实际的存储形式。数据的逻辑结构不是依赖于计算机的。算法是对解题方法和步骤的描述。二、填空题整理1、数据有逻辑结构和存储结构两种结构。2、数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。3、数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。4、树形结构和图形结构和称为非线性结构。5、在树形结构中，除了树根结点以外，其余每个结点只有1个前驱几点。6、在图形结构中，每个结点的前驱结点数和后驱结点数可以任意多个。7、数据的存储结构又叫物理结构。8、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。9、线性结构中的元素之间存在一对一的关系。10、树形结构中的元素之间存在一对多的关系。11、图形结构的元素之间存在多对多的关系。12、数据结构主要研究数据的逻辑结构、存储结构和算法3个方面的内容。13、数据结构被定义为(D,R)，其中D是数据的有限集合，R是D上的关系的有限集合。14、算法是一个有穷指令的集合。15、算法效率的度量可以分为事先估算和事后统计法。16、一个算法的时间复杂性是算法输入规模的函数。17、算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。18、若一个算法中的语句频度之和为T(n)=6n+3n(2logn),则算法的时间复杂度为O(n(2logn)。19、若一个算法中的语句频度之和为T(n)=3n+n(2logn)+n*n,则算法的时间复杂度为O(n*n)20、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对像以及它们之间的关系和运算的学科。三、选择题整理1、数据结构通常是研究数据的存储结构和逻辑结构及它们之间的相互联系。2、在逻辑上可以把数据结构分为线性结构和非线性结构。3、数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为顺序存储结构。4、非线性结构中的每个结点可能有多个直接前驱结点和多个直接后续结点。5、链式存储结构所占存储空间分两部分，一部分放结点的值，另一部分放表示结点间关系的指针。6、算法的计算量大小称为算法的时间复杂性。7、数据的基本单位是数据元素。8、每个结点只含有一个数据元素，所有存储结点相继存放在一个连续存储空间里，这种结构称为顺序存储结构。9、每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是链式存储。10、任何两个结点之间都没有逻辑关系是集合。11、在数据结构中，与所用的计算机无关的是逻辑结构。12、4种基本逻辑结构中，数据元素之间关系最弱的是集合。13、与数据元素本身的形式、内容、相对位置和个数无关的是数据的逻辑结构。14、每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是索引存储方式。15、算法能正确地实现预定功能的特性称为算法的正确性。16、算法在发生非法操作时可以作出相应处理的特性称为算法的健壮性。17、在O(1),O(n),O(2logn),O(n*n)中，时间复杂度中最坏的是O(n*n)18、for(i=0;in;i+) For(j=0;jprior-next=p-next。三、选择题整理1）在具有n个结点的单向链表中，实现遍历链表或求链表的第i个结点的操作，其算法的时间复杂度是O(n)。3）单向链表的存储密度小于1。（存储密度=结点数据占得存储位/整个结点实际分配的存储位 可知：顺序表的存储密度等于1，而链表的存储密度小于1。）4）已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为B+（i-1）m。5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为O(n)。6）设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是P-rear=1。7）两指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是P-next=Q。第三章（1）栈是一种运n算受限制的线性表，它只允许在栈顶进行插入和删除等操作。（2）栈的逻辑结构和线性表相同，数据元素之间存在一对一的关系，其主要特点是“后进先出”。（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。（4）重点掌握在顺序栈和链栈上实现的进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。（5）熟悉栈在计算机的软件设计中的各种应用，能灵活应用栈的基本原理解决一些综合性的应用问题。第四章（1）队列是一种操作受限制的线性表，一般队列只允许在队尾进行插入操作，在对头进行删除操作。（2）队列的逻辑结构和线性表也相同，数据元素之间存在一对一的关系，其主要特点是“先进先出”。（3）队列