重慶郵電大學2017年碩士研究生入學
《數據結構（802）》考試大綱

考試內容和要求
（一）、概述
[1]熟悉數據結構相關術語的含義，掌握基本概念。
[2]掌握數據結構中邏輯結構、存儲結構以及兩者之間關系。
[3]了解抽象數據類型的定義和表示方法。
[4]掌握計算語句頻度和估算算法時間復雜度的方法。
（二）、線性結構——線性表、棧、隊列和串
[1]理解線性表的邏輯結構定義。
[2]熟悉抽象數據類型定義方式。
[3]熟練掌握線性結構的順序和鏈式存儲結構。
[4]掌握線性表、棧和隊列的應用，理解各種線性結構之間的關系。
[5]熟悉串的邏輯結構和典型存儲方式，理解串的主要運算。
[6]熟練掌握在順序和鏈式存儲結構上實現相關基本操作。
（三）、數組和廣義表
[1]掌握數組的邏輯特征與存儲方式。
[2]掌握矩陣的壓縮存儲方式及其特點。
[3]理解廣義表的邏輯特征和存儲方式。
[4]掌握廣義表的基本操作。
（四）、樹和二叉樹
[1]熟練掌握二叉樹的基本性質。
[2]熟練掌握二叉樹的各種存儲結構的實現，各存儲結構的特點及適用范圍。
[3]熟練掌握二叉樹各種遍歷策略的遞歸算法。
[4]熟練掌握基于遍歷策略的二叉樹操作及應用。
[5]樹（森林）與二叉樹的關系（存儲）
[6]了解最優樹的特性，掌握建立最優樹和哈夫曼編碼的方法。
（五）、圖
[1]掌握圖的定義及其它基本概念。
[2]掌握圖的存儲結構——鄰接矩陣、鄰接表。
[3]掌握圖的遍歷方法——深度優先搜索、廣度優先搜索。

[4]掌握最小生成樹生成方法。
[5]掌握圖的最短路徑算法。
[6]了解拓撲排序概念，了解關鍵路徑算法。
（六）、查找（檢索）
[1]掌握靜態查找表——順序表、有序表、索引表的查找算法；理解算法復雜性的分析過程；熟悉算法特
點。
[2]掌握動態查找表——二叉排序樹和平衡二叉樹的概念、基本操作及其實現。
[3]理解B?樹的概念和特點。
[4]熟練掌握哈希查找思想、哈希沖突解決方法、哈希查找性能。
（七）、排序
[1]掌握直接插入排序、希爾排序、冒泡排序、簡單選擇排序的思想及實現方法；
[2]掌握快速排序、堆排序、歸并排序的思想和及實現方法。
[3]掌握算法復雜度及其分析方法；熟悉算法特點及其適用場景。
（八）、文件
[1]了解與文件有關的基本概念；
[2]理解文件結構及其組織方式——順序、索引、散列文件（HASH）。
參考書目
《數據結構（C語言版）》，嚴蔚敏、吳偉民，清華大學出版社。