2020年?yáng)|北電力大學(xué)計(jì)算機(jī)學(xué)院初試

1、初試科目考試大綱“數(shù)據(jù)結(jié)構(gòu) ”考試大綱一、考試的學(xué)科范圍數(shù)據(jù)結(jié)構(gòu)課程教學(xué)（大綱）基本要求的所有內(nèi)容。二、評(píng)價(jià)目標(biāo)主要考查考生對(duì)數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)理論、基本知識(shí)掌握和運(yùn)用的情況， 要求考生應(yīng)掌握以下有關(guān)知識(shí)：1. 數(shù)據(jù)結(jié)構(gòu)的基本概念：理解數(shù)據(jù)結(jié)構(gòu)的基本概念和常用術(shù)語(yǔ)，掌握算法的 定義及特性，了解分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度的方法。2. 線(xiàn)性表：理解線(xiàn)性表的基本概念；掌握順序表的各種基本操作；掌握單鏈 表、雙向鏈表的特點(diǎn)及各種基本操作；會(huì)運(yùn)用線(xiàn)性表解決實(shí)際問(wèn)題。3. 棧和隊(duì)列：理解棧的定義及其基本運(yùn)算；掌握順序棧和鏈棧的特點(diǎn)及各種 操作實(shí)現(xiàn)；理解隊(duì)列的定義及其基本運(yùn)算；掌握循環(huán)隊(duì)列的特點(diǎn)和各種

2、操作實(shí) 現(xiàn)；會(huì)運(yùn)用棧和隊(duì)列解決實(shí)際問(wèn)題。4. 數(shù)組和廣義表：理解數(shù)組和廣義表的基本概念；掌握二維數(shù)組的存儲(chǔ)結(jié)構(gòu) 和稀疏矩陣的壓縮存儲(chǔ)方法。5. 樹(shù)和二叉樹(shù)：理解樹(shù)和二叉樹(shù)的概念；掌握二叉樹(shù)的性質(zhì)；掌握二叉樹(shù)的 存儲(chǔ)結(jié)構(gòu)以及在該存儲(chǔ)結(jié)構(gòu)下各種基本操作的實(shí)現(xiàn)；掌握樹(shù)、森林與二叉樹(shù)之 間的轉(zhuǎn)換關(guān)系；掌握哈夫曼樹(shù)的定義與應(yīng)用。6. 圖：理解圖的基本概念；掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)；掌握?qǐng)D 的深度、廣度優(yōu)先搜索算法的基本思想；理解最小生成樹(shù)的概念；掌握最短路 徑算法的實(shí)現(xiàn)思想；掌握拓?fù)渑判虻母拍罴八惴▽?shí)現(xiàn)思想。7. 查找：理解查找的基本概念；掌握順序查找、折半查找、分塊查找的特點(diǎn) 和方法；掌握二

3、叉排序樹(shù)的構(gòu)造和查找方法；了解平衡二叉樹(shù)的構(gòu)造和查找方 法；掌握哈希表的構(gòu)造和查找方法。8. 排序：理解內(nèi)部排序、外部排序、穩(wěn)定排序、不穩(wěn)定排序等概念；掌握直 接插入排序、冒泡排序、直接選擇排序等簡(jiǎn)單的排序方法和特點(diǎn)；掌握希爾排 序、快速排序、堆排序和歸并排序等高效排序方法和特點(diǎn)；了解基數(shù)排序的基 本思想。三、試題主要類(lèi)型1.答題時(shí)間： 180 分鐘2. 試題主要類(lèi)型：選擇題，簡(jiǎn)答題，解答題，算法題四、考查要點(diǎn)（一）數(shù)據(jù)結(jié)構(gòu)的基本概念：1. 數(shù)據(jù)結(jié)構(gòu)的基本概念。2. 算法的概念3. 算法分析方法（算法的時(shí)間、空間復(fù)雜度）（二）線(xiàn)性表：1. 線(xiàn)性表的概念2. 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)及運(yùn)算算法3.

4、 線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)及運(yùn)算算法4. 線(xiàn)性表的典型應(yīng)用（三）棧和隊(duì)列：1. 棧的定義及基本運(yùn)算算法2. 隊(duì)列的定義及基本運(yùn)算算法3. 棧的典型應(yīng)用4. 隊(duì)列的典型應(yīng)用四）數(shù)組和廣義表：1. 數(shù)組的順序表示和實(shí)現(xiàn)2. 矩陣的壓縮存儲(chǔ)3. 廣義表的定義及其存儲(chǔ)結(jié)構(gòu)（五）樹(shù)和二叉樹(shù)：1. 樹(shù)的定義及基本術(shù)語(yǔ)2. 樹(shù)的表示3. 樹(shù)的存儲(chǔ)結(jié)構(gòu)4. 二叉樹(shù)的定義及性質(zhì)5. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6. 二叉樹(shù)的遍歷算法7. 線(xiàn)索二叉樹(shù)8. 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換9. 哈夫曼樹(shù)的構(gòu)造方法及應(yīng)用（六）圖：1. 圖的定義及基本術(shù)語(yǔ)2. 圖的存儲(chǔ)結(jié)構(gòu)3. 圖的遍歷方法4. 圖的聯(lián)通性5. 圖的最短路徑算法6.A0V網(wǎng)與

