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

链表是从头指针开始读数据和下个数据的指针如 左图 1、Head为165 2、读取165内的数据为bat，下一个指针为130 读取130 cat， 135 135 eat … 一直到最后一个指针为NULL(空)时停止
考点7树与二叉树及其基本性质
性质 1： 在二叉树的第 i 层上至多有 2 i - 1 个结点 (i ≥1)。 性质 2：深度为 k 的二叉树至多有 2k－1 个结点（k ≥1)。 性质 3：对任何一棵二叉树 T，如果其叶子数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。 性质 4：具有 n 个结点的完全二叉树的深度为 log2n + 1。 性质 5： 如果对一棵有 n 个结点的完全二叉树 (深度为 log2n+1) 的结点按层序编号 (从第 1 层到第 log2n+1 层，每层从左到右)，则对任一结点 i (1≤i≤n)，有：
A A B A B B
具有两个结点的二叉树有两种状态
具有两个结点的树只有一种状态
二叉树的 5 种基本形态
(a) 空二叉树
(b) 根和空的 左右子树
(c) (d) 根和左子树 根和右子树
(e) 根和左右子树
注：虽然二叉树与树概念不同， 但有关树的基本术语对二叉树都适用。
完全二叉树 (Complete binary tree) 深度为 k 的具有 n 个结点的二叉树，当且仅当其 每一个结点都与深度为 k 的满二叉树中编号为 1~ n 的 结点一一对应时，称之为完全二叉树。 特点：叶子只可能分布在层次最大的两层上。
前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来 看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没 有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH 中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树 的根A，连起来是BDA。再访问根的右子树，C的左子树的左子树是F，F的根E， E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无 右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC


线性结构
对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序） 集合。 它有四个基本特征： 1．集合中必存在唯一的一个"第一个元素"；


2．集合中必存在唯一的一个"最后的元素"；
3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。

空间复杂度 占用存储空间的大小
考点3数据结构的定义

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面： （1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据 的存储结构；
（3）对各种数据结构进行的运算。
考点4线性结构与非线性结构
Leabharlann Baidu

2、定义 队列（Queue）是只允许在一端进行插 入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。 （2）允许插入的一端称为队尾（Rear）。 （3）当队列中没有元素时称为空队列。 （4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。 新来的成员总是加入队尾（即不允许"加塞"）， 每次离开的成员总是队列头上的（不允许中途 离队），即当前"最老的"成员离队。 【例】在队列中依次加入元素a1，a2，…， an之后，a1是队头元素，an是队尾元素。退出 队列的次序只能是a1，a2，…，an。
二叉树
二叉树在树结构的应用中起着非常重要的作用，因为对 二叉树的许多操作算法简单，而任何树均可与二叉树相互转 换，这样就解决了树的存储结构及其运算中存在的复杂性。
二叉树的定义 定义 二叉树是 n (n≥0) 个结点的有限集，它或者是 空集 (n = 0)，或者由一个根结点及两棵互不相交的 分别称作这个根的左子树和右子树的二叉树组成。
0 0 1 5 2 37 3 19 4 21 5 13 6 56 7 64 64
9
64
8 92 9 88 10 11 80 75
顺序查找
优点：算法简单，适应面广。 缺点：平均查找长度大。
在下列两种情况下也只能采用顺序查找： （1）如果线性表为无序表，则不管是顺序存储结构还是 链式存储结构，只能用顺序查找。 （2）即使是有序线性表，如果采用链式存储结构，也只 能用顺序查找。

（1）算法中对数据的运算和操作 在一般的计算机系统中，基本的运算和操作有以下4类： 算术运算、逻辑运算、关系运算和数据传输。

