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

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

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

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

　　二、考試的基本要求

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

　　三、考試方法和考試時(shí)間

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

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

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

　　1、考試內(nèi)容

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

　　2、基本要求

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

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

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

　　4）時(shí)間復(fù)雜度、空間復(fù)雜度的概念以及簡(jiǎn)單算法時(shí)間復(fù)雜度的計(jì)算。

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

　　第2章線性表

　　1、考試內(nèi)容

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

　　2、基本要求

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

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

　　3）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其運(yùn)算的實(shí)現(xiàn)。

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

　　第3章棧和隊(duì)列

　　1、考試內(nèi)容

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

　　2、基本要求

　　1）棧和隊(duì)列的定義、基本運(yùn)算。

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

　　3）棧和隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

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

　　5）理解遞歸的概念。

　　第4章串

　　1、考試內(nèi)容

　　串的定義及其基本操作。

　　2、基本要求

　　1）串的定義。

　　2）串的幾種表示方法。

　　3）串的基本操作。

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

　　1、考試內(nèi)容

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

　　2、基本要求

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

　　2）稀疏矩陣的存儲(chǔ)。

　　3）廣義表的概念。

　　第6章樹

　　1、考試內(nèi)容

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

　　2、基本要求

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

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

　　3）二叉樹的存儲(chǔ)結(jié)構(gòu)，包括順序和鏈?zhǔn)酱鎯?chǔ)。

　　4）二叉樹的遍歷、遞歸算法及其應(yīng)用。

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

　　第7章圖

　　1、考試內(nèi)容

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

　　2、基本要求

　　1）圖的基本概念。

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

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

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

　　第8章查找

　　1、考試內(nèi)容

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

　　2、基本要求

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

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

　　3）散列表的概念。

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

　　第9章排序

　　1、考試內(nèi)容

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

　　2、基本要求

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

　　2）選擇排序的方法（簡(jiǎn)單選擇排序）

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

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

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

　　五、命題要求

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

　　1）選擇題：30%

　　2）判斷題：15%

　　3）簡(jiǎn)答題：15%

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

　　5）編程題：10%

　　六、主要參考書目

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

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

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