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

一、考試性質(zhì)

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

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

一、考試基本要求

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

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

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

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

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

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

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

第1章緒論

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

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

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

3、算法的概念和特性

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

二、考核要求

1、識(shí)記

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

2、領(lǐng)會(huì)

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

(2)算法的定義和特性

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

3、簡(jiǎn)單應(yīng)用

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

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

4、綜合應(yīng)用

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

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

第2章線性表

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

1、線性表的類型定義

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

3、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

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

二、考核要求

1、識(shí)記

(1)線性表的定義

(2)線性表的特點(diǎn)

2、領(lǐng)會(huì)

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

3、簡(jiǎn)單應(yīng)用

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

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

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

(4)一元多項(xiàng)式的表示和基本運(yùn)算

4、綜合應(yīng)用

(1)一般線性表的合并

(2)有序表的合并

第3章棧和隊(duì)列

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

1、棧的類型定義

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

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

4、隊(duì)列的類型

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

二、考核要求

1、識(shí)記

(1)棧的類型定義

(2)隊(duì)列的類型定義

2、領(lǐng)會(huì)

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

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

3、簡(jiǎn)單應(yīng)用

(1)表達(dá)式求值

(2)打印楊暉三角形

(3)迷宮求解問(wèn)題

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

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

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

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

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

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

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

二、考核要求

1、識(shí)記

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

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

2、領(lǐng)會(huì)

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

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

3、綜合應(yīng)用

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

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

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

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

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

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

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

5、樹(shù)和森林的定義，樹(shù)的存儲(chǔ)

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

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

8、線索化二叉樹(shù)

二、考核要求

1、識(shí)記

(1)二叉樹(shù)的定義

(2)樹(shù)和森林的定義

2、領(lǐng)會(huì)

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

(2)特殊的二叉樹(shù)

3、簡(jiǎn)單應(yīng)用

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

(2)線索化二叉樹(shù)

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

4、綜合應(yīng)用

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

(2)二叉樹(shù)的遍歷方法

(3)哈夫曼編碼

第6章圖

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

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

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

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

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

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

6、求最短路徑問(wèn)題

二、考核要求

1、識(shí)記

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

2、領(lǐng)會(huì)

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

(2)圖的鄰接表表示法

3、簡(jiǎn)單應(yīng)用

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

3、綜合應(yīng)用

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

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

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

第7章查找

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

1、查找的基本概念

2、基于線性表的查找

3、基于樹(shù)表的查找

4、散列表

二、考核要求

1、識(shí)記

(1)查找的基本概念

(2)散列表的基本概念

2、簡(jiǎn)單應(yīng)用

(1)順序查找

(2)折半查找

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

3、綜合應(yīng)用

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

(2)處理沖突的方法

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

第8章排序

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

1、排序的基本概念

2、插入排序

3、交換排序

4、選擇排序

5、歸并排序

6、基數(shù)排序

7、排序算法分析

二、考核要求

1、識(shí)記

(1)排序的基本概念

2、簡(jiǎn)單應(yīng)用

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

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

(3)簡(jiǎn)單選擇排序、堆排序

(4)排序算法分析

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

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

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

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

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

四.參考書(shū)目

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

五.題型示例

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

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

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

3.鏈?zhǔn)酱鎯?chǔ)的線性表可以實(shí)現(xiàn)順序存取。()

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

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

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

B.數(shù)據(jù)項(xiàng)

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

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

2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址是()

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

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

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

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

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

A.元素個(gè)數(shù)

B.元素類型

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

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

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

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

(1)畫(huà)出這棵二叉樹(shù);

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

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

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

(2)計(jì)算其查找成功的平均查找長(zhǎng)度。