文档介绍：二级公共基础知识
章节提要
第一章数据结构与算法
第二章程序设计基础
第三章软件工程基础
第四章数据库设计基础
第一章数据结构与算法
考试大纲
;算法复杂度的概念和意义(时间复杂度与空间复杂度)。
;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
;线性表的顺序存储结构及其插入与删除运算。
;栈和队列的顺序存储结构及其基本运算。
、双向链表与循环链表的结构及其基本运算。
;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
;基本排序算法(交换类排序,选择类排序,插入类排序)。
算法的基本概念
算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等于计算机方法,程序的编制不可能优于算法的设计。 1、算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。
特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,取能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。
2、算法的基本要素:
一是对数据对象的运算和操作;
二是算法的控制结构。
(1)算法中对数据的运算和操作
指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。
(2)算法的控制结构:
一个算法的功能不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
3、算法设计基本方法
(1)列举法:根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。
(2)归纳法:通过列举少量的特殊情况,经过分析,最后找出一般的关系。
(3)递推:是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。
(4)递归:将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解决当最后那些最简单的总是后,再沿着原来分解的逆过程逐步进行综合,
(5)减半递推技术:所谓“减半”,是指将问题材的规模减半,而问题的性质不变;所谓“递推”,是指重复“减半”的过程。
(6)回溯法:通过对问题的分析,找出一个解决总是的线索,然后沿着这个线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得到问题的解,若试探失败,就逐步回退,换别的路线再进行试探。
算法复杂度:算法时间复杂和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即
算法的工作量=f(n)