公共基础知识[计算机理论]

Jayfar2020-03-112025-02-15

计算机系统公共基础知识

一、数据结构与算法

算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。
算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。
数据元素：数据元素是数据的基本单位。
数据对象：数据对象是性质相同的数据元素的集合。
数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。
数据的逻辑结构包括数据对象和数据对象之间的关系。
数据的存储结构包括数据元素的存储方式和关系的存储方式。
一种数据的逻辑结构可以表示成多种存储结构。
线性结构的条件（一个非空数据结构)：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
栈、队列、双向链表是线性结构；树、二叉树为非线性结构。
线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的存储结构：顺序存储结构（顺序表，图3a)）和链式存储结构（链表，图3b)）。
线性表的顺序存储结构有两个特点：
（1）线性表中所有元素所占的存储空间连续；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
线性表的链式存储结构存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。结点包含：数据域、指针域。（注：链式存储方式既可用于表示线性结构，也可用于表示非线性结构）。
栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
栈具有记忆功能，队列没有记忆功能。栈的特点是先进后出,后进先出,所以对一个栈进行出栈操作,出来的元素肯定是最后存入栈中的元素,所以栈有记忆功能。而队列是先进先出,取队列的第一个元素,得到的是最先存入队列的元素,而不是上一个存入队列的元素,所以没有记忆功能。
栈、队列的存储结构：
（1）顺序存储结构：用一组地址连续的存储单元即一维数组来存储；
（2）链式存储：线性链表。
计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。
树是个结点的有限集合，是一种非线性结构。
结点的度：结点所拥有的子树的个数。
叶子结点：度为0的结点。
分支结点：除叶子结点以外的结点。
结点的层次：根结点在第一层。
树的深度：所处层次最大的那个结点的层次。
树的度：树中所有结点的度的最大值。
二叉树每个结点最多只有两棵子树，且有左右之分，不能互换，二叉树有五种不同的形态。
在二叉树的第层上，最多有个结点。
深度为的二叉树最多有个结点。
在任意一棵二叉树中，度为的结点（叶子结点）总是比度为的结点多一个。
具有个结点的二叉树，其深度不小于，其中表示为的整数部分。
满二叉树：每一层上的结点数都达到最大值，即在满二叉树的第层上有个结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
具有个结点的完全二叉树的深度为。
完全二叉树中度为的结点数为或。
前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。
只能采用顺序查找：
（1）线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）有序线性表，如果采用链式存储结构，也只能用顺序查找。
二分查找的条件：
（1）用顺序存储结构，
（2）线性表是有序表。
对于长度为的有序线性表，在最坏情况下，二分法查找只需比较次，而顺序查找需要比较次。
排序算法
1、交换类排序
（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为。
（2）快速排序法，在最坏的情况下，快速排序需要比较次数为。
2、插入类排序：
（1）简单插入排序法，最坏情况需要次比较；
（2）希尔排序法，最坏情况需要次比较。
3、选择类排序：
（1）简单选择排序法，最坏情况需要次比较；
（2）堆排序法，最坏情况需要次比较。相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。

来源：http://data.biancheng.net/view/157.html

A结点的度为3，B结点的度为2，C结点的度为1，D结点的度为3，E、F、G、H、I 以及J度都为0，称为叶子结点.

https://blog.csdn.net/u010104750/article/details/49515553

二、程序设计基础

形成良好的程序设计风格需注意：
①源程序文档化；
②数据说明的方法；
③语句的结构；
④输入和输出。
⑤模块设计要保证低耦合、高内聚。
(内聚：每个模块尽可能独立完成自己的功能，不依赖于模块外部的代码。
耦合：模块与模块之间接口的复杂程度，模块之间联系越复杂耦合度越高，牵一发而动全身。)
结构化程序设计方法的四条原则：
①自顶向下；
②逐步求精；
③模块化；
④限制使用goto语句。
两类循环语句：先判断后执行的循环体称为当型循环结构；先执行循环体后判断的称为直到型循环结构。
面向对象的程序设计以对象为核心，强调对象的抽象性，封装性，继承性、多态性、（依赖性）。
对象的基本特点：
（1）标识惟一性；
（2）分类性；
（3）多态性；
（4）封装性；
（5）模块独立性好。
属性：即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。类：是具有相似属性与操作的一组对象。类是关于对象性质的描述。类是对象的抽象，对象是其对应类的一个实例。
消息：是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的组成包括：
（1）接收消息的对象的名称；
（2）消息标识符，也称消息名；
（3）零个或多个参数。
多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。
在软件设计过程中，必须遵循软件工程的基本原则：这些原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可靠性。
面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是，使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考。
字符常量是单引号括起来的一个字符，例如’a’，也可以通过转义序列表示方法表示一些不可显示字符或无法通过键盘输入的字符，例如’\n’的含义是换行。

