全国计算机等级考试二级共公基础知识(NCRE 2 P)教案

二级公共基础知识总目录第1章数据结构与算法第2章程序设计基础第3章软件工程基础第4章数据库设计基础第1章数据结构与算法1.1算法1.1.1算法的基本概念1.1.2算法复杂度1.2数据结构的基本概念1.2.1什么是数据结构1.2.2数据结构的图形表示1.2.3线性结构与非线性结构1.3线性表及其顺序存储结构1.3.1线性表的基本概念1.3.2线性表的顺序存储结构1.3.3顺序表的插入运算1.3.4顺序表的删除运算1.4栈和队列1.4.1栈及其基本运算1.4.2队列及其基本运算1.5线性链表1.5.1线性链表的基本概念1.5.2线性链表的基本运算1.5.3循环链表及其基本运算1.6树与二叉树1.6.1树的基本慨念1.6.2二叉树及其基本性质1.6.3二叉树的存储结构1.6.4二叉树的遍历1.7查找技术1.7.1顺序查找1.7.2二分法查找1.8排序技术1.8.1交换类排序法1.8.2插入类排序法1.8.3选择类排序法习题11.1算法1.1.1算法的基本概念算法：对解题方案准确而完整的描述1、算法的特征可行性确定性有穷性（可能完成、合理时间）拥有足够的情报2、算法的基本要素（1）对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输（2）算法的控制结构：控制结构（顺序、选择、循环），描述工具（传统流程图、N-S流程图、描述语言等）3、算法设计基本方法列举法归纳法递推递归（直接递归：显示调用自己，间接递归：PQP）减半递推技术回溯法（穷试）1.1.2算法复杂度（时间、空间）1、算法的时间复杂度（执行算法所需的计算工作量）（所执行的基本运算次数）平均性态分析（从数组中找某个值时，恰为第1个，则只比较一次）最坏情况复杂度（上述问题中，比较的最大次数）例1.2（略）2、算法的空间复杂度（指执行这个算法所需的内存空间）3516788543293321544616212933354346547885无序表有序表1.2数据结构的基本概念数据结构涉及三方面问题：数据的逻辑结构：数据元素间固有逻辑关系数据的存储结构：数据元素在计算机中的存储关系对各种数据结构进行的运算1.2.1什么是数据结构例1.3无序表的顺序查找与有序表的对分查找1、数据的逻辑结构包含信息和前后件（直接前驱与直接后续）关系（与存储位置无关）两方面2、数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式一般数据的位置关系与逻辑关系不同，故在存储数据信息的同时，还要存储数据元素间的前后件关系一般数据的逻辑结构可采用顺序、链接、索引等存储结构1.2.2数据结构的图形表示1.2.3线性结构与非线性结构（按数据元素间前后件关系的复杂程度分）线性结构：有且只有一个根结点，每个结点只有一个前（后）件（增删后仍如此）非线性结构：不是线性结构的数据结构春夏秋冬儿子父亲女儿1.3线性表及其顺序存储结构1.3.1线性表的基本概念非空线性表的结构特征：有且只有一个无前件的根结点有且只有一个无后件的终端结点其他结点有且只有一个前件和后件线性表的长度：结点的个数。为零时称为空表线性表举例：英文小写字母表、四季矩阵（元素为行（列）向量，每一个（列）向量又是一个线性表）1.3.2线性表的顺序存储结构线性表顺序存储的特点：存储空间是连续的元素在存储空间按逻辑顺序存放采用顺序存储的线性表的主要运算有：插入、删除、查找、排序、分解、合并、复制、逆转1.3.3顺序表的插入运算在第i个元素之前插入新元素时，需要移动n-i+1个元素在存储空间满的情况下插入新元素，将发生上溢错误效率：平均移动一半的元素（第1位置全移动，最后位置不用动）1.3.4顺序表的删除运算原理同插入运算3516788543293321__原表新表35181678854329332165顺序表的插入1.4栈和队列1.4.1栈及其基本运算栈：限定在一端进行插入与删除的线性表特征：FILO、具有记忆功能运算：入栈：插入新元素，使top+1。Top=m(Max)时将发生上溢错误退栈：删除元素，使top-1。Top=0(栈空)时将发生下溢错误读栈顶元素：DCBAbottom→top→入栈↓退栈↑76543211.4.2队列及其基本运算队列：允许在一端进行插入、另一端进行删除的线性表特征：FIFO循环队列及其运算：标志：s=0队列空s=1队列非空初始状态：s=0rear=front=m入队：rear=rear+1ifrear=m+1thenrear=1ifs=1andrear=frontthen队列满，上溢退队：front=front+1iffront=m+1thenfront=1ifs=0then队列空，下溢退队←↑frontABC↑rear←入队DCBAfront→rear→m=61.5线性链表1.5.1线性链表的基本概念线性表的顺序存储结构的缺点：增删元素时平均移动一半的元素；表已满时将上溢，在其后找不到与之连续的可用空间时运算失败或中断；不便于对存储空间的动态分配线性链表：线性单链表、双向链表、循环链表1、线性单链表2、双向链表3、带链的栈（略）4、带链的队列（略）D1P2HEADD2P3DnNULL/0…0P2HEADP1P3…D1D2P2P3D3P30D4数据域指针域1.5.2-31.5.2线性链表的基本运算插入/删除（合并/分解、逆转、复制、排序/查找）1.5.3循环链表及其基本运算D1P2HEADD2P3DnP表头…表头P1D1PxHEADD2P3DnNULL/0…DxP21.6树与二叉树1.6.1树的基本慨念树是一种简单的非线性结构基本术语：父结点：每个结点只有一个前件（根结点/根）子结点：每个结点可以有多个后件（叶子结点）度：一个结点所拥有的后件个数树的度：所有结点中最大的度树的深度：树的最大层次子树：以某结点为根的树RKPQDBENOTCHXSZWAFYGLM1.6.2-41.6.2二叉树及其基本性质1、二叉树的定义非空二叉树只有一个根结点每个结点最多有两棵子树（左子树、右子树）2、二叉树的基本性质性质1：第k层上最多有2k-1（k=1）个结点性质2：深度为m的二叉树最多有2m-1个结点性质3：度为0的结点总比度为2的结点多一个性质4：具有n个结点的二叉树，其深度至少为[log2n]+13、满二叉树4、完全二叉树（只有最后一层只缺少右边的若干结点）1.6.3二叉树的存储结构二叉树通常采用链式存储结构（类似于双向链表）1.6.4二叉树的遍历前序遍历DLR中序遍历LDR后序遍历LRD查看答案FCADBEGHPACBDFEHGP1.7查找技术1.7.1顺序查找从第一个开始逐个比较，最坏情况是比较到最后一个，平均要比较一半的元素无序线性表：不论顺序或链式存储结构，都只能用顺序查找有序线性表：若为链式存储结构，则只能用顺序查找对于长度为n的表，最坏情况下，需比较n次1.7.2二分法查找只适于顺序存储的有序线性表对于长度为n的表，最坏情况下，需比较log2n次1.8排序技术（针对顺序存储的线性表）1.8.1交换类排序法1、冒泡排序法一次比较排除一个逆序对于长度为n的表，最坏情况下需比较n(n-1)/2次2、快速排序法选取分界线，再将小的放前、大的放后，如此多次1.8.2插入类排序法1、简单插入排序法无序元素插入到有序线性表中对于长度为n的表，最坏情况下需比较n(n-1)/2次2、希尔排序法（ShellSort）改进的简单插入排序法对于长度为n的表，最坏情况下需比较O（n1.5）次1.8.3选择类排序法1、简单选择类排序法每次扫描整个线性表，找出最小元素并置于最前。如此在子表中重复对于长度为n的表，最坏情况下需比较n(n-1)/2次2、堆排序法对于长度为n的表，最坏情况下需比较O（nlog2n）次第2章程序设计基础2.1程序设计方法与风格2.2结构化程序设计2.2.1结构化稃序设计的原则2.2.2结构化程序的荩本结构与特点2.2.3结构化程序没计原则和方法的应用2.3面向对象的程序设计2.3.1关于面向对象方法2.3.2面向对象方法的基本慨念习题2第2章程序设计基础2.1程序设计方法与风格结构化程序设计面向对象的程序设计影响良好程序设计风格的因素（详见课本）1、源程序文档化2、数据说明的方法3、语句的结构4、输入和输出2.2结构化程序设计2.2.1结构化程序设计的原则自顶向下逐步求精模块化限制使用goto语句2.2.2结构化程序的基本结构与特点顺序结构选择结构（简单选择、多分支选择）重复结构（当型循环、直到型循环）2.2.3结构化程序设计原则和方法的应用2.3面向对象的程序设计2.3.1关于面向对象方法（主要优点）1、与人类习惯的思维方法一致2、稳定性好3、可重用性好（模块具有功能内聚性）4、易于开发大型软件产品5、可维护性好2.3.2面向对象方法的基本概念1、对象属性：静态特征方法：执行操作特点：惟一、分类、多态、封装、模块独立2、类和实例3、消息：不同实例间信息传递，类似调用4、继承5、多态性：不同对象接收同一消息执行不同操作第3章软件工程基础3.1软件工程基本概念3.1.1软件定义与软件特点3.1.2软件危机与软件工程3.1.3软件工程过程软件生命周期3.1.4软件工程的目标与原则3.1.5软件开发工具软件开发环境3.2结构化分析方法3.2.1需求分析与需求分析方法3.2.2结构化分析方法3.2.3软件需求规格说明书3.3结构化设计方法3.3.1软件设计的基本概念3.3.2概要设汁3.3.3详细设计3.4软件测试3.4.1软件测试的目的3.4.2软件测试的准则3.4.3软件测试技术与方法综述3.4.4软件测试的实施3.5程序的调试3.5.1基本概念3.5.2软件调试方法习题3第3章软件工程基础2-13.1软件工程基本概念3.1.1软件定义与软件特点软件：程序、数据、相关文档的完整集合3.1.2软件危机与软件工程软件危机：软件开发与维护的成本、质量、生产率等问题软件工程：需求计划、可行性研究、工程审核、质量监督等软件工程三要素：方法、工具、过程3.1.3软件工程过程与软件生命周期1、软件工程过程Plan软件规格说明Do软件开发Check软件确认Action软件演进2、软件生命周期软件产品从提出、实现、使用维护，到停止使用退役的过程分为三个阶段：软件定义：可行性研究、软件开发软件运行维3.1.4软件工程的目标与原则1、软件工程的目标（有效、可靠、可理解、可维护、可重用、可适应、可移植、可追踪、可互操作、满足用户需求）2、软件工程的原则（抽象、封装、模块化、局部化、确定性、一致性、完备性、可验证性）3.1.5软件开发工具与软件开发环境（略）3.2结构化分析方法（略）数据流图、数据字典、判断树、判断表3.3结构化设计方法3.3.1软件设计的基本原理抽象模块信息隐蔽模块独立性（内聚性—高、耦合性—低）3.3.2概要设计3.3.3详细设计（过程设计工具）1、流程图2、N-S图3、PAD图4、过程设计语言PDL（伪代码）第3章软件工程基础2-23.4软件测试3.4.1软件测试的目的3.4.2软件测试的准则3.4.3软件测试技术与方法1、静态测试与动态测试2、白盒测试与黑盒测试3.4.4软件测试的实施1、单元测试——白盒2、集成测试3、确认测试——黑盒4、系统测试（基于计算机系统）3.5程序的调试3.5.1基本概念1、基本步骤错误