2020廣東技術(shù)師范大學(xué)天河學(xué)院專(zhuān)插本專(zhuān)業(yè)課《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

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

廣東技術(shù)師范大學(xué)天河學(xué)院 2020 年本科插班生招生考試 《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

一、考試要求

本大綱為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科插班生專(zhuān)門(mén)編寫(xiě)，作為考試命題的依據(jù)。《數(shù)據(jù)結(jié)構(gòu)與算法》是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的一門(mén)學(xué)科核心課程，它是培養(yǎng)程序設(shè)計(jì)所用到的基本數(shù)據(jù)類(lèi)型和數(shù)據(jù)結(jié)構(gòu)的基本操作和解決實(shí)際軟件工程問(wèn)題的相關(guān)算法的重要課程。

《數(shù)據(jù)結(jié)構(gòu)與算法》課程考試旨在考察學(xué)生對(duì)本課程涉及的基本數(shù)據(jù)類(lèi)型、基本數(shù)據(jù)結(jié)構(gòu)的基本操作及基本算法應(yīng)用掌握的深度和廣度，具備進(jìn)一步學(xué)習(xí)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)后續(xù)課程的能力和基礎(chǔ)。

二、教材及主要參考書(shū)目

教材：《數(shù)據(jù)結(jié)構(gòu) c 語(yǔ)言版（第二版）》 嚴(yán)蔚敏、李冬梅、吳偉民著 中國(guó)工信出版集團(tuán) 人民郵電出版社

三、考試內(nèi)容

第 1 章 緒論

1、數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定

關(guān)系的數(shù)據(jù)元素的集合。

2、數(shù)據(jù)結(jié)構(gòu)的三要素：

1）邏輯結(jié)構(gòu)：集合結(jié)構(gòu)； 線(xiàn)性結(jié)構(gòu)：一對(duì)一關(guān)系；樹(shù)結(jié)構(gòu)：一對(duì)多關(guān)系；圖結(jié)構(gòu)：多對(duì)多關(guān)系。例如：線(xiàn)性表、棧、隊(duì)列、串、數(shù)組等是邏輯結(jié)構(gòu)；

2）存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

例如：順序表、鏈表、鏈隊(duì)列等是存儲(chǔ)結(jié)構(gòu)；

3）數(shù)據(jù)的操作：有插入、刪除、查找、排序等。

此處尤其要注意邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)分，多有考選擇題如：以下哪個(gè)是存儲(chǔ)結(jié)構(gòu)的術(shù)語(yǔ)或以下哪個(gè)不是存儲(chǔ)結(jié)構(gòu)的術(shù)語(yǔ)。

3、算法：（算法的概念、特性；算法優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)；算法分析的目的；熟記）；算法的時(shí)間復(fù)雜度的分析(能分析出一段程序的時(shí)間復(fù)雜度；掌握分析的方法)

第 2 章 線(xiàn)性表

1、順序表：存儲(chǔ)和操作；

如：兩個(gè)有序的順序表要合并成一個(gè)順序，要進(jìn)行的最少的比較次數(shù)。順序表中刪除或插入一個(gè)元素時(shí)進(jìn)行的移動(dòng)操作。

2、線(xiàn)性表:

1）單鏈表：

如：?jiǎn)捂湵碇袛?shù)據(jù)的插入、刪除和比較操作；例：以帶頭結(jié)點(diǎn)的單鏈表表示有序表，編寫(xiě)算法，從有序表 A 中刪除所有和有序表 B 中元素相同的結(jié)點(diǎn)。 帶頭結(jié)點(diǎn)的單鏈表中，刪除數(shù)據(jù)域的值為 n 的結(jié)點(diǎn)，或者刪除所有數(shù)據(jù)域的值為 n 的結(jié)點(diǎn)（意思是單鏈表中有多個(gè)數(shù)據(jù)域的值為 n）。

2）循環(huán)鏈表：

第 3 章 棧和隊(duì)列

