題型分布

　　一、選擇題：(40道題，每題2分，共80分)數據結構：16道題

　　機器學習：16道題

　　知識表示與處理：8道題

　　二、綜合問答題：(8道題，共70分)數據結構：3題(共28分)

　　機器學習：3題(共28分)

　　知識表示與處理：2題(共14分)

　　考試大綱

　　數據結構

　　【考查目標】

　　1. 理解數據結構的基本概念;掌握數據的邏輯結構、存儲結構及其差異以及各種基本操作的實現。

　　2. 棠握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。

　　3. 能夠選擇合適的數據結構和方法進行問題求解;具備采用C++、python語言設計與實 現算法的能力。

　　[考查范圍】

　　一、復雜度分析和遞歸

　　(—)算法的時間與空間復雜度分析

　　(二)遞歸及遞歸的復雜度分析

　　(三)初級動態規劃算法二、鏈表、棧、隊列

　　(—)鏈表的基本概念和實現

　　(二)棧和隊列的基本概念

　　(三)棧和隊列的順序存儲結構

　　(四)棧和隊列的鏈式存儲結構

　　(五)棧和隊列的應用：表達式求值算法等三、樹與二叉樹

　　(—)樹的基本概念

　　(二)二叉樹

　　1. 二叉樹的定義及其主要特征

　　2. 二叉樹的順序存儲結構和鏈式存儲結構

　　3. 二叉樹的遍歷

　　4. 平衡二叉樹

　　5. 哈夫曼(Huffman)樹和哈夫曼編碼

　　6. AVL樹四、圖

　　(—)圖的概念

　　(二)圖的存儲及基本操作

　　1. 鄰接矩陣法

　　2. 鄰接表法

　　(三)圖的遍歷

　　1. 深度優先搜索

　　2. 廣度優先搜索

　　(四)圖的基本應用

　　1. 最短路徑

　　2. 拓撲排序

　　3. Dijkstra(迪杰斯特拉)算法及其特點分析五、查找

　　(-)查找的基本概念

　　(二)順序查找法

　　(三)折半查找法

　　(四)樹在查找的應用

　　(五)哈希(Hash)表

　　(六)局部敏感哈希算法

　　(七)查找算法的分析及應用六、排序

　　(-)排序的基本概念

　　(二)插入排序

　　1. 直接插入排序

　　2. 折半插入排序

　　(三)冒泡排序

　　(四)選擇排序

　　(五)快速排序

　　(六)堆排序

　　(七)基數排序

　　(八)各種內部排序算法的比較

　　(九)排序算法的應用

　　機器學習

　　【考察目標】

　　1. 棠握機器學習的基本概念、基本流程;理解機器學習的常用任務、方法和模型。

　　2. 理解機器學習方法和模型的數學原理和優缺點;能夠結合具體任務對模型進行評估和選 擇。

　　3. 能夠運用機器學習的方法、模型和基本原理，通過計算和分析，解決機器學習領域的理 論和實際問題。

　　【考察范圍】

　　一、機器學習的基本概念(—)機器學習的定義

　　(二)機器學習的基本概念

　　1. 樣本、特征、標簽、數據集

　　2. 訓練、測試、模型參數、損失函數、誤差

　　3. 泛化能力、正則化二、回歸模型

　　(—)線性回歸

　　1. 線性回歸模型

　　2. 線性回歸模型的優化

　　正規方程法、梯度下降法、隨機梯度下降、牛頓法

　　(二)非線性回歸的概念

　　(三)正則化線性回歸

　　1. 嶺回歸

　　2. 套索(LASSO)回歸

　　3. 近端梯度法三、分類模型

　　(一)判別模型與生成模型的概念和區別

　　(二)K最近鄰算法

　　(三)貝葉斯分類器

　　1. 生成貝葉斯分類器

　　2. 樸素貝葉斯分類器

　　3. 高斯樸素貝葉斯分類器

　　4. 線性判別分析

　　(四)邏輯回歸(對數幾率回歸)

　　1. 幾率與邏輯函數(對數幾率函數)

　　2. 二分類邏輯回歸

　　3. 邏輯回歸的極大似然估計求解

　　4. 多類邏輯回歸

　　Softmax函數、—對多邏輯回歸、一對—邏輯回歸

　　(五)感知機

　　(六)支持向星機

　　1. 間隔與支持向星

　　2. 硬間隔支持向噩機及其對偶優化

　　3. 軟間隔支持向噩機

　　4. 支持向噩機的核方法

　　(七)深度學習

　　1. 神經元

　　2. 多層神經網絡的結構和損失函數

　　3. 多層神經網絡的優化

　　4. 卷積神經網絡

　　(八)決策樹與隨機森林

　　1. 決策樹的分類過程

　　2. 決策樹的劃分準則

　　信息增益、信息增益比、基尼不純度

　　3. 隨機森林

　　(九)集成學習

　　1.聚合算法(bagging) 2.提升算法(boosting) 3.堆疊算法(stacking) 四、無監督學習

　　(—)聚類

　　1. 層次聚類

　　2. K均值算法

　　3. 高斯混合模型

　　4. 期望最大化(EM)算法

　　(二)降維

　　1. 數據降維的概念和動機

　　2. 主成分分析五、學習理論

　　(一)特征選擇

　　1. 過濾法

　　2. 包裹法

　　3. 嵌入法

　　(二)模型選擇

　　1. 欠擬合與過擬合

　　2. 訓練-測試法

　　3. 交叉驗證法

　　留一交叉驗證、K折交叉驗證

　　(三)偏差-方差權衡

　　1. 預測誤差期望 (期望泛化誤差)

　　2. 預測誤差期望的預測偏差-方差分解

　　知識表示與處理

　　【考察目標】

　　1. 棠握知識圖譜的基本概念、基本流程;理解知識圖譜的常用任務、方法和模型。

　　2. 理解知識圖譜的基本方法和模型的數學原理。

　　3. 能夠運用知識圖譜的方法、模型和基本原理，通過計算和分析，解決知識圖譜應用領域的實際問題。

　　【考察范圍】

　　—、知識圖譜的定義和基本概念

　　(一)知識圖譜的定義

　　(二)知識圖譜的基本概念

　　1. 本體、語義網、知識庫、模式知識

　　2. 類、關系、屈性、實例

　　3. 知識表示、語義網絡、RDF、RDFS、OIVL

　　二、知識表示與建模(—)傳統知識表示方法1.霍恩子句和霍恩邏輯

　　2. 語義網絡

　　3. 描述邏輯

　　(二)語義網知識表示方法

　　1. RDF和RDFS

　　2. OWL和OWL2 Fragment

　　3. 知識圖譜查詢語言的表示三、知識存儲

　　(一)知識圖譜數據模型

　　(二)知識圖譜查詢語言

　　(三)知識圖譜存儲方法

　　1. 面向RDF的三元組數據庫

　　2. 原生圖數據庫

　　3. 知識圖譜數據庫比較 四、知識抽取與知識挖掘

　　(一)面向非結構化數據的知識抽取

　　1. 實體抽取

　　2. 關系抽取

　　3. 事件抽取

　　(二)面向結構化數據的知識抽取

　　1. 直接映射

　　2. R2RML

　　(三)實體鏈接五、知識融合

　　(—)本體概念層觸合

　　1. 本體映射分類

　　2. 本體映射方法

　　(二)實例層融合

　　1. 基于快速相似度計算的實例匹配方法

　　2. 基千規則的實例匹配方法

　　3. 基千學習的實例匹配方法六、知識圖譜推理

　　(一)什么是推理

　　(二)本體推理與規則推理

　　1. RDFS推理

　　2. 基于規則前向推理