北航--数据结构课件 复习
- 格式:pps
- 大小:138.50 KB
- 文档页数:18
软件工程技术基础复习指南一.数据结构1.术语:1.数据;2.数据元素;3数据结构;4.结构2.数据结构定义:就是具有结构的数据元素的集合。
3.算法的定义:用来解决某个特定课题的指令的集合。
4.算法的性质:输入、输出、有穷性、确定性、有效性5.算法描述:自然语言、程序流程图、具体程序语言6.算法分析:指对算法质量优劣的评价。
(时间复杂度、空间复杂度、可读性、可移植性、易测试性)7.时间复杂度:依据算法编写的程序在计算机中运行时间多少的度量(关键语句之行的次数)O(n);(O(log2n)(二分检索)<O(n)(比较两个具有n个字符串)<O(nlog2n)<O(n2)<O(n3)(常规矩阵乘)<O(2n)<O(n!));O(1):访问数组中的元素是常数时间操作8.空间复杂度:依据算法编写的程序在计算机中占存储空间多少的度量9.频度统计法:以语句执行的次数的多少作为算法的时间量度的分析方法10.语句的频度:语句被执行的次数11.算法的频度:算法中所有语句的频度之和12.数组:下标与值组成的偶对的有穷集合13.二维数组的存储结构:行序为主序分配方式、列序为主序分配方式、14.特殊矩阵的压缩存储:对称矩阵、对角矩阵、15.线性表:数据元素之间具有的逻辑关系为线性关系的数据元素集合16.线性表的基本操作:创建、索引、存入、插入、删除、排序、17.线性表顺序存储结构:用一组地址连续的存储单元依次存储线性表的数据元素,数据元素之间的逻辑关系通过数据元素的存储位置直接反映18.顺序存储结构优点:原理简单、元素存储地址可用简单解析式计算、存储空间开销小19.顺序存储结构缺点:需事先分配连续地址、基本操作时间效率低20.线性链表:用一组地址任意的存储单元(连续的或不连续的)依次存储表中各个数据元素,数据元素之间的逻辑关系通过间接地反映出来21.链式存储结构优点:存储空间动态分布、地址不连续、插入删除操作效率高(O(1))22.链式存储结构缺点:存储密度小、查找定位效率低O(n)23.堆栈定义:是一种只允许在表的一端进行插入操作和删除操作的线性表。
数据结构复习重点谁让我找到你们了.第一章1.数据是信息的载体,它能够被计算机识别、存储和加工处理。
2.数据元素是数据的基本单位。
有些情况下,数据元素也称为元素、结点、顶点、记录。
3.数据结构指的是数据之间的相互关系,即数据的组织形式。
一般包括三个方面的内容:①数据元素之间的逻辑关系,也称为数据的逻辑结构;②数据元素及其关系在计算机存储器内的表示,称为数据的存储结构;③数据的运算,即对数据施加的操作。
4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
按"值"是否可分解,可将数据类型划分为两类:①原子类型,其值不可分解;②结构类型,其值可分解为若干个成分。
5.抽象数据类型是指抽象数据的组织和与之相关的操作。
可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
6.数据的逻辑结构简称为数据结构。
数据的逻辑结构可分为两大类:①线性结构(~的逻辑特征是若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继);②非线性结构(~的逻辑特征是一个结点可能有多个直接前趋和直接后继)。
7.数据存储结构可用四种基本的存储方法表示:①顺序存储方法(该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构);②链接存储方法(该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构);③索引存储方法(该方法通常是在存储结点信息的同时,还建立附加的索引表);④散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。
8.非形式地说,算法是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值为输出。
因此,一个算法是一系列将输入转换为输出的计算步骤。
9.求解同一计算问题可能有许多不同的算法,究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是"正确"的。
祝同学们新学期愉快学习进步!课程名称:数据结构教材名称:《数据结构教程》唐发根刘又诚编著北京航空航天大学出版社1996《数据结构》唐发根编著科学出版社1998开设本课程的必要性以及课程的特点:1. 计算机专业重要的专业基础课之一.2. 需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.3. 实践性较强.第一章绪论1.1 什么是数据结构描述客观事物的数字、字符以及一切能够输入到计算机中,并且能够被计算机程序处理的符号的集合。
数据这个集合中的一个一个元素。
具有相同特性的数据元素的集合。
数据元素之间具有的关系(联系)。
数据数据元素数据对象结构一. 名词术语二. 数据结构的定义1.数据元素之间的联系称之为结构,数据结构就是具有结构的数据元素的集合。
2. 数据结构是一个二元组Data-Structure=(D,R)其中,D是数据元素的有限集合,R是D上的关系的集合。
数据元素之间具有的逻辑关系(结构)。
线性关系(线性结构)如线性表、数组、堆栈、队列、串、文件等具有某种逻辑结构的数据在计算机存储器中的存储方式(存储映象)。
物理结构也被称为存储结构。
顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素,数据元素之间的逻辑关系通过元素的地址直接反映。
用一组地址任意的存储单元依次存放数据元素,数据元素之间的逻辑关系通过指针间接地反映。
非线性关系(非线性结构)如树、二叉树、图等物理结构逻辑结构例刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………姓名性别民族年龄其他逻辑结构:线性结构(线性表)a 1a 2a 3 a 30…d 1d 2 d 3d 4…d 30a 2a 1a 3a 4a 30存储结构:1. 顺序存储结构:2. 链式存储结构:…d 1d 2 d 3d 4a 1a 2a 3a 30∧list…a 2a 1a 4a 3d 4d 1d 5d31.研究数据元素之间的客观联系。
北航算法与数据结构复习题北航《算法与数据结构》复习题单选题(每小题2分,总分10分)1、线性表若采用链表存储结构时,要求内存中可用存储单元的地址(D )A、必需是联系的B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以2、对顺序表上的插入、删除算法的时间复杂性分析来说,通常以什么为标准操作(B)A、条件判断B、结点移动C、算术表达式D、赋值语句3、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是(B )A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;4、对关键码序列28,16,32,12,60,2,5,72快速排序,从小到大一次划分结果为(C )A、(2,5,12,16)26(60,32,72)B、(5,16,2,12)28(60,32,72)C、(2,16,12,5)28(60,32,72)D、(5,16,2,12)28(32,60,72)5、稀疏矩阵的压缩存储方法是只存储(A )A、非零元素B、三元组(i,j, aij)C、aijD、i,j1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为(A)排序法。
A、插入B、选择C、希尔D、二路归并2、用线性探测法查找闭散列表,可能要探测多个散列地址,这些位置上的键值(D )A、一定都是同义词B、一定都不是同义词C、都相同D、不一定都是同义词3、将含有83个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为41的双亲结点编号为(D )A、42B、40C、21D、204、一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是(B )A、不确定B、n-i+1C、ID、n-i5、设深度为k的二叉树上只有度为0和度为2的节点,则这类二叉树上所含结点总数最少(C)个A、k+1B、2kC、2k-1D、2k+1判断题(每小题1分,总分10分)(A==对,B==错)6、在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行前序遍历和后序遍历,则具有相同的结果。
总复习
总复习
一.考试复习范围
第一章绪论
第二章线性表
第三章数组
第四章堆栈和队列
第五章广义表
第六章串
第七章树与二叉树
第八章图
第九章文件和查找
第十章内排序
二、试题类型
1. 概念题
2. 算法题
3. 综合题(问题求解题)
(1).是非判断题
(2).简答题
(3).填空题
(4).单项选择题
(1).算法设计题
(2).算法填空题
三、复习内容
1. 第一章绪论
(1)关于结构
∙结构的种类
∙结构之间的关系
(2)关于算法
∙算法的定义
∙算法的描述
∙SPARKS语言
∙算法分析的基本概念
2. 第二章线性表
(1)关于线性表
∙什么是线性关系?
∙什么是线性表?
∙线性表的基本操作有哪些?(2)线性表的顺序存储结构
∙线性表的顺序存储结构的构造原理
∙插入、删除操作对应的算法的设计
∙线性表的顺序存储结构的特点(3)线性表的链式存储结构
∙线性表的链式存储结构的构造原理
∙线性链表的插入、删除算法
∙循环链表的插入、删除算法
∙双向链表的插入、删除算法
3. 第三章数组
(1)数组的基本概念
(2)数组的存储结构
∙一维数组
∙二维数组
(3)特殊矩阵的压缩存储
∙对称矩阵
∙对角矩阵(三对角矩阵)
∙稀疏矩阵的三元组方法、十字链表方法(4)数组的应用
4. 第四章堆栈和队列
(1)堆栈和队列的基本概念
∙定义
∙基本操作
∙特殊性
(2)堆栈和队列的存储结构
∙顺序存储结构
插入、删除操作对应的算法设计
∙链式存储结构
插入、删除操作对应的算法设计(3)堆栈和队列在解决实际问题中的应用
5. 第五章广义表
(1)广义表的基本概念
(2)广义表的存储结构
(3)多元多项式的广义表存储方法
6. 第六章串
(1)串的基本概念
∙串的定义
∙几个名词术语、概念
(2)串的基本操作
(3)串的存储结构
∙顺序存储结构--紧缩格式、非紧缩格式
∙链式存储结构
(4)几个基本算法
7. 第七章树与二叉树
(1)树的基本概念
∙树的定义
∙树的逻辑特点
∙树的逻辑表示方法
∙名词术语
(2)树的存储方法
∙多重链表、三重链表
(3)二叉树
∙二叉树的基本概念(定义)
∙两种特殊形态的二叉树(满二叉树、完全二叉树)(4)二叉树的基本性质(五个)
(5)二叉树的存储结构
∙顺序存储结构
∙链式存储结构----二叉链表
(6)二叉树的遍历
∙遍历的基本概念
∙几种常见的遍历方法
前序遍历、中序遍历、后序遍历、按层次遍历∙由遍历序列恢复二叉树
∙遍历的非递归算法的设计
(7)二叉排序树
∙二叉排序树的定义
∙建立二叉排序树的逐点插入方法
∙二叉排序树的删除(原则)
∙二叉排序树的查找
8. 第八章图
(1)图的基本概念
∙图的定义
∙图的分类
∙名词术语
---顶点的度、路径、子图、图的连通、生成树(2)图的存储方法
∙邻接矩阵存储方法
∙邻接表存储方法
(3)图的遍历
∙图的遍历的基本概念
∙深度优先遍历方法
∙广度优先遍历方法
(4)最小生成树
∙最小生成树的概念
∙求解最小生成树的方法(5)最短路径
∙路径长度的定义
∙最短路径的概念
∙求解最短路径的方法(6)AOV网与拓扑排序(7)AOE网与关键路径
∙AOE网与关键路径的定义
∙求解关键路径的方法
9. 第九章文件及其查找
(1)文件的基本概念
∙名词术语
∙文件的逻辑结构和物理结构
∙文件的基本操作
查找、插入、删除、修改、排序
(2)顺序文件
∙顺序文件的分类
∙连续顺序文件的顺序查找方法
∙排序连续顺序文件的折半查找方法
∙连接顺序文件的查找方法
(3)索引文件
∙索引文件的概念---组成、索引表的特点
∙稠密索引文件与非稠密索引分块文件的查找
(4)B树与B+树
∙B 树和B+ 树的定义
∙B 树和B+ 树的查找
(5)杂凑文件(Hash文件)
∙杂凑文件的基本概念
杂凑函数、杂凑文件、哈希冲突∙杂凑函数的构造方法
∙哈希冲突的处理方法
开放地址法、再哈希法、链地址法
10. 第十章内排序
(1)排序的基本概念
∙排序的定义
∙排序的功能
∙排序的分类---内排序、外排序(2)插入排序法
(3)选择排序法
(4)泡排序法
(5)谢尔(Shell)排序法
(6)快速排序法
(7)堆积排序法
(8)二路归并排序法
每一种排序方法的的基本原理、规律、特点。
最好和最坏情况下排序过程中进行的元素之间的比较次数,如插入排序方法、选择排序方法。
某些排序法的排序趟数有何特点。
祝大家取得好成绩!。