计算机二级公共基础知识重点

计算机二次公共基础知识焦点计算机二次公共基础一、数据结构和算法1.1.1数据结构的基本概念数据结构表示彼此相关的数据元素的集合。数据逻辑结构反映了数据元素之间的逻辑关系。存储结构是将数据保存在计算机存储空间中的逻辑结构，它分为四种类型：顺序存储、链存储、索引存储和散列存储。数据结构可以分为两种：具体取决于元素之间前后关系的复杂性(1)线性结构：有根节点，每个节点最多有一个直接前兆和一个直接后继非空数据结构。(2)非线性结构：不满足线性结构的数据结构。1.1.2算法1.算法的基本概念(1)概念：算法意味着对解决问题的方法的准确、完整的说明。(2)基本特征：可行性、确定性、贫穷性和充分的信息。(3)基本要素：数据对象的计算和操作、算法和控制结构。(4)设计的基本方法：枚举方法、归纳方法、递归方法、半递归技术、回溯方法。算法的复杂性(1)算法的时间复杂性：运行算法所需的计算工作量。(2)算法的空间复杂性：运行算法所需的内存空间。1.1.3线性表及其顺序存储结构1.定线表格的基本概念定线结构也称为定线表格，定线表格是最简单、最常用的资料结构。2.线性表的顺序存储结构顺序存储结构具有以下特点：(1)元素占用的存储空间必须连接在一起。(2)元素按逻辑顺序存储在存储空间中的位置。3.插入路线表操作在I元素之前插入新元素时，首先将原始I节点向后移动一个元素位置，直到第n个节点。然后将新节点放置在第I个位置，最后修改线性表中的节点数。4.删除定线表格要删除I位置的元素，请先将I后不包含第I个元素的n-i元素向前移动一个位置，然后修改线性表格中的节点数。1.1.4堆栈和队列1.堆栈和基本运算堆栈是特殊的线表，插入和删除操作只在线性表的一端进行，也称为先进先出表或后进先出表。堆栈顶部是允许插入和删除的一端，堆栈底部是堆栈顶部的另一端。空堆栈是堆栈中没有元素的堆栈。堆栈具有以下特征：(1)堆栈顶层元素艺术家最后插入的、最早删除的元素。(2)插入到堆栈的第一个、最后删除的元素。(3)栈起记忆作用。(4)在顺序存储结构中，堆栈的插入和删除操作不需要移动表中的其他数据元素。(5)堆栈顶部指针top动态反映堆栈中元素的更改。顺序存储和运算包括人堆栈运算、反向堆栈运算和读堆栈锯运算。2.队列和基本运算队列是可以在一端插入并在另一端删除的线性表，也称为先进先出(first-out)的线性表。尾部是允许插入的一端，通常用尾部指针指向页脚元素。头是允许删除的一端，通常用头指针指向头元素以前的位置。循环队列及其操作包括入队和出队操作。1.1.5树和二进制树1.树的基本概念树是简单的非线性结构，树没有前导节点，其馀节点不相交的有限点被划分为不相交的m个有限集合T1、t2tm，每个集合称为T1，t2tm是与节点的子树。(1)父节点：每个节点只有一个前置节点，没有前置节点的节点只有一个称为树的根节点(2)子节点：每个节点可以有多个背面项目，没有背面项目的节点称为叶节点。(3)树的度：因此节点的最大度(4)树的深度：树的最大级别。二叉树和基本特性二叉树是非线性结构，是有限节点集，由两个左叉树和右叉树组成，这两个叉树是空的或与一个根节点不相交的。可以分为完整的二叉树和完整的二叉树。完整的二进制树必须是完整的二进制树，但整个二进制树不一定是完整的二进制树。二进制树的特征包括：(1)二进制树可以为空，空的二进制树没有节点，非空的二进制树只有一个根节点。(2)每个节点最多可以有两个子树：左子树和右子树。二叉树存储结构二进制树使用链存储结构，通常由数据域和指针字段组成。完整的二进制树和完整的二进制树可以按层次顺序存储。二叉树遍历二进制树的遍历不重复访问二进制树的节点，主要表示非空的二进制树，对于空的二进制树，结束返回。二叉树遍历分为预遍历、中间遍历和后遍历。1.1.6寻找技术(1)顺序查找：在路线表中查找指定的元素。(2)二进制查找：此查找仅适用于连续存储结构的线性表，它必须是连续表，如果需要二分查找，则重复查找成功或子表长度为零时结束。1.1.7校准技术(1)交换类排序方法：通过数据元素(例如冒泡和快速排序)之间的相互交换进行排序。(2)插入类排序方法：将未排序序列中的每个元素按顺序插入到已排序的线性表中，例如简单插入排序方法和跟排序方法。(3)选择类排序方法，例如，选择整个路线表中最小的元素并将其交换到表的开头，查找其馀元素中最小的元素并将其交换到最小元素的后面。包括简单选择排序方法和推式排序方法。1.2编程基础1.2.1编程方法和风格(1)编程主要是指具有结构化编程方法、软件过程方法和面向对象方法的程序的设计、准备、调试方法和过程。(2)好的设计风格应该集中在源代码文档、数据描述方法、语句的结构和输入输出等因素上。1.2.2面向对象的编程面向对象方法的本质是强调，从客观世界固有的事物构建系统，构建的系统可以映射问题领域。面向对象方法可以涵盖的主要概念如下：(1)目标：用来表示客观世界的任何实体，可以是有明确界限和意义的任何东西。(。(2)类：具有公共属性和公共方法的对象的集合。(3)消息：在实例之间传递的消息，它整合了数据流和控制流。(4)继承：基于现有类定义创建新类的定义技术。(5)例如，特定对象是分类的实例。(6)多态：对象根据自己接受的信息行事，当同一信息被接受到其他对象中时，对象的行为会有所不同。(。面向对象编程的优点：思维方式与人类习惯一致，稳定性好，可重用性好，开发大型软件产品的简便性好，可维护性好。1.3软件工程基础1.3.1软件工程基本概念1.软件定义和特性软件表示与计算机系统运行相关的计算机程序、领域、规则和可能的文件、文档和数据。软件具有以下特征：(1)逻辑实体和抽象。(2)生产没有明显的制作过程。(3)运行过程中没有磨损和老化问题。(4)由于依赖于计算机系统的开发和运行，软件存在迁移问题。(5)复杂性高，成本高。(6)发展包括很多社会因素。2.软件危机和软件工程(1)软件危机：是指计算机软件开发和维护中出现的一系列严重问题。(2)软件工程：适用于定义、开发和维护计算机软件的整套方法、工具、手册、实践标准和程序。(3)软件工程由开发技术和软件工程管理两部分组成。(4)软件工程流程：将输入转换为输出的一组相关资源和活动。(5)软件生命周期：软件产品从建议、实施、使用维护到停止使用的过程。(6)软件工程的目标：以给定的成本、进度为前提，开发符合用户要求的产品，具有有效性、可靠性、可理解性、可维护性、可重用性、可移植性、可追溯性和互操作性。(7)软件工程的最终原则：抽象、信息隐藏、模块化、本地化、确定性、一致性、完整性和可验证性。(8)软件开发工具：要从早期单向工具发展到集成工具，软件开发方法必须得到该工具的支持。(9)软件开发环境：全面支持开发过程的软件工具栏。计算机辅助软件工程是当前的研究工作和开发方向。1.3.2结构化分析方法需求分析可以汇总为需求获取、需求分析、需求规格说明和需求复查。典型的分析方法包括：(1)结构化分析方法：实质上侧重于数据流，由上而下、按层次分解，建立系统的处理流，使用典型的数据流图、数字词典、判断树和判断表等工具。(2)面向对象的分析方法。1.3.3结构化设计方法1.软件设计的基本概念和方法软件设计是将软件要求转换为软件表示的过程。(1)基本原则：抽象、模块化、信息隐藏、模块独立性。(2)基本思路：将软件设计成相对独立、具有单一功能的模块的结构。2.摘要设计(1)摘要设计包括设计软件系统结构、数据结构和数据库设计、摘要设计文档创建、摘要设计文档审阅等四项任务。(2)数据流导向设计方法：数据流图中的信息分为交换和事务形式的交换流和事务物流。3.详细设计的工具(1)图形工具：流程图、N-S、pad、HIPO。(2)表格工具：决定表格。(3)语言工具：伪代码(PDL)。1.3.4软件测试软件测试的目的是发现错误，其说明如下：(1)因此，测试应追溯到用户要求。(2)严格执行测试计划，排除测试的随机性。(3)充分注意测试的集群现象。(4)程序员不得确认自己的程序。(5)彻底的测试是不可能的。(6)适当保存设计计划、测试案例、错误统计和最终分析报告。软件测试方法可以从被测试软件是否需要运行的角度分为静态测试和动态测试，按功能分为白盒测试和黑盒测试。(1)白盒测试：也称为结构测试，根据软件的内部逻辑设计和工作过程检查软件的内部组件。主要方法包括逻辑覆盖测试、基本路径测试等。(2)黑盒测试：也称为功能测试，根据规格的功能设计测试，包括等效分割、边界值分析、错误估计方法、原因图等。1.3.5程序调试程序调试的主要任务是诊断和更正程序中的错误，应用的主要方法是强制误行方法、回溯方法和原因排除。1.4数据库设计基础1.4.1数据库系统的基本概念(1)数据：描述事物的符号记录，分为临时数据和永久数据。(2)数据库：长期存储在计算机内部的有组织的、可共享的数据集合。(3)数据库管理系统：负责数据库的系统软件，如数据组织、数据操作、数据维护、控制和保护、数据服务等。(4)数据库技术开发经历了手动管理阶段、文件系统阶段、数据库系统阶段等三个阶段。(5)数据库系统具有整合、高共享、低冗馀、数据集成管理和控制功能。(6)三阶段模式(概念模式、内部模式、外部模式)和辅助模式(外部模式/概念模式的映射、概念模式/内部模式的映射)构成了数据库系统内部的抽象结构系统。1.4.2数据模型数据模型以抽象层次描述系统的静态特征、动态行为和约束条件，所描述的内容是数据机制、数据操作和数据约束条件。概念数据模型、逻辑数据模型和物理数据模型是数据模型的三层。(1)E-R模型：提供表示实体、属性和连接的方法。实体和实体之间有“一对一”、“一对多”和“多对一”的关联。(2)层次模型：使用树结构表示实体及其之间的连接。其中节点是实体，分支是连接，从上到下是一对多关系。(3)网格模型：对以网格结构表示实体及其之间连接的层次模型的扩展。网格模型是记录型节点，反映了现实中更复杂的事物连接。(4)关系模型：显示为二维表，您可以在其中查询、添加、删除和修改数据。关系模型允许定义三种约束：实体完整性、参照完整性和用户定义的完整性。1.索引键：在2d表格中唯一识别祖系的一组最小属性。2.候选关键字：二维表中可能存在一些关键字。3.主键：二维表中所有关键字使用的键之一。1.4.3关系代数(1)典型的集合运算包括关系和运算、关系交叉运算、关系差异运算和广义笛卡尔乘积；(2)特殊关系运算包括选择、投影和连接。1.4.4数据库设计和管理1.数据库设计概述数据库设计通常是通过应用面向数据的方法和面向流程的方法来完成的，并以流程迭代和逐步细化为基本思路资料库的设计阶段为需求分析-概念设计-逻辑设计-实体资料-代码-测试执行-进一步修改2.分析数据库设计要求需求收集和分析员数据库设计的第一步。此阶段使用了很多结构化分析方法和面向对象的方法，主要用于数据流程图、数据分析、功能分析、功能处理模块以及确定数据之间的关系。数据字典