数据结构学习指导12章

《数据结构学习指导12章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第一、二章学习指导第一章绪论1、数据结构课程的主要研究内容？P32、基本概念及术语：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型等；p4-63、各类数据的逻辑结构的特点，元素间的关系：线性结构：一对一；树型结构：一对多；图结构：多对多；4、数据结构的分类：从逻辑结构上可以把数据结构分为两大类：线性、非线性；分成三大类：线性、树、图；5、什么是算法？算法有哪5大基本特性？P136、评价一个算法主要是分析哪两大指标（时间复杂度、空间复杂度）？7、算法时间复杂度的计算方法？相关习题、例题、课件8、不同

2、算法时间复杂度效率高低排序？第二章线性表1、线性结构的特点：有且仅有一个称为第一个的数据元素；有且仅有一个称为最后一个的数据元素；除第一个元素外其余元素有且仅有一个直接前驱；除最后一个元素外，其余元素有且仅有一个直接后继。2、线性表的存储结构有哪两大类？3、顺序表中元素地址的计算？会用地址计算公式计算数组（向量）中任一元素的地址；4、算法设计：顺序表的插入、删除、定位、删除顺序表中的重复元素等，及相应算法的分析评价；5、单链表中头指针、头结点、始结点概念上的区别？带头结点与不带头结点的单链表的判空条件？6、单链表的相关运算：单链表的创建、

3、输出、查找、插入、删除等；7、顺序存储结构与链式存储结构优劣比较？基本习题一、填空1、某算法的主要语句如下：for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;则该算法的时间复杂度为___O(n*n)_______。2、某算法的主要语句如下：i=1;while(i<=n){x=x+1;i++;}则该算法的时间复杂度为__O(n)________。3、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的关系和运算的学科。4、在数据结构中，从逻辑上可以把数据分成_____线性结构___和非线性

4、结构____________。5、数据的逻辑结构是数据元素之间逻辑关系的整体。6、算法的执行时间是问题规模的函数。7、一个向量中第一个元素的存储地址是200，每个元素的长度为4，则第5个元素的地址为_216______。8、建立一个有n个有值结点的单链表的算法的时间复杂度是____O（n）________。9、对于一个栈，给定的输入项为a，b，c，则所有可能的输出序列有_abc_____,_acb______,_bac______,_bca________,_cba________。10、在一个有n个数据元素的顺序表中删除第i个元素(1<

5、=i<=n)，需向前移动____n-i________个数据元素。11、单链表是通过___指针_________记录数据元素间的逻辑位置关系的。12、线性表中除第一个元素外，其余元素有且仅有一个__直接前驱_____；除最后一个元素外，其余元素有且仅有一个__直接后继_____。二、判断1、线性表采用链表存储结构时，结点和结点内部的存储空间可以是不连续的。（错）2、顺序存储结构的优点时存储密度高求插入、删除运算效率高。（错）3、数据项是数据的最小单位。（对）4、链表是一种可随机存取的存储结构。（错）5、程序与算法的重要区别之一在于程序不一

6、定要满足有穷性。（对）6、采用顺序存储结构存储的线性表适于进行元素的插入及删除运算。（错）三、选择1、在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A．存储结构B．存储实现C．逻辑结构D．运算实现3、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据

7、元素所包含的数据项的个数要相等4、以下说法正确的是（）。A．数据元素是数据的最小单位数据项B．数据项是数据的基本单位数据元素C．数据结构是带有结构的各数据项的集合数据对象D．一些表面上很不相同的数据可以有相同的逻辑结构5、以下与数据的存储结构无关的术语是（）。A．顺序队列B.链表C.有序表D.链栈6、以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈7、在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。A、逻辑结构B、顺序存储C、链式存储D、以上都对8、一个存储结点存储了一个（）。A、数据项B、数据元

8、素C、数据结构D、数据类型9、在数据结构中与所使用的计算机无关的是（）。A、逻辑结构B、存储结构C、物理结构D、逻辑结构和存储结构10、以下哪一因素不会影响到算法的运行时间（）。A、硬件的速度