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

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

二、考試內(nèi)容

一、考試的基本要求

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

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

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

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

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

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

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

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

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

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

2.基本功

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

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

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

二、考核知識點和考核要求

靠前章導(dǎo)言

首先，評估知識點

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

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

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

二、考核要求

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

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

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

第二章線性表

首先，評估知識點

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

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

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

二、考核要求

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

2.理解:順序存儲和鏈?zhǔn)酱鎯Φ谋容^，以及各種鏈表的基本運算算法

第三章堆棧和隊列

首先，評估知識點

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

2.隊列的定義和操作特點，如存儲、入隊、出隊、判斷空(滿)、取隊列靠前個元素等。

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

二、考核要求

1.記憶:棧和隊列的概念、功能、操作特點和主要操作。

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

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

第四章弦

首先，評估知識點

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

2.字符串的基本操作。

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

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

二、考核要求

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

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

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

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

首先，評估知識點

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

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

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

4.廣義表的定義。

二、考核要求

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

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

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

第六章樹和二叉樹

首先，評估知識點

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

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

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

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

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

二、考核要求

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

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

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

第七章圖

首先，評估知識點

1.圖的定義。

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

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

(2)度、度、頂點度。

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

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

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

4.遍歷圖

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

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

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

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

7.最短路徑算法。

二、考核要求

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

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

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

第8章動態(tài)存儲管理(不需要)

第九章搜索

首先，評估知識點

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

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

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

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

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

4.哈希表

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

二、考核要求

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

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

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

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

首先，評估知識點

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

2.直接插入排序的想法

3.快速分類

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

4.選擇排序

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

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

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

二、考核要求

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

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

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

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

第十二章文件(不要求)

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

1.考試形式:采用閉卷筆試形式。考試時間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):試題分為客觀題和主觀題?？陀^題一般包括填充空題、選擇題、名詞解釋、程序填充空題等。主觀題一般包括簡答題和算法設(shè)計題。

四.參考書目

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

v題舉例

一、填寫空

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

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.先進先出b .后進先出c .后進后出d .沒有順序

第三，名詞解釋

1.連通圖

2.完全二叉樹

四.在程序中填寫空問題

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

{ Tree * p = boot

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

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

____________________________

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

___________________________

其他

___________________________

}

return(0)；

}

動詞 （verb的縮寫）簡答題

1、嘗試比較鏈?zhǔn)酱鎯晚樞虼鎯Φ膬?yōu)缺點。

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

六、算法設(shè)計題

設(shè)計了一種算法來合并遞減數(shù)組A [0...n-1]和前導(dǎo)節(jié)點的遞增單鏈表B組成前導(dǎo)節(jié)點的遞增鏈表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年廣東專版考試時間是3月7-8日。對于準(zhǔn)備參加考試的考生，我們和樂貞老師一起來看看廣東寒山師范學(xué)院2020年專版數(shù)據(jù)結(jié)構(gòu)考試大綱。了解考試大綱后，考生備考會更加得心應(yīng)手。

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