天津理工大學2021年碩士研究生入學初試考試大綱

學院（蓋章）：計算機科學與工程學院

考試科目名稱：數(shù)據(jù)結構與C++程序設計（814）

一、考試方式

考試采用筆試形式，考試時間為180分鐘，試卷滿分為150分。

 二、 試卷結構與分數(shù)比重

題型包括填空題（20%）、選擇題（20%）、算法或數(shù)據(jù)結構的設計與分析題（30%）、程序分析題（15%）與編程題（15%）等。

 三、考查的知識范圍

《數(shù)據(jù)結構與C++程序設計》入學考試包括兩部分內(nèi)容：其中數(shù)據(jù)結構考試主要涉及線性結構、樹、圖、查找和排序，占75分；C++程序設計考試主要涉及支持面向對象程序設計的內(nèi)容，同時兼顧C++支持結構化程序設計的特征，占75分。本試卷總共150分，具體考試內(nèi)容主要包括：

 

數(shù)據(jù)結構部分

一、緒論（5%）

1． 數(shù)據(jù)結構相關基本概念

2． 邏輯結構和物理結構

3． 算法效率的度量（O－表示法）

二、線性表、棧和隊列（20%）（以下各點要求掌握算法的程序實現(xiàn)）

1． 順序表的表示和基本操作的實現(xiàn)算法

2． 單鏈表、循環(huán)鏈表、雙向鏈表的表示和和基本操作的實現(xiàn)算法

3． 棧的表示和和基本操作的實現(xiàn)算法

4． 循環(huán)隊列、鏈隊列的表示和和基本操作的實現(xiàn)算法

三、數(shù)組、遞歸（5%）

1． 數(shù)組的存儲方式

2． 特殊矩陣的壓縮存儲

3． 遞歸思想的特點

4． 遞歸算法和遞歸函數(shù)

四、樹和二叉樹（20%）

1． 樹的定義和基本術語

2． 二叉樹的定義、性質(zhì)，二叉鏈表存儲結構

3． 完全二叉樹的性質(zhì)

4． 二叉樹的深度優(yōu)先（先序、中序、后序）和廣度優(yōu)先（層序）遍歷算法和程序實現(xiàn)

5． 樹的存儲結構

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

7． 哈夫曼樹的定義、性質(zhì)、構造方法

五、圖（15%）

1． 圖的定義和術語

2． 圖的鄰接矩陣、鄰接表存儲結構

3． 圖的深度優(yōu)先搜索、廣度優(yōu)先搜索及其算法實現(xiàn)

4． 生成樹的定義，圖的最小生成樹定義與構造方法（不要求算法實現(xiàn)）

5． 拓撲排序

6． 單源最短路徑問題的求解

六、查找（25%）

1． 平均搜索長度（ASL）的定義

2． 順序表的查找算法、程序實現(xiàn)和ASL分析

3． 二分查找法的算法描述、程序實現(xiàn)和ASL分析

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

5． 二叉排序樹的定義、插入、刪除操作

6． 平衡二叉樹的定義、構造（掌握4種旋轉方法），計算等概率下查找成功的ASL和查找不成功的ASL

7． B-樹的定義、插入與刪除操作

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

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

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

七、排序（10%）（以下每種排序算法要求掌握排序過程和程序實現(xiàn)）

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

2． 冒泡排序、快速排序

3． 簡單選擇排序、堆排序

4． 歸并排序

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

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

 

C++程序設計部分

一、C++基礎語法（15%）

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

2． 常見的數(shù)據(jù)類型

3． 變量與常量

4． 運算符的優(yōu)先級和結合性

5． 表達式的類型與計算順序

6． 語句：包括操作運算語句和流程控制語句

7． C++中的編譯預處理

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

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

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

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

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

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

6． 標識符的作用域與變量的存儲類別 

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

三、類的封裝性（20%）

1． 類的定義

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

3． 隱含的this指針

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

5． 類的友元

6． 指向類成員的指針

7． 復雜對象與成分對象

8． 類的常量成員

四、類的繼承性（15%）

1． 基類與派生類

單繼承與多繼承

繼承方式：public protected private

2． 訪問特征

派生類成員函數(shù)對基類成員的訪問

派生類對象對基類成員的訪問

派生類的派生類對基類成員的訪問

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

多繼承時的二義性

虛基類：在派生類對象中只有一份拷貝

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

Con：虛基類－非虛基類－成員對象類－派生類

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

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

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

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

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

運行時的多態(tài)性：采用動態(tài)聯(lián)編

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

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

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

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

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

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

六、模板與I/O流類（20%）：

1． 模板引入的必要性

函數(shù)模板

類模板

2． C++ I/O流類庫

標準I/O 

文件I/O

字符串I/O

四、參考書目

 

《數(shù)據(jù)結構》 機械工業(yè)出版社 2008年     戴敏

《C++面向對象程序設計教程》（第3版）  2009年   陳維興

學院研究生招生領導小組組長簽字：

 

添加天津理工大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[天津理工大學考研分數(shù)線、天津理工大學報錄比、天津理工大學考研群、天津理工大學學姐微信、天津理工大學考研真題、天津理工大學專業(yè)目錄、天津理工大學排名、天津理工大學保研、天津理工大學公眾號、天津理工大學研究生招生）]即可在手機上查看相對應天津理工大學考研信息或資源。