一、考試性質(zhì)

　　本課程是人工智能專(zhuān)業(yè)、機(jī)器人專(zhuān)業(yè)和大數(shù)據(jù)科學(xué)專(zhuān)業(yè)的專(zhuān)業(yè)基

　　礎(chǔ)必修課，其涵蓋知識(shí)是相關(guān)專(zhuān)業(yè)研究生開(kāi)展創(chuàng)新研究必須具備的基

　　礎(chǔ)。

　　二、考查目標(biāo)

　　本課程主要考核線(xiàn)性表、樹(shù)、圖數(shù)據(jù)結(jié)構(gòu)表示方法、操作及應(yīng)用；

　　常用查找與排序算法；算法時(shí)間、空間復(fù)雜度分析等。

　　三、適用范圍

　　本考試大綱適用于我校人工智能學(xué)院的081200計(jì)算機(jī)科學(xué)與技

　　術(shù)和085410人工智能專(zhuān)業(yè)的碩士研究生招生考試。

　　四、考試形式和試卷結(jié)構(gòu)

　?。ㄒ唬┰嚲頋M(mǎn)分及考試時(shí)間

　　試卷滿(mǎn)分：150分；考試時(shí)間：180分鐘。

　?。ǘ┰嚲韮?nèi)容結(jié)構(gòu)

　　1)數(shù)據(jù)結(jié)構(gòu)及算法的基礎(chǔ)知識(shí)：約25分；

　　2)數(shù)據(jù)結(jié)構(gòu)及算法的應(yīng)用與分析：約95分；

　　3)數(shù)據(jù)結(jié)構(gòu)及算法的代碼分析、設(shè)計(jì)與實(shí)現(xiàn)：約30分。

　?。ㄈ┰嚲眍}型結(jié)構(gòu)及分值比例

　　五、考查內(nèi)容

　　1．緒論

　?。?）數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容

　　（2）基本概念和術(shù)語(yǔ)

　?。?）抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)

　?。?）算法和算法分析

　　2．線(xiàn)性表

　?。?）線(xiàn)性表的定義和特點(diǎn)

　　（2）線(xiàn)性表的類(lèi)型定義

　?。?）線(xiàn)性表的順序表示和實(shí)現(xiàn)

　?。?）線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

　?。?）順序表和鏈表的比較

　?。?）線(xiàn)性表的應(yīng)用

　　3.棧和隊(duì)列

　　（1）棧和隊(duì)列的定義和特點(diǎn)

　?。?）棧的表示和操作的實(shí)現(xiàn)

　　（3）棧與遞歸

　?。?）隊(duì)列的表示和操作的實(shí)現(xiàn)

　?。?）棧與隊(duì)列的應(yīng)用：表達(dá)式計(jì)算；迷宮問(wèn)題等

　　4.串、數(shù)組和廣義表

　?。?）串的類(lèi)型定義、存儲(chǔ)結(jié)構(gòu)及其運(yùn)算

　?。?）數(shù)組的定義、存儲(chǔ)以及特殊矩陣的壓縮存儲(chǔ)

　　5.樹(shù)和二叉樹(shù)

　?。?）樹(shù)和二叉樹(shù)的定義

　?。?）樹(shù)和二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義=（3）二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)

　?。?）遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)

　　（5）樹(shù)和森林

　?。?）哈夫曼樹(shù)及其應(yīng)用

　　6.圖

　　（1）圖的定義和基本術(shù)語(yǔ)

　?。?）案例引入

　?。?）圖的類(lèi)型定義

　?。?）圖的存儲(chǔ)結(jié)構(gòu)

　　（5）圖的遍歷

　?。?）圖的應(yīng)用：最小生成樹(shù)、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑等

　　7.查找

　?。?）查找的基本概念

　　（2）線(xiàn)性表的查找：順序查找、折半查找、分塊查找

　　（3）樹(shù)表的查找：二叉排序樹(shù)、平衡二叉樹(shù)、B-樹(shù)、B+樹(shù)

　?。?）散列表的查找

　　8.排序

　?。?）基本概念和排序方法概述

　?。?）插入排序：直接插入排序、折半插入排序、希爾排序

　　（3）交換排序：冒泡排序、快速排序

　?。?）選擇排序：簡(jiǎn)單選擇排序、樹(shù)形選擇排序、堆排序

　?。?）歸并排序

　?。?）基數(shù)排序

　?。?）外部排序

　?。?）各種排序時(shí)間、空間復(fù)查度和算法穩(wěn)定性等方面綜合比較

　　六、參考書(shū)目

　　嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版），人民郵電出版社，2017年