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

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

I 考試的性質(zhì)

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

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

一、考試基本要求

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

1、基本理論知識

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

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

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

串的定義及其基本操作。

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

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

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

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

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

2、基本技能

能閱讀用類 C 語言編寫的算法。

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

能根據(jù)要求用類 C 語言編寫算法。

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

第一章 緒論

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

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

算法、算法的特性、如何用類 C 語言來描述算法。

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

2、考核要求

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

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

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

第二章 線性表

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

線性表的定義和基本操作。

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

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

2、考核要求

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

理解：順序存儲和鏈?zhǔn)酱鎯Φ谋容^，各種鏈表的基本操作算法。

第三章 排序

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

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

簡單排序方法

插入排序的思想和算法。

冒泡排序的思想和算法。

先進(jìn)排序方法

快速排序的思想和算法。

歸并排序的思想。

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

基數(shù)排序。

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

2、考核要求

識記：插入排序、冒泡排序、簡單選擇排序的思想。

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

應(yīng)用：用類 C 或者 C 語言編寫插入排序、冒泡排序、簡單選擇排序等排序算法。

第四章 棧和隊列

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

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

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

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

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

2、考核要求

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

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

應(yīng)用：棧和隊列的常見的使用場合。

第五章 串和數(shù)組

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

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

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

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

2、考核要求

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

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

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

第六章 二叉樹和樹

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

樹的定義和基本概念。

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

二叉樹遍歷算法（先序、中序、后序）。

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

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

2、考核要求

識記：樹的基本概念。

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

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

第七章 圖和廣義表

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

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

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

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

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

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

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

鄰接矩陣。

鄰接表(含逆鄰接表)。

遍歷圖

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

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

生成樹、最小生成樹的概念。

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

求最短路徑的算法。

2、考核要求

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

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

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

第八章 查找表

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

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

靜態(tài)查找表

順序查找

折半查找

分塊查找

動態(tài)查找表

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

平衡二叉樹的定義。

2、考核要求

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

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

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

第九章 文件（不要求）

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

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

一、考試形式

考試形式為閉卷，筆試。試卷滿分為 100 分；考試時間為 120 分鐘。

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

三、試卷題型比例

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

四、試卷難易度比例

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

IV 參考書目

主要參考書：

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é)專插本考試大綱匯總