《国家二级vb考试补充知识点》由会员分享，可在线阅读，更多相关《国家二级vb考试补充知识点（32页珍藏版）》请在金锄头文库上搜索。
1、VB二级考试涉及到的知识点,1 数据结构（线性表、二叉树、栈、线性数据结构、树的中序遍历和后序遍历） 2 数据库（数据操纵语言、关系运算选择、 投影、连接） 3 软件工程（软件测试如模块测试、单元测试）,1 链表(单链表 和循环链表) 2 栈 3 队列 4 递归 5 树,单链表 (Singly Linked List),特点每个元素(表项)由结点(Node)构成。线性结构 结点可以不连续存储,表可扩充,单链表的存储映像,单链表中的插入与删除,插入第一种情况：在第一个结点前插入newnodelink = first ; first = newnode；,（插入前） （插入后）,循环链表 (Cir
2、cular List),循环链表是单链表的变形。 循环链表最后一个结点的link指针不为 0 (NULL)，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,循环链表的示例带表头结点的循环链表,用循环链表求解约瑟夫问题,约瑟夫问题的提法n 个人围成一个圆圈，首先第2个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 例如 n = 3 m = 8,例如 n = 3 m = 8
3、,2 栈 ( Stack ),只允许在一端插入和删除的顺序表 允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom) 特点后进先出 (LIFO),进栈示例,3 队列 ( Queue ),定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out),队列的进队和出队,进队时队尾指针先进一 rear = rear + 1，再将新元素按 rear 指示位置加入。出队时队头指针先进一 front = front + 1，再将下标为 front 的元素取出
4、。队满时再进队将溢出出错；队空时再出队将队空处理。,队列的应用举例 逐行打印二项展开式 (a + b)i 的系数,杨辉三角形 (Pascals triangle),分析第 i 行元素与第 i+1行元素的关系,目的是从前一行的数据可以计算下一行的数据,递归的概念,递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 在以下三种情况下，常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的,定义是递归的,求解阶乘函数的递归算法long Factorial ( long n ) if ( n
5、= 0 ) return 1;else return n*Factorial (n-1); ,例如，阶乘函数,求解阶乘 n! 的过程,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法long Fib ( long n ) if ( n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,结点(node) 结点的度(degree) 分支
6、(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点,兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree),有序树无序树森林,二叉树 (Binary Tree),二叉树的定义,二叉树的五种不同形态,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,性质1 若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i 0)证明用数学归纳法 性质2 高度为k的二
7、叉树最多有 2k+1-1个结点。 (k -1)证明用求等比级数前k项和的公式 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有n0n21,二叉树的性质,证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1n2 = n0 - 1 n0 = n2 + 1 定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree)若设二叉树的高度为h
8、，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。,性质4 具有n个结点的完全二叉树的高度为log2(n+1) -1 证明：设完全二叉树的高度为h，则有2h - 1 n 2h+1 - 1 2h n+1 2h+1 取对数 h log2(n+1) h+1,完全二叉树的数组表示 一般二叉树的数组表示,二叉树的表示,数组表示,二叉树遍历 (Binary Tree Traversal),所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L遍历根的右子树记作 R则可能
9、的遍历次序有前序 VLR 镜像 VRL中序 LVR 镜像 RVL后序 LRV 镜像 RLV,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。遍历结果a + b * c - d - e / f,中序遍历 (Inorder Traversal),表达式语法树,前序遍历 (Preorder Traversal),前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。遍历结果 - + a * b - c d / e f,后序遍历 (Postorder Traversal),后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。遍历结果 a b c d - * + e f / -,
