《二级公共基础知识数据结构与算法演示文稿》由会员分享，可在线阅读，更多相关《二级公共基础知识数据结构与算法演示文稿（108页珍藏版）》请在金锄头文库上搜索。
1、二级公共基础知识数据结构(sh j ji u)与算法演示文稿1页，共108页，星期一。二级公共基础知识数据结构(sh j ji u)与算法2页，共108页，星期一。考试( (k k o os sh h ) )形式1、公共( (g g n ng gg g n ng g) )基本知识部份只考选择题，没有操作题。2、公共基本知识占10分，共10道题，每题1分。3页，共108页，星期一。注意事项注意事项公共基础知识部份的内容是属于计算机专业本科生的专业课，知识点特别散，而且有一定的难度。所以考生在学习的过程(guchng)(guchng)中，一定要克服畏难情绪，跟上老师的节奏。老师让记的，要记住。没做
2、要求的，要学会放弃。放弃该放弃的，选择轻装上阵放弃该放弃的，选择轻装上阵4页，共108页，星期一。一、 数据结构(sh j ji u)与算法 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。线性表的定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义
3、；栈和队列的顺序存储结构及其基本运算。栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环线性单链表、双向链表与循环(xnhun)链表的结构及其基本运算。链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，插入顺序查找与二分法查找算法；基本排序算法（交换类排序，插入类排序，选择类排序）。类排序，选择类排序）。 5页，共108页，星期一。1.1 算法(sun f)1.1.1 算法算法(sun
4、 f)(algorithm)基本概念基本概念它是指令的有限序列，其中每一条指令表示一个或多个操作。它是指令的有限序列，其中每一条指令表示一个或多个操作。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法算法计算机解题的过程实际上是在实施某种算法，这种算法称为计算计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。机算法。6页，共108页，星期一。算法的基本特征算法的基本特征:(1)有穷性有穷性(2)确定性确定性(3)可行性可行性(4)拥有足够拥有足够(zgu)的情报的情报（有零个或多个
5、（有零个或多个输入，输入，有一个或多个有一个或多个输出输出）一个算法有零个或多个输入有零个或多个输入，以刻画运算(yn sun)对象的初始情况，所谓零个输入是指算法本身定出了初始条件；一个算法有一个或多个输出有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；7页，共108页，星期一。伪代码伪代码:S1:输入圆的半径输入圆的半径(bnjng)R;S2:求面积求面积 R2;S3:输出面积输出面积;例例1:已知圆的半径已知圆的半径(bnjng),求圆的面积求圆的面积.描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-S结构化流程结构化流程图、伪代码等。图、
6、伪代码等。开始开始输入输入R RS=3.14 * R*R输出输出S S结束结束传统流程图传统流程图8页，共108页，星期一。第9页n算法与计算机程序算法与计算机程序 算法算法是一组逻辑步骤是一组逻辑步骤(bzhu) 程序程序用计算机语言描述的算法用计算机语言描述的算法算法不等于算法不等于算法不等于算法不等于(dngy)(dngy)程序，也不等于程序，也不等于程序，也不等于程序，也不等于(dngy)(dngy)计算方法，程序的编制不可能优于算计算方法，程序的编制不可能优于算计算方法，程序的编制不可能优于算计算方法，程序的编制不可能优于算法的设计。法的设计。法的设计。法的设计。算法是程序设计的核心
7、算法是程序设计的核心9页，共108页，星期一。算法算法:S1:输入输入(shr)圆的半径圆的半径R;S2:求面积求面积R2;S3:输出面积输出面积;例题例题:已知圆的半径已知圆的半径(bnjng),求圆的面积求圆的面积.程序程序#include#definePI3.14159intmain()floatr,s;doprintf(Pleaseinputr:);scanf(%f,&r);if(r0)printf(Error！n);while(r=0);s=PI*r*r;printf(Area=%fn,s);return0;10页，共108页，星期一。1.1.2 算法的基本要素算法的基本要素 1、对
8、数据对象的运算和操作、对数据对象的运算和操作n算术运算算术运算n逻辑运算逻辑运算n关系运算关系运算n数据传输数据传输2、算法的控制结构、算法的控制结构n算法中各操作之间的执行顺序算法中各操作之间的执行顺序n一个算法一般可以用一个算法一般可以用顺序、选择、循环顺序、选择、循环3种基本种基本(jbn)结构组合而成。结构组合而成。11页，共108页，星期一。算术算术(sunsh)运算运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输顺序、选择、顺序、选择、循环循环3种基本种基本(jbn)结构结构#include#definePI3.14159intmain()floatR,S;doprintf(P
9、leaseinputR:);scanf(%f,&R);if(R0)printf(Error！n);while(R=0);s=PI*R*R;printf(Area=%fn,S);return0;12页，共108页，星期一。1.1.3 算法设计基本方法算法设计基本方法n列举法列举法n归纳法归纳法n递推递推n递归（以简洁的形式递归（以简洁的形式(xngsh)设计和描述算法）设计和描述算法）n减半递推技术减半递推技术n回溯法回溯法13页，共108页，星期一。1.2 算法算法(sun f)复杂度复杂度1.2.1 时间复杂度时间复杂度n是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。n通常
10、有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。算法的工作量用算法所执行的算法的工作量用算法所执行的基本运算基本运算次数来度量次数来度量.算法所执行的基本运算次数与算法所执行的基本运算次数与问题的规模问题的规模n有关有关(yugun)（即（即算法所执行的基本次数是问题规模的函数）算法所执行的基本次数是问题规模的函数）.执行算法所需要的计算工作量和执行算法所需要的计算工作量和f(n)同步增长，记为同步增长，记为:算法的工作量算法的工作量=f(n)时间复杂度时间复杂度=O(f(n)而对于一个固定的规模，算法所执行的基本次数还与特定的输入有关。14页，共108页，星期一。例子例子(lz
11、i)4：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;基本运算：基本运算：基本运算的执行基本运算的执行(zhxng)次次数：数：X增增1i=20i=31i=42i=nn-21+2+3+(n-2)=(n-1)(n-2)/2O（）例子例子2：+x;O（1）例子例子3：for(i=1;i=n;+i)+x;O（n）时间复杂度：时间复杂度：O(n*n-3n+2)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n15页，共108页，星期一。
12、1.2.2 算法的空间复杂度算法的空间复杂度n 一般是指执行这个算法所需要的内存空间一般是指执行这个算法所需要的内存空间n一个算法所占用的内存空间包括一个算法所占用的内存空间包括算法程序算法程序所占所占的空间、的空间、输入的初始输入的初始(ch sh)数据数据所占的存储空间所占的存储空间以及算法在执行过程中所需要的额外空间这以及算法在执行过程中所需要的额外空间这3部部分。分。16页，共108页，星期一。n 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要执行算法程序所需要(xyo)的时间的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过
13、程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数n算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。和拥有足够的情报。n算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间n在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题例题
14、(lt)讲解讲解有穷性有穷性17页，共108页，星期一。n算法算法(sun f)分析的目的是分析的目的是 A) 找出数据结构的合理性找出数据结构的合理性 B) 找出算法中输入和输出之间的关系找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D) 分析算法的效率以求改进分析算法的效率以求改进n算法的工作量大小和实现算法所需的存储单元多少分别称为算法的算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。时间时间(shjin)复杂度和空间复杂度和空间复杂度复杂度18页，共108页，星期一。1.2 数据结构(sh j ji u)n数据结构的定义(
15、dngy)n数据的逻辑结构和存储结构n数据结构的图形表示n线性结构与非线性结构19页，共108页，星期一。能输入能输入(shr(shr ) )到计算机中到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形图形(t(t x x ng)ng)、声音。、声音。1.2.2 基本概念和术语数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。20页，共108页，星期一。计算机管理图书计算机管理图
16、书(t(t sh)sh)问题问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间数据结构数据结构(shjjiu)是一门研究是一门研究数据数据组组织织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 21页，共108页，星期一。如何将如何将0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的计算机中能最快地达到你所需要的目的(m(m d d ) )？ 目的不同，最佳的存储方方法就不同目的不同，最佳的存储方方法就不同。 从大到小排列：从大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0输出偶数：输出偶数：0,2
