当前位置：文档之家 › 2016计算机二级office公共基础知识(一)数据结构

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

  • 格式：pptx
  • 大小：1023.62 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

2016年9月计算机二级公共基础知识资料

2016年9月计算机二级公共基础知识资料

2016年9月二级公共基础知识总结——计算机二级新大纲第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

计算机二级Office选择题(知识点：公共基础)

计算机二级Office选择题(知识点：公共基础)

二级公共基础知识一、数据结构与算法1.下列叙述中正确的是A)所谓算法就是计算方法B)程序可以作为算法的一种描述方法C)算法设计只需考虑得到计算结果D)算法设计可以忽略算法的运算时间B【解析】算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。

算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。

算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，。

算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。

2.下列关于算法的描述中错误的是A)算法强调动态的执行过程，不同于静态的计算公式B)算法必须能在有限个步骤之后终止C)算法设计必须考虑算法的复杂度D)算法的优劣取决于运行算法程序的环境D【解析】算法设计不仅要考虑计算结果的正确性，还要考虑算法的时间复杂度和空间复杂度。

3.下列叙述中正确的是A)算法的复杂度包括时间复杂度与空间复杂度B)算法的复杂度是指算法控制结构的复杂程度C)算法的复杂度是指算法程序中指令的数量D)算法的复杂度是指算法所处理的数据量A【解析】算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

算法的复杂度包括时间复杂度与空间复杂度。

算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。

4.下列叙述中正确的是A)算法的时间复杂度与计算机的运行速度有关B)算法的时间复杂度与运行算法时特定的输入有关C)算法的时间复杂度与算法程序中的语句条数成正比D)算法的时间复杂度与算法程序编制者的水平有关B【解析】为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

全国计算机二级公共基础知识知识点

全国计算机二级公共基础知识知识点

公共基础知识第一章数据结构与算法1.1 算法1.1.1 算法的基本概念1、算法的基本特征可行性、确定性、有穷性、拥有足够的情报所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

2、算法的基本要素（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作：算术运算、逻辑运算、关系运算、数据传输（2）算法的控制结构描述算法的工具：传统流程图、N-S结构化流程图、算法描述语言等一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成3、算法设计基本方法列举法、归纳法、递推（本质上也属于归纳法，递推关系式往往是归纳的结果）、递归（基础也是归纳，分为直接递归和间接递归两种）、减半递推技术、回溯法（“试”）1.1.2 算法复杂度1、算法的时间复杂度（执行算法所需要的计算工作量）算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数算法的工作量=f(n)，n是问题的规模两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为n3对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关——可以用两种方法来分析算法的工作量：平均性态、最坏情况复杂性2、算法的空间复杂度（执行这个算法所需要的内存空间）如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的1.2 数据结构的基本概念数据结构主要有三个方面的问题：●数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构●在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构●对各种数据结构进行的运算提高数据处理的效率，主要包括两个方面：●提高数据处理的速度●尽量节省在数据处理过程中所占用的计算机存储空间1.2.1 什么是数据结构无序表，只能用顺序查找对分查找只适用于有序表（在词典中查单词的方法类似于对分查找）数据结构是指相互有关联的数据元素的集合（向量、矩阵、图书馆中的图书卡片目录……）在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（直接前驱与直接后继关系）来描述，前后件关系所表示的实际意义随具体对象的不同而不同1、数据的逻辑结构一个数据结构应包含以下两方面的信息：●表示数据元素的信息●表示各数据元素之间的前后件关系（数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关）一个数据结构可以表示成：B=（D，R）D为数据元素的集合，R为D中各数据元素之间的前后件关系（一般用二元组来表示）a与b是D中的两个数据，则二元组（a,b）表示a是b的前件，b是a的后件2、数据的存储结构各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构1.2.2 数据结构的图形表示在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（叶子结点）数据结构中除了根结点与终端结点外的其他结点一般称为内部结点在对数据结构的处理过程中，不仅数据结构中的结点（即数据元素）个数在动态地变化，而且，各数据元素之间的关系也有可能在动态地变化1.2.3 线性结构与非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构如果一个非空的数据结构满足两个条件：●有且只有一个根结点●每一个结点最多有一个前件，也最多有一个后件则称该数据结构为线性结构。

全国计算机二级公共基础知识

全国计算机二级公共基础知识

全国计算机全国计算机二级公共基础知识二级公共基础知识二级公共基础知识((重点部分重点部分))第一章 数据结构基础1.1算法1.1.1 算法的基本概念算法是解题方案的准确而完整的描述算法是解题方案的准确而完整的描述，，它不等于程序它不等于程序，，也不等计算方法也不等计算方法。

