一、数据流图

相关概念

数据流图

数据流图描述数据在系统中如何被传送或变换，以及如何对数据流进行变换的功能或子功能，用于对功能建模，数据流图相关概念如图

数据流图是可以分层的，从顶层到0层、1层等，顶层数据流图只含有一个假工处理表示整个管理系统（描述了系统的输入和输出，以及和外部实体的数据交互）

数据字典

数据字典是用来定义在数据流图中出现的符号或名称的含义，在数据流图中，每个存储、加工、实体的含义必须定义在数据字典中，并且父图和子图之家这些名称要相同

设计原则

1. 数据守恒原则：对任何一个加功来说，其所有输出数据流中的数据必须能从该加工的输入数据流中直接获取，或直接说是通过该加工产生的数据
2. 守恒加功原则：对同一个加工来说，输入与输出的名字必须不同，即使他们的组成成分相同
3. 对于每个加工，必须既有输入数据流，又有输出数据流
4. 外部实体与外部实体之间不存在数据流
5. 外部实体与数据存储之间不存在数据流
6. 数据存储与数据存储之间不存在数据流
7. 父图与子图的平衡原则：子图的输入输出数据流同父图相应加工的输入输出数据流类必须一致，此即父图与子图的平衡
8. 数据流与加功有关，且必须经过加工

数据平衡原则

• 父图与子图间平衡：顶层图中，描述了外部实体和系统之间的数据流关系，在0层图中，展开系统，变成了外部实体和系统内部更详细的数据流关系，但是，顶层和0层互为父图、子图关系，其输入、输出数据流个数和名称不应该发送变换，也即应该保持平衡
• 子图内平衡：对于子图内的每一个加工，要求既有输入，也要有输出，才是数据平衡，根据这一原则，可以对每个输入进行判断，是否有相应的输出
• 数据流只能和加工有关，即从加工流向加工、数据源流向加工或加工流向数据源
• 输入数据流和输出数据流名称不能相同，类型必须匹配

解题技巧

题型

• 第一小题 ： 补充外部实体
• 第二小题：补充数据存储
• 第三小题：补充缺失数据流
• 第四小题： 概念相关题型

外部实体补充题型

外部实体就是与系统进行交互的其它实体，可以是大型系统、公司部门、相关人员等，外部实体会与系统进行交互，反应在数据流图中就是一个个事件流，依据事件的名称结合题目比描述

数据存储补充题型

数据存储出现在0层数据流图中，反应系统内部数据的存储，可以直接根据数据流图中就存储的输入数据流和输出数据流判断该数据存储的信息

数据流补充题型

首先判断父图和子图是否数据平衡，依据父图和子图间数据平衡原则核对父图中的每个输入、输出数据流是否都能在子图中找到，直接看外部实体输入、输出数据流

而后判断子图内部是否数据平衡，依据子图内数据平衡原则，详细阅读题目描述，对每句话一一核对是否反映子图中，以及每个加工是否都有输入、输出等原则判断。

真题示例

题目1

根据题目描述，可以填充实体E1-E3分别为

客服服务助理、客户、经济人

题目2

根据题目描述，可以填充数据存储为D1-D3分别为

客户记录、账户记录、交易记录

题目3

根据图所知，子图和父图数据流平衡。子图内部的数据流不平衡，现补充数据流

存款——存款金额——D2

取款——取款金额——D2

证券交易（在线）——交易信息——交易记录

证券交易（电话）——交易信息——交易记录

题目4

看问题的描述，定位到 证券交易 这个加工数据流， 其中又提到 证券交易中心这个外部实体。可以对此进行修改论述说明。

答案参考

练习

题目1

根据题目描述和数据流图，E1-E5代表的实体分别是

巴士司机、机械师、会计、主管、库存管理系统

题目2

根据题目描述和数据流图，D1-D4的数据存储分别是

巴士列表文件、维修记录文件、部件清单、人事档案

题目3

维修系统的内部联系没有表现出来

题目4

根据描述，对数据流进行补充

二、数据库设计

相关概念

• E-R图
• 关系模式

E-R图：即实体-联系图，使用椭圆表示属性、长方体表示实体、菱形表示联系，联系两端要标注联系类型

联系类型： 1:1、1:N、M:N

1. 实体和子实体（直线连接、从属关系）
2. 多个实体一个类型（...）
3. 主键和外键（主键是本关系内唯一，外键是其它关系的主键，外键可以有多个）

关系模式：以名称和属性名表示一个联系

主键：不能为空，能唯一标识当前关系的属性

