计算机二级基础知识

全全国国计计算算机机二二级级考考试试精精华华1第一章一、数据结构与算法1.算法A．基本特征：可行性、确定性、有穷性、拥有足够的情报B．基本要素：对数据对象的运算和操作、算法的控制结构C．设计的基本方法：列举法、归纳法、递推法、递归法、回溯法、减半递推技术D．复杂度：时间复杂度、空间复杂度2.数据结构的基本概念A．定义：相互有关联的数据元素的集合，即数据的结构形式，包括逻辑结构和存储结构B．图形表示：前后件关系（结点）直观易懂C．线性结构（线性表）和非线性结构注：一个线性结构中插入或删除任何一个结点后还应该是线性结构，否则不能称之为线性结构3.线性表及其顺序存储结构全全国国计计算算机机二二级级考考试试精精华华2A．基本概念：有限序列；除第一个元素，有且只有一个前件，除最后一个元素，有且只有一个后件；要么是空表，要么表示为（a1，a2，……，ai，……，an），其中ai（i=1,2,……，n）是一个结点B．特点：元素占得存储空间连续性，元素存储的位置按逻辑顺序C．插入运算步骤：a插入点后所有结点后移一位；b放新结点；c修正线性表结点个数D．删除运算步骤：a插入点后所有结点前移一位；b修正线性表结点个数4.栈和队列A．栈：特殊的线性表，插入和删除都在一端进行，称为栈顶（top），另一端称为栈底（bottom），存在空栈特点：具有记忆功能，不需要移动元素，指针top反变化情况映，栈顶元素后插先被删，栈底元素先插后被删基本运算：入栈运算、退栈运算、读栈顶元素B．队列：特殊的线性表，一端插入另一端删除，插入段为队尾，被尾指针rear指着，删除端为排头，被头指针front指着基本运算：入队运算、出队运算全全国国计计算算机机二二级级考考试试精精华华3C．循环队列尾指针指向尾元素，头指针指向头元素，初始状态为空即rear=front基本运算：入队运算、出队运算5.线性链表组成：数据域、指针域特点：用一组不连续的存储单元存储线性表中的各个元素基本运算：排序，查找，逆转，复制，合并。分解，插入，删除循环链表：单链表第一个结点前增加一个表头结点并被队头指针指着，最后一个结点的指针域值由NULL改为指向表头结点6.树和二叉树A．树：以分支关系定义的层次结构，由n个结点构成的有限集合树的结点必需条件：a有且只有一个没有前驱的结点称为根，b其余结点分为m个互不相交的有限集合T1，T2，……，Tm，每一集合又可作为一棵树，称为根结点的子树注：只有一个前件的结点称为父结点，任意元素是各自前件的子结点，一个结点包含的后继个数为该结点的度，所有结点最大的度则为树的度，树的大层次为树的深度B．二叉树：一个有限的结点集合，由一个根结点和两棵互不相交的左右二叉子树组成，集合为空时则称为空二叉全全国国计计算算机机二二级级考考试试精精华华4特点：a空二叉树没有结点，非空二叉树则有且只有一个，b每个结点最多两颗子树满二叉树：除最后一层外，每一层的所有结点都有两个子结点第k层上有2k-1个结点，深度为m的满二叉树中有2m-1个结点完全二叉树：除最后一层外，每一层的结点数都达到最大值，只有最后一层缺少右边的若干结点性质：a非空二叉树的第k层最多有2k-1个结点，b深度为m的满二叉树中有2m-1个结点，c有n个结点的完全二叉树的深度为【log2n】+1，d对任一树，度为0的结点总比度为2的结点多一个存储结构：链式存储结构遍历：不重复的访问二叉树中的所有结点，主要分为前序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）7.查找A．顺序查找基本思路：从第一个元素依次比较被查找的元素与线性表中的元素，直到找到为止，若没有找到则查找不成功注：有序的链式存储结构线性表和无序的线性表只能用顺序查找全全国国计计算算机机二二级级考考试试精精华华5B．二分查找条件：线性顺序存储的有序表查找过程：将x与中间项比较，分半再与中间项比较，直至查找成功或子表长度为0为止8.排序技术A．交换类排序法：借助元素的“交换”进行排序a冒泡排序法：从表头或表尾依次查找相邻元素并将较大的元素不断向后移直至消除所有的逆序才结束，适当重复上述过程b快速排序法：选取任一元素T，在剩下的线性表中逐个选取元素进行排序直至所有元素全部选取完毕才结束，适当重复上述过程B．插入类排序法：将无序序列中的各元素插入有序的线性表中a简单插入排序法：选取任一元素T作为有序表，其余元素作为无序表，从无序表中选取元素插入有序表中形成新的有序表，直至无需表为空时才结束b希尔排序法：将整个分割成若干个相隔某个增量h的小的子序列并分别进行插入排序C．选择类排序法：每次从待排序序列中选取最小的元素放在已排好的有序子表后面直到全部序列满足排序要求才结束全全国国计计算算机机二二级级考考试试精精华华6a简单选择排序法：从n个待排序序列元素中选取最小的元素与第一个元素交换，剩下的n-1个元素中选取最小的元素与第二个元素交换，重复操作直至所有元素有序为止b堆排序法：将一个无序序列建成堆，……二、程序设计基础1．程序设计方法与风格A．程序设计方法：研究问题求解如何进行系统构造的软件方法程序设计：设计程序、编制程序、调试程序的方法和过程方法：结构化程序设计方法、软件工程方法和面向对象方法B．程序设计风格：编写程序时所表现的特点、习惯和逻辑思路规范（注重考虑的因素）：源程序文档化，数据说明方法，语句的结构，输入和输出2.结构化程序设计：一种面向过程的程序设计方法原则：自顶向下、逐步求精、模块化、限制使用goto语句基本结构：顺序结构、选择结构、循环结构注：控制结构只准许有一个入口和一个出口，程序语句组成的块只有一个入口和一个出口，对语言中没有的控制结构采用前后一致的方法来模拟，复杂结构应采用嵌套的基本控制全全国国计计算算机机二二级级考考试试精精华华7结构进行组合嵌套来实现，使用有限的控制结构表示控制逻辑3.面向对象的程序设计A．本质：以客观事物来构造系统，用人类思维认识、理解和描述客观事物，最终建立的系统能够映射问题域B．优点：稳定性好，可重用性好，可维护性好，易于开发大型软件产品，与人类习惯的思维方法一致C．特点：封装性、继承性、多态性、标识唯一性D．基本概念a对象：用来表示客观世界任何实体，是最基本的概念b类：具有共同属性、方法的对象的描述，是对象的抽象描述c实例：一个具体对象是其对应类的实体d消息：一个实例和另一个实例之间传递的信息e继承：使用已有的类定义，上层有父类，下层有子类f多态性：对象根据所接受的信息而做出动作，同样的信息被不同的对象接收时可以有不同的行动全全国国计计算算机机二二级级考考试试精精华华8三、软件工程基础1.软件工程基本概念A．软件：与计算机系统操作有关的程序、规程、规则、数据特点：抽象性，无明显制作过程，没有磨损老化问题，复杂性高，成本昂贵，对计算机系统依赖性强，涉及诸多社会问题核心思想：把软件产品看做是一个工程产品来处理B．软件危机：泛指软件在开发和维护中遇到的成本、质量、生产率等严重问题C．软件工程:应用于计算机软件的定义、开发、维护的方法、工具、文档、实践标准、工序D．软件生命周期：从提出、实现、使用维护到停止使用E．软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性等F．软件工程目标：给定成本、进度的前提下，开发出有效性、可靠性、可维护性、可重用性、可适应性、可移植性、可追踪性、可互操作性的适应用户需求的产品2.结构化分析方法全全国国计计算算机机二二级级考考试试精精华华9A．需求分析的阶段性工作：需求获取、需求分析、编写需求规格说明书、需求评审任务：发现需求、求精、建模、定义需求的过程方法：结构化分析方法、面向对象分析方法B．结构化分析方法实质：着眼于数据流，自顶向下逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型常用工具：数据流图（DFD）、数据字典（DD）、判断树、判断表注：数据存储是静止状态的，数据流是运动中的数据C．软件需求规格说明书：需求分析阶段的最后结果标准：正确性、无歧义性、完整性、可验证性、可理解性、一致性、可修改性、可追踪性3.结构化设计方法A．基本概念a软件设计：把一个软件需求转化为软件表示的过程基本目标：用抽象概括的方式确定目标系统如何完成预定任务b（独立性）：耦合性、内聚性全全国国计计算算机机二二级级考考试试精精华华10c结构化设计方法：决定用哪些方法把哪些部分联系起来解决好某个具体有清楚定义的问题基本思想：将软件设计成相对独立、单一功能的模块组成结构B．概要设计a任务：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审b面向数据流的设计方法；DFD从系统的输入数据流到系统的输出数据流的一连串连续加工形成的一条数据流图的信息流设计过程：确认数据流图类型，说明数据流的边界，把数据流图映射为程序结构，根据设计准则对产生的结构进行优化结构化设计准则：提高模块独立性、模块的作用域应在控制域内、模块功能可以预测、深度宽度扇入扇出应适中、模块规模适中、降低模块接口的复杂度、设计单接口和单出口的模块C．详细设计a任务：为软件结构图中的模块确定实现算法和局部数据结构，用表达工具表示算法和全全国国计计算算机机二二级级考考试试精精华华11数据结构的细节b常用工具：图形工具、表格工具、语言工具4.软件测试：需求定义阶段的需求测试，编码阶段的单元测试、集成测试，之后的确认测试、系统测试，检验是否合格A．目的：发现错误而执行程序的过程B．准则：追溯用户需求，排除测试随意性，注意测试中的群集现象，妥善保存测试计划、测试用例、出错统计、最终分析报告，程序员避免检查自己的程序，穷举测试不可能C．方法：从是否需要被测软件的角度、按功能划分a静态测试：通过人工分析，不实际运行软件，包括代码检查、静态结构分析、代码质量度量b动态测试：基于计算机的测试注：测试用例：为测试设计的数据c白盒测试：根据程序内部逻辑设计，用于检查逻辑通路d黑盒测试：根据规格说明书的功能设计，用于检查程序功能全全国国计计算算机机二二级级考考试试精精华华12D．实施：单元（模块）测试、集成（组装）测试、确认（验收）测试、系统测试5.程序的调试：对程序中的错误的定性、定位和排错A．目的：诊断和改正程序中的错误B．原则：确定错误的性质和位置，修改错误C．组成：a确定程序错误的确切性质、原因和位置b对程序进行修改，排除这个错误D．方法：强行排错法，回溯法，原因排除法，（从是否跟踪和执行程序出发，分为静态调试和动态调试）E．步骤：a错误定位b修改设计和代码以排除错误c进行回归测试以防止引入新的测试四、数据库设计基础1.数据库系统的基本概念A．数据（Date）：描述事物的符号记录B．数据库（DB,DateBase）：长期存储在计算机内的、有组织的、可共享的数据集合C．数据库管理系统（DBMS,DateBaseManagementSystem）：数据库的机构，一个系统软件，负责数据的组织、操纵、维护、控制、保护和服务类型：文件管理系统、层次数据库系统、网状数据库系统、关系数据库系统（最广泛）全全国国计计算算机机二二级级考考试试精精华华13传统数据模型：层次数据模型、网状数据模型、关系数据模型D．数据库系统（DBS）：引进数据库技术后的计算机系统，实现有组织的、动态的存储大量数据，提供数据处理和信息资源共享组成：硬件系统、数据库、数据库管理系统、数据库管理员、用户特点：共享并减少数据冗余，用特定的数据模型，有较高数据独立性，有统一的数据控制功能注：数据库∈数据库管理系统∈数据库系统E．数据库系统的发展：人工管理、文件系统、数据库系统、分布式数据库系统、面向对象的数据库系统F．特点：数据集成性、数据高共享性与低冗余性、数据独立性、数据统一管理和控制G．内部机构体系：3级模式及2级映射注：一个数据库只有一个概念模式和一个内模式，可有多个外模式H．数据库管理系统：用户和操作系统之间的数据管理软件主要目标：是数据成为方便用户使用的资源并增进数据的安全性、完整性和可用性功能：数据的定义、操作、组