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

1、數(shù)據(jù)結(jié)構(gòu)考試大綱一、 考試要求1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念；把握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)；2、把握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析；3、能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。二、 考試內(nèi)容1、線(xiàn)性表 （1）線(xiàn)性表的定義和基本操作。（2）線(xiàn)性表的實(shí)現(xiàn)：順序存儲(chǔ)結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；線(xiàn)性表的應(yīng)用。2、棧、隊(duì)列和數(shù)組（1）棧和隊(duì)列的基本概念。（2）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。（3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（4）棧和隊(duì)列的應(yīng)用。（5）非凡矩陣的壓縮存儲(chǔ)。3、樹(shù)與二叉樹(shù)（1）樹(shù)的概念。（2）二叉樹(shù)：二叉樹(shù)的定義及其主要特征；二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)?/p>

2、存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的遍歷；線(xiàn)索二叉樹(shù)的基本概念和構(gòu)造；二叉排序樹(shù)；平衡二叉樹(shù)。（3）樹(shù)、森林：樹(shù)的存儲(chǔ)結(jié)構(gòu)；森林與二叉樹(shù)的轉(zhuǎn)換；樹(shù)和森林的遍歷。（4）樹(shù)的應(yīng)用：等價(jià)類(lèi)問(wèn)題；哈夫曼（Huffman）樹(shù)和哈夫曼編碼。4、圖 （1）圖的概念。（2）圖的存儲(chǔ)及基本操作：鄰接矩陣法；鄰接表法；（3）圖的遍歷：深度優(yōu)先搜索；廣度優(yōu)先搜索。（4）圖的基本應(yīng)用及其復(fù)雜度分析：最小（代價(jià)）生成樹(shù)；最短路徑；拓?fù)渑判?；關(guān)鍵路徑。5、查找 （1）查找的基本概念。（2）順序查找法。（3）折半查找法。（4）B-樹(shù)。（5）散列（Hash）表及其查找。（6）查找算法的分析及應(yīng)用。5、內(nèi)部排序 （1）排序的基本概念。（2）插入

3、排序：直接插入排序；折半插入排序；（3）氣泡排序。（4）簡(jiǎn)單選擇排序。（5）希爾排序（shell sort）。 （6）快速排序。（7）堆排序。（8）二路歸并排序（merge sort）。（9）基數(shù)排序。（10）各種內(nèi)部排序算法的比較。（11）內(nèi)部排序算法的應(yīng)用。 離散數(shù)學(xué)考試大綱一、 考試要求：1、掌握命題邏輯和謂詞邏輯的基本概念及邏輯推理；2、掌握集合、關(guān)系、函數(shù)的基本概念，集合與關(guān)系的各種運(yùn)算方法；3、掌握?qǐng)D與樹(shù)的基本概念及表示方法；3、掌握形式語(yǔ)言與自動(dòng)機(jī)的基本概念與基本原理。二、 考試內(nèi)容：1、數(shù)理邏輯（1）命題邏輯：命題及其表示法；聯(lián)結(jié)詞；命題公式與翻譯；真值表與等價(jià)公式；重言式與蘊(yùn)

4、含式；對(duì)偶與范式；推理理論；數(shù)理邏輯應(yīng)用。（2）謂詞邏輯：謂詞的概念與表示；命題函數(shù)與量詞；謂詞公式與翻譯；變?cè)募s束；謂詞演算的等價(jià)式與蘊(yùn)含式；前束范式；謂詞演算的推理理論。2、集合論（1）集合與關(guān)系：集合的概念和表示法；集合的運(yùn)算；包含排斥原理；序偶與笛卡爾積；關(guān)系及其表示；關(guān)系的性質(zhì)；復(fù)合關(guān)系和逆關(guān)系；關(guān)系的閉包運(yùn)算；集合的劃分和覆蓋； 10等價(jià)關(guān)系與等價(jià)類(lèi)； 11相容關(guān)系； 12序關(guān)系。（2）函數(shù)：函數(shù)的概念；逆函數(shù)和復(fù)合函數(shù)；特征函數(shù)與模糊子集；基數(shù)的概念；可數(shù)集與不可數(shù)集；基數(shù)的比較。3、代數(shù)系統(tǒng)（1）代數(shù)結(jié)構(gòu)：代數(shù)系統(tǒng)的引入；運(yùn)算及其性質(zhì)；半群；群與子群；阿貝爾群和循環(huán)群；置換群

