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

1、算法执行的结果要能够达到预期的目的。分析方法： 平均性态分析，最坏情况复杂性分算法执行的结果要能够达到预期的目的。分析方法： 平均性态分析，最坏情况复杂性分一、算法算法：指解题方案的准确而完整的描述。算法的特征：可行性：算法中的每一个步骤必须能实现，确定性有穷性拥有足够的情报算法设计的基本方法：列举法归纳法递推递归：直接递归，间接递归减半递推回溯法算法的复杂度：时间复杂度和空间复杂度 时间复杂度：执行算法所需要的计算工作量。析空间复杂度：执行算法所需要的内存空间 数据结构：是指相互有关联的数据元素的集合 主要研究：数据的逻辑结构，数据的存储结构，对各种数据结构进行的运算 主要目的：提高数据处理

2、的效率数据的逻辑结构：反映数据元素之间逻辑关系的数据结构数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式数据结构分为线性结构和非线性结构。线性结构： 1.有且只有一个根结点 2.每个结点最多有一个前件，最多有一个后件。 矩阵也是一种线性表。线性表是一种线性结构。由若干个数据项组成的数据元素成为记录， 由多个记录构成的线性表称为文件。 每一个学生 的情况是一个记录，学生情况的登记表是一个文件。数据项是最小的数据元素。线性表的顺序存储：线性表中所有元素所占的存储空间是连续的线性表中各数据元素在存储空间中是按逻辑顺序依次存放的栈是一种特殊的线性表。 一端是封闭的， 不允许进行插入和删除元素

3、。 允许插入和删除的一端为栈顶。栈是按照“先进后出”的原则。Top 指针指向栈顶， bottom 指针指向栈底，指针 top 反映了栈中元素的变化情况。 Top=0 表示栈空， top=m 表示栈满。入栈，退栈和读栈顶元素。 队列：指允许在一端进行插入、而在另一端进行删除的线性表。“先进先出”的线性表。队尾指针 rear 指向队尾元素，排头指针 front 指向排头元素的前一个位置。 插入元素只涉及指针 rear 的变化，删除元素只涉及指针 front 的变化。 循环队列的初始状态唯恐，即 rear=front=m 每进行一次入队运算，队尾指针进一，当 rear=m+1 时，置 rear=1.

4、 每进行一次退队运算，排头指针进一，当 front=m+1 时，置 front=1 ； 当 front=rear 时，不能确定是队列满还是队列空。线性表顺序存储结构的缺点：插入与删除运算的效率很低存储空间不便于扩充不便于对存储空间的动态分配。链式存储结构： 一部分用于存放数据元素值， 称为数据域，另一部分用于存放指针，称为指 针域。链式存储结构中， 存储数据的存储空间可以不连续， 数据结点的存储数据和数据元素之间的 逻辑关系可以不一致。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。线性表的链式存储结构称为线性链表。树是一种简单的非线性结构。一个结点所拥有的后件个数称为该结点的度。所

5、有结点中的最大的度称为树的度。树的结点数为树中所有结点的度之和再加 1.树的最大层次称为树的深度。树在计算机中通常用多重链表表示。二叉树：非空二叉树只有一个根结点每一个结点最多有两棵子树，分别称为该结点的左子树和右子树。二叉树的基本性质：在二叉树的第 k 层上，最多有 2 的 k-1 次方个结点。深度为 m 的二叉树，最多有 2 的 m 次方减 1 个结点。在任意一棵二叉树中，度为 0 的结点总是比度为 2 的结点多一个。层上只缺少右边的具有 n 个结点的二叉树，其深度至少为 log2 (n )+1 。 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树： 除最后一层外，

