考試科目名稱：數據結構與算法

一、考試性質

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

二.考試內容及要求

一、考試基本要求

通過數據結構與算法理論的學習，使學生學會分析研究計算機加工的數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術;配合算法設計和上機實踐的訓練，還應培養(yǎng)學生的數據抽象能力和程序設計的能力，對理論和實踐的操作使學生得到全面的領會和深刻的認識。

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

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

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

領會：要求在識記的基礎上，能把握相關的基本概念、基本原理和基本方法，掌握有關概念、原理、方法的區(qū)別與聯系。

簡單應用：要求在領會的基礎上，運用所掌握的基本概念、基本原理和基本方法中的少量知識點，分析和解決一般的理論問題或實際問題。

綜合應用：要求在簡單應用的基礎上，運用學過的多個知識點，綜合分析和解決比較復雜的實際問題。

第1章緒論

一、考核知識點

1、數據結構的基本概念

2、抽象數據類型的表示和實現

3、算法的概念和特性

4、算法時間復雜度和空間復雜度分析

二、考核要求

1、識記

(1)數據結構的研究內容

2、領會

(1)抽象數據類型的表示和實現

(2)算法的定義和特性

(3)評價算法優(yōu)劣的基本標準

3、簡單應用

(1)簡單數據結構的程序設計

(2)簡單數據結構程序的時間復雜度和空間復雜度分析

4、綜合應用

(1)數據結構的一些基本概念

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

第2章線性表

一、考核知識點

1、線性表的類型定義

2、線性表的順序表示和實現

3、線性表的鏈式表示和實現

4、線性表的應用

二、考核要求

1、識記

(1)線性表的定義

(2)線性表的特點

2、領會

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

3、簡單應用

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

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

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

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

4、綜合應用

(1)一般線性表的合并

(2)有序表的合并

第3章棧和隊列

一、考核知識點

1、棧的類型定義

2、棧的存儲結構表示和實現

3、棧與遞歸的實現

4、隊列的類型

6、隊列的存儲結構標識和實現

二、考核要求

1、識記

(1)棧的類型定義

(2)隊列的類型定義

2、領會

(1)棧的存儲結構表示和實現

(2)隊列的存儲結構標識和實現

3、簡單應用

(1)表達式求值

(2)打印楊暉三角形

(3)迷宮求解問題

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

第4章串、數組和廣義表

一、考核知識點

1、串的表示和實現

2、數組的存儲方法

3、特殊存儲結構

4、廣義表的邏輯結構和存儲結構

二、考核要求

1、識記

(1)串的表示和實現

(2)數組的存儲方法

2、領會

(1)特殊結構的存儲方法

(2)廣義表的邏輯結構和存儲結構

3、綜合應用

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

第5章樹和二叉樹

一、考核知識點

1、二叉樹的定義和術語

2、二叉樹的性質，特殊的二叉樹

3、二叉樹的存儲結構，順序存儲和二叉鏈表

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

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

6、樹、森林與二叉樹的轉換、

7、樹的應用，哈夫曼樹和哈夫曼編碼

8、線索化二叉樹

二、考核要求

1、識記

(1)二叉樹的定義

(2)樹和森林的定義

2、領會

(1)二叉樹的術語

(2)特殊的二叉樹

3、簡單應用

(1)二叉樹的存儲結構

(2)線索化二叉樹

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

4、綜合應用

(1)二叉樹的性質

(2)二叉樹的遍歷方法

(3)哈夫曼編碼

第6章圖

一、考核知識點

1、圖的定義和術語

2、圖的存儲結構(鄰接表和鄰接矩陣)

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

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

5、拓撲排序和關鍵路徑

6、求最短路徑問題

二、考核要求

1、識記

(1)圖的定義和術語

2、領會

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

(2)圖的鄰接表表示法

3、簡單應用

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

3、綜合應用

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

(2)拓撲排序和關鍵路徑

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

第7章查找

一、考核知識點

1、查找的基本概念

2、基于線性表的查找

3、基于樹表的查找

4、散列表

二、考核要求

1、識記

(1)查找的基本概念

(2)散列表的基本概念

2、簡單應用

(1)順序查找

(2)折半查找

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

3、綜合應用

(1)散列函數的構造方法

(2)處理沖突的方法

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

第8章排序

一、考核知識點

1、排序的基本概念

2、插入排序

3、交換排序

4、選擇排序

5、歸并排序

6、基數排序

7、排序算法分析

二、考核要求

1、識記

(1)排序的基本概念

2、簡單應用

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

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

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

(4)排序算法分析

三.考試形式及試卷結構

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

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

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

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

四.參考書目

嚴蔚敏.數據結構與算法(C語言版).人民郵電出版社.2011

五.題型示例

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

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

2.圖的拓撲有序序列不是唯一的。()

3.鏈式存儲的線性表可以實現順序存取。()

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

1.計算機內部數據表示的最小單位是()

A.數據

B.數據項

C.數據元素

D.數據庫

2.線性表采用鏈式存儲時，結點的存儲地址是()

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

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

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

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

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

A.元素個數

B.元素類型

C.邏輯結構

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

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

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

(1)畫出這棵二叉樹;

(2)將這棵二叉樹轉換成對應的樹(或森林)。

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

(1)對該關鍵字序列構造哈希表;

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