计算机国家二级基础知识总结.doc

算法的执行效率与数据的存储结构有关时间复杂度：在运行算法时所需要的时间为f(n)，（即n的函数），算法执行过程中所需要的基本运算次数空间的复杂度：实现算法所占用的空间为f(n)，（即n的函数）线性结构通俗的理解就是能否排成直线：队列是先进先出的线性表，栈是先进后出的线性表，线性表是宏观概念，包括顺序表、链表、堆栈、队列一颗二叉树的节点数：2n-1（n代表是第几层）符合结构化程序设计风格的是使用顺序、选择、循环三种基本控制结构表示程序的控制逻辑没有规定模块有一个入口多个出口，模块之间的可以通过多个接口来耦合结构化程序设计提倡程序的可读性（可理解性），超过程序执行效率的要求结构化程序设计限制使用goto语句因为他可用三种基本的控制结构来代替，只是限制使用面向对象=对象+类+继承+通过消息的通信对象：一组属性及其上的操作的封装体对象不必须用继承性，是属性和方法的封装体，对象间的通信靠消息传递，操作时对象的动态性属性类：一组有相同属性和操作对象的集合继承：一个类为另一个类上的扩充方式，子类继承父类，只要的目的是代码复用消息：对象间通信的手段过程调用只是结构化程序设计或过程式语言中面向对象只是兼容这种方式但不是其特征软件工程的瀑布模型：问题定义，可行性研究，需求分析，概要设计，详细设计，编码，测试，运行和维护可行性研究包括经济可行性、技术可行性、操作可行性、即以最小的代价确定系统的规模是否实现需求分析阶段的工作可分为四个阶段：需求获取、需求分析、编写需求规格说明书以及需求审评，审评每个阶段都有概要设计的任务是确定软件的总体结构、子结构和模块划分详细设计的任务是确定每一模块的实现细节，包括数据结构、算法和接口层次图和HIPO图是概要设计中的工具图；程序流程图、N-S图、问题分析PAD图、设计程序语言PDL是详细设计中的工具图数据结构设计和给出系统模块结构是概要设计中，定义模块算法是详细设计中，定义需求并建立系统模块是分析阶段数据库管理系统DBMS是数据库系统的核心，上层用户打交道，底层与操作系统接口数据库系统是一整套业务系统，包括用户、应用程序、DBMS、及操作系统的支持数据库设计的根本目标是要解决数据共享问题数据库有物理独立性和逻辑独立性数据库的物理结构式最底层即对应内模式，对应的模式映像为内模式/模式（概念模式映像），逻辑独立性则对应于模式/外模式映像数据流图由一些特定的图符构成，用于需求分析阶段，我们只考虑大致的数据流流向，不必讨论控制流，我们只关心的：数据流、数据存储、变换/加工（相当一个黑盒子，不关心内部细节）、外部实体输入流是源，输出流是潭关系表中每一横行称为一个元组，字段：列，属性名；属性：实体的某一特征，如学生表中的学号、姓名；码（主键）：元组（实体）的唯一标识，比如学生有同名的，但是学号是唯一的数据库设计包括：需求分析-（需求说明）-概念设计-（概念结构）-逻辑结构设计-（逻辑结构）-物理设计（物理结构）-算法占用的主要是内存空间，因为算法中的变量、地址等等通常保存在内存中（如果在虚存、缓存、甚至已在CPU中运行，也算是占用存储空间）软件工程的三要素是工具、方法、过程程序流程图（PFD）和N-S图中的箭头代表的是哪条语句的执行，代表控制流层次模式是一颗有向树，每个节点代表一种记录类型，这些节点满足：有且仅有一个节点无双亲（根节点），其他节点有且仅有一个双亲节点网状模型相当一个有向图，一个节点可以有多个双亲节点，且多个双亲节点可以无双亲节点关系模式则是二维表，一张表即为一个关系，如学生关系（学号、姓名、性别）数据模式不是数据库的基本模式数据库模型分为：层次模型、网状模型、关系模型、面向对象模式关系数据库管理系统能实现的专门关系运算包括选择、投影、连接（相当一个表格）确认测试也称合格测试、验收测试，主要由用户参加，检验软件规格说明的技术标准的符合程度，是保证软件质量的最后关键环节单元测试主要采用白盒法，之后再采用集成测试，主要采用黑盒法，白盒测试，我们要注意代码；黑盒测试我们只关心程序运行的输入输出是否正确索引属于内模式，索引的写入修改了数据库的物理结构，而不是简单的逻辑设计，内模式规定了数据在存储介质上的物理组织方式、记录地址方式将E-R图转换到关系模式时，实体与联系都可以表示成 关系，关系可以表示成二维表PAD，问题分析图，常用详细设计PFD，程序流程图，常用详细设计N-S，方框图，常用详细设计DFD，数据流图，原理具体的计算机上的实现，需求分析算法具有确定性、可行性、并拥有足够的情报希尔排序法属于插入类排序法对长度为N的线性进行顺序查找最坏需要N次，二分法最欢Log2 2n的最小整数值，二分法适用于已排序的顺序表模块的独立性越强，则信息的隐蔽性越好数据库概念设计的过程中，视图设计一般有自顶向下、由底向上、由内向外1自顶向下：先全局框架，然后逐步细化2自底向上：先局部概念结构，再集成为全局结构3自里向外：先核心结构，再向外扩张混合策略：1和2结合栈和队列的共同点是值允许在端点处插入和删除元素测试有单元测试，集成测试，确定测试，系统测试程序调试的方法强行排除法，回溯法，原因排除法需求规格说明书的作用是1便于用户、开发人员进行理解和交流2反映出用户问题的结构，可以作为软件开发工作的基础和依据3作为确认测试和验收的依据SQL语言又称为结构化查询语言增加头结点的目的是方便运行的实现单个用户使用的数据视图的描述为外模式栈实际也是线性表，栈只能在一端进行插入和删除，插入和删除的一端为栈顶，另一端栈底，队列只允许在一端删除，在另一端插入，删除一端叫对头，插入一端叫队尾软件调试主要采用三种方法强行排错发：作为传统的调试方法其过程概括为设置断点、程序暂停、观察程序状态、继续运行程序回溯法：适合小规模的排错。原因排除法：是通过演绎和归纳，以及二分法来实现耦合度又高到低内容耦合：一个模块直接访问另一个模块公共耦合：一组模块都访问同一全局数据结构外部耦合：一组模块都访问同一全局数据项控制耦合：一个模块明显的吧开关量。名字等信息送入另一模块，控制另一个模块的功能标记耦合，数据耦合，费直接耦合面向对象的方法主要特征有：表示唯一性，多态性，封装性，模块独立性，集成性和多态性好Scanf的输入特点是遇到空格就停止联合体的几个特点：联合体占用的内存空间为最长的成员所占用的空间各个成员分量全部是从低地址方向开始使用内存单元、联合体中的空间在某一时刻只能保存某一个成员的数据联合体和结构体可以任意嵌套宏的替换有两类：简单的字符替换和带参数的宏替换注意：宏定义仅仅是符号替换，不是复制语句，因此不做语法检查为了区分程序中的其他标识符，宏的定义通常是大写字母、双引号中出现的宏不替换】使用宏定义可以嵌套即后定义的宏可以使用先定义的宏Fread（buffer ，size，count，fp）参数说明：buffer是一个指针，对fread来说，它是读入数据的存放地址。Size是要读写的字节数，count是要进行读写多少个size字节的数据项吗、fp是指文件指针算法的基本特征：可行性、确定性、有穷性、拥有足够的情报当有序线表为顺序存储时才可以使用二分查找类是具有共同属性，共同操作性质的对象集合，是已经定义了的关于对象的特征、外观和行为的模板软件产品从提出、实现、使用维护到停止使用退役的过程成为软件的生命周期软件生命周期的8个阶段 可行性研究与计划、需要分析、概要分析、详细设计、实现、综合测试、确定测试、使用与维护二叉树可以是空集合非空二叉树只有一个根结点；每个结点最多有两颗子树，分别叫左子树和右子树注释一般为序言性注释和功能性注释序言注释包括程序注释、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期和修改日期功能注释一般嵌在源程序体之中，用于描述其后的语句或程序的主要功能数据库管理系统的三级模式：外模式 或子模式或用户模式模式或逻辑模式或概念模式 内模式或存储模式或物理模式度为0的结点比度为2的结点多一个Sizeof的功能是计算出运算对象在计算机的内存中所占用的字节数量，返回值是一个整数 C语言中可以用位置在函数外部说明来指定变量、函数和其他标识符的特征数据结构分为逻辑结构与存储结构内聚性是度量一个模块功能强度的一个相对指标，耦合性则是用来度量模块之间的相互联系程度数据模型就是现实世界的反应，数据模型所描述的内容是数据结构、数据操作、与数据约束数据结构主要研究的是逻辑结构、存储结构、和数据的运算对象的基本特征：标识唯一性，分类性、多态性、封装性、模块独立性好关系模型允许3类数据约束：实体完整性约束，参照完整性约束，用户定义的完整性约束关系表中每一行记录为一个元组Auto类定义的自动变量实质上是一个函数内部的局部变量，作用域是在说明的函数中Register说明只能用于说明函数中的变量和参数中的形参，因此不允许将外部变量或静态变量说明为registerExtern是定义在所有函数之外的全局变量，他可以被所有的函数访问，在多有 函数体的内部是有效的，所以函数之间