1、棧：棧的應(yīng)用：如：棧在遞歸函數(shù)中的應(yīng)用，已知棧的入棧順序，求棧的出棧順序。

2、隊(duì)列：

已知循環(huán)鏈表的頭指針、尾指針，求長(zhǎng)度；

已知循環(huán)鏈表的頭指針、長(zhǎng)度，求尾指針；

已知循環(huán)鏈表的尾指針、長(zhǎng)度，求頭指針；

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

1、串類(lèi)型的定義

字符串的實(shí)現(xiàn)

字符串模式匹配算法

如：串匹配算法的實(shí)現(xiàn)：求子串在主串中首次出現(xiàn)位置的算法

2、數(shù)組:

數(shù)組的基本概念

數(shù)組的順序存儲(chǔ)方式

如：求二維數(shù)組某元素的存儲(chǔ)地址：按行優(yōu)先和按列優(yōu)先；

例：已知二維數(shù)組的首地址和每個(gè)元素的存儲(chǔ)長(zhǎng)度，求 A[i][j]存儲(chǔ)地址。

矩陣

矩陣的定義和操作

特殊矩陣

稀疏矩陣

求特殊矩陣的壓縮存儲(chǔ)：

如：某矩陣壓縮存儲(chǔ)一維數(shù)組 S[k]中，二維數(shù)組元素 a[i][j]存儲(chǔ)在一維數(shù)組 S[k]中時(shí)元素下標(biāo) k 與二維數(shù)組元素下標(biāo) i，j 的關(guān)系。

3、廣義表

基本概念

如：廣義表的深度、長(zhǎng)度的計(jì)算；Head(L)求表頭函數(shù)和 Tail(L)求表

尾函數(shù)的應(yīng)用。

廣義表 L=((a,b),((c,d),(e,f)))

廣義表的深度=?

廣義表的長(zhǎng)度=?

head(tail(head(tail(L))))=?

第 5 章 樹(shù)和二叉樹(shù)

1、樹(shù)的基本概念

樹(shù)的定義

基本術(shù)語(yǔ)

2、二叉樹(shù)

二叉樹(shù)的定義

二叉樹(shù)的性質(zhì)

如：已知完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)，求該二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)。

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

3、二叉樹(shù)的遍歷

遍歷的定義

遍歷算法

如：已知二叉樹(shù)的中序遍歷序列和先序遍歷序列，畫(huà)出該二叉樹(shù)和寫(xiě)出后序遍歷序列；或者已知二叉樹(shù)的中序遍歷序列和后序遍歷序列，畫(huà)出該二叉樹(shù)和寫(xiě)出先序遍歷序列；或者已知二叉樹(shù)的中序遍歷序列和層序遍歷序列，畫(huà)出該二叉樹(shù)和寫(xiě)出先序遍歷序列；

4、樹(shù)和森林

樹(shù)的存儲(chǔ)表示

森林的存儲(chǔ)表示

如：一個(gè)森林有 m 棵樹(shù)，頂點(diǎn)總數(shù)為 n，則森林中含有的總邊數(shù)是

樹(shù)和森林的遍歷

樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換

5、哈夫曼樹(shù)與哈夫曼編碼

哈夫曼樹(shù)的基本概念

哈夫曼樹(shù)構(gòu)造算法

哈夫曼樹(shù)編碼

如：已知一串字母的權(quán)值，畫(huà)出該哈夫曼樹(shù)和寫(xiě)出各字母的哈夫曼編碼；

第 6 章 圖

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

2、圖的存儲(chǔ)表示

鄰接矩陣

如：已知圖的鄰接矩陣 A，求各頂點(diǎn)的度

鄰接表

如：已知有向圖的鄰接表，畫(huà)出該有向圖和該有向圖的逆鄰接表。

3、圖的遍歷

深度優(yōu)先搜索

廣度優(yōu)先搜索

4、圖的最小生成樹(shù)

Prim 算法

Kruskal 算法

如：已知無(wú)向帶權(quán)圖 G，畫(huà)出圖 G 的鄰接矩陣和圖 G 的一棵最小生成樹(shù)。

