计算机二级公共基础知识复习必备.docx
《计算机二级公共基础知识复习必备.docx》由会员分享，可在线阅读，更多相关《计算机二级公共基础知识复习必备.docx（24页珍藏版）》请在冰点文库上搜索。
计算机二级公共基础知识复习必备
计算机二级公共基础知识（复习必备）
1算法的基本概念
1、算法一般应具有以下几个基本特征：
可行性、确定性、有穷性、拥有足够的情报。
算法是对解题方案的准确而完整的描述，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效和明确的，此顺序将在有限的次数下终止。
2、算法的基本要素
（1）算法中对数据的运算和操作。
通常有4类：
算术运算，逻辑运算，关系运算和数据传输。
（2）算法的控制结构。
算法的功能不仅仅取决于所选择的操作，还与操作之间的执行顺序及算法的控制结构有关。
3、算法设计基本方法
算法设计的基本方法有列举法、归纳法和递推法、递归法和减半递推技术。
4、算法的复杂度（在算法正确的前提下，评价算法的标准）
（1）算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。
（2）算法的空间复杂度
算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
一个算法所占的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
数据结构，直接影响算法的选择和效率。
而数据结构包括两方面，即数据的逻辑结构和数据的存储结构。
数据之间的相互关系称为逻辑结构。
通常分为4类基本逻辑结构，即集合、线性结构、树形结构和图状结构或网状结构。
存储结构图是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
存储结构在计算机有两种，即顺序存储结构和链式存储结构。
时间复杂度与空间复杂度之间没有必然的联系。
2数据结构基本概念
1、数据结构是指反映数据元素之间的数年据元素集合的表示。
2、所谓数据的逻辑结构，是指所映数据元素之间逻辑关系的数据结构。
数据的逻辑结构有两个要素：
一是数据元素的集合；二是数据元素之间的关系。
3、各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。
3线性表和线性链表
1、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系复杂程度，一般将数据结构分为两大类型：
线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点。
（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构不是线性结构，则称之为非线性结构。
如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字
2、线性表的基本概念
线性表是由n（n>=0）个数据元素
组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。
3、线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
线性表中所有元素所占的存储空间是连续的。
线性表中各数据元素在存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。
3、线性链表
大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。
在链式存储结构中，要求每个结点由两部分组成：
一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。
其中指针于指向该结点的前一个或后一个结点。
在链式存储结构称为线性链表。
一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。
栈和队列也是线性表，也可以采用链式存储结构。
4、线性链表的基本运算
线性链表的基本运算有：
在非空线性链表中寻找包含指定元素值X的前一个结点P，线性链表的插入，线性链表的删除。
5、循环链表及其基本运算
循环链表的结构与一般的单链表相比，具有以下两个特点：
（1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。
循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。
（3）在单链表中，增加头结点的目的是方便运算的实现。
（4）循环链表的主要优点是从表中任一结点出发都能访问到整个链表。
⑸线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构、顺序存取的存储结构
4栈和队列
栈是限定在一端进行插入与删除的线性表。
栈是按照“先进后出”或“后进先出”的原则组织数据的。
栈的运算、退栈运算、读栈顶元素。
队列是是允许在一端进行插入、而在另一端进行删除的线性表。
队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上环状空间，供队列循环使用。
循环队列的初始状态为空，即rear=front=m。
循环队列主要有两个基本运算：
入队运算和退队运算。
5树与二叉树
1、树的基本概念
树是一种简单的非线性结构。
树结构中，每一个结点只有一个前件，称为父结点。
在树中，没前件的结点只有一个，称为树的根结点，简称为树的根。
在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件个数称为结点的度。
树结构具有明显的层次关系，树是是一种层次结构。
根结点在第1层。
同一层上所有结点的所有子结点在下一层。
树的最大层次称为树的深度。
在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。
要树中，叶子结点没有子树。
2、二叉树的特点
（1）非空二叉树只有一个根结点；每一个结点最多有两个棵子树，且分别称为该结点的左子树与与右子树。
（2）在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树。
而树结构中的每一个结点的度可以是任意的。
另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。
在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。
当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。
3、二叉树的性质
（1）在二叉树的第K层上，最多有2k-1（k≥1）个结点。
（2）深度为m的二叉树最多有2m-1个结点。
（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。
4、满二叉树与完全二叉树
（1）满二叉树，除最后一层外，每一层上的所有结点都有两个子结点。
这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。
（2）完全二叉树。
除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1.
满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
具有n个结点的完全二叉树的深度为[log2n]+1。
5、二叉树的存储结构
二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：
数据域与指针域。
6、二叉树的遍历微信公众号：
高校学习墙
二叉树的遍历是指不重复地访问二叉树中的所有结点。
在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。
在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为3种：
前序遍历、中序遍历、后序遍历。
（1）前序遍历（DLR）。
所谓前序遍历是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
因此，前序遍历二叉树的过程是一个递归的过程。
（2）中序遍历（LDR）。
所谓中序遍历是首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
因此，中序遍历二叉树的过程也是一个递归的过程。
（3）后序遍历（LRD）。
所谓后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后右子树，最后访问根结点。
因此，后序遍历二叉树的过程也是一个递归的过程。
6查找技术
1、顺序查找
顺序查找又称顺序搜索。
顺序查找一般是指在线性表中查找指定的元素。
如果线性表中的第一个元素就是被查找的元素，则只需做一次比较就查找成功，最坏的情况是被查元素是线性表中的最后一个元素，或者被查元素在线性表中根本不存在，则为了查找这个元素需要与线性表中所有的元素进行比较。
平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。
2、二分法查找
二分法查找只适用于顺序存储的有序表。
设有序线性表的长度为n，被查元素为x，则对分查找的方法为：
将x与线性表的中间项进行比较，如果中间项的值等于x，则说明查到，查找结束；如果x小于中间项的值，则在线性表的前半部分以相同的方法进行查找；如果大于中间项的值，则在线性表的后半部分以相同的方法进行查找，这个过程一直进行到查找成功或子表长度为0（说明线性表中没有该元素）为止。
当有序线性表为顺序存储时才能采用二分查找，效率比顺序查找高得多。
对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较log2n次。
最简单的交换排序方法是冒泡排序法。
7排序技术
排序是指将一个无序序列整理成按值非递减顺序排序的有序序列。
1、交换类排序法
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。
冒泡排序法和快速排序法都属于交换类的排序方法。
（1）冒泡排序。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n-1）/2。
（2）快速排序。
快速排序法的基本思想为：
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分，T插入到分界线的位置处，这个过程称为线性表的分隔。
如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。
2、插入排序法
所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
（1）简单插入排序法。
在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。
在最坏情况下，简单插入排序需要n（n-1）/2次比较。
（2）希尔排序法。
希尔排序的效率与所选取的增量序列有关。
如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为O（n1.5）.
3选择类排序
（1）简单选择排序。
简单选择排序在最坏情况下需要比较n（n-1）/2次。
（2）堆排序。
在最坏情况下，堆排序需要比较的次数为O（nlog2n）。
4常见的排序方法有插入排序（包括简单插入排序法和希尔排序法等）、交换排序（包括冒泡排序和快速排序法等）和选择排序（包括简单选择排序和堆排序等）。
8程序设计方法与风格
1、源程序文档化
（1）符号的命名：
符号名应具有一定的实际含义，以便于对程序功能的理解。
（2）程序注释：
正确的注释能够帮助读者理解程序。
注释一般分为序言性注释和功能性注释。
（3）视觉组织：
为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。
2、数据说明的方法
数据说明的风格一般应注意：
数据说明的次序规范化；说明语句中变量安排有序化；使用释来说明复杂数据的结构。
3、语言结构
程序应简单易懂，语句构造应简单直接。
4、输入和输出
输入输出的方式和格式应尽可能方便用户的使用。
9结构化程序设计
1、结构化程序设计的原则
结构化程序设计方法的主要原则为自顶向下，逐步求精，模块化，限制使用goto语句。
（1）自顶向下：
程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；先从最上层总目标开始设计，逐步使问题具体化。
（2）逐步求精：
对复杂问题，应设计一些子目标作为过渡，逐步细化。
（3）模块化：
一个复杂问题，是由若干个简单问题构成的。
模块化是把程序要解决的总目标分解分目标，再进一步分解为具体的小目标，把每一个小目标称为一个模块。
（4）限制使用goto语句：
滥用goto语句有害，应尽量避免。
2、结构化程序的基本结构和特点
采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。
程序设计语言仅用顺序、选择、重复3种基本控制结构就可以表达出各种其他形式结构的程序设计方法。
（1）顺序结构：
顺序结构是顺序执行结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序。
（2）选择结构：
又称为分支结构，它包括简单选择和多分支选项择结构。
这种结构根据设定的条件，判断应该选择哪一条分支来执行相应的语句。
（3）重复结构：
又称循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。
重复结构有两类循环语句，先判断后执行循环体的称为当型循环结构，先执行循环后判断的称为直到型循环结构。
遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有的优点为：
其一，程序易于理解、使用和维护；其二，提高了编程工作的效率，降低了软件开发成本。
3、结构化程序的设计原则和方法的应用
在结构图化程序设计的具体实施中，要注意把握如下因素：
（1）使用程序设计语言的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。
（2）选用的控制结构只准许有一个入口和一个出口。
（3）程序语句组成容易识别的块，每块只有一个入口和一个出口。
（4）复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现。
（5）语言中所没有的控制结构，应该采用前后一致的方法来模拟。
（6）严格控制goto语句的使用。
10面向对象的程序设计
1、面向对象方法的主要优点
面向对象方法的主要优点为：
与人类习惯的思维方式一致；稳定性好；可重用性好；易于开发大型软件产品；可维护性好。
2、面向对象技术的基本概念
（1）对象。
面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
（2）类和实例。
类是具有共同属性、共同方法的对象的集合。
类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象是其对应类的一个实例。
类同对象一样，也包括一组数据属性和在数据上的一组合法操作。
（3）消息。
消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。
消息的使用类似于函数调用，消息中指定了某一个实例，一个操作和一个参数表。
（4）继承。
继承是使用已有的类定义作为基础建立新类的定义技术。
在面向对象技术中，把类组成具有层次结构的系统：
一个类的上层可以有父类，下层可以有子类；一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。
（5）多态性。
对象根据所接受的信息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。
更多资料关注微信公众号：
高校学习墙
（6）面向对象技术中包括以下几个基本概念，即对象、类、方法、消息、继承和封装，其中封装是一种信息隐蔽技术，目的在于将对象的使用者对象的和设计者分开。
11软件工程基本概念
1、软件及软件工程的定义
软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。
程序是软件开发人员根据用户需求开发的，用程序设计语言描述的、适合计算机执行的指令序列。
数据是使程序能正常操纵信息的数据结构。
文档是与程序开发、维护和使用有关的图文资料。
软件工程学是用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法的一门工程学科。
软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。
软件工程包括3个要素，即方法、工具和过程。
方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。
2、软件生命周期
软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。
一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。
还可将软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。
软件生命周期的主要活动阶段是：
可行性研究与计划指定、需求分析、软件设计、软件测试、运行和维护。
3、软件开发工具与软件开发环境
软件开发工具与软件开发环境的使用提高了软件的开发效率、维护效率和软件质量。
软件工程的出现是由于软件危机的出现。
软件开发离不开系统环境资源的支持，其中必要的测试数据属于辅助资源。
软件结构是以模块化为基础而组成的一种控制层次结构。
12结构化分析方法
1、需求分析与需求分析方法
软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。
需求分析的任务是发现需求、求精、建模和定义需求的过程。
需求分析阶段的工作，可概括为以下几方面：
需求获取、需求分析、编写需求规格说明书、需求评审。
常见的需求分析方法有结构化分析方法和面向对象的分析方法。
2、结构化分析方法
结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。
结构化分析方法是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。
结构化分析的常用工具有数据流图、数字字典、判断树、判断表。
（1）数据流图（DFD）。
数据流图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。
数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。
数据流图中的主要图形元素如下图。
第一个是加工（转换）；第二个是数据流；第三个是存储文件（数据源）；第四个是源（潭）。
建立数据流图的步骤：
由外向里，自顶向下，逐层分解。
（2）数据字典（DD）。
数据字典是结构化分析方法的核心。
数据字典是对所有与系统相关的数据元素的一个有组织的列表。
数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。
数据字典包含的信息有名称、别名、何处使用如何使用、内容描述、补充信息等。
（3）数据字典是各类数据描述的集合，它通常包括5个部分，即数据项，是数据的最小单位；数据结构，是若干数据项有意义的集合；数据流，可以是数据项，也可以是数据结构，表示某一处理过程的输入或输出；数据存储，处理过程中存取的数据，常常是手工凭证、手工文档或计算机文件；处理过程
3、软件需求规格说明书
软件需求规格说明书把在软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他与要求有关的数据。
13结构化设计方法
1、软件设计的基本概念
从技术观点来看，软件设计包括结构设计、数据设计、接口设计、过程设计。
从工程管理角度来看，软件设计分两步完全，即概要设计和详细设计。
2、软件设计的基本原理
衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。
耦合性是模块间互相联结的紧密程度的度量。
内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。
一般较优秀的软件设计，应尽量做到高内聚、低耦合。
3、概要设计
概要设计也称总体设计。
软件概要设计的任务是：
设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。
常用的软件设计工具为程序结构图。
典型的数据流类型有两种：
变换型和事务型。
设计准则：
提高模块独立性；模块规模适中；深度、宽度、扇入和扇出适当；使模块的作用域在该模块的控制域内；应减少模块的接口和界面的复杂性；设计成单入口、单出口的模块；设计功能可预测的模块。
4、详细设计
详细设计为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。
设计工具：
图形工具（程序流程图、N-S、PAD、HIPO）、表格工具（判定表）、语言工具（伪码）。
结构化程序设计主要强调的是程序易读性。
软件的过程设计是指系统结构部件转换成软件的过程描述。
软件设计模块化的目的是降低复杂性。
结构化分析方法主要包括：
面向数据流的结构化分析方法（SA-Structuredanalysis），面向数据结构的Jackson方法（JSD-Jacksonsystemdevelopmentmethod）和面向数据结构的结构化数据系统开发方法（DSSD-Datastructuredsystemdevelopmentmethod）。
14软件测试
1、软件测试方法和技术
软件测试是为了发现错误而执行程序的过程，其主要过程涵盖了整个软件生命期的过程。
若从是否需要执行被测软件的角度划分，软件测试方法和技术可以分为静态测试和动态测试方法。
若按照功能划分，可以分为黑盒测试和白盒测试。
（1）白盒测试
白盒测试方法也称结构测试或逻辑驱动测试。
白盒测试把测试对象看做一个打开的盒子，允许测试人员利用程序内部进行，主要用于完成软件内部操作的验证。
白盒测试的基本原则：
保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块中每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。
白盒测试的主要方法有逻辑覆盖、基本路径测试等。
（2）黑盒测试方法
黑盒测试方法也称功能测试或数据驱动测试。
黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。
黑盒测试在软件接口处进行。
黑盒测试主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。
黑盒测试的主要诊断方法有等价类划分法、边界分析法、错误推测法、因果图法等，主要用于软件确认测试。
2、软件测试的实施
软件测试一般按4个步骤进行，即单元测试、集成测试、确认测试和系统测试。
通过这些步骤的实施来验证软件是否合格，能否交付用户使用。
软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定；调试也称排错，它是一个与测试有联系又有区别的概念。
具体来说，测试的目的是暴露错误，评价程序的可靠性，而调试的目的是发现错误的位置，并改正错误。
15程序的调试
程序进行了成功的测试之后进入调试阶段，程序调试是诊断和改正程序中潜在的错误。
调试主要在开发阶段。
程序的调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位置。
二是对程序进行修改，排除错误。
程序调试的基本步骤为：
错误定位，修改设计和代码，进行回归测试。
软件调试的方法从是否跟踪和执行程序的角度，可分为静态调试和动态调试。
静态调试主要指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试的。
主要的调试方法为：
强行排错法，回溯法，原因排除法。
16数据库系统的
升级会员 