计算机二级理论知识精华版(共6页).doc

《计算机二级理论知识精华版(共6页).doc》由会员分享，可在线阅读，更多相关《计算机二级理论知识精华版(共6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第一章 数据结构与算法第一节 算法一、算法的基本概念所谓算法是指解题方案的准确而完整的描述。1、算法的基本特征:(1)可行性(2)确定性(3)有穷性(4)拥有足够的情报2、算法的基本要素(1)算法中对数据的运算和操作算术运算，逻辑运算，关系运算，数据传输(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。一个算法可以用顺序、选择、循环三种基本控制结构组合而成。2、算法设计的基本方法(1)列举法(2)归纳法(3)递推(4)递归(5)减半递推技术二、算法复杂度1、算法的时间复杂度：指执行算法所需要的计算工作量。用算法在执行过程中所需基本运算的次数来衡量算法

2、的工作量。方法：平均性态，最坏情况复杂性2、算法的空间复杂度：指执行这个算法所需的内存空间。第二节 数据结构的基本概念一、什么是数据结构数据结构是指相互有关联的数据元素的集合。如：(1)春、夏、秋、冬 (2)父亲、儿子、女儿(1)数据元素有共同的特征(2)各个元素之间存在着某种关系(联系)。用前后件关系来描述。如：夏是秋的前件，秋是夏的后件。父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件1、数据的逻辑结构数据结构是指带有结构的数据元素的集合。一个数据结构应包含以下两方面的信息：(1)表示数据元素的信息(2)表示各数据元素之间的前后件关系，前后件关系是逻辑关系，与它们在计算机中的存储位置无关。

3、数据的逻辑结构反映数据元素之间的逻辑关系。2、数据的存储结构数据的逻辑结构在计算机中的存放形式称为数据的存储结构，也称数据的物理结构。采用不同的存储结构，数据处理的效率不同。一般情况下，数据的逻辑结构和存储结构是不同的。二、数据结构的图形表示每一个数据元素用中间标有元素值的方框表示，称为数据结点，简称结点。用一条有向线段从前件结点指向后件结点。数据1 数据1 数据1 nullhead父亲儿子女儿春夏秋冬在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点(也称为叶子结点)。其他结点一般称为内部结点。插入与删除是对数据结构的两种基本运算还有查找、分类、合并、分解、复制和修改等运算三

4、、线性结构与非线性结构根据各数据元素之间前后件关系，将数据结构分为：线性结构与非线性结构线性结构满足以下两个条件：(1)有且只有一个根结点(2)每一个结点最多只有一个前件，也最多有一个后件线性结构又称为线性表。第三节 线性表及其顺序存储结构一、线性表的基本概念线性表是由n个数据元素a1，a2,an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。特征：(1)有且只有一个根结点a1 ，它无前件。 (2)有且只有一个终端结点an ，它无后件。 (3)其它结点有且只有一个前件和一个后件。线性表中结点的个数n称为线性表的长度，n为0称为空表二、

5、线性表的顺序存储结构线性表的顺序存储结构具有以下特点(1)线性表中所有元素所占的存储空间是连续的。(2)线性表各数据元素在存储空间中是按逻辑顺序依次存放的。三、线性表的插入运算要在第i个元素前插入一个新元素，要从最后一个元素开始，直到第n-i+1个元素依次向后移动一个位置,第i个位置就被空出，然后将新元素插入到第i项。四、线性表的删除运算要删除第i个元素，要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。第四节 栈和队列一、栈及其基本运算栈是一种特殊的线性表。一端是封闭的，不允许进行插入与删除，另一端是开口的，允许进行插入与删除。如：子弹夹栈中的元素遵循“先进后出”

6、或“后进先出”的原则二、队列及其基本运算队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为排头(也称为队头)。 遵循“先进先出”或“后进后出”的原则，体现了“先来先服务”的原则第五节 线性链表一、线性表的缺点(1)插入与删除的效率低(2)线性表的存储空间不便于扩充(3)不便于对存储空间的动态分配二、线性链表的概念V(i) Next(i)数据域 指针域在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域。另一部分用于存放指针，称为指针域。二、线性链表的概念线性表的链式存储结构称为线性链表。在线性链表中，各数据元素之间的前

7、后件关系由各结点的指针域来表，指向第一个结点的指针HEAD称为头指针。第六节 树与二叉树一、树的基本概念树是一种简单的非线性结构，所有元素之间的关系具有明显的层次特征。1、树的基本术语(1)每一个结点只有一个前件，称为该结点的父结点(2)没有前件的结点只有一个，称为根结点(3)每一个结点可以有多个后件，称为该结点的子结点(4)没有后件的结点称为叶子结点(5)每一个结点所拥有的后件个数称为该结点的度，叶子结点的度为0(6)所有结点中的最大的度称为树的度(7)树的最大层次称为树的深度(8)在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。二、二叉树及其基本性质1、什么

8、是二叉树(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树，称为左子树与右子树即每一个结点的度最大为22、二叉树的基本性质(1)在第k层上，最多有2k-1(k1)个结点(2)深度为m的二叉树最多有2m-1个结点(3)度为0的结点(即叶子结点)比度为2的结点多1个(4)具有n个结点的二叉树，其深度至少为log2n+1其中log2n表示的log2n整数部分。3、满二叉树与完全二叉树(1)满二叉树指，除最后一层外，每一层上的所有结点都有两个子结点。即每一层上的结点数均达到最大值。 满二叉树的第k层上有有2k-1个结点 深度为m的满二叉树有2m-1个结点(2)完全二叉树指，除最后一层外，每一

9、层上的结点数均达到最大值。在最后一层上只缺少右边的若干结点。满二叉树是完全二叉树，但完全二叉树一般不是满二叉树三、二叉树的遍历(递归方法)(1)前序遍历(2)中序遍历(3)后序遍历第七节 查找技术查找是指在一个给的数据结构中查找某个指定的元素。1、顺序查找顺序查找一般是指在线性表中查找指定的元素。过程：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等则表示找到(查找成功)。若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示没有找到要找的元素(查找失败)。2、二分法查找二分法查找只适用于顺序存储的有序表。方法：设有序线性表的长度为n，被查元素为x(1)将x与线性表的

10、中间项进行比较；(2)做中间项等于x，则说明查到，查找结束；(3)若x小于中间项，则线性表的前半部分以相同的方法继续进行查找。 (4)若x大于中间项，则线性表的后半部分以相同的方法继续进行查找。第八节 排序技术一、交换类排序法1、冒泡排序法2、快速排序法二、插入类排序法1、简单插入排序法2、希尔排序法三、选择类排序法思想：扫描整个线性表，从中选中最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法。1、简单选择排序法2、堆排序法以上各种查找方法中的一种的运算次数最大为n(n-1)/2次第二章 程序设计基础第一节 程序设计方法与风格一、程序设计方法(1)结构化程序设计方法(2)面向对

11、象程序设计方法二、程序设计风格指编写程序时所表现出的特点、习惯和逻辑思路。程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。即：清晰第一、效率第二第二节 结构化程序设计一、结构化程序设计的原则(1)自顶向下(2)逐步求精(3)模块化(4)限制使用goto语句二、结构化程序设计的基本结构与特点(1)顺序结构(2)选择结构(3)循环结构第三节 面向对象程序设计一、对象是系统中用来描述客观事物的一个实体，它由一组表示静态特征的属性和它可执行的一组操作组成。如：一辆汽车是一个对象，它包含了汽车的属性(颜色，型号)及其操作(启动，刹车)。一个窗口是一个对象，它包含了窗口的属性(大小，颜色，

12、位置)及其操作(打开，关系)特点：(1)分类性(2)多态性(3)封装性(4)模块独立性好二、类和实例:类是具有共同属性、共同方法的对象的集合。类是对象的抽象，而一个对象则是其对应类的一个实例。三、方法:对象所具有的操作。四、继承:是使用已有的类定义作为基础建立新类的定义技术。五、多态性:同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。第三章 软件工程基础第一节 软件工程基本概念一、软件定义与软件特点软件是包括程序、数据及相关文档的完整集合。包括：(1)机器可执行的程序与数据。(2)机器不可执行的，与软件开发、运行、维护、使用等相关的文档。特点：(1)软件是一种逻辑实体，不是

13、物理实体，具有抽象性。(2)软件的生产与硬件不同，没有明显的制作过程。一旦开发成功，可以大量拷贝。(3)软件在运行、使用期间不存在磨损与老化问题(4)软件的开发、运行对计算机系统有依赖性(5)软件复杂性高，成本昂贵二、软件危机与软件工程软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件工程的核心思想是把软件产品看作一个工程产品来处理。以期达到工程项目的三个基本要素：进度、经费和质量目标。三、软件生命周期将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。(1)可行性研究与计划制定(2)需求分析(3)软件设计(4)软件实现(5)软件测试(6)运行与维护可行

14、性研究初步项目计划需求分析概要设计详细设计实现调试使用维护退役定义阶段开发阶段维护阶段四、软件工程的目标在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可移植性和可互操作性且满足用户需求的产品。第二节 结构化分析方法一、需求分析与需求分析方法1、需求分析：指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析阶段的工作：(1)需求获取：确定对目标系统的各方面的需求(2)需求分析：对获取的需求进行分析与综合，最终给出系统的解决方案和目标系统的逻辑模型。(3)编写需求规格说明书(4)需求评审2、

15、需求分析方法(1)结构化分析方法(2)面向对象的分析方法二、结构化分析方法1、结构化分析方法的定义结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。步骤如下：(1)通过对用户的调查，获得当前系统的具体模型(2)根据具体模型，抽象出当前系统的逻辑模型(3)根据计算机的特点，建立目标系统的逻辑模型(4)写出目标系统的软件需求规格说明书(5)评审直到确认完全符合用户对软件的需求2、结构化分析的常用工具(1)数据流程图(DFDData Flow Diagram)数据流程图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示。数据流程图中的主要图形元素与说明如下： 加工(转换)：输入数据经

16、加工变换产生输出数据流存储文件(数据源)源，潭：表示系统和环境的接口，属系统之外的实体建立数据流程图的步骤：(1)由外向里(2)自顶向下(3)逐层分解帐卡检验出的问题检验取款存折取款单登录储户存折付款信息现金日历付款年月日银行取款业务的数据流程图(2)数据字典(DDData Dictionary)数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义。数据字典的作用是对DFD中出现的被命名的图形元素的确切解释。三、软件需求规格说明书1、作用：(1)便于用户、开发人员进行理解和交流(2)反映出用户问题的结构，可以作为软件开发工作的基础和依据(3)作为确认测试和验收的依据2

17、、内容(1)概述(2)数据描述：数据流程图，数据字典，系统接口说明，内部接口(3)功能描述：功能，处理说明，设计的限制(4)性能描述：性能参数，测试种类，预期的软件响应，应考虑的特殊问题第三节 结构化设计方法一、软件设计的概念1、从技术观点来看，软件设计包括：软件结构设计，数据设计，接口设计，过程设计。从工程管理角度来看，软件设计分两步：概要设计和详细设计。2、软件设计的基本原理(1)抽象(2)模块化(3)信息隐蔽(4)模块独立性内聚性：一个模块内各个元素间彼此紧密程度的度量耦合性：模块间互相连接的紧密程度的度量一般较优秀的软件设计，应尽量做到：高内聚，低耦合二、概要设计任务：(1)设计软件系

18、统结构：在需求分析阶段，已经把系统分解成层次结构，在概要设计阶段，需要进一步分解，划分为模块以及模块的层次结构。(2)数据结构及数据库设计(3)编写概要设计文档(4)概要设计文档评审三、详细设计任务：为软件结构图中的每一个模块确定实现算法的局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。第四节 软件测试一、软件测试的目的使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。测试要以查找错误为中心，而不是为了演示软件的正确功能。二、软件测试的准则(1)所有测试都应追溯到需求(2)严格执行测试计划，排除测试的随意性(3)程

19、序员应避免检查自己的程序(4)妥善保管测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。三、软件测试技术与方法从是否需要执行被测软件的角度分为：静态测试和动态测试按照功能划分：白盒测试与黑盒测试1、静态测试与动态测试(1)静态测试包括：代码检查，静态结构分析，代码质量度量等。静态测试不实际运行软件，由人工进行。(2)动态测试：是基于计算机的测试，是为了发现错误而执行程序的过程。设计高效、合理的测试用例是动态测试的关键。2、白盒测试方法与测试用例设计白盒测试也称结构测试或逻辑驱动测试。它是根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规格要求。白盒测试把测试对象看

20、成一个打开的盒子，允许测试人员利用程序内部的逻辑结构及有关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。原则：(1)保证所测模块中每一独立路径至少执行一次(2)保证所测模块所有判断的每一分支至执行一次(3)保证所测模块每一循环都在边界条件和一般条件下至少各执行一次(4)验证所有内部数据结构的有效性白盒测试是“穷举”路径测试。主要方法有逻辑覆盖、基本路径测试等。逻辑覆盖包括：语句覆盖，路径覆盖，判定覆盖，条件覆盖和判断条件覆盖。3、黑盒测试方法与测试用例设计黑盒测试也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部的逻辑结构

21、和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。黑盒测试只要诊断功能不对或遗漏、界面错误、数据结构或外部数据访问错误、性能错误、初始化或终止条件错误。主要方法有：等价类划分法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。四、软件测试的实施软件测试是保证软件质量的重要手段，分四个步骤：(1)单元测试(2)集成测试(3)验收测试(确认测试)(4)系统测试1、单元测试：是针对软件设计的最小单位模块进行正确性检验的测试。单元测试的目的是发现各模块内部存在的各种错误。单元测试可以采用静态分析和动态测试，动态测试以白盒测试为主，辅之以黑盒测试。2、集成测试集成

22、测试是测试和组装软件的过程。它是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。集成测试时将模块组装成程序通常采用两种方式：非增量方式组装与增量方式组装。非增量方式组装也称为一次性组装方式增量方式组装是将已经测试好的模块逐步组装成较大系统3、验收测试(确认测试)确认测试的任务是验证软件的功能和性能及其他特征是否满足了需求规格说明书中确定的各种需求，以及软件配置是否完全、正确。4、系统测试系统测试是将通过确认测试的软件，作为基于整个计算机系统的一个元素，与计算机硬件、外设、支持软件、数据和人员等其他系统元素组合在一起，在实际运行(使用)环境下对计算机系统进行一系列的集

23、成测试和确认测试。第五节 程序的调试程序调试的任务是诊断和改正程序中的错误。软件测试是尽可能多地发现软件中的错误。先要发现软件中的错误，然后借助于一系列的调试工具去执行找出软件错误的具体位置。软件测试贯穿于软件生命期，调试主要在开发阶段。程序调试由两部分构成：(1)根据错误的迹象确定程序中错误的确切性质、原因和位置。(2)对程序进行修改，排除这个错误。1、程序调试的基本步骤(1)错误定位(2)修改设计和代码，以排除错误(3)进行回归调试，防止引进新错误2、程序调试方法(1)强行排错法(2)回溯法(3)原因排除法第四章 数据库设计基础第一节 数据库系统的基本概念一、数据、数据库、数据库管理系统1

24、、数据(Data)：描述事物的符号记录2、数据库(DataBase)：是长期保存在计算机内，有组织、可共享的数据集合。3、数据库管理系统(DataBase Management System, DBMS)：是对数据库进行管理和维护的系统软件。功能：(1)定义数据库(2)操纵数据库(3)数据控制(完整性、安全性、并发控制)(4)故障恢复为了完成以上功能，DBMS提供了相应的语言：(1)数据定义语言(DDL):定义数据模式(2)数据操纵语言(DML)：查询,添加,删除,修改(3)数据控制语言(DCL)：负责数据完整性、安全性、并发控制以及故障恢复4、数据库管理员(DataBase Adminstr

25、ator,DBA)主要工作如下：(1)数据库设计(2)数据库维护(3)改善系统性能，提高系统效率5、数据库系统( DataBase System, DBS)数据库系统由以下几部分构成：(1)数据库(数据)(2)数据库管理系统(3)数据库管理员(4)硬件：计算机、网络(5)软件：操作系统，数据库系统开发工具，接口软件二、数据库系统的发展(1)人工管理阶段(2)文件系统阶段：数据共享性差、独立性差、冗余度大(3)数据库系统阶段：数据的共享性好、独立性强，冗余度小三、数据库系统的基本特点(1)数据的集成性(2)数据的高共享性与低冗余性(3)数据独立性强(4)数据统一管理与控制四、数据库系统的内部结构

26、体系1、数据库系统的三级模式应用A应用B应用C应用D应用E外模式1外模式2外模式3逻辑模式内模式数据库外模式/模式映像模式/内模式映像(1)逻辑模式：又称概念模式或模式。是数据库系统中全局数据逻辑结构的描述。是全体用户公共数据视图。此种描述是一种抽象的描述，它不涉及具体的硬件环境与平台，也与具体的软件环境无关。一个数据库系统只有一个逻辑模式。(2)外模式：又称子模式或用户模式。它是用户的数据视图，也就是用户见到的数据模式，由逻辑模式导出。一个概念模式可以有多个外模式。(3)内模式：又称物理模式。它给出了数据库物理存储结构与物理存储方法。2、数据库系统的两级映射(1)概念模式到内模式的映射(2)

27、外模式到概念模式的映射第二节 数据模型一、数据模型的基本概念数据库中的数据模型可以将复杂的现实世界要求反映到计算机数据库中的物理世界，这种反映是一个逐步转化的过程，它分两个阶段：由现实世界开始，经历信息世界而至计算机世界，从而完成整个转化。1、现实世界2、信息世界：通过抽象对现实世界进行描述所构成的逻辑模型。信息世界用概念模型表示，概念模型和具体的数据库管理系统无关，也和计算机平台无关。用E-R图表示：(1)实体集表示法：用矩形表示，在矩形内写上该实体集的名字。学生(2)属性表示法：用椭圆表示，在椭圆内写上该属性的名称。并用线段和对应的实体集连接起来。学号(3)联系表示法：用菱形表示，在菱形内

28、写上联系的名称。并用线段与有关实体集连接起来，同时在线段旁边标出联系的类型。联系也可能有属性，表示方法与实体集的属性表示方法相同。选修选修学生课程学号姓名性别年龄课程号课程名学分成绩mn3、计算机世界信息世界中的信息，经过处理形成计算机能够处理的数据，就是计算机世界(数据世界)。计算机世界用数据模型来表示。数据模型描述的内容分三个部分，又称为数据模型的三要素。即：数据结果，数据操作和完整性约束数据模型是一种面向数据库系统的模型，根据数据在数据库中的结构数据模型分为三种：(1)层次数据模型(2)网状数据模型(3)关系数据模型二、层次数据模型:层次数据模型的基本结构是树型结构(层次结构)。擅长表示

29、一对多联系，无法直接表示多对多联系。三、网状数据模型:网状数据模型的基本结构是消除了层次模型的限制。四、关系数据模型1、关系数据结构关系模型用二维表表示。有以下性质：(1)关系中元组均不相同元组的唯一性(2)元组的次序可以任意交换元组的次序无关性(3)元组分量是不可分的数据项元组分量的原子性(4)属性名各不相同属性名唯一性(5)属性次序可以任意交换属性的次序无关性(6)同一属性的数据具有相同的值域关系有关的名词：(1)元组：关系中的一行，也叫记录(2)属性：关系中的一列，也叫字段(3)属性的域：属性的取值范围(4)码：关系中能唯一标识元组的属性或数据组。(5)分量：某个元组的某个属性值成为分量

30、(6)关系模式：对关系的描述称为关系模式，表示方法为：关系名(属性名，属性名，)2、关系操作(1)数据查询(2)数据修改(删除，插入，修改)3、关系的完整性约束(1)实体完整性：主码不能重复(2)参照完整性：外码要么取空值，要么从与其对应的被参照关系的主码中取值。(3)用户自定义完整性：用户自己通过设置条件来进一步限制属性的取值范围。第三节 数据代数一、关系模型的基本操作关系是由若干元组组成，因此关系是元组的集合。关系操作是集合操作，关系操作的对象和结果都是关系。二、关系模型的基本运算1、并运算(插入新记录)RSR S2、差运算(删除记录)R-SR S3、交运算(把两个表中相同的记录取出)RS

31、=R-(R-S)R S4、投影运算：从关系中取出部分属性构成新的关系。A(R)5、选择运算：从关系中挑选出部分元组构成新的关系。F(R)F是选择的条件6、迪卡儿积运算：其实是一种不附加任何条件的连接运算RS7、连接运算8、自然连接(消除连接中的重复属性)第四节 数据库设计一、数据库设计概述数据库设计一般采用生命周期法,即将整个数据库应用系统的开发分解成若干阶段，即：需求分析阶段，概念设计阶段，逻辑设计阶段，物理设计阶段。需求分析概念设计逻辑设计物理设计需求说明书概念数据模型逻辑数据模型数据库内模式二、数据库设计的需求分析任务：通过详细调查现实世界要处理的对象，充分了解原系统的工作情况，明确用户的各种需求，然后在此基础上确定新系统的功能。三、数据库概念设计：用E-R图来表示数据的抽象模型。四、数据库的逻辑结构设计：主要工作是将E-R图转换成指定DBMS中的关系模式。五、数据库的物理设计：主要目标是对数据库内部物理结构作调整并选择合适的存取路径，以提高数据库访问速度及有效利用存储空间专心-专注-专业