6、每一层上的结点数均达到最大值， 在最后 若干结点。层上只缺少右边的具有 n 个结点的完全二叉树的深度为 log2(n)+1. 二叉树通常采用链式存储结构。二叉树的链式存储结构称为二叉链表。 二叉树的遍历：指不重复地访问二叉树中的所有结点。前序遍历：访问根结点前序遍历左子树前序遍历右子树 中序遍历：中序遍历左子树访问根结点中序遍历右子树 后序遍历：后序遍历左子树后序遍历右子树访问根结点知道某二叉树的后序序列和中序序列， 可以唯一的恢复该二叉树， 只知道前序序列和中序序 列可以唯一的恢复二叉树，只知道前序序列和后序序列，不能唯一的恢复二叉树。顺序查找：最坏情况下为 n 次二分法查找只能用于顺序存储

7、的有序表，最坏情况下查找 log2（n）无序表只能用顺序查找，有序表的链式存储结构也只能用顺序查找。排序：冒泡排序法： n（n-1 ） /2快速排序法： n（n-1 ） /2简单插入排序： n（ n-1 ）/2希尔排序法： n 的 1.5 次方简单选择排序法： n（n-1 ）/2堆排序： nlog2 （n ）二、程序设计基础结构化程序设计和面向对象的程序设计。注重的因素：源程序文档化数据说明的方法语句的结构输入和输出结构化程序设计的原则：自顶向下逐步求精模块化限制使用 goto 语句结构化程序的基本结构：顺序结构选择结构循环结构面向对象方法的优点：与人类习惯的思维方法一致稳定性好可重用性好易于

8、开发大型软件产品可维护性好对象的基本特点：标识唯一性分类型多态性封装性属性是对象所包含的信息。类是具有共同属性、共同方法的对象的集合。消息是一个实例与另一实例之间传递的消息。 继承是使用已有的类定义作为基础建立新类的定义技术。 继承分为单继承和多重继承 对象，消息，类和实例，继承，多态性。三、软件工程基础计算机软件是包括程序、数据及相关文档的完整集合。软件的特点：是一种逻辑实体，而不是物理实体，具有抽象性。软件没有明显的制作过程软件不存在磨损、老化问题软件的开发和运行对计算机系统具有依赖性。软件的复杂性高，成本昂贵软件开发涉及诸多的社会因素。软件危机的主要表现：软件需求的增长得不到满足软件开发

9、成本和进度无法控制软件质量难以保证软件不可维护或维护程度非常低软件的成本不断提高软件开发生产率的提高赶不上硬件的发展和应用需求的增长。归结为：成本、质量、生产率的问题。软件工程三要素：方法、工具、过程。工程项目的三个目标：进度、经费和质量的目标。软件过程的四个基本活动：软件规格说明软件开发或软件设计与实现软件确认软件演进软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。 分为软件定义、软件开发和软件运行维护三个阶段。需求分析的工作：需求获取需求分析编写需求规格说明书需求评审需求分析方法：结构化分析方法：数据流图（ DFD ）和数据字典（ DD ）为主要工具。面向对象的分析方法建

10、立数据流图的步骤：由外向里自顶向下逐层分解箭头指数据流。软件需求规格说明书：便于用户、开发人员进行理解和交流反映出用户问题的结构，可以作为软件开发工作的基础和依据作为确认测试和验收的依据为成本估算和编制计划进度提供基础软件不断改进的基础高内聚低耦合原则。 白盒测试也称结构测试或逻辑驱动测试，白盒法是穷举路经测试。 主要方法：逻辑覆盖，基本路径测试。黑盒测试也称功能测试或数据驱动测试。主要方法：等价类划分法、边界值分析法、错误推测法、因果图等。 软件测试过程：单元测试、集成测试、验收测试和系统测试 软件调试方法：强行排错法回溯法原因排除法四、数据库设计基础数据语言：数据定义语言数据操纵语言数据控制语言数据库管理员的主要工作：数据库设计数据库维护改善系统性能，提高系统效率数据库发展的三个阶段：人工管理阶段文件系统阶段数据库系统阶段 数据库系统的特点：1. 数据的集成性2. 数据的高共享性与低冗余性数据独立性数据统一管理与控制三级模式：1. 概念模式：描述数据的概念记录类型及他们间的关系2. 外模式：也称子模式或用户模式，给出每个用户的局部数据描述内模式：又称物理模式，给出了数