2024年湖南師范大學(xué)非全日制研究生招生考試《數(shù)據(jù)結(jié)構(gòu)（C語言）》考試大綱

　　考試內(nèi)容及要點

　　數(shù)據(jù)結(jié)構(gòu)考試旨在考察學(xué)生所具有的數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計的基礎(chǔ)知識、基礎(chǔ)思想和基礎(chǔ)技能，考察學(xué)生對典型數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法的掌握程度，以及使用這些數(shù)據(jù)結(jié)構(gòu)和算法解決實際問題的能力。本門課程考核要求由低到高共分為“了解”、“掌握”、“熟練掌握”三個層次。其含義：了解，指學(xué)生能知道所學(xué)知識，能在有關(guān)問題中認識或再現(xiàn)它們掌握，指學(xué)生清楚地理解所學(xué)知識(例如鏈表的基本操作實現(xiàn)等)，并且能在基本運算和簡單應(yīng)用中正確地使用它們；熟練掌握，指學(xué)生能較為深刻理解所學(xué)知識，在此基礎(chǔ)上能夠準確、熟練地使用它們，以及分析解決較為簡單的實際問題。

　　第1章 緒論

　　(一) 考核知識點

　　1.數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語和概念

　　2.關(guān)于算法描述與算法分析

　　(二) 考核要求

　　1.掌握數(shù)據(jù)結(jié)構(gòu)的概念，能深刻領(lǐng)會相關(guān)的基本術(shù)語。

　　2.了解算法的時間復(fù)雜度和空間復(fù)雜度的概念，能知曉算法的效率的含義。

　　第2章 線性表

　　(一)考核知識點

　　1.線性表的定義和基本運算

　　2.線性表的順序存儲結(jié)構(gòu)

　　3.線性表的鏈式存儲結(jié)構(gòu)

　　(二)考核要求

　　1.了解線性表的邏輯結(jié)構(gòu)特性，掌握線性表的兩種存儲結(jié)構(gòu)。

　　2.熟練掌握順序表、鏈表上各種基本操作的實現(xiàn)。

　　第3章 棧和隊列

　　1.棧

　　(1)棧的定義及基本運算

　　(2)棧的存儲結(jié)構(gòu)及基本運算的實現(xiàn)

　　(3)棧的簡單應(yīng)用

　　2.隊列

　　(1)隊列的定義及基本運算

　　(2)隊列的存儲結(jié)構(gòu)及基本運算的實現(xiàn)

　　(3)隊列的簡單應(yīng)用

　　(二)考核要求

　　1.掌握棧和隊列的特性以及它們之間的差異。

　　2.重點掌握順序棧和鏈棧上實現(xiàn)棧的基本操作，注意棧滿和棧空的條件。

　　3.重點掌握順序隊列和鏈隊列上實現(xiàn)隊列的基本操作，注意循環(huán)隊列上隊滿和隊空的條件。

　　4.了解棧和隊列的簡單應(yīng)用。

　　第4章 串

　　(一)考核知識點

　　1.串的基本概念

　　2.串的存儲結(jié)構(gòu)

　　3.串的基本操作

　　(二)考核要求

　　1.掌握串的特性，串和線性表之間的關(guān)系

　　2.掌握串的各種存儲結(jié)構(gòu)，比較它們的優(yōu)缺點。

　　3.理解串的各種基本操作。

　　第5章 樹和二叉樹

　　(一)考核的知識點

　　1.樹的定義和基本術(shù)語

　　2.二叉樹的定義和基本性質(zhì)；二叉樹的存儲結(jié)構(gòu)；二叉樹的遍歷；

　　3.樹的存儲結(jié)構(gòu)、森林與二叉樹的轉(zhuǎn)換、樹和森林的遍歷。

　　(二)考核要求

　　1.掌握樹的定義和基本術(shù)語，掌握二叉樹的遞歸定義.表示方式；

　　2.重點掌握二樹叉的遍歷。

　　3.掌握二叉排序樹的定義和建立、顯示與刪除二叉排序樹的基本操作。

　　4.熟練掌握樹、森林和二叉樹之間的轉(zhuǎn)換方法；

　　5.熟練掌握哈夫曼樹的建立過程和哈夫曼編碼。

　　第6章 圖

　　(一)考核知識點

　　1、圖結(jié)構(gòu)的基本概念

　　2、圖的存儲結(jié)構(gòu)。

　　3、圖的遍歷和求圖的連通分量。

　　4、生成樹和最小生成樹；

　　5、最短路徑

　　(二)考核要求

　　1、掌握圖的定義、特性和相關(guān)概念。

　　2、深刻理解圖的最小生成樹和最短路徑的算法，并能運用這些算法解決綜合問題。

　　第7章 查找

　　(一)考核知識點

　　1、順序表的查找

　　2、樹表的查找

　　3、哈希表及其查找

　　(二)考核要求

　　1、掌握各種查找的特性以及它們之間的差異，知道使用各種查找方法的條件。

　　2、重點掌握順序查找、二分查找和分塊查找的基本算法。

　　3、重點掌握構(gòu)造哈希函數(shù)的方法和哈希沖突解決方法。能夠按照給定條件構(gòu)造哈希表。

　　第8章 排序

　　(一)考核知識點

　　1、一般概念

　　2、插入排序、選擇排序、歸并排序、基數(shù)排序。

　　3、有關(guān)內(nèi)部排序方法的討論。

　　(二)考核要求

　　1、掌握各種排序的基本思想及其特點，熟悉各種排序方法的排序過程。

　　2、掌握各種排序方法的優(yōu)缺點。