北京工业大学 数据结构 期末复习.ppt

《北京工业大学 数据结构 期末复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、考试题型单选：5题，共10分填空：5题，共10分简答题：5题，共45分算法阅读：15分算法设计：20分考试要求：闭卷第1章概论DS描述“按一定逻辑关系组织的数据元素的表示及相关操作数据逻辑结构：线性结构、树形结构和图形结构数据存储结构：顺序方法、链接方法、索引方法、散列方法抽象数据类型ADT算法4个特性：通用性、有效性、确定性、有穷性算法分析：T(n)、S(n)算法分析的相关概念；最差、最佳与平均情况的意义ADT的定义三元组表示ADT=(D,R,P)ADT抽象数据类型名{数据对象D:<数据对象的定义>数据关系R:<数据关系的定义>基本操作P:<基本操作的定义>}A

2、DT抽象数据类型名用C++类模板的声明表示ADT数据的抽象算法的抽象ADT定义类模板类模板代表一类类，不代表具体的类类模板的定义格式:template//类型参数Type,使用时用具体数据类型代替classclassName{private:TypedataList;…public:methodName();…};C++引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型声明、定义和使用C++类模板(2)类模板：描述了一组相关的类，它们只能通过类型来区分1、类模板声明：仅提供了类的名称和类的模板参数template

3、//类模板Array可接受任何类型作为参数classArray{Elem*data;intsize;//声明类模板Array的类数据public:Array(intsz);//函数成员intGetSize();};2、函数成员定义templateArray::Array(intsz){size=sz;data=newElem[size];}templateintArray::GetSize(){returnsize;}3、类模板的用法Arrayint_array(100);//Array

4、接收int作参数,//int_array为长100的int型数组对象常见上限g(n)的种类(用于比较各算法优劣)O(1)

5、度为m的单链表之后的算法时间复杂度为()。A.O(n)B.O(1)C.O(m)D.O(m+n)第2章线性表清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义存储形式：顺序存储结构、链式存储结构顺序存储结构的特点：1.逻辑结构与物理结构一致；2.属于随机存取方式缺点：插入删除元素需要移动，平均约一半的元素，限制了长度变化链式存储结构的特点：1.逻辑结构与物理结构不一致；2.属于顺序存取方式2.1.2线性表的存储结构逻辑结构存储空间的映射数据存储单元建立映射关系存储单元之间关系建立映射线性表2类存储结构顺序存储（定长的一维数组结构、向量型顺序存储

6、结构）为整个元素动态分配连续空间特点：逻辑相邻物理也相邻链式存储（变长的线性表存储结构）按需分配(插入:分配一个结点/删除:回收一结点)特点：逻辑相邻物理不一定相邻链表—单向、循环、双向不特殊说明，均带头结点(避免对空表的特殊处理)算法：（时间复杂性）在有序表中插入/删除结点给定元素位置，插入/删除相应结点注意：对循环链表操作时，尾部的判断双向链表的插入/删除结点删除结点一定要释放空间2.4线性表实现方法的比较顺序表优点存储紧凑（逻辑结构由存储相对位置体现，没使用指针，不用花费附加开销）随机访问（给定下标,常量时间可定位）链表优点不限定长度（无需事先了解线性表的长

7、度，允许线性表的长度有很大变化）不必移动，仅需改指针即可插删（能够适应经常插入删除内部元素的情况）适用不能确定长度上限、频繁插删：用链式存储结构按位置频繁进行读取、数据域占用空间小于指针域：用顺序存储结构有序的顺序表与无序的顺序表相比，其操作优势是（）。A.删除快B.插入快C.生成快D.查找快。若对线性表进行的主要操作是按下标存取，且很少插入和删除，则应该采用的存储结构是_____；若需要频繁地对线性表进行插入和删除时，则应该采用的存储结构是。题型举例第3章栈与队列栈与队列的定义、ADT定义及基本操作。栈的应用：会跟踪递归函数执行过程深度（纵向）周游表达式求值(中

8、缀后缀