C语言公共基础知识样本.doc

第一部分公共基础部分知识归纳数据结构和算法算法---是一组严谨地定义运算次序规则算法基础要素---一是对数据对象运算和操作,二是算法控制结构算法设计基础方法---列举法、归纳法、递推、递归、减半递推算法复杂度---包含时间复杂度和空间复杂度时间复杂度---实施算法所需计算工作量空间复杂度---实施算法所需内存空间数据结构---相互相关联数据元素集合。如春、夏、秋、冬;18、11、35、23、16。。。;父亲、儿子、女儿等全部是数据元素。前件---数据元素之间关系,如父亲是儿子和女儿前件后件---如儿子是父亲后件结构---指数据元素之间前后件关系数据逻辑结构—是指反应数据元素之间逻辑关系,而和它们在计算机中存放位置无关数据存放结构(物理结构)---数据逻辑结构在计算机存放空间中存放形式,数据元素在计算机存放空间位置关系可能和逻辑关系不一样。依据数据结构中各数据元素之间前后件关系复杂程度,可将数据结构分两类---线性结构和非线性结构线性结构(线性表)---满足下列两个条件(1)有且只有一个根结点(2)每一个结点最多有一个前件和后件。则称该数据结构为线性结构,不然为非线性结构。线性表是最简单、最常见一个数据结构,其数据元素之间相对位置是线性,其存放方法为次序存放,如数组栈---是限定在一端进行插入和删除线性表,一端封闭,另一端开口,其操作标准是“优异后出”,栈运算有入栈、退栈、读栈顶元素队列---是指在一端进行插入(称为队尾)而在另一端进行删除(称为队头)线性表,其操作规则是“优异先出”,其运算有入队和退队。树---是一个简单非线性结构,而且是层次结构,是倒立大树,有根结点、父结点、子结点、叶子结点。根结点在第一层,一个结点所拥有后件个数称为该结点度,全部结点中最大度称为树度,树最大层次称为树深度。二叉树---(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树(左子树和右子树),其存放结构为链式。二叉树性质---(1)K层上最多有2(K-1)个结点(2)深度为m二叉树最多有2m-1个结点(3)度为0结点(叶子结点)比度为2结点多一个(4)含有n个结点二叉树,其深度最少为[Log2n]+1,其中[Log2n]表示对Log2n取整满二叉树---除最终一层外,其它层结点全部有两个子结点完全二叉树---除最终一层外,每一层上结点数均达成最大值,在最终一层上只缺乏右边若干结点,叶子结点只可能在层次最大两层上出现。满二叉树是完全二叉树,而完全二叉树不是满二叉树。完全二叉树有两个性质:(1)含有n个结点完全二叉树深度为[Log2n]+1(2)二叉树遍历---不反复地访问各个结点。分为前序遍历(DLR-根左右)、中序遍历(LDR-左根右)和后序遍历(LRD-左右根)查找技术---次序查找——对于长度为n有序线性表,查找时需要比较n次二分法查找——对于长度为n有序线性表,查找时需要比较log2n次排序技术---假设线性表长度为n,则冒泡排序和简单插入排序比较次数(时间复杂度)为n(n-1)/2;希尔排序比较次数为O();简单选择排序比较次数为n(n-1)/2;堆排序比较次数为O(nlog2n).习题1算法时间复杂度是指(),算法空间复杂度是指();线性表、栈、队列、线性链表是(线性结构),树是(非线性结构);数据存放结构是指();队列是(优异先出),栈是(优异后出);下列二叉树遍历结果:前序遍历(ABDECF)、中序遍历(DBEAFC)、后续遍历(DEBFCA)在深度为5满二叉树中,叶子结点个数为(16);设树T度为4,其中度为1,2,3,4结点个数分别为4,2,1,1。则T中叶子结点个数为(8);对于长度为n有序线性表,次序查找次数为(n),二分法查找次数为(log2n);一棵完全二叉树共有700个结点,则在该二叉树中有(350)个叶子结点;一棵二叉树中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后续遍历结果为(DEBFCA);冒泡排序时间复杂度为(n(n-1)/2);在一个容量为15循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有(3)元素;程序设计基础结构化程序设计三种结构---是次序、选择和循环对象---表示客观世界任何实体类---是含有共同属性和方法对象集合实例---任何一个对象全部是其对应类实例消息---一个实例和另一个实例之间传输信息继承---是指直接取得已经有性质和特征,而无须反复定义它们。比如子类继承父类结构化程序设计关键强调---程序易读性良好程序设计风格是---程序应简单、清楚、可读性好在面向对象方法中,一个对象请求另一个对象为其服务方法是经过发送(消息)来实现信息隐蔽概念和(模块独立性)概念直接相关(任何对象全部含有继承性)这句话是错误注释分为(序言性注释)和(功效性注释