2022年2022年计算机二级vf理论资料 .pdf

第一章数据结构与算法一、算法1. 算法：是指解题方案的准确而完整的描述。通常，程序的编制不可能优于算法。2. 算法的基本特征：a. 可行性 b. 确定性 c. 有穷性（有限的时间、合理的执行时间）d. 拥有足够的情报（一个算法的执行结果总是与输入的初始数据有关）。3. 算法的基本要素：一是对数据对象的运算和操作 算术运算 ( 加减乘除 ) 、逻辑运算（与或非） 、关系运算（大于，小于，等于，不等于）、数据传输（赋值，输入，输出） ，二是算法的控制结构：算法中各个操作之间的执行顺序（描述算法的工具：传统的流程图、NS结构化流程图、算法的描述语言等；算法的三种基本控制结构：顺序、选择、循环) 4. 算法设计的基本方法：a. 列举法 b. 归纳法 c. 递推（本质上也属归纳，从初始条件出发，逐次推出所需求的结果）d. 递归（基础也是归纳，分直接递归和间接递归，从算法本身到达递归边界的，通常递归算法要比递推算法清晰易读，其结构比较简练）e. 减半递推技术 （是工程上常用的分治法，也是归纳法的一个分支）f. 回溯法5. 算法复杂度： 一是时间复杂度( 指执行算法所需要的计算工作量a. 平均性态b. 最坏情况复杂性 ) ；二是空间复杂度（指执行这个算法所需要的内存空间；一个算法所占用的存储空间是算法程序所占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间）二、数据结构的基本概念6. 数据结构指相互有关联的数据元素的集合，其主要研究和讨论的问题：a. 数据的逻辑结构b. 数据的存储结构c. 对各种数据结构进行的运算；目的是提高数据处理的效率（提高数据处理的速度、尽量节省在数据处理过程中所占用的计算机存储空间）7. 数据处理：是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。（无序表的顺序查找与有序表的对分查找）8. 数据的逻辑结构：是指数据集合中各数据元素之间所固有的逻辑关系（数据结构： 表示数据元素的信息、 表示各数据元素之间的前后件关系）反映数据元素之间逻辑关系的数据结构。B=(D，R）9. 数据的存储结构是在对数据进行处理时，各数据元素在计算机中的存储关系，主要有顺序、链接、索引等存储结构10. 在数据结构中的图形表示：没有前件的结点是根结点；没有后件的结点是终端结点；除根节点与终端结点以外的其他结点一般称为内部结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 11. 数据结构：分为线性结构（a. 有且只有一个根结点b. 每一个结点最多有一个前件，也最多有一个后件）和非线性结构（不是线性结构的），两种结构都可以是空的数据结构，按对该数据的结构运算处理判断是否为线性。三、线性表及其顺序存储结构12. 线性表是由n（n=0）个数据元素a1， a2,，, an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件，即线性表或是一个空表。非空线性表的结构特征：a. 有且只有一个根结点a1，它无前件b. 有且只有一个终端结点an，它无后件c. 除了根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n 称为线性表的长度。当 n=0时，称为空表。13. 线性表的顺序存储结构有两个基本特点：a. 线性表中所有元素所占的存储空间是连续的b. 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。14. 在线性表的顺序存储结构下，可以对线性表进行各种处理：线性表的a. 插入 b. 删除 c. 查找 d. 排序 e. 分解 f. 合并 g. 复制 h. 逆转。四、栈和队列15. 栈是限定在一端进行插入与删除的线性表（顺序存储结构） ，是一种特殊的线性表：一端开口允许插入和删除称为栈顶，一端封闭不允许插入和删除称为栈底；即“先进后出” 表或“后进先出”表，具有记忆作用；具有三种基本运算a. 入栈运算b. 退栈运算c. 读栈顶元素16. 队列：在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。一端插入、另一端删除；即“先进先出”表或“后进后出”表。队列的顺序存储结构一般采用循环队列的形式。具有两种基本运算：入队运算和退队运算五、线性链表17. 线性链表属于链式的存储方式，分为单向链表、双向链表和循环链表（实现了空表与非空表的运算统一） 。线性结构与非线性结构都可表示。具有的基本运算如下：a. 插入 b. 删除c. 查找 d. 排序 e. 分解 f. 合并 g. 复制 h. 逆转。六、树与二叉树18. 树是一种简单的非线性结构：上端结点是前件，下端结点是后件，具有明显的层次关系19. 树的基本术语：每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点； 每一个结点可以有多个后件，称为该结点的子结点；没有后件的结点称为叶子结点； 一个结点所拥有的后件个数称为该结点的度；树的最大层次称为树的深度；叶子结点没有子树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 20. 二叉树是一种很有用的非线性结构，其特点是：a. 非空二叉树只有一个根结点b. 每一个结点最多有两颗子树，且分别称为该结点的左子树和右子树。21. 二叉树的性质：a. 在二叉树的第k 层，最多有2k-1（k=1）个结点b. 深度为m的二叉树最多有2m-1个结点 c. 在任意一颗二叉树中，度为0 的结点（即叶子结点）总是要比度为二的结点多一个d. 具有 n 个结点的二叉树，其深度至少为log2n+1 ，其中log2n 表示取 log2n 的整数部分e. 具有 n个结点的完全二叉树的深度为log2n+1 22. 满二叉树是完全二叉树，但是完全二叉树一般不是满二叉树。存储结构：通常采用链式存储结构；二叉树的遍历：前序遍历、中序遍历、后序遍历。七、查找技术类型最坏情况复杂性查找技术长度为 n 的有序表顺序查找n 二分法Log2n 排序技术顺序存储的线性表交换类冒泡排序法n(n-1 ）/2 快速排序法n(n-1 ）/2 插入类简单插入排序法n(n-1 ）/2 希尔排序法O(n1.5) 选择类简单选择排序法n(n-1 ）/2 堆排序法O(nlog2n) 第二章程序设计基础一、程序设计方法与风格1. 程序设计方法和技术发展：经历了结构化程序设计和面向对象的程序设计阶段。“清晰第一，效率第二”是主导的程序设计风格。2. 良好的程序设计风格的要求：a. 在一行内只写一条语句b. 程序编写应优先考虑清晰性c. 除非对效率有特殊要求，程序编写要做到清晰第一，效率第二d. 首先要保证程序正确，然后才能要求提高速度e. 避免使用临时变量而使程序的可读性下降名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - f. 避免不必要的转移g. 尽可能使用库函数h. 避免采用复杂的条件语句i. 尽量减少使用“否定”条件的条件语句j. 数据结构要有利于程序的简化k. 要模块化，使模块功能尽可能单一化l. 利用信息隐蔽，确保每一个模块的独立性m.从数据出发去构造程序n. 不要修补不好的程序，要重新编写3. 输入和输出的原则（P49，8 条）4. 结构化程序设计的方法主要原则：自顶向下，逐步求精，模块化，限制使用goto 语句5. 程序设计的基本控制结构：顺序结构、选择结构（又称分支结构，包括简单选择和多分支选择）和重复结构（也称循环结构）结构化程序设计原则和方法的应用（P51，6 条）3. 面向对象方法的优点：a. 与人类习惯的思维方法一致b. 稳定性好c. 可重用性好（是提高软件生产率的最主要的方法）d. 易于开发大型软件产品e. 可维护性好4. 面向对象方法中的概念：A.对象是指客观世界中的任何实体，其特点a. 标识唯一性b. 分类性 c. 多态性 d. 封装性 e. 模块独立性好B.类和实例： 类是具有共同属性、共同方法的对象的集合， 类是对象的集合，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例C.消息：是一个实例与另一个实例之间传递的信息，有三部分组成，a.接收消息的对象的名称b. 消息标识符（也称消息名）c. 零个或多个参数D.继承：是面向对象的方法的一个主要特征（类之间的共享属性和操作机制）。继承是使用已有的类定义作为基础建立新类的定义技术。分单继承（一个类只允许有一个父类）与多重继承（一个类允许有多个父类） 。F. 多态性：指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。第三章软件工程基础一、软件工程基本概念1. 计算机软件： 是计算机系统中与硬件相互依存的另一部分，是包括程序、 数据及相关文档的完整集合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 2. 软件的特点：a. 是一种逻辑实体，不是物理实体，具有抽象性b. 生产与硬件不同，没有明显的制作过程c. 在运行、使用期间不存在磨损、老化问题d. 软件的开发、运行对计算机系统具有依赖性e. 复杂性高，成本昂贵f. 涉及诸多的社会因素3. 软件按功能分：a. 应用软件b. 系统软件c. 支撑软件（或工具软件）4. 软件的危机：主要是成本、质量、生产方面的问题5. 软件工程：将系统化、规范化、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中。核心思想是把软件产品看作是一个工程产品来处理。具有代表性的技术方法有面向对象方法和软件开发模型及软件开发过程。6. 软件工程过程（4 种活动）： Plan 软件规格说明Do软件开发Check 软件确认Action软件演进7. 软件生命周期：a. 软件定义b. 需求分析c. 软件运行维护；主要的活动阶段：a. 可行性研究与计划制定b. 需求分析c. 软件设计 d. 软件实现 e. 软件测试f. 运行和维护8. 软件工程的目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、 可重用性、 可适应性、 可移植性、 可追踪性和可互操作性且满足用户需求的产品。9. 软件工程的原则：a. 抽象 b. 信息隐蔽c. 模块化 d. 局部化 e. 确定性 f. 一致性 g. 完备性 h.可验证性二、结构化分析方法10. 软件开发方法包括：分析方法、设计方法和程序设计方法11. 结构化方法包括已经形成了配套的结构化分析方法、结构化设计方法和结构化编程方法，其核心和基础是结构化程序设计理论。12. 需求分析方法包括结构化分析方法（面向数据流的结构化分析方法SA ，面向数据结构的Jackson 方法 JSD，面向数据结构的结构化数据系统开发方法DSSD ）和面向对象的分析方法OOA 。13. 结构化分析是使用数据流图（DFD ） 、数据字典（ DD ） 、结构化英语、判定表和判定树等工具，来建立一种新的、称为结构化规格说明的目标文档，其常用工具：a. 数据流图（ DFD ）b. 数据字典（ DD ） c. 判定表 d. 判定树等。三、结构化设计方法1. 软件设计的重要性和地位a. 软件开发阶段（设计、编码、测试）占据软件项目开发总成本绝大部分，是在软件开发中形成质量的关键环节b. 软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径c. 软件设计作出的决策，最终影名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 响软件实现的成败d. 设计是软件工程和软件维护的基础；从技术观点来看：软件设计包括结构设计、数据设计、接口设计、过程设计。从工程管理角度来看，软件设计分为概要设计和详细设计。2. 软件设计的基本原理：a. 抽象 b. 模块化 c. 信息隐蔽 d. 模块独立性 : 内聚性（从弱到强) ：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚（模块的独立程度是评价设计好坏的重要度量标准，内聚性是信息隐蔽和局部化概念的自然扩展，一个模块的内聚性越强则该模块的模块独立性越强; 耦合性（从高到低）：内容耦合、 公共耦合、 外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合（独立性最强）；较优秀的软件设计应为高内聚，低耦合。 、3. 结构化设计方法的基本思想是将软件设计成由相对独立、单一功能的模块组成的结构。4. 软件概要的设计的基本任务：a. 设计软件系统结构b. 数据结构及数据库设计（防卫性、一致性、 冗余性设计） 数据设计应掌握的设计原则（P76,7 条)c. 编写概要设计文档d. 概要设计文档评审 ( 带实心圆的箭头表示传递的是控制信息；带空心圆的箭头表示传递的是数据) 5. 面向数据流的设计方法：A.数据流类型： a. 变换型（处理问题分三步：取得数据、变换数据、输出数据）b. 事务型 B.面向数据流的结构设计方法的实施要点与设计过程6. 设计的准则： a. 提高模块独立性b. 模块规模适中c. 深度、宽度、扇出和扇入适当d. 使模块的作用域在该模块的控制域内e. 应减少模块的接口和界面的复杂性f. 设计成单入口、单出口的模块g. 设计功能可预测的模块7. 详细设计： A.常用的过程设计工具：a. 图形工具 : 程序流程图， NS，PAD ，HIPD b. 表格工具 : 判定表 c. 语言工具： PDL （伪码）8. 程序流程图的5 种控制结构：顺序型、选择型、先判断重复型、后判断重复型、多分支选择型9.NS图具有以下特征：a. 每个构件具有明确的功能域b. 控制转移必须遵守结构化设计要求 c. 易于确定局部数据和（或）全局数据的作用域d. 易于表达嵌套关系和模块的层次关系10.PAD 图具有以下特征：a. 结构清晰，结构化程度高b. 易于阅读c. 最左端的纵线是程序主干线， 对应程序的第一层结构，每增加一层PAD图向右扩展一条纵线，故程序的纵线数等于程序层次数d. 程序执行：从PAD图最左主干线上端结点开始，自上而下、自左向右依次执行，程序终止于最左主干线。11.PDL 具有以下特征：a. 有为结构化构成元素、数据说明和模块化特征提供的关键词语法（过程设计语言）b. 处理部分的描述采用自然语言语法c. 可以说明简单和复杂数据结构d.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 支持各种接口描述的子程序定义和调用技术四、软件测试12. 软件测试：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清楚预期结果与实际结果之间的差别。是为了发现错误而执行程序的过程。13. 软件测试的准则：a. 所有测试都应追溯到需求b. 严格执行测试计划，排除测试的随意性e. 充分注意测试中的群集现象d. 程序员应避免检查自己的程序e. 穷举测试不可能f. 妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便14. 软件测试从是否需要执行被测试软件的角度，分为静态测试和动态测试方法；按功能划分为白盒测试和黑盒测试方法。15. 白盒测试也称结构测试或逻辑驱动测试，其基本原则是保证所测试模块中每一独立路径至少执行一次； 保证所测试模块所有判断的每一分支至少执行一次；保证所测试模块每一循环都在边界条件和一般条件下各执行一次；验证所有数据的有效性。16. 白盒测试的主要方法有：A.逻辑覆盖测试：a. 语句覆盖b. 路径覆盖c. 判定覆盖d. 条件覆盖 e. 判断条件覆盖B. 基本路径测试17. 黑盒测试也称功能测试或驱动测试，其主要诊断功能不对或遗漏、界面错误、 数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。18. 黑盒测试的主要方法：等价类划分法、边界值分析法、错误推测法、因果图。19. 软件测试的实施：按4 个步骤进行：单元测试（静态分析和动态分析，对动态测试通常以白盒测试为主，黑盒测试为辅）、集成测试（增量方式包括自顶向下、自底向上、自顶向下与自底向上相结合的混合增量方式）、验收测试（确认测试，其任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确）系统测试 （其目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方，具体实施包括功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试）五、程序的调试：20. 程序调试的任务是诊断和改正程序中的错误，软件测试贯穿整个软件生命期，调试主要是在开发阶段21. 程序调试的基本步骤：a. 错误定位b. 修改设计和代码，以排除错误，c. 进行回归测试，防止引进新的错误名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 22. 程序调试的原则：A.分析错误的性质和位置时的注意事项a. 分析思考与错误征兆有关的信息 b. 避开死胡同c. 只把调试工具当做辅助手段来使用d. 避免使用试探法，最多只能把它当做最后手段B.修改错误的原则：a. 在出现错误的地方，很可能还有别的错误b. 修改错误的一个常见错误是只修改了这个错误的征兆或这个错误的表现，而没有修改错误本身c. 注意修正一个错误的同时有可能引入新的错误d. 修改错误的过程将迫使人们暂时回到程序设计阶段 e. 修改源代码，不要改变目标代码23. 软件的调试方法:a. 强行排错法b. 回溯法（适合小规模程序的排错）c. 原因排除法（通过演绎和归纳以及二分法来实现的）第四章数据库设计基础一、数据库系统的基本概念1. 数据库系统的基本概念：A.数据：描述事物的符号记录B.数据库：是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享C.数据库管理系统：是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、 控制及保护和数据服务等。完成上述六项功能需要提供相应的数据语言：数据定义语言、数据操纵语言、数据控制语言。（作用： 数据库管理系统是数据库系统的核心。数据的完整性与安全性的维护时数据库管理系统的基本功能）D.数据库管理员： 其主要工作是数据库的设计、数据库的维护和改善系统性能、提高系统效率。E.数据库系统（DBS ） ：由以下几部分组成：数据库（数据）、数据库管理系统（软件） 、数据库管理员（人员），系统平台之一硬件平台（硬件）、系统平台之二软件平台（软件）。F. 数据库应用系统（DBAS ） ：具体包括：数据库、数据库管理系统、数据库管理员、硬件平台、软件平台、应用软件、应用界面。2. 数据库系统的发展a. 文件系统阶段b. 层次数据库与网状数据库系统阶段c. 关系数据库系统阶段3. 数据库系统的基本特点：a. 数据的集成性b. 数据的高共享性与低冗余性c. 数据独立性 ( 物理独立性和逻辑独立性)d. 数据统一管理与控制（数据的完整性检查、数据的安全性保护、并发控制）4. 数据库系统的内部结构体系：A.数据库系统的三级模式a. 概念模式b. 外模式 c. 内模式 B.数据库系统的两级映射a. 概念模式到内模式的映射b. 外模式到概念模式的映射二、数据模型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 5. 数据模型的内容包括三个部分：数据结构、数据操作与数据约束。6. 数据模型按不同的应用层次分为三种：概念数据模型、逻辑数据模型、物理数据模型7. 著名的概念模型：E-R 模型、扩充的E-R 模型、面向对象模型及谓词模型8.E-R模型（实体、属性、联系）；层次模型支持的操作是查询、插入、删除、更新；网状模型；关系模型9. 关系模型的7 个性质： a. 元组个数有限性b. 元组的唯一性c. 元组的次序无关性d. 元组分量的原子性e. 属性名唯一性f. 属性次序无关性g. 分量值域的同一性三、关系代数：10. 关系模型的基本操作：a. 关系的属性指定b. 关系的元组的选择c. 两个关系的合并d. 关系的查询e. 关系元组的插入f. 关系元组的删除11. 关系模型的基本运算：a. 插入 b. 删除 c. 修改 d. 查询（投影运算、选择运算、笛卡尔积运算）四、数据库设计与管理12. 数据库设计是数据库应用的和核心，其基本任务是根据用户对象的信息需求、处理需求和数据库的支持环境（包括硬件、操作系统与DBMS ）设计出数据模式13. 数据库设计一般采用生命周期阶段（8 个阶段）：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段14. 数据库概念设计的方法a. 集中式模式设计法b. 视图集成设计法15. 数据库概念设计的过程：a. 选择局部应用b. 视图设计 （自顶向下、 由底向上、 由内向外）c. 视图集成16. 数据库的物理设计主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。一般的RDBMS 留给用户参与物理设计的内容为：索引设计、集簇设计和区分设计。17. 数据库管理内容包括：a. 数据库的建立（数据模式建立、数据加载）b. 数据库的调整c.数据库的重组d. 数据库安全性控制与完整性控制e. 数据库的故障恢复f. 数据库监控名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -