全国计算机二级c语言考试 ：公共基础篇

以下知识点皆为书中必考知识点必须牢记(此书不必购买，只看此页足矣)

1.数据结构和算法            2.程序设计基础               3.软件工程基础          4.数据库系统

1：必背知识点讲解（如果难以理解就死记硬背！！！！肯定会考到的）红色备注为重点必须记住

第一章：

1.1.1

          算法的基本概念：所谓算法是解题方案准确而完整的描述

          算法的基本特征：1.可行性   2.确定性   3.有穷性   4.拥有足够的情报

          算法的基本要素：1.是对数据对象的运算操作 2.算法的控制结构

          算法设计的基本方法：1.列举法 2.归纳法 3.递推 4.递归 5.减半递推技术 6.回溯法

1.1.2   

          算法的时间复杂度：是指执行算法所需要的计算工作量.

1.2.1

          数据结构的基本概念：利用计算机进行数据处理是计算机应用的一个重要领域。

          数据结构主要研究和讨论的问题：1.数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构  

                                                                                a.线性结构线性表             b.非线性结构

                                                         2.在对数据处理时，数据元素在计算机之间的存储关系，即数据的存储结构

                                                                                a.顺序存储                        b.链式存储

                                                         3.对各种数据结构进行的运算

          数据的逻辑结构：是指反映元素之间关系的数据元素集合的表示（实际上是数据元素之间的前后件关系） 

                                                                      (首结点或根结点)a->b->c（尾结点）

          一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。而采用不同的存储结构，其数据处理的效率是不同的

1.2.3

            数据结构一般分为两个类型：线性结构与非线性结构。

            线性结构（线性表）的满足条件：1.有且只有一个根结点 2.每一个结点最多有一个前件，也最多有一个后件。

            如果说一个数据结构不是线性结构，则称之为非线性结构。

            线性链表：线性表的链性存储结构称之为线性链表。

1.5

            栈和队列（线性结构）

          栈：

                   基本点：1.第一个空间也存放数据 2.数据进出情况（先进后出，后进先出）

                    结论：1.数据进栈出栈都是在栈顶进行的     2.数据的进栈出栈都是用栈顶指针表示

        队列：

                     基本点：1第一个空间不放数据  2.数据的进出情况（先进先出，后进后出）

                     结论：  1.数据从队尾入队，从队首出队    2.数据的插入用队尾指针表示 数据的删除用队首指针表示

1.6

            树：树是简单的非线性结构。

            满二叉树：除了最后一层外，所有的结点都具有两个子结点。（每一层树结点数都是最大值）

                                   计算公式：在满二叉树的k层上有2^k-1个结点，深度为m的满二叉树有2^m-1

            完全二叉树：除最后一层外，每一层上的所有结点都达到最大值，在最后一层上只缺少右边的若干结点（如图D错误处）。

_1.7

            查找技术                                                             时间复杂度

        1.        顺序查找                                                                               n

        2.      二分法查找                                                                            log₂n                   

              排序技术                                                           比较次数

    交换类排序法

       1.      冒泡排序                                                                                 n（n-1）/2

       2.     快速排序                                                                                  n（n-1）/2（最坏的情况下等于冒泡排序）

    插入类排序法

       3.    简单插入排序法                                                                         n（n-1）/2

       4.     希尔排序法                                                                                O（n^1.5）

    选择类排序法

       5.    简单选择排序法                                                                           n（n-1）/2

       6.    堆排序法                                                                                           O(nlog₂n)        

第二章：

2.1

   程序设计的风格：清晰第一，效率第二

   源程序文档化：1.符号名的命名

                 2.程序注释（注释分为：a序言性注释 b.功能性注释）

                3.视觉组织

  结构化程序设计方法主要原则：

       1.自顶向下

       2.逐步求精

       3.模块化

       4.限制使用goto语句

结构化程序设计的基本结构与特点

      1顺序结构

      2.选择结构

      3.重复结构

2.3.2

  面向对象的方法的基本概念

1对象： 属性和结构的封装体  （a.属性：静态特点 b.结构：动态特点）

                     对象基本特点：a.标识唯一性 b.分类性 c.多态性 d.封装性 e.模块独立性好

2.类和实例：类是具有共同属性，共同方法的对象集合（对象是类的一个实例）

3.消息：对象间传递信息的手段

4.继承：类和对象间对属性和方法的有效的共享机制

5.多态性

第三章

      软件由两个部分组成：1.机器可执行的程序和数据  2.机器不可执行的与软件开发，运行，维护，使用等有关文档

软件危机和软件工程：为了解决软件危机在软件开发和维护过程中尽可能的使用工程化原理来指导工作（软件工程的目的）

      软件工程三要素：1.方法 2.工具 3.过程

3.1.

      软件工程的目标：1.软件开发技术 2.软件工程管理

      软件工程原则：1.抽象 2.信息隐蔽 3.模块化 4.局部化 5.确定性 6.一致性 7.完备性 8.可验证性

3.2

      需求分析的步骤：1.需求获取  2.需求分析  3.编写需求规格说明书  4.需求评审

      需求分析的方法：1结构化分析方法（a.面向数据流的结构化分析方法SA    b.面向数据结构的Jackson方法JSD   c.面向数据结构化数据系统开发方法DSSD）

                      2面向对象的分析方法OOA

3.2

      结构化分析常用工具：1.数据流图（DFD-Data Flow Diagram）

                                      2.数据字典（DD-Data Dictionary）（数据字典是结构化分析方法的核心）

                                      3.判定树

                                      4.判定表

3.3软件设计遵循的基本原理

                          1.抽象 2.模块化 3.信息隐蔽性 4.模块独立性 （高内聚低耦合）

                          一般优秀的软件设计，应尽量做到高内聚低耦合  有利于提高模块独立性

          设计准则：1.提高模块独立性 2.模块规模适中

          常用软件设计工具：

                          图形工具：程序流程图（PFD-Program For Gir），N-S，PAD,HIPO

                          表格工具：判定表

                          语言工具：PDL（伪码）

3.4软件测试的技术和方法

      1静态测试和动态测试

      白盒测试(结构测试或逻辑驱动测试)的基本原则：保证所测模块中每一个独立的路径至少执行一次

      白盒测试主要方法：1.逻辑覆盖 2.基本路径测试

      黑盒测试（功能测试或数据驱动测试）的方法：等价类策划分法….（主要用于软件确认测试）

      软件测试的实施：1单元测试  2.集成测试   3.确认测试  4.系统测试

3.5程序调试（目的：尽可能多的改正错误）

      调试方法：1强行排错法  2.回溯法  3.原因排除法

第四章

        数据库（Data Base ，DB）

       数据库管理系统（Data Management System，DBMS）:数据库管理系统是数据库系统的核心     

       数据库发展三个阶段：1.人工管理阶段 2.文件系统阶段 3.数据库系统阶段

       数据库系统的基本特点

     三个世界四种模型： 现实世界  信息世界   计算机世界             E-R模型   层次模型   网状模型 关系模型

    E-R图向关系模式转换：后续做题了解