二级vb考试大纲.doc

二级vb考试大纲 二级公共基础知识大纲 基本要求：（1）、掌握算法的基本概念 （2）、掌握基本数据结构及其操作 （3）、掌握基本排序和查找算法 （4）、掌握逐步求精的呃呃结构化程序设计方法 （5）、掌握软件工程的基本算法，具有初步应用相关技术进行软件开发能力 （6）、掌握软件工程的基本算法知识，了解关系数据库的设计 考试内容： 一、基本数据结构与算法 基本数据结构与算法 （1）、数据结构的定义：数据是对客观事物来用计算机能够识别、存储和处理的形式所进行的描述 是指相互之间存在一种或多种特定关系的数据元素集合，即带有结构的元素集合 1）、分为：a、逻辑结构：是指从逻辑关系上描述数据，它与数据存储无关 b、存储结构：顺序存储和链接存储 顺序存储：是指把逻辑上相邻的结点存储在物理位置上相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来实现 链接存储：是指逻辑上相邻的结点在物理位置上可以相邻，也可以不相邻。结点间的逻辑关系由附加的指针来表示。 2）、数据结构的图形表示 3）、线性结构概念： 非线性结构概念： 算法：是对特定问题求解步骤的一种描述，是指令的有限 序列 算法复杂度：a、时间复杂度：是指执行一个算法所耗的时间 T（n）f(n)每一条语句的执行时间 b、空间复杂度：是指算法所需存储空间的度量 S(n)=O（f(n)）K字节，第i个数据元素ai的存储地址用Loc(ai)表示 顺序表的插入运算：是指线性表在顺序存储结构下的插入运算 顺序表的删除运算：是指线性表在顺序存储结构下的删除运算 data next 4、线性单链表： 单链表结构： 建立单链表从空表开始 NULL、O、n表示指针值域为空 单链表的查找：按值查找；按顺序查找 单链表的插入：在单链表中指定元素之间插入一个新的元素 按值插入和按序号进行插入 步骤:a、申请新结点 b、查找 c、修改链接 单链表的删除：是指在单链表中删除一个数据元素 步骤：a、查找 b、修改链接 c、释放结点 Llink Data Rlink 5、双链表：双链表结构： 6、栈：一种特殊线性列表。它是限定仅在一端进行插入或删除操作的线性行为 （1）、 栈顶：允许进行插入或删除操作的一端 栈底：不允许进行插入或删除操作的一端 （2）、栈是根据“先进后出”或“后进先出”的原则 （3）、顺序栈及其基本运算 顺序栈：用顺序存储结构来存储的栈 基本运算：入栈：①、修改指针 ②、插入 出栈：①、退栈②修改指针 读栈顶元素： 7、队列： （1）、定义：一种特殊的线性表，它是限定在表的一端进行插入操作而在另一端进行操作的线性表 （2）、顺序队列：先进先出或后进后出 （3）、顺序队列的基本运算： 8、树的基本概念：n（n≥0）个结点的有限集合 （1）、有且仅有一个结点称为树的根，根结点没有前驱结点 其余n-1个结点被分为m(m≥0)个互不相交的有限集合 （2）、基本术语 结点：树中的每个数据元素 双亲结点：每个结点的上一层结点 孩子结点：每个结点的子树的根 叶子结点：树中度为0的结点，即无后继的结点 分支结点：树中度不为0的结点 结点的度：每个结点拥有子树的个数 树的度：所有结点的度中最大的值 结点的层次： 树的深度：所有结点的层数中最大的值 8、二叉树 （1）、定义 （2）、性质：a、在二叉树的第i层上，至少有2的k-1次方个结点 b、在深度为k的二叉树中，至多有2的k次方-1个结点 c、在任意一棵二叉树中，叶子结点的数目比度为2的结点数目多一个 （3）、5种形态 （4）、二叉树的遍历 先序遍历：是指二叉树为空则遍历结束否则 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历：若二叉树为空则遍历结束否则 中序遍历左子树 访问根结点 中序遍历右子树 后序遍