计算机国二office公共基础知识

第1章数据结构及算法(10-12分)

考点：

1.算法(****)

2.数据结构(***)

3.线性表及其依次存储结构(**)

4.栈和队列(*****)

5.线性链表(**)

6.树及二叉树(*****)

7.查找技术(****)

8.排序技术(***)

一，数据结构及算法

1,概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作

2,数据的逻辑结构

•线性结构(例：一维数组，链表，栈，队列，串，线性表)

•非线性结构(例：多维数组，广义表，树，图)

3,数据的存储结构(线性表)

•依次存储方法：线性表中全部元素所占的存储空间是连续的;线性表中各数据元素在存储空间中

是按逻辑依次依次存放的

•链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的

・计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系

•一种数据的逻辑结构依据须要可以表示成多种存储结构。数组是数据的逻辑结构，可以用多种存

储结构来表示

・线性链表：就是指线性表的链式存储结构，简称链表

4,算法的基本特征

•可行性：针对实际问题而设计的算法，执行后能够得到满足的结果

•确定性：算法中的每一个步骤都必需有明确的定义，不允许出现歧义性

•有穷性：算法必需在有限时间内做完，即必需在执行有限个步骤之后终止，算法程序的运行时间

是有限的

•拥有足够的情报：要使算法有效必需为算法供应足够的情报当算法拥有足够的情报时，此算法才

最有效的；而当供应的情报不够时，算法可能无效

5,算法的困难度

•时间困难度：该算法执行的时间耗费，是指执行算法所须要的计算工作量，即算法执行过程中所

须要的基本运算次数

•空间困难度：该算法执行时所耗费的存储空间

6,依次表和链表的比较：

基于空间的考虑：(1)依次表的存储空间是静态安排的，而链表的存储空间是动态安排的。(2)依次表

占的存储空间必需是连续的，而链表占的存储空间可以是连续的，也可是不连续的

I二，栈I

•栈实际也是线性表，只不过是一种特别的线性表。栈称为“先进后出”

表或“后进先出”表，依次存储，链式存储

•栈的计算：求栈中元素的个数：栈底元素一栈顶元素

•栈是限定在一端进行插入及删除的线性表，允许插入元素的一端为戌顶,

允许删除元素的一端为栈底，栈顶元素总是最终被插入的元素，也是最

先被删除的元素；栈底元素则总是最先被插入而最终被删除的元素

三，队列

•队列也是一种运算受限的线性表，是一种“先进先出”，“后进

后出”的线性表，依次存储，链式存储

•队列的计算：求队列中元素的个数：当rear>front时，rear

—front当rear<front时，rear-front+m

m（代表队列的容量）

•循环队列仍旧是依次存储结构，是队列常采纳的形式

•队列是一种线性表，它允许在一端进行插入，在另一端进行删

除

front：队头Rear：队尾

四，树及二叉树（非线性结构）出队—一入队

1,树

・节点：树中的每一个点叫做节点，分为根节点（0或1个），父节点，子节点

•度：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。度为1的

点节叫做nl,度为2的节点叫做1.2

・叶子节点：度为零的结点称为叶子（没有子节点的节点）叫做n0

•深度：树中结点的最大层数称为树的高度或深度

2,二叉树

•二叉树：由左树和右树组成，二叉树的度<=2,当度

为0时叫做空树

•具有3个结点的二叉树有5种形态

•满二叉树：指除最终一层外，每一层上的全部结点都

有两个子结点的二叉树

•完全二叉树：除最终一层外，每一层上的结点数均达

到最大值，在最终一层上只缺少右边的若

干结点

•二叉树的性质：

性质1：二叉树第k层上的结点数目最多为2kl（k>=l）

性质2：深度为m的二叉树至多有2*1-1个结点（k>=l）

性质3：度为2的结点数为n2,度为。的节点叫做nO,则

（度为0的节点比度为2的节点多一个），整个二叉树节

点个数：n=n0+nl+n2

性质4：具有n个结点的完全二叉树的深度至少为[log2n]+l,其中

[log2n]表示取log2n的整数部分

•二叉树的遍历：

遍历：是指沿着某条搜寻路线，依次对树中每个结点均做一次且仅做一次访问

