文档介绍：计算机二级 access
公共基础知识
算法:是指解决方案的准确而完整的描述
算法的有穷性:是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
算法的复杂度
时间复杂度——执行算法所需的计算工作量
(用基本运算的次数来度量) 两者不相关
空间复杂度——执行算法所需的内存空间
算法必须有一个或一个以上的输出[必须有输出]
可以没有输入
数据结构:是指相互有关联的数据元素的集合
数据的逻辑结构:就是数据元素之间的逻辑关系,它是从逻辑上描述数据元素之间关系的,是独立于计算机的
数据的存储结构:是研究数据与数据元素之间的关系如何在计算机中表示的
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)
各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的
逻辑结构与存储结构之间不是一一对应的
根据数据结构中各数据元素之间前后件关系的复杂程度,分为:
线性结构:满足条件一对一关系
(1)有且只有一个根结点
(2)每一个结点最多有一个前件,也最多有一个后件
(3)在一个线性结构中插入或删除任何一个结点后还应是线性结构
如:循环链表、双向链表
非线性结构: 一对多或多对一关系
、最常用的一种数据结构
线性表的顺序存储结构和链式存储结构两者比较
术语
父结点:每个节点只有一个前件
根结点:没有前件的结点只有一个
子节点:每个结点可以有多个后件
叶子结点:没有后件
结点的度:一个结点所拥有的后件个数
树的深度:树的最大层次
什么是二叉树?(树,非线性结构)
非空二叉树只有一个根结点
每一个结点最多有两颗子树,且分别称为该结点的左子树与右子树
二叉树通常采用链式存储结构
性质
顺序查找
最坏情况下查找n次
无序表只能采用顺序查找
有序线性表,若为链式存储结构,只能采用顺序查找
二分法查找
只适用于顺序存储的有序表
最坏情况下查找㏒2n次
交换类排序法
:相邻两元素的交换
最坏情况下,比较n(n-1)/2
:分割
最坏情况下,比较n(n-1)/2
插入类排序法
:无序插入有序
最坏情况下,比较n(n-1)/2
:分割插入
选择排序法
:选最小放最前面
最坏情况下,比较n㏒2n
结构化程序设计的原则(比较)
结构化程序设计的基本结构
顺序结构、选择结构、重复(循环)结构
结构化程序设计的特点:易读性
对象
标识唯一性
分类性
多态性
封装性
模块独立性(信息隐蔽)[没有:一致性]
消息
消息是一个实例与另一个实例之间传递的信息
软件危机
软件需求的增长得不到满足
软件开发的成本和进度难以控制
软件质量难以保障
软件不可维护或维护程度非常低
软件的成本不断提高
软件开发生产率的提高赶不上硬件的发展和应用需求的增长
[没有:软件过程不规范]
软件工程