江苏师范大学数据结构总复习总结课件.ppt

《江苏师范大学数据结构总复习总结课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复习第一章绪论本章要点：（1）有关数据结构的基本概念，包括：数据、数据对象、数据元素或者数据成员、数据结构、数据类型等；数据抽象、抽象数据类型、数据结构的抽象层次等。（2）算法设计与分析：算法的定义和算法的特性算法的设计方法：包括问题解决的基本思路、算法设计的基本步骤、算法的实现算法的性能分析：包括算法的性能标准，算法的后期测试；算法的事情估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法1、顺序存储结构中数据元素间的逻辑结构是由（）来表示的，链接存储结构中数据元素间的逻辑关系是由（）表示。A指针B逻辑顺序C存储位置D问题上下文2、算法的时间复杂度

2、与（）有关。A问题规模B计算机硬件的运行速度C源程序的长度D编译后执行程序的质量3、某算法的时间复杂度为O(n2)，表明该算法（）A问题规模是n2B问题规模与n2成正比C执行时间等于n2D执行时间与n2成正比CAAD4、算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、（）、有穷和可行性等特性。5、算法效率的度量分为（）和（）。前者主要通过在算法的某些部位插装时间函数来测定算法完成某一个规定功能所需要的时间。而后者不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂度。6、程序所需要的存储空间包含两个部分（）和（）。前者

3、空间的大小与输入输出数据的个数多少，数值大小无关。后者空间主要包括其大小与问题规模有关的成分变量所占空间等等。确定性事后测量事前估计固定部分可变部分7、有实现同一功能的两个算法A1和A2，其中A1的渐进时间复杂度是，A2的渐进时间复杂度为。仅就时间复杂度而言，具体分析这两个算法哪个好。比较算法好坏，需要比较两个函数2n和n2当n=1时，21>12，算法A2好于A1当n=2时，22=22，算法A2与A1相当当n=3时，23<32，算法A1好于A2当n=4时，24>42，算法A2好于A1当n>4时，24>n2，算法A2好于A1当n→时，算法A2在时间上好于A1第二章线性

4、表本章要点：（1）线性表的定义和特点，包括：线性表的定义，注意几个关键词：有穷、序列、数据元素；线性表特点：唯一前驱和唯一后继。③线性表元素类型④线性表与向量（一维数组）的关系，注意它们间的异同⑤线性表的操作归类：包括访问操作（搜索，遍历）、维护操作（插入、删除），设置操作（初始化或者置空），判断操作（判空、判满）、游标操作（前驱、后继）第二章线性表本章要点：（2）线性表的顺序存储表示：顺序表的静态和动态的C结构定义，以及C++类定义顺序表的特点：即元素的逻辑顺序和物理顺序的一致性顺序表的主要操作，如插入、删除、搜索等的实现算法④掌握主要功能的关键语句：如遍

5、历整个顺序表、遍历到指定节点的语句；插入、删除时成片移动元素的语句等⑤掌握简单的效率分析，包括搜索算法中数据比较次数的计算，插入、删除的数据移动次数的计算第二章线性表本章要点：（3）线性表的链接存储表示：单链表的C结构定义，以及C++类定义单链表的特点：即元素的逻辑顺序和物理顺序的不一致性单链表的主要操作，如插入、删除、搜索等的实现算法。注意无附加头结点和带附加头结点的单链表上操作实现的差异④掌握主要功能的关键语句：如遍历整个顺序表、遍历到指定节点的语句；无头结点单链表的表头插入、删除；带头结点单链表的搜索操作；带头结点单链表的插入、删除运算以及单链表的创建、释

6、放、逆置、分裂、合并等运算⑤有序单链表的主要操作：如搜索、插入、删除等，以及分裂，合并，剔除重复元素等运算1、在下列关于线性表的叙述中正确的是（）A线性表的逻辑顺序和物理顺序总是一致的B线性表的顺序存储表示优于链式存储表示C线性表若采用链式存储表示时，所有存储单元的地址可连续或者可不连续D每种数据结构都应具备三种基本运算——插入、删除和查找2、若长度为n的非空线性表采用顺序存储结构，在表的i个位置插入一个数据元素，i的合法值应该是（）Ai>0B1<=i<=nC0<=i<=n-1D0<=i<=n3、对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应（）A将n个元

7、素从小到大排序B从线性表中删除第i个元素（1<=i<=n）C查找第i个元素（1<=i<=n）D在第i个元素（1<=i<=n）后插入一个新元素4、若长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）AO(n)BO(1)CO(n2)DO(log2n)5、已知L是带表头的单链表，L是表头指针，则摘除首元结点的语句是（）AL=L->linkBL->link=L->link->linkCL=L->link->linkDL->link=L6、已知单链表A长度为m，单链表B长度为n，若将B接在A的末尾，在没有链尾指针的情形下，算法的时间复杂度应为（）AO(