2025年云南專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

2024-12-27

來源：好老師升學(xué)幫

閱讀 928

＂導(dǎo)讀：本文是2025年云南專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱，由好老師升學(xué)幫整理供大家參考！

一、考試內(nèi)容及要求

　　(一)了解

　　1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、抽象數(shù)據(jù)類型等概念。

　　2.數(shù)據(jù)結(jié)構(gòu)的基本概念;數(shù)據(jù)的邏輯結(jié)構(gòu)及物理結(jié)構(gòu);算法的定義及特點(diǎn)。

　　3.線性表的定義及特點(diǎn);在線性表上常進(jìn)行的基本操作。

　　4.頭指針、頭結(jié)點(diǎn)及首元結(jié)點(diǎn)的概念及它們的區(qū)別;設(shè)置頭結(jié)點(diǎn)的好處。

　　5.棧和隊(duì)列的定義、特點(diǎn)、表示方法和實(shí)現(xiàn);入棧和出棧序列的對應(yīng)關(guān)系;入隊(duì)和出隊(duì)序列的對應(yīng)關(guān)系。

　　6.串的定義及其相關(guān)概念。

　　7.數(shù)組的定義、運(yùn)算和存儲(chǔ);特殊矩陣和稀疏矩陣的壓縮存儲(chǔ);廣義表的定義和相關(guān)概念。

　　8.樹的定義、基本術(shù)語和存儲(chǔ)結(jié)構(gòu);二叉樹的定義和性質(zhì);二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作的基本原理;樹和森林的相關(guān)概念;Huffman樹和Huffman編碼。

　　9.圖的定義和常用術(shù)語。

　　10.查找表、關(guān)鍵字、查找操作、靜態(tài)查找、動(dòng)態(tài)查找等查找相關(guān)概念。

　　11.排序的定義及相關(guān)概念;各種常用內(nèi)部排序操作的一趟排序的概念。

　　(二)掌握

　　1.數(shù)據(jù)邏輯結(jié)構(gòu)的分類;邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的區(qū)別與聯(lián)系;物理存儲(chǔ)結(jié)構(gòu)的分類及不同存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。

　　2.數(shù)據(jù)結(jié)構(gòu)的二元組表示;算法設(shè)計(jì)的要求;算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。

　　3.線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu);兩種不同存儲(chǔ)結(jié)構(gòu)下常用操作算法的實(shí)現(xiàn)及復(fù)雜度分析;順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。

　　4.循環(huán)鏈表、雙向鏈表及雙向循環(huán)鏈表的基本操作算法實(shí)現(xiàn)及這些特殊鏈表的應(yīng)用;

　　5.棧和隊(duì)列的與線性表的關(guān)系;棧和隊(duì)列的共同點(diǎn)與不同點(diǎn);棧和隊(duì)列在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)時(shí)基本操作的算法實(shí)現(xiàn);棧和隊(duì)列的應(yīng)用。

　　6.串與線性表的聯(lián)系與區(qū)別;串的存儲(chǔ)表現(xiàn)形式;串的常用操作及串操作的特點(diǎn);空串和空格串的區(qū)別。串的模式匹配及求子串的基本原理。

　　7.數(shù)組存儲(chǔ)的特點(diǎn)和數(shù)組操作的特點(diǎn);一維數(shù)組和二維數(shù)組中數(shù)據(jù)元素存儲(chǔ)地址的計(jì)算;特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)時(shí)，一維存儲(chǔ)空間地址下標(biāo)和其行號列標(biāo)的對應(yīng)關(guān)系;廣義表的嵌套定義;求解非空廣義表的表頭和表尾;求解廣義表的長度和深度。

　　8.二叉樹的特點(diǎn)及性質(zhì);二叉樹的存儲(chǔ)結(jié)構(gòu)及其特點(diǎn);二叉樹遍歷的基本原理;樹和森林與二叉樹的相互轉(zhuǎn)換;樹和森林的遍歷及與其對應(yīng)二叉樹遍歷的關(guān)系;構(gòu)建哈夫曼樹的基本原理及哈夫曼編碼。

　　9.圖的存儲(chǔ)結(jié)構(gòu)及其遍歷操作;求最小生成樹、關(guān)鍵路徑、最短路徑的基本方法，拓?fù)渑判虻幕驹?最小生成樹的構(gòu)造過程(Prim算法和Kmskal算法)。

　　10.各種查找方法的基本查找原理;每種查找的適用范圍及平均查找長度的分析;各種查找的特點(diǎn);不同查找方法查找某一特定數(shù)據(jù)元素時(shí)的具體比較次數(shù);靜態(tài)查找與動(dòng)態(tài)查找的特點(diǎn);二叉排序樹與平衡二叉樹的特點(diǎn);哈希函數(shù)的構(gòu)造方法及沖突解決辦法。

　　11.各種常用內(nèi)部排序方法基本實(shí)現(xiàn)原理;各種內(nèi)排序算法的基本思想和算法的時(shí)間復(fù)雜度、空間復(fù)雜度分析，不同排序方法的比較。

　　(三)應(yīng)用

　　1.能閱讀用類C語言編寫的算法。

　　2.能分析算法所實(shí)現(xiàn)的功能、運(yùn)行結(jié)果和時(shí)間、空間復(fù)雜度。

　　3.能應(yīng)用線性表的基本操作算法解決現(xiàn)實(shí)生活中的相關(guān)問題。

　　4.能應(yīng)用棧和隊(duì)列解決現(xiàn)實(shí)生活中的相關(guān)問題。

　　5.能設(shè)計(jì)算法解決現(xiàn)實(shí)生活中字符串處理的問題。

　　6.能根據(jù)實(shí)際的特殊矩陣推算其壓縮存儲(chǔ)一維存儲(chǔ)空間地址下標(biāo)與其元素的行號列標(biāo)之間的對應(yīng)關(guān)系，能計(jì)算對應(yīng)元素的實(shí)際物理地址;能求解實(shí)際非空廣義表的表頭、表尾、長度和深度。

　　7.能利用樹和二叉樹設(shè)計(jì)算法解決現(xiàn)實(shí)生活中的相關(guān)問題;能針對實(shí)際數(shù)據(jù)進(jìn)行哈夫曼編碼。

　　8.能應(yīng)用圖的基本操作解決現(xiàn)實(shí)生活中的相關(guān)問題。

　　9.能針對實(shí)際查找記錄，選擇合適的查找算法進(jìn)行數(shù)據(jù)查找。

　　10.能針對實(shí)際待排序記錄，選擇合適的排序方法進(jìn)行數(shù)據(jù)排序操作，并能分析實(shí)際采用的排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度。