计算机二级公共知识部分

1、计算机辅助公共知识部分对解决问题的方法的准确完整的说明称为算法。算法分析的目的是分析并提高算法的效率。算法的基本特征是具有可行性、确定性、贫穷和充分的信息。算法的贫乏意味着算法程序的执行时间有限。算法的复杂性分为时间复杂性和空间复杂性。时间复杂度代表执行演算法所需的工作负载计算。算法的空间复杂性指示运行算法所需的“存储空间”。算法的时间复杂性或空间复杂性中的一个值没有办法给出另一个值。2、数据结构数据结构分为逻辑结构和存储结构。线性结构和非线性结构属于逻辑结构。顺序、链和索引属于存储结构(物理结构)。循环队列属于存储结构。数据的存储结构，也称为物理结构，是数据在计算机存储空间中的逻辑结构的存档

2、形式。一个逻辑结构可以有多个存储结构，不同的存储结构会影响数据处理的效率。程序执行的效率与数据的存储结构密切相关。数据结构分为线性结构和非线性结构，带链的队列属于线性结构。线性表的存储结构主要分为顺序存储结构和链存储结构。顺序存储结构中的存储必须是连续的，链存储中的存储空间不必是连续的。有序线性表既可以使用顺序存储结构，也可以使用链存储结构。队列是根据“先进先出”原则组织数据的特殊线性表。循环队列是队列的“顺序”存储结构。数据的独立性分为物理独立性能和逻辑独立。基于逻辑结构的应用程序不需要修改(称为物理独立性)，因为数据的存储结构发生更改时，逻辑结构可能不会发生更改。3、堆栈和队列堆栈是一种特

3、殊的线性表，只能在一端插入和删除，它的特征是最先插入(FILO)。堆栈是“高级后退出”的线性表。栈有记忆效果。在堆栈的插入和删除操作中，不需要更改“堆栈底部的指针”。如果元素1、2、3、a、b依次移动到堆栈，则堆栈的顺序为b、a、3、2、1。栈和队列都是线性结构，树是非线性结构。支持子程序调用的数据结构是“堆栈”。堆栈和队列的共同点是只能在端点插入和删除元素。堆栈可以按顺序存储的说明无效。堆栈可以存储“顺序和链”。队列是可以在一个段中插入，在另一端删除的线性表，其特征是“先进先出”。循环队列中的元素数由团队头指针和团队尾指针确定。如果循环队列的头指针为front，尾指针为rear，容量为max

4、Size，则循环队列中的元素数为(rear-front maxSize)mod maxSize。4、线性链接列表线性链接列表是线性表的链存储结构。使用关联列表表示线性表的优点是“插入和删除操作方便”。线性链接表的存储空间不连续，个元素的存储顺序是随机的。5、树和二进制树树结构中一个节点拥有后(下一个)的数目称为该节点的度，所有节点中最大的程度称为树度。二叉树中的每个节点的程度只能接受值0、1和2，不能是其他值。也就是说，如果知道叶节点或度为2的节点之一，前提是度为1节点数，那么就可以找到节点总数。节点数量计算的一些特性包括：(1)任意二叉树、叶节点数、度为2的节点数至少一个(即已知叶节点数、减

5、法1是度为2的节点数；已知节点数2和1是叶节点数)(2)如果有N个完整的二进制树节点，则N为奇数的叶节点数为(N 1)/2，二进制树中只有0度的叶节点和2度的节点，没有1度的节点。如果N是偶数，则叶节点数为N/2。(注意条件必须是完整的二进制树，当然还包括完整的二进制树)(3)整个二叉树k层的节点数为2k-1；深度为k的二叉树，节点总数为2K-1。上述计算公式是深度为7的整个二叉树，度为2的节点数是多少？由于满是二叉树，叶节点数为第7层的节点数，即26，可以计算叶节点64，因此图2的节点数为63(叶节点数减去1)。二进制树的初始顺序遍历，中间顺序遍历，后续遍历：前三个词相对于根，前三个词为根-

