第一章 数据结构与算法
所谓算法是解题方案的准确而完整的描述。是一组 严谨地定义运算顺序的规则，此顺序将在有限的次数 下终止。
算法的基本特征：可行性、确定性、有穷性、拥有 足够的情报。
：一是对数据对象线 性表仍然为顺序存储，则在插入或删除过程中需要移
学 校 总 部 ： 矿 院 北 门 东 行 200 米动大量的数据元素。②、当为一个线性表分配顺序存 储空间后，如果出现线性表的存储空间已满时，就会 发生“上溢”错误。③、在实际应用中，往往是同时 有多个线性表共享计算机的存储空间。
在链式存储方式中，要求每个结点由两部分组成： 一部分用于存放数据元素的值，称为数据域；另一部 分用于存放指针，称为指针域。其中指针用于指向该 结点的前一个结点或后一个结点（即前件或后件）。
线性表的链式存储结构称为线性链表。
一般来说，在线性表的链式存储结构中，各数据结 点的存储序号是不连续的，并且各结点在存储空间中 的位置关系与逻辑关系也不一致。
二叉树具有以下两个特点: 非空二叉树只有一个根结点; 每一个结点最多有两棵子树 ,且分别称为该结点的左 子树与右子树.
二叉树具有以下几个性质:
（1） 在二叉树的第K层上,最多有2k-i（K$ 1）个结点. 深度为m的二叉树最多有2m-1个结点。
（2） 在任意一棵二叉树中，度为0的结点（即叶子结 点）总是比度为 2 的结点多一个。
（3） 具有n个结点的二叉树，其深度至少为[logn]+1,
其中logn的整数部分。 2
（4） 具有n个结点的完全二叉树的深度为[logn]+1。 38•设完全二叉树共有n个结点。如果从根结点开始， 按层序（每一层从左到右）用自然数1，2,…，N给 结点进行编号，则对于编号为K （K=1, 2,…，n）的 结点有以下结论：
若K=1,则该结点为根结点，它没有你结点；若K>1, 则该结点的你结点编号为INT （K/2）。
若2KWN,则编号为K的结点的左子结点编号为2K； 否则该结点无左子结点（显然也没有右子结点）。
若2K+1Wn，则编号为K的结点的右子结点编号为 2K+1；否则该结点无右子结点。
二叉树通常采用链式存储结构。
二叉树的遍历是指不重复地访问二叉树中的所有 结点。
二叉树的遍历可以分为三种：前序遍历、中序遍历、 后序遍历。
所谓前序遍历是指在访问根结点、遍历左子树与遍 历右子树这三者中，首先访问根结点，然后遍历左子 树，最后遍历右子树；并且，在遍历左、右子树时， 仍然先访问根结点，然后遍历左子树，最后遍历右子 树。
所谓中序遍历是指在访问根结点、遍历左子树与遍 历右子树这三者中，首先遍历左子树，然后访问根结 点，最后遍历右子树；并且，在遍历左、右子树时， 仍然先遍历左子树，然后访问根结点，最后遍历右子 树。
所谓后序遍历是指在访问根结点、遍历左子树与遍 历右子树这三者中，首先遍历左子树，然后遍历右子 树，最后访问根结点，并且，在遍历左、右子树时， 仍然先遍历左子树，然后遍历右子树，最后访问根结 点。
所谓查找是指在一个给定的数据结构中查找某个 指定的元素。
二分法查找只适用于顺序存储的有序表。
对于长度为 n 的有序线性表，在最坏情况下，二分 查找只需要比较log2n次，而顺序查找需要比较n次
二级公基知识点 来自淘豆网m.daumloan.com转载请标明出处.
