2020年廣東專版考試時間已經確定，準備參加考試的考生必須在考試前做好準備。樂貞老師和李老師整理了廣東寒山師范學院2020年數據結構考試大綱，希望對考生有所幫助。

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

二、考試內容

一、考試的基本要求

1.基礎理論知識

(l)數據結構的基本概念和術語，算法的描述方法，算法分析的基本概念。

(2)線性表的基本概念，線性表的基本操作，以及這些操作分別在順序存儲和鏈式存儲結構下的實現和復雜度分析。

(3)棧和隊列的定義、存儲結構、實現和典型應用。

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

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

(6)樹的定義、基本術語和存儲結構，二叉樹的定義和性質，二叉樹的存儲結構和各種運算，哈夫曼樹的概念和應用。

(7)圖形的定義和術語，圖形的存儲結構及其基本操作。

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

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

2.基本功

(1)、可以用基本數據結構及其算法來描述和解決實際的簡單問題。

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

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

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

靠前章導言

首先，評估知識點

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

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

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

二、考核要求

1.記憶:數據結構的基本概念和四種基本數據結構的特征。

2.理解:四種基本數據結構的基本運算，算法復雜度度量的基本概念。

3.應用:用類C語言描述算法

第二章線性表

首先，評估知識點

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

2.線性表順序存儲結構的表示和基本操作。

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

二、考核要求

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

2.理解:順序存儲和鏈式存儲的比較，以及各種鏈表的基本運算算法

第三章堆棧和隊列

首先，評估知識點

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

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

3.棧應用的例子，比如數字轉換，表達式求值等。

二、考核要求

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

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

3.應用:棧和隊列的常用場合。

第四章弦

首先，評估知識點

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

2.字符串的基本操作。

3.字符串的順序存儲結構及其下基本操作的實現。

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

二、考核要求

1.記憶:字符串的相關概念。

2.理解:字符串的基本運算，字符串的順序存儲結構及其基本運算。

3.應用:使用字符串的基本運算功能。

第五章數組和廣義表

首先，評估知識點

1.數組的順序存儲結構。

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

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

4.廣義表的定義。

二、考核要求

1.記憶:數組的順序存儲結構和廣義表的定義。

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

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

第六章樹和二叉樹

首先，評估知識點

1.樹的定義和術語。

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

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

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

5.樹的路徑長度，樹的加權路徑長度，哈夫曼樹的構造方法。

二、考核要求

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

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

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

第七章圖

首先，評估知識點

1.圖的定義。

2.圖形的基本術語。

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

(2)度、度、頂點度。

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

3.圖的存儲結構

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

4.遍歷圖

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

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

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

6.拓撲排序法

7.最短路徑算法。

二、考核要求

1.記憶:圖的基本概念和術語，最小生成樹、拓撲排序和最短路徑的概念和算法思想。

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

3.應用:拓撲序列的應用，最短路徑的應用。

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

第九章搜索

首先，評估知識點

1.搜索、關鍵詞、平均搜索長度的概念。

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

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

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

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

4.哈希表

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

二、考核要求

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

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

3.應用:分析各種搜索算法的比較次數。

第十章內部排序

首先，評估知識點

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

2.直接插入排序的想法

3.快速分類

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

4.選擇排序

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

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

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

二、考核要求

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

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

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

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

第十二章文件(不要求)

三、考試形式和試卷結構

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

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

3.不同能力水平的試題要求的分數，記憶約為30%，理解約為40%，應用約為30%。

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

5.試卷結構:試題分為客觀題和主觀題?？陀^題一般包括填充空題、選擇題、名詞解釋、程序填充空題等。主觀題一般包括簡答題和算法設計題。

四.參考書目

主要參考書:《數據結構》(C語言版)嚴為民吳偉民主編，清華大學出版社。

v題舉例

一、填寫空

1.深度為8(根的層數為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.棧操作數據的原理是_ _ _ _ _ _。

A.先進先出b .后進先出c .后進后出d .沒有順序

第三，名詞解釋

1.連通圖

2.完全二叉樹

四.在程序中填寫空問題

下面的過程是在二進制排序樹中查找給定的關鍵字，如果找到就返回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、嘗試比較鏈式存儲和順序存儲的優(yōu)缺點。

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

六、算法設計題

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

struct SingleLink{

ElemType數據；

SingleLink * next

};

使用功能原型:

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

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

2020年廣東專版考試時間是3月7-8日。對于準備參加考試的考生，我們和樂貞老師一起來看看廣東寒山師范學院2020年專版數據結構考試大綱。了解考試大綱后，考生備考會更加得心應手。

部分內容來源于網絡轉載、學生投稿，如有侵權或對本站有任何意見、建議或者投訴，請聯系郵箱（1296178999@qq.com）反饋。 未經本站授權，不得轉載、摘編、復制或者建立鏡像， 如有違反，本站將追究法律責任！