（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有
传统流程图、 N-S结构化流程图、 算法描述语言 （C语言，汇编，文字）等。
N-S流程图
数据结构
OFFICE公共基础（一） 韩磊
宁师VIP速成班
考点1算法的基本概念

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：
一个算法由两种基本要素组成： 一是对数据对象的运算和操作； 二是算法的控制结构。
特点
1、每个结点最多有俩孩子 (二叉树中不存在度大于 2 的结点) 。 2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。
注
二叉树不是树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有一 棵子树也要进行区分，说明它是左子树，还是右子树。树当 结点只有一个孩子时，就无须区分它是左还是右。（也就是 二叉树每个结点位置或者说次序都是固定的，可以是空，但 是不可以说它没有位置，而树的结点位置是相对于别的结点 来说的，没有别的结点时，它就无所谓左右了），因此二者 是不同的。这是二叉树与树的最主要的差别。
后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其 根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直 接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA
考 点 顺 序 查 找
顺序查找：从表的一端开始，逐个进行记录的关
键字和给定值的比较。 查找过程：
找63
7 64 8 75
High < low
性能分析： i 查找成功：
1 5
2 13
3 19
4 21
5 37
6 56
7 64
8 75
9 80
10 11 88 92
Ci 3
4
2
3
4
1
3
4
2
3
4
比较次数 = 路径上的结点数
比较次数 = 结点 4 的层数 比较次数 树的深度 1
-1 1-2
6 3 4
表中一个记录
考 点 十 折 半 查 找
有序表表示静态查找表 查找过程：
1 5
low 1 5 low 2 13 3 19 4 21 5 37
折半查找
6 56
mid 6 56 mid
找21
2 13 3 19 4 21 5 37 7 64 8 75 9 80 10 11 88 92
high 9 80 10 11 88 92 high
对任一结点，如果其右子树的最大层次为 l，则其 左子树的最大层次必为 l 或 l + 1。 1
2 3 2
1
3
满二叉树
一 定 是
6
4
5
6
4
5
是 定 一 不
完全二叉树
完全二叉树
非完全二叉树
考点8二叉树的遍历
二叉树的遍历有三种方式，如下： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树， 最后遍历右子树。简记根-左-右。 （2）中序遍历（LDR），首先遍历左子树，然后访问根结点， 最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树， 最后访问根结点。简记左-右-根。
判定树
7 5
4-5 5-6 6-7
9
10 8
7-8 8-9 9-10
log2n +1
查找不成功：
比较次数 = 路径上的内部结点数
≤
＝
2
3-4 2-3
11
11-
10-11
比较次数 ≤ log2n +1
考 点 交 换 类 排 序 法
冒泡排序法和快速排序法都属于交换类排序法。 （1）冒泡排序法 首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素 大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后 最大者到了线性表的最后。然后，从后到前扫描剩下的线性表，逐次比较相邻两个 元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元 素中的小者往前移动，最后最小者到了线性表的最前面。对剩下的线性表重复上述 过程，直到剩下的线性表变空为止，此时已经排好序。在最坏的情况下，冒泡排序 需要比较次数为n（n－1）/2。 （2）快速排序法 它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素）， 通过一趟排序，将待 排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序 码，右子序列的排序码则 大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。 疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？ 冒泡排序法的平均执行时间是O（n2），而快速排序法的平均执行时间是O （nlog2n）。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构
关于广义表，是一种非线性的数据结构。哈希表 常见的非线性结构有：树(二叉树等)，图(网等)
考点5栈和队列及其基本运算

1、栈的定义 栈（Stack）是限制仅在表的一端进行插入 和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶 （Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。 (3)栈为后进先出（Last In First Out）的线 性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次 删除（退栈）的总是当前栈中"最新"的元素，即 最后插入（进栈）的元素，而最先插入的是被放 在栈的底部，要到最后才能删除。 栈的基本运算有：入栈，出栈（删除栈顶元素）， 初始化、置空、判断栈是否为空或满、提取栈顶 元素等，对栈的操作都是在栈顶进行的。
(1) 如果 i = 1，则结点 i 是二叉树的根，无双亲；
如果 i >1，则其双亲是结点 i / 2。 (2) 如果 2i > n，则结点 i 为叶子结点，无左孩子； 否则，其左孩子是结点 2i。 (3) 如果 2i + 1 > n，则结点 i 无右孩子；否则，其 右孩子是结点 2i + 1。
11
传统流程图

一个算法一般都可以用
顺序、选择、循环3种基本控制结构组合而成。
考点2算法复杂度

时间复杂度 一个算法所需要时间
一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样 做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上 界，这就保证了算法的运行时间不会比任何更长。
考点6线性链表的基本概念

1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以 是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结 点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的 地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可 用来表示各种非线性的数据结构。