2016计算机二级office公共基础知识(一)数据结构.ppt

《2016计算机二级office公共基础知识(一)数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构Office公共基础（一）韩磊宁师VIP速成班考点1算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。2．算法的基本要素：一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描

2、述语言（C语言，汇编，文字）等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。传统流程图N-S流程图考点2算法复杂度时间复杂度一个算法所需要时间一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。空间复杂度占用存储空间的大小考点3数据结构的定义数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各

3、数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。考点4线性结构与非线性结构线性结构对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合。它有四个基本特征：1．集合中必存在唯一的一个"第一个元素"；2．集合中必存在唯一的一个"最后的元素"；3．除最后元素之外，其它数据元素均有唯一的"后继"；4．除第一元素之外，其它数据元素均有唯一的"前驱"。常用的线性结构有：线性表，栈，队列，双队列，数组，串。关于广义表，是一种非线性的数据结构。哈希表常见的非线性结构有：树(二叉树等)，图(网等)非线

4、性结构考点5栈和队列及其基本运算1、栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。   　栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取

5、栈顶元素等，对栈的操作都是在栈顶进行的。2、定义队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表       　　（1）允许删除的一端称为队头（Front）。　　（2）允许插入的一端称为队尾（Rear）。　　（3）当队列中没有元素时称为空队列。　　（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。   　队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队

6、。【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。考点6线性链表的基本概念1、链接存储方法链接方式存储的线性表简称为链表（LinkedList）。   　链表的具体存储表示为：　　①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）　　②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(lin

7、k)）注意：　　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。链表是从头指针开始读数据和下个数据的指针如左图1、Head为1652、读取165内的数据为bat，下一个指针为130读取130cat，135135eat…一直到最后一个指针为NULL(空)时停止考点7树与二叉树及其基本性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k－1个结点（k≥1)。性质3：对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。性质

8、4：具有n个结点的完全二叉树的深度为log2n+1。性质5：如果对一棵有n个结点的完全二叉树(深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)