三、软件工程基础

软件是包括程序、数据和相关文档的完整集合。分为应用软件和系统软件。
软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程。可分为软件定义，软件开发及软件维护3个阶段。
软件危机泛指在计算机软件的开发和维护过程中遇到的一系列严重的问题，集中表现在成本、质量、生产效率等几个方面。
软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程的主要思想强调在软件开发过程中需要应用工程化原则。软件工程的核心思想是把软件当作一个工程产品来处理。
软件工程3要素：方法，工具和过程。
软件工程过程是把软件转化为输出的一组彼此相关的资源活动，包含4种基本活动：
（1）P(plan)—软件规格说明；
（2）D(do)—软件开发；
（3）C(check)—软件确认；
（4）A(action)—软件演进。
软件工程的理论和技术性研究的内容主要包括软件开发技术和软件工程管理。
软件工程的原则：抽象，信息隐蔽，模块化，局部化，确定性，一致性，完备性，可验证性。
需求分析阶段的工作：需求获取，需求分析，编写需求规格说明书，需求评审。
需求分析方法：
（1）结构化需求分析方法：
①面向数据结构的Jackson方法（JSD）；
②面向数据流的结构化分析方法（SA）；
③面向数据结构的结构化数据系统开发方法（DSSD）；
（2）面向对象需求分析方法（OOA）：
①静态分析方法
②动态分析方法。
结构化方法包括结构化分析方法，结构化设计方法，结构化编程方法。结构化方法中，软件功能分解属于总体设计阶段。
结构化分析的常用工具： （1）数据流图（DFD-Data Flow Diagram）：
是结构化分析方法中用于系统逻辑模型的一种工具。它以图形的方式描绘在系统中流动和处理的过程。数据流图中四种基本的符号：
①【箭头】：表示【数据流】，数据流是数据在系统中传播的路径。 ②圆或椭圆：表示加工，加工又称为数据处理，是对数据流进行某些操作或变换。
③双横：表示数据存储（数据源）。数据存储又称为文件，指暂时保存的数据，它可以是数据库文件或任何形式的数据组织。
④方框：数据的源点或终点。它是软件系统外部环境中的实体，统称外部实体。

（2）数据字典（DD）：
它是结构分析方法的核心，是用来描述系统中所用到的全部数据和文件的文档,作用是对DFD中出现的被命名的图形元素进行确切解释。
数据字典由以下4类元素组成：
①数据流
②数据流分量
③数据存储
④处理

（3）判定树（决策树）：
是一种描述加工的图形工具，适合描述时候处理中具有多个判断，而且每个决策与若干条件有关。

（4）判定表：
与判定树类似，也是一种描述加工的图形工具。如果一个加工逻辑有多个条件、多个操作，并且在不同的条件组合下执行不同的操作，那么可以使用判定表来描述。
软件需求规格说明书（SRS，Software Requirement Specification）是需求分析阶段得出的最主要的文档。软件需求规格说明书的特点：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性。
软件需求规格说明书的作用：
①便于用户和开发人员进行理解和交流。
②反映出用户问题的结构，可以作为软件开发工作的基础和依据。
③作为确认测试和验收的依据。
软件设计是确定系统的物理模型。软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。
从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。
从工程管理角度来看，软件设计分两步完成：
（1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；
（2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。
软件设计的基本原理 ：
模块化、抽象化、信息隐藏和局部化（实现信息隐蔽依靠对象的封装）、模块独立性。
耦合性和内聚性
衡量软件的模块独立性的两个定性的度量标准。
耦合性：是对一个软件结构内不同模块之间互联程度的度量。耦合性的强弱取决于模块间接口的复杂程度。
内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。
一个模块的内聚性越强则该模块的模块独立性越强。一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。
在结构程序设计中，模块划分的原则是模块内具有高内聚度，模块间具有低耦合度。
耦合度由低到高：非直接耦合，数据耦合，标记耦合，控制耦合，外部耦合，公共耦合，内容耦合。
内聚性由强到弱：功能内聚，顺序内聚，通信内聚，过程内聚，时间内聚，逻辑内聚，偶然内聚。
概要设计的工具：结构图（SC-Structure Chart）也称程序结构图。
在结构图中：
矩形表示模块；
【箭头表示模块间的调用关系】；
带注释的箭头表示模块调用过程中来回传递的信息；
实心圆箭头表示传递控制信息;
空心圆箭心表示传递数据。

