考試科目名稱：數(shù)據(jù)結(jié)構(gòu)與算法

一、考試性質(zhì)

普通高等學(xué)校本科插班生招生考試是由?？飘厴I(yè)生參加的選拔性考試。高等學(xué)校根據(jù)考生的成績，按已確定的招生計劃，德、智、體全面衡量，擇優(yōu)錄取。該考生所包含的內(nèi)容將大致穩(wěn)定，試題形式多種，具有對學(xué)生把握本課程程度的較強識別、區(qū)分能力。

二.考試內(nèi)容及要求

一、考試基本要求

通過數(shù)據(jù)結(jié)構(gòu)與算法理論的學(xué)習(xí)，使學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時間分析和空間分析技術(shù);配合算法設(shè)計和上機實踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計的能力，對理論和實踐的操作使學(xué)生得到全面的領(lǐng)會和深刻的認(rèn)識。

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

本大綱的考核中，按照“識記”、“領(lǐng)會”、“簡單應(yīng)用”和“綜合應(yīng)用”等四個層次規(guī)定應(yīng)達到的能力層次要求。各能力層次為遞進等級關(guān)系，后者必須建立在前者的基礎(chǔ)上，其含義是：

識記：要求考生知道有關(guān)的名詞、概念、原理、知識的含義，并能正確認(rèn)識或識別。

領(lǐng)會：要求在識記的基礎(chǔ)上，能把握相關(guān)的基本概念、基本原理和基本方法，掌握有關(guān)概念、原理、方法的區(qū)別與聯(lián)系。

簡單應(yīng)用：要求在領(lǐng)會的基礎(chǔ)上，運用所掌握的基本概念、基本原理和基本方法中的少量知識點，分析和解決一般的理論問題或?qū)嶋H問題。

綜合應(yīng)用：要求在簡單應(yīng)用的基礎(chǔ)上，運用學(xué)過的多個知識點，綜合分析和解決比較復(fù)雜的實際問題。

第1章緒論

一、考核知識點

1、數(shù)據(jù)結(jié)構(gòu)的基本概念

2、抽象數(shù)據(jù)類型的表示和實現(xiàn)

3、算法的概念和特性

4、算法時間復(fù)雜度和空間復(fù)雜度分析

二、考核要求

1、識記

(1)數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

2、領(lǐng)會

(1)抽象數(shù)據(jù)類型的表示和實現(xiàn)

(2)算法的定義和特性

(3)評價算法優(yōu)劣的基本標(biāo)準(zhǔn)

3、簡單應(yīng)用

(1)簡單數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計

(2)簡單數(shù)據(jù)結(jié)構(gòu)程序的時間復(fù)雜度和空間復(fù)雜度分析

4、綜合應(yīng)用

(1)數(shù)據(jù)結(jié)構(gòu)的一些基本概念

(2)算法的時間復(fù)雜度分析

第2章線性表

一、考核知識點

1、線性表的類型定義

2、線性表的順序表示和實現(xiàn)

3、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

4、線性表的應(yīng)用

二、考核要求

1、識記

(1)線性表的定義

(2)線性表的特點

2、領(lǐng)會

(1)線性表的抽象數(shù)據(jù)類型定義

3、簡單應(yīng)用

(1)線性表的順序存儲和基本操作實現(xiàn)

(2)單鏈表的存儲和基本實現(xiàn)

(3)雙鏈表的存儲和基本實現(xiàn)

(4)一元多項式的表示和基本運算

4、綜合應(yīng)用

(1)一般線性表的合并

(2)有序表的合并

第3章棧和隊列

一、考核知識點

1、棧的類型定義

2、棧的存儲結(jié)構(gòu)表示和實現(xiàn)

3、棧與遞歸的實現(xiàn)

4、隊列的類型

6、隊列的存儲結(jié)構(gòu)標(biāo)識和實現(xiàn)

二、考核要求

1、識記

(1)棧的類型定義

(2)隊列的類型定義

2、領(lǐng)會

(1)棧的存儲結(jié)構(gòu)表示和實現(xiàn)

(2)隊列的存儲結(jié)構(gòu)標(biāo)識和實現(xiàn)

3、簡單應(yīng)用

(1)表達式求值

(2)打印楊暉三角形

(3)迷宮求解問題

(4)模擬汽車加油站問題

第4章串、數(shù)組和廣義表

一、考核知識點

1、串的表示和實現(xiàn)

2、數(shù)組的存儲方法

3、特殊存儲結(jié)構(gòu)

4、廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

二、考核要求

1、識記

(1)串的表示和實現(xiàn)

(2)數(shù)組的存儲方法

2、領(lǐng)會

(1)特殊結(jié)構(gòu)的存儲方法

(2)廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

3、綜合應(yīng)用

(1)古典的模式匹配算法

