2021中國石油大學（華東）數(shù)據(jù)結(jié)構(gòu)研究生考試大綱

發(fā)布時間：2020-12-28 編輯：考研派小莉推薦訪問：

2021中國石油大學（華東）數(shù)據(jù)結(jié)構(gòu)研究生考試大綱內(nèi)容如下，更多考研資訊請關注我們網(wǎng)站的更新！敬請收藏本站，或下載我們的考研派APP和考研派微信公眾號（里面有非常多的免費考研資源可以領取，有各種考研問題，也可直接加我們網(wǎng)站上的研究生學姐微信，全程免費答疑，助各位考研一臂之力，爭取早日考上理想中的研究生院校。）

+中國石油大學(華東) 研究生
微信,為你答疑,送資源

2021中國石油大學（華東）數(shù)據(jù)結(jié)構(gòu)研究生考試大綱正文

2021 年碩士研究生入學考試大綱

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

考試時間：180 分鐘，滿分：150 分

一、考試要求

1．理解數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、算法、數(shù)據(jù)類型、抽象數(shù)據(jù)類型(ADT)等基本概念及

它們之間的關系。

2．掌握線性表、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)的 ADT 定義以及基于不同存儲方式（順序、

鏈式等）的實現(xiàn)，并能對占用存儲空間情況和算法的時間復雜度進行分析。

3．掌握典型的查找結(jié)構(gòu)（靜態(tài)表、搜索樹、散列等）、查找算法的基本思想及性能

分析。

4．掌握內(nèi)部排序（選擇、插入、交換、歸并等）的重要算法的基本思想、特點及性

能分析。

5．能夠運用學習的數(shù)據(jù)結(jié)構(gòu)及算法的知識和技能進行問題的分析與求解，即能對問

題進行抽象建模，能熟練使用高級語言（C 或 C++或 JAVA 等）進行模型的具體實

現(xiàn)（編程）。

二、考試內(nèi)容

1．數(shù)據(jù)結(jié)構(gòu)和算法的重要性

（1）基本概念及它們之間的關系

（2）各種存儲結(jié)構(gòu)的空間占用情況及映射邏輯關系的方式

（3）算法的評價及對算法漸近時間復雜性的理解

2．一般線性表

（1）一般線性表 ADT 的定義

（2）線性表 ADT 基于順序存儲的實現(xiàn)（存儲方式、特點、重要操作的算法，下同）

（3）線性表 ADT 基于鏈式存儲的實現(xiàn)（存儲方式、特點、重要操作的算法，下同）

3．特殊線性表（棧、隊列、字符串、數(shù)組）

（1）棧的特點及棧 ADT 的定義

（2）棧 ADT 基于順序存儲的實現(xiàn)

（3）棧 ADT 基于鏈式存儲的實現(xiàn)（4）棧 ADT 的應用（表達式求值、遞歸處理、迷宮問題）

（5）隊列的特點及隊列 ADT 的定義

（6）隊列 ADT 基于順序存儲的實現(xiàn)

（7）隊列 ADT 基于鏈式存儲的實現(xiàn)

（8）隊列 ADT 的應用（廣度遍歷、資源分配問題）

（9）字符串特點及串 ADT 的定義

（10）字符串 ADT 基于順序存儲的實現(xiàn)（重點掌握經(jīng)典的模式匹配算法：BF，KMP）

（11）數(shù)組的特點及 ADT 定義

（12）數(shù)組 ADT 基于順序存儲的實現(xiàn)（重點掌握多維數(shù)組的存儲結(jié)構(gòu)）

（13）特殊矩陣的存儲及操作實現(xiàn)（重點掌握分布有規(guī)律的特殊矩陣和分布無規(guī)律的

稀疏矩陣如何高效存儲及矩陣典型操作的實現(xiàn)）

4．樹與二叉樹

（1）二叉樹的特點及 ADT 定義

（2）二叉樹的重要性質(zhì)及證明

（3）二叉樹基于順序存儲的實現(xiàn)

（4）二叉樹基于鏈式存儲的實現(xiàn)（重點掌握重要操作：建立、遍歷、求深度、計算葉

子等等）

（5）線索二叉樹的基本概念（為什么加線索？如何記錄線索？如何使用線索？）

（6）建立（畫）線索二叉樹

（7）樹、森林的定義及特點

（8）樹的存儲結(jié)構(gòu)（重點掌握子女-兄弟表示）

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

（10）樹和森林的遍歷

（11）哈夫曼（Huffman）樹和哈夫曼編碼的構(gòu)造過程

（12）二叉排序樹的定義及建立（重點掌握結(jié)點的插入和刪除的思想和過程）

（13）平衡二叉樹的定義及建立（平衡的目的？如何達到平衡？）

（14）堆的定義及建立和調(diào)整（堆的構(gòu)造和調(diào)整過程）5．圖

（1）圖的基本概念及 ADT 定義

（2）圖的 ADT 的實現(xiàn)（存儲方式及基本操作實現(xiàn)）

①鄰接矩陣存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）

②鄰接表存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）

③各種存儲方式下操作的算法實現(xiàn)（圖的建立、遍歷、插入邊、刪除邊等）

（3）圖的遍歷及生成樹

①深度優(yōu)先遍歷（思想、過程及算法實現(xiàn)）

②廣度優(yōu)先遍歷（思想、過程及算法實現(xiàn)）

（4）圖的基本應用（掌握算法的思想、過程）

①最小生成樹問題

②最短路徑問題

③有向圖與工程問題（工程調(diào)度：AOV 網(wǎng)與拓撲排序，工期：AOE 網(wǎng)與關鍵路徑）

6．查找

（1）查找的基本概念

（2）順序查找法（監(jiān)視哨法的思想和算法）

（3）折半查找法（思想和算法）

（4）樹查找（二叉排序樹）

（5）B 樹及其基本操作、B+樹的基本概念（思想和過程）

（6）散列（Hash）查找（Hash 函數(shù)和解決沖突的方法的思想和過程）

（6）各種查找表的組織及查找算法的時間復雜度、平均查找長度的分析

7．排序

（1）排序的基本概念

（2）基于“插入”思想的排序方法

①直接插入排序

②折半插入排序（思想和過程）

③希爾排序（思想和過程）（3）基于“交換”思想的排序方法

①冒泡排序（思想、過程和算法）

②快速排序（思想、過程和算法）

（4）基于“選擇”思想的排序方法

①簡單選擇排序（思想、過程和算法）

②堆排序（思想和過程）

（5）基于“歸并”思想的排序方法

二路歸并排序（思想、過程）

（6）各種常用內(nèi)部排序算法的特點及應用

三、參考書目

1. 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc C++語言描述）（第 2 版）.殷人昆主編. 北京：清華大

學出版社.2007.6

2. 數(shù)據(jù)結(jié)構(gòu)（C 語言版）.嚴蔚敏、吳偉民編著. 北京：清華大學出版社. 2007

中國石油大學(華東)

添加中國石油大學(華東)學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[中國石油大學(華東)考研分數(shù)線、中國石油大學(華東)報錄比、中國石油大學(華東)考研群、中國石油大學(華東)學姐微信、中國石油大學(華東)考研真題、中國石油大學(華東)專業(yè)目錄、中國石油大學(華東)排名、中國石油大學(華東)保研、中國石油大學(華東)公眾號、中國石油大學(華東)研究生招生）]即可在手機上查看相對應中國石油大學(華東)考研信息或資源。