2022年合肥師范學院專升本數據結構考試大綱

第一章 緒論

數據結構的研究范疇;數據、數據元素、數據項、數據對象概念;邏 輯結構、物理結構概念;算法分析 (時間復雜度) 。

第二章 線性表

順序表、鏈表特點;線性表在順序表及鏈表中實現基本操作 (查找、 插入、刪除等) 的算法;有序表在鏈表中實現插入、刪除、合并等操作的 算法。

第三章 棧和隊列

棧的定義;給定入棧序列，如何得到一特定出棧序列;棧的表示;隊 列的定義;隊列的順序表示和實現—循環隊列。

第四章 串

串的定義和有關基本概念。

第五章 數組

數組的定義;數組元素在內存中的地址計算方法。

第六章 樹和二叉樹

樹的定義及相關術語;二叉樹的定義;二叉樹的性質;二叉樹的先序、 中序、后序遍歷方法;給出先序 (或后序) +中序遍歷序列，能畫出這棵 樹，并寫出對應后序 (或先序) 遍歷序列;二叉樹的先序、中序、后序遍 歷的遞歸算法及應用;樹、森林與二叉樹之間的轉換;哈夫曼樹的定義、 構造及其應用。

第七章 圖

圖的定義和術語;圖的鄰接矩陣表示法和鄰接表表示法;深度優先搜 索、廣度優先搜索遍歷;求最小生成樹;拓撲排序序列。

第八章 查找

順序查找、折半查找、索引順序查找對表的要求及查找效率;折半查 找算法;二叉排序樹的查找方法及算法;給出一組關鍵字、哈希函數和處 理沖突的方法，構造哈希表，求平均查找長度。

第九章 內部排序

直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆 排序、歸并排序時間復雜度 、輔助空間、 穩定性;上述幾種內部排序方 法的特點;希爾排序、快速排序、堆排序的排序過程。

【參考書目】

1.《C 語言程序設計》(第 4 版) ，蘇小紅等編著，高等教育出版社，2019.8 2.《數據結構》 (C 語言版) (第 2 版) ，嚴蔚敏、李冬梅、吳偉民編著， 人民郵電出版社，2015.2. 3.《新編數據結構習題與解析》,李春葆、喻丹丹、曾平、曾慧編著，清 華大學出版社，2013.5.