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

2023年湖南人文科技學院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

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

二、考試時量：120分鐘

三、卷面分數(shù)：100分

四、考核內(nèi)容與要求

（一）緒論

1、考核知識點

（1）合適的數(shù)據(jù)結(jié)構(gòu)在解決實際應(yīng)用問題中的關(guān)鍵性；以及學習《數(shù)據(jù)結(jié)構(gòu)》的意義。

（2）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本概念。

（3）數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)表示方法。

（4）抽象數(shù)據(jù)類型的表示和實現(xiàn)。

（5）算法的五個特點。

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

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

2、考核要求

（1）識記

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

2）合適的數(shù)據(jù)結(jié)構(gòu)在解決實際應(yīng)用問題中的關(guān)鍵性，以及學習《數(shù)據(jù)結(jié)構(gòu)》的意義。

3）數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)表示方法。

（2）理解

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

（二）線性表

1、考核知識點

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

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

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

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

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

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

（7）雙向鏈表的定義和相關(guān)算法。

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

2、考核要求

（1）識記

1）線性表的邏輯結(jié)構(gòu)特征；

2）線性表上定義的基本運算，并利用基本運算構(gòu)造出較復(fù)雜的運算。

（2）理解

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

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

（3）綜合應(yīng)用

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

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

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

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

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

6）雙鏈表的定義和相關(guān)算法。

（三）棧和隊列

1、考核知識點

（1）棧的抽象數(shù)據(jù)類型的定義

（2）棧的表示和實現(xiàn)

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

（4）抽象數(shù)據(jù)類型隊列的定義

（5）隊列的鏈式表示和實現(xiàn)

（6）隊列的順序表示和實現(xiàn)

2、考核要求

（1）理解

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

（2）綜合應(yīng)用

1）棧的邏輯結(jié)構(gòu)特點，棧與線性表的異同。

2）順序棧和鏈棧上實現(xiàn)進棧、退棧等基本算法。

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

4）隊列邏輯結(jié)構(gòu)特點，隊列與線性表的異同。

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

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

（四）串

1、考核知識點

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

（2）串的基本操作。

（3）串的順序存儲結(jié)構(gòu)及在順序存儲結(jié)構(gòu)下基本操作的實現(xiàn)。

（4）串的堆分配存儲表示及其在堆分配存儲結(jié)構(gòu)下基本操作的實現(xiàn)。

（5）串的鏈式存儲表示

2、考核要求

（1）理解

串的有關(guān)概念及其基本運算。

（2）簡單應(yīng)用

1）串的三種存儲表示。

2）使用串解決與串相關(guān)的簡單的應(yīng)用問題。

（五）數(shù)組和廣義表

1、考核知識點

（1）數(shù)組的順序存儲結(jié)構(gòu)。

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

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

2、考核要求

（1）理解

1）多維數(shù)組的邏輯結(jié)構(gòu)特征。

2）多維數(shù)組的順序存儲結(jié)構(gòu)及其地址計算方式。

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

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

（六）樹和二叉樹

1、考核知識點

（1）樹的定義和術(shù)語。

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

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

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

（5）樹和森林及二叉樹的轉(zhuǎn)換方法。

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

（7）赫夫曼編碼方法。

2、考核要求

（1）理解

1)樹的邏輯結(jié)構(gòu)特征。

2)樹的不同表示方法。

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

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

5)樹的各種存儲結(jié)構(gòu)及其特點。

6)樹的遍歷方法。

（2）簡單應(yīng)用

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

2)二叉樹的性質(zhì)，了解相應(yīng)的證明方法。

3)二叉樹的兩種存儲結(jié)構(gòu)、特點及適用范圍。

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

5)赫夫曼算法的思想。

6)根據(jù)給定的葉結(jié)點及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹。

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

（3）綜合應(yīng)用

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

2)根據(jù)不同的遍歷方法，應(yīng)能得出其相應(yīng)的結(jié)點訪問次序。

（七）圖

1、考核知識點

（1）圖的邏輯結(jié)構(gòu)特征。

（2）圖的常用術(shù)語及含義。

（3）圖的鄰接矩陣表示法存儲結(jié)構(gòu)。

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

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

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

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

（8）構(gòu)造最小生成樹的PRIM算法思想。

（9）構(gòu)造最小生成樹的Kruskal算法思想。

（10）拓撲排序。

（11）關(guān)鍵路徑。

（12）關(guān)于最短路徑的算法——Dijkstra算法思想。

2、考核要求

（1）理解

1)圖的邏輯結(jié)構(gòu)及特征。

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

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

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

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

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

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

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

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

（2）簡單應(yīng)用

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

2）根據(jù)應(yīng)用問題的特點選擇合適的存儲結(jié)構(gòu)。

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

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

5）圖的兩種遍歷和樹的遍歷之間的關(guān)系。

6）兩種遍歷算法分別使用的數(shù)據(jù)結(jié)構(gòu)（棧和隊列）。

（八）查找

1、考核知識點

（1）查找的定義關(guān)鍵字、查找、平均查找長度。

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

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

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

（5）哈希法的特點。

（6）哈希函數(shù)和散列地址。

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

2、考核要求

（1）識記

1)查找在數(shù)據(jù)處理中的重要性。

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

（2）簡單應(yīng)用

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

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

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

4）哈希表、哈希函數(shù)、哈希地址（散列地址）、裝填因子等有關(guān)概念

5）哈希函數(shù)的構(gòu)造方法和解決沖突的方法

（九）內(nèi)部排序

1、考核知識點

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

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

（3）選擇排序的思想

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

（5）起泡排序的思想。

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

2、考核要求

（1）識記

1）排序在數(shù)據(jù)處理中的重要性。

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

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

（2）理解

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

（3）簡單應(yīng)用

1)堆、極小堆、極大堆、堆頂?shù)扔嘘P(guān)概念和定義。

2)堆的性質(zhì)及堆與完全二叉樹的關(guān)系。

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

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

（4）綜合應(yīng)用

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

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

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

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

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

五、題型

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

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

應(yīng)用與設(shè)計題30分（2-3個小題）

六、參考教材

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

2、參考教材：嚴蔚敏,吳偉民主編.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社，2011年7月

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

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

部分內(nèi)容來源于網(wǎng)絡(luò)轉(zhuǎn)載、學生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖姟⒔ㄗh或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像， 如有違反，本站將追究法律責任！