C语言二级公共基础知识讲义

全国计算机等级考试NationalComputerRankExamination二级·公共基础知识全国计算机等级考试1二级公共基础知识二级公共基础知识考试内容数据结构和算法程序设计基础软件工程数据库设计基础全国计算机等级考试2二级公共基础知识1、二级公共基础的考试方式为笔试，与各科语言的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、公共基础知识有10道选择题和5道填空题。二级公共基础知识考试方式全国计算机等级考试3二级公共基础知识理解基本概念多做练习适当记忆一些名词与所学程序设计语言结合起来理解二级公共基础知识学习方法全国计算机等级考试4二级公共基础知识第一章数据结构和算法全国计算机等级考试5二级公共基础知识本章知识要点算法算法的定义算法的特征算法复杂度数据结构数据结构的定义逻辑结构和物理结构线性结构和非线性结构顺序表、链表、堆栈队列、循环队列、树算法的基本要素全国计算机等级考试6二级公共基础知识算法是对特定问题求解步骤的一种描述。一、算法算法的特性：

（1）有穷性：算法必须在有限的次数内完成。（2）确定性：算法的每一步必须是明确的。（3）可行性：算法的每一步必须是可以实现的。

（4）拥有足够的情报：算法必须有一定的输入和输出。全国计算机等级考试7二级公共基础知识算法的基本要素：（1）对数据对象的运算和操作：A.算术运算B.逻辑运算C.关系运算D.数据传输（2）算法的控制结构：A.顺序结构B.选择结构C.循环结构全国计算机等级考试8二级公共基础知识算法的复杂度：衡量算法优劣的量。（1）时间复杂度：算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间同步增长，称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关，是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工作量。（2）空间复杂度：执行算法所需要的内存空间。全国计算机等级考试9二级公共基础知识二、数据结构数据结构主要研究两方面的问题：（1）数据本身。（2）数据之间的前后件关系。数据结构数据本身数据之间的前后件关系数据结构表示为：DS={D，S}例：D={春，夏，秋，冬}S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}全国计算机等级考试10二级公共基础知识数据的结构分为：（1）物理结构：数据在计算机存储介质中真正存储的结构，也被称为“存储结构”（2）逻辑结构：人们所理解的数据之间的结构，可以用图示的方法绘画出来的数据之间的结构。例：一个班由35名同学，他们的座位牌号就是物理结构，一次考试的排名是逻辑结构。1注意：逻辑结构和物理结构没有必然的联系，也不一定是一一对应的。全国计算机等级考试11二级公共基础知识数据的结构分为：（1）线性结构：非空数据结构同时满足以下两个条件就是线性结构：A.有且仅有一个根结点；B.除头结点和尾结点外，任何结点有且仅有一个前件和一个后件。（2）非线性结构：除了线性结构都是非线性结构。全国计算机等级考试12二级公共基础知识全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种：线性表堆栈队列循环队列线性链表树和二叉树线性结构物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构不相同物理结构和逻辑结构不相同非线性结构全国计算机等级考试13二级公共基础知识1020304050607080三、顺序表：顺序表就是数组1、顺序表也叫做线性表，属于线性结构。线性表的逻辑结构和物理结构相同。2、特点：（1）有且仅有一个头结点（根节点）和尾结点。（2）任意其他结点至多有一个前件，一个后件。（3）头结点没有前件，尾结点没有后件。全国计算机等级考试14二级公共基础知识四、堆栈栈顶top栈底入栈/压入出栈/弹出1、定义：只允许在栈顶位置插入数据和删除数据的线性结构是堆栈，简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构相同。4、特点：先进后出，后进先出所以堆栈也叫做先进后出表（FILO）5、堆栈具备存储功能：函数的递归调用和表达式求解都用到了堆栈。全国计算机等级考试15二级公共基础知识入栈顺序：a、b、c、d、e、f栈空abacbabadba…………..入a入b入c出c入d模拟堆栈的数据出入过程：全国计算机等级考试16二级公共基础知识【典型题型】假设一个堆栈，入栈顺序为abcde，认为在任何时刻均允许出栈，下列选项中不可能的出栈顺序为：A）abcde（可能）B）edcba（可能）C）cdeba（可能）D）cdeab（不可能）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（）A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意顺序栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（）A)ABCED B)DCBEAC)DBCEA D)CDABE全国计算机等级考试17二级公共基础知识五、队列队头front队尾rear入队出队1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义：入队操作发生在队尾，出队操作发生在队头。4、特点：先进先出，后进后出，所以队列也叫做先进先出表（FIFO）。全国计算机等级考试18二级公共基础知识六、循环队列rearfront全国计算机等级考试19二级公共基础知识入队顺序：a、b、c、d、e、f模拟循环队列的数据出入过程：循环队列空front=rearrearfrontafrontrear数据a入队afrontrearb数据b入队frontrearb数据a出队全国计算机等级考试20二级公共基础知识七、线性链表1、链表属于线性结构。2、链表的逻辑结构和物理结构不相同。3、线性链表由结点组成：每个结点有两个区域：数据域，指针域。A.数据域，用来存储数据。B.指针域，用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。链表的结点数据域指针域12345^单链表全国计算机等级考试21二级公共基础知识链表的种类：单链表、循环链表、双向链表。1234512345循环链表双向链表^12345^全国计算机等级考试22二级公共基础知识八、树与二叉树1、树属于非线性结构。2、树的逻辑结构和物理结构不相同。3、树有且仅有一个根节点。根节点xeoqkbg全国计算机等级考试23二级公共基础知识二叉树：每个结点最多分两叉的有序树。二叉树二叉树的术语有序树与无序树二叉树的五种基本结构满二叉树和完全二叉树二叉树的计算二叉树的遍历全国计算机等级考试24二级公共基础知识1、二叉树的术语：根节点xeoqbg叶子节点A.结点、根节点、叶子节点：（1）构成树的基本结构是结点。（2）没有父结点的结点是根节点。（3）没有子结点的结点是叶子节点（度为0的结点）。B.结点的度：结点子结点的个数。C.树的度：树中度数最大的结点的度就是树的度。D.树的高度/层数：树有多少层。E.父结点、子结点、双亲结点、孩子结点、左孩子、右孩子、兄弟结点、堂兄结点。全国计算机等级考试25二级公共基础知识2、有序树与无序树：eABeBA二叉树和度为二的树的区别：A.二叉树是有序树，度为二的树是普通树，属于无序树。B.二叉树允许为空，度为二的数至少有三个结点。【普通树不允许为空，至少有一个结点】全国计算机等级考试26二级公共基础知识3、二叉树的五种基本结构：aaabcbab空二叉树只有一个结点的二叉树有两个结点的二叉树有三个结点的二叉树全国计算机等级考试27二级公共基础知识4、满二叉树和完全二叉树：A.满二叉树：二叉树的每一层均具备该层最大结点个数。（即：不具备度为1的结点）B.完全二叉树：满二叉树是一个特殊的完全二叉树。将所有结点自上向下、自左向右编号，结点编号连续而不缺失。xeoqkbgxeoqkb满二叉树完全二叉树123456全国计算机等级考试28二级公共基础知识5、二叉树的计算：A.二叉树第n层的最大结点个数：2n-1。B.n层满二叉树的结点个数：2n-1。C.n层完全二叉树的最小结点个数：2n-1。n层完全二叉树的最大结点个数：2n-1。D.度为0的结点个数表示为n0，同理，n1表示度为1的结点个数，n2表示度为2的结点个数。则，对于任意二叉树都有：n0=n2+1。E.结点编号：任意结点编号n，其左孩子为2n，其右孩子为2n+1。xeoqkbg1234567全国计算机等级考试29二级公共基础知识填空题：设一棵完全二叉树共有700个结点，则在该二叉树中有

