计算机二级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）/22. 快速排序法：n（n-1）/23. 简单插入排序：n（n-1）/24. 希尔排序法：n的1.5次方5. 简单选择排序法：n（n-1）/26. 堆排序：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 页