5、拓?fù)渑判?.A0E網(wǎng)與關(guān)鍵路徑（七）查找：1 .查找的基本概念2. 靜態(tài)查找的順序查找、折半查找、分塊查找算法3. 動(dòng)態(tài)查找表的基本概念4. 二叉排序樹(shù)的構(gòu)造方法及查找5. 平衡二叉樹(shù)查找6. 哈希法查找（八）排序：1 .排序的基本概念2 .直接插入排序的基本思想和特點(diǎn)3 .希爾排序的基本思想和特點(diǎn)4. 折半插入排序的基本思想和特點(diǎn)5. 冒泡排序的基本思想和特點(diǎn)6 .快速排序的基本思想和特點(diǎn)7. 簡(jiǎn)單選擇排序的基本思想和特點(diǎn)8. 堆排序的基本思想和特點(diǎn)9 .歸并排序的基本思想和特點(diǎn)10. 基數(shù)排序的基本思想和特點(diǎn)11. 各類(lèi)排序算法的時(shí)間空、間復(fù)雜度的比較五、主要參考書(shū)目1. 曲朝陽(yáng)主編，數(shù)據(jù)

6、結(jié)構(gòu)，北京：中國(guó)電力出版社2. 嚴(yán)蔚敏主編，數(shù)據(jù)結(jié)構(gòu)，北京：清華大學(xué)出版社 2016“程序設(shè)計(jì)方法 ”考試大綱一、考試的學(xué)科范圍程序設(shè)計(jì)方法課程考試的主要內(nèi)容：數(shù)據(jù)類(lèi)型及其運(yùn)算、基本語(yǔ)句、順序 程序設(shè)計(jì)、選擇結(jié)構(gòu)程序設(shè)計(jì)、循環(huán)結(jié)構(gòu)程序設(shè)計(jì)、數(shù)組、函數(shù)、指針、結(jié)構(gòu) 體、文件。二、評(píng)價(jià)目標(biāo)主要考察C語(yǔ)言程序設(shè)計(jì)的基礎(chǔ)知識(shí)，數(shù)據(jù)類(lèi)型定義及使用，順序程序設(shè) 計(jì)、選擇結(jié)構(gòu)程序設(shè)計(jì)和循環(huán)結(jié)構(gòu)程序設(shè)計(jì)方法，數(shù)組定義及使用，函數(shù)定義 及調(diào)用，指針定義及使用，結(jié)構(gòu)體以及文件操作。要求理解和掌握 C語(yǔ)言程序 設(shè)計(jì)的基本方法和基本技能，編寫(xiě)和調(diào)試程序的能力。要求考生應(yīng)掌握以下有 關(guān)知識(shí)：1、介紹程序設(shè)計(jì)的基本思想、

7、基本要求，掌握算法的基本知識(shí)，數(shù)據(jù)類(lèi) 型；2、掌握順序結(jié)構(gòu)程序的設(shè)計(jì)；3、掌握選擇結(jié)構(gòu)程序的設(shè)計(jì)；4、掌握循環(huán)結(jié)構(gòu)程序的設(shè)計(jì)；5、掌握一維數(shù)組、二維數(shù)組的使用方法；6、掌握函數(shù)的定義、函數(shù)的調(diào)用方法；7、熟悉指針的含義，指針的重要性，學(xué)會(huì)數(shù)組指針的定義和使用方法；8、熟悉結(jié)構(gòu)的定義、引用和初始化方法；指向結(jié)構(gòu)體類(lèi)型數(shù)據(jù)的指針的定義和 使用方法； 9、了解文件定義，文件操作命令，打開(kāi)、關(guān)閉、讀寫(xiě)、定位、出錯(cuò) 檢測(cè)等。三、試題主要類(lèi)型1、答題時(shí)間： 180 分鐘2、程序設(shè)計(jì)方法試題類(lèi)型：選擇題、填空題、編程題四、考查要點(diǎn)（一）數(shù)據(jù)類(lèi)型及其運(yùn)算1. C的數(shù)據(jù)類(lèi)型及其定義方法2. C運(yùn)算符的種類(lèi)、運(yùn)算

8、優(yōu)先級(jí)和結(jié)合性3. C 表達(dá)式類(lèi)型（賦值表達(dá)式、算術(shù)表達(dá)式、關(guān)系表達(dá)式、邏輯表達(dá)式、條 件表達(dá)式、逗號(hào)表達(dá)式）（二）基本語(yǔ)句1. 表達(dá)式語(yǔ)句，空語(yǔ)句，復(fù)合語(yǔ)句2. 數(shù)據(jù)的輸入與輸出，輸入輸出函數(shù)的調(diào)用3. 順序結(jié)構(gòu)程序設(shè)計(jì)（三）選擇結(jié)構(gòu)程序設(shè)計(jì)1用if語(yǔ)句實(shí)現(xiàn)選擇結(jié)構(gòu)2. 用 switch 語(yǔ)句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)3. 選擇結(jié)構(gòu)的嵌套4. 選擇結(jié)構(gòu)程序設(shè)計(jì)（四）循環(huán)結(jié)構(gòu)程序設(shè)計(jì)1. for 循環(huán)結(jié)構(gòu)2. while和do while循環(huán)結(jié)構(gòu)3. 循環(huán)的嵌套4. 循環(huán)結(jié)構(gòu)程序設(shè)計(jì)（五）數(shù)組的定義和引用1. 一維數(shù)組和二維數(shù)組的定義、初始化和引用2. 字符串與字符數(shù)組3. 數(shù)組的應(yīng)用（六）函數(shù)1. 函數(shù)的定義方法2. 函數(shù)的類(lèi)型和返回值3. 形式參數(shù)與實(shí)在參數(shù)，參數(shù)值的傳遞4. 函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用（七）指針1.指針與指針變量的概念，指針與地址運(yùn)算符2.變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針以及指向變量、數(shù)組、字符串 指針變量3. 用指針作函數(shù)參數(shù)4. 指針應(yīng)用（八）結(jié)構(gòu)體1.結(jié)構(gòu)體類(lèi)型數(shù)據(jù)的定義方法和引用方法2.單向鏈表的建立、輸出（九）