首页  思维导图  详情

2020DHU-CST

2020-03-17 18:06:40   0  举报





AI智能生成

东华大学计算机考研（数学二、专业课）

东华大学

计算机

考研

笔记

读书笔记

学习笔记

作者其他创作

大纲/内容

政治（100分）

肖四（必背）

背诵马原分析题、其他分析题熟读

肖八

中国特色社会主义制度为政治稳定、经济发展、文化繁荣、民族团结、人民幸福、社会安宁、国家统一提供了有力保障，是当大中国发展进步的根本。

英语（100分）

真题

作文

王江涛

潘赟

数学（150分）

高数

极限

麦克劳林公式V24

https://www.yuque.com/stefango/blog/fily9p

（可用麦克劳林公式推导）x→0，原1首1，原0首x（原式0则首项x，原式1则首项1）

定积分的定义求极限V4

点火公式、特殊性质1-3V46

单调有界的数列必有极限V5

a+b≥2√(ab)、√(ab)≤(a+b)/2

中值定理求极限E9：罗尔、拉格朗日、柯西V17

等价无穷小公式V6上方

二项式定理

微分方程公式

导数

导数&微分基本公式

积分变限求导V41

牛顿-莱布尼茨公式V43

二阶可导可以推出一阶可导连续，不能推出二阶连续

三角函数

辅助角公式

arctan x+arccot x=±π/2

例题

设f(x)连续，对使用洛必达之后，出现f(x)的导函数，则不能使用洛必达，考虑积分中值定理

七种未定型

子主题

微分学

f(x)在[a,b]上连续，则

有界与最值定理

m≤u≤M,其中m,M分别为f(x)在[a,b]上的最小值与最大值.

介值定理

当m≤u≤M时，存在ξ∈[a,b]，使得f(ξ)=u.

平均值定理

零点定理

当f(a)·f(b)<0时，存在ξ∈(a，b)，使得f(ξ)=0.

中值定理

罗尔

拉格朗日

柯西

费马

积分中值定理（与介值定理的ξ都是∈闭区间）

综合题用到的公式

子主题

一元微分学应用

公式

伽马函数（两种写法）

常用不等式

ln(1+x)≤x

多元函数微分学

子主题

不定积分

公式

定积分

负代换

倒代换

表格法

线代

行列式

矩阵

向量

方程组

特征值和特征向量

Aα=λα(α≠0，特征值λ，特征向量α)

李林数二试卷分析

子主题

专业课(19/18真题)

数据结构（75分）

1、掌握数据结构的基本概念，熟悉评价算法的标准。

数据结构三要素

与逻辑结构有关：有序表（指出了表中数据是按一定的逻辑顺序排列的）、栈、队列、二叉树、有/无向图

与存储/物理结构有关：循环队列、双向链表、散列表、线索树、循环队列

数据的运算

算法的5个重要特性

有穷性

确定性

可行性

输入

输出

算法效率的度量

时间复杂度：将算法中基本操作的执行次数作为算法时间复杂度的度量

空间复杂度：指算法在运行时所需存储空间的度量

被创建次数最多的变量，它被创建了多少次，
那么这个算法的空间复杂度就是多少

2、掌握线性表的基本概念，熟练运用顺序存储结构和链式存储结构实现其相应操作。

线性表

顺序存储：用一组连续的内存单元依次存放线性表的数据元素。

顺序表

链式存储：用一组任意的存储单元存储线性表的各个数据元素。
元素的先后关系:每个元素存储自身的信息，
还要保存直接前趋元素或直接后继元素的存储位置。

3、掌握栈和队列的特点，理解栈的应用、递归算法的设计。

栈

限定仅能在表尾插入/删除的线性表

后进先出

队列

仅能在表头删除、表尾插入的线性表

先进先出

4、掌握树的基本概念，熟练掌握二叉树的性质、存储结构，
了解线索二叉树、树与森林，熟练掌握树的遍历及应用。

树与二叉树

