公共信息基础

《公共信息基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法算法是指解题方案的准确而完整的描述算法的时间复杂度：是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数來度量算法的空间复杂度：一个算法的空间复杂度，是指执行这个算法所需要的内存空间时间复杂度和空间复杂度并不相关算法具有5个特性:①有穷性：-•个算法必须（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有限时间内完成，即运行时间是有限的;②确定性:算法中每一条指令必须有确切的含义，读者理解吋不会产牛:歧义;③可行性:—•个算法是可行的,即算法中描述的操作都是可以通过己经实现的基木运算执行有限次来实现;④输入:一个算法有零个或多个输入，这些输入収自

2、于某个特定的对•象的集合;⑤输出:一个算法有一个或多个输出。一个算法一般都可以用顺序、选择、循坏三种基本控制结构组合而成数据结构数据的逻辑结构，是指反映数据元索Z间逻辑关系的数据结构数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式（也称数据的物理结构）。数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。数据的存储结构有顺序、链接、索引等。数据的逻辑结构有线性及非线性结构数据元索采用不同的存储结构，其数据处理的效率是不同的。线性结构与非线性结构都可以是空的数据结构，对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则

3、属于非线性结构循坏队列屈于顺序存储结构带链的队列属于线性结构双向链表是线性结构线性表线性表的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。链式存储结构存储空间多于顺序存储有序线性表既可以采用顺序存储结构，也可以采用链式存储结构栈，队列（必考）08.4栈是限定在一端进行插入为删除的线性表，允许插入少删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈按照〃先进后出〃或"后进先出〃组织数据，栈具有记忆作用。对于栈的插入与删除操作中，不需要改变栈底指针；栈可以链式和顺序存储；栈屮元索随着栈顶指针的变化而

4、变化支持了程序调用的结构是栈若top=a,bottom=b,那么此栈有b・a+l个元素队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。允许插入的一端称为队尾，允许删除的一端称为排头（或队头）。队列乂称为〃先进先出或〃后进后出的线性表。往队列的队尾插入-•个元索称为入队运算，从队列的排头删除一个元索称为退队运算当循环队列非空（s“）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为〃上溢〃。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为〃下溢循环序列队头指针可以大于也可以小于队尾指针循环队列中元素的个数及动态变化情况是山

5、队头指针和队尾指针共同决定的。个数=队尾指针（rear）•队头指针（front）+容量（maxSize）队列空的条件为s=0;队列满的条件为s=l且front=rear线性链表线性列表存储空间不一定是连续，且各元素的存储顺序是任意的，优点是便于插入和删除操作二叉树（必考）二叉树的基本性质：（重要）a.在二叉树的第k层上，最多有2kl（k>=l）个结点（满二叉树）b.深度为m的二叉树最多有2卩1个结点。深度为m的二叉树是指二叉树共冇m层。c.已知叶子结点的数量，减去1则是度为2的结点的数量d.貝-有n个结点的二叉树，其深度至少为［Iog2n］+1,其中［Iog2n］表

6、示取Iog2n的整数部分满二叉树与完全二叉树是两种特殊形态的二叉树。a.满二叉树：在满二叉树屮，每一层上的结点数都达到最人值，即在满二叉树的第k层上有2“个结点，几深度为m的满二义树共有2叫1个结点。b.完全二叉树：除最后一层外，每一层上的结点数均达到最人值；在最后一层上只缺少右边的若干结点。完全二叉树如果有N个结点，当N为奇数的时候，叶子结点数为(N+l)/2，此时二叉树只有度为0的叶子结点及度为2的结点，没有度为1的结点；当N为偶数的时候，叶了结点的数量为N/2注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。二义树结点个数公式：2*度数为二的结点数+

7、1*度数为一的结点数+1二叉树的遍历：在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、屮序遍历、后序遍历。叶子结点的先后顺序是不变的，和遍历无关。.前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。根左右b.中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。左根右c.后序遍历：首先遍历左了树，然后遍历右了树，最后访问根结点。左右跟前序遍历屮一定以根结点开头，后序遍历一定以根结点结尾，而屮序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树査找技术对于长度为n的有序线性表，在最坏的悄况下，二分查找只需要比较比较［