《數據結構》是2023年湖南人文科技學院專升本考試科目之一，考試時長 120分鐘，滿分100分，考試題型：填空題、單項選擇題、判斷題、簡答題、應用與設計題等。2023年湖南人文科技學院專升本《數據結構》考試大綱已經公布，考試大綱明確了考試內容，考試題型，考試要求等。需要考試該科目的同學一定要研究考試大綱，院校會根據考試大綱進行出題，具體考試大綱內容請參考下方。

2023年湖南人文科技學院專升本《數據結構》考試大綱

一、考試形式：筆試（閉卷）

二、考試時量：120分鐘

三、卷面分數：100分

四、考核內容與要求

（一）緒論

1、考核知識點

（1）合適的數據結構在解決實際應用問題中的關鍵性；以及學習《數據結構》的意義。

（2）數據、數據元素、數據項、數據結構等基本概念。

（3）數據結構的四種邏輯結構和兩種存儲結構表示方法。

（4）抽象數據類型的表示和實現。

（5）算法的五個特點。

（6）算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。

（7）算法描述和算法分析的方法，對于一般算法能分析出時間復雜度。

2、考核要求

（1）識記

1）數據結構的基本概念和術語。

2）合適的數據結構在解決實際應用問題中的關鍵性，以及學習《數據結構》的意義。

3）數據結構的四種邏輯結構和兩種存儲結構表示方法。

（2）理解

算法的描述和分析：算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度。

（二）線性表

1、考核知識點

（1）線性表的類型定義。

（2）順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。

（3）鏈式表示和實現，單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。

（4）單鏈表上實現的建表、查找、插入和刪除等基本算法及其時間復雜度。

（5）循環(huán)鏈表上尾指針取代頭指針的作用。

（6）單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。

（7）雙向鏈表的定義和相關算法。

（8）順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優(yōu)的時空性能。

2、考核要求

（1）識記

1）線性表的邏輯結構特征；

2）線性表上定義的基本運算，并利用基本運算構造出較復雜的運算。

（2）理解

1)順序表和鏈表的比較，各自的優(yōu)缺點。

2）針對線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲結構才能取得較優(yōu)的時空性能。

（3）綜合應用

1）順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。

2）單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；

3）單鏈表上實現的建表、查找、插入和刪除等基本算法及其時間復雜度。

4）循環(huán)鏈表中尾指針取代頭指針的作用，

5）單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。

6）雙鏈表的定義和相關算法。

（三）棧和隊列

1、考核知識點

（1）棧的抽象數據類型的定義

（2）棧的表示和實現

（3）棧的簡單應用

（4）抽象數據類型隊列的定義

（5）隊列的鏈式表示和實現

（6）隊列的順序表示和實現

2、考核要求

（1）理解

棧和隊列的特點，棧和隊列各自的使用情況。

（2）綜合應用

1）棧的邏輯結構特點，棧與線性表的異同。

2）順序棧和鏈棧上實現進棧、退棧等基本算法。

3）利用棧解決簡單的實際問題。

4）隊列邏輯結構特點，隊列與線性表的異同。

5）順序隊列（主要是循環(huán)隊列）和鏈隊列上實現的入隊、出隊等基本算法。

6）順序隊列的“假溢出”現象及其采用循環(huán)隊列進行解決的方法。

（四）串

1、考核知識點

（1）串的定義、空串、空格串、子串、主串、串相等。

（2）串的基本操作。

（3）串的順序存儲結構及在順序存儲結構下基本操作的實現。

（4）串的堆分配存儲表示及其在堆分配存儲結構下基本操作的實現。

（5）串的鏈式存儲表示

2、考核要求

（1）理解

串的有關概念及其基本運算。

（2）簡單應用

1）串的三種存儲表示。

2）使用串解決與串相關的簡單的應用問題。

（五）數組和廣義表

1、考核知識點

（1）數組的順序存儲結構。

（2）二維數組的按行存儲及按列存儲和計算數組元素的地址計算公式。

（3）矩陣的壓縮存儲、特殊矩陣的表示。

2、考核要求

（1）理解

1）多維數組的邏輯結構特征。

2）多維數組的順序存儲結構及其地址計算方式。

3）特殊矩陣和稀疏矩陣的概念。

4）疏矩陣的壓縮存儲方式——三元組表。

（六）樹和二叉樹

1、考核知識點

（1）樹的定義和術語。

（2）二叉樹(完全二叉樹、滿二叉樹)的定義和性質(結論)、二叉樹的存儲結構——順序表示法和鏈表表示法。

（3）二叉樹的三種遍歷方法及相應的遞歸算法。

（4）樹的存儲表示法——孩子表示法、雙親表示法、孩子兄弟表示法。

（5）樹和森林及二叉樹的轉換方法。

（6）樹的路徑長度、樹的帶權路徑長度、赫夫曼樹（最優(yōu)二叉樹）的構造方法。

（7）赫夫曼編碼方法。

2、考核要求

（1）理解

1)樹的邏輯結構特征。

2)樹的不同表示方法。

3)樹的常用術語及含義。

4)樹和森林與二叉樹之間的轉換方法。

5)樹的各種存儲結構及其特點。

6)樹的遍歷方法。

（2）簡單應用

1)二叉樹的定義及樹與二叉樹的差別。

2)二叉樹的性質，了解相應的證明方法。

3)二叉樹的兩種存儲結構、特點及適用范圍。

4)最優(yōu)二叉樹和前綴編碼的概念及特點。

5)赫夫曼算法的思想。

6)根據給定的葉結點及其權值構造出相應的最優(yōu)二叉樹。

