?2022年合肥師范學(xué)院專升本數(shù)據(jù)結(jié)構(gòu)考試大綱

2022年合肥師范學(xué)院專升本數(shù)據(jù)結(jié)構(gòu)考試大綱

第一章 緒論

數(shù)據(jù)結(jié)構(gòu)的研究范疇;數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象概念;邏 輯結(jié)構(gòu)、物理結(jié)構(gòu)概念;算法分析 (時(shí)間復(fù)雜度) 。

第二章 線性表

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

第三章 棧和隊(duì)列

棧的定義;給定入棧序列，如何得到一特定出棧序列;棧的表示;隊(duì) 列的定義;隊(duì)列的順序表示和實(shí)現(xiàn)—循環(huán)隊(duì)列。

第四章 串

串的定義和有關(guān)基本概念。

第五章 數(shù)組

數(shù)組的定義;數(shù)組元素在內(nèi)存中的地址計(jì)算方法。

第六章 樹和二叉樹

樹的定義及相關(guān)術(shù)語(yǔ);二叉樹的定義;二叉樹的性質(zhì);二叉樹的先序、 中序、后序遍歷方法;給出先序 (或后序) +中序遍歷序列，能畫出這棵 樹，并寫出對(duì)應(yīng)后序 (或先序) 遍歷序列;二叉樹的先序、中序、后序遍 歷的遞歸算法及應(yīng)用;樹、森林與二叉樹之間的轉(zhuǎn)換;哈夫曼樹的定義、 構(gòu)造及其應(yīng)用。

第七章 圖

圖的定義和術(shù)語(yǔ);圖的鄰接矩陣表示法和鄰接表表示法;深度優(yōu)先搜 索、廣度優(yōu)先搜索遍歷;求最小生成樹;拓?fù)渑判蛐蛄小?/p>

第八章 查找

順序查找、折半查找、索引順序查找對(duì)表的要求及查找效率;折半查 找算法;二叉排序樹的查找方法及算法;給出一組關(guān)鍵字、哈希函數(shù)和處 理沖突的方法，構(gòu)造哈希表，求平均查找長(zhǎng)度。

第九章 內(nèi)部排序

直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆 排序、歸并排序時(shí)間復(fù)雜度 、輔助空間、 穩(wěn)定性;上述幾種內(nèi)部排序方 法的特點(diǎn);希爾排序、快速排序、堆排序的排序過(guò)程。

【參考書目】

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