2021年湖南專升本考試公告尚未發(fā)布。對(duì)于即將參加2021年湖南省大專生考試的考生，以下樂貞老師為考生編輯的2020年湖南省人文科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)考試大綱，可供2021年考生參考。

湖南文理學(xué)院數(shù)據(jù)結(jié)構(gòu)考試大綱

一、考試大綱描述

1、課程的性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的必修專業(yè)基礎(chǔ)課。這門課程的主要特點(diǎn)是實(shí)用性強(qiáng)。不僅要學(xué)習(xí)基礎(chǔ)理論知識(shí)，還要注重計(jì)算機(jī)實(shí)踐。通過(guò)計(jì)算機(jī)實(shí)踐，驗(yàn)證了算法的正確性，掌握并鞏固了所學(xué)的理論知識(shí)。開設(shè)本課程的目的是使學(xué)生學(xué)會(huì)分析和研究計(jì)算機(jī)處理的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，從而為應(yīng)用中涉及的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法，初步了解算法的時(shí)間分析和空互分析技術(shù)。另一方面，通過(guò)本課程中算法設(shè)計(jì)和計(jì)算機(jī)實(shí)踐的訓(xùn)練，也要培養(yǎng)學(xué)生的數(shù)據(jù)抽象和程序設(shè)計(jì)能力，為后續(xù)課程尤其是軟件課程打下堅(jiān)實(shí)的知識(shí)基礎(chǔ)。要求學(xué)生掌握各種常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算算法。

2.考試目標(biāo)和要求

通過(guò)本課程的學(xué)習(xí)，學(xué)生要從數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面系統(tǒng)地掌握常用的數(shù)據(jù)結(jié)構(gòu)如線性表、棧、隊(duì)列、串、數(shù)組、樹、圖等；并了解在各種常用數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)的排序和搜索算法，有一定的分析空之間的時(shí)間和復(fù)雜度的能力；對(duì)于簡(jiǎn)單的應(yīng)用問(wèn)題，我們應(yīng)該能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)有效的算法來(lái)解決它們?？荚嚨哪康氖强疾鞂W(xué)生對(duì)上述問(wèn)題的掌握程度，以及在具體算法實(shí)施中發(fā)現(xiàn)和糾正錯(cuò)誤的能力。

3.相關(guān)事項(xiàng)

在試題中，不同能力水平要求的分?jǐn)?shù)一般如下:死記硬背占20%，理解占30%，簡(jiǎn)單應(yīng)用占30%，綜合應(yīng)用占20%。

試題合理安排的難度結(jié)構(gòu)。試題難度可分為易、易、難、難四個(gè)等級(jí)。每張?jiān)嚲碇?，不同難度題目的評(píng)分比例為2: 3: 3: 2、

本課程有填空、單項(xiàng)選擇、真假題、簡(jiǎn)答題、算法應(yīng)用題、算法填空六種題型。

4.教學(xué)參考書

[1]吳偉民嚴(yán)為民。數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版本)。北京:清華大學(xué)出版社. 2011，7

專升本考試大綱" alt="湖南專升本考試大綱" width="600" height="372" border="0" vspace="0" style="width: 600px; height: 372px;"/>

二、考試內(nèi)容及具體要求

(a)導(dǎo)言

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

(1)解決實(shí)際應(yīng)用問(wèn)題時(shí)，正確數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵；以及研究數(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)算法描述和算法分析方法，可以分析一般算法的時(shí)間復(fù)雜度。

2.評(píng)估要求

(1)記憶

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

2)正確的數(shù)據(jù)結(jié)構(gòu)在解決實(shí)際應(yīng)用問(wèn)題中的關(guān)鍵和研究數(shù)據(jù)結(jié)構(gòu)的意義。

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

(2)理解

算法描述和分析:時(shí)間復(fù)雜度和空之間的復(fù)雜度，算法最差和平均時(shí)間復(fù)雜度。

(2)線性表

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

(1)線性表的類型定義。

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

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

(4)單鏈表的創(chuàng)建表、搜索、插入、刪除等基本算法及其時(shí)間復(fù)雜度。

(5)尾部指針代替循環(huán)鏈表上的頭部指針。

(6)單循環(huán)鏈表上的算法與單鏈表上對(duì)應(yīng)算法的異同。

(7)雙鏈表的定義。

(8)序列表和鏈表的比較，以及如何選擇一個(gè)作為其存儲(chǔ)結(jié)構(gòu)來(lái)達(dá)到更好的time 空性能。

2.評(píng)估要求

(1)記憶

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)，才能獲得更好的time 空性能。

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

1)序列表的含義和特征，以及對(duì)序列表的插入和刪除操作。

2)單鏈表和雙鏈表的區(qū)別；

