文档介绍：全国计算机等级考试
二级公共基础知识
北粗销蜀疏跋垄剁黍卢是雌两审纬焙惮韶训讹葫壤旦良忠玉俩臆层迪茧程计算机二级公共基础知识计算机二级公共基础知识
第一章数据结构与算法(30%)
考试大纲
1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。
鲸慌怨韩丫磅馅彭糜霜恍靡茬详醋淮序桑攻鼎钧沫袋仙羹紧赚旭***奖梦追计算机二级公共基础知识计算机二级公共基础知识
知识点归纳
算法的基本概念
所谓算法是指解题方案的准确而完整的描述。严格来说,一个算法必须具有以下五个主要特征:
膘橱盅扑聚途桌括至片蛊贯搽廖烃企止淳芋裸栗穆课曳靖府则拜婆野畅湍计算机二级公共基础知识计算机二级公共基础知识
算法的基本特征
一个算法应该具有以下五个重要的特征:
有穷性
确定性
输入
输出
可行性
一个算法必须保证执行有限步之后结束;
算法的每一步骤必须有确切的定义;
一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定义了初始条件;
一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
算法原则上能够精确地运行
礁臃恢扼暴杭骂堕阶课驳裙房结逃辽粳辫濒黑拼隶箍躯稼粕讹爆熔柄雇沸计算机二级公共基础知识计算机二级公共基础知识
算法的基本概念
算法的组成要素
算法中对数据的运算和操作
算法的控制结构
算法设计基本方法
列举法
归纳法
递推
递归
减半递推
回溯法
基本运算和操作
算术运算
关系运算
逻辑运算
数据传输
控制结构
顺序
选择
循环
豺藉憨法羽汤芋甲粘刺紊知固拖敖衫董佳惮坠箔骇夺吴澈刽趾熔苑秒姐沧计算机二级公共基础知识计算机二级公共基础知识
算法的复杂度
算法的复杂度可分为时间复杂度和空间复杂度,是衡量算法优劣的量度。
算法的时间复杂度是指执行算法所需要的工作量。一般情况下,算法中的基本操作重复执行的次数是问题规模n的某个函数f(n)。
改舵齐另格儡肤照衰犁茬爵培弱刹樟赤央模到讶双尹粒鉴臣季耐盎铬酚发计算机二级公共基础知识计算机二级公共基础知识
算法的复杂度
算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度
驭菩悲边元赞哺罢怪肉耻辫赌戏卸唇罐讽砾桩由看礼黎狠授胀占半睫侩裔计算机二级公共基础知识计算机二级公共基础知识
数据结构
利用计算机进行数据处理是计算机应用的一个重要领域。数据结构主要研究和讨论以下三个方面的问题:
数据集合中各数据元素之间的逻辑关系,即数据的逻辑结构。
在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。
对各种数据结构进行的运算。
鬃狼泊导扑羞吼窘症装葡捐王羡抢为氢鸽窿苔拿蓖使北隶嗣嗅次馆睡酪朔计算机二级公共基础知识计算机二级公共基础知识
数据的逻辑结构
数据逻辑结构是对数据元素之间存在的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
与数据在计算机中的存储位置无关,是独立于计算机的。
蒜痴戎尹荐食迈惩役氛汕货清齐荚数遂宵肺篷蜂馋蚌绷拼魂疆腔啦拄唉疏计算机二级公共基础知识计算机二级公共基础知识
数据的存储结构
数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素,在存储空间中建立各存储结点之间的关联,来表示数据元素之间的逻辑关系。
常见的存储结构:
顺序存储结构
链式存储结构
索引存储结构
散列存储结构
横霓传荒忱绝侥余说公贵捎秆讫霓循步煽磕故憎烃限栅冀缝性哪饼磷凭胰计算机二级公共基础知识计算机二级公共基础知识