2020中山大學(xué)南方學(xué)院專插本專業(yè)課《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

2020年中山大學(xué)南方學(xué)院專插本專業(yè)課《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱是什么？即將參加2020年廣東專插本考試且將中山大學(xué)南方學(xué)院作為目標(biāo)院校的考生注意啦，此次易學(xué)仕小編為大家整理了《數(shù)據(jù)結(jié)構(gòu)與算法》的考試大綱，詳情如下：

《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

一、考試性質(zhì)

普通高等學(xué)校本科插班生招生考試是由?？飘厴I(yè)生參加的選拔性考試。高等學(xué)校根據(jù)考生的成績，按已確定的招生計(jì)劃，德、智、體全面衡量，擇優(yōu)錄取。該考生所包含的內(nèi)容將大致穩(wěn)定，試題形式多種，具有對學(xué)生把握本課程程度的較強(qiáng)識別、區(qū)分能力。

二.考試內(nèi)容及要求

一、考試基本要求

通過數(shù)據(jù)結(jié)構(gòu)與算法理論的學(xué)習(xí)，使學(xué)生學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時(shí)間分析和空間分析技術(shù)；配合算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力，對理論和實(shí)踐的操作使學(xué)生得到全面的領(lǐng)會和深刻的認(rèn)識。

二、考核知識點(diǎn)及考核要求

本大綱的考核中，按照“識記”、“領(lǐng)會”、“簡單應(yīng)用”和“綜合應(yīng)用”等四個(gè)層次規(guī)定應(yīng)達(dá)到的能力層次要求。各能力層次為遞進(jìn)等級關(guān)系，后者必須建立在前者的基礎(chǔ)上，其含義是：

識記：要求考生知道有關(guān)的名詞、概念、原理、知識的含義，并能正確認(rèn)識或識別。

領(lǐng)會：要求在識記的基礎(chǔ)上，能把握相關(guān)的基本概念、基本原理和基本方法，掌握有關(guān)概念、原理、方法的區(qū)別與聯(lián)系。

簡單應(yīng)用：要求在領(lǐng)會的基礎(chǔ)上，運(yùn)用所掌握的基本概念、基本原理和基本方法中的少量知識點(diǎn)，分析和解決一般的理論問題或?qū)嶋H問題。

綜合應(yīng)用：要求在簡單應(yīng)用的基礎(chǔ)上，運(yùn)用學(xué)過的多個(gè)知識點(diǎn)，綜合分析和解決比較復(fù)雜的實(shí)際問題。

第 1 章 緒論

一、考核知識點(diǎn)

1、數(shù)據(jù)結(jié)構(gòu)的基本概念

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

3、算法的概念和特性

4、算法時(shí)間復(fù)雜度和空間復(fù)雜度分析

二、考核要求

1、識記

（1）數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

2、領(lǐng)會

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

（2）算法的定義和特性

（3）評價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)

3、簡單應(yīng)用

（1）簡單數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計(jì)

（2）簡單數(shù)據(jù)結(jié)構(gòu)程序的時(shí)間復(fù)雜度和空間復(fù)雜度分析

4、綜合應(yīng)用

（1）數(shù)據(jù)結(jié)構(gòu)的一些基本概念

（2）算法的時(shí)間復(fù)雜度分析

第 2 章 線性表

一、考核知識點(diǎn)

1、線性表的類型定義

2、線性表的順序表示和實(shí)現(xiàn)

3、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

4、線性表的應(yīng)用

二、考核要求

1、識記

（1）線性表的定義

（2）線性表的特點(diǎn)

2、領(lǐng)會

（1）線性表的抽象數(shù)據(jù)類型定義

3、簡單應(yīng)用

（1） 線性表的順序存儲和基本操作實(shí)現(xiàn)

（2）單鏈表的存儲和基本實(shí)現(xiàn)

（3）雙鏈表的存儲和基本實(shí)現(xiàn)

（4）一元多項(xiàng)式的表示和基本運(yùn)算

4、綜合應(yīng)用

（1）一般線性表的合并

（2）有序表的合并

第 3 章 棧和隊(duì)列

一、考核知識點(diǎn)

1、棧的類型定義

2、棧的存儲結(jié)構(gòu)表示和實(shí)現(xiàn)

3、棧與遞歸的實(shí)現(xiàn)

4、隊(duì)列的類型

6、隊(duì)列的存儲結(jié)構(gòu)標(biāo)識和實(shí)現(xiàn)

二、考核要求

1、識記

（1）棧的類型定義

（2）隊(duì)列的類型定義

2、領(lǐng)會

（1）棧的存儲結(jié)構(gòu)表示和實(shí)現(xiàn)

（2）隊(duì)列的存儲結(jié)構(gòu)標(biāo)識和實(shí)現(xiàn)

3、簡單應(yīng)用

（1）表達(dá)式求值

（2）打印楊暉三角形

（3）迷宮求解問題

（4）模擬汽車加油站問題

第 4 章 串、數(shù)組和廣義表

一、考核知識點(diǎn)

1、串的表示和實(shí)現(xiàn)

2、數(shù)組的存儲方法

3、特殊存儲結(jié)構(gòu)

4、廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

二、考核要求

1、識記

（1）串的表示和實(shí)現(xiàn)

（2）數(shù)組的存儲方法

2、領(lǐng)會

（1）特殊結(jié)構(gòu)的存儲方法

（2）廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

3、綜合應(yīng)用

（1）古典的模式匹配算法

第 5 章 樹和二叉樹

一、考核知識點(diǎn)

1、二叉樹的定義和術(shù)語

