2024年天津職業(yè)技術(shù)師范大學(xué)非全日制研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱

　　參考書(shū)目：

　　《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》，清華大學(xué)出版社，嚴(yán)蔚敏 吳偉民

　　考試內(nèi)容

　　1、數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析

　　(1) 什么是數(shù)據(jù)結(jié)構(gòu)。

　　(2) 抽象數(shù)據(jù)類(lèi)型及面向?qū)ο蟾拍睿簲?shù)據(jù)類(lèi)型;數(shù)據(jù)抽象與抽象數(shù)據(jù)類(lèi)型;面向?qū)ο蟮母拍?用于描述數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言。

　　(3) 數(shù)據(jù)結(jié)構(gòu)的抽象層次。

　　(4) 算法定義。

　　(5) 性能分析與度量：算法的性能標(biāo)準(zhǔn);算法的后期測(cè)試;算法的事前估計(jì);空間復(fù)雜度度量;時(shí)間復(fù)雜度度量;時(shí)間復(fù)雜度的漸進(jìn)表示法;漸進(jìn)的空間復(fù)雜度。

　　2、線性表

　　(1)線性表的定義和基本操作。

　　(2)線性表的實(shí)現(xiàn)：線性表的順序存儲(chǔ)結(jié)構(gòu);線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

　　(3)線性表的應(yīng)用。

　　3、棧和隊(duì)列

　　(1) 棧：棧的抽象數(shù)據(jù)類(lèi)型;棧的順序存儲(chǔ)表示;棧的鏈接存儲(chǔ)表示。

　　(2) 隊(duì)列 ：隊(duì)列的抽象數(shù)據(jù)類(lèi)型;隊(duì)列的順序存儲(chǔ)表示;隊(duì)列的鏈接存儲(chǔ)表示。

　　(3) 遞歸過(guò)程與遞歸工作棧;棧的遞歸實(shí)現(xiàn);棧和隊(duì)列的應(yīng)用。

　　(4) 優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義;優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示。

　　4、串

　　(1) 字符串的抽象數(shù)據(jù)類(lèi)型;串的存儲(chǔ)表示;字符串操作的實(shí)現(xiàn);字符串的模式匹配。

　　(2) 串的應(yīng)用。

　　5、數(shù)組和廣義表

　　(1)數(shù)組的定義和初始化;數(shù)組的順序存儲(chǔ)方式。

　　(2)順序表：順序表的定義和特點(diǎn);順序表的類(lèi)定義;順序表的查找、插入和刪除;使用順序表的事例。

　　(3)矩陣的壓縮存儲(chǔ)。

　　(4)廣義表：廣義表的概念;廣義表的表示及操作;廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn);廣義表的訪問(wèn)算法;廣義表的遞歸算法。

　　6、樹(shù)和二叉樹(shù)

　　(1)樹(shù)的概念。

　　(2)二叉樹(shù)：二叉樹(shù)的定義及其主要特征;二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu);二叉樹(shù)的遍歷。

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

　　(4) 堆;二叉排序樹(shù);平衡二叉樹(shù)。

　　(5) 樹(shù)和森林：樹(shù)的存儲(chǔ)結(jié)構(gòu);森林與二叉樹(shù)的轉(zhuǎn)換;樹(shù)和森林的遍歷。

　　(6) 樹(shù)的應(yīng)用：等價(jià)關(guān)系與等價(jià)類(lèi);確定等價(jià)類(lèi)的鏈表方法;最優(yōu)二叉樹(shù);哈夫曼(Huffman)樹(shù)和哈夫曼編碼;哈夫曼樹(shù)的應(yīng)用。

　　7、圖

　　(1) 圖的定義及基本術(shù)語(yǔ)。

　　(2) 圖的存儲(chǔ)及基本操作：數(shù)組表示法;鄰接矩陣;鄰接表;十字鏈表;

　　(3) 圖的遍歷：深度優(yōu)先搜索;廣度優(yōu)先搜索

　　(4) 圖的連通性問(wèn)題：無(wú)向圖的連通分量和生成樹(shù);有向圖的強(qiáng)連通分量;最小生成樹(shù)。

　　(5) 有向無(wú)環(huán)圖應(yīng)用及其復(fù)雜度分析：拓?fù)渑判?關(guān)鍵路徑;最短路徑。

　　8、查找

　　(1) 查找的基本概念。

　　(2) 靜態(tài)查找表：順序表的查找;有序表的查找;靜態(tài)樹(shù)表的查找;索引順序表的查找。

　　(3) 動(dòng)態(tài)查找表：折半查找;分塊查找;二叉排序樹(shù)查找;

　　(4) B_樹(shù)：B_樹(shù)的定義;B_樹(shù)的插入;B_樹(shù)的刪除

　　(5) 哈希表：哈希表與哈希方法;哈希函數(shù)的構(gòu)造方法;哈希沖突與解決沖突的方法;哈希表的查找及其分析。

　　9、排序

　　(1) 排序的基本概念及各種排序算法比較。

　　(2) 插入排序：直接插入排序;對(duì)分插入排序;鏈表插入排序;希爾排序。

　　(3) 交換排序：起泡排序;快速排序。

　　(4) 選擇排序：直接選擇排序;錦標(biāo)賽排序;堆排序。

　　(5) 歸并排序：歸并;迭代的歸并排序算法;遞歸的表歸并排序。

　　(6) 基數(shù)排序：多關(guān)鍵碼排序;鏈?zhǔn)交鶖?shù)排序。

　　(7) 內(nèi)部排序算法的應(yīng)用。

　　(8) 外排序：外排序的基本過(guò)程;k路平衡歸并;初始?xì)w并段的生成;最佳歸并樹(shù)。