二级ACESS重点知识点.doc

第一 数据结构与算法　　算法指解题方案的准确而完整的描述。 　　基本特征可行性确定性有穷性拥有足够的情报 　　基本要素数据对象的运算和操作算法的控制结构。 　　算法控制结构：顺序结构、选择结构循环结构。常用工具：流程图、N-S结构图算法描述语言等。 　　算法设计的基本方法列举法归纳法递推递归减半递推技术回溯法 算法复杂度时间复杂度计算工作量空间复杂度需要的内存空间。 　　线性结构：有且只有一个根结点每一个结点最多只有一个前件，也最多只有一个后件线性结构又称线性表。 线性表中结点的个数称为结点的长度n。当n=0时，称为空表。 2．顺序存储结构特点：线性表中所有的元素所占的存储空间是连续的各数据元素在存储空间中是按逻辑顺序依次存放的 　　栈一种特殊的线性表，它是限定在一端进行插入和删除的线性表。原则：先进后出或后进先出。　　队列是允许在一端进行插入，而在另一端进行删除的线性表。规则：先进先出或后进后出 循环队列是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。顺序存储结构简单运算方便运算效率较低如果出现线性表的存储空间已满，还需要插入元素时，会发生“上溢”错误有可能使有的队列空间不够或过多造成浪费。对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。 　　链式存储 　　假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。 　　每一个结点由两部分组成：一部分用于存放数据元素，为数据域；另一部分用于存放指针，称为指针域。　　存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致链式存储结构既可以用于线性结构，也可用于非线性结构。 二叉树的性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。 　　2：深度为m的二叉树最多有2m-1个结点。 　　3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。 　　4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。 5：具有n个结点的完全二叉树的深度为[log2n]+1二叉树的遍历二叉树的存储常采用链式存储结构　　前序遍历 根结点左子树右子树。 　　中序遍历左子树根结点右子树。 后序遍历左子树右子树根结点。　　 查找技术　　1．顺序查找最坏情况的查找次数是n次2．二分查找最坏情况的查找次数是log2n次。 排序技术 　1．交换类排序法冒泡排序法快速排序法 2．插入类排序法简单插入排序希尔排序法　　3．选择类排序法简单选择排序法堆排序法第二程序设计基础　　程序设计方法：主要经过了面向过程的结构化程序设计和面向对象的程序设计方法。 　　程序设计风格指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。要形成良好的程序设计的风格，应考虑：源程序文档化数据说明方法语句的结构输入和输出 结构化程序设计原则：自顶而下、逐步求精，模块化，限制使用goto语句。 基本结构顺序结构选择结构重复结构特点使程序结构良好、易读、易理解、易维护。 面向对象的程序设计与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好基本概念对象基本特点：标识的唯一性分类性多态性封装性 模块独立性好类和实例消息继承多态性 　　 第三 软件工程基础软件与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。 　　软件危机泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题软件工程：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。要素：方法、工具过程软件规格说明软件开发软件确认软件演进过程　目标：在给定成本、进度的情况下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。 　　理论和技术性研究内容：软件开发技术软件工程管理。 原则抽象信息隐蔽模块化局部化确定性一致性完备性可验证性。软件生命周期主要阶段：软件定义软件开发软件维护 主要活动阶段：可行性研究与计划制定需要分析软件设计软件实现软件测试运行和维护。需求分析指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。任务是发现需求、求精、建模和定义需求的过程。 工作需求获取需求分析编写需求规格说明书需求评审方法结构化分析方法面向对象的分析方法 　　结构化分析方法实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。常用工具数据流图数据字典判定树判定表 　软件需求规格说明