考試科目數(shù)據(jù)結(jié)構(gòu)與C 程序設(shè)計(jì)

1、天津理工大學(xué)2011年全日制工程碩士研究生入學(xué)考試大綱一、考試科目：數(shù)據(jù)結(jié)構(gòu)與C+程序設(shè)計(jì)（834）二、考試方式：考試采用筆試形式，考試時(shí)間為180分鐘，試卷滿分為150分。三、試卷結(jié)構(gòu)與分?jǐn)?shù)比重：題型包括填空題（20%）、選擇題（20%）、算法或數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與分析題（30%）、 程序分析題（15%）與編程題（15%）等。四、考查的知識(shí)范圍：數(shù)據(jù)結(jié)構(gòu)與C+程序設(shè)計(jì)入學(xué)考試包括兩部分內(nèi)容：其中數(shù)據(jù)結(jié)構(gòu)考試主要涉 及線性結(jié)構(gòu)、樹(shù)、圖、查找表和排序，占75分；C+程序設(shè)計(jì)考試主要涉及支持面向 對(duì)象程序設(shè)計(jì)的內(nèi)容，同時(shí)兼顧C(jī)+支持結(jié)構(gòu)化程序設(shè)計(jì)的特征，占75分。本試卷總 共150分，具體考試內(nèi)容主要

2、包括：數(shù)據(jù)結(jié)構(gòu)部分一、緒論（5%）數(shù)據(jù)結(jié)構(gòu)相關(guān)基本概念邏輯結(jié)構(gòu)和物理結(jié)構(gòu)算法效率的度量（O表示法）二、線性表、棧和隊(duì)列（25%）（以下各點(diǎn)要求掌握算法的程序?qū)崿F(xiàn)）順序表的表示和基本操作的實(shí)現(xiàn)算法線性鏈表、循環(huán)鏈表、雙向鏈表的表示和和基本操作的實(shí)現(xiàn)算法棧的表示和和基本操作的實(shí)現(xiàn)算法循環(huán)隊(duì)列、鏈隊(duì)列的表示和和基本操作的實(shí)現(xiàn)算法三、數(shù)組、遞歸（10%）數(shù)組的存儲(chǔ)方式2 .特殊矩陣的壓縮存儲(chǔ)遞歸思想的特點(diǎn)遞歸算法和遞歸函數(shù)四、樹(shù)和二叉樹(shù)（15%）樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)的定義、性質(zhì)，二叉鏈表存儲(chǔ)結(jié)構(gòu)完全二叉樹(shù)的性質(zhì)二叉樹(shù)的深度優(yōu)先（先序、中序、后序）和廣度優(yōu)先（層序）遍歷算法和程序?qū)?現(xiàn)樹(shù)的孩子一兄弟

3、二叉鏈表存儲(chǔ)結(jié)構(gòu)樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換霍夫曼樹(shù)的定義、性質(zhì)五、圖（10%）圖的定義和術(shù)語(yǔ)圖的鄰接矩陣、鄰接表存儲(chǔ)結(jié)構(gòu)圖的深度優(yōu)先搜索、廣度優(yōu)先搜索及其算法實(shí)現(xiàn)生成樹(shù)的定義拓?fù)渑判蛄?、查找?5%）平均搜索長(zhǎng)度（ASL）的定義順序表的查找算法、程序?qū)崿F(xiàn)和ASL分析二分查找法的算法描述、程序?qū)崿F(xiàn)和ASL分析二叉排序樹(shù)的定義，插入、刪除操作平衡二叉樹(shù)的定義，建立過(guò)程（掌握4種旋轉(zhuǎn)方法），計(jì)算等概率下查找成功的 ASL和查找不成功的ASL索引順序表的查找B樹(shù)的定義，插入、刪除操作散列表的概念，散列函數(shù)的構(gòu)造方法散列表處理沖突的方法（線性探查法、二次探查法、再散列法、鏈地址法），計(jì) 算等概率下查找成功的

4、ASL和查找不成功的ASL散列表負(fù)載因子（裝填因子）a的定義七、排序（10%）（以下每種排序算法要求掌握排序過(guò)程和程序?qū)崿F(xiàn)）直接插入排序、希爾排序冒泡排序、快速排序簡(jiǎn)單選擇排序、堆排序4 .歸并排序以上各種排序算法的時(shí)間復(fù)雜度分析，各自的特征及其比較C+程序設(shè)計(jì)部分一、C+基礎(chǔ)語(yǔ)法（15%）C+的字符集與詞法規(guī)則常見(jiàn)的數(shù)據(jù)類型變量與常量運(yùn)算符的優(yōu)先級(jí)和結(jié)合性表達(dá)式的類型與計(jì)算順序語(yǔ)句：包括操作運(yùn)算語(yǔ)句和流程控制語(yǔ)句C+中的編譯預(yù)處理二、函數(shù)、指針、結(jié)構(gòu)與聯(lián)合（15%）函數(shù)定義/說(shuō)明的格式函數(shù)的參數(shù)和返回值函數(shù)的調(diào)用機(jī)制函數(shù)的參數(shù)傳遞方式重載函數(shù)以及函數(shù)重載的原則標(biāo)識(shí)符的作用域與變量的存儲(chǔ)類別指

5、針、引用與數(shù)組的概念和應(yīng)用三、類的封裝性（20%）類的定義構(gòu)造函數(shù)與析構(gòu)函數(shù)3 .隱含的this指針類的靜態(tài)成員類的友元指向類成員的指針復(fù)雜對(duì)象與成分對(duì)象類的常量成員四、類的繼承性（15%）基類與派生類單繼承與多繼承繼承方式：public protected private訪問(wèn)特征派生類成員函數(shù)對(duì)基類成員的訪問(wèn)派生類對(duì)象對(duì)基類成員的訪問(wèn)派生類的派生類對(duì)基類成員的訪問(wèn)虛擬繼承（共享繼承）多繼承時(shí)的二義性虛基類：在派生類對(duì)象中只有一份拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)的調(diào)用順序Con :虛基類一非虛基類一成員對(duì)象類一派生類Des：以構(gòu)造函數(shù)相反的順序五、多態(tài)性（15%）1 .多態(tài)性的概念多態(tà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)形式運(yùn)算符重載：“四不變”原則，另外只能重載已有的運(yùn)算符，而不能創(chuàng)造新的運(yùn) 算符；即將C+已有的運(yùn)算符擴(kuò)展到用戶自定義類的類型上。兩種形式：成員函數(shù)與友元函數(shù)形式+