5、有向無(wú)環(huán)圖的應(yīng)用

拓?fù)渑判?/p>

如：己知有向圖 G，求 G 的拓?fù)湫蛄?/p>

關(guān)鍵路徑

6、最短路徑問(wèn)題

單源點(diǎn)最短路徑

所有頂點(diǎn)之間的最短路徑

第 7 章 查找

1、查找的基本概念

2、靜態(tài)表的查找

順序查找

有序表的查找

如：對(duì)表長(zhǎng)為 n 的順序表進(jìn)行分塊查找，假設(shè)每一塊的長(zhǎng)度均為 m，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長(zhǎng)度為？

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

二叉排序樹(shù)

如：在一棵深度為 h 的具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中，查找任一結(jié)點(diǎn)的最多比較次數(shù)是。

4、散列表

4.1 散列表的概念

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

4.3 處理沖突的方法

如：設(shè)散列表長(zhǎng) m=8，散列函數(shù) H(key)=key％7。表中已保存 4 個(gè)關(guān)鍵字：addr(17)=3，addr(32)=4，addr(54)=5，addr(20)=6，其余地址均為開(kāi)放地址。存儲(chǔ)關(guān)鍵字 47 時(shí)存在沖突，采用線(xiàn)性探測(cè)法來(lái)處理。則查找關(guān)鍵字 42 時(shí)的探查次數(shù)是？

第 8 章 排序

1、排序概述

排序算法的時(shí)間復(fù)雜度和穩(wěn)定性；如：以下哪個(gè)排序算法的最好時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是 O（nlogn）且是穩(wěn)定的?；蛞韵履膫€(gè)排序算法是不穩(wěn)定的或以下哪個(gè)排序算法是穩(wěn)定的；

2、插入排序

直接插入排序

Shell 排序

3、交換排序

冒泡排序

快速排序

4、選擇排序

普通選擇排序

堆排序

5、歸并排序

如：

1）排序算法的應(yīng)用；求應(yīng)用 XX 排序，對(duì)關(guān)鍵字序列（43，02，80，

48，26，57，15，73，21，24，66）進(jìn)行一趟、二趟或三趟排序時(shí)，則得到的各趟結(jié)果為：

第一趟：

第二趟：

第三趟：

2）能應(yīng)用某種排序算法編寫(xiě)程序，將某關(guān)鍵字序列進(jìn)行升序或者降

序排列；

四、考試方式與試題類(lèi)型

1、考試方式：閉卷、筆試，考試時(shí)間為 120 分鐘，試卷滿(mǎn)分為 100分。

2、試題類(lèi)型

1）選擇題(每題 1 分，共 20 分)

單項(xiàng)選擇題，共 20 題，每題 1 分，共 20 分

2）填空題(每題 2 分，共 20 分)

共 10 題，每題 2 分，共 20 分

3）簡(jiǎn)答題(每題 5 分，共 20 分)

共 4 題，每題 5 分，共 20 分

4）程序填空題(每題 10 分，共 20 分)

共 2 題，每題 10 分，共 20 分

5）算法設(shè)計(jì)題(每題 20 分，共 20 分)

共 1 題，每題 20 分，共 20 分

總分共 100 分，考試時(shí)間 120 分鐘；

以上就是“2020年廣東技術(shù)師范大學(xué)天河學(xué)院專(zhuān)插本專(zhuān)業(yè)課《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱”全部?jī)?nèi)容。考生在備考的過(guò)程中，如遇到問(wèn)題或有疑難的話(huà)，請(qǐng)?jiān)L問(wèn)易學(xué)仕在線(xiàn)，會(huì)有專(zhuān)業(yè)老師為你解答! 小編在此預(yù)祝大家在2020年廣東專(zhuān)插本考試中都能取得優(yōu)異成績(jī)。

推薦閱讀：

2020年廣東技術(shù)師范大學(xué)天河學(xué)院專(zhuān)插本招生計(jì)劃