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

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

(大學(xué)升級)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、考試方法

采用筆試(閉卷)，考試時長100分鐘。

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

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

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

更多湖南專升本信息政策，請及時關(guān)注樂貞教育。

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