2023年湖南人文科技學(xué)院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

瀏覽次數(shù):次 發(fā)布時(shí)間:2023-04-21

《數(shù)據(jù)結(jié)構(gòu)》是2023年湖南人文科技學(xué)院專升本考試科目之一,考試時(shí)長(zhǎng) 120分鐘,滿分100分,考試題型:填空題、單項(xiàng)選擇題、判斷題、簡(jiǎn)答題、應(yīng)用與設(shè)計(jì)題等。2023年湖南人文科技學(xué)院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱已經(jīng)公布,考試大綱明確了考試內(nèi)容,考試題型,考試要求等。需要考試該科目的同學(xué)一定要研究考試大綱,院校會(huì)根據(jù)考試大綱進(jìn)行出題,具體考試大綱內(nèi)容請(qǐng)參考下方。

2023年湖南人文科技學(xué)院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、考試形式:筆試(閉卷)

二、考試時(shí)量:120分鐘

三、卷面分?jǐn)?shù):100分

四、考核內(nèi)容與要求

(一)緒論

1、考核知識(shí)點(diǎn)

(1)合適的數(shù)據(jù)結(jié)構(gòu)在解決實(shí)際應(yīng)用問(wèn)題中的關(guān)鍵性;以及學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義。

(2)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)等基本概念。

(3)數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲(chǔ)結(jié)構(gòu)表示方法。

(4)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。

(5)算法的五個(gè)特點(diǎn)。

(6)算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均的時(shí)間復(fù)雜度等概念。

(7)算法描述和算法分析的方法,對(duì)于一般算法能分析出時(shí)間復(fù)雜度。

2、考核要求

(1)識(shí)記

1)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)。

2)合適的數(shù)據(jù)結(jié)構(gòu)在解決實(shí)際應(yīng)用問(wèn)題中的關(guān)鍵性,以及學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義。

3)數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)和兩種存儲(chǔ)結(jié)構(gòu)表示方法。

(2)理解

算法的描述和分析:算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均的時(shí)間復(fù)雜度。

(二)線性表

1、考核知識(shí)點(diǎn)

(1)線性表的類型定義。

(2)順序表的含義及特點(diǎn),順序表上的插入、刪除操作及其平均時(shí)間性能分析。

(3)鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。

(4)單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法及其時(shí)間復(fù)雜度。

(5)循環(huán)鏈表上尾指針取代頭指針的作用。

(6)單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點(diǎn)。

(7)雙向鏈表的定義和相關(guān)算法。

(8)順序表和鏈表的比較,以及如何選擇其一作為其存儲(chǔ)結(jié)構(gòu)才能取得較優(yōu)的時(shí)空性能。

2、考核要求

(1)識(shí)記

1)線性表的邏輯結(jié)構(gòu)特征;

2)線性表上定義的基本運(yùn)算,并利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算。

(2)理解

1)順序表和鏈表的比較,各自的優(yōu)缺點(diǎn)。

2)針對(duì)線性表上所需要執(zhí)行的主要操作,知道選擇順序表還是鏈表作為其存儲(chǔ)結(jié)構(gòu)才能取得較優(yōu)的時(shí)空性能。

(3)綜合應(yīng)用

1)順序表的含義及特點(diǎn),順序表上的插入、刪除操作及其平均時(shí)間性能分析。

2)單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別;

3)單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法及其時(shí)間復(fù)雜度。

4)循環(huán)鏈表中尾指針取代頭指針的作用,

5)單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點(diǎn)。

6)雙鏈表的定義和相關(guān)算法。

(三)棧和隊(duì)列

1、考核知識(shí)點(diǎn)

(1)棧的抽象數(shù)據(jù)類型的定義

(2)棧的表示和實(shí)現(xiàn)

(3)棧的簡(jiǎn)單應(yīng)用

(4)抽象數(shù)據(jù)類型隊(duì)列的定義

(5)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

(6)隊(duì)列的順序表示和實(shí)現(xiàn)

2、考核要求

