全国计算机等级考试 计算机二级考试 公共基础知识 第二讲 老师给的资料.pdf

满二叉树 是指这样的一种二叉树： 除最后一层外，每一层上的所有结 点都有两个子结点。 完全二叉树 是指这样的二叉树：除最后一层外， 每一层上的结点数均达到最大值；在 最后一层上只缺少右边的若干结点。 满二叉树与完全二叉树 a b e f c k m a b e f c k 考点1 二叉树的遍历（重点） ?1.先根遍历(前序遍历)特点是：先 访问根结点，接着访问左子树， 最后访问右子树。 abefck ?2.中跟遍历(中序遍历)特点是：先 访问左子树，再访问根结点，最后 访问右子树。 ebfakc ?3.后根遍历(后序遍历)特点是：先 访问左子树，再访问右子树，最后 访问根结点。 efbkca ?先根遍历先根遍历(根左右根左右) ?中根遍历中根遍历(左根右左根右) ?后根遍历后根遍历(左右根左右根) a b c d e f h g a b e f c k m l 先根遍历： abeflckm 中根遍历： eblfak mc 后根遍历： elfbmkc a dbxea yfzc d 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 st.length 顺序表的查找过程顺序表的查找过程： ： 假设给定值 e = 64, 假设给定值 e = 64, 问问: i = ?: i = ? i i 66 i i ?线性表为无序表时，对于长度为n的 无序表，最坏的情况下比较n次。 ?表采用链式存储结构时，对于长度为 n的无序表，最坏的情况下比较n次。 b ?二分法查找(对半查找)查找只适合用 于顺序存储的有序表，对于长度为n 的有序线性表，最坏的情况下比较 次。 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 st.elem st.length 例如: 例如: key = 64 key = 64 的查找过程如下的查找过程如下 low high mid low mid high mid low low 指示查找区间的下界指示查找区间的下界; ; high high 指示查找区间的上界指示查找区间的上界; ; mid mid = (low+high)/2= (low+high)/2。 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 st.elem st.length 例如: 例如: key = 66 key = 66 的查找过程如下的查找过程如下 low high mid low mid high mid low low 指示查找区间的下界指示查找区间的下界; ; high high 指示查找区间的上界指示查找区间的上界; ; mid mid = (low+high)/2= (low+high)/2。 high low mid highlow 1、什么是排序？ 什么是排序？ 排序是计算机内经常进行的一种操作，其目的是 排序是计算机内经常进行的一种操作，其目的是 将一组将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列的记录序列。 。 例如：例如：将下列关键字序列将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为调整为: 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 13 38 49 65 76 97 6 6 97 76 65 49 38 13 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 6 简单插入排序法 简单插入排序法：最坏的情况需要比较 的次数为 n (n 1 ) 2 d ?程序设计原则： ?清晰第一，效率第二。 ?注重易读性，易理解，可以添加 注释。 ?结构化程序设计方法的主要原则 为： ?自顶向下 ?逐步求精 ?模块化 ?限制使用goto语句。 a a ?模块独立性要高，有两原则 ?高内聚（模块内） ?低耦合（两模块之间） b a b ?对象 ?对象具有如下特征：标识惟一性、 分类性、多态性、封装性、模块独 立性。 a ?类 ?是具有共同属性、共同方法的对象的 集合。它描述了属于该对象类型的所 有对象的性质，而一个对象则是其对 应类的一个实例。 ?消息 ?消息是一个实例和另一个实例之 间传递的信息。 继承 ?继承是指类之间共享的属性和操作