《計(jì)算機(jī)綜合》考試大綱

1、計(jì)算機(jī)綜合考試大綱大綱綜述計(jì)算機(jī)綜合是報(bào)考北京林業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)研究生的考試科目。計(jì)算機(jī)綜合考試由數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)二個(gè)部分組成。為幫助考生明確考試復(fù)習(xí)范圍和有關(guān)要求，特制定本考試大綱?？荚噧?nèi)容數(shù)據(jù)結(jié)構(gòu)100分 + 數(shù)據(jù)庫(kù)技術(shù)50分（一）數(shù)據(jù)結(jié)構(gòu)部分1. 數(shù)據(jù)結(jié)構(gòu)基本概念(1) 數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等。(2) 算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。2. 線性表(1) 線性表的定義。(2) 線性表的順序存儲(chǔ)結(jié)構(gòu)和主要算法實(shí)現(xiàn)，如查找、插入和刪除算法。(3) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和主要算法實(shí)現(xiàn)，如查找、插入和刪除算法。(4) 循環(huán)鏈表、雙

2、向鏈表的特點(diǎn)。(5) 從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。(6) 線性表的應(yīng)用，如線性表的合并算法。3. 棧和隊(duì)列(1) 棧的定義及特點(diǎn)，棧的順序存儲(chǔ)和鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)棧出棧算法，順序棧棧滿(mǎn)和?？盏臈l件。(2) 棧的應(yīng)用，如表達(dá)式求值算法，借助棧深入理解遞歸算法。(3) 隊(duì)列的定義及特點(diǎn)，隊(duì)列的順序存儲(chǔ)(循環(huán)隊(duì))和鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)隊(duì)出隊(duì)算法，循環(huán)隊(duì)列中隊(duì)滿(mǎn)及隊(duì)空的條件。4. 串和數(shù)組(1) 串的定義。(2) 串的古典模式匹配算法。(3) 數(shù)組地址的計(jì)算方法。(4) 特殊矩陣的壓縮存儲(chǔ)方法。5. 樹(shù)和二叉樹(shù)(1) 二叉樹(shù)的定義和性質(zhì)。(2) 二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)：順序

3、存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。(3) 二叉樹(shù)的創(chuàng)建和三種不同遍歷算法，利用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作，如計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)的高度等算法。(4) 線索二叉樹(shù)的特性及構(gòu)造方法。(5) 樹(shù)和森林的定義、存儲(chǔ)結(jié)構(gòu)與二叉樹(shù)的轉(zhuǎn)換方法。(6) 樹(shù)的應(yīng)用，哈夫曼樹(shù)及哈夫曼編碼的構(gòu)造算法、帶權(quán)路徑長(zhǎng)度的計(jì)算。6. 圖(1) 圖的定義和性質(zhì)。(2) 圖的兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表。(3) 圖的兩種遍歷策略：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。 (4) 圖的基本應(yīng)用，包括拓?fù)渑判蛩惴ā⑶蠼庾疃搪窂降牡辖芩固乩惴?、?gòu)造最小生成樹(shù)的兩種算法（普里姆算法和克魯斯卡爾算法）。7. 查找(1) 線性表的查找

4、：順序查找和折半查找算法。(2) 樹(shù)表的查找：二叉排序樹(shù)的定義，二叉排序樹(shù)的創(chuàng)建、插入、刪除和查找算法。(3) 散列表的查找：兩種處理沖突的方法包括開(kāi)放地址法（線性探測(cè)法、二次探測(cè)法）和鏈地址法。(4) 上述三種不同查找算法的分析，平均查找長(zhǎng)度ASL的計(jì)算方法及時(shí)間復(fù)雜度分析，不同查找算法的適用場(chǎng)合。8. 排序 (1) 排序的基本概念。(2) 插入排序：直接插入排序、折半插入排序和希爾排序。(3) 交換排序：冒泡排序和快速排序。(4) 選擇排序：簡(jiǎn)單選擇排序和堆排序。(5) 歸并排序：2-路歸并排序。(6) 上述各種排序方法的特點(diǎn)和排序過(guò)程，時(shí)間和空間復(fù)雜度的分析，排序方法“穩(wěn)定”或“不穩(wěn)定”

