海南師范大學(xué)

從海南師范大學(xué)研究生院獲悉，2022年海南師范大學(xué)919數(shù)據(jù)結(jié)構(gòu)考研考試大綱及參考書目?jī)?nèi)容如下

 

海南師范大學(xué)2023年全國碩士研究生招生自命題考試大綱

考試科目代碼：[919]              考試科目名稱：數(shù)據(jù)結(jié)構(gòu)

﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡

一、考試形式與試卷結(jié)構(gòu)

（一）試卷成績(jī)及考試時(shí)間

本試卷滿分為150分，考試時(shí)間為180分鐘。

（二）答題方式

答題方式為閉卷、筆試。

（三）試卷結(jié)構(gòu)

選擇題；填空題；簡(jiǎn)答題；算法理解題；算法應(yīng)用題；算法設(shè)計(jì)題等

二、考試目標(biāo)：

1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和基礎(chǔ)知識(shí)。

2.掌握數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的基本原理和方法

3.考查對(duì)各類數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的分析和算法設(shè)計(jì)的能力以及解決實(shí)際問題的能力。

三、考試范圍：

第一章. 概述

(1) 數(shù)據(jù)結(jié)構(gòu)以及數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念(理解)

(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)以及存儲(chǔ)結(jié)構(gòu)(掌握)

(3) 算法的五個(gè)特性(理解)

(4) 算法時(shí)間復(fù)雜度和空間復(fù)雜度的方法 (掌握)

(5) 抽象數(shù)據(jù)類型(理解)

第二章. 線性表

(1) 線性表的邏輯結(jié)構(gòu)以及相關(guān)概念(理解)

(2) 線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(掌握)

(3) 線性表的順序結(jié)構(gòu)及基本操作的實(shí)現(xiàn)(掌握)

(4) 線性表的鏈?zhǔn)浇Y(jié)構(gòu)及基本操作的實(shí)現(xiàn) (掌握)

(5) 從時(shí)間、空間復(fù)雜度的角度比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)(理解)

(6) 線性表的應(yīng)用(理解)

第三章. 棧和隊(duì)列

(1) 棧的相關(guān)概念及特點(diǎn)(理解)

(2) 棧的順序存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)(掌握)

(3) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)(掌握)

(4) 遞歸算法中棧的作用(理解)

(5) 棧的典型應(yīng)用實(shí)例(掌握)

(6) 隊(duì)列的相關(guān)概念及特點(diǎn)(理解)

(7) 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)(掌握)

(8) 鏈隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)(掌握)

(9) 隊(duì)列的典型應(yīng)用實(shí)例(掌握)

第四章. 串與數(shù)組

(1) 字符串模式匹配(掌握)

(2) 掌握掌握KMP算法的原理(掌握)

(3) next數(shù)組的推理過程(理解)

(4) 數(shù)組的定義(掌握)

(5) 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)(掌握)

第五章. 樹與二叉樹

(1) 樹與二叉樹的相關(guān)概念(理解)

(2) 二叉樹的各種存儲(chǔ)結(jié)構(gòu)(掌握)

(3) 二叉樹的性質(zhì)(掌握)

(4) 按各種次序遍歷二叉樹的遞歸算法(掌握)

(5) 中序遍歷二叉樹的非遞歸算法(理解)

(6) 建立二叉樹的各種算法(掌握)

(7) 二叉樹的線索化(理解)

(8) 建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)

(9) 樹與二叉樹、森林與二叉樹的相互轉(zhuǎn)換(理解)

第六章. 圖

(1) 圖的相關(guān)概念(理解)

(2) 圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)(掌握)

(3) 圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷(掌握)

(4) 最小生成樹(PRIM算法和Kruscal算法)(掌握)

(5) 某一點(diǎn)到其他各點(diǎn)之間的最短路徑(迪杰斯特拉算法)(掌握)

(6) 拓?fù)渑判?掌握)

(7) 關(guān)鍵路徑和關(guān)鍵活動(dòng)(掌握)

第七章. 查找算法

(1) 順序查找算法及特點(diǎn)(掌握)

(2) 折半查找算法及特點(diǎn)(掌握)

(3) 二叉排序樹的構(gòu)造方法和查找過程(掌握)

(4) 二叉平衡樹的平衡調(diào)整方法(掌握)

(5) 哈希表的構(gòu)造方法和解決沖突的方法(掌握)

(6) 各種查找算法在等概率情況下查找成功和查找失敗時(shí)的平均查找長度的計(jì)算方法(掌握)

第八章. 排序算法

(1) 插入排序(直接插入排序、折半插入排序)方法的排序過程和特點(diǎn)(掌握)

(2) SHELL插入排序方法的排序過程(掌握)

(3) 交換排序(起泡排序,快速排序)方法的排序過程和特點(diǎn)(掌握)

(4) 選擇排序(簡(jiǎn)單選擇排序,堆排序)的排序過程和特點(diǎn)(掌握)

(5) 歸并排序方法的排序過程和特點(diǎn)(掌握)

(6) 各種排序方法的算法實(shí)現(xiàn)以及時(shí)間復(fù)雜度和空間復(fù)雜度分析(理解)

四、主要參考書目

1、嚴(yán)蔚敏，李冬梅，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版 第2版），人民郵電出版社，2022

2、嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2003.

原文鏈接 http://yjsc.hainnu.edu.cn/html/2022/gongzuoxinxi_0708/9348.html