遼寧石油化工大學(xué)研究生院—計算機(jī)與通信工程學(xué)院考試大綱

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

　　一、 考試要求

　　1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念；把握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)；

　　2、把握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析；

　　3、能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。

　　二、 考試內(nèi)容

　　1、線性表

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

　?。?）線性表的實現(xiàn)：①順序存儲結(jié)構(gòu)；②鏈?zhǔn)酱鎯Y(jié)構(gòu)；③線性表的應(yīng)用。

　　2、棧、隊列和數(shù)組

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

　?。?）棧和隊列的順序存儲結(jié)構(gòu)。

　?。?）棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

　?。?）棧和隊列的應(yīng)用。

　?。?）非凡矩陣的壓縮存儲。

　　3、樹與二叉樹

　?。?）樹的概念。

　?。?）二叉樹：①二叉樹的定義及其主要特征；②二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)；③二叉樹的遍歷；④線索二叉樹的基本概念和構(gòu)造；⑤二叉排序樹；⑥平衡二叉樹。

　?。?）樹、森林：①樹的存儲結(jié)構(gòu)；②森林與二叉樹的轉(zhuǎn)換；③樹和森林的遍歷。

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

　　4、圖

　?。?）圖的概念。

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

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

　?。?）圖的基本應(yīng)用及其復(fù)雜度分析：①最小（代價）生成樹；②最短路徑；③拓?fù)渑判?；③關(guān)鍵路徑。

　　5、查找

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

　?。?）順序查找法。

　?。?）折半查找法。

　?。?）B-樹。

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

　?。?）查找算法的分析及應(yīng)用。

　　5、內(nèi)部排序

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

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

　?。?）氣泡排序。

　?。?）簡單選擇排序。

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

　?。?）快速排序。

　?。?）堆排序。

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

　?。?）基數(shù)排序。

　?。?0）各種內(nèi)部排序算法的比較。

　?。?1）內(nèi)部排序算法的應(yīng)用。

　　離散數(shù)學(xué)考試大綱

　　一、 考試要求：

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

　　2、掌握集合、關(guān)系、函數(shù)的基本概念，集合與關(guān)系的各種運算方法；

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

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

　　二、 考試內(nèi)容：

　　1、數(shù)理邏輯

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

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

　　2、集合論

　?。?）集合與關(guān)系：①集合的概念和表示法；②集合的運算；③包含排斥原理；?、苄蚺寂c笛卡爾積；⑤關(guān)系及其表示；⑥關(guān)系的性質(zhì)；⑦復(fù)合關(guān)系和逆關(guān)系；⑧關(guān)系的閉包運算；⑨集合的劃分和覆蓋；10等價關(guān)系與等價類；11相容關(guān)系；12序關(guān)系。

　?。?）函數(shù)：①函數(shù)的概念；②逆函數(shù)和復(fù)合函數(shù)；③特征函數(shù)與模糊子集；④基數(shù)的概念；⑤可數(shù)集與不可數(shù)集；⑥基數(shù)的比較。

　　3、代數(shù)系統(tǒng)

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

　?。?）格和布爾代數(shù)：①格的概念；②分配格；③有補格；④布爾代數(shù)；⑤布爾表達(dá)式。

　　4、圖論

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

　　5、計算機(jī)科學(xué)中的應(yīng)用

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

　　數(shù)據(jù)庫原理考試大綱

　　一、 考試要求：

　　1、理解數(shù)據(jù)庫的基本概念；把握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。

　　2、把握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析。

　　3、能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。

　　二、 考試內(nèi)容：

　　1、數(shù)據(jù)庫系統(tǒng)基礎(chǔ)

　?。?）數(shù) 據(jù) 模 型

　?。?）數(shù)據(jù)庫系統(tǒng)結(jié)構(gòu)

　?。?）數(shù)據(jù)庫系統(tǒng)的組成

　　2、關(guān)系理論

　?。?）關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義

　?。?）關(guān)系操作

　?。?）關(guān)系的完整性

　?。?）關(guān)系代數(shù)

　?。?）關(guān)系演算

　?。?）關(guān)系的規(guī)范化

　?。?）模式的分解

　　3、關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL

　?。?）數(shù)據(jù)定義

　?。?）數(shù)據(jù)查詢

　?。?）數(shù)據(jù)更新

　?。?）視圖

　　4、數(shù)據(jù)庫安全性

　?。?）數(shù)據(jù)庫安全性控制

　?。?）視圖機(jī)制

　?。?）審計

　?。?）數(shù)據(jù)加密

　　5、數(shù)據(jù)庫完整性

　?。?）實體完整性

　?。?）參照完整性

　?。?）用戶定義的完整性

　　（4）完整性約束命名子句

　?。?）觸發(fā)器

　　計算機(jī)基礎(chǔ)及程序設(shè)計考試大綱

　　一、 考試要求：

　　1、掌握計算機(jī)系統(tǒng)的組成，掌握計算機(jī)中數(shù)據(jù)的表示及運算方法；

　　2、掌握操作系統(tǒng)的基本概念；

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

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

　　5、掌握C語言的語法結(jié)構(gòu)，并能使用C語言編寫簡單的程序。

　　二、 考試內(nèi)容：

　　1、計算機(jī)基礎(chǔ)

　?。?）計算機(jī)系統(tǒng)的組成

　?。?）計算機(jī)中數(shù)據(jù)的表示方法

　?。?）二進(jìn)制數(shù)的運算方法

　?。?）數(shù)制之間的轉(zhuǎn)換

　　2、操作系統(tǒng)

　?。?）操作系統(tǒng)的作用

　?。?）進(jìn)程及進(jìn)程調(diào)度

　　3、計算機(jī)信息安全

　?。?）計算機(jī)病毒及其原理

　?。?）計算機(jī)安全常識

　　4、Windows及Office

　?。?）Windows的基本操作

　?。?）Office的基本操作

　　5、C語言程序設(shè)計

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

　?。?）C語言的控制結(jié)構(gòu)

　?。?）C語言中的數(shù)組、結(jié)構(gòu)、指針的定義及使用

　?。?）簡單程序設(shè)計