北京工业大学数据结构期末深刻复习.ppt
《北京工业大学数据结构期末深刻复习.ppt》由会员分享,可在线阅读,更多相关《北京工业大学数据结构期末深刻复习.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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: ADT 抽象数据类型名 用C+类模板的声明
2、表示ADT,ADT定义类模板,类模板代表一类类,不代表具体的类 类模板的定义格式: template /类型参数Type,使用时用具体数据类型代替 class className private: Type dataList; public: methodName( ); ; C+引入模板概念,是想突出数据的逻辑结构而忽略其具体的数据类型,声明、定义和使用 C+类模板(2),类模板:描述了一组相关的类,它们只能通过类型来区分 1、类模板声明:仅提供了类的名称和类的模板参数 template /类模板 Array 可接受任何类型作为参数 class Array Elem* data; int s
3、ize; /声明类模板Array的类数据 public: Array( int sz ) ; /函数成员 int GetSize( ) ; ; 2、函数成员定义 template Array:Array( int sz ) size = sz; data = new Elemsize; template int Array:GetSize( ) return size; 3、类模板的用法 Array int_array(100); /Array接收int作参数, /int_array为长100的int型数组对象,常见上限g(n)的种类(用于比较各算法优劣),O(1)O(logn)O(n)O(n
4、logn)O(n2) 常数阶 对数 线性 对数乘积 平方 O(n3).O(2n)O(n!) 立方 指数 阶乘 常数:g(n) = 1 对数:g(n) = logn 线性增长: g(n) = n 二阶增长: g(n) = n2 g(n) = nlog(n), n = nlog(n)增长率 = n2 指数增长: g(n) = an,题型举例,算法指的是( )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法D. 解决问题的有限运算序列 将长度为 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 ( ) 。 A. O( n ) B. O( 1 ) C. O( m )D. O(
5、m + n ),第2章 线性表,清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义 存储形式:顺序存储结构、链式存储结构 顺序存储结构的特点: 1.逻辑结构与物理结构一致; 2.属于随机存取方式 缺点:插入删除元素需要移动,平均约一半的元素, 限制了长度变化 链式存储结构的特点: 1.逻辑结构与物理结构不一致; 2.属于顺序存取方式,2.1.2 线性表的存储结构,逻辑结构存储空间 的映射 数据存储单元 建立映射 关系存储单元之间关系 建立映射 线性表2类存储结构 顺序存储(定长的一维数组结构、向量型顺序存储结构 ) 为整个元素动态分配连续空间 特点:逻辑相邻物理也相邻 链式存储(
6、变长的线性表存储结构) 按需分配(插入:分配一个结点/删除:回收一结点) 特点:逻辑相邻物理不一定相邻,链表单向、循环、双向,不特殊说明,均带头结点(避免对空表的特殊处理) 算法:(时间复杂性) 在有序表中插入/删除结点 给定元素位置,插入/删除相应结点 注意: 对循环链表操作时,尾部的判断 双向链表的插入/删除结点 删除结点一定要释放空间,2.4 线性表实现方法的比较,顺序表优点 存储紧凑(逻辑结构由存储相对位置体现,没使用指针,不用花费附加开销 ) 随机访问(给定下标,常量时间可定位) 链表优点 不限定长度(无需事先了解线性表的长度,允许线性表的长度有很大变化 ) 不必移动,仅需改指针即可
7、插删(能够适应经常插入删除内部元素的情况 ) 适用 不能确定长度上限、频繁插删:用链式存储结构 按位置频繁进行读取、数据域占用空间小于指针域:用顺序存储结构,有序的顺序表与无序的顺序表相比,其操作优势是( )。 A. 删除快 B. 插入快 C. 生成快 D. 查找快。 若对线性表进行的主要操作是按下标存取,且很少插入和删除,则应该采用的存储结构是_;若需要频繁地对线性表进行插入和删除时,则应该采用的存储结构是 。,题型举例,第3章 栈与队列,栈与队列的定义、ADT定义及基本操作。 栈的应用:会跟踪递归函数执行过程 深度(纵向)周游 表达式求值(中缀后缀求值) 队列的应用:按层周游 注意:熟悉A
8、DT的操作形式,会直接调用抽象数据类型中定义的操作,算符优先关系表,+ - * / ( ) # + - * / ( 错 # =,左,右,a/(b-c)+d*e# abc-/de*+,后缀表达式求值,循环:依次分析输入序列: 1.输入是操作数:则入栈; 2.输入是运算符:则两次出栈,取操作数2和操作数1,按照运算符进行计算。将结果入栈。 重复,直至遇到结束符“=” 此时栈顶值就是输入表达式的值。,第 4 章 字符串(了解),基本概念 存储结构(顺序、标准类) 基本操作的含义,第5章 二叉树,定义、性质、存储结构(相应的类定义) 满二叉树、完全二叉树及扩充二叉树 抽象数据类型定义中的基本操作含义
9、深度周游(递归与非递归),广度周游 二叉搜索树插入、删除(改进)与检索算法;必须能够跟踪执行过程;求ASL。 堆概念、建堆、筛选、插、删的相关算法(过程) Huffman树构造及Huffman编码,深度优先周游二叉树(递归实现),template void BinaryTree:PreOrder (BinaryTreeNode* root) if(root!=NULL) Visit(root-value( );/前序 DepthOrder(root-leftchild(); /访问左子树 DepthOrder(root-rightchild();/访问右子树 ,Visit( root ) /中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京工业大学 数据结构 期末 深刻 深入 复习 温习
限制150内