湖南工業(yè)學(xué)院公布了2021年湖南學(xué)院升本招生專業(yè)各科考試大綱。以下是《數(shù)據(jù)結(jié)構(gòu)》考試大綱的詳細(xì)內(nèi)容。

數(shù)據(jù)結(jié)構(gòu)課程考試大綱

(大學(xué)升級(jí))

課程名稱:數(shù)據(jù)結(jié)構(gòu)

適用專業(yè):計(jì)算機(jī)相關(guān)專業(yè)

教材使用:嚴(yán)為民，數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，清華大學(xué)出版社

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

《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)專業(yè)基礎(chǔ)課，旨在培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，學(xué)會(huì)分析程序處理的數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，為程序處理的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法，掌握空之間算法時(shí)間和復(fù)雜度的分析技術(shù)。

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

1.簡(jiǎn)介:熟悉名詞和術(shù)語(yǔ)的含義，掌握基本概念，尤其是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系；理解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)；熟悉類C語(yǔ)言的編寫(xiě)標(biāo)準(zhǔn)，特別注意值調(diào)用和引用調(diào)用的區(qū)別，輸入輸出的方式和錯(cuò)誤處理的方式；理解算法五行的確切含義；掌握計(jì)算句子頻率和估計(jì)算法時(shí)間復(fù)雜度的方法。

2.線性表:線性表的各種存儲(chǔ)結(jié)構(gòu)的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和描述方法；在線性表的兩種存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ))上實(shí)現(xiàn)基本操作；一元多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法。

3.棧和隊(duì)列:棧和隊(duì)列的結(jié)構(gòu)特征；如何在兩種存儲(chǔ)結(jié)構(gòu)中實(shí)現(xiàn)棧和隊(duì)列的基本操作，如何用棧和隊(duì)列來(lái)模擬遞歸程序的運(yùn)行。

4.String:字符串的數(shù)據(jù)類型定義；字符串的存儲(chǔ)表示有三種:定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)、區(qū)塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；字符串各種基本運(yùn)算的實(shí)現(xiàn)和應(yīng)用；字符串模式匹配算法。

5.數(shù)組和廣義表:數(shù)組的類型定義和表示；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法及運(yùn)算實(shí)現(xiàn)：廣義表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，m元多項(xiàng)式的廣義表表示，廣義表運(yùn)算的遞歸算法實(shí)例。

6.樹(shù)與二叉樹(shù):二叉樹(shù)的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的遍歷和線索以及遍歷算法的各種描述形式；樹(shù)木和森林的定義和存儲(chǔ)結(jié)構(gòu)，樹(shù)木和森林以及二叉樹(shù)之間的轉(zhuǎn)換和遍歷；樹(shù)的多重應(yīng)用；平衡二叉樹(shù)和平衡二叉排序樹(shù)的定義、性質(zhì)及應(yīng)用。

7.圖:圖的定義和術(shù)語(yǔ)；圖的四種存儲(chǔ)結(jié)構(gòu):數(shù)組表示、鄰接表、交叉鏈表和鄰接多表；圖的兩種遍歷策略:深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性:連通分支和最小生成樹(shù)；拓?fù)渑判蚝完P(guān)鍵路徑；求解最短路徑問(wèn)題的兩種算法。

8.查找:討論查找表(包括靜態(tài)查找表和動(dòng)態(tài)查找表)的各種實(shí)現(xiàn)方法:順序表、有序表、樹(shù)形表、哈希表；關(guān)于衡量查找表的主要操作——查找效率的平均查找長(zhǎng)度。

9.內(nèi)部排序:討論比較各種內(nèi)部排序方法，如插入排序、交換排序、選擇排序、合并排序、基數(shù)排序等，以及它們的基本思想、算法特點(diǎn)、排序過(guò)程和時(shí)間復(fù)雜度。在每一種排序方法中，都要從簡(jiǎn)單的方法入手，重點(diǎn)放在性能較高的方法上(排序類中的Hill排序，交換排序類中的快速排序，select排序類中的堆排序等)。).

10.外部排序:實(shí)現(xiàn)外部排序的基本方法；為了減少平衡合并排序所需的外部存儲(chǔ)器讀/寫(xiě)次數(shù)，可以采用失敗者樹(shù)實(shí)現(xiàn)多路合并，通過(guò)排列選擇排序生成初始合并段，并為不同長(zhǎng)度的合并段構(gòu)造最佳合并樹(shù)。

“數(shù)據(jù)結(jié)構(gòu)”要求學(xué)生掌握基本概念、重要的數(shù)據(jù)結(jié)構(gòu)和基本算法，以及各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法。根據(jù)當(dāng)前計(jì)算機(jī)應(yīng)用的發(fā)展，舉例說(shuō)明了數(shù)據(jù)結(jié)構(gòu)的描述和應(yīng)用的實(shí)現(xiàn)算法。

三、考試方法

采用筆試(閉卷)，考試時(shí)長(zhǎng)100分鐘。

四、試卷結(jié)構(gòu)和題型

類型:填空題(10%)、選擇題(10%)、真假題(10%)、簡(jiǎn)答題(20%)、

填寫(xiě)空程序題(20%)和程序設(shè)計(jì)題(30%)。

更多湖南專升本信息政策，請(qǐng)及時(shí)關(guān)注樂(lè)貞教育。

部分內(nèi)容來(lái)源于網(wǎng)絡(luò)轉(zhuǎn)載、學(xué)生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖?jiàn)、建議或者投訴，請(qǐng)聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像， 如有違反，本站將追究法律責(zé)任！