2022年武昌首義學(xué)院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

　　報考武昌首義學(xué)院專升本計算機專業(yè)的同學(xué)，在復(fù)習(xí)備考專業(yè)課數(shù)據(jù)結(jié)構(gòu)時，對于該復(fù)習(xí)哪些內(nèi)容感到迷茫，因為計算機專業(yè)在平時的課程中，大多數(shù)都是需要上機操作實踐的。對于該復(fù)習(xí)哪些知識點不太清楚，這時候可以圍繞考試大綱中的內(nèi)容來重點復(fù)習(xí)備考。 　　一、考試性質(zhì)

　　數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在整個專業(yè)教學(xué)中占有十分重要的地位。主要介紹用計算機解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種存儲數(shù)據(jù)結(jié)構(gòu)上執(zhí)行操作的算法。課程教學(xué)應(yīng)達到的目標(biāo)是使學(xué)生掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算的基本理論、基本知識和基本技能，并具有利用計算機解決實際應(yīng)用問題的能力。數(shù)據(jù)結(jié)構(gòu)課程既是對以往課程的深入和擴展，也是為將來更加深入地學(xué)習(xí)后續(xù)專業(yè)課程打下基礎(chǔ)。

　　本考試是為在計算機專科畢業(yè)生中招收本科生，實施的具有選拔功能的水平考試，指導(dǎo)思想是既有利于國家對高層次人才的選拔，又利于促進高等學(xué)校課程教學(xué)質(zhì)量的提高。

　　二、考試的基本要求

　　要求學(xué)生比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)的基本知識和基本技能，初步具有在明確所要解決的問題的基礎(chǔ)上，經(jīng)過對問題的深入分析和抽象，為其在計算機中建立一個模型，然后確定恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示該模型，再在此基礎(chǔ)上設(shè)計合適的算法，最后根據(jù)設(shè)計的數(shù)據(jù)結(jié)構(gòu)和算法進行相應(yīng)的程序設(shè)計來模擬和解決實際問題，為后繼專業(yè)課程學(xué)習(xí)提供基礎(chǔ)。

　　三、考試方法和考試時間

　　考試方法為閉卷筆試，考試時間為90分鐘，滿分為100分。

　　四、考試內(nèi)容和要求

　　第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

　　1、考試內(nèi)容

　　數(shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語，算法的描述和算法分析。

　　2、基本要求

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

　　2）數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法的概念。

　　3）數(shù)據(jù)類型、抽象數(shù)據(jù)類型的概念。

　　4）時間復(fù)雜度、空間復(fù)雜度的概念以及簡單算法時間復(fù)雜度的計算。

　　5）數(shù)據(jù)結(jié)構(gòu)二元組的概念。S=（D,R）

　　第2章線性表

　　1、考試內(nèi)容

　　線性表的定義、線性表的邏輯結(jié)構(gòu)、線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，單向鏈表、循環(huán)鏈表。

　　2、基本要求

　　1）線性表的定義和線性結(jié)構(gòu)的特點。。

　　2）線性表的順序存儲結(jié)構(gòu)及其運算的實現(xiàn)。

　　3）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其運算的實現(xiàn)。

　　4）單鏈表、循環(huán)鏈表的特點。

　　第3章棧和隊列

　　1、考試內(nèi)容

　　棧和隊列的定義、表示方法和實現(xiàn)。

　　2、基本要求

　　1）棧和隊列的定義、基本運算。

　　2）棧和隊列的順序?qū)崿F(xiàn)及其運算的實現(xiàn)。

　　3）棧和隊列的鏈?zhǔn)綄崿F(xiàn)及其運算的實現(xiàn)。

　　4）棧和隊列的應(yīng)用。

　　5）理解遞歸的概念。

　　第4章串

　　1、考試內(nèi)容

　　串的定義及其基本操作。

　　2、基本要求

　　1）串的定義。

　　2）串的幾種表示方法。

　　3）串的基本操作。

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

　　1、考試內(nèi)容

　　數(shù)組的定義、運算和存儲、稀疏矩陣的壓縮存儲、廣義表的定義和操作。

　　2、基本要求

　　1）數(shù)組的定義。

　　2）稀疏矩陣的存儲。

　　3）廣義表的概念。

　　第6章樹

　　1、考試內(nèi)容

　　樹的定義、基本術(shù)語和存儲結(jié)構(gòu)，二叉樹的定義和性質(zhì)、二叉樹的存儲結(jié)構(gòu)及其各種操作，哈夫曼樹及編碼。

　　2、基本要求

　　1）樹的定義及其存儲結(jié)構(gòu)。

　　2）二叉樹的定義和性質(zhì)。

　　3）二叉樹的存儲結(jié)構(gòu)，包括順序和鏈?zhǔn)酱鎯Α?br />
　　4）二叉樹的遍歷、遞歸算法及其應(yīng)用。

　　5）哈夫曼樹及哈夫曼編碼。

　　第7章圖

　　1、考試內(nèi)容

　　圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)及其各種操作。

　　2、基本要求

　　1）圖的基本概念。

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

　　3）圖的遍歷方法（深度優(yōu)先遍歷、廣度優(yōu)先遍歷）。

　　4）圖的最小生成樹的算法（prim算法、kruskal算法）。

　　第8章查找

　　1、考試內(nèi)容

　　各種查找方法的算法、適用范圍及時間復(fù)雜度的分析。

　　2、基本要求

　　1）各種靜態(tài)查找技術(shù)和算法（順序查找、折半查找）。

　　2）動態(tài)查找的概念（二叉查找樹）。

　　3）散列表的概念。

　　4）散列函數(shù)構(gòu)造方法以及處理沖突的辦法

　　第9章排序

　　1、考試內(nèi)容

　　多種排序算法的基本思想和算法的時間復(fù)雜度分析，不同排序方法的比較。

　　2、基本要求

　　1）排序的基本概念（關(guān)鍵字、內(nèi)外排序、穩(wěn)定性等）

　　2）選擇排序的方法（簡單選擇排序）

　　3）插入排序的方法（直接插入排序）

　　4）交換排序的方法（冒泡排序）

　　5）各種排序方法的優(yōu)缺點。

　　五、命題要求

　　本課程命題范圍應(yīng)涵蓋課程的所有章節(jié)，試題難易程度分為，較易占45％，中等難度占35％，較難占20％。在題型結(jié)構(gòu)上，主要包括客觀題和主觀題。

　　1）選擇題：30%

　　2）判斷題：15%

　　3）簡答題：15%

　　4）應(yīng)用題：30%

　　5）編程題：10%

　　六、主要參考書目

　　1、程海英，彭文藝．?dāng)?shù)據(jù)結(jié)構(gòu)案例教程（C語言版）．北京：電子工業(yè)出版社，2019．

　　2、嚴(yán)蔚敏，李冬梅，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）.第2版.北京：人民郵電出版社，2016.

　　相信閱讀完以上專升本數(shù)據(jù)結(jié)構(gòu)考試大綱后，相信報名專升本的同學(xué)們對于復(fù)習(xí)方向有了大概的了解，希望同學(xué)們能夠認(rèn)真復(fù)習(xí)，順利通過升本考試。