个叶子结点二叉树的结点共有三种：度为0的叶子结点、度为1的结点和度为2的结点。设度为0的叶子结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，则：

n0+n1+n2=700 （1）根据二叉树性质：叶子结点个数比度为2的结点个数多1，即：

n0=n2+1 （2）将（2）式带入（1）式，所以：

n0+n1+n0-1=7002n0=701-n1完全二叉树总结点个数为偶数，则度为1的结点个数为1；完全二叉树的总结点个数为奇数，则度为1的结点个数为0。所以：2n0=701-1，即n0=350。全国计算机等级考试30二级公共基础知识6、二叉树的遍历：A.前/先（根）序遍历，GLR。【根节点为序列开头】B.中（根）序遍历，LGR。【没有左子树，根节点为开头；没有右子树，根节点为结尾】【左右子树均有，根节点的位置位于左子树结点个数之和+1】C.后（根）序遍历，LRG。【根节点为序列结尾】xeoqbg先序序列：xeqbog中序序列：qebxog后序序列：qbegox全国计算机等级考试31二级公共基础知识第二章程序设计基础全国计算机等级考试32二级公共基础知识本章知识要点面向过程的程序设计结构化程序设计模块化程序设计面向对象的程序设计对象的定义对象的属性和方法类和实例的派生与继承消息与多态性全国计算机等级考试33二级公共基础知识一、程序设计方法1、面向过程的程序设计：C语言、BASIC语言等。（1）结构化程序设计：顺序、选择、循环。三大结构（顺序、选择、循环）可以解决所有的问题，和问题的规模没有关系。（2）模块化程序设计：利用将程序分解的方法，将复杂的问题简单化，将单一的问题分成多个模块独立解决。C语言：模块就是函数。VB语言：模块就是模块、子例程、子程序。VFP数据库：模块就是子程序。Access数据库：模块就是宏、事件代码。2、面向对象的程序设计：VB、VFP、Java、Delphi等。全国计算机等级考试34二级公共基础知识二、程序设计风格1.源程序文档化选择标示符的名字注释（序言性和功能性注释）程序的视觉组织2.数据说明的方法显式地说明一切变量数据说明的次序应该规范化说明语句中变量安排有序化对复杂数据结构应注释说明3.语句的结构每条语句简单明了尽量不用或少用GOTO语句尽量只采用3种基本控制结构编程4.输入和输出对输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表全国计算机等级考试35二级公共基础知识三、结构化程序设计20世纪70年代提出了结构化程序设计

