【導(dǎo)語】

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

考試科目名稱：數(shù)據(jù)結(jié)構(gòu) 考試時(shí)間：180 分鐘，滿分：150 分

一、考試要求

1．理解數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法、數(shù)據(jù)類型、抽象數(shù)據(jù)類型(ADT)等基本概念及它們之間的關(guān)系。

2．掌握線性表、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)的 ADT 定義以及基于不同存儲(chǔ)方式（順序、鏈?zhǔn)降龋┑膶?shí)現(xiàn)，并能對(duì)占用存儲(chǔ)空間情況和算法的時(shí)間復(fù)雜度進(jìn)行分析。

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

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

5．能夠運(yùn)用學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)及算法的知識(shí)和技能進(jìn)行問題的分析與求解，即能對(duì)問題進(jìn)行抽象建模，能熟練使用高級(jí)語言（C 或 C++或 JAVA 等）進(jìn)行模型的具體實(shí)現(xiàn)（編程）。 

二、考試內(nèi)容

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

（1）基本概念及它們之間的關(guān)系

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

（3）算法的評(píng)價(jià)及對(duì)算法漸近時(shí)間復(fù)雜性的理解

2．一般線性表

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

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

（3）線性表 ADT 基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)（存儲(chǔ)方式、特點(diǎn)、重要操作的算法，下同）

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

（1）棧的特點(diǎn)及棧 ADT 的定義

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

（3）棧 ADT 基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)

（4）棧 ADT 的應(yīng)用（表達(dá)式求值、遞歸處理、迷宮問題）

（5）隊(duì)列的特點(diǎn)及隊(duì)列 ADT 的定義

（6）隊(duì)列 ADT 基于順序存儲(chǔ)的實(shí)現(xiàn)

（7）隊(duì)列 ADT 基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)

（8）隊(duì)列 ADT 的應(yīng)用（廣度遍歷、資源分配問題）

（9）字符串特點(diǎn)及串 ADT 的定義

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

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

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

（13）特殊矩陣的存儲(chǔ)及操作實(shí)現(xiàn)（重點(diǎn)掌握分布有規(guī)律的特殊矩陣和分布無規(guī)律的稀疏矩陣如何高效存儲(chǔ)及矩陣典型操作的實(shí)現(xiàn)）

4．樹與二叉樹

（1）二叉樹的特點(diǎn)及 ADT 定義

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

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

（4）二叉樹基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)（重點(diǎn)掌握重要操作：建立、遍歷、求深度、計(jì)算葉子等等）

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

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

（7）樹、森林的定義及特點(diǎn)

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

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

（10）樹和森林的遍歷

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

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

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

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

5．圖

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

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

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

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

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

（4）圖的基本應(yīng)用（掌握算法的思想、過程）

①最小生成樹問題

②最短路徑問題

③有向圖與工程問題（工程調(diào)度：AOV 網(wǎng)與拓?fù)渑判颍て冢篈OE 網(wǎng)與關(guān)鍵路徑）

6．查找

（1）查找的基本概念

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

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

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

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

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

（6）各種查找表的組織及查找算法的時(shí)間復(fù)雜度、平均查找長(zhǎng)度的分析

7．排序

（1）排序的基本概念

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

①直接插入排序

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

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

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

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

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

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

①簡(jiǎn)單選擇排序（思想、過程和算法）

②堆排序（思想和過程）

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

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

三、參考書目

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

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

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

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