结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。
结构图有四种模块类型：传入模块、传出模块、变换模块和协调模块。
任何软件系统都可以用数据流图表示，典型的数据流类型有两种：变换型和事务型。
设计的准则
（1）提高模块独立性。
（2）模块规模适中。
（3）深度，宽度，扇出和扇入适当。
如果深度过大，则说明有的控制模块可能简单了，如果宽度过大，则说明系统的控制过于集中，扇出过大说明模块过分复杂，需要控制和协调过多的下级模块，应适当加中间层次，扇出过小可以把模块进一步分解成若干小模块，或合并到上级模块中，扇入越大则共享该模块的上级数目越多。好的软件设计结构通常顶层高扇出，中间扇出较少，底层高扇入。
（4）使模块的作用域在该模块的控制域内。
（5）减少模块的接口和界面的复杂性。
（6）设计成单入口，单出口的模块。
（7）设计功能可预测的模块。
详细设计常用的设计工具（工程设计工具）：图形工具，表格工具和语言工具。
图形工具：
程序流程图：【箭头表示控制流】，方框表示加工步骤，菱形表示逻辑条件。
N-S图（盒图）：有五种基本图形。
PAD图（Problem Analysis Diagram）：问题分析图，有五种基本图型。
表格工具：判定表。
语言工具：PDL—过程设计语言（结构化的英语和伪码）。
软件测试的目标：发现程序中的错误。
软件测试方法
1、静态测试和动态测试
①静态测试
包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。
②动态测试
通过运行软件来检验软件中的动态行为和运行结果的正确性。
2、白盒测试和黑盒测试
①白盒测试
也称为结构测试或逻辑测试，是把程序看成装在一只透明的白盒子里，测试者完全了解程序的结构和处理过程。它根据程序的内部逻辑来设计测试用例，检查程序中的逻辑通路是否都按预定的要求正确地工作。
白盒测试的方法：逻辑覆盖，基本路经测试。
②黑盒测试
也称功能测试或数据驱动测试，是把程序看成一只黑盒子，测试者完全不了解，或不考虑程序的结构和处理过程。它根据规格说明书的功能来设计测试用例，检查程序的功能是否符合规格说明的要求。
黑盒测试的方法：等价划分法，边界值分析法，错误推测法。
软件测试过程分4个步骤，即单元测试—>集成测试—>验收测试（确认测试）—>系统测试。
确认测试：检查软件产品是否符合需求定义。
程序调试是诊断（而非发现）和改正程序中的错误。
主要的调试方法有：
（1）强行排错法；（2）回溯法；（3）原因排除法，包括演绎法，归纳法和二分法。
结构化分析（属于需求分析方法）的常用工具：
①数据流图（DFD）
②数据字典（DD）
③判定树
④判定表
概要设计（开发阶段）的常用工具：
①系统结构图
详细设计（开发阶段）的常用工具：
①程序流程图
②N-S图（盒图）
③PAD图
④HIPO图

软件生命周期

数据流图4种基本符合

数据流图

数据字典中的符号

数据字典示例

判定表示例

判定树示例

程序结构图的基本图符

程序结构图中的专业术语

N-S图示例

—————————–2020-1-6——————————-

四、数据库设计基础