5、與伯恩賽德定理；陪集與拉格朗日定理；同態(tài)與同構(gòu)；環(huán)與域。（2）格和布爾代數(shù)：格的概念；分配格；有補(bǔ)格；布爾代數(shù)；布爾表達(dá)式。4、圖論（1）圖論：圖的基本概念；路與回路；圖的矩陣表示；歐拉圖與漢密爾頓圖；平面圖；對(duì)偶圖與著色；樹(shù)與生成樹(shù)；根樹(shù)及其應(yīng)用。5、計(jì)算機(jī)科學(xué)中的應(yīng)用（1）形式語(yǔ)言與自動(dòng)機(jī)：串和語(yǔ)言；形式文法；有限狀態(tài)自動(dòng)機(jī)；有限狀態(tài)機(jī)的簡(jiǎn)化；有限狀態(tài)機(jī)與正則語(yǔ)言。 數(shù)據(jù)庫(kù)原理考試大綱一、 考試要求：1、理解數(shù)據(jù)庫(kù)的基本概念；把握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。2、把握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。3、能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行

6、問(wèn)題求解。二、 考試內(nèi)容：1、數(shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ)（1）數(shù) 據(jù) 模 型 （2）數(shù)據(jù)庫(kù)系統(tǒng)結(jié)構(gòu) （3）數(shù)據(jù)庫(kù)系統(tǒng)的組成 2、關(guān)系理論（1）關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義（2）關(guān)系操作（3）關(guān)系的完整性 （4）關(guān)系代數(shù) （5）關(guān)系演算（6）關(guān)系的規(guī)范化（7）模式的分解3、關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語(yǔ)言SQL（1）數(shù)據(jù)定義 （2）數(shù)據(jù)查詢(xún) （3）數(shù)據(jù)更新 （4）視圖 4、數(shù)據(jù)庫(kù)安全性（1）數(shù)據(jù)庫(kù)安全性控制 （2）視圖機(jī)制（3）審計(jì) （4）數(shù)據(jù)加密5、數(shù)據(jù)庫(kù)完整性（1）實(shí)體完整性（2）參照完整性（3）用戶(hù)定義的完整性 （4）完整性約束命名子句（5）觸發(fā)器 計(jì)算機(jī)基礎(chǔ)及程序設(shè)計(jì)考試大綱一、 考試要求：1、掌握計(jì)算機(jī)系統(tǒng)的組成，掌握計(jì)算機(jī)中數(shù)據(jù)的表示及運(yùn)算方法；2、掌握操作系統(tǒng)的基本概念；3、掌握計(jì)算機(jī)信息安全的基本概念；4、掌握Windows XP、Windows2007、Word、Excel、Powerpoint的基本操作；5、掌握C語(yǔ)言的語(yǔ)法結(jié)構(gòu)，并能使用C語(yǔ)言編寫(xiě)簡(jiǎn)單的程序。二、 考試內(nèi)容：1、計(jì)算機(jī)基礎(chǔ)（1）計(jì)算機(jī)系統(tǒng)的組成 （2）計(jì)算機(jī)中數(shù)據(jù)的表示方法（3）二進(jìn)制數(shù)的運(yùn)算方法（4）數(shù)制之間的轉(zhuǎn)換2、操作系統(tǒng)（1）操作系統(tǒng)的作用（2）進(jìn)程及進(jìn)程調(diào)度3、計(jì)算機(jī)信息安全（1）計(jì)算機(jī)病毒及其原理（2）計(jì)算機(jī)安全常識(shí)