计算机二级备考知识思维导图

a. 结点的度：结点所拥有的子树的个数。

b. 叶子结点：度为 0 的结点。

c. 分支结点：除叶子结点以外的结点。

d. 结点的层次：根结点在第一层，同一层上左右结点的子结点在下一层。

e. 树的深度：所处层次最大的那个结点的层次。

f. 树的度：树中所有结点的度的最大值。

二叉树是一种特殊的树形结构，每个结点最多只有两棵子树，且有左右之分 不能互换。

性质 1 在二叉树的第 k 层上，最多有 2k-1(k≥1）个结点。

性质 2 深度为 m 的二叉树最多有 2m-1 个结点。

性质 3 在任意一棵二叉树中，度为 0 的结点（叶子结点）总是比度为 2 的结 点多一个。

（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为 n(n－1)/2。

（2）快速排序法，在最坏的情况下，快速排序需要比较次数为 n(n－1)/2。

（1）简单插入排序法，最坏情况需要 n(n-1)/2 次比较；

（2）希尔排序法，最坏情况需要 O(n1.5)次比较。

（1）简单选择排序法，最坏情况需要 n(n-1)/2 次比较；

（2）堆排序法，最坏情况需要 O(nlog2n)次比较

1、源程序文档化； 2、数据说明的方法； 3、语句的结构； 4、输入和输出。

自顶向下，逐步求精，模块化，限制使用 goto 语句。

属性：即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象 的操作来改变。

类：是具有相似属性与操作的一组对象。类是关于对象性质的描述

类是对 象的抽象，对象是其对应类的一个实例。

消息：是一个实例与另一个实例之间传递的信息。

消息的组成包括：

继承：是使用已有的类定义作为基础建立新类的定义技术，广义指能够直接 获得已有的性质和特征，而不必重复定义他们。

继承具有传递性，一个类实际上继承了它上层的全部基类的特性。

继承分单继承和多重继承。单继承指一个类只允许有一个父类，即类等级为 树形结构；多重继承指一个类允许有多个父类

多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。