發(fā)布時(shí)間:2019/12/04 17:21:47 來(lái)源:易學(xué)仕專(zhuān)升本網(wǎng) 閱讀量:3801
摘要: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)與算法》的考試大綱,詳情如下:
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ī)。
推薦閱讀:
操作成功