（StructuredProgramming）结构化程序设计的原则：（1）自顶向下。（2）逐步求精。（3）模块化。（4）限制使用goto语句。结构化程序设计的基本结构：（1）顺序结构。（2）选择结构。（3）重复结构。结构化程序设计主要强调程序的易读性。全国计算机等级考试36二级公共基础知识利用图示表示顺序结构ABAB程序流程图N-S图全国计算机等级考试37二级公共基础知识利用图示表示选择结构条件满足不满足AB程序流程图N-S图AB条件满足不满足全国计算机等级考试38二级公共基础知识利用图示表示重复结构(1)条件满足不满足S条件满足不满足S程序流程图当型循环程序流程图直到型循环全国计算机等级考试39二级公共基础知识利用图示表示重复结构(2)WHILE条件SSUNTIL条件N-S图当型循环N-S图直到型循环全国计算机等级考试40二级公共基础知识三、面向对象的程序设计面向对象(ObjectOriented)的程序设计方法已经发展成为主流的软件开发方法，起源于对面向对象语言的研究。20世纪60年代后期首次被提出，80年代开始走向实用。面向对象的程序设计的术语：对象、属性、方法、封装性、事件、类、父类、子类、实例、派生、继承、消息、多态性。全国计算机等级考试41二级公共基础知识面向对象方法的主要优点：（1）与人类习惯的思维方法一致。（2）稳定性好。（3）可重用性好。（4）易于开发大型软件产品。（5）可维护性好。全国计算机等级考试42二级公共基础知识1、对象的定义对象：现实生活中存在的可以相互区分的物体。是属性和方法的封装。对象的基本特点：（1）标识唯一性。（2）分类型。（3）多态性。（4）封装性。（5）模块独立型好。全国计算机等级考试43二级公共基础知识2、对象的属性和方法属性（Property）：用来描述对象的状态，是对象的静态特性。包括属性名和属性值两方面。例如：“显示器”作为对象，具备“颜色”属性，取值为“银白色”。方法（Method）：用来描述对象的行为，是对象的动态特性。方法具备方法名。方法必须利用事件来激活。例如:“显示器”作为对象，具备“关闭”的方法，必须用“断电”事件来激活。属性名属性值方法名事件封装性：(Encapsulation)对象依靠对象名将自身的属性和方法封装。全国计算机等级考试44二级公共基础知识3、类和实例的派生与继承（1）类（Class）：具有相同属性和方法的对象的集合，是对对象属性和方法的抽象。（2）实例（Instances）：类的子类派生出的对象就是该类的一个实例。类展现对象的共性；实例展现对象的个性。（3）派生过程中将发生属性和方法的继承（Inheritance）父类将自身的所有属性和方法传递给子类，子类继承父类传递的所有属性和方法，并产生自身特有的属性和方法，再将这些属性和方法的总和传递给下一级子类。人好人坏人中国人外国人张三全国计算机等级考试45二级公共基础知识4、消息与多态性（1）消息（Message）：进行对象之间的信息传递。（2）多态性（Polymorphism）：同样的消息传递给不同的对象，导致完全不同的行动。消息的组成：A.接收消息的对象名称。B.消息标识符，也叫做“消息名”。C.零个或多个参数。全国计算机等级考试46二级公共基础知识第三章软件工程基础软件（Software）=程序+文档全国计算机等级考试47二级公共基础知识本章知识要点软件危机软件生命周期需求分析概要设计详细设计测试调试软件工程全国计算机等级考试48二级公共基础知识一、软件危机软件危机主要表现在：（1）软件需求的增长得不到满足。（2）软件开发成本和进度无法控制。（3）软件质量难以保证。（4）软件不可维护或可维护度非常低。（5）软件的成本不断提高。（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率问题全国计算机等级考试49二级公共基础知识二、软件工程软件工程是为了摆脱软件危机而诞生的，主要思想是在软件开发过程中应用工程化原则。软件工程的三要素：方法、工具、工程。软件工程的主要内容：软件开发技术、软件工程管理。软件工程的原则：（1）抽象。（2）信息隐蔽。（3）模块化。（4）局部化。（5）确定性。（6）一致性。（7）完备性。（8）可验证性。全国计算机等级考试50二级公共基础知识二、软件生命周期软件生命周期（SoftwareLifeCycle，SLC）：将软件产品从提出、实现、使用维护到停止使用退役的过程称为“软件生命周期”。可行性研究需求分析概要设计详细设计实现测试使用退役维护定义阶段开发阶段维护阶段全国计算机等级考试51二级公共基础知识软件工程步骤用到的方法用到的工具生成的文档需求分析结构化分析SA数据流图DFD数据字典DD判定表判定树《软件需求规格说明书》SRS概要设计结构化设计SD软件结构图SC《概要设计说明书》《数据库设计说明书》《集成测试计划》详细设计结构化编程SP程序流程图N-S图问题分析图PAD伪码PDL-全国计算机等级考试52二级公共基础知识三、需求分析需求与需求分析需求分析的方法结构化分析方法数据流图与数据字典判定树与判定表软件需求规格说明书全国计算机等级考试53二级公共基础知识1、需求与需求分析需求：用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析：发现用户需求的过程需求分析阶段的工作：（1）需求获取（2）需求分析（3）编写需求规格说明书（4）需求评审全国计算机等级考试54二级公共基础知识2、需求分析的方法A.面向数据流的结构化分析方法SA。B.面向数据结构的Jackson方法JSD。C.面向数据结构的结构化数据系统开发方法DSSD。D.面向对象的分析方法OOA。全国计算机等级考试55二级公共基础知识3、结构化分析方法：数据流图DFD数据流图DFD中的主要图形元素：加工/转换数据流存储文件/数据源源/潭全国计算机等级考试56二级公共基础知识结构化分析方法：数据字典DD数据字典DD是结构化分析方法的核心。数据字典的作用：对数据流图DFD中出现的被命名图形元素进行确切的解释。全国计算机等级考试57二级公共基础知识结构化分析方法：判定树与判定表判定树

