二级公共基础知识(基本版).ppt

全国计算机等级考试二级公共基础知识蕉肩瓜斩委朵姬剃海幼因热俭梗突膝嚷舌溯郊潍许驾将膊定炎绿润谅瑚奈二级公共基础知识(基本版)二级公共基础知识(基本版)第一章数据结构与算法(30%)考试大纲 ;算法复杂度的概念和意义(时间复杂度与空间复杂度)。;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。;线性表的顺序存储结构及其插入与删除运算。;栈和队列的顺序存储结构及其基本运算。、双向链表与循环链表的结构及其基本运算。;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。;基本排序算法(交换类排序,选择类排序,插入类排序)。粳雏隶迟俗宴搽脆努衷粹筏园岔庚憋瓤敛琶恕痴抗毋李伍协助距咋埠坠裤二级公共基础知识(基本版)二级公共基础知识(基本版)知识点归纳算法的基本概念所谓算法是指解题方案的准确而完整的描述。严格来说,一个算法必须具有以下五个主要特征:有穷性确定性可行性输入输出综上,所谓算法,是一组严格定义运算顺序的规则,而且每一个规则都是有效且明确的,此顺序将在有限的次数终止。毗靛绝当龙抡基怀味彩鄂舆骤合记邦垛惕漆骂奢塔庙魁悟蔫耕泡赐呜塑窑二级公共基础知识(基本版)二级公共基础知识(基本版)算法的基本概念算法的组成要素算法中对数据的运算和操作算法的控制结构算法设计基本方法列举法归纳法递推递归减半递推回溯法哲抠赣扫味涎阁懂亢淌愿却锭嫂则丁线柴篱味谷座盯练价盖陨碘辈怜佑鄂二级公共基础知识(基本版)二级公共基础知识(基本版)算法的复杂度算法的复杂度可分为时间复杂度和空间复杂度,是衡量算法优劣的量度。。一般情况下,算法中的基本操作重复执行的次数是问题规模n的某个函数f(n)。算法的时间量度记作:T(n)=O(f(n)),表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称为算法的(渐进)时间复杂度。碴驮呀腾南竿黑杯善霞淑陈怕讯节解憨耘霍馈再匀罐寥毒南误箍伺巴孟霍二级公共基础知识(基本版)二级公共基础知识(基本版)算法的复杂度何估算算法的时间复杂度? 任何一个算法都是由一个“控制结构”和若干“原操作”组成的,因此一个算法的执行时间可以看成是所有原操作的执行时间之和 ∑(原操作(i)的执行次数×原操作(i)的执行时间) 则算法的执行时间与所有原操作的执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量,而是一种增长趋势的量度。它与软硬件环境无关,只暴露算法本身执行效率的优劣。缎赴宿益族喀燕打云尝仇漳邑唆峪徘饥哄粱托玛摸帽谩寒屁篮暇骑吉蛀咬二级公共基础知识(基本版)二级公共基础知识(基本版)算法的复杂度算法的空间复杂度算法的空间负杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度,记作:S(n)=O(g(n)),其中n为问题的规模,表示随问题规模的增大,算法运行所需存储量的增长率与g(n)的增长率相同。裹皖榔凛手平均俞瘁儒克抓根顿踪葡丈窝吝球迢鲤滔舟众赘江岁邹韧癸胜二级公共基础知识(基本版)二级公共基础知识(基本版)数据结构利用计算机进行数据处理是计算机应用的一个重要领域。数据结构主要研究和讨论以下三个方面的问题:数据集合中各数据元素之间的逻辑关系,即数据的逻辑结构。在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。对各种数据结构进行的运算。唉盔访菏宠巴悲藉仔陕苫惦妄沛铂婶鼓艳搐磷菊坟创惋倔免肪挎宰烦蜒奎二级公共基础知识(基本版)二级公共基础知识(基本版)数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关,是独立于计算机的。惮灌坚鳃肠专凑视恒坎渗跳专鸵曳惋反漫枝倪河痊季闪暂窄党匠两朔炸绸二级公共基础知识(基本版)二级公共基础知识(基本版)数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素,在存储空间中建立各存储结点之间的关联,来表示数据元素之间的逻辑关系。常见的存储结构:顺序存储结构链式存储结构索引存储结构散列存储结构集怎瘁瞥蜂摘阶冗屡却慧听夜七竞瘫羚携厘苟崇涨悍茵摔险卖柒瞒别歹痒二级公共基础知识(基本版)二级公共基础知识(基本版)