计算机二级ACC公共基础知识重难点.docVIP

二级公共基础知识 数据结构 算法：指解题方案准确而完整的描述。 算法基本特征：1）可行性；2）确定性；3）有穷性；4)拥有足够情报。 算法复杂度：1）时间复杂度：执行过程中所需基本运算次数； 2）空间复杂度：执行此运算所需内存空间。 数据结构包括：数据的逻辑结构、存储结构、数据的逻辑运算。 数据结构：相互有关联的元素的集合 1）逻辑结构：数据元素之间前后件关系； 2）存储结构：逻辑结构在计算机中存放形式； 3）常用存储结构：顺序、链接、索引。 数据结构分类：线性结构、非线性结构。 栈：先进后出； 队列：先进先出。 线性链表：线性表的链式存储结构。 线性链表中用指针HEAD指向第一个元素结点； 最后一个元素没有后件其指针域为空，用Null或0表示。 10.、线性链表中插入和删除运算不需要移动表中元素，只需改变有关元素指针。提高效率，浪费时间。 11.、树是一种非线性结构。 12.、一个结点拥有后件个数称为该结点的度。 13.、所有结点中最大度称为树的度。 14.、以某结点的一个根结点为根构成的树称为该结点的一棵子树。 15.、二叉特点：1）非空二叉只有一个根结点；2）每一个结点最多有二个子树，左子树、右子树。 16.、二叉树性质：1）第k层最多有2（k≥1）个结点； 2）深度为m的二叉树最多有2-1结点； 3）度为0的结点（叶子结点）总是比度为2的结点多一个。 17.、满二叉树指除最后一层外每一层所有结有结点有2个子结点。 18.、完全二叉树：除最后一层外每一层上结点数均达最大值，最后一层上只缺少右边若干个结点。 19.、二叉树遍历：不重复地访问二叉树所有结点。1）前序遍历：根左右；2）中序遍历：左根右；3）后序遍历：左右根。 20.、查找：1）长度为n的线性表，顺序查找在平均情况下大约要与线性表中一半元素进行比较，最坏情况下比较n次。 2）二分法查找适用于顺序存储的有序表，对长度为n的有序线性表，最坏情况下比较logn次。 21.、排序：将一个无序序列整理成按值非递减顺序排列的有序序列。 排序分类 排序方法 最坏情况下比较次数 交换法 冒泡法 n(n-1)/2 快速法 插入法 简单插入法 希尔排序法 0（n） 选择法 简单选择法 n(n-1)/2 堆排序法 0(logn) 程序设计基础 程序设计主要通过了结构化程序设计和面向对象程序设计阶段。 当今主导程序设计风格：“清晰第一，效率第二”。 程序注释分为：序言性注释、功能性注释。 语句结构应注意：1）一行只写一条语句； 2）优先考虑清晰性； 3）模块化，模块功能单一化； 4）利用信息隐蔽，确定每个模块独立性。 结构化程序设计方法主要原则：自顶向下、逐步求精、模块化、限制使用goto语句。 程序设计语言仅用 顺序、选择、重复 三种基本控制结构就足以表达出其它各种程序设计方法。 对象之间通过传递消息互相联系。 对象由一组表示其静态特征的属性和它可执行的一组操作组成（动态属性也被称为方法）对象是属性和方法的封装体。 对象特点：1）标志唯一性；2)分类性；3）多态性；4）封装性（实现信息隐蔽）；5）模块独立性好。 类：具有同属性、共同方法的对象的集合。对象是其对类的一个实例。 消息是一个实例与另一个实例之间传递的信息。 继承是类之间共享属性和操作的机制。提高软件可重用性。 软件工程 计算机软件包括程序、数据、相关文档的完整集合。 软件特点：1）软件是一种逻辑实体而不是物理实体，具有抽象性。 2）软件不存在磨损老化问题、但存在退化； 3）软件的开发运行对计算机系统依赖性，受计算机系统的限制。 软件分类：应用、系统、支撑（工具）软件。 软件危机可分为：成本、质量、生产率问题。 软件工程的主要思想都是在强调在软件开发工程中需要应用 工程化原则。 软件工程三要素：方法、工具、过程。方法是完成软件工程面目的技术手段；工具是支持软件的开发、管理、文档生成；过程支持软件开发各个环节的控制管理。 软件生命周期：软件产从提出、实现、使用维护到停止使用退役的过程。 1）可行性研究； 2）需求分析：准确地确定“系统必需做什么”以及目标系统必需具备哪些功能性能； 3）概要设计（总体设计）：系统怎么做、软件功能分解； 4）详细设计：为分解出的每个模块设计实现过程（算法）； 5）软件实现（编码阶段）：把软件设计转换成计算机可以接受的程序代码； 6）软件测试：在软件投入生产运行前尽可能多地发现错误，是保证软件质量的重要手段； 7）运行维护：改正、适应、完善、预防性维护。 软件工程的理论和技术性研究内容：软件开发技术、软件工程管理。 10、软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性。 11、软件开发环境或软件工程 环境是全面支持软件