（1）前序遍历：

访问根结点----左子树---右子树

（2）中序遍历：

左子树一一访问根结点一一右子树

（3）后序遍历：

左子树一一右子树一一访问根结点

例：前序：ABDEGCF

中序：DBGEACF

后序：DGEBFCA

五，排序

•冒泡排序：是最简单的一种交换类排序法。在最坏的状况下，对长度为n的线性表排序，冒泡排

序须要比较的次数为n(n-1)/2,其时间困难度为0(「)

•直接选择排序：最坏状况要比较的次数为0(一),其时间困难度为0(r)

•直接插入排序：最坏的状况下，时间困难度为0(一)

•快速排序：平均时间为0(nlog2Q,最坏状况下，时间效率为0(r)

•堆排序：最坏状况下，时间困难度为0(nlog2n)

各种内部排序方法的比较

排序方法最坏时间

直接插入0(n2)或n(n-l)/2

直接选择0(n2)或n(n-l)/2

冒泡0(n2)或n(n-l)/2

快速0(n2)或n(n-l)/2

堆0(nlog2n)

|六，杳找|

•依次查找：即适用依次存储结构，又适用链式存储结构。对长度为n的线性表进行依次查找，在

最坏状况下须要比较n次

•二分查找：要求线性表是有序表，另外，二分查找只适用依次存储结构，在链式存储结构上无法

实现二分查找

•二分法查找只适用于依次存储的有序表，在最坏状况下，二分查找须要比较log2n次

•在平均状况下，在依次存储的线性表中查询一个元素，须要一半的元素，在最坏状况下，则须要

比较线性表中全部的元素。

第2章程序设计基础(2-4分)

考点：

1.程序设计方法和风格(**)

2.结构化程序设计(**)

3.面对对象的程序设计(***)

程序设计方法及风格

1,程序设计

指设计，编制，调试程序的方法和过程

2,良好的设计风格：

(1)源程序文档化：程序注释的目的主要是便利其他人人阅读程序(程序中要有必要的注释)

(2)数据说明的方法：数据说明的次序要规范化，增加可读性(程序的可读性好)

(3)语句的结构：一行只写一条语句；避开运用临时变量；避开彩困难条件语句；应运用库函数；

程序模块化；确保模块独立；不要修补不良结构的程序，避开滥用goto语句

(4)输入输出：对输入数据检查合法性；排列合理；输入格式简单；应允许运用自由格式和默认值;

应在屏幕上给出状杰信息(输入数据前要有提示信息)

一模块设计要保证低耦合,高内聚

二，结构化程序丽

1,结构化程序设计的原则：

自顶向下，逐步求精，模块化及限制运用got。语句

2,结构化程序的基本结构：

依次，选择，循环结构

三，面对对象的程序设计

1,对象的特点：

标识唯一性，分类性，多态性，封装性，模块独立性好

(1)标识唯一性：对象是可以区分的

(2)分类性：具有相同属性和噪作的对象可以抽象成一个类

(3)多态性：同一个操作可以是不同对象的行为，是指在类中定义名称相同的函数，但是这些

函数的参数或者返回值的类型不同

(4)封装性：对外部只供应接口，便利用户调用，内部实现对外不可见，可实现信息隐藏，是

指将对象分为内部实现和外部接口两个部分

(5)模块独立性好：对象内部各种元素彼此结合紧密，内聚性好

2,类：

是具有共同属性，共同方法的一组对象的集合，是关于对象的抽象描述，反映属于该对象类型的全

部对象的性质，类是对象的抽象，而一个对象则是其对应类的一个实例

3,继承：

是指能够直接获得已有的性质和特征，而不必重复地定义它们

4,多态性：

对象依据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象

称为多态性

第3章软件工程基础(8分)

考卢•

1.软件工程基本概念(***)

2.结构化分析方法(**)

3.结构化设计方法(****)

4.软件测试(****)

5.程序的调试(**)

基本概念

•软件：包括程序，数据，文档的完整集合

•软件按功能分为：应用软件，系统软件，支撑软件

二，软件工程

・软程包含3个要素：方法，工具和过程

方法是完成软件开发各项任务的技术手段

工具支持软件的开发，管理，文档生成

过程支持软件开发的各个环的限制，管理

•软件工程探讨的主要内容是软件开发技术和软件开发管理两个方面。

•软件工程的原则：抽象，信息隐藏，模块化，局部化，确定性，一样性，完备性，可验

证性

抽象：采纳分层抽象，自顶向下，逐层细化的方法限制软件开发过程的困难性

信息隐藏：将模块设计成“黑箱”，实现的细微环节隐藏在模块内部。这就是信息封装，运

用及实现分别的原则

模块化：有助于信息隐藏和抽象，有助于表示困难的系统

局部化：保证模块之间具有松散的耦合关系，模块内部具有较强的内聚，这有助于限制分解

的困难性

确定性：软件开发过程中全部概念的表达应是确定的，无歧义的，规范的

可验证性：开发大型的软件系统须要对系统自顶向下，逐层分解，以确保系统的正确性

三，软件工程过程

•所进行的基本活动主要包含4种：软件规格说明，软件开发，软件确认，软件演进

软件规格说明：规定软件的功能以及运行的限制

软件开发：产生满足规格说明的软件

软件确认：确认能够满足用户提出的要求

四，软件生命而丽

•软件生存周期：通常把软件产品从提出，实现，运用，维护到停止运用，退役的过

程称为软件生命周期

・软件生命周期分为3个时期共8个阶段：

1.软件定义时期：包括问题定义，可行性和需求分析3个阶段

2.软件开发期：包括概要设计，具体设计，实现和测试4个阶段

3.运行维护期：即运行维护阶段

・软件生命周期各阶段的主要任务：

1.问题定义：

2.可行性探讨及安排制定：

3.需求分析：对待开发软件提出需求进行分析并给出具体定义。编写软件规格说

明书及初步的用户手册，提交评审。

4.软件设计：通常又分为概要设计和具体设计两个阶段，给出软牛的结构，模块

的划分，功能的安排以及处理流程。该阶段提交评审的文档有概要

设计说明书，具体设计说明书和测试安排初稿

5.软件实现：在软件设计的基础上编写程序。该阶段完成的文档有用户于册，操

作手册等面对用户的文档，以及为下一步做打算而编写的单元测试

安排

6.软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分

析报告

7.运行维护：

五，结构化分析方法

1,需求分析和需求分析方法

•1),需求分析阶段的工作：