第5章樹和二叉樹

一、考核知識點

1、二叉樹的定義和術(shù)語

2、二叉樹的性質(zhì)，特殊的二叉樹

3、二叉樹的存儲結(jié)構(gòu)，順序存儲和二叉鏈表

4、二叉樹的遍歷(前序、中序、后序、層次)

5、樹和森林的定義，樹的存儲

6、樹、森林與二叉樹的轉(zhuǎn)換、

7、樹的應(yīng)用，哈夫曼樹和哈夫曼編碼

8、線索化二叉樹

二、考核要求

1、識記

(1)二叉樹的定義

(2)樹和森林的定義

2、領(lǐng)會

(1)二叉樹的術(shù)語

(2)特殊的二叉樹

3、簡單應(yīng)用

(1)二叉樹的存儲結(jié)構(gòu)

(2)線索化二叉樹

(3)樹、森林和二叉樹的轉(zhuǎn)換

4、綜合應(yīng)用

(1)二叉樹的性質(zhì)

(2)二叉樹的遍歷方法

(3)哈夫曼編碼

第6章圖

一、考核知識點

1、圖的定義和術(shù)語

2、圖的存儲結(jié)構(gòu)(鄰接表和鄰接矩陣)

3、圖的遍歷(深度優(yōu)先和廣度優(yōu)先)

4、構(gòu)造最小生成樹的短發(fā)

5、拓?fù)渑判蚝完P(guān)鍵路徑

6、求最短路徑問題

二、考核要求

1、識記

(1)圖的定義和術(shù)語

2、領(lǐng)會

(1)圖的鄰接矩陣表示法

(2)圖的鄰接表表示法

3、簡單應(yīng)用

(1)圖的遍歷方法：深度優(yōu)先遍歷、廣度優(yōu)先遍歷

3、綜合應(yīng)用

(1)最小生成樹算法：普里姆算法、克魯斯卡爾算法

(2)拓?fù)渑判蚝完P(guān)鍵路徑

(3)最短路徑問題算法：迪杰斯特拉算法、佛洛依德算法

第7章查找

一、考核知識點

1、查找的基本概念

2、基于線性表的查找

3、基于樹表的查找

4、散列表

二、考核要求

1、識記

(1)查找的基本概念

(2)散列表的基本概念

2、簡單應(yīng)用

(1)順序查找

(2)折半查找

(3)二叉排序樹、平衡二叉樹

3、綜合應(yīng)用

(1)散列函數(shù)的構(gòu)造方法

(2)處理沖突的方法

(3)散列表的查找和分析

第8章排序

一、考核知識點

1、排序的基本概念

2、插入排序

3、交換排序

4、選擇排序

5、歸并排序

6、基數(shù)排序

7、排序算法分析

二、考核要求

1、識記

(1)排序的基本概念

2、簡單應(yīng)用

(1)直接插入排序、折半插入排序、希爾排序

(2)快速排序、冒泡排序、2-路歸并排序

(3)簡單選擇排序、堆排序

(4)排序算法分析

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

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

2、試卷內(nèi)容比例：第一～四章占40%，第五、六章占40%，第七、八章占20%。

3、試卷題型比例：判斷題占20%，選擇題占30%，綜合計算分析題占50%。

4、試卷難易比例：易、中、難分別為30%，50%，20%。

四.參考書目

嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)與算法(C語言版).人民郵電出版社.2011

五.題型示例

一、判斷題(每題2分，對的打√，錯的打×，共20分)

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()

2.圖的拓?fù)溆行蛐蛄胁皇俏ㄒ坏摹?)

3.鏈?zhǔn)酱鎯Φ木€性表可以實現(xiàn)順序存取。()

二、選擇題(每題2分，共30分)

1.計算機內(nèi)部數(shù)據(jù)表示的最小單位是()

A.數(shù)據(jù)

B.數(shù)據(jù)項

C.數(shù)據(jù)元素

D.數(shù)據(jù)庫

2.線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址是()

A.必須是不連續(xù)的

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結(jié)點的存儲地址相連續(xù)

3.棧與一般線性表的區(qū)別是()

A.元素個數(shù)

B.元素類型

C.邏輯結(jié)構(gòu)

D.插入、刪除元素的位置

三、綜合計算分析題(共50分)

1.假設(shè)一棵二叉樹的先序序列是：ABDFCEGH，中序序列是：BFDAGEEHC。試分析：

(1)畫出這棵二叉樹;

(2)將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹(或森林)。

2.設(shè)有一組關(guān)鍵字(9，1，23，14，55，20，84，27，30)，采用哈希函數(shù)：H(key)=key%8，表長為10，用開放地址法的二次探測法處理沖突。要求：

(1)對該關(guān)鍵字序列構(gòu)造哈希表;

(2)計算其查找成功的平均查找長度。