廣東理工學院2020年專插本《數(shù)據(jù)結構與算法》考試大綱

I 考試的性質

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

II 考試內容和要求

一、考試基本要求

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

1、基本理論知識

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

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

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

（4）串的定義及其基本操作。

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

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

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

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

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

2、基本技能

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

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

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

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

第一章   緒論

1、考核知識點

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

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

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

2、考核要求

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

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

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

第二章   線性表

1、考核知識點

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

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

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

2、考核要求

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

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

第三章   排序

1、考核知識點

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

（2）簡單排序方法

l 插入排序的思想和算法。

l 冒泡排序的思想和算法。

（3）先進排序方法

l 快速排序的思想和算法。 

l 歸并排序的思想。

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

（4）基數(shù)排序。

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

2、考核要求

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

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

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

第四章   棧和隊列

1、考核知識點

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

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

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

（4）棧和隊列的應用。

2、考核要求

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

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

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

第五章   串和數(shù)組

1、考核知識點

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

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

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

2、考核要求

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

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

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

第六章   二叉樹和樹

1、考核知識點

（1）樹的定義和基本概念。

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

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

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

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

2、考核要求

（1）識記：樹的基本概念。

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

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

第七章   圖和廣義表

1、考核知識點

（1）廣義表的定義和存儲結構。

（2）圖的定義和基本術語。

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

l 頂點的度、入度、出度。

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

（3）圖的存儲結構

l 鄰接矩陣。

l 鄰接表(含逆鄰接表)。

（4）遍歷圖 

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

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

（5）生成樹、最小生成樹的概念。

（6）拓撲排序的概念。

（7）求最短路徑的算法。

2、考核要求

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

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

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

第八章   查找表

1、考核知識點

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

（2）靜態(tài)查找表

l 順序查找  

l 折半查找  

l 分塊查找  

（3）動態(tài)查找表

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

l 平衡二叉樹的定義。

2、考核要求

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

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

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

第九章   文件（不要求）

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

III 考試形式及試卷結構

一、考試形式

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

二、試卷內容比例

第一章     約占8%

第二章     約占20%

第三章     約占15%

第四章     約占10%

第五章     約占8%

第六章     約占15%

第七章     約占14%

第八章     約占10%

三、試卷題型比例

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

四、試卷難易度比例

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

IV 參考書目

主要參考書：

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

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

V 題型示例

一、填空題

1、一棵深度為8（根的層次號為1）的滿二叉樹有______________個葉子結點。

2、串的長度是指__________。

二、選擇題

1、一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是__________

A .e d c b a   B.  d e c b a  C.  d c e a b  D. a b c d e

2、對于棧操作數(shù)據(jù)的原則是___________。

A. 先進先出    B. 后進先出    C. 后進后出     D. 不分順序

三、名詞解釋

1、連通圖

2、完全二叉樹

四、程序填空題

下面的程序段是在一棵二叉排序樹中查找給定的關鍵字，找到返回1，找不到返回0。請把該程序補充完整。

五、簡答題

1、試比較鏈式存儲和順序存儲的優(yōu)缺點。

2、已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試寫出其先序序列。

六、算法設計題

設計一算法，實現(xiàn)將一個遞減的數(shù)組 A[0..n-1]和一個帶頭結點的遞增單鏈表B合并成一個帶頭結點的遞增鏈表C。已知單鏈表的數(shù)據(jù)定義為：

數(shù)組A和要鏈接的單鏈表B通過函數(shù)參數(shù)傳遞，n是數(shù)組的規(guī)模。函數(shù)返回值是生成的鏈表。

推薦閱讀

廣東理工學院2020年專插本《計算機組成原理》考試大綱