数据结构与算法
数据结构与算法
算法的基本特性:可行性,确定性,有穷性,拥有足够的情报。 算法是指解题方案准确而完善的描述。
算法复杂度包括时间复杂度和空间复杂度。
时间复杂度:执行算法所需要的计算机工作量。
空间复杂度:执行算法所要的内存空间。
数据结构分为逻辑结构和存储结构。常用的存储结构有顺序结构、链式存储结构、索引存储结构、
数据逻辑结构:反映数据元素之间逻辑关系的数据结构。
数据存储结构:数据的逻辑结构在计算机存储空间中的存放形式。
队:FIFO ,一头进,另一头出来。循环队列,一般题型:概念、计算队列中还有几个元素(尾指针减去头指针)。
栈:FILO ,只能从一个头进,出。一般题型:概念、问A B C D 四个选项中不能出栈的次序。
线性表的基本概念。记住线性表顶多有一个头节点和一个后继节点。所以栈、队列、单向链表都是线性表,树、双向链表不是线性表。
树;叶子节点最多的个数:2n-1个节点。一共的节点数目2n-1,节点为2的数目为节点为1的数目减一。也就是n2=n0-1
满二叉树:_____________________。
完全二叉树:_____________________。
二叉树中,度为0的数目比度为2的数目多一个。 n0=n2+1
二叉树的前序遍历、中序遍历、后序遍历是考试重点。
顺序查找:长度为n 的线性表,平均要进行n/2,最坏要进行n 次比较。(常考)
二分查找:对于长度为n 的线性表,在最坏情况进行 log2n 次。 要背的话:
算法的时间复杂度和空间复杂度没有必然的联系。
一个数据结构的逻辑结构根据需要可以有多个存储结构。存储结构的不同,会造成处理的效率不同。
栈具有记忆性。如果要存的数据是1 2 3 4 5,栈可以不顺序存储。 我们存放数据的时候,存储空间不一定是连续的,并且各个元素的存储顺序可以是任意的。如:链表。
在线性链表中查找一个元素比在顺序表中查找一个元素要快,
冒泡排序、选择排序、交换排序、堆排序中平均排序次数最快的是 堆排序。 能够用二分查找的是顺序存储的有序线性表。
逻辑结构
线性表
栈
队列
树
二叉树 存储结构 链表,顺序存放 链表,顺序存放 链表,顺序存放 链式存放 链式存放
2012年计算机二级公共基础知识章节复习要点
2012-01-31 15:51:06 我要评论(20) 阅读次数:3179
第一章 数据结构与算法
算法---是一组严谨地定义运算顺序的规则
算法的基本要素---一是对数据对象的运算和操作,二是算法的控制结构 算法设计基本方法---列举法、归纳法、递推、递归、减半递推
算法的复杂度---包括时间复杂度和空间复杂度
时间复杂度---执行算法所需的计算工作量
空间复杂度---执行算法所需的内存空间
数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬;18、11、35、23、16。。。;父亲、儿子、女儿等都是数据元素。
前件---数据元素之间的关系,如父亲是儿子和女儿的前件
后件---如儿子是父亲的后件
结构---指数据元素之间的前后件关系
数据的逻辑结构—是指反映数据元素之间逻辑关系,而与它们在计算机中的存储位置无关
数据的存储结构(物理结构)---数据的逻辑结构在计算机存储空间中的存放形式,数据元素在计算机存储空间的位置关系可能与逻辑关系不同。
根据数据结构中各数据元素之间前后件关系的复杂程度,可将数据结构分两类---线性结构与非线性结构
线性结构(线性表)---满足下列两个条件(1)有且只有一个根结点(2)每一个结点最多有一个前件和后件。则称该数据结构为线性结构,否则为非线性结构。
线性表是最简单、最常用的一种数据结构,其数据元素之间的相对位置是线性的,其存储方式为顺序存储的,如数组
栈---是限定在一端进行插入与删除的线性表,一端封闭,另一端开口,其操作原则是“先进后出”,栈的运算有入栈、退栈、读栈顶元素
队列---是指在一端进行插入(称为队尾)而在另一端进行删除(称为队头)的线性表,其操作规则是“先进先出”,其运算有入队和退队。
树---是一种简单的非线性结构,而且是层次结构,是倒立的大树,有根结点、父结点、子结点、叶子结点。根结点在第一层,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为 树的度,树的最大层次称为树的深度。
二叉树---(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树(左子树和右子树),其存储结构为链式。
二叉树性质---(1)K 层上最多有2(K-1)个结点(2)深度为m 的二叉树最多有2m-1个结点
(3)度为0的结点(叶子结点)比度为2的结点多一个(4)具有n 个结点的二叉树,其深度至少为[Log2n]+1,其中[Log2n]表示对Log2n 取整 满二叉树---除最后一层外,其余层的结点都有两个子结点
完全二叉树---除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点,叶子结点只可能在层次最大的两层上出现。满二叉树是完全二叉树,而完全二叉树不是满二叉树。完全二叉树有两个性质:(1)具有n 个结点的完全二叉树的深度为[Log2n]+1(2)
二叉树遍历---不重复地访问各个结点。分为前序遍历(DLR-根左右) 、中序遍历(LDR-左根右) 和后序遍历(LRD-左右根)
查找技术---顺序查找——对于长度为n 的有序线性表,查找时需要比较n 次
二分法查找——对于长度为n 的有序线性表,查找时需要比较log2n 次 排序技术---假设线性表的长度为n ,则冒泡排序和简单插入排序的比较次数(时间复杂度)为n(n-1)/2;希尔排序的比较次数为O(n1.5);简单选择排序的比较次数为n(n-1)/2;堆排序的比较次数为O(nlog2n).
第二章 程序设计基础
结构化程序设计的三种结构---是顺序、选择和循环
对象---表示客观世界的任何实体
类---是具有共同属性和方法的对象的集合
实例---任何一个对象都是其对应类的实例
消息---一个实例和另一个实例之间传递的信息
继承---是指直接获得已有的性质和特征,而不必重复定义它们。例如子类继承父类
结构化程序设计主要强调---程序的易读性
良好的程序设计风格是---程序应简单、清晰、可读性好
第三章 软件工程基础
软件生命周期---软件产品从提出、实现、使用维护到停止使用退役的过程。分为软件定义、软件开发、软件运行维护三个阶段。
软件生命周期的主要活动阶段---可行性分析、需求分析、软件设计、软件实现、软件测试、运行和维护。
常见的需求分析方法---
(1)结构化分析方法---主要包括面向数据流的结构化分析方法SA ;面向数据结构的Jackson 方法JSD ;面向数据结构的结构化数据系统开发方法DSSD 。
(2)面向对象的分析方法OOA
结构化分析方法工具---
(1)数据流图DFD ,记住DFD 图的几个符号
(2)数据字典DD
(3)判定树
(4)判定表
程序结构图(SC ),N-S 图,问题分析图(PAD )
程序流程图(PFD )的几个符号:
软件测试---黑盒测试:功能测试
白盒测试:内部结构测试,穷举路径测试
第四章 数据库设计基础
数据库---DB ;数据库管理系统---DBMS ;数据库管理员---DBA ;数据库系统---DBS ;数据库应用系统---DBAS
数据模型所描述的内容分三个部分(数据结构)、(数据操作)、(数据约束)
逻辑数据模型分(层次模型)、(网状模型)、(关系模型)、(面向对象模型)
E-R 模型---实体关系模型,主要由实体、属性、联系组成,联系分:1对1,1对多,多对多;
以二维表为基本结构所建立的模型称为关系模型,关系模型采用二维表来表示,简称表,由行和列组成,行称为元组或记录,列称为字段
主键---唯一标识一个记录的字段
外键---一个表的字段是其他表的主键