条件1

条件2

结果计7月－9月

订票量>20:

15%算12月

订票量<=20:5%折扣1月－6月

订票量>20:30%量10月11月

订票量<=20:5%全国计算机等级考试58二级公共基础知识判定表旅游时间7月—9月，12月1月—6月，10月，11月订票量>20%<=20%>20%<=20%折扣率15%5%30%20%全国计算机等级考试59二级公共基础知识结构化分析方法：需求规格说明书软件需求规格说明书（SRS）是需求分析阶段的最后成果，将在软件工程的最后转换为用户手册。软件需求规格说明书的作用：（1）便于用户、开发人员进行理解和交流。（2）反映出用户问题的结构，可作为软件开发工作的基础和依据。（3）作为确认测试和验收的依据。全国计算机等级考试60二级公共基础知识四、概要设计软件设计的基本原理：（1）抽象：把事物本质的共同特性提取出来而不考虑细节。（2）模块化：把待开发软件分解成若干个小的简单部分。（3）信息隐蔽：在一个模块内包含的信息，对于不需要这些信息的其他模块来说是不能访问的。（4）模块独立性：评价设计好坏的重要度量指标。内聚性和耦合性是模块独立性的两个定性标准：A.内聚性：一个模块内部各个元素间彼此结合的紧密程度。B.耦合性：模块间互相连接的紧密程度。一款优秀的软件设计，应做到高内聚，低耦合。全国计算机等级考试61二级公共基础知识概要设计的任务：（1）设计软件系统结构。（2）确定软件的每一个模块（3）确定模块之间的调用关系（4）评价模块结构质量。采用的方法：结构化设计方法【SD】