外键：其它关系模式的主键或者为空

E-R图转关系模式

首现，每个实体都要转换为一个关系模式，对于联系，一对一，联系作为一个属性随便加入到哪个实体中；一对多，联系可以单独转换为一个关系模式，也可以作为一个属性加入到 N端；多对多，联系必须单独转换为一个关系模式，且此关系模式应包含两端实体的主键；

转换之后原来两个实体之间的联系必须还存在，能够通过查询方式查到对方

解题技巧

题型

• 第一小题：补充 E-R 图
• 第二小题：补充关系模式
• 第三、四小题：数据库设计相关题型

补充E-R图题型

根据题目描述确定哪些实体之间的联系，联系类型是哪一种

补充关系模式题型

E-R图转换为关系模型，补充缺失的属性，分为两步：

首先审题，题目会给出每个关系模式的属性信息，先将题目中的属性信息和问题对应，将缺少的属性全部填充

而后在按照规则转换...

真题示例

题目1

补充实体之间的5个联系，根据题目描述5个联系分别是

1. 分公司与员工之间的联系 1：n
2. 经理和分公司之间的联系 1：1
3. 申请单和业务员之间的联系 n：1
4. 申请单和客户之间的联系 n：1
5. 调度员和业务员之间的联系 n：m

题目2

将关系模式 a-c 填充完整、给出 员工、申请单、安排承运 关系模式的主键和外键 。 根据题目描述

1. a：任职时间
2. b：申请号
3. c：承运业务员

答案参考

练习

题目1

补充联系和联系的类型

1. 球队和队员之间的联系 1：n
2. 教练与球员之间的联系 1：n
3. 球队和球队之间的联系 1：1
4. 裁判和球队之间的联系 1：n

题目2

补充关系模式

1. 球队编号
2. 球队编号

题目3

参考答案

三、UML建模

相关概念

• 用例图：

  静态图，展现了一种用例、参与者以及他们之间的关系

  用例图中的参与者是人、硬件或者其它系统可以扮演的角色；用例是参与者完成的一些列操作

  主要考察 参与者和用例的识别、用例之间的关系（包括include、扩展、extend、泛化）

  

  如图所示，登记外借信息用例包含用户登录用例，因为每次如果要登记外借信息，必然要先进行用户登录。而查询书籍信息的扩展是修改书籍信息，是因为每次查询书籍信息后，发现有错误才会修改，否则不修改，不是必要操作。因此区分用例的关系是否包含扩展，关键在于 是否必须操作

• 类图

  主要考察 类名、多重度、类之间的联系（泛化、组合、聚合、实现、依赖）

  

  多重度：

  • 1：表示一个集合中的一个对象对应另一个集合中的1个对象

  • 0..*：表示一个集合中的一个对象对应另一个集合中的 0 个或多个对象

  • 1..*：表示一个集合中的一个对象对应另一个集合中的 1 个或多个对象

  • *：表示一个集合中的一个对象或多个对象对应另一个集合中的多个对象

  

  依赖：一个事物的语义依赖另一个事物的语义的变化而变化

  关联：是一种结构关系，描述了一组链，链是对象之间的连接。分为组合和聚合，都是部分和整体的关系，其中组合事物之间关系更强。两个类之间的关联，实际上是两个类所扮演的角色的关联，因此，两个类之间可以有多个由不同角色表示的关联

  泛化：一般/特殊的关系，子类和父类之间的关系

  实现：一个类元指定了另一个类元保证执行的契约

  理解聚合和组合都是部分和整体之间的关系，类之间大多考虑这种关系，必须记住其符号，且菱形一端为整体，表示其由另一端实体组成，可依据题意找出组成元素解题

  依赖关系最弱，只要由部分相关就是依赖。

  泛化关系是父子关系

  组合和聚合都是 部分-整体 关系，组合更强

• 序列图

  即顺序图，动态图，是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动

  

  主要考察对象名、消息名

• 通信图

  是顺序图的另一种表示方式，也是由对象和消息组成的图，只不过不强调时间顺序，指强调事件之间的通信，而且也没有固定的画法规则，和顺序图统称为交互图

  对象名、消息名

  

• 活动图

  动态图，是一种特殊的状态图，展现了在系统内从一个活动到另一个活动的流程

  活动的分岔和汇合是一条水平粗线

  

• 状态图

  主要描述状态之间的转换，转换可以通过事件触发器触发，事件触发后相应的监护条件会进行检查。状态图中转换和状态是两个独立的概念

  

  考察 ： 状态名、转换条件

