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