计算机二级真题总结.docxVIP

算法的特性：1.有穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成 2.确定性：算法中的每一步都有确切的含义 3.输入：一个算法有零个或者多个输入，零个输入就是算法本身确定了初始条件 4.输出：一个算法有一个或多个输出，以反映出数据加工的结果 5.可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现 算法的有穷性：算法程序的运行时间有限 算法的空间复杂度：算法在执行过程中所需要的内存空间 算法的时间复杂度：执行算法所需要的计算工作量（度量标准：算法所执行的基本运算次数） *算法的空间复杂度和时间复杂度两者没有直接关系* 算法的时间复杂度与使用的计算机、程序设计语言以及算法实现过程中的许多细节无关； 算法的描述：1.伪代码 2.流程图 3.N-S结构图 面向对象基本方法的基本概念：对象、类和实例、消息、继承与多态性 程序执行的效率与1.数据的存储结构、2.数据的逻辑结构、3.程序的控制结构、4.所处理的数据量等有关 线性链表中数据的插入和删除：不需要移动表中的元素，只需要改变结点的指针域即可 线性链表的链式存储结构：各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。 线性结构（线性表）：（前提：一个非空的数据结构）1.有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，也称为线性表；2.可以采用顺序存储和链式存储，其中顺序存储的空间连续而链式存储空间不连续 顺序表：1.线性表中所有元素所占的存储空间是连续的；2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的；3.在顺序表中，每个元素占有相同的存储单元。 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 栈：1.所有的插入与删除都限定在表的同一端进行；2.线性结构；3.先进后出；4.数据的插入和删除都在栈顶进行操作 队列：1.允许在一端进行插入，而在另一端进行删除；2.线性结构；3.先进先出 循环队列：是队列（线性结构）的一种顺序存储结构 *从排头指针front指向的后一个位置知道队尾指针rear指向的位置之间的所有元素均为队列中的元素* 双向链表：1.顺序存储结构；2.有两个指针域 循环链表是链表，循环队列是队列，队列只能在队尾入队，在排头退队，链表可以在任何位置插入、删除 二叉树：1.链式存储结构；2.非线性结构 完全二叉树：1.非线性结构；2.但其最佳存储方式是顺序存储方式 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 线性表的链式存储结构中每个节点都由数据域与指针域两部分组成，增加了存储空间，所以一般要对于顺序存储结构 C语言程序的模块化：通过函数来体现 结构化程序设计的基本原则：1.自项向下 2.逐步求精 3.模块化 4.限制使用goto语句 结构化程序包括的基本控制结构：1.顺序结构；2.选择结构；3.循环结构 程序模块化思想：自项向下、逐步细化 在软件设计中： 1.系统结构图：对软件系统结构的总体设计的图形显示 2.PAD图：在详细设计阶段用到 3.程序流程图：对程度流程的图形表示，在详细设计过程中用到 *数据流图：机构化分析方法中使用的工具，是一种功能模型，是在可行性研究阶段用到的而非软件设计时用到* 对象的基本特点：1.标识唯一性、2.分类型、3.多态性、4.封装性、5.模块独立性好 多态性：同一个操作可以是不同对象的行为 封装性：从外面看只能看到对象的外部特征，而不知道也无须知道数据的具体结构以及实现操作 面向对象基本方法的基本概念：1.对象 2.类和实例 3.消息 4.继承与多态性 继承：是面向对象的方法的一个主要特征，是使用已有的类定义作为基础建立新类的定义技术，是指类之间共享属性和操作的机制 软件：1.程序、2.数据、3.有关文档 软件的特点：1.软件是一种逻辑实体，具有抽象性； 2.软件没有明显的制作过程； 3.软件在使用期间不存在磨损、老化问题； 4.对硬件和环境具有依赖性； 5.软件复杂性高，成本昂贵； 6.软件开发涉及诸多的社会因素，如知识产权等。 软件按功能分：1.应用软件（教务管理系统） 2.系统软件（编译软件、操作系统、汇编程序）、 3.支撑软件（或工具软件）； 软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程 1.软件定义：问题定义、可行性研究、需求分析 2.软件开发：设计、详细设计、实现、测试 3.软件运行维护：运行维护 需求分析阶段（确定软件系统的功能）：1.需求获取 2.需求分析 3.编写需求规格说明书 4.需求审评 软件需求规格说明书的作用：1.便于用户和开发人员进行理解和交流 2.反映出用户问题的结构，可以作为软件