算法的基本特征可行性(effectiveness) 确定性(definiteness) 有穷性(finiteness) 拥有足够的情报 算法的时间复杂度执行算法所需要的计算工作量 与下列因素有关：书写算法的程序设计语言 ,编译产生的机器语言，代码质量 机器执行指令的速度 ,问题的规模 问题的规模函数 算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n 的某个函数f(n)，记作记作：：T(n)=O(f(n)) 记号“O ”读作“大O ”。

表示随问题规模n 的增加，算法执行时间的增长率和f(n)相应增加。

常见算法复杂度常见算法复杂度：：O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶 O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶算法的空间复杂度算法执行过程中所需的最大存储空间 存储量包括以下三部分算法程序所占的空间 ,输入的初始数据所占的存储空间 ,算法执行过程中所要的额外空间1.2 数据结构的基本概念数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式 常用的存储结构：顺序, 链式, 索引一种数据结构可根据需要采用不同的存储结构。

采用不同的存储结构，其数据处理的效率是不同 线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。

常见的线性结构有：线性表、栈与队列、线性链表非线性结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。

计算机二级公共基础知识

计算机二级公共基础知识
n0，度为2的结点数为n2 ，则：n0 =n2+1 性质4 具有n个结点的二叉树，其深度至少为
[log2n] +1
整理ppt
28
满二叉树和完全二叉树
满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就 是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1 个结点，且深度为m的满二叉树有2m-1个结点。
一个算法有0个或多个输入，以刻画运算对象的 初始情况，所谓0个输入是指算法本身定义了初 始条件； 一个算法有一个或多个输出，以反映对输入数据 加工后的结果。没有输出的算法是毫无意义的； 算法原则上能够精确地运行
整理ppt
4
算法的基本概念
算法的组成要素
算法中对数据的运算和操作
算法的控制结构
算法设计基本方法
2. 在对数据进行处理时，各数据元素在计算机 中的存储关系，即数据的存储结构。
3. 对各种数据结构进行的运算。
整理ppt
8
数据的逻辑结构
数据逻辑结构是对数据 元素之间存在的逻辑关 系的描述，它可以用一 个数据元素的集合和定 义在此集合上的若干关 系表示。
与数据在计算机中的存 储位置无关，是独立于 计算机的。
F
6
C
90E
2 0 A0 8
D0
5
G
11 0 B 0
13 0 H 0
10P0 整理ppt
i L(i) V(i) R(i)
1
0
P
0
2
0
A
0
3
全国计算机等级考试
二级公共基础知识
整理ppt
1
第一章 数据结构与算法(30%)
考试大纲
1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复 杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表 示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序 和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类 排序，插入类排序）。

计算机二级考试公共基础知识(数据结构)

计算机二级考试公共基础知识(数据结构)
B．非线性结构
树形结构 图形结构
2、数据的存储结构
A 顺序存储
B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
数据结构基础知识
线性结构
A , B , C , ··· ·· ，X ,Y , Z ··
线性表——结点间是以线性关系联结
线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一 个后件。
于自己的序号，元素之间的相对位置是线性的。 表中的每一个数据元素，除了第一个外，有且只有一个前
件，除了最后一个外，有且只有一个后件。线性表中数据
元素的个数称为线性表的长度。 线性表可以为空表。
*：线性表是一种存储结构，它的存储方式：顺序和 链式。
数据结构基础知识
2、线性表的顺序存储结构具有两个基本特点：
的位置之间，所有的元素均为队列中的元素。
• 循环队列中元素的个数=rear-front。
数据结构基础知识
1.5 线性链表
1、线性表顺序存储的缺点：
1）插入或删除的运算效率很低。在顺序存储的线 性表中，插入或删除数据元素时需要移动大量的数据 元素； 2）线性表的顺序存储结构下，线性表的存储空间 不便于扩充； 3）线性表的顺序存储结构不便于对存储空间的动 态分配。
3、数据的运算：检索、排序、插入、删除、修改等。
数据结构基础知识
图形结构——节点间的连结是任意的
1 4
2 1
3
2
3
数据结构基础知识
线性表 栈 A．线性结构 1．数据的逻辑结构 数 据 结 构 的 三 个 方 面 队 线性链表
B．非线性结构
树形结构 图形结构
2、数据的存储结构
(亦称物理结构)

计算机二级公共基础知识完整.doc

第一章数据构造与算法经过对部分考生的检查以及对最近几年真题的总结剖析，笔试部分常常考察的是算法复杂度、数据构造的看法、栈、二叉树的遍历、二分法查找，读者应付此部分进行要点学习。

详尽要点学习知识点：1．算法的看法、算法时间复杂度及空间复杂度的看法2．数据构造的定义、数据逻辑构造及物理构造的定义3．栈的定义及其运算、线性链表的储存方式4．树与二叉树的看法、二叉树的基天性质、完好二叉树的看法、二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点 1算法的基本看法考试链接：考点1在笔试考试中查核的几率为30% ，主假如以填空题的形式出现，分值为2分，此考点为识记内容，读者还应当认识算法中对数据的基本运算。

