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

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

I 考試的性質

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

II 考試內容和要求

一、考試基本要求

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

1、基本理論知識

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

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

棧和隊列的定義、存儲結構、實現(xiàn)和典型應用。

串的定義及其基本操作。

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

樹的定義、基本術語和存儲結構，二叉樹的定義和性質、二叉樹的存儲結構及其各種操作，哈夫曼樹的概念和應用。

圖的定義和術語、圖的存儲結構及其各種操作。

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

多種內排算法的基本思想和算法的時間復雜度分析，不同排序方法的比較。

2、基本技能

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

能分析算法所完成的功能、運行結果和時間復雜度。

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

二、考核知識點及考核要求

第一章 緒論

1、考核知識點

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

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

算法設計的基本要求以及計算語句頻度和估算算法時間復雜度的方法。

2、考核要求

識記：有關數(shù)據(jù)結構的基本概念，四種基本數(shù)據(jù)結構的特點。

理解：四種基本數(shù)據(jù)結構的基本運算，算法復雜度度量的基本概念。

應用：用類 C 語言描述算法。

第二章 線性表

1、考核知識點

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

線性表的順序存儲結構和基本操作。

線性表的鏈式存儲，帶有附加表頭結點和不帶附加表頭結點的單鏈表、循環(huán)鏈表和雙向鏈表的表示和查找、插入、刪除等基本操作。

2、考核要求

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

理解：順序存儲和鏈式存儲的比較，各種鏈表的基本操作算法。

第三章 排序

1、考核知識點

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

簡單排序方法

插入排序的思想和算法。

冒泡排序的思想和算法。

先進排序方法

快速排序的思想和算法。

歸并排序的思想。

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

基數(shù)排序。

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

2、考核要求

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

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

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

第四章 棧和隊列

1、考核知識點

棧和隊列的定義、基本運算。

棧和隊列的順序實現(xiàn)及其運算的實現(xiàn)。

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

棧和隊列的應用。

2、考核要求

識記：棧和隊列的概念、功能、操作特點、主要運算。

理解：棧和隊列與一般線性表對比的特殊性，棧和隊列的順序存儲和鏈式存儲。

應用：棧和隊列的常見的使用場合。

第五章 串和數(shù)組

1、考核知識點

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

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

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

2、考核要求

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

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

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

第六章 二叉樹和樹

1、考核知識點

樹的定義和基本概念。

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

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

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

樹的路徑長度、樹的帶權路徑長度、Huffman 樹的構造方法。

2、考核要求

識記：樹的基本概念。

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

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

第七章 圖和廣義表

1、考核知識點

廣義表的定義和存儲結構。

圖的定義和基本術語。

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

頂點的度、入度、出度。

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

圖的存儲結構

鄰接矩陣。

鄰接表(含逆鄰接表)。

遍歷圖

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

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

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

拓撲排序的概念。

求最短路徑的算法。

2、考核要求

識記：圖的基本概念和術語，最小生成樹、拓撲排序、最短路徑的概念。

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

應用：求拓撲序列的方法，求最短路徑的方法。

第八章 查找表

1、考核知識點

查找、關鍵字、平均查找長度等概念。

靜態(tài)查找表

順序查找

折半查找

分塊查找

動態(tài)查找表

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

平衡二叉樹的定義。

2、考核要求

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

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

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

第九章 文件（不要求）

第十章 數(shù)據(jù)結構程序設計示例（不要求）

III 考試形式及試卷結構

一、考試形式

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

二、試卷內容比例

三、試卷題型比例

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

四、試卷難易度比例

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

IV 參考書目

主要參考書：

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

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

推薦閱讀：

2020年廣州科技職業(yè)技術大學專插本考試大綱匯總