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

第1章 数据结构与算法（10-12分）
考点：
1. 算法(****)
2. 数据结构(***)
3. 线性表及其顺序存储结构(**)
4. 栈和队列(*****)
5. 线性链表(**)
6. 树与二叉树(*****)
7. 查找技术(****)
8. 排序技术(***)

一、数据结构与算法
1、概念
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
2、数据的逻辑结构
l 线性结构(例：一维数组、链表、栈、队列、串、线性表)
l 非线性结构(例：多维数组、广义表、树、图)
3、数据的存储结构(线性表)
l 顺序存储方法：线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
l 链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的
l 计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系
l 一种数据的逻辑结构根据需要可以表示成多种存储结构。数组是数据的逻辑结构，可以用多种存储结构来表示
l 线性链表：就是指线性表的链式存储结构，简称链表
4、算法的基本特征
l 可行性：针对实际问题而设计的算法，执行后能够得到满意的结果
l 确定性：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性
l 有穷性：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止，算法程序的运行时间是有限的
l 拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效
5、算法的复杂度
l 时间复杂度：该算法执行的时间耗费，是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数
l 空间复杂度：该算法执行时所耗费的存储空间
6、顺序表和链表的比较：
基于空间的考虑：(1)顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。(2)顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的

栈顶 top
A
B
C
D
栈底 bottom
入栈
出栈
二、栈
l 栈实际也是线性表，只不过是一种特殊的线性表。栈称为“先进后出”表或“后进先出”表，顺序存储、链式存储
l 栈的计算：求栈中元素的个数：栈底元素—栈顶元素
l 栈是限定在一端进行插入与删除的线性表，允许插入元素的一端为栈顶，允许删除元素的一端为栈底，栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素则总是最先被插入而最后被删除的元素

三、队列
l 队列也是一种运算受限的线性表，是一种“先进先出”，“后进后出”的线性表， 顺序存储、链式存储
l 队列的计算：求队列中元素的个数：当rear>front时, rear—front 当rear<front时，rear-front+m m(代表队列的容量)
l 循环队列仍然是顺序存储结构，是队列常采用的形式
入队
出队
Rear：队尾
front：队头
l 队列是一种线性表，它允许在一端进行插入，在另一端进行删除

四、树与二叉树（非线性结构）
1、树
l 节点：树中的每一个点叫做节点，分为根节点(0或1个)、父节点、子节点
A
B
C
G
D
E
F
树
l 度：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。度为1的点节叫做n1，度为2的节点叫做n2
l 叶子节点：度为零的结点称为叶子（没有子节点的节点） 叫做n0
l 深度：树中结点的最大层数称为树的高度或深度
2、二叉树
A
B
C
D
E
G
F
二叉树
l 二叉树：由左树和右树组成，二叉树的度<=2 ,当度
为0时叫做空树
l 具有3个结点的二叉树有5种形态
l 满二叉树：指除最后一层外，每一层上的所有结点都
有两个子结点的二叉树
A
B
C
D
E
F
G
满二叉树
l 完全二叉树：除最后一层外，每一层上的结点数均达
到最大值，在最后一层上只缺少右边的若
干结点
A
B
C
D
E
F
完全二叉树
l 二叉树的性质：
性质1：二叉树第k层上的结点数目最多为2k-1(k>=1)
性质2：深度为m的二叉树至多有2m-1个结点(k>=1)
性质3：度为2的结点数为n2，度为0的节点叫做n0，则n0=n2+1（度为0的节点比度为2的节点多一个），整个二叉树节点个数：n=n0+n1+n2
性质4：具有n个结点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分
l 二叉树的遍历：
遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问
（1）前序遍历：
A
B
C
D
E
G
F
访问根结点——左子树——右子树
（2）中序遍历：
左子树——访问根结点——右子树
（3）后序遍历：
左子树——右子树——访问根结点
例：前序：ABDEGCF
中序：DBGEACF
后序：DGEBFCA

五、排序
l 冒泡排序：是最简单的一种交换类排序法。在最坏的情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2，其时间复杂度为O(n2)
l 直接选择排序：最坏情况要比较的次数为O(n2) ，其时间复杂度为O(n2)
l 直接插入排序：最坏的情况下，时间复杂度为O(n2)
l 快速排序：平均时间为O(nlog2n)，最坏情况下，时间效率为O(n2)
l 堆排序：最坏情况下，时间复杂度为O(nlog2n)
各种内部排序方法的比较
排序方法
最坏时间
直接插入
O(n2) 或 n(n-1)/2
直接选择
O(n2) 或 n(n-1)/2
冒 泡
O(n2) 或 n(n-1)/2
快 速
O(n2) 或 n(n-1)/2
堆
O(nlog2n)

