804-網(wǎng)絡(luò)空間安全基礎(chǔ)

1、804-網(wǎng)絡(luò)空間安全基礎(chǔ)本考試科目包括離散數(shù)學和數(shù)據(jù)結(jié)構(gòu)兩部分內(nèi)容，每部分內(nèi)容各占1/2。考試形式閉卷、筆試?？荚嚂r間180分鐘，滿分為150分。（一）離散數(shù)學考查目標要求考生系統(tǒng)地理解與掌握離散數(shù)學的基本概念、計算和證明方法，以及應用概念和方法進行應用問題離散建模、計算求解和邏輯推理的能力。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。考試內(nèi)容1. 數(shù)理邏輯1.1 命題邏輯及其應用：命題、邏輯聯(lián)結(jié)詞、復合命題真值表、邏輯等價、析取范式與合取范式、命題的可滿足性1.2 謂詞邏輯及其應用：謂詞、量詞、謂詞邏輯中的邏輯等價、嵌套量詞1.3 邏輯推理與數(shù)學證明

2、：自然語言與邏輯表達式之間的翻譯、推理規(guī)則、證明方法和策略2. 基本結(jié)構(gòu)2.1 集合：基本概念、集合運算、集合的基數(shù)2.2 函數(shù)，序列，矩陣：基本概念、常用的函數(shù)與序列、序列求和、矩陣運算3. 歸納與遞歸3.1 數(shù)學歸納法：歸納法的原理、利用歸納法進行證明3.2 強歸納法與遞歸：強歸納法的原理、利用強歸納法進行證明、良序性及其應用、遞歸定義4. 組合計數(shù)4.1 基礎(chǔ)知識：乘積法則與求和法則4.2 鴿巢原理及其應用4.3 排列組合：排列數(shù)、組合數(shù)、二項式系數(shù)、組合恒等式與算兩次思想、排列組合的推廣（圓排列、隔板法及其應用）4.4 容斥原理及其應用5. 二元關(guān)系5.1 基本概念：二元關(guān)系及其性質(zhì)、

3、二元關(guān)系的表示、關(guān)系的閉包5.2 等價關(guān)系：等價關(guān)系的性質(zhì)、等價類與劃分5.3 偏序關(guān)系：偏序集中的相關(guān)概念、哈塞圖6. 圖論6.1 基本概念：圖論基本術(shù)語、圖模型及其應用、常用的特殊圖、圖的鄰接矩陣與關(guān)聯(lián)矩陣及其性質(zhì)6.2 圖論專題：匹配、二部圖、連通性、歐拉回路與歐拉通路、哈密頓回路與哈密頓通路、最短通路問題、平面圖與歐拉公式、圖的著色、圖的獨立數(shù)和獨立集6.3 樹：基本概念、樹的性質(zhì)和應用、樹的遍歷、生成樹和最小生成樹參考教材Discrete Mathematics and Its Applications，Kenneth H. Rosen著，徐六通 楊娟 吳斌 譯，7th editio

4、n，機械工業(yè)出版社（ISBN：9787111453826）（二）數(shù)據(jù)結(jié)構(gòu)考查目標1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度的分析。3.能夠運用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進行問題的分析與求解，具備采用C或 C+語言設(shè)計與實現(xiàn)算法的能力。考試內(nèi)容1.線性表1.1線性表的基本概念1.2線性表的實現(xiàn)1.2.1順序存儲1.2.2鏈式存儲1.3線性表的應用2.棧、隊列和數(shù)組2.1 棧和隊列的基本概念2.2棧和隊列的順序存儲結(jié)構(gòu)2.3棧和隊列的鏈式存儲結(jié)構(gòu)2.4多維數(shù)組的存儲2.5特殊矩陣的壓縮存儲2.6棧、隊列和

5、數(shù)組的應用3.樹與二叉樹3.1樹的基本概念3.2二叉樹3.2.1二叉樹的定義及其主要特征3.2.2二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)3.2.3二叉樹的遍歷3.2.4線索二叉樹的基本概念和構(gòu)造3.3樹、森林3.3.1樹的存儲結(jié)構(gòu)3.3.2森林與二叉樹的轉(zhuǎn)換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最小(代價) 生

6、成樹4.4.2最短路徑4.4.3拓撲排序4.4.4關(guān)鍵路徑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 基數(shù)排序6.10 外部排序6.11 各種排序算法的比較6.12 排序算法的應用參考教材1.數(shù)據(jù)結(jié)構(gòu)（C語言版）,