本考试类别包括离散数学和数据规划两有些内容，每有些内容各占1/2。

考试方法

闭卷、书面考试。考试时刻180分钟，满分为150分。

（一）离散数学

查询方针

需求考生体系地了解与掌控离散数学的根柢概念、核算和证明办法，以及使用概念和办法进行使用疑问离散建模、核算求解和逻辑推理的才能。

需求考生具有笼统思维才能，逻辑推理才能，和归纳运用所学的常识分析疑问和处置疑问的才能。

考试内容

1. 数理逻辑

1.1 出题逻辑及其使用：出题、逻辑联合词、复合出题真值表、逻辑等价、析取范式与合取范式、出题的可满足性

1.2 谓词逻辑及其使用：谓词、量词、谓词逻辑中的逻辑等价、嵌套量词

1.3 逻辑推理与数学证明：天然言语与逻辑表达式之间的翻译、推理规则、证明办法和战略

2. 根柢规划

2.1 集结：根柢概念、集结运算、集结的基数

2.2 函数，序列，矩阵：根柢概念、常用的函数与序列、序列求和、矩阵运算

3. 归纳与递归

3.1 数学归纳法：归纳法的原理、使用归纳法进行证明

3.2 强归纳法与递归：强归纳法的原理、使用强归纳法进行证明、良序性及其使用、递归界说

4. 组算计数

4.1 基础常识：乘积规则与求和规则

4.2 鸽巢原理及其使用

4.3 摆放组合：摆放数、组合数、二项式系数、组合恒等式与算两次思维、摆放组合的推广（圆摆放、隔板法及其使用）

4.4 容斥原理及其使用

5. 二元联络

5.1 根柢概念：二元联络及其性质、二元联络的标明、联络的闭包

5.2 等价联络：等价联络的性质、等价类与区别

5.3 偏序联络：偏序会集的有关概念、哈塞图

6. 图论

6.1 根柢概念：图论根柢术语、图模型及其使用、常用的特别图、图的邻接矩阵与相关矩阵及其性质

6.2 图论专题：匹配、二部图、连通性、欧拉回路与欧拉通路、哈密顿回路与哈密顿通路、最短通路疑问、平面图与欧拉公式、图的上色、图的独立数和独立集

6.3 树：根柢概念、树的性质和使用、树的遍历、生成树和最小生成树

参阅教材

discrete mathematics and its applications，kenneth h. rosen著，徐六通 杨娟 吴斌 译，7thedition，机械工业出书社（isbn：9787111453826）

（二）数据规划

查询方针

1.掌控数据规划的根柢概念、根来历理和根柢办法。

2.掌控数据的逻辑规划、存储规划及根柢操作的完成，可以对算法进行根柢的时刻凌乱度与空间凌乱度的分析。

3.可以运用数据规划根来历理和办法进行疑问的分析与求解，具有

选用c或 c++言语方案与完成算法的才能。

考试内容

1.线性表

1.1线性表的根柢概念

1.2线性表的完成

1.2.1次序存储

1.2.2链式存储

1.3线性表的使用

2.栈、行列和数组

2.1 栈和行列的根柢概念

2.2栈和行列的次序存储规划

2.3栈和行列的链式存储规划

2.4多维数组的存储

2.5特别矩阵的紧缩存储

2.6栈、行列和数组的使用

3.树与二叉树

3.1树的根柢概念

3.2二叉树

3.2.1二叉树的界说及其首要特征

3.2.2二叉树的次序存储规划和链式存储规划

3.2.3二叉树的遍历

3.2.4条理二叉树的根柢概念和规划

3.3树、森林

3.3.1树的存储规划

3.3.2森林与二叉树的变换

3.3.3.树和森林的遍历

3.4树与二叉树的使用

3.4.1二叉查找树

3.4.2平衡二叉树

3.4.3哈夫曼(huffman) 树和哈夫曼编码

4.图

4.1图的根柢概念

4.2 图的存储及根柢操作

4.2.1邻接矩阵法

4.2.2邻接表法

4.2.3十字链表

4.3图的遍历

4.3.1深度优先查找

4.3.2广度优先查找

4.4图的根柢使用

4.4.1最小(价值) 生成树

4.4.2最短途径

4.4.3拓扑排序

4.4.4要害途径

5.查找

5.1 查找的根柢概念

5.2 次序查找法

5.3 分块查找法

5.4 减半查找法

5.5 b-树、b+树的根柢概念及其根柢操作

5.6 散列(hash) 表

5.7 字符串方法匹配

5.8 查找算法的分析及使用

6.排序

6.1排序的根柢概念

6.2 刺进排序

6.2.1 直接刺进排序

6.2.2 减半刺进排序

6.3起泡排序(bubble sort) ?

6.4简略选择排序

6.5希尔排序(shell sort)

6.6 快速排序

6.7堆排序

6.8 二路归并排序(mergesort)

6.9 基数排序

6.10 外部排序

6.11 各种排序算法的比照

6.12 排序算法的使用

参阅教材

1.《数据规划（c言语版）》,作者：严蔚敏，吴伟民,出书社：清华大学出书社,isbn：9787302023685

2.《数据规划与算法》,作者：张铭，王腾蛟，赵海燕,出书社：高级教育出书社,isbn：9787040239614

2022年硕士研讨生招生考试大纲：考试大纲 | 山东大学804网络空间平安基础考试大纲