六、查找
l 顺序查找：即适用顺序存储结构，又适用链式存储结构。对长度为n的线性表进行顺序查找，在最坏情况下需要比较n次
l 二分查找：要求线性表是有序表，另外，二分查找只适用顺序存储结构，在链式存储结构上无法实现二分查找
l 二分法查找只适用于顺序存储的有序表，在最坏情况下，二分查找需要比较log2n次
l 在平均情况下，在顺序存储的线性表中查询一个元素，需要一半的元素，在最坏情况下，则需要比较线性表中所有的元素。

第2章 程序设计基础（2-4分）
考点：
1. 程序设计方法和风格(**)
2. 结构化程序设计(**)
3. 面向对象的程序设计(***)

一、程序设计方法与风格
1、程序设计
指设计、编制、调试程序的方法和过程
2、良好的设计风格：
（1）源程序文档化：程序注释的目的主要是方便其他人人阅读程序（程序中要有必要的注释）
（2）数据说明的方法：数据说明的次序要规范化，增强可读性（程序的可读性好）
（3）语句的结构：一行只写一条语句；避免使用临时变量；避免彩复杂条件语句；应使用库函数；程序模块化；确保模块独立；不要修补不良结构的程序，避免滥用goto语句
（4）输入输出：对输入数据检查合法性；排列合理；输入格式简单；应允许使用自由格式和默认值；应在屏幕上给出状态信息（输入数据前要有提示信息）
**模块设计要保证低耦合、高内聚
二、结构化程序设计
1、结构化程序设计的原则：
自顶向下、逐步求精、模块化及限制使用goto语句
2、结构化程序的基本结构：
顺序、选择、循环结构

三、面向对象的程序设计
1、对象的特点：
标识唯一性、分类性、多态性、封装性、模块独立性好
（1）标识唯一性：对象是可以区分的
（2）分类性：具有相同属性和操作的对象可以抽象成一个类
（3）多态性：同一个操作可以是不同对象的行为，是指在类中定义名称相同的函数，但是这些函数的参数或者返回值的类型不同
（4）封装性：对外部只提供接口，方便用户调用，内部实现对外不可见，可实现信息隐蔽，是指将对象分为内部实现和外部接口两个部分
（5）模块独立性好：对象内部各种元素彼此结合紧密，内聚性好
2、类：
是具有共同属性、共同方法的一组对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质，类是对象的抽象，而一个对象则是其对应类的一个实例
3、继承：
是指能够直接获得已有的性质和特征，而不必重复地定义它们
4、多态性：
对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性

第3章 软件工程基础（8分）
考点：
1. 软件工程基本概念(***)
2. 结构化分析方法(**)
3. 结构化设计方法(****)
4. 软件测试(****)
5. 程序的调试(**)

一、基本概念
l 软件：包括程序、数据、文档的完整集合
l 软件按功能分为：应用软件、系统软件、支撑软件

二、软件工程
l 软程包含3个要素：方法、工具和过程
方法是完成软件开发各项任务的技术手段
工具支持软件的开发、管理、文档生成
过程支持软件开发的各个环的控制、管理
l 软件工程研究的主要内容是软件开发技术和软件开发管理两个方面。
l 软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性
抽象：采用分层抽象、自顶向下、逐层细化的办法控制软件开发过程的复杂性
信息隐蔽：将模块设计成“黑箱”，实现的细节隐藏在模块内部。这就是信息封装，使用与实现分离的原则
模块化：有助于信息隐蔽和抽象，有助于表示复杂的系统
局部化：保证模块之间具有松散的耦合关系，模块内部具有较强的内聚，这有助于控制分解的复杂性
确定性：软件开发过程中所有概念的表达应是确定的、无歧义的、规范的
可验证性：开发大型的软件系统需要对系统自顶向下、逐层分解，以确保系统的正确性

三、软件工程过程
l 所进行的基本活动主要包含4种：软件规格说明、软件开发、软件确认、软件演进
软件规格说明：规定软件的功能以及运行的限制
软件开发：产生满足规格说明的软件
软件确认：确认能够满足用户提出的要求

