題型分布

　　一、選擇題：(40道題，每題2分，共80分)數(shù)據(jù)結(jié)構(gòu)：16道題

　　機器學(xué)習(xí)：16道題

　　知識表示與處理：8道題

　　二、綜合問答題：(8道題，共70分)數(shù)據(jù)結(jié)構(gòu)：3題(共28分)

　　機器學(xué)習(xí)：3題(共28分)

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

　　考試大綱

　　數(shù)據(jù)結(jié)構(gòu)

　　【考查目標(biāo)】

　　1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異以及各種基本操作的實現(xiàn)。

　　2. 棠握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。

　　3. 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解;具備采用C++、python語言設(shè)計與實 現(xiàn)算法的能力。

　　[考查范圍】

　　一、復(fù)雜度分析和遞歸

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

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

　　(三)初級動態(tài)規(guī)劃算法二、鏈表、棧、隊列

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

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

　　(三)棧和隊列的順序存儲結(jié)構(gòu)

　　(四)棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

　　(—)樹的基本概念

　　(二)二叉樹

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

　　2. 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

　　3. 二叉樹的遍歷

　　4. 平衡二叉樹

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

　　6. AVL樹四、圖

　　(—)圖的概念

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

　　1. 鄰接矩陣法

　　2. 鄰接表法

　　(三)圖的遍歷

　　1. 深度優(yōu)先搜索

　　2. 廣度優(yōu)先搜索

　　(四)圖的基本應(yīng)用

　　1. 最短路徑

　　2. 拓撲排序

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

　　(-)查找的基本概念

　　(二)順序查找法

　　(三)折半查找法

　　(四)樹在查找的應(yīng)用

　　(五)哈希(Hash)表

　　(六)局部敏感哈希算法

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

　　(-)排序的基本概念

　　(二)插入排序

　　1. 直接插入排序

　　2. 折半插入排序

　　(三)冒泡排序

　　(四)選擇排序

　　(五)快速排序

　　(六)堆排序

　　(七)基數(shù)排序

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

　　(九)排序算法的應(yīng)用

　　機器學(xué)習(xí)

　　【考察目標(biāo)】

　　1. 棠握機器學(xué)習(xí)的基本概念、基本流程;理解機器學(xué)習(xí)的常用任務(wù)、方法和模型。

　　2. 理解機器學(xué)習(xí)方法和模型的數(shù)學(xué)原理和優(yōu)缺點;能夠結(jié)合具體任務(wù)對模型進行評估和選 擇。

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

　　【考察范圍】

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

　　(二)機器學(xué)習(xí)的基本概念

　　1. 樣本、特征、標(biāo)簽、數(shù)據(jù)集

　　2. 訓(xùn)練、測試、模型參數(shù)、損失函數(shù)、誤差

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

　　(—)線性回歸

　　1. 線性回歸模型

　　2. 線性回歸模型的優(yōu)化

　　正規(guī)方程法、梯度下降法、隨機梯度下降、牛頓法

　　(二)非線性回歸的概念

　　(三)正則化線性回歸

　　1. 嶺回歸

　　2. 套索(LASSO)回歸

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

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

　　(二)K最近鄰算法

　　(三)貝葉斯分類器

　　1. 生成貝葉斯分類器

　　2. 樸素貝葉斯分類器

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

　　4. 線性判別分析

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

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

　　2. 二分類邏輯回歸

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

　　4. 多類邏輯回歸

　　Softmax函數(shù)、—對多邏輯回歸、一對—邏輯回歸

　　(五)感知機

　　(六)支持向星機

　　1. 間隔與支持向星

　　2. 硬間隔支持向噩機及其對偶優(yōu)化

　　3. 軟間隔支持向噩機

　　4. 支持向噩機的核方法

　　(七)深度學(xué)習(xí)

　　1. 神經(jīng)元

　　2. 多層神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和損失函數(shù)

　　3. 多層神經(jīng)網(wǎng)絡(luò)的優(yōu)化

　　4. 卷積神經(jīng)網(wǎng)絡(luò)

　　(八)決策樹與隨機森林

　　1. 決策樹的分類過程

　　2. 決策樹的劃分準(zhǔn)則

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

　　3. 隨機森林

　　(九)集成學(xué)習(xí)

　　1.聚合算法(bagging) 2.提升算法(boosting) 3.堆疊算法(stacking) 四、無監(jiān)督學(xué)習(xí)

　　(—)聚類

　　1. 層次聚類

　　2. K均值算法

　　3. 高斯混合模型

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

　　(二)降維

　　1. 數(shù)據(jù)降維的概念和動機

　　2. 主成分分析五、學(xué)習(xí)理論

　　(一)特征選擇

　　1. 過濾法

　　2. 包裹法

　　3. 嵌入法

　　(二)模型選擇

　　1. 欠擬合與過擬合

　　2. 訓(xùn)練-測試法

　　3. 交叉驗證法

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

　　(三)偏差-方差權(quán)衡

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

　　2. 預(yù)測誤差期望的預(yù)測偏差-方差分解

　　知識表示與處理

　　【考察目標(biāo)】

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

　　2. 理解知識圖譜的基本方法和模型的數(shù)學(xué)原理。

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

　　【考察范圍】

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

　　(一)知識圖譜的定義

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

　　1. 本體、語義網(wǎng)、知識庫、模式知識

　　2. 類、關(guān)系、屈性、實例

　　3. 知識表示、語義網(wǎng)絡(luò)、RDF、RDFS、OIVL

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

　　2. 語義網(wǎng)絡(luò)

　　3. 描述邏輯

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

　　1. RDF和RDFS

　　2. OWL和OWL2 Fragment

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

　　(一)知識圖譜數(shù)據(jù)模型

　　(二)知識圖譜查詢語言

　　(三)知識圖譜存儲方法

　　1. 面向RDF的三元組數(shù)據(jù)庫

　　2. 原生圖數(shù)據(jù)庫

　　3. 知識圖譜數(shù)據(jù)庫比較 四、知識抽取與知識挖掘

　　(一)面向非結(jié)構(gòu)化數(shù)據(jù)的知識抽取

　　1. 實體抽取

　　2. 關(guān)系抽取

　　3. 事件抽取

　　(二)面向結(jié)構(gòu)化數(shù)據(jù)的知識抽取

　　1. 直接映射

　　2. R2RML

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

　　(—)本體概念層觸合

　　1. 本體映射分類

　　2. 本體映射方法

　　(二)實例層融合

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

　　2. 基千規(guī)則的實例匹配方法

　　3. 基千學(xué)習(xí)的實例匹配方法六、知識圖譜推理

　　(一)什么是推理

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

　　1. RDFS推理

　　2. 基于規(guī)則前向推理