二级公共基础(第一)

1、CopyRight2009 SWPUNCRE All Rights Reserved二级公共基础知识二级公共基础知识二级等级考试辅导考试方式分值分布学习方法 记忆和理解基本概念与基本原理记忆和理解基本概念与基本原理 多做练习多做练习 适当记忆一些名词适当记忆一些名词 与所学的程序设计知识结合起来，以增加对知与所学的程序设计知识结合起来，以增加对知识的理解能力识的理解能力第一章 算法与数据结构算法2、算法的复杂度 算法的算法的复杂度复杂度 衡量算法好坏的度量，分为衡量算法好坏的度量，分为时间复杂度时间复杂度和和空间复杂度空间复杂度算法的算法的时间复杂度时间复杂度？ 指执行算法所需要的计算工作量指

2、执行算法所需要的计算工作量，即算法执行过程，即算法执行过程中所需要的基本运算次数。中所需要的基本运算次数。算法的算法的空间复杂度空间复杂度？ 指执行算法所需要的内存空间指执行算法所需要的内存空间。一般来说，求解同一个问题有若干多种算法，一般来说，求解同一个问题有若干多种算法，则执行时间短的算法效率高，则执行时间短的算法效率高，占用存储空间少的算法较好。占用存储空间少的算法较好。 算法的时间开销和空间开销往往是相互制约的，算法的时间开销和空间开销往往是相互制约的， 但没有必然的联系！但没有必然的联系！ 对高时间效率和低存储占用的要求只能根据问题的对高时间效率和低存储占用的要求只能根据问题的 性质

3、折中处理性质折中处理算法的效率：与问题的规模和数据的存储结构有关算法的效率：与问题的规模和数据的存储结构有关第一章 算法与数据结构1.2 数据结构的基本概念 什么是数据结构？什么是数据结构？ 数据：数据：凡是能被计算机识别、存取和加工处理的符凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频信号、程序等号、字符、图形、图像、声音、视频信号、程序等一切信息。一切信息。 结构结构：数据之间的逻辑关系。数据之间的逻辑关系。 数据结构数据结构指相互有关联的数据元素的集合。指相互有关联的数据元素的集合。 数据、数据元素之间的关系。数据、数据元素之间的关系。 数据元素数据元素是数据的基

4、本单位。是数据的基本单位。1.3 数据的逻辑结构1.3 数据的逻辑结构与存储结构1、数据的、数据的逻辑结构逻辑结构： 数据的逻辑结构是指数据元素之间的逻辑关系数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。与数据的存储无关，是独立于计算机的。2、数据的逻辑结构可分成、数据的逻辑结构可分成2类类 线性结构线性结构 非线性结构非线性结构春春夏夏秋秋冬冬父亲父亲儿子儿子女儿女儿线线性逻辑结构逻辑结构又称为线称为线性表，栈栈和队队列都是特殊的线线性表。树树型结构结构和图图都属属于非线线性结构结构3、数据的、数据的存储结构存储结构？ 数据的存储结构又称为物理结构数据的存储结

5、构又称为物理结构，是指数据元素及，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。在计算机存储空间中的存放形式。4、数据的存储结构可分为哪、数据的存储结构可分为哪4类类？ 顺序结构、链式结构顺序结构、链式结构、索引结构、散列结构、索引结构、散列结构5、数据的存储结构与逻辑结构的关系、数据的存储结构与逻辑结构的关系 同一逻辑结构可以采用不同的存储结构同一逻辑结构可以采用不同的存储结构1.3 数据的逻辑结构与存储结构1.4 线性表及其存储结构1.4 线性表及其存储结构 1、线性表必须满足的、线性表必须满足的3个条件

6、：个条件： an a2 a1 2、线性表的长度：、线性表的长度：1.4 线性表及其存储结构3、线性表的存储结构：、线性表的存储结构：（一）顺序表线性表的顺序存储结构aa(0) a(1)a(n-1)特点：特点：1、所有元素所占的存储空间是连续的、所有元素所占的存储空间是连续的2、各元素在存储空间中是按逻辑顺序存放的、各元素在存储空间中是按逻辑顺序存放的 an a2 a1 （二）线性链表（二）线性链表线性表的链式存储结构线性表的链式存储结构特点：指针域指向前一个或后一个数据元素，体现各数据特点：指针域指向前一个或后一个数据元素，体现各数据元素的逻辑顺序元素的逻辑顺序1.4 线性表1、栈1、栈：、栈

