计算机二级公共基础知识

1、全国计算机二级考试公共基础知识公共基础知识MS Office高级应用高级应用公共基础知识公共基础知识 数据结构与算法数据结构与算法 程序设计基础程序设计基础 软件工程软件工程 数据库数据库设计基础设计基础公共基础公共基础知识知识 数据结构数据结构与算法与算法知识知识点点 算法的定义 算法的特征 算法的基本要素 算法的复杂程度 数据结构的定义。 逻辑结构与物理结构。 线性结构和非线性结构。 顺序表、链表、堆栈、队列、循环队列、树。 算法数据结构公共基础知识公共基础知识 数据结构与算法数据结构与算法算法是解决问题的准确而完整性的描述算法程序，算法计算方法。公共基础知识公共基础知识 数据结构与算法数

2、据结构与算法有穷性：算法必须在有限的次数内完成。确定性：算法的每一步必须是明确的。可行性：算法的每一步必须是可以实现的。拥有足够的情报：算法必须有一定的输入和输出。公共基础知识公共基础知识 数据结构与算法数据结构与算法 对数据对象的运算和操作： 算术运算 逻辑运算 关系运算 数据传输 算法的控制结构： 顺序结构 选择结构 循环结构公共基础知识公共基础知识 数据结构与算法数据结构与算法算法的复杂程度：衡量算法优劣的量。时间复杂度：算法的时间耗费。 算法中基本操作重复执行次数和算法执行时间同 步增长，被称作算法的时间复杂度。 算法中基本操作重复执行次数和问题规模有关，是问题规模的函数。 算法的时间

3、复杂度是指执行算法所需要的计算工作量。空间复杂度：执行算法所需要的内存空间。公共基础知识公共基础知识 数据结构与算法数据结构与算法数据结构主要研究两方面问题：数据本身 数据之间的前后件关系数据结构表示为：A=x,y,z公共基础知识公共基础知识 数据结构与算法数据结构与算法逻辑结构：人们所理解的数据之间的结构，可以用图示的方法绘画出来的数据之间的结构。物理结构：数据在计算机存储介质中真正存储的结构，也被称作存储结构。逻辑结构与物理结构没有必然的联系，也不一定是一一对应的。公共基础知识公共基础知识 数据结构与算法数据结构与算法 线性结构：非空数据结构 A.有且仅有一个根结点；B.除头结点和尾结点外

4、，任何结点有且仅有一个前件和一个后件。 非线性结构：除了线性结构都是非线性结构。公共基础知识公共基础知识 数据结构与算法数据结构与算法 线性表 物理结构和逻辑结构相同 堆栈 物理结构和逻辑结构相同 队列 物理结构和逻辑结构相同 循环队列 物理结构和逻辑结构相同 线性链表 物理结构和逻辑结构不相同 树和二叉树 物理结构和逻辑结构不相同线性结构非线性结构公共基础知识公共基础知识 数据结构与算法数据结构与算法顺序表：数组。 顺序表也叫做线性表，属于线型结构。 线性表的逻辑结构和物理结构相同。 特点：有且仅有一个头结点（根节点）和尾结点；任意其他结点至多有一个前件，一个后件；头结点没有前件，尾结点没有

5、后件。1020304050607080公共基础知识公共基础知识 数据结构与算法数据结构与算法堆栈：只允许在栈顶位置插入数据和删除数据的线性结构，简称“栈”。堆栈的逻辑结构和物理结构相同。特点：先进后出，后进先出。所以也叫“先进后出表（FILO）”。堆栈具备存储功能：函数的递归调用和表达式求解都用到堆栈。公共基础知识公共基础知识 数据结构与算法数据结构与算法栈顶栈顶toptop栈底栈底入栈入栈/ /压入压入出栈出栈/ /弹出弹出公共基础知识公共基础知识 数据结构与算法数据结构与算法队列：队列属于线性结构；队列的逻辑结构与物理结构相同；入队操作发生在队尾，出队操作发生在队头；先进先出后进后出，所以

