二级c精选基础.doc

算法的基本特征（1）可行性 确定性 （3）有穷性数据结构研究三个方面1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构算法复杂度时间复杂度和空间复杂度。 数据的存储结构有顺序、链接、索引等（2）二叉树的基本性质 完全二叉树还具有如下两个特性： 性质5 具有n个结点的完全二叉树深度为 。 性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论： ①若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的编号为INT(k/2)。 ②若2k≤n，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。 ③若2k+1≤n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。 在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n次。 顺序查找一个具有n个元素的线性表，其平均复杂度为O（n）。 线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O（log2n）。 5、二叉树的遍历（1）前序遍历（DLR）（2）中序遍历（LDR）（3）后序遍历（LRD）。 *：循环队列中元素的个数=rear-front。 *：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。 *：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。插入、删除运算不方便。 *：线性表是一种存储结构，它的存储方式：顺序和链式。 *：常见的非线性结构有树、二叉树和图等。 *：常见的线性结构有线性表、栈、队列和线性链表等。 *：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 *：数据的逻辑结构二分法查找只适用于顺序存储的表，。对于 程序设计的风格主要强调：“清晰第一，效率第二”。主要应注重和考虑下述一些因素 2）程序的注释。分为序言性注释和功能性注释，确保每一个模块的独立性； 结构化程序设计方法的原则自顶向下逐步求精结构化程序的基本结构：循环结构 面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息操作描述了对象执行的功能，操作也称为方法或服务。*：一个对象由对象名、属性和操作三部分组成。 对象的基本特点：消息的组成包括（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。 计算机软件是包括程序、数据及相关文档的完整集合。 软件工程包括3个要素：方法、工具和过程。 软件生命周期软件定义、软件开发运行维护原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。结构化方法的核心和基础是结构化程序设计理论。需求分析方法有1）结构化需求分析方法；2）面向对象的分析方法。结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具建立系统的逻辑模型。结构化分析的常用工具1）数据流图；2）数据字典3）判定树；4）判定表。加工（转换）：输入数据经加工变换产生输出。 数据流：沿箭头方向传送数据的通道，一般在旁边标注数据流名。 存储文件（数据源）：表示处理过程中存放各种数据的文件。 源，潭：表示系统和环境的接口，属系统之外的实体。 画数据流图的基本步骤：自外向内，自顶向下，逐层细化，完善求精。 *：需求分析主要解决“做什么”的问题，而软件设计主要解决“怎么做”的问题。 从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 结构设计：定义软件系统各主要部件之间的关系。 数据设计：将分析时创建的模型转化为数据结构的定义。 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。 过程设计：把系统结构部件转换成软件的过程性描述。 从工程角度来看，软件设计分两步完成，即概要设计和详细设计。 概要设计：又称结构设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式。 详细设计：确定每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。 软件设计的基本原理包括：抽象、模块化、信息隐蔽和模块独立性。 抽象。抽象