軟件工程0835數(shù)據(jù)結(jié)構(gòu)加試

1、湖南師范大學(xué)科目代碼： 入學(xué)自命題大綱科目名稱：數(shù)據(jù)結(jié)構(gòu)一、形式與試卷結(jié)構(gòu)1)試卷成績及時間：本試卷滿分為 100 分，時間為 180 分鐘。2)答題方式：閉卷、筆試3)試卷內(nèi)容結(jié)構(gòu)（一）客觀題部分60%（二）題部分40%4)題型結(jié)構(gòu)a: 選擇題, 約 20%b: 閱讀題，約 20%c: 簡答題，約 20%d: 算法題，約 40%二、內(nèi)容與要求數(shù)據(jù)結(jié)構(gòu)目標(biāo)：“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。目的就是要培養(yǎng)他們的數(shù)據(jù)抽象能力，學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、結(jié)構(gòu)及實現(xiàn)應(yīng)用的相應(yīng)算法，并掌握分析算法的時間和空間復(fù)雜度的技術(shù)。內(nèi)容：一、 緒論：熟悉各名

2、詞、術(shù)語的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和結(jié)構(gòu)之間的關(guān)系；了解抽象數(shù)據(jù)類型的定義、表示方法；熟悉類C 語言的書寫規(guī)范，特別要注意值調(diào)用和輸出的方式以及錯誤處理方式；理解算法五個要素的確切含義；掌握計算語句頻度和估算算法時間復(fù)雜度的方法。調(diào)用的區(qū)別，輸入、二、 線性表：線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種結(jié)構(gòu)的描述方法；性表的兩類結(jié)構(gòu)（順序和鏈?zhǔn)剑┥蠈崿F(xiàn)基本操作；一元多項式的抽象數(shù)據(jù)類型定義、表示及加法的實現(xiàn)。三、 棧和隊列：棧和隊列的結(jié)構(gòu)特性；在兩種結(jié)構(gòu)上如何實現(xiàn)棧和隊列的基本操作和棧和隊列在程序設(shè)計中的應(yīng)用以及如何利用堆棧去模擬遞歸程序的運行。四、 串：串的數(shù)據(jù)類型定義；串

3、的三種構(gòu)；表示：定長順序結(jié)構(gòu)、塊鏈結(jié)構(gòu)和堆分配結(jié)串的各種基本操作的實現(xiàn)及應(yīng)用；串的模式匹配算法。五、 數(shù)組和廣義表：數(shù)組的類型定義和表示方法； 特殊矩陣和稀疏矩陣的壓縮方法及運算的實現(xiàn)；廣義表的邏輯結(jié)構(gòu)和結(jié)構(gòu)、m 元多項式的廣義表表示以及廣義表的操作的遞歸算法舉例 。六、 樹和二叉樹：二叉樹的定義、性質(zhì)和結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、 樹的多種應(yīng)用；結(jié)構(gòu)、樹和森林與二叉樹的轉(zhuǎn)換、遍歷；平衡二叉樹、平衡二叉排序樹的 定義、性質(zhì)極其應(yīng)用。 本章是該課程的重點內(nèi)容之一。七、 圖：圖的定義和術(shù)語；圖的四種結(jié)構(gòu)：數(shù)組表示法、鄰接表、鏈表和鄰接多重表；圖的兩種遍歷策

4、略：深度優(yōu)先搜索和廣度優(yōu)先搜索； 圖的連通性：連通分量和最小生成樹；拓撲排序和關(guān)鍵路徑；兩類求最短路徑問題的解法。八、 查找：查找表（包括靜態(tài)查找表和動態(tài)查找表）的各種實現(xiàn)方法：順序表、有序表、樹表和哈希表；關(guān)于衡量查找表的主要操作查找的查找效率的平均查找長度的。九、排序：比較各種排序方法，排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本析。、算法特點、排序過程以及它們的時間復(fù)雜度分在每類排序方法中，從簡單方法入手，重點性能先進的高效方法（如，排序類中的排序、交換排序類中的快速排序、選擇排序類中的堆排序等）。要求：要求學(xué)生掌握基本概念、重要數(shù)據(jù)結(jié)構(gòu)、基本算法，掌握各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、結(jié)構(gòu)算法。根據(jù)當(dāng)前