6、也叫“先进先出表(FIFO)”。队尾队尾rear队头队头front入队入队出队出队公共基础知识公共基础知识 数据结构与算法数据结构与算法循环序列：frontrearfrontrear循环队列循环队列空空front=reararearbrearfrontrear数据数据a入队入队数据数据b入队入队数据数据a出队出队模拟循环队列的数据出入过程：入队运算是往队列队尾插入一入队运算是往队列队尾插入一个数据元素；个数据元素； 退队运算是从队退队运算是从队列对头删除一个数据元素。列对头删除一个数据元素。公共基础知识公共基础知识 数据结构与算法数据结构与算法线性链表：链表属于线性结构；链表的逻辑结构与物理结

7、构不同；线性链表由结点组成： 每个结点有两个区域，数据域，指针域。5个结点组成的链表数据为1、2、3、4、5.（用来储存数据）（用来储存数据） （用来指向下（用来指向下一个一个 结点结点的位置）的位置）2 23 34 45 51 1单链表公共基础知识公共基础知识 数据结构与算法数据结构与算法链表的种类：单链表、循环链表、双向链表。循环链表：2 23 34 45 5 1 1双向链表：公共基础知识公共基础知识 数据结构与算法数据结构与算法树与二叉树：1.树是一种简单的非线性结构，是n个结点的有限集合。从逻辑结构看：1）书中只有根节点没有前驱；2）除根外，其他结点都有且只有一个前驱；3）树的结点，可

8、以有零个或多个后继；4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构。注意：1）树结构具有明显的层次结构，即树是一种层次结构。因此具有层次关系的数据都可以用树这种数据结构来描述。2）在树结构中分层的原则是根结点在第一层，同一层上所有结点的所有子结点都在下一层。3）在树中，叶子结点没有子树。公共基础知识公共基础知识 数据结构与算法数据结构与算法2.树的基本术语： 1）根结点：在数据结构中，没有前件的结点只有一个，称为树的根结点。 2）子结点：在数据结构中，每一个结点可以有多个后件，它们都成为该结点的子结点。没有后件的结点叫做叶子结点。 3）度：在数据结构中，一个节点所

9、拥有的后件的个数称为该结点的度。在树中，所有结点的中最大的度称为该树的度。 4）树的深度：树的最大层次称为树的度。公共基础知识公共基础知识 数据结构与算法数据结构与算法3.二叉树 二叉树也是一种非线性结构，每个结点最多分两叉的有序树。二叉树两个特点：1）非空二叉树只有一个根结点；2）每个结点最多有两个子树，且分别称为该结点的左子树和右子树。Da)只有根结点的二叉树b)深度为4的二叉树公共基础知识公共基础知识 数据结构与算法数据结构与算法4.有序树与无序树 二叉树与度为二的树的区别： 1）二叉树是有序树，度为二的树是普通树，属于无序树。 2）二叉树允许为空，度为二的树至少有三个结点。 【普通树不

10、允许为空，至少有几个结点】 公共基础知识公共基础知识 数据结构与算法数据结构与算法5.二叉树的五种基本结构：空二叉树a只有一个结点的二叉树b有两个结点的二叉树c有三个结点的二叉树公共基础知识公共基础知识 数据结构与算法数据结构与算法6.二叉树的基本性质 性质1 在二叉树的第k层上，最多有2K-1(k1)个结点。 性质2 深度为m的二叉树最多有2m-1个结点。 根据性质1，第一层到第m层上最大树的结点相加就可以得到整个二叉树中结点的最大值，即：21-1+22-1+2m-1=2m-1 性质3 在任意一棵二叉树中，度数为零的节点（即叶子结点）总比度为二的结点多一个。n0=n2+1 性质4 具有n个结

11、点的二叉树，其深度至少为log2n+1,其中log2n表示取其整数部分。 性质5 具有n个结点的完全二叉树的深度为log2n+1。 公共基础知识公共基础知识 数据结构与算法数据结构与算法7.满二叉树和完全二叉树 1）满二叉树：二叉树的每一层均具备该层最大结点个数。（即不具备度为1的结点） 2）完全二叉树：满二叉树是一个特殊的完全二叉树，将所有结点从上到下、从左到右编号，结点编号连续而不缺失。公共基础知识公共基础知识 数据结构与算法数据结构与算法公共基础知识公共基础知识 数据结构与算法数据结构与算法8.二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的所有结点。二叉树由根、左子树、右子树三部分

