2024年山東大學非全日制研究生招生考試《網絡空間安全基礎》考試大綱

　　本考試科目包括離散數學和數據結構兩部分內容，每部分內容各占1/2。

　　考試形式

　　閉卷、筆試?？荚嚂r間180分鐘，滿分為150分。

　　(一)離散數學

　　考查目標

　　要求考生系統(tǒng)地理解與掌握離散數學的基本概念、計算和證明方法，以及應用概念和方法進行應用問題離散建模、計算求解和邏輯推理的能力。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。

　　考試內容

　　1. 數理邏輯

　　1.1 命題邏輯及其應用：命題、邏輯聯結詞、復合命題真值表、邏輯等價、析取范式與合取范式、命題的可滿足性

　　1.2 謂詞邏輯及其應用：謂詞、量詞、謂詞邏輯中的邏輯等價、嵌套量詞

　　1.3 邏輯推理與數學證明：自然語言與邏輯表達式之間的翻譯、推理規(guī)則、證明方法和策略

　　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著，徐六通 楊娟 吳斌 譯，7th edition，機械工業(yè)出版社(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深度優(yōu)先搜索

　　4.3.2廣度優(yōu)先搜索

　　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