导图社区 公共基础知识
- 相似推荐
- 大纲
公共基础知识
数据结构与算法
算法
基本特征
1. 可行性
2. 确定性
3. 有穷性
4. 拥有足够的情报
算法复杂度
时间复杂度
执行算法所需要的计算工作量
空间复杂度
执行算法所需要的内存空间
数据结构
线性结构
（非空）线性结构
有且只有一个根节点
每一个节点最多有一个前件，也最多有一个后件
非线性结构
栈
栈和一般线性表的表现方式类似，通常可以采用顺序方式和链接方式来实现。
原则
先进后出
队列
原则
先进先出
循环队列运算
队列的顺序储存结构一般采用循环队列的形式
初始状态为空，当front=rear=m时，不能确定队列满还是队列空。
一般会添加一个标志s来区分队列满还是队列空。当s=0时，表示对队列为空；当s=1时且front=rear时表示队列满。
线性链表
树与二叉树
树
父节点（根）
子节点和叶子节点
度
一个节点所拥有的后件个数；所有节点中最大的度称为树的度。
深度
子树
二叉树
特点
二叉树可以为空，空二叉树没有节点，非空二叉树只有一个根节点
每节点最多有两棵子树
二叉树有左右之分，顺序不能任意颠倒
性质
任何一棵二叉树，叶子结点（度为0）总比度为2的节点多一个
满二叉树和完全二叉树
满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树
满二叉树
除最后一层外，每一层所有节点都有2个子节点
完全二叉树
除最后一层外，每一层上的节点均达到最大值，在最后一层上缺少右边
遍历
前序遍历
中序遍历
后序遍历
查找技术
顺序查找
二分法查找
排序技术
效率由高到低
堆排序，最坏情况nlog（。2）n
快速排序，最坏情况n（n-1）/2
简单插入排序，最坏情况n（n-1）/2
简单选择排序，最坏情况n（n-1）/2
冒泡排序法，n（n-1）/2
希尔排序
程序设计风格
清晰第一，效率第二
结构化程序设计
原则
自顶向下
逐步且精
模块化
限制使用goto语句
基本结构
顺序结构
选择结构
循环结构
面向对象（由数据、方法构成）的程序设计
对象的基本特点
标识唯一性
分类性
多态性
同一操作可以是不同对象的行为
封装性
模块独立性好
类和实例
消息
继承
多态性
软件工程基础
基本概念
软件的分类
系统软件
应用软件
支撑软件
软件工程三要素
方法
工具
过程
软件工程原则
抽象
信息隐蔽
模块化
局部化
确定性
一致性
完备性
可验证性
软件生命周期
三时期八阶段
软件定义期
问题定义
可行性分析
需求分析
软件开发期
概要设计
详细设计
实现
测试
运行维护期
使用和维护
退役
设计及方法
软件设计步骤
软件结构设计
数据设计
接口设计
过程设计
软件设计最好达到
高内聚，低耦合
基本图幅元素
数据流图
结构图
软件测试
静态测试（主）和动态测试（辅）
白盒测试和黑盒测试
白盒测试
逻辑覆盖测试
基本路径测试
黑盒测试
等价类划分法
边界值分析法
错误推测法
因果图
测试实施
单元测试
集成测试
确认测试（验收测试）
系统测试
程序的调试、测试
调试：诊断和改进程序中的错误
测试：发现软件中的错误
数据库管理系统
功能
数据模式定义
数据存取的物理构建
数据操纵
数据完整性
安全性的定义与检查
数据的服务
数据语言
数据定义语言
数据操纵语言
数据控制语言
三级模式结构
内模式
概念模式
外模式（用户模式）
数据模型
三要素
数据结构
数据操纵
数据约束
E-R模型
基本概念：实体（矩形）、联系（菱形）、属性(椭圆）
关系模型
（二维表）
关系
属性
值域
元组
候选码
外键或外码
关系代数
差运算
交运算
并运算
笛卡尔积运算
投影运算
选择运算
除运算
连接运算
数据库设计
满足最低要求的叫第一范式，称1NF
计算机基础
第一台计算机ENIAC,美国，冯·诺依曼
两级映射：逻辑独立性、物理独立性