[计算机二级公共基础知识知乎]计算机二级公共基础知识汇总

计算机二级公共基础知识汇总

计算机二级公共基础知识汇总 本文关键词：基础知识，汇总，计算机

计算机二级公共基础知识汇总 本文简介：1.1算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计

。

5、二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：

(1)前序遍历(DLR)：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树;并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

(2)中序遍历(LDR)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

(3)后序遍历(LRD)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

注释1：这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。

1.7

查找技术

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找结果：

平均查找长度：查找过程中关键字和给定值比较的平均次数。

1、顺序查找

基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。

在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n次。

顺序查找一个具有n个元素的线性表，其平均复杂度为O

1、结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化，限制使用goto语句。

性好；

；2）软件的生产与硬件不同，它没有明显的制作过程；3）软件在运行、使用期间不存在磨损、老化问题；4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；5）软件复杂性高，成本昂贵；6）软件开发涉及诸多的社会因素

软件需求规格说明书是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。

3.3

结构化设计方法

1、软件设计的基础：需求分析主要解决“做什么”的问题，而软件设计主要解决“怎么做”的问题。

从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。

结构设计：定义软件系统各主要部件之间的关系。

数据设计：将分析时创建的模型转化为数据结构的定义。

接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。

过程设计：把系统结构部件转换成软件的过程性描述。

从工程角度来看，软件设计分两步完成，即概要设计和详细设计。

概要设计：又称结构设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式。

详细设计：确定每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。

软件设计的基本原理包括：抽象、模块化、信息隐蔽和模块独立性。

1）抽象。抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。

2）模块化。解决一个复杂问题时自顶向下逐步把软件系统划分成一个个较小的、相对独立但又不相互关联的模块的过程。

3）信息隐蔽。每个模块的实施细节对于其他模块来说是隐蔽的。

4）模块独立性。软件系统中每个模块只涉及软件要求的具体的子功能，而和软件系统中其他的模块的接口是简单的。：模块分解的主要指导思想是信息隐蔽和模块独立性。

模块的耦合性和内聚性是衡量软件的模块独立性的两个定性指标。

内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。：按内聚性由弱到强排列，内聚可以分为以下几种：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚及功能内聚。

耦合性：是模块间互相连接的紧密程度的度量。：按耦合性由高到低排列，耦合可以分为以下几种：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合以及非直接耦合。

一个设计良好的软件系统应具有高内聚、低耦合的特征。

在结构化程序设计中，模块划分的原则是：模块内具有高内聚度，模块间具有低耦合度。

2、总体设计

软件概要设计的基本任务是：1）设计软件系统结构；2）数据结构及数据库设计；3）编写概要设计文档；4）概要设计文档评审。

常用的软件结构设计工具是结构图，也称程序结构图。程序结构图的基本图符：

模块用一个矩形表示，箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据信息。

经常使用的结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。其表示形式如下图：

它们的含义分别是：

传入模块：从下属模块取得数据，经处理再将其传送给上级模块。

传出模块：从上级模块取得数据，经处理再将其传送给下属模块。

变换模块：从上级模块取得数据，进行特定的处理，转换成其他形式，再传送给上级模块。

协调模块：对所有下属模块进行协调和管理的模块。

程序结构图的例图及有关术语列举如下：

深度：表示控制的层数。

上级模块、从属模块：上、下两层模块a和b，且有a调用b，则a是上级模块，b是从属模块。

宽度：整体控制跨度

注释1：单元是程序中最小的部分，由可以隐含的三部分组成：数据输入、加工和数据输出。

注释2：PDL

：过程设计语言，它是用正文形式表示数据和处理过程的设计工具。