為了幫助廣大考生復(fù)習(xí)備考，也應(yīng)廣大考生的要求，現(xiàn)提供我校自命題專業(yè)課的考試大綱供考生下載?？忌趶?fù)習(xí)備考時(shí)，應(yīng)全面復(fù)習(xí)，我校自命題專業(yè)課的考試大綱僅供參考。

    上海電力大學(xué)2021年碩士研究生入學(xué)復(fù)試《算法與程序設(shè)計(jì)基礎(chǔ)》課程考試大綱

    課程名稱算法與程序設(shè)計(jì)基礎(chǔ)

    參考書目[1]嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，清華大學(xué)出版社，2009

    [2]數(shù)據(jù)結(jié)構(gòu)與算法(C語言版第2版高等院校計(jì)算機(jī)教育系列教材)作者：郭龍?jiān)?/胡虛懷//何光明出版社：清華大學(xué)

    出版時(shí)間：2010-03-01

    復(fù)習(xí)的總體要求

    掌握算法與程序設(shè)計(jì)的基本方法，理解算法、程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)；在掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度和空間復(fù)雜度的分析；能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解，具備采用高級(jí)程序語言設(shè)計(jì)程序與實(shí)現(xiàn)算法的能力。

    復(fù)習(xí)內(nèi)容

    1.數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語

    考核要求：理解算法、程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，掌握數(shù)據(jù)結(jié)構(gòu)的概念以及分類、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法的概念、算法的特性、算法的目標(biāo)、算法效率的度量、算法的存儲(chǔ)空間需求。

    考核知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)及算法的概念；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；算法的定義及特性；算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。

    2.線性表、棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、基本運(yùn)算及應(yīng)用

    考核要求：了解線性表的結(jié)構(gòu)特點(diǎn)；掌握順序的和鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)各自特點(diǎn)；熟練掌握線性表的操作，以及鏈表的指針運(yùn)算和各種鏈表的操作；理解循環(huán)鏈表以及雙向鏈表。掌握棧和隊(duì)列的表示和實(shí)現(xiàn)；理解棧和隊(duì)列的操作特點(diǎn)；理解循環(huán)隊(duì)列以及其相關(guān)操作。

    考核知識(shí)點(diǎn)：線性表、棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其存儲(chǔ)特點(diǎn)；線性表的基本操作在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn)；各種變形鏈表(循環(huán)鏈表、雙向鏈表、帶頭結(jié)點(diǎn)的鏈表等)的表示和基本操作的實(shí)現(xiàn)；遞歸過程的特點(diǎn)及實(shí)現(xiàn)方法；循環(huán)隊(duì)列的判滿、判空方法。

    3.串和數(shù)組、廣義表的存儲(chǔ)結(jié)構(gòu)、基本運(yùn)算及應(yīng)用

    考核要求：理解串的存儲(chǔ)結(jié)構(gòu)；理解串的相關(guān)操作；掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)；掌握矩陣的壓縮存儲(chǔ)；理解特殊矩陣以及稀疏矩陣；理解廣義表的有關(guān)概念及其與線性表的關(guān)系。

    考核知識(shí)點(diǎn)：串的兩種存儲(chǔ)表示，串上實(shí)現(xiàn)的模式匹配算法及其時(shí)間性能分析；稀疏矩陣的存儲(chǔ)方法和基本運(yùn)算的實(shí)現(xiàn)(轉(zhuǎn)置、矩陣加法等)；廣義表的定義及其求表頭和表尾的運(yùn)算。

    4.樹和二叉樹的存儲(chǔ)結(jié)構(gòu)、遍歷算法及應(yīng)用

    考核要求：掌握樹和二叉樹的基本定義；熟練掌握二叉樹的性質(zhì)；掌握二叉樹的存儲(chǔ)結(jié)構(gòu)；掌握遍歷二叉樹和線索二叉樹；理解樹和森林的概念以及存儲(chǔ)結(jié)構(gòu)；掌握森林與二叉樹的轉(zhuǎn)換；理解樹和森林的遍歷；掌握赫夫曼樹及其應(yīng)用；理解赫夫曼編碼。

    考核知識(shí)點(diǎn)：二叉樹和樹的遞歸定義、基本術(shù)語、基本性質(zhì)、滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)，以及相互轉(zhuǎn)換算法；線索二叉樹、二叉排序樹的構(gòu)建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構(gòu)建和應(yīng)用。

    5.圖的存儲(chǔ)結(jié)構(gòu)、遍歷算法及應(yīng)用

    考核要求：理解圖的定義和術(shù)語；熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)；熟練掌握?qǐng)D的遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索；理解圖的連通性問題；理解無向圖的連通分量和生成樹；掌握最小生成樹；了解有向無環(huán)圖及其應(yīng)用；掌握最短路徑。

    考核知識(shí)點(diǎn)：圖的基本概念和術(shù)語；圖的基本存儲(chǔ)方法：鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、逆鄰接表、十字鏈表；圖的遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；圖的基本應(yīng)用：最小生成樹、最短路徑。

    6.靜態(tài)查找表、動(dòng)態(tài)查找表和哈希表(包括二叉排序樹、AVL樹)

    考核要求：熟練掌握靜態(tài)查找表的順序表的查找、折半查找、分塊查找；掌握動(dòng)態(tài)查找表；掌握二叉排序樹；理解平衡二叉樹；掌握哈希表；掌握哈希函數(shù)的構(gòu)造方法和處理沖突的方法；了解哈希表的查找及其分析。

    考核知識(shí)點(diǎn)：靜態(tài)查找表、動(dòng)態(tài)查找表和哈希表上的查找方法；哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略；各類查找算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

    7.五類內(nèi)部排序算法的算法思想、時(shí)間特性及穩(wěn)定性

    考核要求：五類內(nèi)部排序方法的基本思想、排序過程、算法實(shí)現(xiàn)、時(shí)間和空間性能的分析以及各種排序方法的比較和選擇。在熟悉這些內(nèi)容的基礎(chǔ)上，掌握五類排序的基本思想及排序過程以及排序算法的實(shí)現(xiàn)。

    考核知識(shí)點(diǎn)：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類排序算法的算法思想和時(shí)間復(fù)雜度；五類排序算法的特性、穩(wěn)定性及適用情形。

添加上海電力大學(xué)學(xué)姐微信，或微信搜索公眾號(hào)“考研派小站”，關(guān)注[考研派小站]微信公眾號(hào)，在考研派小站微信號(hào)輸入[上海電力大學(xué)考研分?jǐn)?shù)線、上海電力大學(xué)報(bào)錄比、上海電力大學(xué)考研群、上海電力大學(xué)學(xué)姐微信、上海電力大學(xué)考研真題、上海電力大學(xué)專業(yè)目錄、上海電力大學(xué)排名、上海電力大學(xué)保研、上海電力大學(xué)公眾號(hào)、上海電力大學(xué)研究生招生）]即可在手機(jī)上查看相對(duì)應(yīng)上海電力大學(xué)考研信息或資源。