解题技巧

题型

• 第一小题：补充用例名、消息等
• 第二小题：补充状态等
• 第三小题：相关概念题型

考察 UML 建模就是考察多种图形，对这些图形的考察一般都是缺失一些关键点，而后要求考生补图

• 要求认真审题，根据题干说明补齐类名或者对象名或者消息名等等，记住类图和对象图中的多重度（互相独立的分析、掌握表示方法）、类之间的联系标识（多边形端为整体，直线端为个体）

题型

• 补充用例图：主要考察补充用例名称、参与者、用例之间的关系
• 补充类图：主要考察补充类名称，需要根据类之间的关系以及多重度来判断，需要牢记类之间关系的图形符号，尤其是组合、聚合、继承的符号，并且观察符号上多重读的数据，与题目描述对应
• 补充状态图：主要补充状态名称
• ...

真题示例

问题1

根据题目描述，S1-S3所对应的状态为

普卡会员、银卡会员、金卡会员

T1-T3处所对应的迁移名称为

自动升级、自动升级、自动降级

题目2

根据题目描述，给出C1-C4的类名

CNonMember、CBasic、CSilver、CGold

题目3

设计模式...

答案参考

练习

题目1

根据题目描述，给出 1-4 的用例名称

1：添加购物车 2：提交购物车 3：选择收货地址 4：选择付款方式

题目2

根据题目描述，

当用户没有预留收获地址，或者是在预留地址清空的情况下。无法选择收获地址是会触发用例3的扩展。同样的当用户没有添加付款方式，用户需要选择付款方式是会触发添加付款方式的扩展

题目3

根据题目描述，1-7 对应的类名是

1：商品

2：商品列表

3：学术出版物

4：论文

5：学术报告

6：讲座资料

7：订单

参考答案

四、程序与算法

• 算法分析
• 算法分类

相关概念

数据成分：指一种程序设计语言的数据和数据类型。数据分为常量、变量、全局量、局部量。数据类型有整型、字符型、双精度、单精度浮点型、布尔型等...

运算成分：指明允许使用的运算符号以及运算规则。包括算术运算、逻辑运算、关系运算、位运算等

控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构

传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等

函数：C程序由一个或多个函数组成，每个函数都有一个名字，其中有且有一个名位 main 的函数作为程序运作时的起点。函数是程序模块的主要成分，是一段具有独立功能的程序。函数使用涉及三个概念：函数定义、函数声明、 函数调用

传值调用：将实参的值传递给形参，形参的改变不会导致调用点所传的实参的值改变，实参可以是合法的变量、常量和表达式

传址调用：引用调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值。实参不能作为常量，只能是合法的变量和表达式

算法的复杂度：

时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量

一般来说，算法中原操作重复执行的次数是规模n的某个函数 T(n)，由于许多情况下要精确计算T（n）是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：

如果存在两个常数 C 和 M，对于所有的 n，当 n>=m 时有 f(n)<=cg(n)，则有 f(n)=O(g(n)) ...

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

算法类型

分治法

递归：指子程序直接调用自己通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方式

递归两个基本要素：边界条件 （确定递归何时终止，递归出口）、递归模式（大问题如何分解成小问题，递归体）

分治法：对于一个规模为 n 的问题，若该问题可以容易地解决或直接解决；否则将其分解为 K 个规模较小的子问题，这些子问题互相独立且原问题形式相同，递归地解决这些子问题，然后将给子问题的解合并得到原问题的解

（二分查找、归并排序）

回溯法

有 通用的解题法 之称，可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点触发搜索解空间树。搜索至任一结点时，总是先判断该节点是否肯定不包含问题的解，如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯

动态规划法

在求解问题中，对于每一步决策，列出各种可能的局部解，再根据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过赛选，以每一步都是最优解来保证全局是最优解

本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间都不是相互独立的，并且不全都相同

贪心法

总是做出在当前来说最好的选择，而并不从整体上加以考虑，他所作的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解

局部贪心，只针对当前的步骤取最优，而非整体考虑

解题技巧

题型

• 第一小题：代码填空
• 第二小题：时间复杂度
• 第三小题：相关概念

补充相关算法学习...

真题示例

题目1

根据题目描述，对代码1-4进行填空

1：k<(p+n1>n2?n1:n2)

2：arr[k]=right[j]

3：end>begin

4：mergeSort(arr,mid,end)

题目2

分治法

时间复杂度：

渐进时间复杂度：

空间复杂度：n

答案参考

练习