全国计算机等级考试 计算机二级考试 公共基础知识老师给的资料.ppt
第一讲 数据结构与算法,考点一 算法的基本概念 考点1在笔试考试中考核的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容。,算法:指解题方案准确而完整的描述。算法的基本特征：可行性确定性有穷性拥有足够的情报。,考点2 算法复杂度,算法的时间复杂度-执行算法所需要的计算工作量,即所需基本运算的执行次数算法的空间复杂度-执行算法所需要的内存空间,D,A,A,D,考点3 数据结构的定义,数据集合中各数据的逻辑关系,即逻辑结构各数据元素在计算机中的存储关系,即存储结构,考点4 线性结构与非线性结构,如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构,线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。,考点5 栈及其基本运算,栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。,栈,bottom,top,出栈,入栈,栈顶,栈底,栈的特点：先进后出(FILO,fist in last out).栈中元素个数的求法：Top-bottom+1,B,C,B,B,A,队列,退队,入队,front,rear,队头,队尾,队列的特点：先进先出(FIFO,fist in last out)队列中元素个数求法rear-front,D,线性表的存储结构：顺序存储结构链式存储结构,顺序表的操作,优点：读取方便缺点：插入、删除操作 时需要移动,线性链表,当元素(数据)变化频繁度大线性表不宜用顺序存储结构链式存储结构：每个结点由两部分组成：数据域、指针域,a1,a2,a3,a1,a2,a3,head,a4,a5,a6,0,a1,a2,a3,head,a4,a5,a6,单链表,循环链表,a1,a2,a3,双向链表,D,考点7 树与二叉树及其基本性质,树是一种简单的非线性结构,A,B,C,D,E,F,H,G,根结点的度树的度层深度,11-911-310-909-909-308-908-307-907-306-3,结点拥有的子树数称为结点的度。树的度是树内各结点的度的最大值。树中结点的最大层次称为树的深度或高度。,度为0的结点称为叶子结点。,二叉树：它的特点是每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)并且，二叉树的子树有左右之分，其次是次序不能任意颠倒。考试要点：(1)结点个数(2)遍历顺序,A,B,E,F,C,K,M,L,二叉树的性质：性质1：在二叉树的第i层上至多有 个结点。性质2：深度为k的二叉树的最多结点数为,满二叉树与完全二叉树,A,B,E,F,C,K,M,A,B,E,F,C,K,C,B,A,C,25,H,满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。,完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,满二叉树与完全二叉树,A,B,E,F,C,K,M,A,B,E,F,C,K,考点1 二叉树的遍历（重点）,1.先根遍历(前序遍历)特点是：先访问根结点，接着访问左子树，最后访问右子树。,ABEFCK,2.中跟遍历(中序遍历)特点是：先访问左子树，再访问根结点，最后访问右子树。,EBFAKC,3.后根遍历(后序遍历)特点是：先访问左子树，再访问右子树，最后访问根结点。,EFBKCA,先根遍历(根左右)中根遍历(左根右)后根遍历(左右根),A,B,C,D,E,F,H,G,A,B,E,F,C,K,M,L,先根遍历：ABEFLCKM,中根遍历：EBLFAKMC,后根遍历：ELFBMKCA,DBXEAYFZC,D,顺序表的查找过程：,假设给定值 e=64,问:i=?,66,线性表为无序表时，对于长度为n的无序表，最坏的情况下比较n次。表采用链式存储结构时，对于长度为n的无序表，最坏的情况下比较n次。,B,二分法查找(对半查找)查找只适合用于顺序存储的有序表，对于长度为n的有序线性表，最坏的情况下比较 次。,ST.elem,ST.length,例如:key=64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界;high 指示查找区间的上界;mid=(low+high)/2。,ST.elem,ST.length,例如:key=66 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界;high 指示查找区间的上界;mid=(low+high)/2。,high,low,mid,high,low,1、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52,49,80,36,14,58,61,23,97,75,调整为:,14,23,36,49,52,58,61,75,80,97,13 38 49 65 76 97 6,6,97,76,65,49,38,13,0 1 2 3 4 5 6 7,6,简单插入排序法,简单插入排序法：最坏的情况需要比较的次数为,D,程序设计原则：清晰第一，效率第二。注重易读性，易理解，可以添加注释。,结构化程序设计方法的主要原则为：自顶向下逐步求精模块化限制使用goto语句。,A,A,模块独立性要高，有两原则高内聚（模块内）低耦合（两模块之间）,B,A,B,对象对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。,A,类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。,消息消息是一个实例和另一个实例之间传递的信息。,继承,继承是指类之间共享的属性和操作机制。继承分单继承和双继承。单继承指一个类只允许有一个父类，多重继承是指一个类允许有多个父类。,D,多态性,多态性是指同样的消息被不同的对象接受时可以导致完全不同的行动现象。,1 软件定义与软件特点,软件指的是程序、数据和相关文档的完整集合。根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。,程序,D,C,B,软件工程包括三个要素：方法、工具、过程。,软件工程包括3个要素：方法、工具和过程。软件工程方法为软件开发提供了如何做的技术。工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。,过程,2 软件工程过程与软件生命周期,软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的过程一般包括可行性分析研究与需求分析、设计、实现、测试、交付使用以及维护等活动，,A,C,开发,需求分析,软件生命周期分三个阶段：软件定义、软件开发、运行维护。,生命周期的主要活动阶段是：可行性研究与计划制定、需求分析、软件设计、软件实施、软件测试及运行与维护。,面向数据流的结构化分析方法，就是使用数据流图（DFD）、数据字典（DD）、结构化英语、判定表和判定树等工具，来建立一种新的、称为结构化规格说明的目标文档。,结构化分析方法的常用工具：数据流图（DFD）数据字典（DD）判定表判定树,C,从工程管理角度来看，软件设计包括：概要设计详细设计,A,B,典型的数据流类型有两种：变换型和事物型。,详细过程设计的常用工具有：（1）图形工具：程序流程图，N-S，PAD，HIPO。（2）表格工具：判定表。（3）语言工具：PDL（伪码）。,B,数据流程图,3 软件测试,软件测试是为了发现错误而执行程序的过程。软件测试的目的是：发现软件中的错误。,软件测试分为静态测试和动态测试。也可分为：白盒测试和黑盒测试。,静态测试无须执行被测代码。静态测试一般是指人工评审软件文档或程序，借以发现其中的错误。由于被评审的文档或程序不必运行，所以称为静态测试。动态测试是使被测代码在相对真实环境下运行。,静态测试,白盒测试的主要方法有逻辑覆盖、基本路径等。黑盒测试方法有等价划分法，边界值分析法、错误推测法、因果图等。,黑盒测试,白盒,白盒测试,软件测试过程分4个步骤，即单元测试集成测试验收测试系统测试,单元,软件调试在对程序进行了成功的测试之后将进入程序调试（通常称Debug，即排错）。程序的调试任务是诊断和改正程序中的错误。,软件测试的目的是发现软件中的错误。软件调试目的是发现并改正程序中的错误。软件测试贯穿整个软件生命周期。软件调试主要在开发阶段。,A,B,D,A,A,基本概念,数据（Data）数据库（Database）数据库管理系统（DBMS）数据定义语言（DDL）、数据操纵语言（DML）、数据控制语言（DCL）,C,数据模型,数据库系统的三级模式：（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。数据库系统的两级映射：（1）概念模式到内模式的映射；（2）外模式到概念模式的映射。,层次模型,基本结构：树形结构特性：每棵树的且仅的一个无双亲结点（根）；树中除根外所有结点有且仅有一个双亲支持的操作主要有：查询、插入、删除、更新,网状模型,基本结构：简单二级树（系），其基本数据单位为记录（实体集）,成员记录,首记录,关系模型,数据结构：采用二维表来表示，其由表框架及表的元组组成；表框架由n（属性元数）个命名的属性组成。关系模型：以二维表为基本所建立的模型,数据库设计生命周期,概念设计,方法：集中式模式设计法、视图集成设计法过程（E-R模型与视图集成设计法进行设计）：选择局部应用、视图设计（自顶向下、由底向上、由内向外）、视图集成（需要解决几种冲突以及消除冗余-命名冲突、概念冲突、域冲突、约束冲突）,逻辑设计,从E-R模型向关系模式转换：会遇到的转换问题-命名与属性域的处理、非原子属性处理、联系的转换,关系运算,关系的基本运算有两类：传统的集合运算有：并、差、交专门的关系运算有：选择、投影、联接,传统的集合运算举例,C,B,D,A,D,C,D,
