二级vb考试大纲

《二级vb考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二级vb考试大纲二级公共基础知识大纲基本要求：（1）、掌握算法的基本概念（2）、掌握基本数据结构及其操作（3）、掌握基本排序和查找算法（4）、掌握逐步求精的呃呃结构化程序设计方法（5）、掌握软件工程的基本算法，具有初步应用相关技术进行软件开发能力（6）、掌握软件工程的基本算法知识，了解关系数据库的设计考试内容：一、基本数据结构与算法1、基本数据结构与算法（1）、数据结构的定义：数据是对客观事物来用计算机能够识别、存储和处理的形式所进行的描述是指相互之间存在一种或多种特定关系的数据元素集合，即带有结构的元素集合1）、分为：a、逻辑结构：是指

2、从逻辑关系上描述数据，它与数据存储无关b、存储结构：顺序存储和链接存储顺序存储：14是指把逻辑上相邻的结点存储在物理位置上相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来实现链接存储：是指逻辑上相邻的结点在物理位置上可以相邻，也可以不相邻。结点间的逻辑关系由附加的指针来表示。2）、数据结构的图形表示3）、线性结构概念：非线性结构概念：1、算法：是对特定问题求解步骤的一种描述，是指令的有限序列算法复杂度：a、时间复杂度：是指执行一个算法所耗的时间T（n）=O(f(n))T(n)时间耗费O数量级f(n)每一条语句的执行时间b、空间复杂度

3、：是指算法所需存储空间的度量S(n)=O（f(n)）S(n)空间耗费2、线性结构表的定义（1）线性表的顺序存储结构：Loc(ai)=Loc(ai-1)+k(2≦i≦n)Loc(ai)=Loc(a1)+(i-1)*k(1≤i≤n)14K字节，第i个数据元素ai的存储地址用Loc(ai)表示（1）顺序表的插入运算：是指线性表在顺序存储结构下的插入运算（2）顺序表的删除运算：是指线性表在顺序存储结构下的删除运算datanext4、线性单链表：单链表结构：建立单链表从空表开始NULL、O、n表示指针值域为空单链表的查找：按值查找；按顺序查找单链表

4、的插入：在单链表中指定元素之间插入一个新的元素按值插入和按序号进行插入步骤:a、申请新结点b、查找c、修改链接单链表的删除：是指在单链表中删除一个数据元素步骤：a、查找b、修改链接c、释放结点LlinkDataRlink5、双链表：双链表结构：6、栈：一种特殊线性列表。它是限定仅在一端进行插入或删除操作的线性行为（1）、栈顶：允许进行插入或删除操作的一端栈底：不允许进行插入或删除操作的一端14（2）、栈是根据“先进后出”或“后进先出”的原则（3）、顺序栈及其基本运算顺序栈：用顺序存储结构来存储的栈a、基本运算：入栈：①、修改指针②、插入出

5、栈：①、退栈②修改指针读栈顶元素：7、队列：（1）、定义：一种特殊的线性表，它是限定在表的一端进行插入操作而在另一端进行操作的线性表（2）、顺序队列：先进先出或后进后出（3）、顺序队列的基本运算：8、树的基本概念：n（n≥0）个结点的有限集合（1）、有且仅有一个结点称为树的根，根结点没有前驱结点其余n-1个结点被分为m(m≥0)个互不相交的有限集合（2）、基本术语结点：树中的每个数据元素双亲结点：每个结点的上一层结点孩子结点：每个结点的子树的根叶子结点：树中度为0的结点，即无后继的结点分支结点：树中度不为0的结点结点的度：每个结点拥有子树

6、的个数树的度：所有结点的度中最大的值14结点的层次：树的深度：所有结点的层数中最大的值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、后序遍历

7、左子树14a、后序遍历右子树b、访问根结点9、顺序查找（检索）二分法查找：数据元素按照升序排列或降序排列过程：（1）、若线性表中间位置记录的关键字值与给定的关键字值相等，则查找成功（2）、若线性表中间位置记录的关键字值大于给定的关键字值，则线性表的前半部分子表以同样的方法进行查找（3）、若线性表中间位置记录的关键字值小于给定的关键字值，则线性表的后半部分子表以同样的方法进行查找（4）、重复以上过程，直到查找成功位置；或直到子表不存在为止基本排序算法1）、插入类算法：是指将无序序列中的元素依次插入有序序中列a、直接插入排序：是指将元素依次插

8、入已经排好的线性表中适当位置的排序方法（在最坏的情况下需要进行n(n-1)/2次比较）b、折半插入排序c、希尔排序：（缩小增量排序）14先将整个无序序列分为若干个较小的子序列，然后再分别对子序