软考中级(软件设计师)——数据库设计(下午15分)——数据结构及算法应用(最难的点1个答题15分-程序填空题-目标3-9分)

软考中级(软件设计师)——数据库设计(下午15分)——数据结构及算法应用(最难的点1个答题15分-程序填空题-目标3-9分)

目录

软考中级(软件设计师)——数据库设计(下午15分)——数据结构及算法应用(最难的点1个答题15分-程序填空题-目标3-9分)

数据库设计过程

ER模型

实体间的联系模型

答题技巧

考的内容：

数据结构及算法应用

分治法

二分查找法

回溯法

贪心法

动态规划法

数据库设计过程

每个阶段都要有对应的产出，例如：

需求分析要出：数据流图、数据字典、需求说明书。

概要概念设计：ER图/ER模型

逻辑结构设计：关系模式图

ER模型

实体间的联系模型

主要分为三种

a）1：1的联系、 b）1：n的联系、 c）m：n的联系

转换的基本原则是:实体和联系分别转换成关系,属性则转换成相应关系的属性

一对一联系 对多联系 多对多联系 多元联系

答题技巧

详细分析试题说明

练掌握基本知识

考的内容：

1、找关系(几对几的关系)

2、ER图转成关系模式

3、主键/外键

4、综合题，前三题的综合补充关系。

数据结构及算法应用

一般第一个空填写【初始化】，一个就是3分。

分治法

斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔

二分查找法

回溯法

N皇后问题、迷宫、背包问题

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某-步时,发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

贪心法

背包问题(如装箱)、多机调度、找零钱问题

动态规划法

斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

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

时间复杂度