计算机解题的过程其实是在实行某种算法，这类算法称为计算机算法。

1．算法的基本特色：可行性、确定性、有穷性、拥有足够的情报。

2．算法的基本因素：（1）算法中对数据的运算和操作一个算法由两种基本因素构成：一是对数据对象的运算和操作；二是算法的控制构造。

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

（2）算法的控制构造：算法中各操作之间的履行次序称为算法的控制构造。

描绘算法的工具往常有传统流程图、N-S构造化流程图、算法描绘语言等。

一个算法一般都能够用次序、选择、循环 3种基本控制构造组合而成。

考点 2算法复杂度考试链接：考点2在笔试考试中，是一个常常考察的内容，在笔试考试中出现的几率为70% ，主假如以选择的形式出现，分值为2分，此考点为要点识记内容，读者还应当识记算法时间复杂度及空间复杂度的看法。

1.算法的时间复杂度算法的时间复杂度是指履行算法所需要的计算工作量。

同一个算法用不一样的语言实现，或许用不一样的编译程序进行编译，或许在不一样的计算机上运转，效率均不一样。

这表示使用绝对的时间单位权衡算法的效率是不合适的。

撇开这些与计算机硬件、软件有关的因素，能够认为一个特定算法"运转工作量 "的大小，只依靠于问题的规模（往常用整数 n表示），它是问题规模的函数。

计算机office二级公共基础知识点


3.线性表的顺序存储结构和线性表的链式存储结构分别是______。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 4.用链表表示线性表的优点是______。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取
考试大纲
考试内容
二、程序设计基础
1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法，对象，方法，属性及继承与多 态性。
考试大纲
考试内容
三、软件工程基础
1、软件工程的基本概念；软件生命周期概念；软件工具与软 件开发环境。 2、结构化分析方法；数据流图，数据字典，软件需求规格说 明书。 3、结构化设计方法； 总体设计，详细设计。 4、软件测试的方法；白盒测试，黑盒测试，测试用例设计； 软件测试的实施；单元测试，集成测试，系统测试。 5、程序的调试，静态调试与动态调试。
5
9
7
（3）在一般情况下，如果在第i个元素之前进 行，则第i个元素之后的所有元素都必须移动。
在平均情况下，需要移动表中一半的元素。
因此算法的平均时间复杂度为O(n).
4、线性表的删除运算
2
14
5
9
7
4、线性表的删除运算 2
5
9
7
4、线性表的删除运算 2 5
9
7
4、线性表的删除运算 2 5 9
6、算法的空间复杂度
指执行算法所需要的存储空间
包括：算法程序所占据的存储空间 待处理数据所占据的存储空间 算法程序执行中所需要的额外存储空间 如果额外存储空间大小不随问题规模变化，则称之为算法原地工作。 降低算法的空间复杂度，应从数据的存储空间和额外空间入手。

计算机国二office公共基础知识

考点：1. 算法(****)2. 数据结构(***)3. 线性表及其顺序存储结构(**)4. 栈和队列(*****)5. 线性链表(**)6. 树与二叉树(*****)7. 查找技术(****)8. 排序技术(***)1、概念算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作 2、数据的逻辑结构● 线性结构(例：一维数组、链表、栈、队列、串、线性表) ● 非线性结构(例：多维数组、广义表、树、图) 3、数据的存储结构(线性表)● 顺序存储方法：线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑顺序依次存放的● 链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的 ● 计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系● 一种数据的逻辑结构根据需要可以表示成多种存储结构。

数组是数据的逻辑结构，可以用多种存储结构来表示● 线性链表：就是指线性表的链式存储结构，简称链表 4、算法的基本特征● 可行性：针对实际问题而设计的算法，执行后能够得到满意的结果 ● 确定性：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性● 有穷性：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止，算法程序的运行时间是有限的● 拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效5、算法的复杂度● 时间复杂度：该算法执行的时间耗费，是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数● 空间复杂度：该算法执行时所耗费的存储空间 6、顺序表和链表的比较：基于空间的考虑：(1)顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。

(2)顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的栈实际也是线性表，只不过是一种特殊的线性表。

计算机二级公共基础知识重点

计算机二级公共(gōnggòng)基础知识重点计算机二级公共(gōnggòng)基础知识一、数据结构(shù jù jiéɡòu)与算法1.1.1 数据结构(shù jù jiéɡòu)的基本概念数据(shùjù)结构指相互有关联的数据元素的集合。

数据逻辑结构反映数据元素之间的逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，分为顺序存储、链式存储、索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为如下两种:(1)线性结构：有且只有一个根节点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构。

