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

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

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

二、考試時(shí)量：120分鐘

三、卷面分?jǐn)?shù)：100分

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

（一）緒論

1、考核知識(shí)點(diǎn)

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

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

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

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

（5）算法的五個(gè)特點(diǎn)。

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

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

2、考核要求

（1）識(shí)記

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

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

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

（2）理解

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

（二）線性表

1、考核知識(shí)點(diǎn)

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

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

（3）鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。

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

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

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

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

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

2、考核要求

（1）識(shí)記

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

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

（2）理解

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

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

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

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

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

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

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

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

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

（三）棧和隊(duì)列

1、考核知識(shí)點(diǎn)

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

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

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

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

（5）隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

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

2、考核要求

（1）理解

棧和隊(duì)列的特點(diǎn)，棧和隊(duì)列各自的使用情況。

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

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

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

3）利用棧解決簡(jiǎn)單的實(shí)際問題。

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

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

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

（四）串

1、考核知識(shí)點(diǎn)

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

（2）串的基本操作。

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

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

（5）串的鏈?zhǔn)酱鎯?chǔ)表示

2、考核要求

（1）理解

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

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

1）串的三種存儲(chǔ)表示。

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

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

1、考核知識(shí)點(diǎn)

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

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

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

2、考核要求

（1）理解

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

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

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

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

（六）樹和二叉樹

1、考核知識(shí)點(diǎn)

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

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

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

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

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

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

（7）赫夫曼編碼方法。

2、考核要求

（1）理解

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

2)樹的不同表示方法。

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

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

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

6)樹的遍歷方法。

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

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

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

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

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

5)赫夫曼算法的思想。

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

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

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

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

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

（七）圖

1、考核知識(shí)點(diǎn)

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

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

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

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

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

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

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

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

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

（10）拓?fù)渑判颉?/p>

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

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

2、考核要求

（1）理解

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

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

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

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

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

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

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

8)拓?fù)渑判虻幕舅枷牒筒襟E。

9)對(duì)給定的有向圖，若拓?fù)湫蛄写嬖?，則要求寫出一個(gè)或多個(gè)拓?fù)湫蛄小?/p>

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

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

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

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

4）確定兩種遍歷的頂點(diǎn)訪問序列。

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

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

（八）查找

1、考核知識(shí)點(diǎn)

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

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

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

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

（5）哈希法的特點(diǎn)。

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

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

2、考核要求

（1）識(shí)記

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

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

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

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

2）二叉排序樹和二叉平衡樹的定義、特點(diǎn)

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

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

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

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

1、考核知識(shí)點(diǎn)

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

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

（3）選擇排序的思想

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

（5）起泡排序的思想。

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

2、考核要求

（1）識(shí)記

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

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

2)排序方法的分類及算法好壞的評(píng)判標(biāo)準(zhǔn)。

（2）理解

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

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

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

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

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

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

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

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

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

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

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

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

五、題型

填空題10分（每空2分）；單項(xiàng)選擇題40分（每小題2分）；

判斷題10分（每小題1分）；簡(jiǎn)答題10分（每小題5分）；

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

六、參考教材

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

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

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

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

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