科目名稱 數據結構 編號 810

考試專業 085404計算機技術、085412網絡與信息安全

一、考試性質

本考試大綱適用于報考湖北民族大學電子信息計算機技術、網絡與信息安全方法的碩士研究生入學考試?！稊祿Y構》不僅是大學本科計算機類專業的專業基礎課，也是其他從事計算機信息處理專業的一門重要的基礎課程。它主要考查考生對數據的組織、存儲、處理等能力，算法設計以及對算法的分析和評價的掌握程度。要求考生理解數據結構的邏輯結構和物理結構的基本概念，熟練掌握各種數據結構以及有關算法，并具有綜合運用所學知識分析和解決實際問題的能力。

二、考核目標

《數據結構》試卷旨在考查考生對算法基本知識、基本理論的掌握，注重考查考生靈活運用這些基礎知識的能力和分析解決計算問題的能力。

具體要求如下：

1. 了解數據結構及其分類、數據結構與算法的密切關系。

2. 掌握堆棧、隊列、表、樹、圖等的數據結構，學會根據實際問題要求來選擇數據結構。

3. 掌握設計算法的步驟和算法分析方法。

4. 掌握數據結構在排序和查找等常用算法中的應用。

5. 掌握算法的空間復雜度和時間復雜度分析的基本算法。

三、考試形式與試卷結構

1. 考試時間：考試時間為180分鐘，3小時。

2. 試卷滿分：本試卷滿分為150分。

3. 考試形式：閉卷、筆試。

4.試卷內容結構：填空題20分，選擇題45分，計算解析題60分，程序設計題25分。

四、考試內容

1. 緒論

要求掌握數據結構的基本概念，理解數據、數據元素和數據項的概念及其相互間關系，清楚數據的邏輯結構、存儲結構的聯系與區別，理解抽象數據類型的概念，掌握算法的時間性能和空間性能分析。要點是分析算法的時間和空間性能。

2. 線性表

要求掌握線性表的基本概念、線性表的順序實現、線性表的鏈式實現、線性表順序實現與鏈接實現的異同。要點是線性表的順序結構與線性表的鏈式結構的插入、刪除和按關鍵字查找的算法實現。

3.棧與隊列

要求掌握棧與隊列的概念與基本操作，棧的應用，鏈隊列與循環隊列的組織方法。要點是鏈隊列與循環隊列的組織方法與基本操作的實現。

4.串

要求掌握串的概念與串的表示和實現。要點是以堆形式實現的串的組織方法與基本操作的實現。

5.數組與廣義表

要求掌握多維數組的結構特點及其存儲地址計算方法，矩陣的壓縮存儲思想，廣義表及其存儲結構。要點是數組的存儲地址計算、矩陣壓縮存儲地址映射關系及廣義表的邏輯結構與存儲結構。

6.樹與二叉樹

要求掌握樹的基本概念、二叉樹的定義與性質，二叉樹的存儲結構，二叉樹的遍歷算法，樹和森林的基本概念，哈夫曼樹等。要點是二叉樹的順序存儲結構與鏈式存儲結構，二叉樹的遍歷算法與哈夫曼編碼。

7.圖

要求掌握圖的基本概念，圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法，圖的遍歷算法，圖的最小生成樹的概念及相關算法，拓撲排序與關健路徑。要點是圖的存儲結構與圖的遍歷算法，圖的拓撲排序算法。

8查找

要求掌握查找的基本概念，靜態查找表的實現，二叉排序樹的概念及查找，哈希表的思想及相關算法。要點是折半查找、二叉排序樹與哈希表。

9.排序

要求掌握排序的基本概念，插入排序，交換排序，選擇排序，歸并排序與基數排序。要點是快速排序、堆排序與歸并排序算法實現與性能分析。

五、參考書目

《數據結構(C語言版)》，嚴蔚敏等，清華大學出版社，2018年