计算机二级c语言公共基础知识.docx

一、 算法
算法：指解题方案的准确而完整的描述。
算法的特征：
1.可行性：算法中的每一个步骤必须能实现，算法执行的结果要能够达到预期的目的。
2.确定性
3.有穷性
4.拥有足够的情报
算法设计的基本方法：
1. 列举法
2. 归纳法
3. 递推
4. 递归：直接递归，间接递归
5. 减半递推
6. 回溯法
算法的复杂度：时间复杂度与空间复杂度
时间复杂度：执行算法所需要的计算工作量。分析方法：平均性态分析，最坏情况复杂性分析
空间复杂度：执行算法所需要的内存空间
数据结构：是指相互有关联的数据元素的集合
主要研究：数据的逻辑结构，数据的存储结构，对各种数据结构进行的运算
主要目的：提高数据处理的效率
数据的逻辑结构：反映数据元素之间逻辑关系的数据结构
数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式
数据结构分为线性结构与非线性结构。
线性结构：1.有且只有一个根结点2.每个结点最多有一个前件，最多有一个后件。
矩阵也是一种线性表。线性表是一种线性结构。
由若干个数据项组成的数据元素成为记录，由多个记录构成的线性表称为文件。每一个学生的情况是一个记录，学生情况的登记表是一个文件。数据项是最小的数据元素。
线性表的顺序存储：
1. 线性表中所有元素所占的存储空间是连续的
2. 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
栈是一种特殊的线性表。一端是封闭的，不允许进行插入与删除元素。允许插入与删除的一端为栈顶。
栈是按照“先进后出”的原则。
Top指针指向栈顶，bottom指针指向栈底，指针top反映了栈中元素的变化情况。
Top=0表示栈空，top=m表示栈满。
入栈，退栈与读栈顶元素。
队列：指允许在一端进行插入、而在另一端进行删除的线性表。
“先进先出”的线性表。
队尾指针rear指向队尾元素，排头指针front指向排头元素的前一个位置。
插入元素只涉及指针rear的变化，删除元素只涉及指针front的变化。
循环队列的初始状态唯恐，即rear=front=m
每进行一次入队运算，队尾指针进一，当rear=m+1时，置rear=1.
每进行一次退队运算，排头指针进一，当front=m+1时，置front=1；
当front=rear时，不能确定是队列满还是队列空。
线性表顺序存储结构的缺点：
1. 插入与删除运算的效率很低
2. 存储空间不便于扩充
3. 不便于对存储空间的动态分配。
链式存储结构：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为指针域。
链式存储结构中，存储数据的存储空间可以不连续，数据结点的存储数据与数据元素之间的逻辑关系可以不一致。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。
线性表的链式存储结构称为线性链表。
树是一种简单的非线性结构。
一个结点所拥有的后件个数称为该结点的度。
所有结点中的最大的度称为树的度。
树的结点数为树中所有结点的度之与再加1.
树的最大层次称为树的深度。
树在计算机中通常用多重链表表示。
二叉树：
1. 非空二叉树只有一个根结点
2. 每一个结点最多有两棵子树，分别称为该结点的左子树与右子树。
二叉树的基本性质：
1. 在二叉树的第k层上，最多有2的k-1次方个结点。
2. 深度为m的二叉树，最多有2的m次方减1个结点。
3. 在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个。
4. 具有n个结点的二叉树，其深度至少为[log2（n）]+1。
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
具有n个结点的完全二叉树的深度为[log2(n)]+1.
二叉树通常采用链式存储结构。
二叉树的链式存储结构称为二叉链表。
二叉树的遍历：指不重复地访问二叉树中的所有结点。
前序遍历：
1. 访问根结点
2. 前序遍历左子树
3. 前序遍历右子树
中序遍历：
1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树
后序遍历：
1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点
知道某二叉树的后序序列与中序序列，可以唯一的恢复该二叉树，只知道前序序列与中序序列可以唯一的恢复二叉树，只知道前序序列与后序序列，不能唯一的恢复二叉树。
顺序查找：最坏情况下为n次
二分法查找只能用于顺序存储的有序表，最坏情况下查找log2(n)
无序表只能用顺序查找，有序表的链式存储结构也只能用顺序查找。
排序：
1. 冒泡排序法：n（n-1）/2
2. 快速排序法：n（n-1）/2
3. 简单插入排序：n（n-1）/2
4. 希尔排序法：n的1.5次方
5. 简单选择排序法：n（n-1）/2
6. 堆排序：nlog2（n）
二、 程序设计基础
结构化程序设计与面向对象的程序设计。
注重的因素：
1. 源程序文档化
2. 数据说明的方法
3. 语句的结构
4. 输入与输出
结构化程序设计的原则：
1. 自顶向下
2. 逐步求精
3. 模块化
4. 限制使用goto语句
结构化程序的基本结构：
1. 顺序结构
2. 选择结构
3. 循环结构
面向对象方法的优点：
1. 与人类习惯的思维方法一致
2. 稳定性好
3. 可重用性好
4. 易于开发大型软件产品
5. 可维护性好
对象的基本特点：
1. 标识唯一性
2. 分类型
3. 多态性
4. 封装性
属性是对象所包含的信息。
类是具有共同属性、共同方法的对象的集合。
消息是一个实例与另一实例之间传递的消息。
继承是使用已有的类定义作为基础建立新类的定义技术。
继承分为单继承与多重继承
对象，消息，类与实例，继承，多态性。
三、 软件工程基础
计算机软件是包括程序、数据及相关文档的完整集合。
软件的特点：
1. 是一种逻辑实体，而不是物理实体，具有抽象性。
2. 软件没有明显的制作过程
3. 软件不存在磨损、老化问题
4. 软件的开发与运行对计算机系统具有依赖性。
5. 软件的复杂性高，成本昂贵
6. 软件开发涉及诸多的社会因素。
软件危机的主要表现：
1. 软件需求的增长得不到满足
2. 软件开发成本与进度无法控制
3. 软件质量难以保证
4. 软件不可维护或维护程度非常低
5. 软件的成本不断提高
6. 软件开发生产率的提高赶不上硬件的发展与应用需求的增长。
归结为：成本、质量、生产率的问题。
软件工程三要素：方法、工具、过程。
工程项目的三个目标：进度、经费与质量的目标。
软件过程的四个基本活动：
1. 软件规格说明
2. 软件开发或软件设计与实现
3. 软件确认
4. 软件演进
软件生命周期：
软件产品从提出、实现、使用维护到停止使用退役的过程。
分为软件定义、软件开发与软件运行维护三个阶段。
需求分析的工作：
1. 需求获取
2. 需求分析
3. 编写需求规格说明书
4. 需求评审
需求分析方法：
1.结构化分析方法：数据流图（DFD）与数据字典（DD）为主要工具。
2.面向对象的分析方法
建立数据流图的步骤：
1. 由外向里
2. 自顶向下
3. 逐层分解
箭头指数据流。
软件需求规格说明书：
1. 便于用户、开发人员进行理解与交流
2. 反映出用户问题的结构，可以作为软件开发工作的基础与依据
3. 作为确认测试与验收的依据
4. 为成本估算与编制计划进度提供基础
5. 软件不断改进的基础
高内聚低耦合原则。
白盒测试也称结构测试或逻辑驱动测试，白盒法是穷举路经测试。
主要方法：逻辑覆盖，基本路径测试。
黑盒测试也称功能测试或数据驱动测试。
主要方法：等价类划分法、边界值分析法、错误推测法、因果图等。
软件测试过程：单元测试、集成测试、验收测试与系统测试
软件调试方法：
1. 强行排错法
2. 回溯法
3. 原因排除法
四、 数据库设计基础
数据语言：
1. 数据定义语言
2. 数据操纵语言
3. 数据控制语言
数据库管理员的主要工作：
1. 数据库设计
2. 数据库维护
3. 改善系统性能，提高系统效率
数据库发展的三个阶段：
1. 人工管理阶段
2. 文件系统阶段
3. 数据库系统阶段
数据库系统的特点：
1. 数据的集成性
2. 数据的高共享性与低冗余性
3. 数据独立性
4. 数据统一管理与控制
三级模式：
1. 概念模式：描述数据的概念记录类型及他们间的关系
2. 外模式：也称子模式或用户模式，给出每个用户的局部数据描述
3. 内模式：又称物理模式，给出了数据库物理存储结构与物理存取方法
数据库系统的两级映射：保证了数据库系统中数据的独立性
概念模式到内模式的映射
外模式到概念模式的映射
数据模型所描述的部分：数据结构、数据操作，数据约束
分为概念数据模型，逻辑数据模型，物理数据模型
E- R模型为概念模型：实体，属性，联系
数据约束：
1. 实体完整性约束
2. 参照完整性约束
3. 用户定义的完整性
第 14 页