(1)理解

棧和隊(duì)列的特點(diǎn),棧和隊(duì)列各自的使用情況。

(2)綜合應(yīng)用

1)棧的邏輯結(jié)構(gòu)特點(diǎn),棧與線性表的異同。

2)順序棧和鏈棧上實(shí)現(xiàn)進(jìn)棧、退棧等基本算法。

3)利用棧解決簡(jiǎn)單的實(shí)際問(wèn)題。

4)隊(duì)列邏輯結(jié)構(gòu)特點(diǎn),隊(duì)列與線性表的異同。

5)順序隊(duì)列(主要是循環(huán)隊(duì)列)和鏈隊(duì)列上實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法。

6)順序隊(duì)列的“假溢出”現(xiàn)象及其采用循環(huán)隊(duì)列進(jìn)行解決的方法。

(四)串

1、考核知識(shí)點(diǎn)

(1)串的定義、空串、空格串、子串、主串、串相等。

(2)串的基本操作。

(3)串的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。

(4)串的堆分配存儲(chǔ)表示及其在堆分配存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。

(5)串的鏈?zhǔn)酱鎯?chǔ)表示

2、考核要求

(1)理解

串的有關(guān)概念及其基本運(yùn)算。

(2)簡(jiǎn)單應(yīng)用

1)串的三種存儲(chǔ)表示。

2)使用串解決與串相關(guān)的簡(jiǎn)單的應(yīng)用問(wèn)題。

(五)數(shù)組和廣義表

1、考核知識(shí)點(diǎn)

(1)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。

(2)二維數(shù)組的按行存儲(chǔ)及按列存儲(chǔ)和計(jì)算數(shù)組元素的地址計(jì)算公式。

(3)矩陣的壓縮存儲(chǔ)、特殊矩陣的表示。

2、考核要求

(1)理解

1)多維數(shù)組的邏輯結(jié)構(gòu)特征。

2)多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及其地址計(jì)算方式。

3)特殊矩陣和稀疏矩陣的概念。

4)疏矩陣的壓縮存儲(chǔ)方式——三元組表。

(六)樹(shù)和二叉樹(shù)

1、考核知識(shí)點(diǎn)

(1)樹(shù)的定義和術(shù)語(yǔ)。

(2)二叉樹(shù)(完全二叉樹(shù)、滿二叉樹(shù))的定義和性質(zhì)(結(jié)論)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)——順序表示法和鏈表表示法。

(3)二叉樹(shù)的三種遍歷方法及相應(yīng)的遞歸算法。

(4)樹(shù)的存儲(chǔ)表示法——孩子表示法、雙親表示法、孩子兄弟表示法。

(5)樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換方法。

(6)樹(shù)的路徑長(zhǎng)度、樹(shù)的帶權(quán)路徑長(zhǎng)度、赫夫曼樹(shù)(最優(yōu)二叉樹(shù))的構(gòu)造方法。

(7)赫夫曼編碼方法。

2、考核要求

(1)理解

1)樹(shù)的邏輯結(jié)構(gòu)特征。

2)樹(shù)的不同表示方法。

3)樹(shù)的常用術(shù)語(yǔ)及含義。

4)樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換方法。

5)樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。

6)樹(shù)的遍歷方法。

(2)簡(jiǎn)單應(yīng)用

1)二叉樹(shù)的定義及樹(shù)與二叉樹(shù)的差別。

2)二叉樹(shù)的性質(zhì),了解相應(yīng)的證明方法。

3)二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)、特點(diǎn)及適用范圍。

4)最優(yōu)二叉樹(shù)和前綴編碼的概念及特點(diǎn)。

5)赫夫曼算法的思想。

6)根據(jù)給定的葉結(jié)點(diǎn)及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹(shù)。

7)根據(jù)最優(yōu)二叉樹(shù)構(gòu)造對(duì)應(yīng)的赫夫曼編碼。

(3)綜合應(yīng)用

1)二叉樹(shù)的三種遍歷算法,理解其執(zhí)行過(guò)程。