5、的含義。排序算法的實(shí)現(xiàn)及適用場(chǎng)合。（二）數(shù)據(jù)庫(kù)技術(shù)部分1. 數(shù)據(jù)庫(kù)系統(tǒng)概述(1) 數(shù)據(jù)庫(kù)系統(tǒng)概論：數(shù)據(jù)，數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)，數(shù)據(jù)管理技術(shù)的產(chǎn)生和發(fā)展，數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)。(2) 數(shù)據(jù)模型：數(shù)據(jù)模型的組成要素，概念模型，層次模型，網(wǎng)狀模型，關(guān)系模型，對(duì)象模型。(3) 數(shù)據(jù)庫(kù)系統(tǒng)結(jié)構(gòu)：數(shù)據(jù)庫(kù)系統(tǒng)模式的概念，數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式結(jié)構(gòu)，數(shù)據(jù)庫(kù)的二級(jí)映像功能與數(shù)據(jù)獨(dú)立性，數(shù)據(jù)庫(kù)系統(tǒng)的組成。(4) 數(shù)據(jù)庫(kù)技術(shù)的研究領(lǐng)域。2. 關(guān)系數(shù)據(jù)庫(kù)(1) 關(guān)系模型概述。(2) 關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義：關(guān)系，關(guān)系模式，關(guān)系數(shù)據(jù)庫(kù)。(3) 關(guān)系的完整性：實(shí)體完整性，參照完整性，用戶(hù)自定義完整性。(4) 關(guān)

6、系代數(shù)：集合運(yùn)算，關(guān)系運(yùn)算。3. 關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語(yǔ)言SQL(1) SQL概述。(2) SQL數(shù)據(jù)定義。(3) SQL查詢(xún)：?jiǎn)伪聿樵?xún)，連接查詢(xún)，嵌套查詢(xún)，集合查詢(xún)。(4) SQL數(shù)據(jù)更新：插入數(shù)據(jù)，修改數(shù)據(jù)，刪除數(shù)據(jù)。(5) 視圖：SQL創(chuàng)建視圖，查詢(xún)視圖，更新視圖，視圖意義。(6) 數(shù)據(jù)控制：SQL授權(quán)，收回授權(quán)。(7) 嵌入式SQL。4. 關(guān)系數(shù)據(jù)庫(kù)理論(1) 關(guān)系模式的冗余和異常問(wèn)題。(2) 規(guī)范化：函數(shù)依賴(lài)，碼，范式，2NF，3NF，BCNF，多值依賴(lài)，4NF。(3) 模式的分解。5. 數(shù)據(jù)庫(kù)安全保護(hù)(1) 數(shù)據(jù)庫(kù)安全性控制。(2) 數(shù)據(jù)庫(kù)完整性控制。(3) 數(shù)據(jù)庫(kù)并發(fā)控制。(4) 數(shù)據(jù)恢復(fù)。6. 數(shù)據(jù)庫(kù)設(shè)計(jì) (1) 數(shù)據(jù)庫(kù)設(shè)計(jì)的概述。(2) 需求分析。(3) 概念結(jié)構(gòu)設(shè)計(jì)。(4) 邏輯結(jié)構(gòu)設(shè)計(jì)。(5) 數(shù)據(jù)庫(kù)物理設(shè)計(jì)。(6) 數(shù)據(jù)庫(kù)實(shí)施。(7) 數(shù)據(jù)庫(kù)運(yùn)行維護(hù)。7. SQL Server 2000數(shù)據(jù)庫(kù)管理系統(tǒng)(1) Transact-SQL程序設(shè)計(jì)：變量，流程控制命令，其他命令，常用函數(shù)。(2) 存儲(chǔ)過(guò)程和觸發(fā)器。(3) 備份和還原?？荚囈笏惴ㄔO(shè)計(jì)題可以采用C或者C+語(yǔ)言描述。試題結(jié)構(gòu)1、選擇題2、填空題3、簡(jiǎn)答題4、設(shè)計(jì)題考試方式及時(shí)間1、考試方式：閉卷筆試2、考試時(shí)間：180分鐘3、試卷滿(mǎn)分：150分主要參考書(shū)1、嚴(yán)蔚敏，李冬梅，吳偉民編著. 數(shù)據(jù)結(jié)