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

计算机二级公共基础知识重点计算机二级公共基础知识一，数据结构及算法1.1.1数据结构的基本概念数据结构指相互有关联的数据元素的集合。数据逻辑结构反映数据元素之间的逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，分为依次存储，链式存储，索引存储和散列存储4种方式。数据结构按各元素之间前后件关系的困难度可划分为如下两种：线性结构：有且只有一个根节点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构。非线性结构：不满意线性结构的数据结构。1. 1.2算法1 .算法的基本概念（1）概念：算法是指解题方案的精确而完善的描述。（2）基本特征：可行性，确定性，有穷性，拥有足够的情报。（3）基本要素：对数据对象的运算和操作，算法和限制结构。（4）设计的基本方法：列举法，归纳法，递推法，递归法，减半递推技术，回溯法。2 .算法的困难度（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 .列队及其基本运算队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表。队尾就是允许插入的一端，一般用尾指针指向队尾元素。排头就是允许删除的一端，一般用头指针指向头元素的前一位置。循环列队及其运算包括入队运算及退队运算。1.1.5树及二叉树1 .树的基本概念树是一种简单的非线性结构，树中有且仅有一个没有前驱的结点为“根”，其余结点互不相交的有限点分成m个互不相交的有限集合T1,T2,Tm,每个集合又是一棵树，称为T1,T2,m为跟结点的子树。（1）父结点：每一个结点只有一个前件，无前件的结点只有一个，称为树的根结点（2）子结点：每一个结点可以有多个后件，无后件的结点称为叶子结点。（3）树的度：所以结点最大的度（4）树的深度：树的最大层次。2 .二叉树及其基本性质二叉树是一种非线性结构，是有限的结点的集合，改集合为空或由一个根结点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树肯定是完全二叉树，但完全二叉树不肯定是满二叉树。二叉树具有如下特点：（1）二叉树可为空，空的二叉树无结点，非空二叉树有且只有一个根结点；（2）每个结点最多可有两棵子树，分别称为左子树和右子树。3 .二叉树的存储结构二叉树通常采纳链式存储结构，存储结点由数据域和指针域组成。对满二叉树和完全二叉树可按层次进行依次存储。4 .二叉树的遍历二叉树的遍历是指不重复地访问二叉树中所以结点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历分为前序遍历，中序遍历和后序遍历。1.1.6查找技术（1）依次查找：在线性表中查找指定的元素。（2）二分查找：这种查找只适用于依次存储结构的线性表，且必是有序表，应有二分查找时，会反复查找知道胜利或子表长度为O时结束。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结构化分析方法需求分析可概括为：需求获得，需求分析，编写需求规格说明书和需求评审。常用的分析方法如下:(I)结构化分析方法：实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，常用数据流图，数字字典，推断树和推断表等工具。(2)面对对象分析方法。1.3.3结构化设计方法1 .软件设计的基本概念和方法软件设计就是把软件需求转换为软件表示的过程。(1)基本原理：抽象，模块化，信息隐藏，模块独立性。(2)基本思想：将软件设计成有相对独立，单一功能的模块组成的结构。2 .概要设计(1)概要设计包括4个任务：设计软件系统结构，数据结构及数据库设计，编写概要设计文档，概要设计文档审评。(2)面对数据流的设计方法：数据流图的信息分为交换流和事物流,结构形式有交换型和事务型。3 .具体设计的工具（1）图形工具：程序流程图，N-S,PAD,HIPO。（2）表格工具：判定表。（3）语言工具：PD1（伪码）。1.3.4软件测试软件测试的目的是为了发觉错误，其相应的准则如下：（1）所以测试应追溯到用户需求。（2）严格执行测试安排，解除测试的随意性。（3）充分留意测试中的群集现象。（4）程序员应避开检查自己的程序。（5）穷举测试不可能。（6）妥当保存设计安排，测试用例，出错统计和最终分析报告。软件测试的方法从是否须要执行被测试软件的角度，可分为静态测试和动态测试，按功能可分为白盒测试和黑盒测试。（1）白盒测试：又称结构测试，是依据软件的内部逻辑设计和工作过程，检查软件内部成分。主要方法有逻辑覆盖测试，基本路径测试等。(2)黑盒测试：又称功能测试，是依据规格说明书的功能来设计测试的，主要方法有等价划分，边界值分析法，错误推想法，因果图发等。1. 3.5程序的调试程序调试的主要任务是诊断和改正程序中的错误，应用的主要方法有强行排错法，回溯法和缘由解除法。1.4数据库设计基础1.4.1 数据库系统的基本概念(1)数据：描述事物的符号记录，分为临时性数据和永久性数据。(2)数据库：长期存储在计算机内的，有组织的，可共享的数据集合。(3)数据库管理系统：负责数据库中：数据组织，数据操作，数据维护，限制及爱护和数据服务的一种系统软件。(4)数据库技术发展经验了人工管理阶段，文件系统阶段，数据库系统阶段等3个阶段。(5)数据库系统具有集成性，高共享性，低冗余性，数据统一管理及限制等特点。（6）三级模式（概念模式，内模式，外模式）和二级模式（外模式/概念模式的映射，概念模式/内模式的映射）构成了数据库系统内部的抽象结构体系。1.4.2 数据模型数据模型从抽象层次上描述了系统的静态特征，动态行为和约束条件，描述的内容包括数据机构，数据操作和数据约束。概念数据模型，逻辑数据模型和物理数据模型是数据模型的3个层次。（1） E-R模型：供应了表示实体，属性和联系的方法。实体及实体之间联系有“一对一”，“一对多”和“多对多”。（2）层次模型：利用树形结构表示实体及其之间的联系，其中结点是实体，树枝是联系，从上到下是一对多的关系。（3）网状模型：用网状结构表示实体及其之间的联系，是层次模型的扩展。网状模型以记录型为结点，反映现实中较为困难的事物联系。（4）关系模型：采纳二维表来表示，可进行数据查询，增加，删除及修改等操作。关系模型允许定义“实体完整性”，“参照完整性”和“用户定义的完整性”3种约束。1 .键：二维表中唯一能标识元祖的最小属性集。2 .候选键：二维表中可能有点全部的键。3 .主键：从二维表全部键中被取出的一个作为用户运用的键。1.4.3 关系代数（1）传统的集合运算包括关系并运算，关系交运算，关系差运算和广义笛卡尔积，（2）特地的关系运算包括选择，投影和连接。1.4.4 数据库设计及管理1 .数据库设计概述数据库的设计一般以过程迭代和逐步求精为基本思想，是应用面对数据的方法和面对过程的方法进行的数据库的设计步骤如下：需求分析一概念设计一逻辑设计一物理数据一编码一测试一运行一进一步修改2 .数据库设计的需求分析需求收集和分析师数据库设计的第一阶段。在这一阶段常用结构化分析方法和面对对象的方法，其主要工作有绘制数据流程图，数据分析，功能分析，确定功能处理模块