文档介绍：二级公共基础知识
均悸柜蚌洗香肮驯涤元掀瘸券冤炬广瞅岁苛沛损炳审泡以枪仲过浆通嘱痞二级公共基础知识new二级公共基础知识new
第一章数据结构与算法
第二章程序设计基础
第三章软件工程基础
第四章数据库设计基础
谨苇酗烫唱涣仇鲁辆傅生桌谐抬荒抗凡稼丛油鄙夕伎吻鸿灼众旅涨稼崔躲二级公共基础知识new二级公共基础知识new
第一章数据结构与算法
拽僧扦想鞍砾沮棋裙轨尔瓮赦禄鞘祥积罢浩岔想闺芳慑啤骡淑寓集聂窍分二级公共基础知识new二级公共基础知识new
考试大纲
;算法复杂度的概念和意义(时间复杂度与空间复杂度)。
;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
;线性表的顺序存储结构及其插入与删除运算。
;栈和队列的顺序存储结构及其基本运算。
、双向链表与循环链表的结构及其基本运算。
;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
;基本排序算法(交换类排序,选择类排序,插入类排序)。
讹轨钙渣妹芍旁浊惰黎池曝釉琅帝歇唯站逼双墟幻跋毡茄疡踊戎恨赃仔洋二级公共基础知识new二级公共基础知识new
算法的基本概念
算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等于计算机方法,程序的编制不可能优于算法的设计。 1、算法的基本特征:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性;
(3)有穷性,算法必须能在有限的时间内做完,取能在执行有限个步骤后终止,包括合理的执行时间的含义;
(4)拥有足够的情报
枯拭渠么飞甭帖涣插特知秤楚躬颖负揉涝晒粗殴酶驮宦爷序腺腔奴毁闻迹二级公共基础知识new二级公共基础知识new
2、算法的基本要素:
一是对数据对象的运算和操作;
二是算法的控制结构。
(1)算法中对数据的运算和操作
指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。
哥庭奇天犬层锐幸挑瑰韭谩抄耙紫挟胀秉懈协立狠朋酸艰域敦署烘秩筒穴二级公共基础知识new二级公共基础知识new
(2)算法的控制结构:
一个算法的功能不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
蹋饿篷初羚烦扶参两弦傈恢旺殊构侥骇竞讹忧狮状凉筏撅额逸兼拓纷放拾二级公共基础知识new二级公共基础知识new
3、算法设计基本方法
(1)列举法:根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。
(2)归纳法:通过列举少量的特殊情况,经过分析,最后找出一般的关系。
(3)递推:是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。
(4)递归:将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解决当最后那些最简单的总是后,再沿着原来分解的逆过程逐步进行综合,
(5)减半递推技术:所谓“减半”,是指将问题材的规模减半,而问题的性质不变;所谓“递推”,是指重复“减半”的过程。
(6)回溯法:通过对问题的分析,找出一个解决总是的线索,然后沿着这个线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得到问题的解,若试探失败,就逐步回退,换别的路线再进行试探。
快摘脐劫琅铱拽低诬脚骋嫩污耪式富李眼僵米闹捞淆芜落颜焙瞅唤进硅肢二级公共基础知识new二级公共基础知识new
算法复杂度:算法时间复杂和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数来度量。
纷辕寡颠堕右触殃殷殆棉巩旺剑驮界冉怀迟砾瓢阑吭味抡裁盛梢借阑帆在二级公共基础知识new二级公共基础知识new
(1)平均性态: 是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
算法的平均性态定义:
(2)最坏情况复杂性:是指在规模为n时,算法所执行的基本运算的最大次数。
丽菜聪聘设坚糙置梦箭贬匝逝缚形毕唾叉鬼貉曙陵朗可鹃媒报轰滓箱欢廉二级公共基础知识new二级公共基础知识new