结点的层次：根结点的层次定义为1；根的孩子为第二层，依此类推

树的高度（或者深度）：树中结点的最大层次

叶子/终端结点：度为0的结点

结点的深度：从根节点到该节点路径上的节点个数

结点的高度：从下往上

树的带权路径长度(WPL):
树中所有叶子结点的带权路径长度（该结点到根之间的路径长度x结点的权值）之和

二叉树遍历

先序

根左右

中序(必须)

左根右

后序

左右根

其中先序+后序就不能唯一确定一棵二叉树，其他两种组合（先序+中序、中序+后序）可以唯一的确定一颗二叉树

二叉树

性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。

性质2: 深度为k的二叉树至多有2k-1个结点（k≥1）。

首项为1、公比为2的等比数列前k项和

性质3: 对任意一棵二叉树T，若叶结点数为n0，而其度为2的结点数为n2，则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为[A]+1，其中A=log[2,n]，[A]表示向下取整，[A]+1表示向上取整。

性质5: 对于有n个结点的完全二叉树，按照从上到下、从左到右的顺序
对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：
（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为[i/2]（下取整）
（2）如2i>n，则序号为i的结点无左孩子；如2i≤n，则序号为i的结点的左孩子结点的序号为2i。
（3）如2i＋1>n，则序号为i的结点无右孩子；如2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1。

满二叉树

满二叉树：除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树

完全二叉树

完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
也就是说，在满叉树的基础上，我在最底层从右往左删去若干节点，得到的都是完全二叉树。
所以说，满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

5、理解图的基本概念，掌握图的存贮结构，图的遍历、最小生成树和拓扑排序。

6、掌握查找的基本概念、查找性能分析、熟练掌握顺序查找、折半查找和哈希查找。

7、熟练掌握直接插入排序、希尔排序、快速排序、简单选择排序和归并排序，理解堆排序和各种排序方法的比较。

选择题20分，填空题20分，简答题15分，算法题20分。

真题

根据先序、中序遍历画出二叉树

哈夫曼树的加权路径长度WPL

构造

构造森林全是根
选用两小造新树
删除两小添新人
重复2、3剩单根

哈夫曼树的结点的度为0或2

邻接矩阵

克鲁斯卡尔算法最小生成树

归并排序、快速排序、堆排序

线性探测

图广/深度优先

零碎知识

线性表

栈：

数据库（75分）

https://wenku.baidu.com/view/8fa0b4aea98271fe900ef974.html

1、掌握数据库系统的基本概念，
包括三层模式结构与两级映像、数据独立性等。

三层模式结构

外模式（子模式或用户模式）
用户看见和使用的局部数据的逻辑结构和特征的描述（用户的数据视图），
是与某一个应用有关的数据的逻辑表示。
用户对数据库的操作，只能与外模式发生联系，按照外模式的结构存储操纵数据。

模式（逻辑模式或概念模式）
全局数据逻辑结构和特征的描述，
所有用户的公共数据视图。

内模式（又称存储模式、物理模式）
数据物理结构和存储结构的描述，
数据在数据库内部的表示方式。
定义所有的文件的组织方式、索引和聚簇，存取方式和存取路径。

一个数据库中只有一个内模式和一个模式，但可有多个外模式。

两级映像

外模式/模式映象
外模式/模式映象定义了各外模式和模式之间的对应关系（在各自外模式的描述中定义）。
当模式改变时，由数据库管理员对各个外模式/模式映象作相应的改变，
而外模式仍然保持不变，从而应用程序不必修改，保证了数据的逻辑独立性。

模式/内模式映象
模式/内模式映象定义了数据全局逻辑结构与存储结构之间的对应关系。
当数据库的内模式发生改变，即数据库的存储结构发生改变时，
由数据库管理员对模式/内模式映象作相应的改变，
而使模式保持不变，从而保证了数据的物理独立性。

2、掌握关系模型的基本概念，
熟练掌握关系代数运算和关系代数表达式的优化。

数据模型的三要素

数据结构

数据操纵