12、组成。二叉树的遍历可以分解为访问根、遍历左子树、遍历右子树。令 L遍历左子树 D访问根结点 约定先左后右有三种遍历方法： R遍历右子树 先序遍历（先根遍历）DLR有六种遍历方法： 中序遍历（中根遍历）LDRDLR,LDR,LRD, 后序遍历（后根遍历）LRDDRL,RDL,RLD，公共基础知识公共基础知识 数据结构与算法数据结构与算法公共基础知识公共基础知识 数据结构与算法数据结构与算法公共基础公共基础知识知识 程序设计基础面向过程的程序设计面向对象的程序设计结构化程序设计模块化程序设计对象的定义对象的属性和方法类和实例的派生与继承消息与多态性公共基础知识公共基础知识 程序设计基础一、程序设计

13、方法1.面向过程的程序设计：C语言，BASIC语言等。 (1)结构化程序设计：顺序、选择、循环。 三大结构（顺序、选择、循环）可以解决所有问题， 和问题的规模没有关系。 (2)模块化程序设计：利用将程序分解的方法，将复杂的问题简单化，将单一的问题分成多个模块独立解决。 C语言：模块就是函数。 VB语言：模块就是模块、子例程、子程序。 VFP数据库：模块就是子程序。 Access数据库模块就是宏、事件代码。2.面向对象的程序设计：VB、VFP、Java、Delphi等。公共基础知识公共基础知识 程序设计基础二、程序设计风格1.源程序文档化 选择标示符的名称 注释（序言性和功能性注释） 程序的视觉

14、组织 2.数据说明的方法 显示的说明一切变量 数据说明的次序应该规范化 说明语句中变量安排有序化 对复杂数据结构应注释说明3.语句的结构 每条语句简单明了 尽量不用或少用GOTO语句 尽量只采用3种基本控制结构编程4.输入和输出 对输入数据进行校验和合理性检查 输入输出格式保持一致 设计良好的输出报表公共基础知识公共基础知识 程序设计基础三、结构化程序设计 20世纪70年代提出了结构化程序设计 (Structured Programming)结构化程序设计的基本结构： 顺序结构、选择结构、重复结构。结构化程序设计的原则： 自顶向下、逐步求精、模块化、限制使用goto 语句。结构化程序设计主要强

15、调程序的易读性。公共基础知识公共基础知识 程序设计基础 顺序结构 顺序结构 重复结构公共基础知识公共基础知识 程序设计基础四、面向对象的程序设计 面向对象(Object Oriented)的程序设计方法已经发展成为主流的软件开发方法，起源于对面向对象语言的研究。20世纪60年代后期首次被提出，80年代开始走向实用。 面向对象的程序设计术语：对象、属性、方法、封装性、事件、类、父类、子类、实例、派生、继承、消息、多态性。公共基础知识公共基础知识 程序设计基础面向对象方法的主要优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。公共

16、基础知识公共基础知识 程序设计基础1.对象的定义 对象：现实生活中存在的可以相互区分的物体。 是属性和方法的封装。 对象的基本特点： （1）标识唯一性； （2）分类型； （3）多态性； （4）封装性； （5）模块独立性好。公共基础知识公共基础知识 程序设计基础2.对象的属性和方法属性(Property)用来描述对象的状态，是对象的静态特征。 包括属性名和属性值两方面。 例：“显示器”作为对象，具备“颜色”属性，取值为“银白色”。 属性名 属性值 方法(Method)用来描述对象的行为，是对象的动态特征。 方法具备方法名。 方法必须利用时间来激活。例：“显示器”作为对象，具备“关闭”的方法，必须

17、用“断电”事件来激活。 方法名 事件封装性(Encapsulation) 对象依靠对象名将自身的属性和方法封装。公共基础知识公共基础知识 程序设计基础3.类和实例的派生与继承(1)类(Class)：具有相同属性和方法的对象的集合，是对对象属性和方法的抽象。(2)实例(Instances)：类的子类派生出的对象就是该类的一个实例。(3)派生过程中将发生属性和方法 的继承(Inheritance) 父类将自身的所有属性和方法传递给子类，子类继承父类传递的所有属性和方法，并产生自身特有的属性和方法，再将这些属性和方法的总和传递给下一级子类。公共基础知识公共基础知识 程序设计基础4.消息与多态性(1)

