选择题公共知识点汇总(一)
算法
算法是解决问题的操作步骤。不等于程序,不等于数学上的计算方法。
算法的基本特征:可行性、确定性、有穷性(有限时间)、拥有足够的情报。
算法要求有0个及以上输入,1个及以上输出。
算法的基本要素:对数据对象的运算和操作、控制结构。
算法复杂度:
时间复杂度
执行算法所需要的计算工作量(最坏情况可=平均情况)(控制结构可计算时间复杂度)空间复杂度
执行算法所需内存空间
两者独立,无直接或间接关系
数据的逻辑结构和存储结构不是一一对应的。
算法的基本运算次数与特定的输入有关。
算法的工作量与计算机、程序设计语言、编制者、实现细节无关。
算法的效率与问题的规模和数据的存储结构都有关。
程序可以作为算法的一种表达方式
数据
- 数据结构 相互之间有关联的数据元素的集合
- 数据的基本单位 数据元素
- 数据的最小单位 数据项
- 表示数据结构的方法
二元关系表示法
图形表示法
- 数据结点 标有元素值的方框表示数据元素
- 元素前后关系 有向线段从前件指向后件结点
- 数据的逻辑结构(与存储无关)
线性结构
有且只有一个根节点常见线性结构
线性表、栈(先进后出)、队列(先进先出)、向量、矩阵、二维表
非线性结构
树、图形结构
- 数据的存储结构 逻辑结构在存储空间的存放形式
- 分类:顺序、链式、索引、散列存储方式
非空数据结构可以是线性结构也可以是非线性结构
非空数据结构可以没有根节点
线性表
- 线性表是n个元素的有限序列(n=0为空表)。
- 对线性表可进行查找、删除、插入等操作。
- 线性表中各元素具有相同的数据性,所有线性表都可采用顺序存储。
- 非空线性表满足的条件:
- 只有一个根节点,且无前件;
- 只有一个终端店,且无后件;
- 除根节点和终端点之外,其他节点只有一个前件和后件。
- 线性表的顺序存储结构:
- 元素所占的空间是连续的;
- 各数据元素在存储空间中的存放顺序是按照逻辑顺序依次存放的。
- 线性表的链式存储结构
- 存储空间可连续也可以不连续;
- 每个元素占有相同的存储单元;
- 数据的插入和删除不需要移动元素,只需要改变结点的指针域。
- 循环链表和双向链表为线性结构的数据结构
- 循环队列为队列的顺序存储结构(循环链表不是链表的顺序存储结构)
- 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。
- 线性结构的存储结点可以有多个指针
栈与队列(线性表)
- 栈是一种先进后出表,队列是一种先进先出表(操作系统中的作业调用就是队列)。
- 栈只允许在栈顶(top)进行插入和删除操作,不允许在栈底进行操作(bottom)。
栈支持子程序调用。
- 队列只允许在队头(front)进行删除,在队尾(rear)进行插入。
- 存储结构:
栈的存储结构
:- 相当于是一个一维数组,m为栈的最大容量, 当top=0时,栈为空栈;
- 发生上溢错误,表明栈已满;发生下溢错误,表明栈已空;
- 读栈顶元素=将值赋给一个变量。
- 队列的存储结构:
- 用一维数组作为顺序存储空间;
- rear=front=m时,队空或队满;
front>rear时,元素个数=m-(front-rear);
front<rear时,元素个数=rear-front。
- 带链的队列:
- 一个单链表表示队列
- 队列空 头尾指针为NULL
- 队列一个元素 头尾指针都指向它
- 链式存储结构:
- 每个结点由数据域(元素值)和指针域(指针)构成;
- 存储节点不一定连续,结点存储顺序与数据元素之间1的逻辑可以不一致;
- 链式存储的可以是线性结构,也可以是非线性结构。
- 线性链表
- 是线性表的链式存储结构;
- head不得丢失,最后一个结点指针域为空NULL/0;
- head=NULL/0是空表;
- 不一定连续,逻辑顺序不一致。
- 单链表
- 缺点:找到后件,找不到前件。
- 循环链表 指针域指向线性表的第一个元素结点
- 至少有一个节点存在(表头结点);
- 实现空表和非空表1的运算的统一;
- 可以实现从任意结点无重复地扫描到所有节点。
二叉树(非线性结构)
- 存储结构:
顺序存储结构
:连续存储单元 从上至下,从左到右(满二叉树和完全二叉树可按层次进行顺序存储)链式存储结构
- 二叉树分为完全二叉树和满二叉树。满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。
- 遍历 (不重复地访问所有结点):
- 前序:根 左 右
- 中序:左 根 右
- 后序:左 右 根
查找技术与排序技术
- 顺序查找 从线性表的第一个元素开始
- 只能采用顺序查找:
无序线性表(顺序结构、链式结构)
有序线性表(链式结构)
- 最坏情况下需要比较n次
- 只能采用顺序查找:
- 二分法
- 最坏情况下需要比较log次
- 适用于顺序存储的有序表(已对顺序存储结构排序,但相邻元素值可相等)
- 排序
- 冒泡排序、直接插入排序、快速排序和简单选择排序法最坏情况下需要比较次数为
n(n-1)/2
; - 希尔排序
(n^1.5次)
; - 堆排序 时间复杂度为
o(n〖log〗_2n)
最坏情况下堆排序比较次数最少
快速排序适用于顺序存储的线性表
冒泡排序是相邻元素进行交换 - 冒泡排序、直接插入排序、快速排序和简单选择排序法最坏情况下需要比较次数为
程序设计
定义 是设计、编制、调试程序的方法和过程
设计风格
- 源程序文档化
- 数据说明方法
- 语句的结构(清晰第一,效率第二)
- 程序的输入和输出
高内聚,低耦合
结构化程序设计
- 基本原则
- 自顶向下
- 逐步求精
- 模块化
- 限制使用goto语句
- 基本结构 顺序结构、选择结构(分支结构)、循环结构(重复结构)
- 结构化方法软件需求分析工具
数据流程图(DFD)
数据存储间无数据流,支持软件系统功能建模- 椭圆 表示加工(转换)
- 箭头 表示数据流
- 双杠 表示存储文件(数据源)
- 矩形 表示源、潭
- 数据字典(DD) 解释DFD图形元素
- 判定树
- 判定表
- 基本原则
面向对象的程序设计
- 组成
对象
描述客观事物的一个实体,实构成软件系统的基本单位。 对象=数据(属性)+方法(操作)- 标识唯一性
- 分类性
- 多态性
- 封装性
- 模块独立性好
对象是类的一个实例
- 类 具有相同属性和服务的一组对象的集合 可用于创建对象
- 封装 目的是为了实现信息隐蔽
- 向外部提供外部接口,降低对象间耦合度。
对象间的紧密程度越高,耦合度越高,可维护性越低。
- 向外部提供外部接口,降低对象间耦合度。
- 继承 多个类之间共享属性和操作的机制
对象不一定具有继承性
- 消息 统一数据流和控制流 对象间通信靠消息传递
- 多态性 指同一个操作可被不同对象接收导致不同行为
- 组成
软件工程
- 软件
- 概念 包括
程序、数据及文档
的完整集合(逻辑产品) - 分类
应用软件
解决特定领域(office 杀毒软件 浏览器)系统软件
管理计算机本身(数据库管理系统 操作系统 unix系统)支撑软件
为开发、维护软件的软件(编译软件 如DevC++)
- 特点
- 是逻辑实体,有抽象性
- 生产没有明显的制作过程
- 运行使用期间不存在磨损、老化问题
- 开发、运行对计算机系统依赖性高
- 概念 包括
- 软件危机(成本、质量、生产率)
- 产生原因:软件开发、维护方法不当
- 软件工程
- 三要素
方法、工具、过程
- 核心思想 工程产品
- 原则
- 抽象
- 信息隐蔽 封装
- 模块化
- 局部化
- 确定性
- 一致性
- 完备性
- 可验证性、自顶向下、逐层分解
- 研究内容
- 软件开发技术
- 软件工程管理
- 软件生命周期
- 定义:从
提出、实现、使用维护到停止使用退役
的过程 - 阶段
- 软件定义阶段
- 问题定义
- 可行性研究
- 需求分析
- 软件开发期
- 概要设计
- 详细设计
- 实现和测试
- 运行维护期
- 运行维护阶段
- 软件定义阶段
- 定义:从
- 软件需求分析
- 内容: 需求获取、需求分析、编写需求规格说明书、需求评审
- 方法:结构化分析方法&面向对象的分析方法
- 需求规格说明书的作用
- 便于用户、开发人员理解和交流
- 反映出用户问题的结构,可以作为软件开发工作的基础和依据
- 作为确认测试和验收测试的依据
- 软件设计
- 工程管理角度
概要设计
- 设计软件系统结构
- 设计数据结构及数据库
- 编写设计概要文档
- 概要设计文档审评
详细设计(过程设计)
- 图形工具:程序流程图、N-S、PAD、HIPO
- 表格工具:判定表
- 语言工具:PDL(伪码)
程序流程图中图形的含义:箭头——控制流、矩形——加工、菱形——判断
- 技术观点分析
- 结构设计
- 数据设计
- 过程设计
- 基本原理
- 抽象
- 模块化
- 信息隐蔽
- 模块独立性
- 评价设计好坏的重要标准
- 衡量方法
高内聚低耦合
- 工程管理角度
- 软件测试
- 目的:查找错误
- 分类方法
- 是否执行被测试软件
- 静态测试 不执行(人工)
- 动态测试 执行(计算机测试发现错误)
- 功能
白盒测试
(结构设计、逻辑驱动测试) 程序内部进行(逻辑覆盖、基本路径测试
)黑盒测试
(功能测试、驱动测试)(等价类划分法、边界分析法、错误推测法、因果图
)
- 是否执行被测试软件
- 三要素
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yu Hui's Blog!
评论