2020廣州科技職業(yè)技術(shù)大學(xué)專(zhuān)插本《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

2020廣州科技職業(yè)技術(shù)大學(xué)專(zhuān)插本《數(shù)據(jù)結(jié)構(gòu)與算法》考試大綱

I 考試的性質(zhì)

普通高等學(xué)校本科插班生招生考試是由專(zhuān)科畢業(yè)生參加的選拔性考試。《數(shù)據(jù)結(jié)構(gòu)與算法》課程是專(zhuān)科畢業(yè)生入讀計(jì)算機(jī)應(yīng)用工程專(zhuān)業(yè)的考試課程之一。學(xué)校根據(jù)考生的成績(jī)，按已確定的招生計(jì)劃，德、智、體全面衡量，擇優(yōu)錄取。該考試具有較高的信度、較高的效度、必要的區(qū)分度和適當(dāng)?shù)碾y度。

II 考試內(nèi)容和要求

一、考試基本要求

著重考核應(yīng)試者對(duì)常用基本數(shù)據(jù)結(jié)構(gòu)（順序表、鏈表、棧、隊(duì)列、樹(shù)、二叉樹(shù)、圖等）的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法的掌握程度，以及綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)及算法的編程能力，檢查學(xué)生是否達(dá)到了《高等學(xué)校計(jì)算機(jī)類(lèi)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱》所規(guī)定的基本要求。

1、基本理論知識(shí)

（l）數(shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語(yǔ)，算法的描述方法和算法分析的基本概念。

線(xiàn)性表的基本概念、線(xiàn)性表的基本操作以及這些操作分別在順序存儲(chǔ)和鏈式存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)及復(fù)雜度分析。

棧和隊(duì)列的定義、存儲(chǔ)結(jié)構(gòu)、實(shí)現(xiàn)和典型應(yīng)用。

串的定義及其基本操作。

數(shù)組的定義、運(yùn)算和順序存儲(chǔ)。

樹(shù)的定義、基本術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其各種操作，哈夫曼樹(shù)的概念和應(yīng)用。

圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其各種操作。

各種查找方法的算法、適用范圍及時(shí)間復(fù)雜度的分析。

多種內(nèi)排算法的基本思想和算法的時(shí)間復(fù)雜度分析，不同排序方法的比較。

2、基本技能

能閱讀用類(lèi) C 語(yǔ)言編寫(xiě)的算法。

能分析算法所完成的功能、運(yùn)行結(jié)果和時(shí)間復(fù)雜度。

能根據(jù)要求用類(lèi) C 語(yǔ)言編寫(xiě)算法。

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

第一章 緒論

1、考核知識(shí)點(diǎn)

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、元素、結(jié)點(diǎn)等基本概念。抽象數(shù)據(jù)類(lèi)型的定義、表示和實(shí)現(xiàn)方法。

算法、算法的特性、如何用類(lèi) C 語(yǔ)言來(lái)描述算法。

算法設(shè)計(jì)的基本要求以及計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

2、考核要求

識(shí)記：有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，四種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。

理解：四種基本數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算，算法復(fù)雜度度量的基本概念。

應(yīng)用：用類(lèi) C 語(yǔ)言描述算法。

第二章 線(xiàn)性表

1、考核知識(shí)點(diǎn)

線(xiàn)性表的定義和基本操作。

線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)和基本操作。

線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)，帶有附加表頭結(jié)點(diǎn)和不帶附加表頭結(jié)點(diǎn)的單鏈表、循環(huán)鏈表和雙向鏈表的表示和查找、插入、刪除等基本操作。

2、考核要求

識(shí)記：線(xiàn)性表基本概念、基本運(yùn)算，各種鏈表的表示。

理解：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的比較，各種鏈表的基本操作算法。

第三章 排序

1、考核知識(shí)點(diǎn)

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

簡(jiǎn)單排序方法

插入排序的思想和算法。

冒泡排序的思想和算法。

先進(jìn)排序方法

快速排序的思想和算法。

歸并排序的思想。

堆的定義、堆排序的思想。

基數(shù)排序。

各種排序方法的綜合比較。

2、考核要求

識(shí)記：插入排序、冒泡排序、簡(jiǎn)單選擇排序的思想。

理解：快速排序、堆排序、歸并排序的思想，各種排序方法的穩(wěn)定性、平均比較次數(shù)、平均移動(dòng)次數(shù)。

應(yīng)用：用類(lèi) C 或者 C 語(yǔ)言編寫(xiě)插入排序、冒泡排序、簡(jiǎn)單選擇排序等排序算法。

第四章 棧和隊(duì)列

1、考核知識(shí)點(diǎn)

棧和隊(duì)列的定義、基本運(yùn)算。

