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

湖南文理學院數據結構考試大綱

一、考試大綱描述

1、課程的性質、目的和任務

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

2.考試目標和要求

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

3.相關事項

在試題中，不同能力水平要求的分數一般如下:死記硬背占20%，理解占30%，簡單應用占30%，綜合應用占20%。

試題合理安排的難度結構。試題難度可分為易、易、難、難四個等級。每張試卷中，不同難度題目的評分比例為2: 3: 3: 2、

本課程有填空、單項選擇、真假題、簡答題、算法應用題、算法填空六種題型。

4.教學參考書

[1]吳偉民嚴為民。數據結構(c語言版本)。北京:清華大學出版社. 2011，7

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

二、考試內容及具體要求

(a)導言

1、知識點的考核

(1)解決實際應用問題時，正確數據結構的關鍵；以及研究數據結構的意義。

(2)數據、數據元素、數據項、數據結構等基本概念。

(3)數據結構的四種邏輯結構和兩種存儲結構表示。

(4)抽象數據類型的表示和實現。

(5)算法的五個特點。

(6)算法的概念，算法的時間復雜度，空之間的復雜度，最壞和平均時間復雜度等。

(7)算法描述和算法分析方法，可以分析一般算法的時間復雜度。

2.評估要求

(1)記憶

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

2)正確的數據結構在解決實際應用問題中的關鍵和研究數據結構的意義。

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

(2)理解

算法描述和分析:時間復雜度和空之間的復雜度，算法最差和平均時間復雜度。

(2)線性表

1、知識點的考核

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

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

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

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

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

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

(7)雙鏈表的定義。

(8)序列表和鏈表的比較，以及如何選擇一個作為其存儲結構來達到更好的time 空性能。

2.評估要求

(1)記憶

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

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

(2)理解

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

2)對于線性表上要執(zhí)行的主要操作，需要知道是選擇順序表還是鏈表作為其存儲結構，才能獲得更好的time 空性能。

(3)綜合應用

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

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

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

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

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

(3)堆棧和隊列

1、知識點的考核

(1)棧的抽象數據類型的定義

(2)棧的表示和實現

(3)棧的簡單應用

(4)抽象數據類型隊列的定義

(5)隊列的鏈式表示和實現

(6)隊列的順序表示和實現

2.評估要求

(1)理解

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

(2)綜合應用

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

2)在序列棧和鏈棧上實現棧入口和棧出口等基本算法。

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

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

(4)字符串

1、知識點的考核

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

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

(3)字符串的順序存儲結構以及順序存儲結構下基本操作的實現。

2.評估要求

(1)理解

字符串的一些概念及其基本運算。

(2)簡單應用

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

(5)數組和廣義表

1、知識點的考核

(1)數組的順序存儲結構。

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

2.評估要求

(1)理解

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

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

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

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

(6)樹和二叉樹

1、知識點的考核

(1)樹的定義和術語。

(2)二叉樹(完全二叉樹和全二叉樹)的定義和性質，二叉樹的存儲結構——順序表示和鏈表表示。

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

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

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

(6)樹的路徑長度，樹的加權路徑長度，Hoeffmann樹(最優(yōu)二叉樹)的構造方法。

(7)霍夫曼編碼方法。

2.評估要求

(1)理解

1)樹的邏輯結構特征。

2)樹的不同表示。

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

4)樹與林、二叉樹的轉換方法。

5)樹木的各種貯藏結構及其特點。

6)樹的遍歷方法。

(2)簡單應用

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

2)二叉樹的性質

3)二叉樹的兩種存儲結構和特點。

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

5)根據給定的葉節(jié)點及其權重，構造相應的最優(yōu)二叉樹。

6)根據最優(yōu)二叉樹構造相應的霍夫曼碼。

(3)綜合應用

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

2)根據不同的遍歷方式，應該得到相應的節(jié)點訪問順序。

(7)圖

1、知識點的考核

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

(2)圖形的常用術語和含義。

(3)圖的鄰接矩陣表示的存儲結構。

(4)圖的鄰接表表示。

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

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

(7)生成樹和最小生成樹。

(8)構造最小生成樹的PRIM算法。

(9)構造最小生成樹的Kruskal算法。

2.評估要求

(1)理解

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

2)圖形的常用術語和含義。

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

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

Prim和Kruskal算法的基本思想。

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

(2)簡單應用

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

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

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

4)確定兩個遍歷頂點訪問序列。

(八)尋找

1、知識點的考核

(1)搜索定義關鍵詞、搜索和平均搜索長度。

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

(3)散列法的特點。

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

(5)處理沖突的方法:開放地址法和鏈式地址法。開放地址法分為線性檢測再散列、二次檢測再散列和偽隨機檢測再散列。

2.評估要求

(1)記憶

1)數據處理中搜索的重要性。

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

(2)簡單應用

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

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

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

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

5)散列函數的構造方法和沖突解決方法

(9)內部排名

1、知識點的考核

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

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

(3)選擇排序的思想

(5)氣泡排序的思想。

2.評估要求

(1)記憶

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

(2)理解

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

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

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