18、消息(Message)：进行对象之间的信息传递。 消息的组成：A.接收消息的对象名称 B.消息标识符，也叫做“消息名”。 C.零个或多个参数。(2)多态性(Polymorphism)：同样的消息传递给不同的对象，导致完全不同的行动。公共基础知识公共基础知识 程序设计基础公共基础公共基础知识知识 软件工程基础软件工程基础软件(Software)=程序+文档 软件危机 软件工程 软件生命周期 需求分析 概要设计 详细设计 测试 调试公共基础知识公共基础知识 软件工程基础软件工程基础一、软件危机 软件危机主要表现在：1.软件需求的增长得不到满足；2.软件开发成本和进度无法控制；3.软件质量难以保证；

19、4.软件不可维护或维护度非常低；5.软件的成本不断提高；6.软件开发生产率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率问题。公共基础知识公共基础知识 软件工程基础软件工程基础二、软件工程软件工程是为了摆脱软件危机而诞生的，主要思想是在软件开发过程中应用工程化原则。软件工程的三要素：方法、工具、工程。软件工程的主要内容：软件开发技术、软件工程管理。 软件工程的原则：抽象信息隐蔽模块化局部化确定性一致性 完备性可验证性。公共基础知识公共基础知识 软件工程基础软件工程基础三、软件生命周期 软件生命周期(Software Life Cycle,SLC)；将软件产

20、品从提出、实现、实用维护到停止实用退役的过程成为“软件生命周期”。公共基础知识公共基础知识 软件工程基础软件工程基础三、软件生命周期公共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析需求与需求分析需求分析的方法结构化分析方法数据流图与数据字典判定树与判定表软件需求规格说明书公共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析1.需求与需求分析 需求：用户对目标软件系统在功能、行为、性能、设计、 约束等方面的期望。 需求分析：发现用户需求的过程。 需求分析阶段的工作： (1)需求获取; (2)需求分析； (3)编写需求规格说明书； (4)需求评审。公共基础知识公共基础知识

21、软件工程基础软件工程基础四、需求分析2.需求分析的方法 A.面向数据流的结构化分析方法 SA； B.面向数据结构的Jackson方法 JSD； C.面向数据结构的结构化数据系统开发方法 DSSD; D.面向对象的分析方法 00A。公共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析3.结构化分析方法：数据流图DFD 数据流图DFD中的主要图形元素：加工/转换数据流存储文件/数据源源公共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析3.结构化分析方法：数据字典DD 数据字典DD是结构化分析方法的核心。 数据字典的作用：对数据流图DFD中出现的被命名图形元素进行确切的解释。公

22、共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析3.结构化分析方法：判定树与判定表公共基础知识公共基础知识 软件工程基础软件工程基础四、需求分析3.结构化分析方法：需求规格说明书。 软件需求规格说明书(SRS)是需求分析阶段的最后成果，将在软件工程的最后转换为用户手册。 软件需求规格说明书的作用：(1)便于用户、开发人员进行理解和交流；(2)反映出用户问题的结构，可作为软件开发工作的基础和依据；(3) 作为确认测试和验收的依据。公共基础知识公共基础知识 软件工程基础软件工程基础五、概要设计 软件设计的基本原理：抽象：把事物本质的共同特性提取出来而不考虑细节。模块化：把待开发软件分解

23、成若干个小的简单部分。信息隐蔽：在一个模块内包含的信息，对于不需要这些 信息的其它模块来说是不能访问的。模块独立性：评价设计好坏的重要度量指标。 内聚性和耦合性是模块独立性的两个定性标准：A.内聚性：一个模块内部各个元素间彼此结合的紧密程度。B.耦合性：模块间互相连接的紧密程度。 一款优秀的软件设计，应做到高内聚、低耦合。公共基础知识公共基础知识 软件工程基础软件工程基础五、概要设计 概要设计的任务：(1)设计软件系统结构；(2)确定软件的每一个模块；(3)确定模块之间的调用关系；(4)评价模块结构质量。采用的方法：结构化设计方法【SD】使用的工具：软件结构图SC。公共基础知识公共基础知识 软