数据（Data）是数据库存储的基本对象，是描述事物的符号记录。
数据库（DB）是长期储存在计算机内、有组织的、可共享的大量数据的集合。
它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享，所以数据库技术的根本目标是解决数据共享问题。
数据库管理系统（DBMS）是数据库的管理机构，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心。数据库系统包含数据库和数据库管理系统。
数据库管理系统提供相应的数据语言：
数据定义语言（DDL）：负责数据模式定义和数据物理存取构建。
数据操纵语言（DML）：负责数据的操纵。
数据控制语言（DCL）：负责数据完整性，安全性的定义与检查以及并发控制，故障恢复等功能。
数据库系统（DBS）是指在计算机系统中引入数据库后的系统，一般由数据库、数据库管理系统、应用系统、数据库管理员和用户构成。
文件系统阶段的缺陷：
（1）数据冗余
（2）不一致性
（3）数据联系弱。
数据库系统的基本特点：
（1）数据的高集成性
（2）数据的高共享性和低冗余性
（3）数据高独立性
（4）数据统一管理与控制。
数据独立性是数据与程序间的互不依赖性，即数据库中的数据独立于应用程序而不依赖于应用程序。数据的独立性一般分为物理独立性与逻辑独立性两种。
（1）物理独立性：
当数据的物理结构（包括存储结构、存取方式等）改变时，其逻辑结构，应用程序都不用改变。
（2）逻辑独立性：
数据的逻辑结构改变了，如修改数据模式、增加新的数据类型、改变数据间联系等，用户的应用程序可以不变。
—————————–2020-1-7——————————-
数据库系统的三级模式
（1）外模式，外模式也称子模式，它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，一个概念模式可以有若干个外模式。
（2）概念模式，也称逻辑模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图。一个数据库只有一个概念模式。
（3）内模式，内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。一个数据库只有一个内模式。
内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。
两级映射保证了数据库系统中数据的独立性。
E-R模型
（1）实体的表示：用矩形表示实体集，在矩形内写上该实体集的名字。
（2）属性的表示：用椭圆形表示属性，在椭圆形内写上该属性的名称。
（3）联系的表示：用菱形表示联系，菱形内写上联系名。
关系模式采用二维表来表示，(数据模式）由关系数据结构，关系操纵和关系完整性约束3部分组成，在关系数据库中，用来表示实体间联系的是关系。
在二维表中惟一标识元组的最小属性值称为该表的键或码。
三类数据约束，它们是实体完整性约束、参照完整性约束以及用户定义的完整性约束。其中实体完整性约束、参照完整性约束必须满足的完整性约束条件。参照完整性约束不允许关系应用不存在的元组。实体完整性约束要求关系的主键中属性值不能为空，这是数据库完整性的最基本要求。
投影：一元运算，对一个关系进行垂直切割，消去某些列。
除：给定关系R（X，Y）和S（Y，Z），其中X，Y，Z是属性组，R中的Y和S中Y可以有不同的属性名，但必须出自相同的域集。
自然连接满足的条件是
（1）两关系间有公共域
（2）通过公共域的相等值进行连接。
数据库设计
①面向数据的方法是以信息需求为主，兼顾处理需求；
②面向过程的方法是以处理需求为主，兼顾信息需求。
由于数据在系统中稳定性高，数据已成为系统的核心，故面向数据的设计方法已成为主流。
数据库设计生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段。
规范化：一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合。
概念结构设计是将需求分析阶段得到的用户需求抽象为信息结构即概念模型的过程，它是整个数据库设计的关键。
逻辑结构设计的任务是将E—R图转换成关系数据模型的过程。
常用的存取方法：索引方法，聚簇方法和HASH方法。
数据库概念设计的过程中，视图设计一般有三种设计次序：
①自顶向下。这种方法是先从抽象级别高且普遍性强的对象开始逐步细化、具体化与特殊化。
②由底向上。这种设计方法是先从具体的对象开始，逐步抽象，普遍化与一般化，最后形成一个完整的视图设计。
③由内向外。这种设计方法是先从最基本与最明显的对象着手逐步扩充至非基本、不明显的其它对象。
分布式数据库系统具有数据分布性、逻辑整体性、位置透明性和复制透明性的特点。

来源：https://zhuanlan.zhihu.com/p/100698395