為了幫助廣大考生復習備考，也應廣大考生的要求，現提供我校自命題專業課的考試大綱供考生下載。考生在復習備考時，應全面復習，我校自命題專業課的考試大綱僅供參考。

    上海電力大學2021年碩士研究生入學復試《算法與程序設計基礎》課程考試大綱

    課程名稱算法與程序設計基礎

    參考書目[1]嚴蔚敏.《數據結構》(C語言版)，清華大學出版社，2009

    [2]數據結構與算法(C語言版第2版高等院校計算機教育系列教材)作者：郭龍源//胡虛懷//何光明出版社：清華大學

    出版時間：2010-03-01

    復習的總體要求

    掌握算法與程序設計的基本方法，理解算法、程序設計與數據結構的關系。理解數據結構的基本概念，掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現；在掌握基本的數據處理原理和方法的基礎上，能夠對算法進行基本的時間復雜度和空間復雜度的分析；能夠選擇合適的數據結構和方法進行問題求解，具備采用高級程序語言設計程序與實現算法的能力。

    復習內容

    1.數據結構及算法的相關概念和術語

    考核要求：理解算法、程序設計與數據結構的關系，掌握數據結構的概念以及分類、抽象數據類型的表示與實現、算法的概念、算法的特性、算法的目標、算法效率的度量、算法的存儲空間需求。

    考核知識點：數據結構及算法的概念；數據的邏輯結構和存儲結構；算法的定義及特性；算法時間復雜度和空間復雜度的分析方法。

    2.線性表、棧、隊列的存儲結構、基本運算及應用

    考核要求：了解線性表的結構特點；掌握順序的和鏈式的存儲結構各自特點；熟練掌握線性表的操作，以及鏈表的指針運算和各種鏈表的操作；理解循環鏈表以及雙向鏈表。掌握棧和隊列的表示和實現；理解棧和隊列的操作特點；理解循環隊列以及其相關操作。

    考核知識點：線性表、棧和隊列的存儲結構及其存儲特點；線性表的基本操作在順序存儲及鏈式存儲上的實現；各種變形鏈表(循環鏈表、雙向鏈表、帶頭結點的鏈表等)的表示和基本操作的實現；遞歸過程的特點及實現方法；循環隊列的判滿、判空方法。

    3.串和數組、廣義表的存儲結構、基本運算及應用

    考核要求：理解串的存儲結構；理解串的相關操作；掌握數組的存儲結構；掌握矩陣的壓縮存儲；理解特殊矩陣以及稀疏矩陣；理解廣義表的有關概念及其與線性表的關系。

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

    4.樹和二叉樹的存儲結構、遍歷算法及應用

    考核要求：掌握樹和二叉樹的基本定義；熟練掌握二叉樹的性質；掌握二叉樹的存儲結構；掌握遍歷二叉樹和線索二叉樹；理解樹和森林的概念以及存儲結構；掌握森林與二叉樹的轉換；理解樹和森林的遍歷；掌握赫夫曼樹及其應用；理解赫夫曼編碼。

    考核知識點：二叉樹和樹的遞歸定義、基本術語、基本性質、滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲及鏈式存儲，以及相互轉換算法；線索二叉樹、二叉排序樹的構建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構建和應用。

    5.圖的存儲結構、遍歷算法及應用

    考核要求：理解圖的定義和術語；熟練掌握圖的存儲結構；熟練掌握圖的遍歷方法：深度優先搜索和廣度優先搜索；理解圖的連通性問題；理解無向圖的連通分量和生成樹；掌握最小生成樹；了解有向無環圖及其應用；掌握最短路徑。

    考核知識點：圖的基本概念和術語；圖的基本存儲方法：鄰接矩陣、關聯矩陣、鄰接表、逆鄰接表、十字鏈表；圖的遍歷算法：深度優先搜索算法和廣度優先搜索算法；圖的基本應用：最小生成樹、最短路徑。

    6.靜態查找表、動態查找表和哈希表(包括二叉排序樹、AVL樹)

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

    考核知識點：靜態查找表、動態查找表和哈希表上的查找方法；哈希函數的基本構造方法，解決地址沖突的基本策略；各類查找算法的時間復雜度和空間復雜度。

    7.五類內部排序算法的算法思想、時間特性及穩定性

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

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

添加上海電力大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[上海電力大學考研分數線、上海電力大學報錄比、上海電力大學考研群、上海電力大學學姐微信、上海電力大學考研真題、上海電力大學專業目錄、上海電力大學排名、上海電力大學保研、上海電力大學公眾號、上海電力大學研究生招生）]即可在手機上查看相對應上海電力大學考研信息或資源。