2)根據(jù)不同的遍歷方法,應(yīng)能得出其相應(yīng)的結(jié)點(diǎn)訪問(wèn)次序。

(七)圖

1、考核知識(shí)點(diǎn)

(1)圖的邏輯結(jié)構(gòu)特征。

(2)圖的常用術(shù)語(yǔ)及含義。

(3)圖的鄰接矩陣表示法存儲(chǔ)結(jié)構(gòu)。

(4)圖的鄰接表表示法。

(5)圖的深度優(yōu)先遍歷。

(6)圖的廣度優(yōu)先遍歷。

(7)生成樹(shù)和最小生成樹(shù)。

(8)構(gòu)造最小生成樹(shù)的PRIM算法思想。

(9)構(gòu)造最小生成樹(shù)的Kruskal算法思想。

(10)拓?fù)渑判颉?/p>

(11)關(guān)鍵路徑。

(12)關(guān)于最短路徑的算法——Dijkstra算法思想。

2、考核要求

(1)理解

1)圖的邏輯結(jié)構(gòu)及特征。

2)圖的常用術(shù)語(yǔ)及含義。

3)生成樹(shù)和最小生成樹(shù)的概念。

4)對(duì)給定的圖遍歷,畫(huà)出深度優(yōu)先和廣度優(yōu)先生成樹(shù)或森林。

5)Prim和 Kruskal算法的基本思想。

6)要求對(duì)給定的連通圖,根據(jù)Prim和Kruskal算法構(gòu)造最小生成樹(shù)。。

7)求單源點(diǎn)的最短路徑問(wèn)題的Dijkstra算法的基本思想。

8)拓?fù)渑判虻幕舅枷牒筒襟E。

9)對(duì)給定的有向圖,若拓?fù)湫蛄写嬖?,則要求寫(xiě)出一個(gè)或多個(gè)拓?fù)湫蛄小?/p>

(2)簡(jiǎn)單應(yīng)用

1)圖的鄰接矩陣表示法和鄰接表表示法。

2)根據(jù)應(yīng)用問(wèn)題的特點(diǎn)選擇合適的存儲(chǔ)結(jié)構(gòu)。

3)連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法。

4)確定兩種遍歷的頂點(diǎn)訪問(wèn)序列。

5)圖的兩種遍歷和樹(shù)的遍歷之間的關(guān)系。

6)兩種遍歷算法分別使用的數(shù)據(jù)結(jié)構(gòu)(棧和隊(duì)列)。

(八)查找

1、考核知識(shí)點(diǎn)

(1)查找的定義關(guān)鍵字、查找、平均查找長(zhǎng)度。

(2)靜態(tài)查找表的查找算法(順序查找、折半查找、分塊查找(索引順序表的查找))其效率(最壞和平均長(zhǎng)度)。

(3)二叉排序樹(shù)的查找算法及其效率。

(4)平衡二叉樹(shù)的定義。

(5)哈希法的特點(diǎn)。

(6)哈希函數(shù)和散列地址。

(7)處理沖突的方法:開(kāi)放定址法和鏈地址法。開(kāi)放定址法又分為線性探測(cè)再散列、二次探測(cè)再散列和偽隨機(jī)探測(cè)再散列。

2、考核要求

(1)識(shí)記

1)查找在數(shù)據(jù)處理中的重要性。

2)查找成功、不成功的含義。

(2)簡(jiǎn)單應(yīng)用

1)順序查找、折半查找、分塊查找的基本思想、算法實(shí)現(xiàn)和查找效率分析。

2)二叉排序樹(shù)和二叉平衡樹(shù)的定義、特點(diǎn)

3)建立一棵二叉排序樹(shù)的過(guò)程就是對(duì)輸入序列的排序過(guò)程,輸入序列對(duì)所建立的二叉排序樹(shù)形態(tài)的影響

4)哈希表、哈希函數(shù)、哈希地址(散列地址)、裝填因子等有關(guān)概念