四、软件生命周期
l 软件生存周期：通常把软件产品从提出、实现、使用、维护到停止使用、退役的过
程称为软件生命周期
l 软件生命周期分为3个时期共8个阶段：
1. 软件定义时期：包括问题定义、可行性和需求分析3个阶段
2. 软件开发期：包括概要设计、详细设计、实现和测试4个阶段
3. 运行维护期：即运行维护阶段
l 软件生命周期各阶段的主要任务：
1. 问题定义：
2. 可行性研究与计划制定：
3. 需求分析：对待开发软件提出需求进行分析并给出详细定义。编写软件规格说
明书及初步的用户手册，提交评审。
4. 软件设计：通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块
的划分、功能的分配以及处理流程。该阶段提交评审的文档有概要
设计说明书、详细设计说明书和测试计划初稿
5. 软件实现：在软件设计的基础上编写程序。该阶段完成的文档有用户手册、操
作手册等面向用户的文档，以及为下一步做准备而编写的单元测试
计划
6. 软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分
析报告
7. 运行维护：

五、结构化分析方法
1、需求分析和需求分析方法
(1)、需求分析阶段的工作：
l 需求获取
l 需求分析
l 需求编写规格说明书
l 需求评审
(2)、需求分析方法：
常用见的需分析方法：
（1） 结构化分析方法
（2） 面向对象的分析方法：分为静态分析方法和动态分析方法
2、结构化分析方法
使用数据流图（DFD）、数据字典（DD）、结构化英语、判定表和判定树等工具，实质是眼于数据流、自顶向下、对系统的功能进行逐层分解、以数据流图和数据字典为主要工具，建立系统的逻辑模型
3、结构化分析方法的常用工具
（1）数据流图（DFD）
l 数据流图是描述数据处理过程的工具，它是结构化程序设计理论在软件需求分析阶段的运用
l 程序流程图、N-S图、PAD图是详细设计过程中常用的图形工具
数据流：
加工： (又称转换)
存储文件： (又称数据源)
源/潭： (表示系统和环境的接口)
**请注意：数据流图与程序流程图中表示的控制流有本质不同，千万不要混淆
（2）数据字典：其中有4种类型的条目：数据流、数据项、数据存储、加工，对数据流图中所有元素的定义的集合，是结构化分析的核心。它以一种准备的，无二义性的说明方式为系统的分析、设计维护提供了有关元素的一致性定义和详细的描述。
4、软件需求规格说明书
软件需求规格说明书的标准：正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性、可追踪性

六、结构化设计方法
1、软件设计概述
（1）软件设计的基础：从工程管理的角度来看可分为两步：概要设计和详细设计。软件设计包括软件结构设计、数据设计、接口设计、过程设计
l 概要设计：将软件需求转化为软件体系结构
l 详细设计：确立每个模块的实现算法和局部数据结构
l 结构设计：定义软件系统各主要部件之间的关系
l 数据设计：将分析时创建的模型转化为数据结构的定义
l 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信
l 过程设计：把系统结构部件转换成软件的过程描述
（2）软件设计的基本原理和原则：
①模块化 ②抽象 ③信息隐藏 ④模块独立性
模块独立性：一般来说，要求模块之间的耦合尽可能弱，即模块尽可能独立，且要求模块的内聚程度尽可能高。内聚性和耦合性是一个问题的两个方向，耦合性能程度弱的模块，其内聚程序一定高
内聚性：是一个模块内部包含的信息，对于不需要这些信息的其他模块来说是不能访问的；是一个模块内部各个元素间彼此结合的紧密程序的度量
耦合性：是模块间互相连接的紧密程度的度量
对于模块进行设计时，应该尽量做到高内聚、低耦合，即减弱模块之间的耦和性和提高模块的内聚性，这样有利于提高模块的独立性
2、概要设计
（1）编写概要设计文档：概要设计阶段文档有概要设计说明书、数据库设计说明书和集成测试计划等。
（2）概要设计文档评审：在文档编写完成后，要对设计部分是否完整地实现了需求中规定 的功能、性能等要求，设计方案的可行性，关键的处理及内外部接口定义正确性、有效性，各部分之间的一致性等进行评审。
A
B
C
D
E
G
F
3、详细设计
任务是为软件结构图中的每一个模块确实实现算法和局部数据结构
程序流程图（PFD）：
l 方框表示一个加工步骤
l 菱形表示一个逻辑条件
l 箭头表示控制流
4、软件系统结构图的宽度：整体控制跨度（最大块数的层）的显示(如右图，宽度是4)

