【導語】

2025年中國石油大學(華東)研究生859數據結構考試大綱已正式公布，根據中國石油大學(華東)公告《859 數據結構.pdf》所示。為了方便廣大考生，以下是在職研究生網小編整理的2025年中國石油大學(華東)研究生859數據結構考試大綱詳細信息：

考試科目名稱：數據結構 考試時間：180 分鐘，滿分：150 分

一、考試要求

1．理解數據結構、存儲結構、算法、數據類型、抽象數據類型(ADT)等基本概念及它們之間的關系。

2．掌握線性表、樹、圖等基本數據結構的 ADT 定義以及基于不同存儲方式（順序、鏈式等）的實現，并能對占用存儲空間情況和算法的時間復雜度進行分析。

3．掌握典型的查找結構（靜態表、搜索樹、散列等）、查找算法的基本思想及性能分析。

4．掌握內部排序（選擇、插入、交換、歸并等）的重要算法的基本思想、特點及性能分析。

5．能夠運用學習的數據結構及算法的知識和技能進行問題的分析與求解，即能對問題進行抽象建模，能熟練使用高級語言（C 或 C++或 JAVA 等）進行模型的具體實現（編程）。 

二、考試內容

1．數據結構和算法的重要性

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

（2）各種存儲結構的空間占用情況及映射邏輯關系的方式

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

2．一般線性表

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

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

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

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

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

（2）棧 ADT 基于順序存儲的實現

（3）棧 ADT 基于鏈式存儲的實現

（4）棧 ADT 的應用（表達式求值、遞歸處理、迷宮問題）

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

（6）隊列 ADT 基于順序存儲的實現

（7）隊列 ADT 基于鏈式存儲的實現

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

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

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

（11）數組的特點及 ADT 定義

（12）數組 ADT 基于順序存儲的實現（重點掌握多維數組的存儲結構）

（13）特殊矩陣的存儲及操作實現（重點掌握分布有規律的特殊矩陣和分布無規律的稀疏矩陣如何高效存儲及矩陣典型操作的實現）

4．樹與二叉樹

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

（2）二叉樹的重要性質及證明

（3）二叉樹基于順序存儲的實現

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

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

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

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

（8）樹的存儲結構（重點掌握子女-兄弟表示）

（9）樹、森林與二叉樹的相互轉換

（10）樹和森林的遍歷

（11）哈夫曼（Huffman）樹和哈夫曼編碼的構造過程

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

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

（14）堆的定義及建立和調整（堆的構造和調整過程）

5．圖

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

（2）圖的 ADT 的實現（存儲方式及基本操作實現）

①鄰接矩陣存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）②鄰接表存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）③各種存儲方式下操作的算法實現（圖的建立、遍歷、插入邊、刪除邊等）（3）圖的遍歷及生成樹

①深度優先遍歷（思想、過程及算法實現）

②廣度優先遍歷（思想、過程及算法實現）

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

①最小生成樹問題

②最短路徑問題

③有向圖與工程問題（工程調度：AOV 網與拓撲排序，工期：AOE 網與關鍵路徑）

6．查找

（1）查找的基本概念

（2）順序查找法（監視哨法的思想和算法）

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

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

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

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

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

7．排序

（1）排序的基本概念

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

①直接插入排序

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

③希爾排序（思想和過程）

（3）基于“交換”思想的排序方法

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

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

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

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

②堆排序（思想和過程）

（5）基于“歸并”思想的排序方法二路歸并排序（思想、過程）

（6）各種常用內部排序算法的特點及應用

三、參考書目

1. 數據結構（用面向對象方法與 C++語言描述）（第 2 版）.殷人昆主編. 北京：清華大學出版社.2007.6

2. 數據結構（C 語言版）.嚴蔚敏、吳偉民編著. 北京：清華大學出版社. 2007

來源：https://yz.upc.edu.cn/_upload/article/files/42/1e/26a568f04561a5715eb31a516f78/4a9d0965-2c70-4777-aa1f-015e31d028aa.pdf

鄭重聲明：上述內容為《859 數據結構.pdf》所示做出的整理，不具有權威性和官方代表性，一切2025年中國石油大學(華東)研究生859數據結構考試大綱信息應以中國石油大學(華東)公布的官方信息為主，以上提供的內容僅供廣大考生參考。