5)哈希函數(shù)的構(gòu)造方法和解決沖突的方法

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

1、考核知識(shí)點(diǎn)

(1)排序的目的、分類和排序方法的穩(wěn)定性的定義。

(2)插入排序:直接插入排序的算法、折半插入排序的算法、希爾排序的思想。

(3)選擇排序的思想

(4)堆排序的方法、堆的定義、初始堆的建立。

(5)起泡排序的思想。

(6)快速排序的算法、快速排序的最壞情況時(shí)間復(fù)雜度的分析。

2、考核要求

(1)識(shí)記

1)排序在數(shù)據(jù)處理中的重要性。

1)排序方法穩(wěn)定性的含義。

2)排序方法的分類及算法好壞的評(píng)判標(biāo)準(zhǔn)。

(2)理解

1)分類排序和其它幾類排序方法的區(qū)別。

(3)簡(jiǎn)單應(yīng)用

1)堆、極小堆、極大堆、堆頂?shù)扔嘘P(guān)概念和定義。

2)堆的性質(zhì)及堆與完全二叉樹(shù)的關(guān)系。

3)直接選擇排序和堆排序的基本思想和算法實(shí)現(xiàn)。

4)針對(duì)給定的輸入序列,寫(xiě)出堆排序的排序過(guò)程。

(4)綜合應(yīng)用

1)針對(duì)給定的輸入序列,要能寫(xiě)出直接插入排序的排序過(guò)程。

2)起泡排序的基本思想。

3)快速排序的基本思想和算法實(shí)現(xiàn),以及在最好、最壞和平均情況下的時(shí)間性能分析,了解算法的穩(wěn)定性。

4)樞軸元素的選擇對(duì)排序的影響。

針對(duì)給定的輸入序列,能寫(xiě)出快速排序的排序過(guò)程。

五、題型

填空題10分(每空2分);單項(xiàng)選擇題40分(每小題2分);

判斷題10分(每小題1分);簡(jiǎn)答題10分(每小題5分);

應(yīng)用與設(shè)計(jì)題30分(2-3個(gè)小題)

六、參考教材

1、主要教材:李筠,姜學(xué)軍主編,《數(shù)據(jù)結(jié)構(gòu)(高職高專精品課程規(guī)劃教材計(jì)算機(jī)系列)》. 清華大學(xué)出版社,2008年8月

2、參考教材:嚴(yán)蔚敏,吳偉民主編.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社,2011年7月

本文資料來(lái)源:http://www.huhst.edu.cn/jwc2019/info/1045/3868.htm

研究考試大綱,對(duì)大綱中的考點(diǎn)及相關(guān)要求進(jìn)行認(rèn)真研究,是應(yīng)考的關(guān)鍵。正在備考專升本的同學(xué),關(guān)注湖南樂(lè)貞教育網(wǎng)站可以了解更多專升本的考試信息。如果在學(xué)習(xí)上有困難,自制力差,可以在下方留下你的聯(lián)系方式,我們的老師會(huì)針對(duì)你的學(xué)習(xí)情況給出建議。


湖南專升本最新資料領(lǐng)取

部分內(nèi)容來(lái)源于網(wǎng)絡(luò)轉(zhuǎn)載、學(xué)生投稿,如有侵權(quán)或?qū)Ρ菊居腥魏我庖?jiàn)、建議或者投訴,請(qǐng)聯(lián)系郵箱(1296178999@qq.com)反饋。 未經(jīng)本站授權(quán),不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像, 如有違反,本站將追究法律責(zé)任!


本文標(biāo)簽: 湖南人文科技學(xué)院專升本湖南人文科技學(xué)院專升本考試大綱

上一篇:2023年湖南人文科技學(xué)院專升本《C語(yǔ)言程序設(shè)計(jì)》考試大綱                  下一篇:2023年湖南人文科技學(xué)院專升本《旅游學(xué)概論》考試大綱

湖南3+2 統(tǒng)招專升本

一鍵查詢