2020年廣東專版考試時(shí)間已經(jīng)確定，準(zhǔn)備參加考試的考生必須在考試前做好準(zhǔn)備。樂貞老師和李老師整理了廣東寒山師范學(xué)院2020年數(shù)據(jù)結(jié)構(gòu)考試大綱，希望對(duì)考生有所幫助。

本科分班考試是由大學(xué)畢業(yè)生參加的選擇性考試?！稊?shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)(本科)的專業(yè)基礎(chǔ)課?？荚囍饕疾榭忌鷮?duì)存儲(chǔ)組織、維護(hù)操作、基本應(yīng)用、常用基本數(shù)據(jù)結(jié)構(gòu)(順序表、鏈表、棧、隊(duì)列、樹、二叉樹、圖等)的搜索排序等基本算法的掌握情況。)，從而保證后續(xù)課程的學(xué)習(xí)。

二、考試內(nèi)容

一、考試的基本要求

1.基礎(chǔ)理論知識(shí)

(l)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，算法的描述方法，算法分析的基本概念。

(2)線性表的基本概念，線性表的基本操作，以及這些操作分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)和復(fù)雜度分析。

(3)棧和隊(duì)列的定義、存儲(chǔ)結(jié)構(gòu)、實(shí)現(xiàn)和典型應(yīng)用。

(4)字符串的定義及其基本操作。

(5)數(shù)組的定義、操作和存儲(chǔ)。

(6)樹的定義、基本術(shù)語和存儲(chǔ)結(jié)構(gòu)，二叉樹的定義和性質(zhì)，二叉樹的存儲(chǔ)結(jié)構(gòu)和各種運(yùn)算，哈夫曼樹的概念和應(yīng)用。

(7)圖形的定義和術(shù)語，圖形的存儲(chǔ)結(jié)構(gòu)及其基本操作。

(8)各種搜索方法的算法、適用范圍和時(shí)間復(fù)雜度分析。

(9)、各種內(nèi)部行算法的基本思想和時(shí)間復(fù)雜度分析，以及不同排序方法的比較。

2.基本功

(1)、可以用基本數(shù)據(jù)結(jié)構(gòu)及其算法來描述和解決實(shí)際的簡(jiǎn)單問題。

(2)能看懂“C類”語言寫的算法，能根據(jù)需要寫“C類”語言的算法。

(3)可以分析算法的功能、運(yùn)行結(jié)果和時(shí)間復(fù)雜度。

二、考核知識(shí)點(diǎn)和考核要求

靠前章導(dǎo)言

首先，評(píng)估知識(shí)點(diǎn)

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、元素、節(jié)點(diǎn)等基本概念。抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)。

2.算法，它的特點(diǎn)，以及如何用類C語言描述算法。

3.算法設(shè)計(jì)的基本要求以及計(jì)算語句頻率和估計(jì)算法時(shí)間復(fù)雜度的方法。

二、考核要求

1.記憶:數(shù)據(jù)結(jié)構(gòu)的基本概念和四種基本數(shù)據(jù)結(jié)構(gòu)的特征。

2.理解:四種基本數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算，算法復(fù)雜度度量的基本概念。

3.應(yīng)用:用類C語言描述算法

第二章線性表

首先，評(píng)估知識(shí)點(diǎn)

1.線性表的定義和基本操作。

2.線性表順序存儲(chǔ)結(jié)構(gòu)的表示和基本操作。

3.線性表鏈存儲(chǔ)，有附加頭節(jié)點(diǎn)和單鏈表，循環(huán)鏈表和雙鏈表沒有附加頭節(jié)點(diǎn)，搜索、插入、刪除等基本操作。

二、考核要求

1.記憶:線性表的基本概念和運(yùn)算，各種鏈表的表示。

2.理解:順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的比較，以及各種鏈表的基本運(yùn)算算法

第三章堆棧和隊(duì)列

首先，評(píng)估知識(shí)點(diǎn)

1.棧的定義和操作特征，包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)，以及棧、棧、判斷空 (full)、取棧頂元素等基本操作。

2.隊(duì)列的定義和操作特點(diǎn)，如存儲(chǔ)、入隊(duì)、出隊(duì)、判斷空(滿)、取隊(duì)列靠前個(gè)元素等。

3.棧應(yīng)用的例子，比如數(shù)字轉(zhuǎn)換，表達(dá)式求值等。

二、考核要求