棧和隊(duì)列的順序?qū)崿F(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

棧和隊(duì)列的鏈接實(shí)現(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

棧和隊(duì)列的應(yīng)用。

2、考核要求

識(shí)記：棧和隊(duì)列的概念、功能、操作特點(diǎn)、主要運(yùn)算。

理解：棧和隊(duì)列與一般線(xiàn)性表對(duì)比的特殊性，棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)?/span>存儲(chǔ)。

應(yīng)用：棧和隊(duì)列的常見(jiàn)的使用場(chǎng)合。

第五章 串和數(shù)組

1、考核知識(shí)點(diǎn)

串和數(shù)組的定義、基本操作。

串和數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。

二維數(shù)組的按行存儲(chǔ)及按列存儲(chǔ)和計(jì)算數(shù)組元素的地址計(jì)算公式。

2、考核要求

識(shí)記：串和數(shù)組的有關(guān)概念、基本操作。

理解：串和數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及其基本操作。

應(yīng)用：串和數(shù)組基本操作的使用。

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

1、考核知識(shí)點(diǎn)

樹(shù)的定義和基本概念。

二叉樹(shù)(完全二叉樹(shù)、滿(mǎn)二叉樹(shù))的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（順序表示法和二叉鏈表表示法）。

二叉樹(shù)遍歷算法（先序、中序、后序）。

樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的方法（孩子兄弟表示法）。

樹(shù)的路徑長(zhǎng)度、樹(shù)的帶權(quán)路徑長(zhǎng)度、Huffman 樹(shù)的構(gòu)造方法。

2、考核要求

識(shí)記：樹(shù)的基本概念。

理解：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、遍歷算法，孩子兄弟表示法，樹(shù)的路徑長(zhǎng)度， 哈夫曼樹(shù)的構(gòu)造方法。

應(yīng)用：利用哈夫曼樹(shù)解決一些最優(yōu)化問(wèn)題。

第七章 圖和廣義表

1、考核知識(shí)點(diǎn)

廣義表的定義和存儲(chǔ)結(jié)構(gòu)。

圖的定義和基本術(shù)語(yǔ)。

圖及無(wú)向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖。

頂點(diǎn)的度、入度、出度。

頂點(diǎn)間路徑、路徑長(zhǎng)度、環(huán)。

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣。

鄰接表(含逆鄰接表)。

遍歷圖

深度優(yōu)先搜索遍歷圖的算法。

廣度優(yōu)先搜索遍歷圖的思想。

生成樹(shù)、最小生成樹(shù)的概念。

拓?fù)渑判虻母拍睢?/span>

求最短路徑的算法。

2、考核要求

識(shí)記：圖的基本概念和術(shù)語(yǔ)，最小生成樹(shù)、拓?fù)渑判?、最短路徑的概念?/span>

理解：圖的存儲(chǔ)方式和基于該存儲(chǔ)方式的基本操作（求入度、出度、下一條邊等）。

應(yīng)用：求拓?fù)湫蛄械姆椒?，求最短路徑的方?/span>。

第八章 查找表

1、考核知識(shí)點(diǎn)

查找、關(guān)鍵字、平均查找長(zhǎng)度等概念。

靜態(tài)查找表

順序查找

折半查找

分塊查找

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

二叉排序樹(shù)定義、構(gòu)造過(guò)程及其查找算法和效率。

平衡二叉樹(shù)的定義。

2、考核要求

識(shí)記：有關(guān)查找的基本概念，靜態(tài)查找表和動(dòng)態(tài)查找表的概念。

理解：各種靜態(tài)查找算法的比較次數(shù)分析，二叉排序樹(shù)定義的構(gòu)造過(guò)程和查找算法。

應(yīng)用：分析各種查找算法的比較次數(shù)。

第九章 文件（不要求）

第十章 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)示例（不要求）

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

一、考試形式

考試形式為閉卷，筆試。試卷滿(mǎn)分為 100 分；考試時(shí)間為 120 分鐘。

二、試卷內(nèi)容比例

三、試卷題型比例

試題分為客觀題和主觀題。客觀題一般有填空題、選擇題、名詞解釋、程序填空題等類(lèi)型；主觀題一般有簡(jiǎn)答題、算法設(shè)計(jì)題等類(lèi)型。試題對(duì)不同能力層次要求的分?jǐn)?shù)比例：識(shí)記約占 30%，理解約占 40%，應(yīng)用約占 30%。

四、試卷難易度比例

試題按其難度分為容易題、中等題、難題，三種試題分值的比例為 4:5:1。

IV 參考書(shū)目

主要參考書(shū)：

1、《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程（修訂版）》,嚴(yán)蔚敏、陳文博 編著，清華大學(xué)出版社，2011 年。

2、《數(shù)據(jù)結(jié)構(gòu)與算法》, 陳衛(wèi)衛(wèi)、王慶瑞 編著，高等教育出版社，2015 年。

推薦閱讀：

2020年廣州科技職業(yè)技術(shù)大學(xué)專(zhuān)插本考試大綱匯總