《公共基础知识第一章》由会员分享，可在线阅读，更多相关《公共基础知识第一章（2页珍藏版）》请在金锄头文库上搜索。
1、算法具有6个特性。 有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步 都可在有限时间内完成，即运行时间是有限的。 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生歧义。 可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算 执行有限次来实现。 输入：一个算法有零个或多个输入，这些输入取自某个特定的对象的集合。 输出：一个算法有一个或多个输出。 数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间关系的，是独 立于计算机的； 数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示的，它们并非一一 对应。
2、算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 算法的时间复杂度是指算法需要消耗的时间资源，是独立于机器的 算法的空间复杂度是指：算法执行过程中所需的存储空间。 数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关 系 存储结构分为顺序存储结构与链式存储结构，其中顺序存储结构是将逻辑上相邻的数据元素存 储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存 储线性结构的数据， 数组的存储方式连续是指其在计算机中的存储方式，它可以用来处理非线性结构 程序执行的效率与很多因素有关，如数据的存储结构、程序所处理的数据量、程序所采
3、用的算 法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别，其中链式存 储结构的效率要高一些。 根据数据结构中各数据元素之间前后关系的复杂程度，一般将数据结构分为两大类型：线性结 构与非线性结构。线性结构表示数据元素之间为一对一的关系，例：循环队列、带链队列、带 链栈。非线性结构表示数据元素之间为一对多或者多对一的关系。例：二叉树 顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由 存储单元的邻接关系来体现。其优点是占用最少的存储空间， 链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后 继元素之间的关系，除了存储
4、元素本身的信息外，还需存储一个指示其直接后继的存储位置信 息。 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。栈顶元 素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素， 从而也是最后才能被删除的元素。因而栈是按照“先进后出“或“后进先出“的原则组织数据 的。 栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数 时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到 主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点， 队列是一种操作受限的线性表。它只允许在线性表的一端进行插入操
5、作，另一端进行删除操作。 其中，允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。队列具有先进先出的特点，它是按“先进先出“的原则组织数据的， 对于任何一棵二叉树T，如果其终端节点(叶子)数为n1，度为2的节点数为n2，则n1n21。 所以该二叉树的叶子节点数等于n1。 叶子结点个数=度为2的结点个数+1，二叉树是一棵单支树，树中结点个数即为树的深度。 二叉树前序遍历的含义是：首先访问根节点，然后按前序遍历根节点的左子树，最后按前序遍 历根节点的右子树，前序遍历二叉树的过程是一个递归的过程。 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是。 对长度为n
6、的有序链表进行查找，最坏情况是从最小值开始查找最大值（或从最大值开始查找 最小值），这个过程需要比较的次数为n， 数据结构包括数据的逻辑结构和存储(物理)结构，其中逻辑结构分为线性结构和非线性结构， 存储结构包括顺序结构和链式结构。在循环队列中，队尾的指针指向对首元素，是队列的链式 存储结构。 在二叉树中，度为0的结点数是度为2的结点数加1，故二叉树中结点数的总和为度为0的结点数、 度为1的结点数及度为2的结点数三者相加 根据二叉树的性质，一棵深度为k的满二叉树有2k1个节点，若终端节点的个数为n0，度为2 的节点数为n2， 在满二叉树中，叶子结点数目的计算公式为2(n1)，其中n为树的深度。 二叉树中序遍历的含义是：首先按中序遍历根结点的左子树，然后访问根结点，最后按中序遍 历根结点的右子树，中序遍历二叉树的过程是一个递归的过程。 后序遍历二叉树的定义为：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子 树，访问根结点。 能使用二分法查找的线性表必须满足两个条件：1)用顺序存储结构；2)线性表是有序的。