3)單鏈表創(chuàng)建表、搜索、插入、刪除等基本算法。

4)尾部指針代替循環(huán)鏈表中的頭部指針，

5)單循環(huán)鏈表上的算法與單鏈表上對(duì)應(yīng)算法的異同。

(3)堆棧和隊(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.評(píng)估要求

(1)理解

堆棧和隊(duì)列的特征，以及它們各自的用法。

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

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

2)在序列棧和鏈棧上實(shí)現(xiàn)棧入口和棧出口等基本算法。

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

4)在順序隊(duì)列(主要是循環(huán)隊(duì)列)和鏈?zhǔn)疥?duì)列上實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法。

(4)字符串

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

(1)字符串的定義，空字符串，空點(diǎn)陣字符串，子字符串，主字符串，字符串相等。

(2)字符串的基本操作。

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

2.評(píng)估要求

(1)理解

字符串的一些概念及其基本運(yùn)算。

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

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

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

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

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

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

2.評(píng)估要求

(1)理解

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

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

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

4)稀疏矩陣的壓縮存儲(chǔ)方式——三重表。

(6)樹和二叉樹

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

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

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

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

(4)樹的存儲(chǔ)表征——兒童表征、父母表征和兒童兄弟表征。

(5)樹、林、二叉樹的轉(zhuǎn)換方法。

(6)樹的路徑長(zhǎng)度，樹的加權(quán)路徑長(zhǎng)度，Hoeffmann樹(最優(yōu)二叉樹)的構(gòu)造方法。

(7)霍夫曼編碼方法。

2.評(píng)估要求

(1)理解

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

2)樹的不同表示。

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

4)樹與林、二叉樹的轉(zhuǎn)換方法。

5)樹木的各種貯藏結(jié)構(gòu)及其特點(diǎn)。

6)樹的遍歷方法。

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

1)二叉樹的定義以及樹和二叉樹的區(qū)別。

2)二叉樹的性質(zhì)

3)二叉樹的兩種存儲(chǔ)結(jié)構(gòu)和特點(diǎn)。

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

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

6)根據(jù)最優(yōu)二叉樹構(gòu)造相應(yīng)的霍夫曼碼。

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

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

2)根據(jù)不同的遍歷方式，應(yīng)該得到相應(yīng)的節(jié)點(diǎn)訪問(wèn)順序。

(7)圖

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算法。

2.評(píng)估要求

(1)理解

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

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

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

4)遍歷給定的圖，先畫深度，先畫寬度的生成樹或森林。

Prim和Kruskal算法的基本思想。

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

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

1)圖的鄰接矩陣表示和鄰接表表示。

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

3)兩種遍歷算法:深度優(yōu)先搜索和廣度優(yōu)先搜索。

4)確定兩個(gè)遍歷頂點(diǎn)訪問(wèn)序列。

(八)尋找

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

(1)搜索定義關(guān)鍵詞、搜索和平均搜索長(zhǎng)度。

(2)靜態(tài)查找表查找算法(順序查找、二進(jìn)制查找、塊查找(索引順序表查找))的效率(最差和平均長(zhǎng)度)。

(3)散列法的特點(diǎn)。

(4)哈希函數(shù)和哈希地址。

(5)處理沖突的方法:開放地址法和鏈?zhǔn)降刂贩āｉ_放地址法分為線性檢測(cè)再散列、二次檢測(cè)再散列和偽隨機(jī)檢測(cè)再散列。

2.評(píng)估要求

(1)記憶

1)數(shù)據(jù)處理中搜索的重要性。

2)找到成功或失敗的意義。

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

1)順序搜索、二分搜索法和塊搜索的基本思想、算法實(shí)現(xiàn)和搜索效率分析。

2)二叉排序樹的定義和特征

3)建立二叉排序樹的過(guò)程是輸入序列的排序過(guò)程，輸入序列對(duì)建立的二叉排序樹形狀的影響

4)哈希表、哈希函數(shù)、哈希地址(哈希地址)、填充因子等相關(guān)概念

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

(9)內(nèi)部排名

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

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

(2)插入排序:直接插入排序算法、分裂插入排序算法、Hill排序思想。

(3)選擇排序的思想

(5)氣泡排序的思想。

2.評(píng)估要求

(1)記憶

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

(2)理解

排序和其他排序方法的區(qū)別。

2021年湖南專升本考試政策還沒有出臺(tái)。準(zhǔn)備參加考試的考生必須為考試做好準(zhǔn)備。2021年，湖南專升本考試視頻課程更新?？忌梢蕴崆暗卿洏坟懡逃龑W(xué)習(xí)，努力進(jìn)入理想的大學(xué)。

部分內(nèi)容來(lá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é)任！