数据结构与算法◆算法得基本概念1、算法:就是对问题处理方案得正确而完整得描述,就是求解问题得方法,就是指令得有效序列。2、具有5个特性:(1)有穷性(在有穷步后完成)算法程序得运行时间就是有限得(2)确定性(每一步都有确定得含义)(3)可行性(4)输入(一个算法有零个或多个输入)(5)输出(一个算法有一个或多个输出)3、算法得复杂度包括:时间复杂度与空间复杂度。二者没有必然得联系。时间复杂度:执行算法所需要得计算工作量或基本运算次数。空间复杂度:算法所需要得空间得度量。◆数据结构得定义1、数据结构包括数据得逻辑结构、数据得存储结构、数据得操作数据得逻辑结构:数据得外部结构,指各数据元素之间得逻辑关系,反映人们对数据含义得解释。包括:线性结构(线性表、栈、队列)与非线性结构(树与图)数据得存储结构:数据得物理结构,指数据得逻辑结构在计算机中得表示。一个逻辑结构可以有多种存储结构。◆线性表:线性表中元素得个数n(n>=0)定义为线性表得长度。顺序存储就是线性表得一种最常用得存储方式。线性表得顺序存储结构与线性表得链式存储结构分别就是随机存取得存储结构与顺序存取得存储结构。1、栈:就是限定在表尾进行插入与删除操作得线性表。具有记忆功能只能顺序存储(错)允许插入与删除得一端叫栈顶。另一端叫栈底。后进先出得线性表2队列:就是限定在一端插入而在另一端删除,插入端叫队尾,删除端叫对头。先进先出得线性表3栈与队列得顺序存储结构循环队列属于线性表存储结构中顺序存储结构与链式存储结构得前者。◆树1、定义:树得结点、度(结点得度)、叶子(终端结点)、数得度、深度、有序树与无序数2、二叉树:结点至多有两棵子树,并且二叉树得子树有之分,次序不能颠倒。性质:★在二叉树得第i层上至多有2i1个结点★深度为k得二叉树至多有2k1个结点。★对任一个二叉树T,如果其叶子(终端结点数)为n,度为二得结点数为m,则n=m+1、★具有n个结点得完全二叉树得深度为k+1,其中k就是㏒2n得整数部分。2、二叉树得遍历▼先序遍历(根—左—右)▼中序遍历(左—根—右)▼后序遍历(左—右—根)◆查找算法(1)顺序查找顺序查找得平均查找长度为(n+1)／2,最坏得情况下比较得次数为n(2)二分查找最坏情况下次数为log2n限定于顺序存储得有序线性表◆排序算法(1)插入类排序▲直接插入排序▲折半插入排序▲希尔排序ｎ^１、５(2)交换类排序▲冒泡排序最坏情况下得比较次数n(n1)／2▲快速排序最坏情况下得比较次数n(n1)／2(3)选择类排序例题精选:1、设一棵完全二叉树共有699个结点,则在该二叉树中得叶子结点数为:3502、已知二叉树后序遍历序列就是dabec,中序遍历序列就是debac,它得前序遍历序列为:cedba3、要求内存量最大得就是:归并排序4、在数据结构中,与所使用得计算机无关得就是数据得就是:逻辑结构5、栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能就是:DCBEA6、已知数据表A中每个元素距其最终位置不远,为节省时间,应采取得算法就是:直接插入排序7、用链式表示线性表得优点就是:便于插入与删除操作。程序设计基础1、程序设计风格好得程序设计风格有利于提高程序得正确性、可读性、可维护性与可用性。要就是程序有良好得风格概括起来可以分为4部分:源程序文档化、数据说明、语句结构、输入输出方法。用户所定义得标示符必须以字母或下划线开头。大、小写字母代表不同标识。2、结构化程序设计(1)结构化程序设计得基本特征:▼程序有3中基本结构组成:顺序结构、选择结构、循环结构▼整个程序采用模块化结构。模块划分得原则:模块内具有高内聚度、模块间具有低耦合度。▼有限得使用转移语句,只限定在一个结构得内部跳转,不允许从一个结构跳到另一结构。▼程序设计时采用“至顶向下、逐步详细”得实施方法。(2)结构化程序设计得3种基本结构:顺序结构、选择结构、循环结构3种基本结构组成得算法只能完成符合结构化得任务(3)结构化程序设计得方法:逐步求精与模块化程序设计方法。结构化设计得总体思想就是采用模块化结构,自上而下,逐步求精。3、面向对象程序设计●基本概念对象:系统中运行得实体,就是有特殊属性(数据)与方法得实体类:由属性与方法构成。一组具有相同得数据结构与相同得行为特征得对象得集合称为类在面对对象得方法中,类得实例称为对象面向对象程序设计特征得就是:继承性、多态性、封装性在面向对象得方法中,实现信息隐蔽就是依靠对象得封装任何对象都必须有继承性(错)例题精选:1、在面对对象得方法中,一个对象请