1.記憶:棧和隊(duì)列的概念、功能、操作特點(diǎn)和主要操作。

2.理解:棧和隊(duì)列相對(duì)于一般線性表的特殊性，棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，循環(huán)隊(duì)列。

3.應(yīng)用:棧和隊(duì)列的常用場(chǎng)合。

第四章弦

首先，評(píng)估知識(shí)點(diǎn)

1.字符串的定義和空字符串的概念。

2.字符串的基本操作。

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

4.字符串的基本模式匹配算法。

二、考核要求

1.記憶:字符串的相關(guān)概念。

2.理解:字符串的基本運(yùn)算，字符串的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

3.應(yīng)用:使用字符串的基本運(yùn)算功能。

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

首先，評(píng)估知識(shí)點(diǎn)

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

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

3.三重表的概念和基本操作。

4.廣義表的定義。

二、考核要求

1.記憶:數(shù)組的順序存儲(chǔ)結(jié)構(gòu)和廣義表的定義。

2.理解:二維數(shù)組的地址計(jì)算和三重表的表示。

3.應(yīng)用:利用三重表解決稀疏矩陣的存儲(chǔ)問題。

第六章樹和二叉樹

首先，評(píng)估知識(shí)點(diǎn)

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

2.二叉樹(完全二叉樹和全二叉樹)的定義和性質(zhì)，二叉樹的存儲(chǔ)結(jié)構(gòu)(順序表示和二進(jìn)制鏈表表示)。

3.二叉樹遍歷算法(一階、中階、末階、層次)。

4.將樹和森林轉(zhuǎn)換為二叉樹的方法(孩子和兄弟表示)。

5.樹的路徑長度，樹的加權(quán)路徑長度，哈夫曼樹的構(gòu)造方法。

二、考核要求

1.記憶:樹木的基本概念

2.了解:二叉樹的存儲(chǔ)結(jié)構(gòu)，遍歷算法，子兄弟表示，樹的路徑長度，以及霍夫曼樹的構(gòu)造方法

3.應(yīng)用:使用霍夫曼樹解決一些優(yōu)化問題

第七章圖

首先，評(píng)估知識(shí)點(diǎn)

1.圖的定義。

2.圖形的基本術(shù)語。

(1)圖與無向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖。

(2)度、度、頂點(diǎn)度。

(3)頂點(diǎn)之間的路徑、路徑長度和循環(huán)。

3.圖的存儲(chǔ)結(jié)構(gòu)

(1)鄰接矩陣(2)鄰接表(包括逆鄰接表)

4.遍歷圖

(1)深度優(yōu)先搜索遍歷圖算法及其時(shí)間復(fù)雜度。

(2)廣度優(yōu)先搜索遍歷圖的思想及其時(shí)間復(fù)雜度。

5.生成樹和最小生成樹的概念。

6.拓?fù)渑判蚍?/p>

7.最短路徑算法。

二、考核要求

1.記憶:圖的基本概念和術(shù)語，最小生成樹、拓?fù)渑判蚝妥疃搪窂降母拍詈退惴ㄋ枷搿?/p>

2.理解:圖形的存儲(chǔ)方式以及基于這種存儲(chǔ)方式的基本操作(求進(jìn)度、出度、下一條邊等)。)

3.應(yīng)用:拓?fù)湫蛄械膽?yīng)用，最短路徑的應(yīng)用。

第8章動(dòng)態(tài)存儲(chǔ)管理(不需要)

第九章搜索

首先，評(píng)估知識(shí)點(diǎn)

1.搜索、關(guān)鍵詞、平均搜索長度的概念。

2.靜態(tài)查找表查找算法及其效率(最差和平均查找長度)。

(1)順序搜索(2)二分搜索法(3)塊搜索

3.動(dòng)態(tài)查找表

二叉排序樹的定義、構(gòu)造過程、搜索算法和效率。

4.哈希表

哈希表的特點(diǎn)。(2)構(gòu)造哈希函數(shù)的方法(除了留余數(shù)等。).(3)處理沖突的方法。

二、考核要求

1.記憶:搜索的基本概念，靜態(tài)查找表和動(dòng)態(tài)查找表的概念，以及哈希表的概念

2.了解:各種靜態(tài)搜索算法的比較次數(shù)分析；二叉排序樹的生成過程和搜索算法；哈希函數(shù)的選擇，沖突處理的方法，哈希搜索的過程。