2、二叉樹的性質(zhì)，特殊的二叉樹

3、二叉樹的存儲結(jié)構(gòu)，順序存儲和二叉鏈表

4、二叉樹的遍歷（前序、中序、后序、層次）

5、樹和森林的定義，樹的存儲

6、樹、森林與二叉樹的轉(zhuǎn)換、

7、樹的應(yīng)用，哈夫曼樹和哈夫曼編碼

8、線索化二叉樹

二、考核要求

1、識記

（1）二叉樹的定義

（2）樹和森林的定義

2、領(lǐng)會

（1）二叉樹的術(shù)語

（2）特殊的二叉樹

3、簡單應(yīng)用

（1）二叉樹的存儲結(jié)構(gòu)

（2）線索化二叉樹

（3）樹、森林和二叉樹的轉(zhuǎn)換

4、綜合應(yīng)用

（1）二叉樹的性質(zhì)

（2）二叉樹的遍歷方法

（3）哈夫曼編碼

第 6 章 圖

一、考核知識點(diǎn)

1、圖的定義和術(shù)語

2、圖的存儲結(jié)構(gòu)（鄰接表和鄰接矩陣）

3、圖的遍歷（深度優(yōu)先和廣度優(yōu)先）

4、構(gòu)造最小生成樹的短發(fā)

5、拓?fù)渑判蚝完P(guān)鍵路徑

6、求最短路徑問題

二、考核要求

1、識記

（1）圖的定義和術(shù)語

2、領(lǐng)會

（1）圖的鄰接矩陣表示法

（2）圖的鄰接表表示法

3、簡單應(yīng)用

（1）圖的遍歷方法：深度優(yōu)先遍歷、廣度優(yōu)先遍歷

3、綜合應(yīng)用

（1）最小生成樹算法：普里姆算法、克魯斯卡爾算法

（2）拓?fù)渑判蚝完P(guān)鍵路徑

（3）最短路徑問題算法：迪杰斯特拉算法、佛洛依德算法

第 7 章 查找

一、考核知識點(diǎn)

1、查找的基本概念

2、基于線性表的查找

3、基于樹表的查找

4、散列表

二、考核要求

1、識記

（1）查找的基本概念

（2）散列表的基本概念

2、簡單應(yīng)用

（1）順序查找

（2）折半查找

（3）二叉排序樹、平衡二叉樹

3、綜合應(yīng)用

（1）散列函數(shù)的構(gòu)造方法

（2）處理沖突的方法

（3）散列表的查找和分析

第 8 章 排序

一、考核知識點(diǎn)

1、排序的基本概念

2、插入排序

3、交換排序

4、選擇排序

5、歸并排序

6、基數(shù)排序

7、排序算法分析

二、考核要求

1、識記

（1）排序的基本概念

2、簡單應(yīng)用

（1）直接插入排序、折半插入排序、希爾排序

（2）快速排序、冒泡排序、2-路歸并排序

（3）簡單選擇排序、堆排序

（4）排序算法分析

三.考試形式及試卷結(jié)構(gòu)

1、考試形式為閉卷，筆試，考試時(shí)間為 120 分鐘，試卷滿分為 100 分。

2、試卷內(nèi)容比例：第一～四章占 40%，第五、六章占 40%，第七、八章占20%。

3、試卷題型比例：判斷題占 20%，選擇題占 30%，綜合計(jì)算分析題占 50%。

4、試卷難易比例：易、中、難分別為 30%，50%，20%。

四.參考書目

嚴(yán)蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)與算法（C 語言版）（第 2 版）．人民郵電出版社．2016年。

五.題型示例

一、判斷題（每題 2 分，對的打√，錯(cuò)的打×，共 20 分）

1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。 （ ）

2.圖的拓?fù)溆行蛐蛄胁皇俏ㄒ坏摹＃?）

3.鏈?zhǔn)酱鎯Φ木€性表可以實(shí)現(xiàn)順序存取。 （ ）

二、選擇題（每題 2 分，共 30 分）

1．計(jì)算機(jī)內(nèi)部數(shù)據(jù)表示的最小單位是（ ）

A.數(shù)據(jù)

B.數(shù)據(jù)項(xiàng)

C.數(shù)據(jù)元素

D.數(shù)據(jù)庫

2．線性表采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)的存儲地址是（ ）

A.必須是不連續(xù)的

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)

3．棧與一般線性表的區(qū)別是（ ）

A.元素個(gè)數(shù)

B.元素類型

C.邏輯結(jié)構(gòu)

D.插入、刪除元素的位置

三、綜合計(jì)算分析題（共 50 分）

1.假設(shè)一棵二叉樹的先序序列是：ABDFCEGH，中序序列是：BFDAGEEHC。試

分析：

（1）畫出這棵二叉樹；

（2）將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。

2.設(shè)有一組關(guān)鍵字（9，1，23，14，55，20，84，27，30），采用哈希函數(shù)：

H（key）=key%8，表長為 10，用開放地址法的二次探測法處理沖突。要求：

（1）對該關(guān)鍵字序列構(gòu)造哈希表；

（2）計(jì)算其查找成功的平均查找長度。

以上就是“2020中山大學(xué)南方學(xué)院專插本專業(yè)課《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱”全部內(nèi)容?？忌趥淇嫉倪^程中，如遇到問題或有疑難的話，請?jiān)L問易學(xué)仕在線，會有專業(yè)老師為你解答! 小編在此預(yù)祝大家在2020年廣東專插本考試中都能取得優(yōu)異成績。

推薦閱讀：

中山大學(xué)南方學(xué)院專插本2020有哪些專業(yè)