•需求获得

•需求分析

•需求编写规格说明书

•需求评审

（2）,需求分析方法：

常用见的需分析方法：

（1）结构化分析方法

（2）面对对象的分析方法：分为静态分析方法和动态分析方法

2,结构化分析方法

运用数据流图（DFD）,数据字典（DD）,结构化英语，判定表和判定树等工具，实质是眼于数据

流，自顶向下，对系统的功能进行逐层分解，以数据流图和数据字典为主要工具，建立系统的逻

辑模型

3,结构化分析方法的常用工具

（1）数据流图（DFD）

•数据流图是描述数据处理过程的工具，它是结构化程序设计理论在软件需求分析阶段的

运用

•程序流程图，N-S图，PAD图是具体设计过程中常用的图形工具

数据流：

加工：（又称转换）

存储文件：。（又称数据源）

源/潭：（表示系统和环境的接口）

木木请留意：数据流图上......…一，1示的限制流有本质不同,T万不娈混淆

（2）数据字典：其中有4种类型的条目：数据流，数据项，数据存储，加工，对数据流图中全部

元素的定义的集合，是结构化分析的核心。它以一种打算的，无二义性的说明方式为系统的分

析，设计维护供应了有关元素的一样性定义和具体的描述。

4,软件需求规格说明书

软件需求规格说明书的标准：正确性，无歧义性，完整性，可验证性，一样性，可理解性，可

修改性，可追踪性

六，结构化设计方法

1,软件设计概述

（1）软件设计的基础：从工程管理的角度来看可分为两步：概要设计和具体设计。软件设计包括软

件结构设计，数据设计，接口设计，过程设计

•概要设计：将软件需求转化为软件体系结构

•具体设计：确立每个模块的实现算法和局部数据结构

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

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

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

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

（2）软件设计的基本原理和原则：

