23年山东大学考研804网络空间安全基础考试大纲
804-网络空间安全基础本考试科目包括离散数学和数据结构两部分内容，每部分内容各占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网络空间安全基础考试大纲
页:
[1]