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

全国计算机等级考试,National Computer Rank Examination,二级 公共基础知识,全国计算机等级考试,2,考试内容,数据结构和算法 程序设计基础 软件工程 数据库设计基础,全国计算机等级考试,3,1、二级公共基础的考试方式为笔 试，与各科语言的笔试部分合 为一张试卷。公共基础部分占 全卷的30分。2、公共基础知识有10道选择题和 5道填空题。,考试方式,全国计算机等级考试,4,理解基本概念多做练习适当记忆一些名词与所学程序设计语言结合起来理解,学习方法,第一章 数据结构和算法,全国计算机等级考试,6,本章知识要点,算法,算法的定义,算法的特征,算法复杂度,数据结构,数据结构的定义,逻辑结构 和 物理结构,线性结构 和 非线性结构,顺序表、链表、堆栈队列、循环队列、树,算法的基本要素,全国计算机等级考试,7,算法是对特定问题求解步骤的一种描述。,一、算法,算法的特性：（1）有穷性：算法必须在有限的次数内完成。（2）确定性：算法的每一步必须是明确的。（3）可行性：算法的每一步必须是可以实现的。（4）拥有足够的情报：算法必须有一定的输入和输出。,全国计算机等级考试,8,算法的基本要素：（1）对数据对象的运算和操作：A.算术运算 B.逻辑运算 C.关系运算 D.数据传输（2）算法的控制结构：A.顺序结构 B.选择结构 C.循环结构,全国计算机等级考试,9,算法的复杂度：衡量算法优劣的量。（1）时间复杂度：算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关，是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工 作量。（2）空间复杂度：执行算法所需要的内存空间。,全国计算机等级考试,10,二、数据结构,数据结构主要研究两方面的问题：（1）数据本身。（2）数据之间的前后件关系。,数据结构表示为：DS=D，S例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春),全国计算机等级考试,11,数据的结构分为：（1）物理结构：数据在计算机存储介质中真正存储的结构，也被称为“存储结构”（2）逻辑结构：人们所理解的数据之间的结构，可以用图示 的方法绘画出来的数据之间的结构。,例：一个班由35名同学，他们的座位牌号就是物理结构，一次考试的排名是逻辑结构。1,注意：逻辑结构和物理结构没有必然的联系，也不一定是 一一对应的。,全国计算机等级考试,12,数据的结构分为：（1）线性结构：非空数据结构同时满足以下两个条件就是线性结构：A.有且仅有一个根结点；B.除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。（2）非线性结构：除了线性结构都是非线性结构。,全国计算机等级考试,13,全国计算机等级考试要求掌握的数据结构共有以下六种：,线性表 堆栈 队列 循环队列 线性链表 树和二叉树,线性结构,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构不相同,物理结构和逻辑结构不相同,非线性结构,全国计算机等级考试,14,10,20,30,40,50,60,70,80,三、顺序表：顺序表就是数组,1、顺序表也叫做线性表，属于线性结构。线性表的逻辑结构和物理结构相同。2、特点：（1）有且仅有一个头结点（根节点）和尾结点。（2）任意其他结点至多有一个前件，一个后件。（3）头结点没有前件，尾结点没有后件。,全国计算机等级考试,15,四、堆栈,1、定义：只允许在栈顶位置插 入数据和删除数据的线性结 构是堆栈，简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构 相同。4、特点：先进后出，后进先出 所以堆栈也叫做先进后出表（FILO）5、堆栈具备存储功能：函数的 递归调用和表达式求解都用 到了堆栈。,全国计算机等级考试,16,入栈顺序：a、b、c、d、e、f,栈空,a,b,a,c,b,a,b,a,d,b,a,.,入a,入b,入c,出c,入d,模拟堆栈的数据出入过程：,全国计算机等级考试,17,【典型题型】假设一个堆栈，入栈顺序为abcde，认为在任何时 刻均允许出栈，下列选项中不可能的出栈顺序为：A）abcde（可能）B）edcba（可能）C）cdeba（可能）D）cdeab（不可能）,如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（）A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2D)任意顺序,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（）A)ABCED B)DCBEA C)DBCEA D)CDABE,全国计算机等级考试,18,五、队列,1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义：入队操作发生在队尾，出队操作发生在队头。4、特点：先进先出，后进后出，所以队列也叫做先进先 出表（FIFO）。,全国计算机等级考试,19,六、循环队列,rear,front,全国计算机等级考试,20,入队顺序：a、b、c、d、e、f,模拟循环队列的数据出入过程：,循环队列空front=rear,rear,front,a,front,rear,数据a入队,a,front,rear,b,数据b入队,front,rear,b,数据a出队,全国计算机等级考试,21,七、线性链表,1、链表属于线性结构。2、链表的逻辑结构和物理结构不相同。3、线性链表由结点组成：每个结点有两个区域：数据域，指针域。A.数据域，用来存储数据。B.指针域，用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。,全国计算机等级考试,22,链表的种类：单链表、循环链表、双向链表。,1,2,3,4,5,1,2,3,4,5,循环链表,双向链表,1,2,3,4,5,全国计算机等级考试,23,八、树与二叉树,1、树属于非线性结构。2、树的逻辑结构和物理结构不相同。3、树有且仅有一个根节点。,根节点,x,e,o,q,k,b,g,全国计算机等级考试,24,二叉树：每个结点最多分两叉的有序树。,二叉树,二叉树的术语,有序树与无序树,二叉树的五种基本结构,满二叉树 和 完全二叉树,二叉树的计算,二叉树的遍历,全国计算机等级考试,25,1、二叉树的术语：,A.结点、根节点、叶子节点：（1）构成树的基本结构是结点。（2）没有父结点的结点是根节点。（3）没有子结点的结点是叶子节点（度为0的结点）。B.结点的度：结点子结点的个数。C.树的度：树中度数最大的结点的度就是树的度。D.树的高度/层数：树有多少层。E.父结点、子结点、双亲结点、孩子结点、左孩子、右孩子、兄弟结点、堂兄结点。,全国计算机等级考试,26,2、有序树与无序树：,e,A,B,e,B,A,二叉树和度为二的树的区别：A.二叉树是有序树，度为二的树是普通树，属于无序树。B.二叉树允许为空，度为二的数至少有三个结点。【普通树不允许为空，至少有一个结点】,全国计算机等级考试,27,3、二叉树的五种基本结构：,全国计算机等级考试,28,4、满二叉树和完全二叉树：,A.满二叉树：二叉树的每一层均具备该层最大结点个数。（即：不具备度为1的结点）B.完全二叉树：满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号，结点编号连续而不缺失。,满二叉树,完全二叉树,1,2,3,4,5,6,全国计算机等级考试,29,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。,全国计算机等级考试,30,填空题：设一棵完全二叉树共有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=700 2n0=701-n1 完全二叉树总结点个数为偶数，则度为1的结点个数为1；完全二叉树的总结点个数为奇数，则度为1的结点个数为0。所以：2n0=701-1，即 n0=350。,全国计算机等级考试,31,6、二叉树的遍历：,A.前/先（根）序遍历，GLR。【根节点为序列开头】B.中（根）序遍历，LGR。【没有左子树，根节点为开头；没有右子树，根节点为结尾】【左右子树均有，根节点的位置位于左子树结点个数之和+1】C.后（根）序遍历，LRG。【根节点为序列结尾】,先序序列：xeqbog,中序序列：qebxog,后序序列：qbegox,第二章 程序设计基础,全国计算机等级考试,33,本章知识要点,面向过程的程序设计,结构化程序设计,模块化程序设计,面向对象的程序设计,对象的定义,对象的属性和方法,类和实例的派生与继承,消息与多态性,全国计算机等级考试,34,一、程序设计方法,1、面向过程的程序设计：C语言、BASIC语言等。（1）结构化程序设计：顺序、选择、循环。三大结构（顺序、选择、循环）可以解决所有的问题，和 问题的规模没有关系。（2）模块化程序设计：利用将程序分解的方法，将复杂的问题 简单化，将单一的问题分成多个模块独立解决。C语言：模块就是函数。VB语言：模块就是模块、子例程、子程序。VFP数据库：模块就是子程序。Access数据库：模块就是宏、事件代码。2、面向对象的程序设计：VB、VFP、Java、Delphi等。,全国计算机等级考试,35,二、程序设计风格,1.源程序文档化 选择标示符的名字 注释（序言性和功能性注释）程序的视觉组织2.数据说明的方法 显式地说明一切变量 数据说明的次序应该规范化 说明语句中变量安排有序化 对复杂数据结构应注释说明,3.语句的结构 每条语句简单明了 尽量不用或少用GOTO语句 尽量只采用3种基本控制结构编程4.输入和输出 对输入数据进行校验和合理性检查 输入输出格式保持一致 设计良好的输出报表,全国计算机等级考试,36,三、结构化程序设计,20世纪70年代提出了结构化程序设计（Structured Programming）,结构化程序设计的原则：（1）自顶向下。（2）逐步求精。（3）模块化。（4）限制使用goto语句。,结构化程序设计的基本结构：（1）顺序结构。（2）选择结构。（3）重复结构。,结构化程序设计主要强调程序的易读性。,全国计算机等级考试,37,利用图示表示顺序结构,程序流程图,N-S图,全国计算机等级考试,38,利用图示表示选择结构,程序流程图,N-S图,全国计算机等级考试,39,利用图示表示重复结构(1),程序流程图当型循环,程序流程图直到型循环,全国计算机等级考试,40,利用图示表示重复结构(2),S,UNTIL 条件,N-S图当型循环,N-S图直到型循环,全国计算机等级考试,41,三、面向对象的程序设计,面向对象(Object Oriented)的程序设计方法已经发展成为主流的软件开发方法，起源于对面向对象语言的研究。20世纪60年代后期首次被提出，80年代开始走向实用。,面向对象的程序设计的术语：对象、属性、方法、封装性、事件、类、父类、子类、实例、派生、继承、消息、多态性。,全国计算机等级考试,42,面向对象方法的主要优点：（1）与人类习惯的思维方法一致。（2）稳定性好。（3）可重用性好。（4）易于开发大型软件产品。（5）可维护性好。,全国计算机等级考试,43,1、对象的定义,对象：现实生活中存在的可以相互区分的物体。是属性和方法的封装。,对象的基本特点：（1）标识唯一性。（2）分类型。（3）多态性。（4）封装性。（5）模块独立型好。,全国计算机等级考试,44,2、对象的属性和方法,属性（Property）：用来描述对象的状态，是对象的静态特性。包括属性名和属性值两方面。例如：“显示器”作为对象，具备“颜色”属性，取值为“银白色”。方法（Method）：用来描述对象的行为，是对象的动态特性。方法具备方法名。方法必须利用事件来激活。例如:“显示器”作为对象，具备“关闭”的方法，必须用“断电”事件来激活。,属性名,属性值,方法名,事件,封装性：(Encapsulation)对象依靠对象名将自身的属性和方法封装。,全国计算机等级考试,45,3、类和实例的派生与继承,（1）类（Class）：具有相同属性和方法的 对象的集合，是对对象属性和方法的抽 象。（2）实例（Instances）：类的子类派生出 的对象就是该类的一个实例。类展现对象的共性；实例展现对象的个性。（3）派生过程中将发生属性和方法的继承（Inheritance）父类将自身的所有属性和方法传递 给子类，子类继承父类传递的所有属性 和方法，并产生自身特有的属性和方 法，再将这些属性和方法的总和传递给 下一级子类。,人,好人,坏人,中国人,外国人,张三,全国计算机等级考试,46,4、消息与多态性,（1）消息（Message）：进行对象之间的信息传递。（2）多态性（Polymorphism）：同样的消息传递给不同的对象，导致 完全不同的行动。,消息的组成：A.接收消息的对象名称。B.消息标识符，也叫做“消息名”。C.零个或多个参数。,全国计算机等级考试,48,本章知识要点,软件危机,软件生命周期,需求分析,概要设计,详细设计,测试,调试,软件工程,全国计算机等级考试,49,一、软件危机,软件危机主要表现在：（1）软件需求的增长得不到满足。（2）软件开发成本和进度无法控制。（3）软件质量难以保证。（4）软件不可维护或可维护度非常低。（5）软件的成本不断提高。（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。,总之，可以将软件危机归结为成本、质量、生产率问题,全国计算机等级考试,50,二、软件工程,软件工程是为了摆脱软件危机而诞生的，主要思想是在软件开发过程中应用工程化原则。,软件工程的三要素：方法、工具、工程。,软件工程的主要内容：软件开发技术、软件工程管理。,软件工程的原则：（1）抽象。（2）信息隐蔽。（3）模块化。（4）局部化。（5）确定性。（6）一致性。（7）完备性。（8）可验证性。,全国计算机等级考试,51,二、软件生命周期,软件生命周期（Software Life Cycle，SLC）：将软件产品从提出、实现、使用维护到停止使用退役的过程称为“软件生命周期”。,全国计算机等级考试,52,全国计算机等级考试,53,三、需求分析,需求与需求分析,需求分析的方法,结构化分析方法,数据流图与数据字典,判定树与判定表,软件需求规格说明书,全国计算机等级考试,54,1、需求与需求分析,需求：用户对目标软件系统在功能、行为、性能、设计 约束等方面的期望。,需求分析：发现用户需求的过程,需求分析阶段的工作：（1）需求获取（2）需求分析（3）编写需求规格说明书（4）需求评审,全国计算机等级考试,55,2、需求分析的方法,A.面向数据流的结构化分析方法 SA。B.面向数据结构的Jackson方法 JSD。C.面向数据结构的结构化数据系统开发方法 DSSD。D.面向对象的分析方法 OOA。,全国计算机等级考试,56,3、结构化分析方法：数据流图DFD,数据流图DFD中的主要图形元素：,加工/转换,数据流,存储文件/数据源,源/潭,全国计算机等级考试,57,结构化分析方法：数据字典DD,数据字典DD是结构化分析方法的核心。,数据字典的作用：对数据流图DFD中出现的被命名图形元素进 行确切的解释。,全国计算机等级考试,58,结构化分析方法：判定树与判定表,判定树,全国计算机等级考试,59,判定表,全国计算机等级考试,60,结构化分析方法：需求规格说明书,软件需求规格说明书（SRS）是需求分析阶段的最后成果，将在软件工程的最后转换为用户手册。,软件需求规格说明书的作用：（1）便于用户、开发人员进行理解和交流。（2）反映出用户问题的结构，可作为软件开发工作的基础和 依据。（3）作为确认测试和验收的依据。,全国计算机等级考试,61,四、概要设计,软件设计的基本原理：（1）抽象：把事物本质的共同特性提取出来而不考虑细节。（2）模块化：把待开发软件分解成若干个小的简单部分。（3）信息隐蔽：在一个模块内包含的信息，对于不需要这些 信息的其他模块来说是不能访问的。（4）模块独立性：评价设计好坏的重要度量指标。,内聚性和耦合性是模块独立性的两个定性标准：A.内聚性：一个模块内部各个元素间彼此结合的紧密程度。B.耦合性：模块间互相连接的紧密程度。一款优秀的软件设计，应做到高内聚，低耦合。,全国计算机等级考试,62,概要设计的任务：（1）设计软件系统结构。（2）确定软件的每一个模块（3）确定模块之间的调用关系（4）评价模块结构质量。,采用的方法：结构化设计方法【SD】使用的工具：软件结构图SC。,全国计算机等级考试,63,认识软件结构图SC,全国计算机等级考试,64,五、详细设计,详细设计的任务：为软件结构图中每一个模块确定实现的算法 和数据结构。表示算法和数据结构的细节。,采用的方法：结构化编程方法【SP】使用的工具：程序流程图、N-S图、问题分析图PAD 判定表 过程设计语言/伪码PDL,全国计算机等级考试,65,程序流程图中的主要图形元素：,加工步骤,控制流,逻辑条件,全国计算机等级考试,66,六、软件测试,软件测试的目的：尽可能多的发现错误。（1）错误理解：软件测试为了发现错误并改正。（2）错误理解：软件测试为了证明软件正确性。,软件测试的准则：（1）所有测试追溯到需求。（2）严格执行测试计划，排除测试随意性。（3）充分注意测试中的群集现象：程序中存在错误的概率与该程 序中已发现的错误数量成正比。（4）程序员避免检测自己的程序。（5）穷举测试不可能。（6）妥善保存测试文档，为维护提供方便。,全国计算机等级考试,67,软件测试的方法：（1）静态测试：由人工进行，无需借助计算机。（2）动态测试：基于计算机，实际运行软件进行测试 A.白盒测试：逻辑覆盖、基本路径测试。B.黑盒测试：等价类划分、边界值分析、错误推测法、因果图。,软件测试的实施：第1步：单元测试（对每一个模块进行测试）第2步：集成测试（将模块组装起来的同时进行测试）第3步：确认测试（验证软件的功能和性能是否满足需求）第4步：系统测试（评估系统环境下软件的功能）,全国计算机等级考试,68,七、软件调试（Debug）,软件调试的目的：诊断和改正程序中的错误。,软件调试的基本步骤：第1步：错误定位。【占据了调试的绝大多数工作量】第2步：修改设计和代码，以排除错误。第3步：进行回归测试，防止引进新的错误。,第四章 数据库设计基础,全国计算机等级考试,70,一、理解数据库：,1、数据（Data）是描述事物的符号记录。2、为什么引入数据库：（1）数据量大，数据多。（2）方便查找。,全国计算机等级考试,71,二、数据库原理术语：,1、数据（Data）是描述事物的符号记录。2、数据库（DataBase，DB）数据的集合，是存放数据的仓库。3、数据库管理系统（DBMS）负责数据的管理。（1）DBMS属于系统软件。（2）DBMS是数据库系统的核心。4、数据库应用系统（DBAS）利用DBMS开发的应用软件。5、数据库系统（DBS）使用了数据库技术的计算机，属于硬件系统。6、数据库管理员（DBA）是数据库系统的人的因素。负责管理、维 护、设计、监视数据库系统的运行。,全国计算机等级考试,72,计算机硬件,操作系统,数据库管理系统,数据库应用系统,用户,Windows XP/Vista/7/2003等。,Access/Visual FoxPro/SQL Server等。,全国计算机等级考试,73,三、数据库系统的三级模式和两级映射：,数据库（DB）,内模式（物理模式）,概念模式,外模式/子模式,用户模式,外模式,应用,应用,应用,概念模式 内模式映射,外模式-概念模式映射,全局数据逻辑结构的描述,局部数据逻辑结构的描述,全国计算机等级考试,74,四、数据模型：,1、数据模型的三层分类：（1）概念数据模型/概念模型（2）逻辑数据模型/数据模型（3）物理数据模型/物理模型2、典型的概念数据模型：E R模型（实体-联系模型）（1）实体：现实生活中的事物。（2）属性：表示实体的一些特征。（3）联系：实体之间的关联。,全国计算机等级考试,75,3、实体间联系：（1）一对一（1:1）学校-校长【计算机不予处理】（2）一对多（1:m）学生 班级【计算机可以直接处理】（3）多对多（m:n）学生 课程【转换为两个一对多联系再处理】,历史上出现过的数据模型：网状模型、层次模型、关系模型,全国计算机等级考试,76,4、E-R模型的图示表示法：,实体,联系,实体的属性,全国计算机等级考试,77,五、关系模型：,关系的数据结构,例：学生关系,属性,元组/记录,主键,关系就是二维表。,1、元组是有限的。2、元组不能重复。3、属性不能重复。4、元素的顺序是无关的。5、属性的顺序是无关的。,全国计算机等级考试,78,关系的数据约束,A.实体完整性约束 主键取值不能为空，不能取重复值。主键取值不同，就是两个不同的元组。B.参照完整性约束 不允许引用不存在的元组。约束了关系之间相关联的情况。C.用户自定义完整性约束,全国计算机等级考试,79,六、关系代数：参与运算的数据都是关系（二维表）。,1、基本关系代数,（1）交：RS=t|tR且tS（2）并：RS=t|tR或tS（3）差：R-S=t|tR且tS,全国计算机等级考试,80,R,A B C,1 2 51 4 92 8 45 6 09 2 4,S,A B C,1 2 53 4 92 6 45 6 03 3 3,结论：并交差三个操作都不能更改关系的属性个数。,全国计算机等级考试,81,R,A B C,1 2 5,1 4 9,5 6 0,S,A B C,1 2 5,3 4 9,RS,R.A R.B R.C S.A S.B S.C,1 2 5 1 2 5,1 4 9 1 2 51 4 9 3 4 95 6 0 1 2 55 6 0 3 4 9,1 2 5 3 4 9,2、关系积（笛卡尔积）,全国计算机等级考试,82,3、扩展关系代数：,（1）选择：AC(R)【对关系的横向分解】（2）投影：A,C(R)【对关系的纵向分解】,A,C(R),A C,1 5,1 9,2 4,5 0,9 4,R,A B C,1 2 5,1 4 9,2 8 4,5 6 0,9 2 4,全国计算机等级考试,83,3、连接：,（1）连接：R S 公共属性取值相同的等值连接,ij,R,A B C,1 2 5,1 4 9,5 6 0,T,D B E,1 2 5,3 4 9,i=j,全国计算机等级考试,84,R,A B C,1 2 5,1 4 9,5 6 0,T,D B E,1 2 5,3 4 9,全国计算机等级考试,85,七、数据库设计与管理：,1、数据库设计的四个阶段：,建立概念数据模型：E-R模型,将E-R图转换为关系模式：实体和联系均转换为关系。,对数据库内部物理结构作出调整并选择合理的存储路径,全国计算机等级考试,86,2、数据库管理：实施人：数据库管理员（DBA）数据库管理的特点：实现数据共享 管理内容：（1）数据库的建立（2）数据库的调整（3）数据库的重组（4）数据安全控制与完整性控制（5）数据库的故障校复（6）数据库监控,