使用的工具：软件结构图SC。软件结构图SC中的主要图形元素模块模块间的调用关系全国计算机等级考试62二级公共基础知识认识软件结构图SC深度=3宽度=3上级模块从属模块原子模块扇入扇出全国计算机等级考试63二级公共基础知识五、详细设计详细设计的任务：为软件结构图中每一个模块确定实现的算法和数据结构。表示算法和数据结构的细节。采用的方法：结构化编程方法【SP】

使用的工具：程序流程图、N-S图、问题分析图PAD

判定表过程设计语言/伪码PDL全国计算机等级考试64二级公共基础知识程序流程图中的主要图形元素：加工步骤控制流逻辑条件全国计算机等级考试65二级公共基础知识六、软件测试软件测试的目的：尽可能多的发现错误。（1）×错误理解：软件测试为了发现错误并改正。（2）×错误理解：软件测试为了证明软件正确性。软件测试的准则：（1）所有测试追溯到需求。（2）严格执行测试计划，排除测试随意性。（3）充分注意测试中的群集现象：程序中存在错误的概率与该程序中已发现的错误数量成正比。（4）程序员避免检测自己的程序。（5）穷举测试不可能。（6）妥善保存测试文档，为维护提供方便。全国计算机等级考试66二级公共基础知识软件测试的方法：（1）静态测试：由人工进行，无需借助计算机。（2）动态测试：基于计算机，实际运行软件进行测试A.白盒测试：逻辑覆盖、基本路径测试。B.黑盒测试：等价类划分、边界值分析、错误推测法、因果图。软件测试的实施：第1步：单元测试（对每一个模块进行测试）第2步：集成测试（将模块组装起来的同时进行测试）第3步：确认测试（验证软件的功能和性能是否满足需求）第4步：系统测试（评估系统环境下软件的功能）全国计算机等级考试67二级公共基础知识七、软件调试（Debug）软件调试的目的：诊断和改正程序中的错误。软件调试的基本步骤：第1步：错误定位。【占据了调试的绝大多数工作量】第2步：修改设计和代码，以排除错误。第3步：进行回归测试，防止引进新的错误。全国计算机等级考试68二级公共基础知识第四章数据库设计基础全国计算机等级考试69二级公共基础知识一、理解数据库：1、数据（Data）是描述事物的符号记录。2、为什么引入数据库：（1）数据量大，数据多。（2）方便查找。全国计算机等级考试70二级公共基础知识二、数据库原理术语：1、数据（Data）是描述事物的符号记录。2、数据库（DataBase，DB）数据的集合，是存放数据的仓库。3、数据库管理系统（DBMS）负责数据的管理。（1）DBMS属于系统软件。（2）DBMS是数据库系统的核心。4、数据库应用系统（DBAS）利用DBMS开发的应用软件。5、数据库系统（DBS）使用了数据库技术的计算机，属于硬件系统。6、数据库管理员（DBA）是数据库系统的人的因素。负责管理、维护、设计、监视数据库系统的运行。全国计算机等级考试71二级公共基础知识计算机硬件操作系统数据库管理系统数据库应用系统用户WindowsXP/Vista/7/2003等。Access/VisualFoxPro/SQLServer等。全国计算机等级考试72二级公共基础知识三、数据库系统的三级模式和两级映射：数据库（DB）内模式（物理模式）概念模式外模式/子模式用户模式外模式应用应用应用概念模式–内模式映射外模式-概念模式映射全局数据逻辑结构的描述局部数据逻辑结构的描述全国计算机等级考试73二级公共基础知识四、数据模型：1、数据模型的三层分类：（1）概念数据模型/概念模型（2）逻辑数据模型/数据模型（3）物理数据模型/物理模型2、典型的概念数据模型：E–R模型（实体-联系模型）（1）实体：现实生活中的事物。（2）属性：表示实体的一些特征。（3）联系：实体之间的关联。全国计算机等级考试74二级公共基础知识3、实体间联系：（1）一对一（1:1）学校--校长【计算机不予处理】（2）一对多（1:m）学生–班级【计算机可以直接处理】（3）多对多（m:n）学生–课程【转换为两个一对多联系再处理】历史上出现过的数据模型：网状模型、层次模型、关系模型全国计算机等级考试75二级公共基础知识4、E-R模型的图示表示法：实体联系实体的属性全国计算机等级考试76二级公共基础知识五、关系模型：关系的数据结构学号姓名性别年龄籍贯01张三男21河北02李四女24山东03王武男28陕西例：学生关系属性元组/记录主键关系就是二维表。1、元组是有限的。2、元组不能重复。3、属性不能重复。4、元素的顺序是无关的。5、属性的顺序是无关的。全国计算机等级考试77二级公共基础知识关系的数据约束A.实体完整性约束主键取值不能为空，不能取重复值。主键取值不同，就是两个不同的元组。B.参照完整性约束不允许引用不存在的元组。约束了关系之间相关联的情况。C.用户自定义完整性约束全国计算机等级考试78二级公共基础知识六、关系代数：参与运算的数据都是关系（二维表）。1、基本关系代数（1）交：R∩S=｛t|t∈R且t∈S｝（2）并：R∪S=｛t|t∈R或t∈S｝（3）差：R-S=｛t|t∈R且t∈S｝全国计算机等级考试79二级公共基础知识RABC125149284560924SABC125349264560333R∩SABC125560结论：并交差三个操作都不能更改关系的属性个数。全国计算机等级考试80二级公共基础知识RABC125149560SABC125349R×SR.AR.BR.CS.AS.BS.C1251251491251493495601255603491253492、关系积（笛卡尔积）全国计算机等级考试81二级公共基础知识3、扩展关系代数：（1）选择：σA>C(R)【对关系的横向分解】（