七、软件测试
1、软件测试目的
软件测试就是在软件投入运行之前，尽可能多地发现软件中的错误,发现程序中的错误
2、软件测试方法
根据软件是否需要被执行，可以分为静态测试和动态测试，如果按照功能划分，可以分为白盒测试和黑盒测试
（1）静态测试：包括代码检查、静态结构分析、代码质量度量等，是指不在计算机上运行被测试程序，而采用其他手段来达到对程序进行检测的目的，包括人工测试和计算机辅助静态分析方法。
（2）动态测试：主要通过人工进行分析。通过运行软件来检验软件中的动态行为和运行结果的正确性，并用所设计的测试用倒对程序进行检测的方法
（3）白盒测试（结构测试）：是把程序看成装在一只透明的白盒子里，测试者完成了解程序的结构和处理过程，保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；验证所有内部数据结构的有效性。
主要方法有逻辑覆盖、基本路径测试等。
（4）黑盒测试（功能测试）：把程序看成一只黑盒子，测试者完成不了解，或不考虑程序的结构和处理过程，也称为功能测试或数据驱动测试，测试时不考虑程序内部细节、结构和实现方式、仅检验程序结果与说明书的一致性。
测试方法主要有：等价划分法、边界分析法、错误推测法、因果图等，主要用于软件确认测试
3、软件测试的实施
（1）单元测试：也称模块测试，模块是软件设计的最小单位，单元测试是对模块进行正确性的检验。可以采用静态测试或者动态测试，动态测试通常以白盒测试为主，测试其结构，以黑盒测试法为辅，测试其功能
（2）集成测试：也称组装测试，它是对各模块按照设计要求组装成的程序进行测试，主要目的是发现与接口有关的错误
（3）确认测试的任务是检验软件的功能、性能及其他特征是否与用户的需求一致，它是以需求规格说明书作为依据的测试。确认测试通常采用黑盒测试
（4）系统测试：目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方
l 测试用例是为测试设计的数据，测试用倒由测试输入数据与之对应的预期输出结果两部分组成。测试用倒的格式为[（输入值集），（输出值集）]
八、程序的调试
程序调试的任务是诊断和改正程序中的错误,改正以后还需要再测试

第4章 数据库设计基础（8-10分）
考点：
1. 数据库系统的基本概念(*****)
2. 数据模型(****)
3. 关系代数(***)
4. 数据库设计与管理(**)

一、数据库系统的基本概念
1、数据、数据库、数据库管理系统
（1）数据库（DB）
（2）数据库管理系统（DBMS）：
数据库语言：
l 数据定义语言（DDL）：负责数据的模式定义和数据的物理存取构建
l 数据库操纵语言（DML）：负责数据的操纵，包括查询及增、删除、改操作
l 数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、数据恢复等功能
（3）数据库系统（DBS）
三者关系：DBS包含DB和DBMS
2、数据库系统的发展
（1）、人工管理阶段：在工人管理阶段，数据不保存，没有对数据进行管理的软件，数据不能共享
（2）、文件系统阶段：这个时期数据管理的特点是：数据需要长期保留在外存储器中供反复使用；程序和数据之间有了一定的独立性；文件夹形式已经多样化；数据的存储基本上以记录为单位，提供了简单的数据共享与数据管理能力，但它不能提供完整的、统一的管理和共享数据的能力
（3）、数据库系统阶段：
l 实现了数据共享，减少了数据冗余；
l 采用了特定的数据模型；
l 真正统一的数据控制功能，能够为多个用户和应用程序提供共享资源
l 具有数据的集成性
（4）、分布式数据库系统阶段
3、数据库系统的基本特点
数据库管理系统是数据库系统的核心
数据库系统特点：
l 数据高度集成
l 数据统一管理控制
l 数据独立性
l 共享性与低冗余性
4、数据库系统的内部结构体系
l 概念模式：是数据库系统中全局数据逻辑结构的描述，此种描述是一种抽象的描述，不但要描述概念记录类型，而且要描述记录之间的联系、所允许的操作、数据的一致性、安全性和其他数据控制方面的要求
l 外模式：也称为数据库的用户式或子模式，是从概念模式导出的子模式，用户可以通过子模式描述语言来描述用户级数据库的记录，还可以利用数据语言对这些记录进行操作。用户使用数据操纵语言对数据库进行操作，实际上是对外模式的外部记录进行操作
l 内模式：也称为数据库的物理式或存储模式。它是由系统程序员设计和组织的、是系统程序员所看到和所理解的数据库，它给出了数据库物理存储结构与物理存取方法。DBMS一般提供相关的内模式描述语言（DLL）
l 数据库系统一般分为物理独立性与逻辑独立性两级。物理独立性指数据的物理结构的改变。在数据系统中，数据的物理结构并不一定与逻辑结构一致
概念模式是一个全局模式，而外模式是用户的局部模式，内模式处于底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求

