2023年山東青年政治學院專升本數(shù)據(jù)結構考試大綱

2023-04-06

來源：好老師升學幫

閱讀 1419

＂導讀：2023年山東青年政治學院專升本數(shù)據(jù)結構科目考試內容包括各種數(shù)據(jù)組織中的數(shù)據(jù)邏輯結構、存儲結構以及有關操作的算法，內容涉及線性結構、樹型結構、圖狀結構、查找和排序?？疾橐罂蓜澐譃椤傲私狻薄ⅰ袄斫狻焙汀罢莆铡比齻€層次，旨在考查考生對各類數(shù)據(jù)結構進行運用的熟練程度、考生的計算思維以及考生運用和設計算法解決現(xiàn)實應用問題的能力。

《數(shù)據(jù)結構》是2023年山東青年政治學院計算機科學與技術專業(yè)考試科目之一，滿分100分，考試題型：名詞解釋、填空、選擇題、簡答題和論述題?？荚嚧缶V明確了考試內容，考試題型，考試要求等。需要考試該科目的同學一定要研究考試大綱，院校會根據(jù)考試大綱進行出題，具體考試大綱內容請參考下方。

Ⅰ. 考試要求

本科目考試內容包括各種數(shù)據(jù)組織中的數(shù)據(jù)邏輯結構、存儲結構以及有關操作的算法，內容涉及線性結構、樹型結構、圖狀結構、查找和排序?？疾橐罂蓜澐譃椤傲私狻?、“理解”和“掌握”三個層次，旨在考查考生對各類數(shù)據(jù)結構進行運用的熟練程度、考生的計算思維以及考生運用和設計算法解決現(xiàn)實應用問題的能力。具體內容與要求如下：

一、基本概念與算法分析基礎

(一)了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、邏輯結構、存儲結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型的基本概念。掌握數(shù)據(jù)邏輯結構和數(shù)據(jù)存儲結構的分類。

(二)了解算法定義、性質、設計策略以及評價標準，理解算法與程序的區(qū)別。

(三)理解問題規(guī)模、語句頻度、時間復雜性、空間復雜性的概念。掌握對非遞歸算法進行時間復雜性和空間復雜性分析的方法。

二、線性結構

(一)理解線性表的概念、特點和抽象數(shù)據(jù)類型定義。

(二)掌握順序表的實現(xiàn)方式、性質以及各種基本運算(取值、插入、刪除、查找)。掌握單鏈表的實現(xiàn)方式、性質以及各種基本運算(取值、插入、刪除、查找、創(chuàng)建)。理解單鏈表的變形(循環(huán)單鏈表、雙向鏈表)以及基本運算(插入、刪除)。理解順序表與單鏈表在時空性能方面的差別。

(三)理解棧的概念以及抽象數(shù)據(jù)類型定義。掌握棧的兩種存儲結構實現(xiàn)以及各種基本運算(元素入棧、元素出棧、取棧頂元素)。了解棧的現(xiàn)實應用。

(四)理解隊列的概念以及抽象數(shù)據(jù)類型定義。掌握隊列的兩種存儲結構實現(xiàn)以及各種基本運算(元素入隊、元素出隊、取隊頭元素)，理解標準順序隊列與循環(huán)隊列之間的差別，掌握循環(huán)隊列基本運算(求隊列長度、元素入隊、元素出隊、取隊頭元素)。了解隊列的現(xiàn)實應用。理解棧與隊列在操作和應用方面的差別。

(五)了解數(shù)組的抽象數(shù)據(jù)類型定義。掌握數(shù)組的順序存儲結構以及該結構下的地址計算方法。了解特殊矩陣、稀疏矩陣的壓縮存儲方法。

(六)理解字符串的概念、基本操作(串賦值、串比較、求串長、串聯(lián)接、求子串)以及抽象數(shù)據(jù)類型定義。了解字符串的存儲結構。理解字符串模式匹配的BF(Brute-Force)算法。

(七)理解廣義表的相關概念(廣義表、廣義表長度、表頭、表尾)，掌握廣義表的基本操作(取表頭、取表尾)，了解廣義表的存儲結構。

三、樹型結構

(一)理解樹的定義以及相關概念(結點、度、葉子、非終端結點、雙親、孩子、兄弟、祖先、子孫、層次、堂兄弟、深度、有序樹、無序樹、森林)以及樹的抽象數(shù)據(jù)類型定義。

(二)掌握二叉樹的定義、性質、各種存儲結構和遍歷算法(前序遍歷、中序遍歷、后序遍歷和層次遍歷)。了解線索二叉樹的概念、分類、存儲結構及線索化算法。

(三)掌握樹的三種存儲結構(雙親表示法、孩子表示法、孩子兄弟表示法)以及樹、森林與二叉樹間的相互轉換方法。理解樹和森林的遍歷算法。

(四)掌握哈夫曼樹的定義以及相關概念(路徑、路徑長度、樹的路徑長度、權、結點的帶權路徑長度、樹的帶權路徑長度)，理解哈夫曼編碼的基本思想，掌握哈夫曼樹的構造方法以及哈夫曼編碼方法。

四、圖狀結構

(一)理解圖的基本概念(有向圖、無向圖、子圖、有向完全圖、無向完全圖、稀疏圖、稠密圖、權、網(wǎng)、鄰接點、度、入度、出度、路徑、路徑長度、回路、環(huán)、簡單路徑、連通圖、連通分量、強連通圖、強連通分量、連通圖的生成樹)。掌握圖的鄰接矩陣和鄰接表存儲結構，理解這兩種存儲結構的優(yōu)缺點。

(二)理解圖的兩種遍歷的基本思想，掌握圖的兩種遍歷算法。

(三)掌握最小生成樹的概念以及求圖的最小生成樹的算法(Kruskal和Prim算法)。

(四)掌握求圖的單源最短路徑問題算法(Dijkstra算法)以及所有頂點間最短路徑問題算法(Floyd算法)。

(五)理解頂點表示活動網(wǎng)絡(AOV網(wǎng))的概念，掌握求拓撲排序的算法。

(六)理解邊表示活動網(wǎng)絡(AOE網(wǎng))的概念，掌握求關鍵路徑的算法。

五、散列與查找算法

(一)理解查找相關概念(查找表、關鍵字、動態(tài)查找表、靜態(tài)查找表)及基于平均查找長度的效率評價方法。

(二)理解散列查找的基本思想和沖突的概念。了解散列函數(shù)的構造方法以及沖突處理方法。

(三)掌握順序查找算法、折半查找算法，理解分塊查找算法。

(四)了解二叉排序樹、平衡二叉樹、B-樹和B+樹的概念。

六、排序算法

(一)掌握典型的插入排序算法(直接插入排序、希爾排序)。