7)根據最優(yōu)二叉樹構造對應的赫夫曼編碼。

（3）綜合應用

1)二叉樹的三種遍歷算法，理解其執(zhí)行過程。

2)根據不同的遍歷方法，應能得出其相應的結點訪問次序。

（七）圖

1、考核知識點

（1）圖的邏輯結構特征。

（2）圖的常用術語及含義。

（3）圖的鄰接矩陣表示法存儲結構。

（4）圖的鄰接表表示法。

（5）圖的深度優(yōu)先遍歷。

（6）圖的廣度優(yōu)先遍歷。

（7）生成樹和最小生成樹。

（8）構造最小生成樹的PRIM算法思想。

（9）構造最小生成樹的Kruskal算法思想。

（10）拓撲排序。

（11）關鍵路徑。

（12）關于最短路徑的算法——Dijkstra算法思想。

2、考核要求

（1）理解

1)圖的邏輯結構及特征。

2)圖的常用術語及含義。

3)生成樹和最小生成樹的概念。

4)對給定的圖遍歷，畫出深度優(yōu)先和廣度優(yōu)先生成樹或森林。

5)Prim和 Kruskal算法的基本思想。

6)要求對給定的連通圖，根據Prim和Kruskal算法構造最小生成樹。。

7)求單源點的最短路徑問題的Dijkstra算法的基本思想。

8)拓撲排序的基本思想和步驟。

9)對給定的有向圖，若拓撲序列存在，則要求寫出一個或多個拓撲序列。

（2）簡單應用

1）圖的鄰接矩陣表示法和鄰接表表示法。

2）根據應用問題的特點選擇合適的存儲結構。

3）連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法。

4）確定兩種遍歷的頂點訪問序列。

5）圖的兩種遍歷和樹的遍歷之間的關系。

6）兩種遍歷算法分別使用的數據結構（棧和隊列）。

（八）查找

1、考核知識點

（1）查找的定義關鍵字、查找、平均查找長度。

（2）靜態(tài)查找表的查找算法（順序查找、折半查找、分塊查找(索引順序表的查找)）其效率(最壞和平均長度)。

（3）二叉排序樹的查找算法及其效率。

（4）平衡二叉樹的定義。

（5）哈希法的特點。

（6）哈希函數和散列地址。

（7）處理沖突的方法：開放定址法和鏈地址法。開放定址法又分為線性探測再散列、二次探測再散列和偽隨機探測再散列。

2、考核要求

（1）識記

1)查找在數據處理中的重要性。

2)查找成功、不成功的含義。

（2）簡單應用

1)順序查找、折半查找、分塊查找的基本思想、算法實現和查找效率分析。

2）二叉排序樹和二叉平衡樹的定義、特點

3）建立一棵二叉排序樹的過程就是對輸入序列的排序過程，輸入序列對所建立的二叉排序樹形態(tài)的影響

4）哈希表、哈希函數、哈希地址（散列地址）、裝填因子等有關概念

5）哈希函數的構造方法和解決沖突的方法

（九）內部排序

1、考核知識點

（1）排序的目的、分類和排序方法的穩(wěn)定性的定義。

（2）插入排序：直接插入排序的算法、折半插入排序的算法、希爾排序的思想。

（3）選擇排序的思想

（4）堆排序的方法、堆的定義、初始堆的建立。

（5）起泡排序的思想。

（6）快速排序的算法、快速排序的最壞情況時間復雜度的分析。

2、考核要求

（1）識記

1）排序在數據處理中的重要性。

1)排序方法穩(wěn)定性的含義。

2)排序方法的分類及算法好壞的評判標準。

（2）理解

1)分類排序和其它幾類排序方法的區(qū)別。

（3）簡單應用

1)堆、極小堆、極大堆、堆頂等有關概念和定義。

2)堆的性質及堆與完全二叉樹的關系。

3)直接選擇排序和堆排序的基本思想和算法實現。

4)針對給定的輸入序列，寫出堆排序的排序過程。

（4）綜合應用

1)針對給定的輸入序列，要能寫出直接插入排序的排序過程。

2)起泡排序的基本思想。

3)快速排序的基本思想和算法實現，以及在最好、最壞和平均情況下的時間性能分析，了解算法的穩(wěn)定性。

4)樞軸元素的選擇對排序的影響。

針對給定的輸入序列，能寫出快速排序的排序過程。

五、題型

填空題10分（每空2分）；單項選擇題40分（每小題2分）；

判斷題10分（每小題1分）；簡答題10分（每小題5分）；

應用與設計題30分（2-3個小題）

六、參考教材

1、主要教材：李筠，姜學軍主編，《數據結構（高職高專精品課程規(guī)劃教材計算機系列）》. 清華大學出版社，2008年8月

2、參考教材：嚴蔚敏,吳偉民主編.數據結構（C語言版）.清華大學出版社，2011年7月

本文資料來源：http://www.huhst.edu.cn/jwc2019/info/1045/3868.htm

研究考試大綱，對大綱中的考點及相關要求進行認真研究，是應考的關鍵。正在備考專升本的同學，關注湖南樂貞教育網站可以了解更多專升本的考試信息。如果在學習上有困難，自制力差，可以在下方留下你的聯系方式，我們的老師會針對你的學習情況給出建議。

部分內容來源于網絡轉載、學生投稿，如有侵權或對本站有任何意見、建議或者投訴，請聯系郵箱（1296178999@qq.com）反饋。 未經本站授權，不得轉載、摘編、復制或者建立鏡像， 如有違反，本站將追究法律責任！