7、： 一种一种特殊的线性表特殊的线性表，是限定在一端，是限定在一端进行插入和删除的线性表。进行插入和删除的线性表。2、栈的特点：、栈的特点： FILO：先进后出：先进后出 LIFO：后进先出：后进先出3、栈中元素个数、栈中元素个数 栈顶栈顶top和栈底和栈底bottom 栈中元素个数：栈中元素个数：top-bottom+14、栈的操作、栈的操作 入栈和出栈入栈和出栈a aaa入栈入栈出栈出栈栈顶栈顶n-1n21栈底栈底toptop进栈进栈 top+ 1 top OPR (top)出栈出栈 (top) OPR top - 1 top进栈进栈top栈顶栈顶栈底栈底出栈出栈栈顶栈顶栈顶栈顶OPR栈顶栈

8、顶栈底栈底bottomtopOPROPR1.4 线性表1、栈4、栈的操作、栈的操作入栈和出栈入栈和出栈bottom1.4 线性表2、队列1、队列：、队列：一种特殊的线性表一种特殊的线性表2、队列的特点：、队列的特点：FIFOFIFO(LILO)(LILO)：先进先出：先进先出 或或 后进后出后进后出3、队列中的元素个数、队列中的元素个数 队头队头frontfront和队尾和队尾rearrear 元素个数元素个数=rear-front=rear-front4.队列的运算：队列的运算：入队和出队入队和出队出队出队 a1 a2 an 入队入队队头队头队尾队尾J65J543210543210543J3

9、2J21J10543J3210队列：可能出现假溢出现象队列：可能出现假溢出现象解决：采用循环队列（依然为顺序存储）解决：采用循环队列（依然为顺序存储）1.4 线性表2、队列队列循环队列及其运算 什么是循环队列什么是循环队列 循环队列是队列的一种循环队列是队列的一种顺序存储结构顺序存储结构形式，在队列形式，在队列最后一个位置已被使用，而第一个位置空闲的情况最后一个位置已被使用，而第一个位置空闲的情况下，仍然能进行入队操作。下，仍然能进行入队操作。 循环队列循环队列3种基本运算种基本运算 入队、出队、读取数据元素入队、出队、读取数据元素 判断循环队列是否为空判断循环队列是否为空( (满满) )的条

10、件的条件 front=rear 队列可能为满也可能为空队列可能为满也可能为空J65J543210循环队列的元素实际个数循环队列的元素实际个数=(rear-front+maxsize)%maxsize1.5 线性链表线性表的链式存储结构1.5 线性链表线性表的链式存储结构数据域数据域 指针域指针域（1 1）用于存储数据元素值，称为）用于存储数据元素值，称为数据域数据域（2 2）用于存放指针，称为）用于存放指针，称为指针域，指针域，用于指向前一个或后用于指向前一个或后一个结点。一个结点。hh空指针空指针1.5 线性链表线性表的链式存储结构数据域数据域 指针域指针域 结点的储存不一定连续结点的储存不

11、一定连续 各结点之间的存储顺序与数据元素的逻辑关系可以不各结点之间的存储顺序与数据元素的逻辑关系可以不一致一致 链式存储适合于线性结构也适合于非线性结构链式存储适合于线性结构也适合于非线性结构hh空指针空指针1.5 线性链表线性表的链式存储结构abdch1.5 线性链表线性表的链式存储结构1.5 线性链表线性表的链式存储结构1.6 非线性结构非线性结构树与二叉树树与二叉树树与树与二叉树树的定义义、二叉树树的性质质、二叉树树的遍历历一、树一、树1. 树树：一种简单的非线性结构，所有元素之间具有明显的一种简单的非线性结构，所有元素之间具有明显的层次特性。层次特性。2. 树的相关概念：树的相关概念：

12、在树结构中，每一个结点只有一个前在树结构中，每一个结点只有一个前件（驱），称为件（驱），称为父结点父结点，没有前件（驱）的结点只有一个，没有前件（驱）的结点只有一个，称为树的称为树的根结点根结点，简称树的根。每一个结点可以有多个后，简称树的根。每一个结点可以有多个后件（继），称为该结点的件（继），称为该结点的子结点子结点。没有后件（继）的结点。没有后件（继）的结点称为称为叶子结点叶子结点。3. 树的深度：树的深度：一个结点所拥有的后件（继）的个数称为该一个结点所拥有的后件（继）的个数称为该结点的度，结点的度，所有结点中最大的度称为树的度所有结点中最大的度称为树的度。树的最大层树的最大层次称为树

13、的深度次称为树的深度。1.6 非线性结构树与二叉树1.6 非线性结构树与二叉树 二叉树的特点：二叉树的特点：（1 1）非空二叉树只有一个根结点；）非空二叉树只有一个根结点；（2 2）每一个结点最多有两棵子树，且分别称为该结点）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。的左子树与右子树。 abcdefg左支树左支树右支树右支树根结点根结点1.6 非线性结构2、二叉树123114589121367101415123114589126710满二叉树满二叉树完全二叉树完全二叉树思考：给出完全二叉树有思考：给出完全二叉树有n个结点，问有多少个叶子结点？个结点，问有多少个叶子结点？深度是

