数据结构与算法
一、基本概念
1、逻辑结构:数据元素之间的逻辑关系2、存储结构:数据元素及其关系在计算机存储器内的表示。
3、数据的运算(算法):即对数据施加的操作
1、线性结构:
特征是:若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点最多只有一个直接前趋和一个直接后继。例:一维数组、链表、栈、队列、串
2、非线性结构:特征是:一个结点可能有多个直接前趋和直接后继。
例:多维数组、广义表、树、图
1、顺序存储方法:该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,一般通过数组来实现的。
2、链接存储方法:该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。
3、索引存储方法:该方法通常是在存储结点信息的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:关键字,地址。
4、散列存储方法:该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址,通过散列函数实现。例:除余法散列函数、相乘取整法散列函数
1、可行性(Effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。
2、确定性(Definiteness):算法中的每一个步骤都必须有明确的定义,不允许出现歧义性。
3、有穷性(Finiteness):算法必须在有限时间内做完,即必须在执行有限个步骤之后终止。
二、线性表:
1、顺序存储(Sequential
2、链式存储(Linked
常见的运算有:
表的初始化、求表的长度、取表中的第i个结点、查找结点、插入新的结点、删除结点。
1、基于空间的考虑:
A、顺序表的存储空间是静态分配的,而链表的存储空间是动态分配的。
B、顺序表占的存储空间必须是连续的,而链表占的存储空间可以是连续的,也可是不连续的
C、顺序表存储密度为1,而链表中的每个结点,除了数据域外,还要额外的设置指针域,存储密度小于1
2、基于时间的考虑:
A、在链表中的任何位置上进行插入和删除,只需要修改指针,而顺序表中平均将要移动近一半的结点。
B、顺序表是随机存取结构,它的存取时间为O(1),而链表需从头结点顺着链扫描链表。
例:关于线性表的描述中,错误的是(
A、线性表是线性结构
C、线性表是单链表
用数组表示线性表的优点是(
A、便于插入和删除操作
三、栈:栈(Stack):是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进先出的线性表,又称为LIFO表。
栈的基本运算有:栈的初始化、判栈空、判栈满、进栈、出栈等
例:若进栈的输入序列是A、B、C、D、E,并且在它们进栈的过程中可以进行出栈操作,则不可能出现的出栈序列是(
四、队列:
例:一个队列的入队序列是1,2,3,4,则队列的输出序列是
A、4,3,2,1
五、串:串(String):是零个或多个字符组成的有限序列。串中所包含的字符个数称为该串的长度。
串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串
注:空串是任意串的子串,任意串是其自身的子串
2、串变量其值是可以改变的。
六、树(非线性结构树(Tree):是n(n>=0)个结点的有限集T,T(n=0)为空时称为空树,否则它满足如下两个条件:
1、有且仅有一个特定的称为根(Root)的结点
2、其余的结点可分为m(m>=0)个互不相交的子集T1,T2,…….,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subtree)。
树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点,相应的该结点称为孩子结点的双亲(Parents)结点或父结点。
结点的层数(Level)是从根起算,设根的层数为1,其余结点的层数等于其双亲结点的层数加1.
二叉树中,每个结点最多只能有两棵子树,并且有左右之分。
例:具有3个结点的二叉树有几种形态。
完全二叉树(Complete
二叉树的性质:性质1:二叉树第i层上的结点数目最多为2i-1(i>=1)
性质2:深度为k的二叉树至多有2k-1个结点(k>=1)性质3:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1性质4:具有n个结点的完全二叉树的深度为[lgn]+1(取下整)
例:一棵二叉树的结点数为18个,求它的最小高度
二叉树的遍历:
前序遍历:(又称为先序遍历、先根遍历)
若二叉树为空,则执行空操作。否则:
1、访问根结点;
若二叉树为空,则执行空操作。否则:
例:已知一棵二叉树的中序遍历序列是:FDGBACHE,其后序遍历序列是:FGDBHECA
求其前序遍历序列。一棵二叉树的前序遍历序列为ABDGCFK,中序遍历序列为DGBAFCK,则结点的后序遍历序列是(
七、排序(Sort):
通过对待排序序列从后向前或从前向后(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)。
直接选择排序(Selection
扫描整个线性表,从中选出最小的元素,将它交换到表的最前面;然后对剩下的子表采用同样的方法,直到子表空为止。
每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
各种内部排序方法的比较
排序方法 | 时间复杂度 | 空间复杂度 | ||
最好时间 | 平均时间 | 最坏时间 | ||
直接插入 | O(n) | O(n2) | O(n2) | O(1) |
直接选择 | O(n2) | O(n2) | O(n2) | O(1) |
冒 | O(n) | O(n2) | O(n2) | O(1) |
快 | O(nlgn) | O(nlgn) | O(n2) | O(lgn) |
堆 | O(nlgn) | O(nlgn) | O(nlgn) | O(1) |
例:对一个具有n个元素的序列进行冒泡排序,在最坏情况下,要进行交换的次数是(
A、n(n+1)/2
对n个元素进行冒泡排序过程中,最好情况下的时间复杂性为(
对n个元素进行快速排序的过程中,平均情况下的时间复杂性为(
八、查找(Searching):
v
v
查找成功的平均查找长度为:(n为结点数目)
v
查找成功时的平均查找长度:(n为结点数目)
当n很大时,可用近似公式:
软件工程基础
一、基本概念:
v
v
4、软件不可维护或维护程度非常低5、软件成本不断提高6、软件开发生产效率的提高赶不上硬件的发展和应用需求的增长
v
v
v
v
v
v
瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型。主要包括问题定义及可行性分析、项目开发计划、需求分析、概要设计、详细设计、编码、测试和维护几个阶段。
例:下列描述中正确的是(
C、软件既是逻辑实体,又是物理实体 D、软件是程序、数据与相关文档的集合
二、软件可行性研究与项目开发计划:
v
v
v
4、导出和评价各种方案5、推荐可行的方案6、编写可行性研究报告
三、软件需求分析:
v
v
1、问题识别A、功能需求B、性能需求C、环境需求D、用户界面需求
2、分析与综合,导出软件的逻辑模型
3、编写文档(需求规格说明书)
v
1、结构化分析(Structured
SA方法利用图形等半形式化的描述方式表达需求,主要描述工具:
A、数据流图(DFD):是SA方法中用于表示系统逻辑模型的一种工具,以图形的方式描绘数据在系统中流动和处理的过程。B、数据字典(DD):用以定义数据流图中的各个成分的具体含义,为系统的分析、设计及维护提供了有关元素的一致的定义和详细的描述。C、描述加工逻辑的结构化语言、判定表、判定树
2、IDEF方法(是
是一种用于进行复杂系统分析和设计的方法,是在结构化分析和设计技术的基础上提出来的。
3、面向对象分析方法(OOP):
将客观世界的事物抽象为对象,通过属性和方法描述对象的状态和行为,具有继承、封装和多态性等特征。
例:软件开发的结构化分析方法中,常用的描述软件功能需求的工具是(
A、业务流程图、处理说明
四、软件概要设计:将软件需求转换为软件表示的过程。
3、编写概要设计文档:
模块化:模块在程序中是数据说明、可执行语句等程序对象的集合,或者是单独命名和编址的元素,如高级语言中的过程、函数、子程序等。
例:为了使模块尽可能独立,要求(
A、模块的内聚程序要尽量高,且各模块间的耦合程序要尽量强
B、模块的内聚程序要尽量高,且各模块间的耦合程序要尽量弱
C、模块的内聚程序要尽量低,且各模块间的耦合程序要尽量弱
D、模块的内聚程序要尽量低,且各模块间的耦合程序要尽量强
五、软件详细设计:主要确定每个模块具体执行过程
3、对数据库进行物理设计:
v
六、软件编码:主要是将详细设计得到的处理过程描述转换为基于某种计算机语言的程序
常用的计算机语言:
七、软件测试:软件测试代表了需求分析、设计、编码的最终复审。软件测试贯穿于软件开发的全过程。
2、一个好的测试用例能够发现至今尚未发现的错误。
3、一个成功的测试是发现了至今尚未发现的错误的测试。
2、测试用例不仅选用合理的输入数据,还要选择不合理的输入数据3、除了检查程序是否做了它应该做的事
4、应制定测试计划并严格执行,排除随意性5、长期保留测试用例
6、对发现错误较多的程序段,应进行更深入的测试7、程序员避免测试自己的程序
v
1、静态测试:是指被测试程序不在机器上运行,而是采用人工检测和计算机辅助静态分析的手段对程序进行检测。
2、动态测试:是指通过运行程序发现错误A、黑盒测试法(功能测试):
主要对软件的接口进行测试,依据需求规格说明书,检查程序是否满足功能要求。常用的技术是等价类划分法、边界值分析法、错误推测法、因果图法、综合策略法
B、白盒测试法(结构测试):
主要测试程序的内部结构和处理过程。常用的技术是语句覆盖、条件覆盖、路径覆盖、判定覆盖等
1、单元测试:
单元测试是对软件设计的最小单位——模块(程序单元)进行正确性检验测试,主要针对模块的以下五个基本特征进行测试:
集成测试是指在单元测试的基础上,将所有模块按照设计要求组装成一个完整的系统进行的测试,故也称组装测试或联合测试。
主要方法有两种:
非渐增式测试:首先对每个模块分别进行单元测试,然后再把所有的模块按设计要求组装在一起进行测试。
渐增式测试:逐个把未经过测试的模块组装到已经过测试的模块上去,进行集成测试,每加入一个新模块进行一次集成测试,重复此过程直至程序组装完毕。
3、确认测试:
确认测试又称有效性测试,它的任务是检查软件的功能与性能是否与需求规格说明书中确定的指标相符合,因而需求规格说明是确认测试的基础。
4、系统测试:
系统测试是通过测试确认的软件作为整个计算机系统的一个元素,与计算机硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起,在实际运行环境下对计算机系统进行一系列的集成测试和确认测试。
调试是在进行了成功的测试之后才开始的工作,目的是确定错误的原因和位置,并改正错误,又称为纠错。
例:软件测试的目的是(
A、证明软件的正确性
C、尽可能多地发现软件系统中的错误
在软件测试方法中,黑箱测试法和白箱测试法是常用的方法,其中黑箱测试法主要是
用于测试(
八、软件维护:
1、校正性维护:
为了识别和纠正错误,修改软件性能上的缺陷,其占整个维护工作的
2、适应性维护:
为了使应用软件适应环境(硬件、系统软件、数据)的变化而修改软件的过程称为适应性维护,其占整个维护工作的25%
3、完善性维护:
增加软件功能、增强软件性能、提高软件运行效率而进行的维护活动称为完善性维护,其占整个维护工作的
4、预防性维护:
为了提高软件的可维护性和可靠性而对软件进行的修改称为预防性维护,其占整个维护工作的
例:软件维护是指(
A、维护软件正常运行B、软件的配置更新C、对软件的改进、适应和完善 D、软件开发期的一个阶段
软件生命周期中所花费用最多的阶段是(
数据库原理基础
一、基本概念:
其经历了以下阶段:
5、面向对象的数据库系统阶段
数据库的建立、使用和维护进行管理和配置的软件系统。
是数据库系统的核心
数据库系统的特点:实现数据共享、减少数据冗余
具有较高的数据独立性
实体:
例:数据库管理系统能实现对数据库中数据的查询、插入、修改和删除,这类功能称为(
A、数据定义功能 B、数据管理功能 C、数据操纵功能 D、数据控制功能
联系的类型:
1、一对一联系:表现为主表中的每一条记录只与相关表中的一条记录相关联。
例如:
2、一对多联系:表现为主表中的每一条记录与相关表中的多条记录相关联。
例如:
3、多对多联系:表现为一个表中的多个记录在相关表中同样有多个记录相关联。
例如:
1、层次模型:用树形结构表示实体及其之间联系的模型称为层次模型。
2、网状模型:用网状结构表示实体及其之间联系的模型称为网状模型。
3、关系模型:用二维表结构来表示实体及实体之间的联系的模型称为关系模型。
一个二维表称为一个关系,在VFP称为数据表。一个关系不仅表示实体本身还表示实体之间的联系。
例:用树形结构表示实体之间联系的模型是(
A、关系模型 B、网状模型 C、层次模型 D、以上三个都是
二、关系数据库:
v
v
v
注:关键字不能出现空值或重复值
v
v
二维表中元组的个数是有限的——元组个数有限性
二维表中元组均不相同——元组的惟一性
二维表中元组的次序可以任意交换——元组的次序无关性
二维表中元组的分量是不可分割的基本数据项——元组分量的原子性
二维表中属性名各不相同——属性名惟一性
二维表中属性与次序无关,可任意交换——属性的次序无关性
例:关系数据模型中表示实体和实体间的联系的结构是(
A、树型
三、关系运算:
并(Union):是由两个关系的元组组成的集合。(两个关系必须具有相同的关系模式)
差(Difference):若有两个相同结构的关系R和S,R差S的结果属于R但不属于S的元组组成的集合。
交(Intersection):若有两个相同的结构关系R和S,交的结果为两个关系共同的元组。
联系客服