6、左-右，中间顺序为左-根-右，然后是左-右-根。具体操作包括：要访问根节点，请首先导航到(D L R):然后导航到左侧子树，最后导航到右侧子树。中间顺序遍历(L D R):按中间顺序遍历左侧子树，访问根节点，按中间顺序遍历右侧子树。反向遍历(L R D):反向遍历左侧子树，反向遍历右侧子树以访问根节点。以下以中间顺序遍历为例说明，对一棵树，用椭圆圈住根部下的左子树，右子树也用椭圆圈住，就可以了。然后在左侧的子树中显示1，在根节点中显示2，在右侧的子树中显示3。对于左侧椭圆内的左侧子树，现在单独取出并分析。将左侧子树显示为圆形1.1、根节点标记1.2和右侧子树标记1.3。可以按照上述方法向下移动

7、树，直到树无法拆分，然后按照从左到右的顺序构建节点的访问顺序。6、寻找技术对于长度为n的线性表，最坏的情况下要比较n次。对数据是否排序没有要求。顺序查找最好的情况下，查询数为1，最坏的情况下为n，平均值(1 n)/2。对于长度为n的有序宣城表，如果二分法最坏，则只比较log2n次。(数据必须有顺序)可以用二分法查找的是按顺序存储的线性表。7、对齐技术气泡排序、快速排序、简单插入排序、简单选择排序最差情况下比较次数相同的n(n-1)/2。堆排序效率最高。nlog2n。跟部对齐最差的情况需要子比较n1.5。跟部排序属于“插入类排序方法”。数据表a中的每个元素都知道离最终位置不远，因此为了节省时间，

8、应使用的算法是“直接插入排序”。排序、插入排序、快速排序、合并排序的最大内存要求是“合并排序”。第二部分软件工程基础(历年27%)1，软件工程基本概念软件是包含逻辑产品程序、数据和相关文档的完整集合。软件工程的三个要素是方法、工具和过程，其中过程支持软件开发各个方面的控制和管理。软件工程的核心思想：强调将软件产品视为工程产品，在软件开发过程中应用工程原则。在工程管理方面，软件设计通常分为两个阶段：摘要设计和详细设计。软件生命周期通常是定义阶段、开发阶段和维护阶段，编码和测试属于开发阶段。需求分析阶段生成的主要文档是软件需求规格指南。软件要求的规格说明必须具有完整性、无歧义、准确性、可验证性、可

9、修改性等特征，其中最重要的是准确性。2、结构分析和设计需求分析的分配如下：结构化需求分析方法，面向对象分析方法。DFD是需求分析阶段可用的工具之一。结构分析常用工具：数据流程图(DFD)；数据预决策树；判定表。在结构化分析中使用数据目录(DFD)时，请使用“数据字典”以准确解释图形元素。数据字典是结构分析的核心。常见的数据流类型有两种：交换和事务处理。典型的流程设计工具包括图形工具(流程图、N-S、pad、HIPO)、表格工具(决策表)和语言工具(PDL伪代码)。衔接是模块内的联系，耦合模块之间的相互联系有多紧密。目标是模块的凝聚力要高，模块之间的耦合程度要最小化。高凝聚力低耦合。程序流程图中

10、带有箭头的段表示“控制流”。平行四边形表示输入输出，矩形表示处理，菱形表示判断。请注意，数据流图中的箭头表示数据流。符合结构原则的三种基本控制结构是“顺序结构”、“选择结构”和“循环结构”。3、软件测试和维护软件测试的目的是找到尽可能多的程序中的错误，但不包括更正错误。(软件调试的目的是更正错误)软件测试分为静态测试和动态测试。其中，“静态测试”是指只检查程序文本，而不运行程序。软件的动态测试主要包括“黑盒测试”和“白盒测试”。黑盒测试方法有等效类划分方法、边值分析、误差估计方法、因果图；白盒测试的主要方法是逻辑覆盖，基本路径测试。考试的时候给方法命名，你要知道是白盒还是黑盒白盒测试的原则之一

11、是确保被测试模块的每个单独路径至少运行一次。白盒测试将程序视为路径集合。软件测试通常按照四个阶段进行：单元测试、集成测试、验收测试和系统测试。集成测试应在单元测试后进行。模块测试要求为测试的每个模块设计“驱动模块”和“执行模块”。驱动器模块的作用是将测试的数据传递到测试的模块并显示结果。测试用例是为目标准备的一系列测试输入、执行条件和预期结果。测试用例包含输入值集和输出值集。诊断和修复程序中的错误称为“程序调试”或“软件调试”，通常称为Debug。软件调试可以分为“静态调试”和“动态调试”。使用软件后修改软件以更正错误或满足新需求的过程称为软件维护。软件维护不是软件生命周期(开发阶段)的任务。

