上海應用技術大學

《數據結構與算法》(816)考試大綱

一、適用對象

2021研究生入學考試

二、試卷結構

滿分：150分

三、考試時間與方式

120分鐘，閉卷。

四、考試內容與要求

(一)C語言部分

1. 程序設計的基本概念

1.1用計算機進行數據處理的基本方法(掌握)

1.2用流程圖表達算法的基本方法(掌握)

1.3 程序設計語言運行環境(了解)

2. 基本數據類型及基本運算

2.1基本數據類型、變量及其定義方法(掌握)

2.2數據在內存中的存儲形式(了解)

2.3運算符、表達式的表示方法及運算規則(掌握)

2.4各種類型數據之間的關系和轉換(掌握)

2.5培養獨立編寫C程序的初步能力(掌握)

3. 輸入/輸出

3.1輸入函數的調用(掌握)

3.2輸出函數的調用(掌握)

3.3輸出格式的控制(掌握)

3.4培養獨立編寫完整C程序的能力(掌握)

4. 流程控制

4.1賦值語句的使用(掌握)

4.2控制語句的使用(掌握)

4.3控制語句的正確嵌套方法(掌握)

4.4程序的三種基本結構(理解)

4.5三種基本結構程序的設計方法(掌握)

重點：程序的三種基本結構

難點：控制語句的正確嵌套方法

5. 數組

5.1一維、二維數組的定義、初始化和引用(掌握)

5.2多維數組的定義、初始化和引用(了解)

5.3字符數組的使用及字符串的處理方法(掌握)

5.4通過對數組的編程，鞏固和提升選擇結構，重復結構程序設計能力(掌握)

重點：數組的定義、初始化和引用

難點：字符數組的使用

6. 函數

6.1函數定義和調用方法(掌握)

6.2函數的嵌套調用，理解遞歸調用方法(掌握)

6.3局部變量、全局變量的用法(掌握)

6.4變量的存儲類別，變量的作用域和生存期(掌握)

6.5內部函數和外部函數 (了解)

重點：函數定義和調用方法

難點：函數的嵌套調用

7. 編譯預處理

7.1宏定義和“文件包含”處理(掌握)

7.2條件編譯(了解)

8. 指針

8.1指針的概念(理解)

8.2指針變量的定義、引用及指針變量作為函數參數(掌握)

8.3數組指針和指向數組的指針變量(掌握)

8.4字符串指針和指向字符串的指針變量(掌握)

8.5返回指針的指針函數、指針數組(了解)

重點：指針的概念

難點：指針變量的定義、引用

9. 結構體

9.1結構體的定義和引用(掌握)

9.2結構體指針的使用(掌握)

9.3結構體數組的使用(掌握)

10. 文件

10.1文件的類型(了解)

10.2文本文件的基本操作方法(掌握)

10.3二進制文件(了解)

(二)數據結構部分

1.線性表

1.1線性表及其邏輯結構

1.2線性表的順序存儲結構(重點)

1.3線性表的鏈式存儲結構(重點)

1.4線性表的應用

1.5有序表

2. 棧和隊列

2.1棧(重點)

2.2隊列(重點)

3. 串

3.1串的基本概念

3.2 串的存儲結構

3.3串的模式匹配

4. 數組和稀疏矩陣

4.1數組

4.2稀疏矩陣

5. 遞歸

5.1什么是遞歸

5.2遞歸調用的實現原理

5.3遞歸算法的設計

5.4遞歸算法到非遞歸算法的轉換

6. 樹形結構(重點)

6.1樹的基本概念

6.2 二叉樹概念和性質

6.3二叉樹存儲結構

6.4二叉樹的遍歷

6.5二叉樹的基本運算及其實現

6.6二叉樹的構造

6.7線索二叉樹(了解)

6.8哈夫曼樹

7. 廣義表

7.1廣義表的定義

7.2廣義表的存儲結構

7.3廣義表的運算

8. 圖

8.1圖的基本概念(重點)

8.2圖的存儲結構(重點)

8.3圖的遍歷(重點)

8.4生成樹和最小生成樹(重點)

8.5最短路徑(重點)

9. 查找

9.1查找的基本概念(重點)

9.2線性表的查找(重點)

9.3樹表的查找

9.4哈希表查找

10. 內排序(重點)

10.1排序的基本概念

10.2插入排序

10.3交換排序

10.4選擇排序

10.5歸并排序

10.6基數排序

10.7各種內排序方法的比較和選擇

對算法的要求：掌握線性表的順序、鏈式表示和實現及應用等算法，棧和隊列的順序、鏈式表示和實現算法，二叉樹的二叉鏈表存儲表示及遍歷的遞歸算法，利用遞歸思想求二叉樹高度、結點數、左右子樹互換等算法，圖的遍歷算法，順序查找及二分查找算法，二叉排序樹的查找算法，各種內部排序算法等。

五、參考書目

[1] C程序設計教程(第四版)，崔武子著，清華大學出版社，2015.6

[2] C程序設計(第四版)，譚浩強著，清華大學出版社，2010.6

[3] 數據結構教程，李春葆(第四版)，清華大學出版社，2013.1