(2)非线性结构：不满足线性结构的数据结构。

1.1.2 算法1. 算法的基本概念（1）概念：算法是指解题方案的准确而完善的描述。

（2）基本特征：可行性、确定性、有穷性、拥有足够的情报。

（3）基本要素：对数据对象的运算和操作、算法和控制结构。

（4）设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术、回溯法。

2. 算法的复杂度（1）算法的时间复杂度：执行算法所需要的计算工作量。

（2）算法的空间复杂度：执行算法所需的内存空间。

1.1.3 线性表及其顺序存储结构1. 线性表的基本概念线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。

2. 线性表的顺序存储结构顺序存储结构的特点(tèdiǎn)如下：（1）元素所占的存储空间必须(bìxū)连接。

（2）元素(yuán sù)在存储空间的位置是按逻辑顺序依次存放的。

3. 线性表的插入(chā rù)运算若在第i 个元素之前插入一个新元素，可先把原来第i 个结点至第n 个结点依次往后移一个元素位置(wèi zhi)。

然后把新结点放在第i 个位置上，最后修正线性表的结点个数。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

11
数据结构
OFFICE公共基础（一） 韩磊
宁师VIP速成班
考点1算法的基本概念

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：
一个算法由两种基本要素组成： 一是对数据对象的运算和操作； 二是算法的控制结构。
找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
表中一个记录

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

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面： （1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据 的存储结构；
（3）对各种数据结构进行的运算。
考点4线性结构与非线性结构
对任一结点，如果其右子树的最大层次为 l，则其 左子树的最大层次必为 l 或 l + 1。 1
2 3 2
1
3
满二叉树
一 定 是
6
4
5
6
4
5
是 定 一 不
完全二叉树
完全二叉树
非完全二叉树
考点8二叉树的遍历
二叉树的遍历有三种方式，如下： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树， 最后遍历右子树。简记根-左-右。 （2）中序遍历（LDR），首先遍历左子树，然后访问根结点， 最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树， 最后访问根结点。简记左-右-根。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构
关于广义表，是一种非线性的数据结构。哈希表 常见的非线性结构有：树(二叉树等)，图(网等)
考点5栈和队列及其基本运算

1、栈的定义 栈（Stack）是限制仅在表的一端进行插入 和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶 （Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。 (3)栈为后进先出（Last In First Out）的线 性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次 删除（退栈）的总是当前栈中"最新"的元素，即 最后插入（进栈）的元素，而最先插入的是被放 在栈的底部，要到最后才能删除。 栈的基本运算有：入栈，出栈（删除栈顶元素）， 初始化、置空、判断栈是否为空或满、提取栈顶 元素等，对栈的操作都是在栈顶进行的。
A A B A B B
具有两个结点的二叉树有两种状态
具有两个结点的树只有一种状态
二叉树的 5 种基本形态
(a) 空二叉树
(b) 根和空的 左右子树
(c) (d) 根和左子树 根和右子树
(e) 根和左右子树
注：虽然二叉树与树概念不同， 但有关树的基本术语对二叉树都适用。
完全二叉树 (Complete binary tree) 深度为 k 的具有 n 个结点的二叉树，当且仅当其 每一个结点都与深度为 k 的满二叉树中编号为 1~ n 的 结点一一对应时，称之为完全二叉树。 特点：叶子只可能分布在层次最大的两层上。
判定树
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）。
链表是从头指针开始读数据和下个数据的指针如 左图 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)，有：
特点
1、每个结点最多有俩孩子 (二叉树中不存在度大于 2 的结点) 。 2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。
注
二叉树不是树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有一 棵子树也要进行区分，说明它是左子树，还是右子树。树当 结点只有一个孩子时，就无须区分它是左还是右。（也就是 二叉树每个结点位置或者说次序都是固定的，可以是空，但 是不可以说它没有位置，而树的结点位置是相对于别的结点 来说的，没有别的结点时，它就无所谓左右了），因此二者 是不同的。这是二叉树与树的最主要的差别。
后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其 根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直 接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA
考 点 顺 序 查 找
顺序查找：从表的一端开始，逐个进行记录的关
键字和给定值的比较。 查找过程：
(1) 如果 i = 1，则结点 i 是二叉树的根，无双亲；
如果 i >1，则其双亲是结点 i / 2。 (2) 如果 2i > n，则结点 i 为叶子结点，无左孩子； 否则，其左孩子是结点 2i。 (3) 如果 2i + 1 > n，则结点 i 无右孩子；否则，其 右孩子是结点 2i + 1。
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）即使是有序线性表，如果采用链式存储结构，也只 能用顺序查找。
前序：根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
考 点 十 折 半 查 找
有序表表示静态查找表 查找过程：
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
考点6线性链表的基本概念

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