12、第三部分数据库设计基础(历年24%)1，数据库系统基本概念数据库设计的基本目标是解决“数据共享问题”。数据库管理技术开发的三个阶段中，数据共享的最佳方法是数据库系统阶段。数据独立性的最高阶段是数据库系统阶段。数据库系统和文件系统的区别在于特定的数据模型。数据库系统的典型数据模型有层次模型、网络模型和关系模型。数据库系统的核心是数据库管理系统。 DBS包含DB和DBMS。总体上，数据库系统DBS由数据库DB、数据库管理系统DBMS、数据库管理员DBA、硬件平台和软件平台组成。数据库应用系统的核心是数据库维护。数据库系统的三阶段模式结构：内部模式是最低的，反映了数据在计算机物理结构中的实际存储形式

13、。概念模型是展示设计者数据全局逻辑要求的中间层，与硬件和软件环境无关。外部模式最外部，反映了用户对数据的需求。用户在数据库系统上看到的数据模式为外部模式。数据库设计的四个阶段是需求分析、概念设计、逻辑设计和物理设计。将E-R图形转换为关系数据模型属于逻辑设计阶段。数据库管理系统提供的数据语言：数据定义语言DDL、数据操纵语言DML、数据控制语言DCL。SQL的全名是structured query language，中文的意思是Structured Query Language。2、数据模型实体之间的关联以树状结构表示的模型是层次模型。二维表表示关系模型。在关系数据库中，数据表示为二维表，每个

14、二维表称为关系。在关系数据库中，用于表示实体之间的联系的是关系。将E-R图转换为关系模式，对象和关联都可以用关系表示。选择“实体a”以查看两个实体之间是否存在一对一、一对多或多对多(两个或多个实体b是否匹配)。要确定多个图元a是否对应，请选择图元b。例如，学生学习过程中的两个团体，学生和课程，一个学生可以学习多门课程，一个课程可以由多个学生学习，所以两者都是多对多的关系。在E-R图中，用于表示实体的图形为“矩形”。用于表示属性的图形是椭圆。用菱形表示联系。关系表中的行称为元组(或记录)，列称为属性或字段。在二维表中，元组的“组件”不能再分割成较小的数据线。要建立关系，首先要建立数据的逻辑关系。

15、3、关系代数在交叉、差、投影中，关系表中的属性数不变，但可以减少元组数的是交叉运算。关系运算法则(下面介绍的7种运算一般在考试时要考察并记住一件事)(1)和rs:运算是两个表行的合并，重复行只出现一次。(2)运算rs:运算是在两个表中选择公共行。(3)减法R-S:减法运算从表格R中移除同时出现在R和S中的列。(4)选择运算：二维表部分的行称为选择运算。(5)投影运算：选取称为投影运算的二维表格部分的栏。(6)连接操作：根据两个表中的公共属性值连接公共属性，而不删除公共属性。如果删除了重复的属性，则称为自然连接。(7)笛卡尔产品：将关系r的每一行与关系s的每一行按顺序组合。注意：其馀元计算需要两

16、个表(两个关系)，但选择和投影操作具有单个表的情况除外。其中，对于运算、交叉运算和差异运算，两个关系r和s必须具有相同数量的属性。第四部分基于编程(历年8%)总体编程原则：明确性1，效率2。好的程序样式包括记录源代码，标准化数据描述的顺序，以避免滥用goto语句。结构化编程的核心是算法，面向对象的核心是对象(类)。结构化编程的基本原理是“自上而下”、“逐步细化”、“模块化”和“限制使用古文字”。类是与相同属性具有相同作业的对象集的集合。在面向对象的模型中，最基本的概念是对象和类。在面向对象的方法中，类的实例称为“对象”，信息隐藏是通过对象的包实现的。面向对象的功能包括抽象、包、继承和多态。继承提高了软件的可重用性。对象是“属性和方法”的程序包，对象之间的通信由“消息传送”执行，操