二级vb考试大纲.doc

二级vb考试大纲二级公共基础知识大纲 基本要求：（1）、掌握算法的基本概念 （2）、掌握基本数据结构及其操作 （3）、掌握基本排序和查找算法 （4）、掌握逐步求精的呃呃结构化程序设计方法 （5）、掌握软件工程的基本算法，具有初步应用相关技术进行软件开发能力 （6）、掌握软件工程的基本算法知识，了解关系数据库的设计考试内容：一、基本数据结构与算法1、 基本数据结构与算法（1）、数据结构的定义：数据是对客观事物来用计算机能够识别、存储和处理的形式所进行的描述是指相互之间存在一种或多种特定关系的数据元素集合，即带有结构的元素集合 1）、分为：a、逻辑结构：是指从逻辑关系上描述数据，它与数据存储无关 b、存储结构：顺序存储和链接存储顺序存储：是指把逻辑上相邻的结点存储在物理位置上相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来实现链接存储：是指逻辑上相邻的结点在物理位置上可以相邻，也可以不相邻。结点间的逻辑关系由附加的指针来表示。 2）、数据结构的图形表示 3）、线性结构概念： 非线性结构概念：2、 算法：是对特定问题求解步骤的一种描述，是指令的有限 序列 算法复杂度：a、时间复杂度：是指执行一个算法所耗的时间 T（n）=O(f(n) T(n)时间耗费 O数量级 f(n)每一条语句的执行时间 b、空间复杂度：是指算法所需存储空间的度量 S(n)=O（f(n)） S(n)空间耗费3、 线性结构表的定义（1） 线性表的顺序存储结构： Loc(ai)=Loc(ai-1)+k(2in) Loc(ai)=Loc(a1)+(i-1) *k(1in) K字节，第i个数据元素ai的存储地址用Loc(ai)表示（2） 顺序表的插入运算：是指线性表在顺序存储结构下的插入运算（3） 顺序表的删除运算：是指线性表在顺序存储结构下的删除运算datanext4、线性单链表：单链表结构： 建立单链表从空表开始 NULL、O、n表示指针值域为空 单链表的查找：按值查找；按顺序查找 单链表的插入：在单链表中指定元素之间插入一个新的元素 按值插入和按序号进行插入 步骤:a、申请新结点 b、查找 c、修改链接 单链表的删除：是指在单链表中删除一个数据元素 步骤：a、查找 b、修改链接 c、释放结点LlinkDataRlink5、双链表：双链表结构：6、栈：一种特殊线性列表。它是限定仅在一端进行插入或删除操作的线性行为 （1）、 栈顶：允许进行插入或删除操作的一端 栈底：不允许进行插入或删除操作的一端 （2）、栈是根据“先进后出”或“后进先出”的原则（3）、顺序栈及其基本运算 顺序栈：用顺序存储结构来存储的栈a、 基本运算：入栈：、修改指针 、插入 出栈：、退栈修改指针 读栈顶元素：7、队列：（1）、定义：一种特殊的线性表，它是限定在表的一端进行插入操作而在另一端进行操作的线性表（2）、顺序队列：先进先出或后进后出（3）、顺序队列的基本运算：8、树的基本概念：n（n0）个结点的有限集合（1）、有且仅有一个结点称为树的根，根结点没有前驱结点其余n-1个结点被分为m(m0)个互不相交的有限集合（2）、基本术语 结点：树中的每个数据元素 双亲结点：每个结点的上一层结点 孩子结点：每个结点的子树的根 叶子结点：树中度为0的结点，即无后继的结点 分支结点：树中度不为0的结点 结点的度：每个结点拥有子树的个数 树的度：所有结点的度中最大的值 结点的层次： 树的深度：所有结点的层数中最大的值8、二叉树（1）、定义（2）、性质：a、在二叉树的第i层上，至少有2的k-1次方个结点 b、在深度为k的二叉树中，至多有2的k次方-1个结点 c、在任意一棵二叉树中，叶子结点的数目比度为2的结点数目多一个（3）、5种形态（4）、二叉树的遍历 先序遍历：是指二叉树为空则遍历结束否则a、 访问根结点b、 先序遍历左子树c、 先序遍历右子树 中序遍历：若二叉树为空则遍历结束否则a、 中序遍历左子树b、 访问根结点c、 中序遍历右子树 后序遍历：若二叉树为空则遍历结束否则a、 后序遍历左子树b、 后序遍历右子树c、 访问根结点9、顺序查找（检索） 二分法查找：数据元素按照升序排列或降序排列 过程：（1）、若线性表中间位置记录的关键字值与给定的关键字值相等，则查找成功 （2）、若线性表中间位置记录的关键字值大于给定的关键字值，则线性表的前半部分子表以同样的方法进行查找 （3）、若线性表中间位置记录的关键字值小于给定的关键字值，则线性表的后半部分子表以同样的方法进行查找 （4）、重复以上过程，直到查找成功位置；或直到子表不存在为止 基本排序算法 1）、插入类算法：是指将无序序列中的元素依次插入有序序中列 a、直接插入排序：是指将元素依次插入已经排好的线性表中适当位置的排序方法（在最坏的情况下需要进行n(n-1)/2次比较） b、折半插入排序 c、希尔排序：（缩小增量排序） 先将整个无序序列分为若干个较小的子序列，然后再分别对子序列按照关键字进行直接插入排序先做宏观调整，再做微观调整2）、交换型排序 a、冒泡排序：将第一个数据元素与第二个数据元素进行比较，若为逆序，则进行交换位置；然后比较第二个数据元素与第三个数据元素；以此类推。（在长度为n的线性表中需进行n(n-1)/2次比较） b、快速排序：【13 15 7 10 30 4 8 25】 【 8 4 7 10 】 13 【30 15 25】 【7 4】 8 【 10】 13 【30 15 25】 4 7 8 10 13 【30 15 25】 4 7 8 10 13 【25 15】 30 4 7 8 10 13 15 25 303）、选择类排序 a、简单选择排序：（0）【13 15 6 10 20 8 3 19】 （1）3 【15 6 10 20 8 13 19】 （2）3 6 【15 10 20 8 13 19】 （3）3 6 8 【10 20 15 13 19】 （4）3 6 8 10 【20 15 13 19】 （5）3 6 8 10 13 【15 20 19】 （6）3 6 8 10 13 15 【20 19】 （7）3 6 8 10 13 15 19 20在长度为n的线性表中需进行n(n-1)/2次比较 b、树形选择排序 c、堆排序二、程序设计基础 1、程序设计的方法与风格 （1）、程序设计语言分类 a、面向机器语言：机器语言和汇编语言 b、高级语言 （2）、程序设计语言的选择 、系统用户的要求 、工程的规模 、软件的运行环境、软件开发人员的知识、软件的可移植性要求、软件的应用领域(3)、程序设计方法与风格程序设计方法：结构化程序设计和面向对象程序设计 、源程序文档化、标示符的命名及说明、语句的构造及书写、输入和输出2、结构化程序设计结构化程序设计的思想：自顶向下、逐步求精、模块化、限制使用goto语句、把整个任务看作一个系统、把系统分成几个基本模块，看做子系统；然后进行分解，直到成为最小模块为止、每个最小模块都可完成独立的功能，可以独立编程，程序结构使用顺序、分支和循环三种基本结构、模块与模块之间的关系要尽量简单而明确，即规定模块接口信息的性质、数量和规则等、程序只有一个入口和一个出口3、面对对象程序设计基本原理：使用现实世界的概念抽象的思考问题从而自然地解决问题。它强调模拟现实世界的概念而不强调算法，它鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考 、对象、类、封装、消息：是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。、继承：是面向对象方法的一个主要特征，是使用已有的类的定义作为基础建立新的定义技术。广义地说，继承是指能够直接获得已有的性质和特征，二不必重复定义他们，所以继承是指类之间共享属性和操作机制、多态性三、软件工程基础 1、软件工程基本概念：软件包括程序和文档 （1）、软件危机：、软件需求的增长得不到满足、软件开发的成本和进度难以控制、软件质量的产品无法保证、软件产品难以维护、软件成本不断提高、软件开发生产率的提高速度难以满足社会需求增长率 （2）、软件生命周期：从提出、实现、使用维护到停止使用的过程 软件工程的基本原则：、抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性2、结构化分析方法 数据化分析：就是使用数据流图（DFD）、数据字典（DD）判定表和判定树等工具，来建立一种新的、称为结构化规格说明的目标文档 （1）、数据流图：是结构化分析方法中用于表示系统逻辑买模型的一种工具，它从数据传递和加工的角度，一图形的方式描绘数据在系统中流动和处理的过程 基本符号：数据流名处理名文件名外部实体名字 数据流 数据处理 数据存储 外部实体 （2）、数据字典：是为了描述在结构化分析过程中定义的对象的内容而使用的一种一半形式化的工具 （3）、判定表： （4）、判定树：3、软件需求规格说明书：是需求分析阶段的最后成果，是软件开发过程中的重要文档之一。 （1）、引言： （2）、项目概述： （3）、具体需求：4、结构化设计方法： 1）、软件设计：把软件需求转换成软件表示的过程。 a、总体设计：又称概要设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构和数据库模式。 （1）、总体设计的任务 、设计软件系统结构 、数据结构和数据设计 、系统可靠性和安全性的设计 、编写文档并复审 （2）、总体设计的工具 、层次图符 号含 义用于表示模块，在方框中标明模块名称用于描述模块之间的调用关系 、结构图 （3）、总体设计的原则 、降低模块的耦合性，提高模块的内聚性 、保持适中的模块规格 、模块应具有高扇入和适当的扇出 、软件结构图中的深度和宽度都不宜过大 、模块的作用域应处于其控制域范围之内 、尽量降低模块的接口复杂度 b、详细设计：确定每个模块的实现算法和局部数据结构，用适当的方法表示算法和数据结构的细节。（1）、详细设计的任务 、确定每个模块的具体算法 、确定每个模块的内部数据结构及数据库的物理结构 、确定模块接口的具体细节 、为每个模块设计一组测试用例 、编写详细设计文档及复审（2）、详细设计工具 、程序流程图 一般处理框 输入/输出框 判断框 流程线 起止框 、N-S图 、P