科目名稱(chēng) 數據結構 編號 810

考試專(zhuān)業(yè) 085404計算機技術(shù)、085412網(wǎng)絡(luò )與信息安全

一、考試性質(zhì)

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

二、考核目標

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

具體要求如下：

1. 了解數據結構及其分類(lèi)、數據結構與算法的密切關(guān)系。

2. 掌握堆棧、隊列、表、樹(shù)、圖等的數據結構，學(xué)會(huì )根據實(shí)際問(wèn)題要求來(lái)選擇數據結構。

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

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

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

三、考試形式與試卷結構

1. 考試時(shí)間：考試時(shí)間為180分鐘，3小時(shí)。

2. 試卷滿(mǎn)分：本試卷滿(mǎn)分為150分。

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

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

四、考試內容

1. 緒論

要求掌握數據結構的基本概念，理解數據、數據元素和數據項的概念及其相互間關(guān)系，清楚數據的邏輯結構、存儲結構的聯(lián)系與區別，理解抽象數據類(lèi)型的概念，掌握算法的時(shí)間性能和空間性能分析。要點(diǎn)是分析算法的時(shí)間和空間性能。

2. 線(xiàn)性表

要求掌握線(xiàn)性表的基本概念、線(xiàn)性表的順序實(shí)現、線(xiàn)性表的鏈式實(shí)現、線(xiàn)性表順序實(shí)現與鏈接實(shí)現的異同。要點(diǎn)是線(xiàn)性表的順序結構與線(xiàn)性表的鏈式結構的插入、刪除和按關(guān)鍵字查找的算法實(shí)現。

3.棧與隊列

要求掌握棧與隊列的概念與基本操作，棧的應用，鏈隊列與循環(huán)隊列的組織方法。要點(diǎn)是鏈隊列與循環(huán)隊列的組織方法與基本操作的實(shí)現。

4.串

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

5.數組與廣義表

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

6.樹(shù)與二叉樹(shù)

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

7.圖

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

8查找

要求掌握查找的基本概念，靜態(tài)查找表的實(shí)現，二叉排序樹(shù)的概念及查找，哈希表的思想及相關(guān)算法。要點(diǎn)是折半查找、二叉排序樹(shù)與哈希表。

9.排序

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

五、參考書(shū)目

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