六、查找（25%）

1．平均搜索長(zhǎng)度（ASL）的定義

2．順序表的查找算法、程序?qū)崿F(xiàn)和ASL分析

3．二分查找法的算法描述、程序?qū)崿F(xiàn)和ASL分析

4．索引順序表的查找（分塊查找）方法和和ASL分析

5．二叉排序樹(shù)的定義，插入、刪除操作

6．平衡二叉樹(shù)的定義，建立過(guò)程（掌握4種旋轉(zhuǎn)方法），計(jì)算等概率下查找成功的ASL和查找不成功的ASL

7．B-樹(shù)的定義

8．散列表的概念，幾種常用散列函數(shù)的構(gòu)造方法

9．散列表處理沖突的方法（線(xiàn)性探查法、二次探查法、再散列法、鏈地址法），計(jì)算等概率下查找成功的ASL和查找不成功的ASL

10．散列表負(fù)載因子（裝填因子）α的定義

七、排序（10%）（以下每種排序算法要求掌握排序過(guò)程和程序?qū)崿F(xiàn)）

1．直接插入排序、希爾排序

2．冒泡排序、快速排序

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

4．歸并排序

5．基數(shù)排序（箱排序）

6．以上各種排序算法的時(shí)間復(fù)雜度分析，各自的特征及其比較

C++程序設(shè)計(jì)部分

一、C++基礎(chǔ)語(yǔ)法（15%）

1．C++的字符集與詞法規(guī)則

2．常見(jiàn)的數(shù)據(jù)類(lèi)型

3．變量與常量

4．運(yùn)算符的優(yōu)先級(jí)和結(jié)合性

5．表達(dá)式的類(lèi)型與計(jì)算順序

6．語(yǔ)句：包括操作運(yùn)算語(yǔ)句和流程控制語(yǔ)句

7．C++中的編譯預(yù)處理

二、函數(shù)、指針、結(jié)構(gòu)與聯(lián)合（15%）

1．函數(shù)定義/說(shuō)明的格式

2．函數(shù)的參數(shù)和返回值

3．函數(shù)的調(diào)用機(jī)制

4．函數(shù)的參數(shù)傳遞方式

5．重載函數(shù)以及函數(shù)重載的原則

6．標(biāo)識(shí)符的作用域與變量的存儲(chǔ)類(lèi)別

7．指針、引用與數(shù)組的概念和應(yīng)用

三、類(lèi)的封裝性（20%）

1．類(lèi)的定義

2．構(gòu)造函數(shù)與析構(gòu)函數(shù)

3．隱含的this指針

4．類(lèi)的靜態(tài)成員

5．類(lèi)的友元

6．指向類(lèi)成員的指針

7．復(fù)雜對(duì)象與成分對(duì)象

8．類(lèi)的常量成員

四、類(lèi)的繼承性（15%）

1．基類(lèi)與派生類(lèi)

單繼承與多繼承

繼承方式：public protected private

2．訪(fǎng)問(wèn)特征

派生類(lèi)成員函數(shù)對(duì)基類(lèi)成員的訪(fǎng)問(wèn)

派生類(lèi)對(duì)象對(duì)基類(lèi)成員的訪(fǎng)問(wèn)

派生類(lèi)的派生類(lèi)對(duì)基類(lèi)成員的訪(fǎng)問(wèn)

3．虛擬繼承（共享繼承）

多繼承時(shí)的二義性

虛基類(lèi)：在派生類(lèi)對(duì)象中只有一份拷貝

4．構(gòu)造函數(shù)和析構(gòu)函數(shù)的調(diào)用順序

Con：虛基類(lèi)－非虛基類(lèi)－成員對(duì)象類(lèi)－派生類(lèi)

Des：以構(gòu)造函數(shù)相反的順序

五、多態(tài)性（15%）

1．多態(tài)性的概念

2．多態(tài)性的分類(lèi)

編譯時(shí)的多態(tài)性：采用靜態(tài)聯(lián)編

運(yùn)行時(shí)的多態(tài)性：采用動(dòng)態(tài)聯(lián)編

3．靜態(tài)聯(lián)編：概念與常見(jiàn)形式

4．運(yùn)算符重載：“四不變”原則，另外只能重載已有的運(yùn)算符，而不能創(chuàng)造新的運(yùn)算符；即將c++已有的運(yùn)算符擴(kuò)展到用戶(hù)自定義類(lèi)的類(lèi)型上。

①兩種形式：成員函數(shù)與友元函數(shù)形式

②++--的重載，分前綴和后綴兩種形式

5．動(dòng)態(tài)聯(lián)編

虛函數(shù)的概念與應(yīng)用

六、模板與I/O流類(lèi)（20%）：

1．模板引入的必要性

函數(shù)模板

類(lèi)模板

2．C++I/O流類(lèi)庫(kù)

標(biāo)準(zhǔn)I/O

文件I/O

字符串I/O

參考書(shū)目：

《數(shù)據(jù)結(jié)構(gòu)》 清華大學(xué)出版社2009年 戴敏

《C++面向?qū)ο蟪绦蛟O(shè)計(jì)教程》（第3版） 機(jī)械工業(yè)出版社2008 陳維興