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

I 考試的性質(zhì)

普通高等學(xué)校本科插班生招生考試是由?？飘厴I(yè)生參加的選拔性考試。《數(shù)據(jù)結(jié)構(gòu)與算法》課程是廣東理工學(xué)院招收?？飘厴I(yè)生入讀計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程專業(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ī)類專業(yè)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱》所規(guī)定的基本要求。

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

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

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

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

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

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

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

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

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

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

2、基本技能

（1）能閱讀用類C語(yǔ)言編寫(xiě)的算法。

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

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

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

第一章   緒論

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

（1）數(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ù)類型的定義、表示和實(shí)現(xiàn)方法。

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

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

2、考核要求

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

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

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

第二章   線性表

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

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

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

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

2、考核要求

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

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

第三章   排序

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

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

（2）簡(jiǎn)單排序方法

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

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

（3）先進(jìn)排序方法

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

l 歸并排序的思想。

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

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

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

2、考核要求

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

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

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

第四章   棧和隊(duì)列

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

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

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

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

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

2、考核要求

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

（2）理解：棧和隊(duì)列與一般線性表對(duì)比的特殊性，棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

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

第五章   串和數(shù)組

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

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

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

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

2、考核要求

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

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

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

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

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

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

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

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

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

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

2、考核要求

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

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

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

第七章   圖和廣義表

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

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

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

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

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

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

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

l 鄰接矩陣。

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

（4）遍歷圖 

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

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

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

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

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

2、考核要求

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

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

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

第八章   查找表

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

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

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

l 順序查找  

l 折半查找  

l 分塊查找  

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

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

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

2、考核要求

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

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

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

第九章   文件（不要求）

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

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

一、考試形式

閉卷，筆試，試卷滿分為100分，考試時(shí)間為120分鐘。

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

第一章     約占8%

第二章     約占20%

第三章     約占15%

第四章     約占10%

第五章     約占8%

第六章     約占15%

第七章     約占14%

第八章     約占10%

三、試卷題型比例

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

四、試卷難易度比例

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

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年。

V 題型示例

一、填空題

1、一棵深度為8（根的層次號(hào)為1）的滿二叉樹(shù)有______________個(gè)葉子結(jié)點(diǎn)。

2、串的長(zhǎng)度是指__________。

二、選擇題

1、一個(gè)棧的入棧序列是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、對(duì)于棧操作數(shù)據(jù)的原則是___________。

A. 先進(jìn)先出    B. 后進(jìn)先出    C. 后進(jìn)后出     D. 不分順序

三、名詞解釋

1、連通圖

2、完全二叉樹(shù)

四、程序填空題

下面的程序段是在一棵二叉排序樹(shù)中查找給定的關(guān)鍵字，找到返回1，找不到返回0。請(qǐng)把該程序補(bǔ)充完整。

五、簡(jiǎn)答題

1、試比較鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)的優(yōu)缺點(diǎn)。

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

六、算法設(shè)計(jì)題

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

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

推薦閱讀

廣東理工學(xué)院2020年專插本《計(jì)算機(jī)組成原理》考試大綱