文档介绍：精选学****资料
- - - - - - - - -
学****好资料 欢迎下载
公共基础学问总结
第一章 数据结构与算法
算法
算法：是指解题方案的精确而完整的描述；
算法不等于程序,也不等运算机方法储备方式即可用于表示线性结构,也可用于表示非线性结构；
线性链表, HEAD 称为头指针, HEAD=NULL （或 0）称为空表,假如是两指针：左指 针（ Llink ）指向前件结点,右指针（ Rlink ）指向后件结点；
线性链表的基本运算：查找、插入、删除；
1．6 树与二叉树
树是一种简洁的非线性结构,全部元素之间具有明显的层次特性；
在树结构中,每一个结点只有一个前件,
称为父结点,没有前件的结点只有一个,
称为
树的根结点,简称树的根；每一个结点可以有多个后件,结点称为叶子结点；
称为该结点的子结点；没有后件的
在树结构中, 一个结点所拥有的后件的个数称为该结点的度, 全部结点中最大的度称为
树的度；树的最大层次称为树的深度；
二叉树的特点： （1）非空二叉树只有一个根结点；分别称为该结点的左子树与右子树；
二叉树的基本性质：
（2）每一个结点最多有两棵子树,且
名师归纳总结
（1）在二叉树的第
k 层上,最多有
2k-1〔k ≥1〕个结点；
第 2 页,共 9 页
（2）深度为 m 的二叉树最多有
2m-1 个结点；
（3）度为 0 的结点（即叶子结点）总是比度为
2 的结点多一个；
精选学****资料
- - - - - - - - -
学****好资料 欢迎下载
（4）具有 n 个结点的二叉树,其深度至少为 部分；
[log2n]+1, 其中 [log2n] 表示取 log2n 的整数
（5）具有 n 个结点的完全二叉树的深度为 [log2n]+1 ；
（6）设完全二叉树共有
n 个结点；假如从根结点开头,按层序（每一层从左到右）用
自然数 1,2,⋯ .n 给结点进行编号（ k=1,2⋯ .n）,有以下结论：
①如 k=1,就该结点为根结点,它没有父结点；如 k>1,就该结点的父结点编号为
INT〔k/2〕 ；
②如 2k≤n,就编号为
k 的结点的左子结点编号为
2k；否就该结点无左子结点
（也无右
子结点）；
③如 2k+1≤n,就编号为 k 的结点的右子结点编号为 2k+1；否就该结点无右子结点；
满二叉树是指除最终一层外,每一层上的全部结点有两个子结点,就 k 层上有 2k-1 个
结点深度为 m 的满二叉树有 2m-1 个结点；
完全二叉树是指除最终一层外, 每一层上的结点数均达到最大值, 在最终一层上只缺少
右边的如干结点；
储；
二叉树储备结构采纳链式储备结构, 对于满二叉树与完全二叉树可以按层序进行次序存
二叉树的遍历：
（1）前序遍历（ DLR ）,第一拜访根结点,然后遍历左子树,最终遍历右子树；（2）中序遍历（ LDR ）,第一遍历左子树,然后拜访根结点,最终遍历右子树；（3）后序遍历（ LRD ）第一遍历左子树,然后拜访遍历右子树,最终拜访根结点；
1．7 查找技术
次序查找的使用情形：
（1）线性表为无序表；
（2）表采纳链式储备结构；
二分法查找只适用于次序储备的有序表,
对于长度为
n 的有序线性表, 最坏情形只需比
较 log2n 次；
1．8 排序技术
排序是指将一个无序序列整理成按值非递减次序排列的有序序列；
交换类排序法： （1）冒泡排序法,需要比较的次数为
n〔n-1〕/2 ； （2）快速排序法；
插入类排序法：（1）简洁插入排序法, 最坏情形需要 n〔n-1〕/2 次比较；（2）希尔排序法,
最坏情形需要 O〔〕次比较；
挑选类排序法： （1）简洁挑选排序法 ,
最坏情形需要 n〔n-1〕/2 次比较；（2）堆排序法,最坏情形需要 O〔nlog2n〕 次比较；
其次章 程序设计基础
2．1 程序设计设计方法和风格
如何形成良好的程序设计风格
1、源程序文档化；
2、数据说明的方法；
3、语句的结构；
4、输入和输出；
注释分序言性注释和功能性注释,语句结构清楚第一、效率其次；
2．2 结构化程序设计
结构化程序设计方法的四条原就是：goto 语句；
结构化程序的基本结构和特点：
1. 自顶向下； 2. 逐步求精； ；
名师归纳总结
- - - - - - -
第 3 页,共 9 页
精选学****资料
- - - - - - - - -