2024年桂林電子科技大學(xué)非全日制研究生招生考試《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

　　一、考試性質(zhì)

　　本課程是人工智能專業(yè)、機(jī)器人專業(yè)和大數(shù)據(jù)科學(xué)專業(yè)的專業(yè)基礎(chǔ)必修課，其涵蓋知識(shí)是相關(guān)專業(yè)研究生開(kāi)展創(chuàng)新研究必須具備的基礎(chǔ)。

　　二、考查目標(biāo)

　　本課程主要考核線性表、樹(shù)、圖數(shù)據(jù)結(jié)構(gòu)表示方法、操作及應(yīng)用; 常用查找與排序算法;算法時(shí)間、空間復(fù)雜度分析等。

　　三、適用范圍

　　本考試大綱適用于我校 085410 人工智能專業(yè)的碩士研究生招生考試。

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

　　1. 試卷滿分及考試時(shí)間

　　試卷滿分：150 分;考試時(shí)間：180 分鐘。

　　2. 試卷內(nèi)容結(jié)構(gòu)

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

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

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

　　3. 試卷題型結(jié)構(gòu)及分值比例

　　命題可根據(jù)考核需要，對(duì)試卷內(nèi)容結(jié)構(gòu)、題型結(jié)構(gòu)及分值比例做適當(dāng)調(diào)整。

　　五、考查內(nèi)容

　　1. 數(shù)據(jù)結(jié)構(gòu)緒論

　　(1) 數(shù)據(jù)結(jié)構(gòu)基本概念

　　(2) 數(shù)據(jù)抽象方法

　　(3) 算法描述方法，算法時(shí)間、空間復(fù)雜度分析

　　2. 線性表

　　(1) 線性表的定義及基本操作(創(chuàng)建、插入、刪除、查找和修改)

　　(2) 線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

　　(3) 單循環(huán)鏈表、雙循環(huán)鏈表和雙鏈表的實(shí)現(xiàn)與應(yīng)用

　　(4) 線性表的應(yīng)用：一元多項(xiàng)式運(yùn)算、Josephus 問(wèn)題

　　(5) 矩陣以及稀疏矩陣的順序表示

　　3. 字符串

　　(1) 字符串的基本概念、邏輯結(jié)構(gòu)和抽象數(shù)據(jù)類型

　　(2) 字符串的順序表示和鏈?zhǔn)奖硎?/p>

　　(3) 字符串的模式匹配

　　4. 棧和隊(duì)列

　　(1) 棧和隊(duì)列的基本概念以及基本操作的實(shí)現(xiàn)

　　(2) 棧和隊(duì)列的順序表示和鏈接表示

　　(3) 使用棧進(jìn)行遞歸函數(shù)與非遞歸函數(shù)的轉(zhuǎn)換;

　　(4) 棧與隊(duì)列的應(yīng)用：表達(dá)式計(jì)算;迷宮問(wèn)題、農(nóng)夫過(guò)河問(wèn)題; 銀行業(yè)務(wù)模擬;

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

　　(1) 樹(shù)的基本概念

　　(2) 二叉樹(shù)的定義以及主要特征

　　(3) 二叉樹(shù)的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

　　(4) 二叉樹(shù)的周游

　　(5) 線索二叉樹(shù)的基本概念和構(gòu)造

　　(6) 樹(shù)與樹(shù)林的定義以及存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

　　(7) 樹(shù)與樹(shù)林的周游

　　(8) 樹(shù)與二叉樹(shù)的應(yīng)用：哈夫曼樹(shù)哈夫曼編碼、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換

　　6. 圖

　　(1) 圖的基本概念、存儲(chǔ)結(jié)構(gòu)表示以及基本操作

　　(2) 圖的周游：深度優(yōu)先周游和廣度優(yōu)先周游

　　(3) 圖的應(yīng)用:最小生成樹(shù)的構(gòu)造、最短路徑、Dijkstra 算法和Floyd 算法等。

　　(4) 面向特定應(yīng)用的圖：AOV 網(wǎng)和AOE 網(wǎng)

　　7. 集合與字典

　　(1) 集合與字典的定義以及抽象數(shù)據(jù)類型

　　(2) 集合的位向量和單鏈表表示

　　(3) 字典的順序表示和散列表示

　　(4) 二分法檢索

　　8. 高級(jí)字典結(jié)構(gòu)

　　(1) 字符樹(shù)的定義以及表示

　　(2) 二叉排序樹(shù)的定義、構(gòu)造、插入、刪除和檢索

　　(3) 最佳二叉排序樹(shù)的基本概念以及等概率搜索

　　(4) 平衡二叉樹(shù)的概念和調(diào)整平衡的模式

　　(5) B+樹(shù)、B-樹(shù)的定義、查找、插入和刪除

　　9. 排序

　　(1) 排序的基本概念

　　(2) 插入排序：直接插入法、二分法插入、表插入排序、Shell排序

　　(3) 選擇排序：直接選擇排序和堆排序

　　(4) 交換排序：氣泡排序和快速排序

　　(5) 分配排序：基數(shù)排序

　　(6) 歸并排序：內(nèi)排序和外排序

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

　　六、參考書(shū)目

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