考試科目：數據結構與數據庫技術

代碼：938

本考試科目包括《數據結構》和《數據庫應用》兩門課程，其中《數據結構》內容占90分(60%)，《數據庫技術》占60分(40%)。

《數據結構》考試大綱

指定教材：《數據結構》(C語言版)，嚴蔚敏主編，清華大學出版社。

考試重點：1. 線性表的鏈表存儲結構、基本運算及其算法應用;

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

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

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

第一章、緒論

掌握算法的時間復雜度和空間復雜度分析方法。

第二章、線性表

2.1 掌握線性表的順序存儲結構

2.2 熟練掌握線性表的鏈表存儲結構、單鏈表的基本運算算法及其應用

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

第三章、棧和隊列

3.1 掌握棧的基本概念

3.2 熟練掌握棧的順序與鏈表存儲結構、棧的基本運算算法

3.3 掌握隊列的基本概念

3.4 掌握隊列的順序與鏈表存儲結構、隊列的基本運算算法

3.5 掌握棧和隊列的應用

第四章、串

了解串的基本概念及其存儲結構

第五章、數組和廣義表

了解稀疏矩陣的概念

第六章、樹

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

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

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

6.4 了解線索二叉樹

6.5 掌握二叉樹、樹和森林的轉換方法

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

第七章、圖

7.1 掌握圖的基本概念和術語

7.2 掌握圖的存儲結構

7.3 了解圖的遍歷方法

7.4 掌握圖的拓撲排序算法

第八章、查找

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

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

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

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

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

第九章、排序

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

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

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

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

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

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

9.7 了解堆排序算法及其算法復雜度分析

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

9.9 了解基數排序算法及其算法復雜度分析

考試題型：

程序設計題 90分

《數據庫技術》考試大綱

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

1. 掌握數據庫的基本概念;了解常用的關系型數據庫管理系統，如SQL SERVER、ORACLE等;

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

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

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

5. 熟練掌握關系代數的各種運算

6. 掌握E-R圖，并能根據E-R導出關系模式

考試題型：

解答題(編寫SQL語句或關系代數表達式、畫E-R圖并導出關系模式)60分