①模块化②抽象③信息隐藏④模块独立性

模块独立性：一般来说，要求模块之间的耦合尽可能弱，即模块尽可能独立，且要求模块的

内聚程度尽可能高。内聚性和耦合性是一个问题的两个方向，耦合性能程度弱

的模块，其内聚程序肯定高

内聚性：是一个模块内部包含的信息，对于不须要这些信息的其他模块来说是不能访问的；

是一个模块内部各个元素间彼此结合的紧密程序的度量

耦合性：是模块间相互连接的紧密程度的度量

对于模块进行设计时，应当尽量做到高内聚，低耦合，即减弱模块之间的耦和性和提高模

块的内聚性，这样有利于提高模块的独立性

2,概要设计

（1）编写概要设计文档：概要设计阶段文档有概要设计说明书，数据库设计说明书和集成测试安排

等。

（2）概要设计文档评审：在文档编写完成后，要对设计部分是否完整地实现了需求中规定的功能,

性能等要求，设计方案的可行性，关键的处理及内外部接口定义正确性，有效性，各部分之间

的一样性等进行评审。

3,具体设计

任务是为软件结构图中的每一个模块确实实现算法和局部数据结构

程序流程图（PFD）：

•方框表示一个加工步骤

•菱形表示一个逻辑条件

•箭头表示限制流

4,软件系统结构图的宽度：整体限制跨度（最大块数的层）下勺显示（如右图，宽度1

七，软件测试

1,软件测试目的

软件测试就是在软件投入运行之前，尽可能多地发觉软件中的错误,发觉程序中的错误

2,软件测试方法

依据软件是否须要被执行，可以分为静态测试和动态测试，假如依据功能划分，可以分为白盒测试和

黑盒测试

（1）静态测试：包括代码检查，静态结构分析，代码质量度量等，是指不在计算机上运行被测试

程序，而采纳其他手段来达到对程序进行检测的目的，包括人工测试和计算机协助

静态分析方法。

（2）动态测试：主要通过人工进行分析。通过运行软件来检验软件中的动态行为和运行结果的正确

性，并用所设计的测试用倒对程序进行检测的方法

（3）白盒测试（结构测试）：是把程序看成装在一只透亮的白盒子里，测试者完成了解程序的结构和

处理过程，保证所测模块中每一独立路径至少执行一次；保证所测模块

全部推断的每一分支至少执行一次；验证全部内部数据结构的有效性。

主要方法有逻辑覆盖，基本路径测试等。

（4）黑盒测试（功能测试）：把程序看成一只黑盒子，测试者完成不了解，或不考虑程序的结构和处

理过程，也称为功能测试或数据驱动测试，测试时不考虑程序内部细微

环节，结构和实现方式，仅检验程序结果及说明书的一样性。

测试方法主要有：等价划分法，边界分析法，错误推想法，因果图

等，主要用于软件确认测试

3,软件测试的实施

（1）单元测试：也称模块测试，模块是软件设计的最小单位，单元测试是对模块进行正确性的检验。

可以采纳静态测试或者动态测试，动态测试通常以白盒测试为主，测试其结构，以

黑盒测试法为辅，测试其功能

（2）集成测试：也称组装测试，它是对各模块依据设计要求组装成的程序进行测试，主要目的是发

觉及接口有关的错误

（3）确认测试的任务是检验软件的功能，性能及其他特征是否及用户的需求一样，它是以需求规格

说明书作为依据的测试。确认测试通常采纳黑盒测试

（4）系统测试：目的是在真实的系统工作环境下检验软件是否能及系统正确连接，发觉软件及系统

需求不一样的地方

•测试用例是为测试设计的数据，测试用倒由测试输入数据及之对应的预期输出结果两部分组成。

测试用倒的格式为[(输入值集)，(输出值集)]

八，程序的调试

程序调试的任务是诊断和改正程序中的错误，改正以后还须要再测试

第4章数据库设计基础(8T0分)

考点：

1.数据库系统的基本概念(*****)

2.数据模型(****)

3.关系代数(***)

4.数据库设计及管理(**)

一，数据库系统的基本概念

1,数据，数据库，数据库管理系统

(1)数据库(DB)

