下午题
试题一
黑洞：加工有输入无输出
白洞(奇迹)：加工有输出无输入
灰洞：数据流输入的加工不足以产生输出结构化语言：
IF ***
THEN
ELSE IF ***
THEN
*******
END IF
END IF
- 数据流的父子图平衡，如果父子图平衡就不会产生实体到加工的数据流
- 数据流的文字平衡
- 一个数据流的起点和终点至少有一个是加工p
- 加工至少有一个输入一个输出
试题二
- 在一对多关系中，需要将一方的主键写入多方关系中做外键
- 在一对一关系中，需要将任意一方的主键归并到另外一方
- 在多对多关系中则需要单独抽出一个关系模式，这里的主键和外键可能相同
- 三个实体相关联的er图中，可以单独抽取一个关系模式
- 题目表述的某个意为一个或多个，而*可以表示一个或多个
- 关系模式的表示 例子：销售（编号，日期，数量） 主键：下滑横线 外键：下滑虚线 实体也许抽成关系模式
试题三
先看题目文字表述最后一行，确定是什么样的UML图 一般都是用例图（有参与者 人） 和类图
- 用例名一般是 名词+动词 类名一般使用文字描述用到的词汇
- 依赖关系：A------>B A依赖B B改变会引起A改变
- 关联关系：A——B 多重度（位于横线上方）0…1（含义：） 0…*（含义：）
- 组合关系：A——◆B 表示整体与部分的关系 整体消失 部分也消失
- 聚合关系：A——◇B 表示整体与部分的关系 整体消失 部分不消失
- 用例与用例之间的三种关系 包含 扩展 泛化
包含关系：include A------>B 关键字include位于虚线上方
当一个用例包含另一个用例时，当基本用例执行是，被包含用例一定会被执行，包含关系由基本用例指向被包含用例关系是一条带箭头虚线上有<>
扩展关系：extend A------>B 关键字extend 位于虚线上方
当一个用例执行，可能会出现特殊情况和可选情况，这时会执行扩展用例，关系是一条带箭头虚线上有<>
泛化关系：generalize A——▷B
泛化关系是一种继承关系，子用例继承父用例所有属性和行为，并且父用例出现的地方子用例也可能出现，关系是实线空心箭头、
- 实现关系：A-------▶B A：类 B：接口
试题四 算法
算法的思想
分治法
将一个复杂问题分解为若干规模较小且结构与原问题相似的子问题，然后递归解决这些子问题，最后将子问题的解合并得到原问题的解。
动态规划法
将原问题分解为若干重叠子问题，通过求解子问题的最优解得到原问题的最优解。使用一个表格来存储子问题的最优解，避免重复计算
贪心法
每一步都选择当前看起来的最优解，不考虑未来，通过一系列的局部最优解，希望得到全局最优解。
回溯法
通过逐步构建解的集合，当发现当前候选解不能满足问题的约束条件时，回溯到上一步进行其他选择，直到找到满足问题的解或者遍历完所有可能的选择（深度优先遍历）
拿分技巧
时间复杂度，关键字
归并排序，快速排序，分组 使用分治法
时间复杂度：通常为O(nlogn)
0-1背包，公共子序列，全局最优解 不一定看具体算代码
时间复杂度：通常为O(n2)或O(n3)
霍夫曼编码、最小生成树（如Prim算法和Kruskal算法），背包问题（部分），任务调度
时间复杂度：通常为O(n)，因为贪心算法只需一次遍历即可得到解
N皇后，迷宫问题
时间复杂度：取决于问题的规模和解的数量，通常为指数级别的复杂度。
时间复杂度
试题六 Java
- 接口里要填的，看实现了接口的方法里的方法（实现了一个接口就要实现这个接口里所有的方法）
- 接口不能直接实例化，要通过实现他的接口来实现实例化
- 根据返回值的类型推断方法的返回值类型，也可以根据方法的返回类型推断返回值的类型
- 在父子类继承关系extend中，补充父类方法时 一定需要加关键字abstract（父类抽象方法被继承）
- 在继承关系中，子类引用父类成员关键字super 例super.drawCircle = drawCircle;
- 在组合模式（类图）中 （+ 代表 public;- 代表 private ; # 代表 protected ; ~ 代表 package）
- 在观察者模式中，需要将观察者添加到观察者列表中区，目标需要更新状态