二、数据模型
l 分为层次模型、网状模型、关系模型
实体集
l 基本概念：一对一、一对多、多对多
l E-R模型：
属性
矩形：实体集
椭圆：属性
菱形：联系
联系
1、层次模型
层次模型的结构是树形结构
2、网状模型
用网状结构表示实体及其之间联系的模型
3、关系模型
l 关系模型采用二维表来表示，每行数据称为元组，列叫做属性
l 关系模型允许定义三类数据约束，它们是实体完整性约束、参照完整性约束以及用户定义的完整性约束

三、关系代数
1、传统的集合运算
并、交、差、笛卡尔积
（1）并（∪）：由2个关系运算生成第3个关系，要求两个关系的元数（字段名称）必须相同，元组（记录）的个数相加
S
A
B
1
3
3
5

R
A
B
m
1
n
2

T
A
B
m
1
n
2
1
3
3
5

例：R∪S

（2）交（∩）：由2个关系运算生成第3个关系，要求两个关系的元数（字段名称）必须相同，第3个关系中只保留前2个关系中相同的元组
例：R∩S
R
A
B
m
1
n
2

T
A
B
n
2

S
A
B
1
3
n
2

（3）差（-）：由2个关系运算生成第3个关系，要求两个关系的元数（字段名称）必须相同，从第1个关系中减去第2个关系中相同的部分
T
A
B
m
1

S
A
B
1
3
n
2

R
A
B
m
1
n
2

例：R-S

（4）笛卡尔积（×）：由2个关系运算生成第3个关系，两个关系中元数可以相同也可以不同，计算的结果元数的个数是相加的关系，元组相乘的关系
例：R×S
S
A
C
1
3
n
5

T
A
B
A
C
m
1
1
3
m
1
n
5
n
2
1
3
n
2
n
5

R
A
B
m
1
n
2

2、专门的关系运算
选择、投影、连接、除
（1） 选择：从关系中找出满足给定条件的元组。通过一个关系生成第二个关系,元组
个数减少，元数个数不变
T
A
B
m
1

R
A
B
m
1
n
2

（2） 投影：从关系模式中指定若干个属性组成新的关系称为投影，通过一个关系生
成第二个关系,元组个数不变，元数个数减少
R
A
B
m
1
n
2

T
A
m
n

（3） 连接：可以将两个关系合并成一个大关系
自然连接（|×|）：是一种特殊的等值连接，两关系间有公开域；通过公共域的相等
值进行连接。自然连接要求两个关系中进行比较的分量必须是相同的属性组，并在 结果中把重复的属性列去掉,计算方法与笛卡尔积相拟
自然连接的结果：元素个数小于等于2个关系元数相加，元组个数小于等于2个关 系元组相乘
例：R|×|S
R
A
B
m
1
n
2

T
A
B
C
n
2
5

S
A
C
1
3
n
5

（4） 除 ( / )：

四、数据库设计与管理
1、数据库设计概述
l 数据库设计是数据库应用的核心
l 数据库设计分为六个阶段：需求分析；概念结构设计；逻辑结构设计；数据库物理设计；数据库实现；数据库运行和维护
1) 数据库的逻辑设计主要工作是将E-R图转换成指定RDMS中的关系模式
2) 需求分析阶段的任务是通过详细调查现实世界要处理的对象
3) 概念设计的目的则是分析数据间内在的语义关联，在此基础上建立一个数据的抽象模型
4) 物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度以及有效利用存储空间
l 数据字典是各类数据描述的集合，数据项是数据的最小单位
l 数据库设计的主要目的就是解决数据的共享问题