3.應(yīng)用:分析各種搜索算法的比較次數(shù)。

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

首先，評(píng)估知識(shí)點(diǎn)

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

2.直接插入排序的想法

3.快速分類

(1)冒泡排序算法。(2)快速排序的思想。

4.選擇排序

(1)簡(jiǎn)單的選擇和排序算法。

(2)堆的定義和堆排序的思想。

5.雙向合并排序的思路。

二、考核要求

1.記憶:直接插入排序、冒泡排序和簡(jiǎn)單選擇排序的想法

2.了解:快速排序、堆排序、雙向合并排序的思路，以及各種排序方法的穩(wěn)定性、平均比較次數(shù)、平均移動(dòng)次數(shù)的分析。

3.應(yīng)用:使用類C語言或類C語言編譯直接插入排序、冒泡排序、簡(jiǎn)單選擇排序等排序算法。

第11章外部排序(不需要)

第十二章文件(不要求)

三、考試形式和試卷結(jié)構(gòu)

1.考試形式:采用閉卷筆試形式?？荚嚂r(shí)間120分鐘，全卷100分鐘。

2.試卷中各章節(jié)的比例:靠前章約占8%，第二、三、四、五章約占40%，第六章約占20%，第七章約占15%，第九章約占12%，第十章約占5%。

3.不同能力水平的試題要求的分?jǐn)?shù)，記憶約為30%，理解約為40%，應(yīng)用約為30%。

4.試題難度比例:易30%左右，中50%左右，難20%左右。

5.試卷結(jié)構(gòu):試題分為客觀題和主觀題?？陀^題一般包括填充空題、選擇題、名詞解釋、程序填充空題等。主觀題一般包括簡(jiǎn)答題和算法設(shè)計(jì)題。

四.參考書目

主要參考書:《數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴(yán)為民吳偉民主編，清華大學(xué)出版社。

v題舉例

一、填寫空

1.深度為8(根的層數(shù)為1)的全二叉樹有_ _ _ _ _ _ _ _ _ _ _ _ _ _個(gè)葉節(jié)點(diǎn)。

2.字符串的長度是指_ _ _ _ _ _ _ _。

二、選擇題

1.如果堆棧的堆疊順序是a、b、c、d、e，那么堆棧的不可能輸出順序是_ _ _ _ _ _ _ _。

答。e d c b a B. d e c b a C. d c e a b D. a b c d e

2.棧操作數(shù)據(jù)的原理是_ _ _ _ _ _。

A.先進(jìn)先出b .后進(jìn)先出c .后進(jìn)后出d .沒有順序

第三，名詞解釋

1.連通圖

2.完全二叉樹

四.在程序中填寫空問題

下面的過程是在二進(jìn)制排序樹中查找給定的關(guān)鍵字，如果找到就返回1，如果沒有找到就返回0。請(qǐng)完成該程序。

{ Tree * p = boot

while(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _){

if(item . key , lt；boot->；data.key)

____________________________

else if(item . key , gt；p-,gt。data.key)

___________________________

其他

___________________________

}

return(0)；

}

動(dòng)詞 （verb的縮寫）簡(jiǎn)答題

1、嘗試比較鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)的優(yōu)缺點(diǎn)。

2.已知二叉樹的中間序列和后面序列分別是BDCEAFHG和DECBHGFA，所以盡量寫出前面的序列。

六、算法設(shè)計(jì)題

設(shè)計(jì)了一種算法來合并遞減數(shù)組A [0...n-1]和前導(dǎo)節(jié)點(diǎn)的遞增單鏈表B組成前導(dǎo)節(jié)點(diǎn)的遞增鏈表C。單一鏈表的已知數(shù)據(jù)結(jié)構(gòu)定義為:

struct SingleLink{

ElemType數(shù)據(jù)；

SingleLink * next

};

使用功能原型:

single link * link aandb(elem type A[]，int n，single link * B)；

數(shù)組a和鏈表b是通過函數(shù)參數(shù)傳遞的，n是數(shù)組的大小。該函數(shù)的返回值是生成的鏈表。

2020年廣東專版考試時(shí)間是3月7-8日。對(duì)于準(zhǔn)備參加考試的考生，我們和樂貞老師一起來看看廣東寒山師范學(xué)院2020年專版數(shù)據(jù)結(jié)構(gòu)考試大綱。了解考試大綱后，考生備考會(huì)更加得心應(yīng)手。

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