24、件工程基础软件工程基础六、详细设计详细设计的任务：为软件结构图中每一个模块确定实现的 算法和数据结构。表示算法和数据结构的细节。采用的方法：结构化编程方法【SP】使用的工具：程序流程图、N-S图、问题分析图PAD 判定表 过程设计语言/伪码PDL公共基础知识公共基础知识 软件工程基础软件工程基础六、详细设计 程序流程图中的主要图形元素：加工步骤控制流逻辑条件公共基础知识公共基础知识 软件工程基础软件工程基础七、软件测试 软件测试的目的：尽可能多的发现错误。 错误理解：发现错误并改正；证明软件正确性。 软件测试的准则：所有测试追溯到需求；严格执行测试计划，排除测试随意性；充分注意测试中的群集现象

25、：程序中存在错误的概率与该 程序中已发现的错误数量成正比；程序员避免检测自己的程序；穷举测试不可能；妥善保存测试文档，为维护提供方便。公共基础知识公共基础知识 软件工程基础软件工程基础七、软件测试 软件测试的方法：(1)静态测试：由人工进行，无需借助计算机。(2)动态测试：基于计算机，实际运行软件进行测试。 A.白盒测试：逻辑覆盖、基本路径测试； B.黑盒测试：等价类划分、边界值分析、错误推测法、因果图。 软件测试的实施：1.单元测试（对每个模块进行测试）2.集成测试（将模块组装起来的同时进行测试）3.确认测试（验证软件的功能和性能是否满足需求）4.系统测试（评估系统环境下软件的功能）公共基础

26、知识公共基础知识 软件工程基础软件工程基础八、软件调试(Debug)软件调试的目的：诊断和改正程序中的错误。软件调试的基本步骤： 1.错误定位。【占据了调试的绝大多数工作量】 2.修改设计和代码，以排除错误。 3.进行回归实验，防止引进新的错误。公共基础知识公共基础知识 软件工程基础软件工程基础练习题公共基础公共基础知识知识 数据库设计基础数据库设计基础一、理解数据库 1.数据(Data)是描述事物的符号记录。 2.为什么引入数据库： (1)数据量大，数据多； (2)方便查找。公共基础知识公共基础知识 数据库设计基础数据库设计基础二、数据库原理术语1.数据(Data)是描述事物的符号记录。2.

27、数据库(DataBase,DB)数据的集合，是存放数据的仓库。3.数据库管理系统(DBMS)负责数据的管理。 (1)DBMS属于系统软件。(2)DBMS是数据库系统的核心。4.数据库应用系统(DBAS)利用DBMS开发的应用软件。5.数据库系统(DBS)使用了数据库技术的计算机，属于硬件系统。6.数据库管理员(DBA)是数据库系统的人的因素，负责管理、维护、监视数据库系统的运行。公共基础知识公共基础知识 数据库设计基础数据库设计基础二、数据库原理术语用户数据库应用系统数据库管理系统操作系统计算机硬件Access/Visual FoxPro/SQL Server等Windows XP/Vista

28、/7/2003等公共基础知识公共基础知识 数据库设计基础数据库设计基础三、数据库系统的三级模式和二级映射外模式外模式/子模式用户模式概念模式局部数据逻辑结构的描述内模式（物理模式）外模式-概念模式映射概念模式-内模式映射全局数据逻辑结构的描述数据库(DB)公共基础知识公共基础知识 数据库设计基础数据库设计基础四、数据模型1.数据模型的三层分类： 概念数据模型/概念模型； 逻辑数据模型/数据模型； 物理数据模型/物理模型。2.典型的概念数据模型：E-R模型（实体-联系模型） 实体：现实生活中的事物； 属性：表示实体的一些特征； 联系：实体之间的关联。公共基础知识公共基础知识 数据库设计基础数据库设计基础四、数据模型3.实体间的联系： (1)一对一（1:1） 学校校长 【计算机不予处理】 (2)一对多（1：m） 班级学生 【计算机可以直接处理】 (3)多对多（m:n）