14、多少呢？深度是多少呢？满二叉树：每一层结点数达到最大满二叉树：每一层结点数达到最大完全叉树：除最后一层外，其余每一层结点数达到最大，完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点最后一层结点或满，或右边连续缺少若干结点二叉树性质423167891011121314155满二叉树满二叉树的第的第i层上有层上有2 i-1个结点，二叉树的个结点，二叉树的第第i层层 上至多有上至多有2 i-1（i 1）个结点；）个结点；二叉树性质423167891011121314155 性质性质5： 完全二叉树完全二叉树按层序（从根结点开始编号为按层序（从根结点开始编号为

15、1，每，每层从左到右）编号，某一结点编号为层从左到右）编号，某一结点编号为k，它若有左孩子结，它若有左孩子结点，左孩子结点编号为点，左孩子结点编号为2k，它若有右孩子结点，右孩子结，它若有右孩子结点，右孩子结点编号为点编号为2k+1。 由性质由性质5可推出：可推出：若若完全二叉树完全二叉树有有n个结点，那该二叉树个结点，那该二叉树有有n-n/2个叶子结点，其中个叶子结点，其中n/2表示对表示对n/2取不大于取不大于n/2的的最大整数。最大整数。423167891011121314155二叉树性质二叉树的遍历先序遍历先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。访问根

16、结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结按后序遍历左子树，按后序遍历右子树，访问根结ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历:二叉树的遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历:二叉树的遍历ADBC L R DL R DL R DADCL R D后序遍历序

17、列：后序遍历序列： D B C A后序遍历:B二叉树的遍历真题练习 2008.9对下列二叉树进行中序遍历的结果对下列二叉树进行中序遍历的结果是是 。A B C D E F X Y Z DBXEAYFZC真题练习 2011.3一棵二叉树的中序遍历结果为一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为，前序遍历结果为ABDECF，则后序遍历结果，则后序遍历结果为为 。 DEBFCA 1.7 数据的运算数据的运算1.1. 顺序表的插入、删除算法顺序表的插入、删除算法在最坏、最好情况下的运算次数在最坏、最好情况下的运算次数及平均运算次数及平均运算次数2.2. 顺序查找算法、折半查找算法顺序查找算

18、法、折半查找算法的应用场合、复杂度的应用场合、复杂度3.3. 各种各种排序算法排序算法的复杂度的复杂度插入插入e 1、顺序表的运算、顺序表的运算插入运算插入运算 1、插入运算的、插入运算的3步骤步骤 2、插入算法的效率、插入算法的效率看数组下标是否越界看数组下标是否越界 1、删除运算、删除运算 的步骤的步骤 2、删除算法的时间复杂度、删除算法的时间复杂度数据元素的数据元素的移动次数移动次数1、顺序表的运算、顺序表的运算删除运算删除运算 什么是查找？什么是查找？ 查找是在一个给定的数据结构中，根据给定的查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采条件查找满足条

19、件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据用不同的查找方法。查找的效率直接影响数据处理的效率。处理的效率。 查找的结果查找的结果 查找成功：找到满足条件的结点查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点查找失败：找不到满足条件的结点1.7 数据的运算2、查找运算2、查找运算顺序查找 顺序查找：顺序查找： 最好的查询次数：最好的查询次数： 最坏的查询次数：最坏的查询次数： 平均查询次数：平均查询次数： 顺序查找的特点顺序查找的特点 查找效率相对较低查找效率相对较低 适合适合无序线性表无序线性表和和有序的线性有序的线性链表进行查找链表进行查找( 08, 14

20、, 23, 37, 46, 55, 68, 79, 91 )i=0i=1i=2( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid查找查找23的过程如下图：的过程如下图：mid=(low+high)/2 二分法查找二分法查找：适合于适合于顺序存储的有序表顺序存储的有序表2、查找运算二分查找( 08, 14, 23, 37, 46, 55,

21、 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )midmidlowhighhighlow( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighhigh2、查找运算二分查找查找查找85的过程如下图：的过程如下图：2、查找运算二分查找 二分法查找二分法查找：适合于适合于顺序存储的有序表顺序存储的有序表 二分法查找的特点：二分法查找的特点： 查找效率比顺序查找高；查找效率比顺序查找高； 最坏最坏情况查询次数：情况查询次数：log2n次次 如果线性表为无序表，则不管是顺序存储结构还如果线性表为无序表，则不管是顺序存储结构还 是链式存储结构，都只能用顺序查