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

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

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

一、考試要求

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

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

二、教材及主要參考書目

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

三、考試內(nèi)容

第 1 章 緒論

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

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

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

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

2）存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和 鏈式存儲結(jié)構(gòu)

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

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

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

3、算法：（算法的概念、特性；算法優(yōu)劣的評價標準；算法分析的目的；熟記）；算法的時間復雜度的分析(能分析出一段程序的時間復雜度；掌握分析的方法)

第 2 章 線性表

1、順序表：存儲和操作；

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

2、線性表:

1）單鏈表：

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

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

第 3 章 棧和隊列

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

2、隊列：

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

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

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

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

1、串類型的定義

字符串的實現(xiàn)

字符串模式匹配算法

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

2、數(shù)組:

數(shù)組的基本概念

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

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

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

矩陣

矩陣的定義和操作

特殊矩陣

稀疏矩陣

求特殊矩陣的壓縮存儲：

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

3、廣義表

基本概念

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

尾函數(shù)的應用。

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

廣義表的深度=?

廣義表的長度=?

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

第 5 章 樹和二叉樹

1、樹的基本概念

樹的定義

基本術語

2、二叉樹

二叉樹的定義

二叉樹的性質(zhì)

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

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

3、二叉樹的遍歷

遍歷的定義

遍歷算法

如：已知二叉樹的中序遍歷序列和先序遍歷序列，畫出該二叉樹和寫出后序遍歷序列；或者已知二叉樹的中序遍歷序列和后序遍歷序列，畫出該二叉樹和寫出先序遍歷序列；或者已知二叉樹的中序遍歷序列和層序遍歷序列，畫出該二叉樹和寫出先序遍歷序列；

4、樹和森林

樹的存儲表示

森林的存儲表示

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

樹和森林的遍歷

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

5、哈夫曼樹與哈夫曼編碼

哈夫曼樹的基本概念

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

哈夫曼樹編碼

如：已知一串字母的權值，畫出該哈夫曼樹和寫出各字母的哈夫曼編碼；

第 6 章 圖

1、圖的定義和術語

2、圖的存儲表示

鄰接矩陣

如：已知圖的鄰接矩陣 A，求各頂點的度

鄰接表

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

3、圖的遍歷

深度優(yōu)先搜索

廣度優(yōu)先搜索

4、圖的最小生成樹

Prim 算法

Kruskal 算法

如：已知無向帶權圖 G，畫出圖 G 的鄰接矩陣和圖 G 的一棵最小生成樹。

5、有向無環(huán)圖的應用

拓撲排序

如：己知有向圖 G，求 G 的拓撲序列

關鍵路徑

6、最短路徑問題

單源點最短路徑

所有頂點之間的最短路徑

第 7 章 查找

1、查找的基本概念

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

順序查找

有序表的查找

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

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

二叉排序樹

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

4、散列表

4.1 散列表的概念

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

4.3 處理沖突的方法

如：設散列表長 m=8，散列函數(shù) H(key)=key％7。表中已保存 4 個關鍵字：addr(17)=3，addr(32)=4，addr(54)=5，addr(20)=6，其余地址均為開放地址。存儲關鍵字 47 時存在沖突，采用線性探測法來處理。則查找關鍵字 42 時的探查次數(shù)是？

第 8 章 排序

1、排序概述

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

2、插入排序

直接插入排序

Shell 排序

3、交換排序

冒泡排序

快速排序

4、選擇排序

普通選擇排序

堆排序

5、歸并排序

如：

1）排序算法的應用；求應用 XX 排序，對關鍵字序列（43，02，80，

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

第一趟：

第二趟：

第三趟：

2）能應用某種排序算法編寫程序，將某關鍵字序列進行升序或者降

序排列；

四、考試方式與試題類型

1、考試方式：閉卷、筆試，考試時間為 120 分鐘，試卷滿分為 100分。

2、試題類型

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

單項選擇題，共 20 題，每題 1 分，共 20 分

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

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

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

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

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

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

5）算法設計題(每題 20 分，共 20 分)

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

總分共 100 分，考試時間 120 分鐘；

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

推薦閱讀：

2020年廣東技術師范大學天河學院專插本招生計劃