湖南人文科技學(xué)院2022年專升本計算機科學(xué)與技術(shù)專業(yè)考試科目為C語言程序設(shè)計、大學(xué)英語、數(shù)據(jù)結(jié)構(gòu)，庫課網(wǎng)校把湖南人文科技學(xué)院2022年專升本數(shù)據(jù)結(jié)構(gòu)考試大綱分享給大家作參考。
湖南人文科技學(xué)院2022年專升本數(shù)據(jù)結(jié)構(gòu)考試大綱
一、考試形式：筆試(閉卷)
二、考試時量：120分鐘
三、卷面分?jǐn)?shù)：100分
四、考核內(nèi)容與要求
(一)緒論
1、考核知識點
(1)合適的數(shù)據(jù)結(jié)構(gòu)在解決實際應(yīng)用問題中的關(guān)鍵性;以及學(xué)習(xí)《數(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)鍵性，以及學(xué)習(xí)《數(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)鏈?zhǔn)奖硎竞蛯崿F(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)隊列的鏈?zhǔn)奖硎竞蛯崿F(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)串的鏈?zhǔn)酱鎯Ρ硎?/p>
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)拓?fù)渑判颉?/p>
(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)拓?fù)渑判虻幕舅枷牒筒襟E。
9)對給定的有向圖，若拓?fù)湫蛄写嬖?，則要求寫出一個或多個拓?fù)湫蛄小?/p>
(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)排序方法的分類及算法好壞的評判標(biāo)準(zhǔn)。
(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、主要教材：李筠，姜學(xué)軍主編，《數(shù)據(jù)結(jié)構(gòu)(高職高專精品課程規(guī)劃教材計算機系列)》. 清華大學(xué)出版社，2008年8月
2、參考教材：嚴(yán)蔚敏,吳偉民主編.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社，2011年7月