数据完整性

实体完整性：主键非空

参照完整性：不允许引用不存在的实体

用户定义的完整性

关系代数运算

五个基本操作

差(Exception)-

施伯乐叫Difference，但是MySQL中使用EXCEPT

并(Union)∪

具有相同的关系模式

笛卡尔积/乘法(Cartesian Product)x

广义笛卡尔乘积（ × ）
设R为m目关系（m列）， S为n目关系，则R和S的广义笛卡尔乘积为：
R×S={t|t=〈tr， ts〉∧tr∈R∧ts∈S}
其结果为m+n目关系。
元组的前m列是关系R的一个元组，元组的后n列是关系S的一个元组。
若R有k1个元组（k行）， S有k2个元组，则R×S有k1×k2个元组。

投影(Projection)π

对一个关系进行垂直分割，选取指定列

选择(Selection)σ

对一个关系进行水平分割，选取符合条件的元组

组合操作

交(Intersection)∩

连接(Join)⋈[连接符号下方位iθj]

θ是等号"="

等值连接

不去除重复列

θ不是等号

自然连接(Natural Join)⋈

去除重复列

除法/笛卡尔积的逆运算(Division)

(施伯乐P48)至少选修course1、course2中列出课程的学生名单

扩充操作

改名

ρ[下标S(新名字1,新名字2)](R)

把关系R改名为关系S(包含列名)

广义投影

允许在投影列表中使用算术函数来对投影进行扩展

如：π的下标可以为score*0.15

赋值←

外连接(Outer Join)

保留自然连接R和S中所舍弃的元组，无对应关系时填上空值(null)

分类

左外连接

在自然连接的基础上加上左边表上不包含自然连接中所含元组（行）的元组。
select * from R left join S

右外连接

在自然连接的基础上加上右边表上不包含自然连接中所含元组（行）的元组。
select * from R right join S

外连接/全外连接

外连接=左连接+右连接；
select * form R outer join S

外部并（Outer Union）

R和S的每个元组各占一行，新增属性为空值(null)

半连接（Semi Join）

R和S的自然连接上只保留关系R的属性集上的投影

聚集操作

输入一个值的集合，输出一个单一的值

常用的聚集函数包括max、min、avg、sum、count等。

关系代数表达式的优化

等价变换规则

规则1 连接和笛卡尔积的交换律

规则2 连接和笛卡尔积的结合律

规则3 投影的级联

规则4 选择的级联

规则5 选择和投影操作的交换

规则6 选择对笛卡尔积的分配律

规则7 选择对并的分配律

规则8 选择对集合差的分配律

规则9 选择对自然连接的分配律

规则10 投影对笛卡尔积的分配律

规则11 投影对并的分配律

规则12 选择与连接操作的结合

规则13 并和交的交换律

规则14 并和交的结合律

启发式优化算法

启发式规则

早执行选择操作

早执行投影操作

避免直接做笛卡尔积，把笛卡尔积操作之前和之后的
一连串选择和投影合并起来一起做

查询语法树（用笛卡尔积表示），并进行查询优化

3、熟练掌握关系数据库语言SQL，
包括数据定义、数据查询、数据更新、视图及索引的使用。

SQL语言(Structured Query Language):结构化查询语言
集
数据定义语言DDL（CREATE、ALTER、DROP）
数据操纵语言DML（INSERT、UPDATE、DELETE）
数据控制语言DCL（GRANT、INVOKE）
的功能于一体

定点数NUMERIC(p,d)：不含符号/小数点的长度为p，精度（小数点后面的位数）为d

典型SQL

select s#,sname,2019-age from s;
(not) exists
嵌套查询in
distinct
group by
having子句为“组条件子句”

两个子查询完全一致时，可以进行

并union、交intersect、差except

4、掌握函数依赖、第一范式、第二范式、第三范式和BC范式等概念，
熟练判断关系模式的范式、进行关系模式的无损连接分解与保持函数依赖分解。

函数依赖(Functional Dependency, FD)

定义