(2)数据库管理系统(DBMS)：

数据库语言：

•数据定义语言(DDL)：负货数据的模式定义和数据的物理存取构建

•数据库操纵语言＜DML)：负责数据的操纵，包括查询及增，删除，改操作

•数据限制语言：负责数据完整性，平安性的定义及检查以及并发限制，数据复原等功能

(3)数据库系统(DBS)

三者关系：DBS包含DB和DBMS

2,数据库系统的发展

(1),人工管理阶段：在工人管理阶段，数据不保存，没有对数据进行管理的软件，数据不能共享

(2),文件系统阶段：这个时期数据管理的特点是：数据须要长期保留在外存储器中供反复运用；

程序和数据之间有了肯定的独立性；文件夹形式已经多样化；数据的存储基本

上以记录为单位，供应了简单的数据共享及数据管理实力，但它不能供应完整

的，统一的管理和共享数据的实力

(3),数据库系统阶段：

•实现了数据共享，削减了数据冗余；

•采纳了特定的数据模型；

•真正统一的数据限制功能，能够为多个用户和应用程序供应共享资源

•具有数据的集成性

(4),分布式数据库系统阶段

3,数据库系统的基本特点

数据库管理系统是数据库系统的核心

数据库系统特点：

•数据高度集成

•数据统一管理限制

•数据独立性

•共享性及低冗余性

4,数据库系统的内部结构体系

•概念模式：是数据库系统中全局数据逻辑结构的描述，此种描述是一种抽象的描述，不但要描述

概念记录类型，而且要描述记录之间的联系，所允许的操作，数据的一样性，平安性和其他

数据限制方面的要求

•外模式：也称为数据库的用户式或子模式，是从概念模式导出的子模式，用户可以通过子模式描

述语言来描述用户级数据库的记录，还可以利用数据语言对这些记录进行操作。用户运用数据操

纵语言对数据库进行操作，事实上是对外模式的外部记录进行操作

•内模式：也称为数据库的物理式或存储模式。它是由系统程序员设计和组织的，是系统程序员

所看到和所理解的数据库，它给出了数据库物理存储结构及物理存取方法。DBMS一般供应相关的

内模式描述语言（DLL）

•数据库系统一般分为物理独立性及逻辑独立性两级。物理独立性指数据的物理结构的改变。在数

据系统中，数据的物理结构并不肯定及逻辑结构一样

概念模式是一个全局模式，而外模式是用户的局部模式，内模式处于底层，它反映了数据在计算机物

理结构中的实际存储形式，概念模式处于中层，它反映了设计者的数据全局逻辑要求，而外模式处于

最外层，它反映了用户对数据的要求

二，数据模型

•分为层次模型，网状模型，关系模型

•基本概念：一对一，一对多，多对多

•E-R模型：

矩形：实体集

椭圆：属性

菱形：联系

1,层次模型

层次模型的结构是树形结构

2,网状模型

用网状结构表示实体及其之间联系的模型

3,关系模型

•关系模型采纳二维表来表示，每行数据称为元组，列叫做属性

•关系模型允许定义三类数据约束，它们是实体完整性约束，参照完整性约束以及用户定义的完

整性约束

|三，关系代捌

1,传统的集合运算

并，交，差，笛卡尔积

（1））\（U）；由2个关系运算生成第3个关系，要求两个关系的元数（字段名称）必需相同，元组

（记录)的个数相加

例：RUS

RST

ABABAB

m113m1

n235n2

13

（2）交（H）：由2个关系运算生成第3个关系，：之求两个关，E的兀数（-。段名称）必需相1司，第3

个关系中只保留前2个关系中相同前35

——

例：RAS

RSI

ABABAB

m113n2

n2n2

（3）差（-）：由2个关系运算生.成笫3个关系，要求两个关系的元数（字段名称）必需相同，从笫1

个关系中减去第2个关系中相同的部分

例：R-S

RST

ABABAB

m113m1

n2n2

（4）笛卡尔积（X）：由2个关系运算生成第3个关系，两个关系中元数可以相同也可以不同，计算

的结果元数的个数是相加的关系，元组相乘的关系

例：RXS

RST

ABACABAC

111113ill113

n2n5m1n5