兰州大学蒙老师数据结构期末考试重点（概念）数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构研究方面：数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算，即数据的逻辑关系、存储关系和数据的运算关系。评价标准：①作为问题的参数的函数来计算存储需要量②作为问题的参数的函数来计算时间效率。逻辑存储关系：有两大类逻辑结构：线性结构（线性表、栈、队列、数组和串），非线性结构（树和图）。物理存储关系：数据在存储器中的关联方式。包括数据元素的表示和关系的表示。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。用于算法的实现。顺序结构、链接结构、索引结构、散列结构。算法：是解决某个问题的指令的有限集合，此外每个算法都必须符合有穷性、确定性、可行性以及输入输出等准则。算法描述方法：计算机程序设计语言、自然语言、PDL 语言（伪码语言，可运行于“抽象计算机”虚拟机）、流程图（N-S 图）。算法评价标准：时间复杂性：由于一般不需要精确时间消耗，只要知道时间消耗的增长率大体在什么范围内。利用某算法处理一个问题规模为 n 的输入锁需时间,它是一个关于 n 的函数。空间复杂性：关注额外存储占用。算法时间复杂性评价经过步骤：1 确定标准操作 2 计算操作次数 3 构造次数函数4 确定函数阶算法特征：有穷性、确定性、可行性、有输入线性表线性表:是 n0 个数据元素的有限序列,序列中除了第一个和最后一个元素以外,每个元素都是有且仅有一个直接前驱和直接后继。链表：通过指针联系起来的结点的整体（集合）。表头结点：增加一个附加结点，放置于链表的最前面，也称头结点。静态链表：以整型变量的值作为存储链接指针值（即地址）联系起来结点的整体。头指针：指向链表起始结点的指针。存储密度：数据本身所占存储量/整个结构所占存储量栈和队列栈：栈在计算机具体应用中，是一个特定的存储区，是一个下限为常数，上限可变化的向量（或者反之），也称为堆栈或堆阵。队列：是一个上限和下限只能增加而不能减少的向量（或反之）。假溢出：当元素被插入到数组中下标最大的位置之后，队列的空间用尽了，此时数组底端还有空闲空间，系统作为有用的存储区还没有满，但队列却发生了溢出。栈/队列和线性表的异同：栈和队列是受限的线性表。栈和队列只能做线性表运算的一部分。栈的插入和删除操作只能在一端进行，队列的插入和删除操作只能在特定位置进行...