形如X→Y的一个命题

FD的推理规则
(Armstrong公理系统的三条推理规则)

自反性

若Y包含于X包含于U，则F蕴涵X→Y（或X→Y在R上成立）

增广性

若F蕴含X→Y，且Z包含于U，则F蕴含XZ→YZ

传递性

若F蕴含X→Y和Y→Z，则F蕴含X→Z

Armstrong公理的三个推论

合并规则: 若X→Y， Y→Z，则X→YZ

分解规则: 若X→Y且Z包含于Y，则X→Z

伪传递规则: 若X→Y， YZ→W，则XZ→W

非平凡函数依赖和平凡函数依赖

对于FD X→Y，如果Y包含于X，那么称X→Y是一个“平凡的FD”，
否则称为“非平凡的FD”。
平凡的FD没有实际意义，只有非平凡的FD才和“真正的”完整性约束条件相关。

例：在关系SC(Sno, Cno, Grade)中，
非平凡函数依赖：(Sno, Cno) → Grade
平凡函数依赖：
(Sno, Cno) → Sno
(Sno, Cno) → Cno

完全函数依赖和部分函数依赖

在一张表中，若 X → Y，且对于 X 的任何一个真子集（假如属性组 X 包含超过一个属性的话），
X → Y 不成立，那么我们称 Y 对于 X 完全函数依赖。

如：学号 F→ 姓名，（学号，课名） F→ 分数
（注：因为同一个的学号对应的分数不确定，
同一个课名对应的分数也不确定）

对于FD W→A，如果存在X⊂W有X→A成立，
那么称W→A是局部依赖（A局部依赖于W）

如：（学号，课名） P→ 姓名，
因为“学号→姓名”成立

传递函数依赖

如果 Y 不包含于 X 且 X 不函数依赖于 Y，Z 不包含于 Y，X→Y，Y→Z ，
那么称 Z 传递函数依赖于 X ，记作 X T→ Z

这里加上条件Y不能推出X，是因为如果 Y →X，
则X←→Y，实际上是X直接退出Z，
是直接函数依赖，而不是传递函数依赖。

术语

超键：设关系模式R的属性集是U，X是U的一个子集。如果X→U在R上成立，那么称X是R的一个超键。
超键：能够唯一标识一条记录的属性或属性集。

键/候选键：如果X→U在R上成立，但对于X的任一真子集X1都有X1→U不成立，那么称X是R上的一个候选键。
键/候选键：可以唯一标识一个元组的最少的属性集合。

候选键是没有多余属性的超键。

如果A是关系模式R候选键中的属性，那么称A是R的主属性；
否则称A是R的非主属性。

范式

1NF

如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式（first normal form，简记为1NF）的模式。
1NF是关系模式应具备的最起码的条件。
满足1NF的关系称为规范化的关系，否则称为非规范化的关系。

2NF

如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式（2NF）的模式。
如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。

3NF

如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选键，那么称R是第三范式（3NF）的模式。
如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式。

BCNF

如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。
如果数据库模式中每个关系模式都是BCNF，则称为BCNF的数据库模式。
如果R是BCNF模式，那么R也是3NF模式。
（等价定义）设F是关系模式R的FD集，如果对F中每个非平凡的FD X→Y，都有X是R的超键，那么称R是BCNF的模式。

无损分解

若在投影、连接后仍能恢复成原来的关系，即未丢失信息，
把这种分解称为“无损分解”。

损失分解

若在投影、连接后不等于原来的元组，把这种分解称为“损失分解”。

5、理解数据库设计的全过程，熟练掌握ER模型，
以及 ER模型到关系模型的转换。

数据库的完整性

数据的正确性

数据的有效性

数据的相容性

6、掌握事务的概念和ACID性质，理解数据库的恢复、
并发控制、完整性约束、安全性保护方法，能够使用SQL创建用户和授权。

并发操作带来的数据不一致性包括丢失修改、不可重复读、读“脏”数据

原子性、一致性、隔离性、持久性