遼寧石油化工大學研究生院—計算機與通信工程學院考試大綱

　　數據結構考試大綱

　　一、 考試要求

　　1、理解數據結構的基本概念；把握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現；

　　2、把握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析；

　　3、能夠選擇合適的數據結構和方法進行問題求解。

　　二、 考試內容

　　1、線性表

　?。?）線性表的定義和基本操作。

　?。?）線性表的實現：①順序存儲結構；②鏈式存儲結構；③線性表的應用。

　　2、棧、隊列和數組

　?。?）棧和隊列的基本概念。

　?。?）棧和隊列的順序存儲結構。

　?。?）棧和隊列的鏈式存儲結構。

　?。?）棧和隊列的應用。

　　（5）非凡矩陣的壓縮存儲。

　　3、樹與二叉樹

　　（1）樹的概念。

　?。?）二叉樹：①二叉樹的定義及其主要特征；②二叉樹的順序存儲結構和鏈式存儲結構；③二叉樹的遍歷；④線索二叉樹的基本概念和構造；⑤二叉排序樹；⑥平衡二叉樹。

　?。?）樹、森林：①樹的存儲結構；②森林與二叉樹的轉換；③樹和森林的遍歷。

　?。?）樹的應用：①等價類問題；②哈夫曼（Huffman）樹和哈夫曼編碼。

　　4、圖

　?。?）圖的概念。

　?。?）圖的存儲及基本操作：①鄰接矩陣法；②鄰接表法；

　?。?）圖的遍歷：①深度優(yōu)先搜索；②廣度優(yōu)先搜索。

　?。?）圖的基本應用及其復雜度分析：①最?。ù鷥r）生成樹；②最短路徑；③拓撲排序；③關鍵路徑。

　　5、查找

　?。?）查找的基本概念。

　　（2）順序查找法。

　?。?）折半查找法。

　?。?）B-樹。

　　（5）散列（Hash）表及其查找。

　?。?）查找算法的分析及應用。

　　5、內部排序

　?。?）排序的基本概念。

　?。?）插入排序：①直接插入排序；②折半插入排序；

　?。?）氣泡排序。

　　（4）簡單選擇排序。

　?。?）希爾排序（shell sort）。

　　（6）快速排序。

　?。?）堆排序。

　?。?）二路歸并排序（merge sort）。

　　（9）基數排序。

　?。?0）各種內部排序算法的比較。

　?。?1）內部排序算法的應用。

　　離散數學考試大綱

　　一、 考試要求：

　　1、掌握命題邏輯和謂詞邏輯的基本概念及邏輯推理；

　　2、掌握集合、關系、函數的基本概念，集合與關系的各種運算方法；

　　3、掌握圖與樹的基本概念及表示方法；

　　3、掌握形式語言與自動機的基本概念與基本原理。

　　二、 考試內容：

　　1、數理邏輯

　?。?）命題邏輯：①命題及其表示法；②聯結詞；③命題公式與翻譯；④真值表與等價公式；⑤重言式與蘊含式；⑥對偶與范式；⑦推理理論；⑧數理邏輯應用?！?/p>

　?。?）謂詞邏輯：①謂詞的概念與表示；②命題函數與量詞；③謂詞公式與翻譯；④變元的約束；⑤謂詞演算的等價式與蘊含式；⑥前束范式；⑦謂詞演算的推理理論。

　　2、集合論

　?。?）集合與關系：①集合的概念和表示法；②集合的運算；③包含排斥原理；　④序偶與笛卡爾積；⑤關系及其表示；⑥關系的性質；⑦復合關系和逆關系；⑧關系的閉包運算；⑨集合的劃分和覆蓋；10等價關系與等價類；11相容關系；12序關系。

　　（2）函數：①函數的概念；②逆函數和復合函數；③特征函數與模糊子集；④基數的概念；⑤可數集與不可數集；⑥基數的比較。

　　3、代數系統

　?。?）代數結構：①代數系統的引入；②運算及其性質；③半群；④群與子群；⑤阿貝爾群和循環(huán)群；⑥置換群與伯恩賽德定理；⑦陪集與拉格朗日定理；⑧同態(tài)與同構；⑨環(huán)與域。

　　（2）格和布爾代數：①格的概念；②分配格；③有補格；④布爾代數；⑤布爾表達式。

　　4、圖論

　　（1）圖論：①圖的基本概念；②路與回路；③圖的矩陣表示；④歐拉圖與漢密爾頓圖；⑤平面圖；⑥對偶圖與著色；⑦樹與生成樹；⑧根樹及其應用。

　　5、計算機科學中的應用

　　（1）形式語言與自動機：①串和語言；②形式文法；③有限狀態(tài)自動機；④有限狀態(tài)機的簡化；⑤有限狀態(tài)機與正則語言。

　　數據庫原理考試大綱

　　一、 考試要求：

　　1、理解數據庫的基本概念；把握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現。

　　2、把握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。

　　3、能夠選擇合適的數據結構和方法進行問題求解。

　　二、 考試內容：

　　1、數據庫系統基礎

　?。?）數 據 模 型

　?。?）數據庫系統結構

　　（3）數據庫系統的組成

　　2、關系理論

　?。?）關系數據結構及形式化定義

　?。?）關系操作

　　（3）關系的完整性

　?。?）關系代數

　?。?）關系演算

　　（6）關系的規(guī)范化

　?。?）模式的分解

　　3、關系數據庫標準語言SQL

　　（1）數據定義

　?。?）數據查詢

　?。?）數據更新

　　（4）視圖

　　4、數據庫安全性

　?。?）數據庫安全性控制

　　（2）視圖機制

　?。?）審計

　?。?）數據加密

　　5、數據庫完整性

　?。?）實體完整性

　?。?）參照完整性

　　（3）用戶定義的完整性

　?。?）完整性約束命名子句

　?。?）觸發(fā)器

　　計算機基礎及程序設計考試大綱

　　一、 考試要求：

　　1、掌握計算機系統的組成，掌握計算機中數據的表示及運算方法；

　　2、掌握操作系統的基本概念；

　　3、掌握計算機信息安全的基本概念；

　　4、掌握Windows XP、Windows2007、Word、Excel、Powerpoint的基本操作；

　　5、掌握C語言的語法結構，并能使用C語言編寫簡單的程序。

　　二、 考試內容：

　　1、計算機基礎

　　（1）計算機系統的組成

　?。?）計算機中數據的表示方法

　?。?）二進制數的運算方法

　　（4）數制之間的轉換

　　2、操作系統

　?。?）操作系統的作用

　　（2）進程及進程調度

　　3、計算機信息安全

　?。?）計算機病毒及其原理

　?。?）計算機安全常識

　　4、Windows及Office

　?。?）Windows的基本操作

　?。?）Office的基本操作

　　5、C語言程序設計

　?。?）C語言的基本語句

　?。?）C語言的控制結構

　　（3）C語言中的數組、結構、指針的定義及使用

　　（4）簡單程序設計