国家二级VB考试补充知识点

《国家二级VB考试补充知识点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、VB二级考试涉及到的知识点1数据结构（线性表、二叉树、栈、线性数据结构、树的中序遍历和后序遍历）2数据库（数据操纵语言、关系运算选择、投影、连接）3软件工程（软件测试如模块测试、单元测试）1链表(单链表和循环链表)2栈3队列4递归5树单链表(SinglyLinkedList)特点每个元素(表项)由结点(Node)构成。线性结构结点可以不连续存储,表可扩充单链表的存储映像单链表中的插入与删除插入第一种情况：在第一个结点前插入newnode→link=first;first=newnode；（插入前）（插入后）循环链表(CircularList)循环链表是单链表的变形。循环链表

2、最后一个结点的link指针不为0(NULL)，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。循环链表的示例带表头结点的循环链表用循环链表求解约瑟夫问题约瑟夫问题的提法n个人围成一个圆圈，首先第2个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。例如n=3m=8例如n=3m=82栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(to

3、p)，另一端称为栈底(bottom)特点后进先出(LIFO)进栈示例3队列(Queue)定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)队列的进队和出队进队时队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。队列的应用举例—逐行打印二项展开式(a+b)i的系数杨辉三角形(Pascal’striang

4、le)分析第i行元素与第i+1行元素的关系目的是从前一行的数据可以计算下一行的数据递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。在以下三种情况下，常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数求解阶乘n!的过程计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法l

5、ongFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}问题的解法是递归的例如，汉诺塔(TowerofHanoi)问题迷宫问题小型迷宫路口动作结果1(入口)正向走进到22左拐弯进到33右拐弯进到44(堵死)回溯退到33(堵死)回溯退到22正向走进到55(堵死)回溯退到22右拐弯进到66左拐弯进到7(出口)43521766左0直2右0行3行5行60040000007007小型迷宫的数据5树和森林的概念树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root

6、)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)有序树无序树森林二叉树(BinaryTree)

7、二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。性质1若二叉树的层次从0开始,则在二叉树的第i层最多有2i个结点。(i0)[证明用数学归纳法]性质2高度为k的二叉树最多有2k+1-1个结点。(k-1)[证明用求等比级数前k项和的公式]性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1二叉树的性质证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