考試科目：數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫技術(shù)

代碼：938

本考試科目包括《數(shù)據(jù)結(jié)構(gòu)》和《數(shù)據(jù)庫應(yīng)用》兩門課程，其中《數(shù)據(jù)結(jié)構(gòu)》內(nèi)容占90分(60%)，《數(shù)據(jù)庫技術(shù)》占60分(40%)。

《數(shù)據(jù)結(jié)構(gòu)》考試大綱

指定教材：《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏主編，清華大學(xué)出版社。

考試重點(diǎn)：1. 線性表的鏈表存儲結(jié)構(gòu)、基本運(yùn)算及其算法應(yīng)用;

2. 二叉樹的各種遍歷算法;二叉排序樹和哈夫曼樹;

3. HASH函數(shù)(表)及其查找算法;

4. 各種排序算法及其算法復(fù)雜度分析。

第一章、緒論

掌握算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析方法。

第二章、線性表

2.1 掌握線性表的順序存儲結(jié)構(gòu)

2.2 熟練掌握線性表的鏈表存儲結(jié)構(gòu)、單鏈表的基本運(yùn)算算法及其應(yīng)用

2.3 了解循環(huán)鏈表和雙向鏈表

第三章、棧和隊(duì)列

3.1 掌握棧的基本概念

3.2 熟練掌握棧的順序與鏈表存儲結(jié)構(gòu)、棧的基本運(yùn)算算法

3.3 掌握隊(duì)列的基本概念

3.4 掌握隊(duì)列的順序與鏈表存儲結(jié)構(gòu)、隊(duì)列的基本運(yùn)算算法

3.5 掌握棧和隊(duì)列的應(yīng)用

第四章、串

了解串的基本概念及其存儲結(jié)構(gòu)

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

了解稀疏矩陣的概念

第六章、樹

6.1 了解樹的基本概念與定義

6.2 掌握二叉樹的基本概念與定義

6.3 熟練掌握二叉樹的前序、中序和后序遍歷算法

6.4 了解線索二叉樹

6.5 掌握二叉樹、樹和森林的轉(zhuǎn)換方法

6.6 熟練掌握二叉排序樹和哈夫曼樹

第七章、圖

7.1 掌握圖的基本概念和術(shù)語

7.2 掌握圖的存儲結(jié)構(gòu)

7.3 了解圖的遍歷方法

7.4 掌握圖的拓?fù)渑判蛩惴?/p>

第八章、查找

8.1 熟練掌握順序表的查找算法及其算法復(fù)雜度分析

8.2 熟練掌握有序表(折半查找)的查找算法及其算法復(fù)雜度分析

8.3 掌握索引表的查找算法及其算法復(fù)雜度分析

8.4 熟練掌握二叉排序樹查找算法及其算法復(fù)雜度分析

8.5 熟練掌握HASH表及其查找算法

第九章、排序

9.1 熟練掌握直接插入排序算法及其算法復(fù)雜度分析

9.2 熟練掌握折半插入排序算法及其算法復(fù)雜度分析

9.3 熟練掌握希爾排序算法及其算法復(fù)雜度分析

9.4 熟練掌握冒泡排序算法及其算法復(fù)雜度分析

9.5 了解快速排序算法及其算法復(fù)雜度分析

9.6 熟練掌握簡單選擇排序算法及其算法復(fù)雜度分析

9.7 了解堆排序算法及其算法復(fù)雜度分析

9.8 了解歸并排序算法及其算法復(fù)雜度分析

9.9 了解基數(shù)排序算法及其算法復(fù)雜度分析

考試題型：

程序設(shè)計(jì)題 90分

《數(shù)據(jù)庫技術(shù)》考試大綱

指定教材：1)《數(shù)據(jù)庫：原理、技術(shù)與應(yīng)用》、祝錫永主編，機(jī)械工業(yè)出版社。

1. 掌握數(shù)據(jù)庫的基本概念;了解常用的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，如SQL SERVER、ORACLE等;

2. 熟練掌握數(shù)據(jù)表的定義，記錄(行)的插入、修改及刪除等操作命令;

3. 熟練掌握SELECT查詢語言，包括帶WHERE、GROUP BY、JOIN子句和子查詢的使用;熟練掌握集合(聚合)函數(shù)的使用方法。

4. 熟練掌握存儲過程的使用

5. 熟練掌握關(guān)系代數(shù)的各種運(yùn)算

6. 掌握E-R圖，并能根據(jù)E-R導(dǎo)出關(guān)系模式

考試題型：

解答題(編寫SQL語句或關(guān)系代數(shù)表達(dá)式、畫E-R圖并導(dǎo)出關(guān)系模式)60分